·477· 朱林立，等：本体学习算法的两类L00一致稳定性和广义界 第3期 证明对任意两个本体样本集S和S'(只有 即f,)+sp∑-o 1下 对应第k个元素不同，分别记为z和z,其他均相 S.T-Do feri:n 人 同)，令 @(S.S)=sup[Rp(f)-Rs-(f)] feri,n 利用简单计算以及本体亏损函数界为1的假 2三.(Y 另一方面，固定n>0,根据上确界的定义，对 设，可以得到： 任意S∈Z,存在使得 ⊙(S,S)-⊙(S',S)= [O(S,S)-⊙(S,S】+[O(S,S)-O(S',S] PR-e,I-7≤R6)-R,U6 ΘS,S)-⊙(S,S)≤ 0Pn-&UI-R-A列s 根据R(f5)的定义，有 BR6刃=5B6训=sE。6,别 2wa-n对 另外，可知 @(S.S)-@(S',S)=sup[Rp(f)-Rs-(f)]- Ek,】=sEg5.=5-Bog6川 其中S表示将本体数据集S中的：和~D sup[Rp(f)-Rs-(f)] 相交换，进而有 根据上确界的定义可知，对任意)>0，存在 B[oS,SJ≤，R(U)-R()+n= f∈Fs,使得sup[Rf)-R(fD】-n≤[Rof)-R(fD】。 s-思06,2]-s5ns6,2]+n 由F=(Fs)sz的LO0一致稳定B,通过类似定 理4中的讨论，可知存在∈Fs使得对任意：，有 5n5ngs.20-6,2]+刀 f,)-1f,z引≤2β。进而 sn5g06r,)-乐.2训+刀 ⊙(S,S)-O(S',S)≤ [Rn(f月-Rs,(f】+n-sup[Rn(f)-Rs.(f]≤ s-5gW5,-15e,+5,2小-5，+7≤ (10) [Rp(f)-Rs-(f)]+-[Rp(f')-Rs-(f)]= 52g5,3-5,3H [Ro(f月-R(f】+n+[R.(f)-R(f]≤4B+n 5-Bog6,)-16,2刃+n≤27+刀 由于7>0是任意的，式(10)意味着⊙(S,S)- (12) 其中，S表示在本体数据集S中删除元素：得到 0S,S)≤4g。从而有06，S)-06,S)≤48+。 的集合。由于式(12)对所有7>0成立，从而有 通过文献[25]中的McDiarmid不等式可知， E[©(S,S】≤2。 对任意6>0，式(11)以概率至少1-6成立。 6- 结合E©S,S1≤2，E[ΘS,S]≤2三(9和 1 式(11)，可知定理5成立。 oS,S)≤5[©S,SJ+1+4ng9) (11) 2n 沿用定理1中的标记，S∈Zm"为多重本体数 下面计算关于拉德马赫复杂度三.（和式 据集，它由m个本体数据集S,S2,…,Sm构成，每 (1)中，EΘS,S川项的关系： 个数据集的容量均为n。第I个本体子数据集的第 个元素记为S,其中1∈(1,2，…，m。定理6刻画了 .s)- 多重本体数据集框架下LOO-CV稳定x的作用。 马LER(n小-ns 定理6设F=(Fs)s2为本体数据依赖假设集 族，存在LOO-CV稳定x,则 风n-&n 25aePs)=rd-ls2x 52动- 其中S将本体数据集S中的：和z~D相交换。 证明通过推导可知 2.5a6-Acd-S ′ z z ′ 证明 对任意两个本体样本集 S 和 （只有 对应第 k 个元素不同，分别记为 和 ，其他均相 同），令 Θ(S,S ′ ) = sup f ∈FS [RD(f)−Rˆ S ′ (f)] 利用简单计算以及本体亏损函数界为 1 的假 设，可以得到： Θ(S,S )−Θ(S ′ ,S ′ ) = [Θ(S,S )−Θ(S,S ′ )]+[Θ(S,S ′ )−Θ(S ′ ,S ′ )] Θ(S,S )−Θ(S,S ′ ) ⩽ sup f ∈FS [ [RD(f)−Rˆ S (f)]−[RD(f)−Rˆ S ′ (f)]] ⩽ sup f ∈FS 1 n ∑n i=1 (l(f,z)−l(f,z ′ )) ⩽ 1 n Θ(S,S ′ )−Θ(S ′ ,S ′ ) = sup f ∈FS [RD(f)−Rˆ S ′ (f)]− sup f ∈FS ′ [RD(f)−Rˆ S ′ (f)] η > 0 f ∈ FS sup f ∈FS [RD(f)−Rˆ S ′ (f)]−η ⩽ [RD(f)−Rˆ S ′ (f)] 根据上确界的定义可知，对任意 ，存在 ，使得 。 F = (FS )S ∈Z n β f ′ ∈ FS ′ |l(f ′ ,z)−l(f,z)| ⩽ 2β 由 的 LOO 一致稳定 ，通过类似定 理 4 中的讨论，可知存在 使得对任意 z，有 。进而 Θ(S,S ′ )−Θ(S ′ ,S ′ ) ⩽ [RD(f)−Rˆ S ′ (f)]+η− sup f ∈FS ′ [RD(f)−Rˆ S ′ (f)] ⩽ [RD(f)−Rˆ S ′ (f)]+η−[RD(f ′ )−Rˆ S ′ (f ′ )] = [RD(f)−RD(f ′ )]+η+[Rˆ S ′ (f ′ )−Rˆ S ′ (f)] ⩽ 4β+η (10) η > 0 Θ(S,S ′ )− Θ(S ′ ,S ′ ) ⩽ 4β Θ(S,S )−Θ(S ′ ,S ′ ) ⩽ 4β+ 1 n 由于 是任意的，式 (10) 意味着 。从而有 。 δ > 0 1−δ 通过文献 [25] 中的 McDiarmid 不等式可知， 对任意 ，式 (11) 以概率至少 成立。 Θ(S,S ) ⩽ E S∼Dn [Θ(S,S )]+(1+4nβ) vut log 1 δ 2n (11) Ξn(Ψ) E S∼Dn [Θ(S,S )] 下面计算关于拉德马赫复杂度 和 式 (11) 中 项的关系： E S∼Dn [Θ(S,S )] = E S∼Dn [ sup f ∈FS [ RD(f)−Rˆ S (f) ] ] = E S∼Dn [ sup f ∈FS [ E T∼Dn [ Rˆ T (f) ] −Rˆ S (f) ] ] ⩽ E S,T∼Dn [ sup f ∈FS [ Rˆ T (f)−Rˆ S (f) ] ] = E S,T∼Dn   sup f ∈FS 1 n ∑n i=1 [ l(f,z T i )−l(f,z S i ) ]   = E S,T∼Dn   E σ   sup f ∈F σ S,T 1 n ∑n i=1 σi [ l(f,z T i )−l(f,z S i ) ]     ⩽ E S,T∼Dn ,σ   sup f ∈F σ S,T 1 n ∑n i=1 σi l(f,z T i )+ sup f ∈F σ S,T 1 n ∑n i=1 −σi l(f,z S i )   = E S,T∼Dn ,σ   sup f ∈F σ S,T 1 n ∑n i=1 σi l(f,z T i )+ sup f ∈F −σ S,T 1 n ∑n i=1 −σi l(f,z S i )   = E S,T∼Dn ,σ   sup f ∈F σ S,T 1 n ∑n i=1 σi l(f,z T i )+ sup f ∈F σ S,T 1 n ∑n i=1 σi l(f,z S i )   = 2Ξn(Ψ) η > 0 S ∈ Z n fS 另一方面，固定 ，根据上确界的定义，对 任意 ，存在 使得 sup f ∈FS [RD(f)−Rˆ S (f)]−η ⩽ RD(fS )−Rˆ S (fS ) 根据 RD(fS ) 的定义，有 E S∼Dn [RD(fS )] = E S∼Dn [ E z∼D [l(fS ,z)]] = E S∼Dn ,z∼D [l(fS ,z)] 另外，可知 E S∼Dn [Rˆ S (fS )] = E S∼Dn ,z∼S [l(fS ,z)] = E S∼Dn ,z ′∼D,z∼S [l(fS z↔z ′ ,z ′ )] S z↔z ′ z ′ 其中 表示将本体数据集 S 中的 z 和 ∼ D 相交换，进而有 E S∼Dn [Θ(S,S )] ⩽ E S∼Dn [ RD(fS )−Rˆ S (fS ) ] +η = E S∼Dn ,z ′∼D [l(fS ,z ′ )]− E S∼Dn ,z ′∼D,z∼S [ l(fS z↔z ′ ,z ′ ) ] +η = E S∼Dn ,z ′∼D,z∼S [ l(fS ,z ′ )−l(fS z↔z ′ ,z ′ ) ] +η = E S∼Dn ,z ′∼D,z∼S [l(fS z↔z ′ ,z)−l(fS ,z)]+η = E S∼Dn ,z ′∼D,z∼S [l(fS z↔z ′ ,z)−l(fS \z ,z)+l(fS \z ,z)−l(fS ,z)]+η ⩽ E S∼Dn ,z ′∼D,z∼S [l(fS z↔z ′ ,z)−l(fS \z ,z)]+ E S∼Dn ,z ′∼D,z∼S [l(fS \z ,z)−l(fS ,z)]+η ⩽ 2 ¯χ+η (12) S \z η > 0 E S∼Dn [Θ(S,S )] ⩽ 2 ¯χ 其中， 表示在本体数据集 S 中删除元素 z 得到 的集合。由于式 (12) 对所有 成立，从而有 。 E S∼Dn [Θ(S,S )] ⩽ 2 ¯χ, E S∼Dn 结 合 [Θ(S,S )] ⩽ 2Ξn(Ψ) 和 式 (11)，可知定理 5 成立。 S ∈ Z m×n S 1,S 2,··· ,S m l i S l,i l ∈ {1,2,··· ,m} χ 沿用定理 1 中的标记， 为多重本体数 据集，它由 m 个本体数据集 构成，每 个数据集的容量均为 n。第 个本体子数据集的第 个元素记为 ，其中 。定理 6 刻画了 多重本体数据集框架下 LOO- CV 稳定 的作用。 F = (FS )S ∈Z n χ 定理 6 设 为本体数据依赖假设集 族，存在 LOO- CV 稳定 ，则 ∑m l=1 E S∼Dmn ,z ′∼D,z∼S l [ P[A(S ) = l] [ l(fS z↔z ′ l ,z)−l(fS l ,z) ]] ⩽ 2χ, S z↔z ′ l S l z ′ 其中 将本体数据集 中的 z 和 ∼ D 相交换。 证明 通过推导可知 ∑m l=1 E S∼Dmn ,z ′∼D,z∼S l [ P[A(S ) = l] [ l(fS z↔z ′ l ,z)−l(fS l ,z) ]] ⩽ ∑m l=1 E S∼Dmn ,z ′∼D,z∼S l [ P[A(S ) = l]× ·477· 朱林立，等：本体学习算法的两类 LOO 一致稳定性和广义界 第 3 期