·475· 朱林立，等：本体学习算法的两类L00一致稳定性和广义界 第3期 结合文献[23]中引理1.2可知： ha)=minL(Sa,z）+4yo ,BRM小-R[MS1≥8 In2 注意到： In ≤6 6 maxL(S,z）≤minL(Sa,)+8y ajEZ 0,无E∠ 从而式(2)成立。 可知： 式(1)证明：设L(S,z)=M(S,)-RM(S小，则易 L(S,2）-h(a≤4y 证L是关于分布D的无偏估计，对任意S∈Z都有 因此： R[LS]=0。由于M的取值范围在[0,1]内，因 此L取值范围是[-1,1]。由于 s545,= RMSJ-RoMS≤EMS,-MSv,a≤y Es,aL6 L拥有LO0一致稳定至多为2y。又因为 nE【,2)-eu4,-e川+ 4n-s(M0=R[MS】-R[MS)】= oEhLS,2+ 日2Ms1-aMs,a》=-246a动=-A4S n Ehe5,小-5。h≤4r+ 得到 5h,+ E【Kao-sM=,B&,LS] 由此，式(1)等价于证明：设本体数据依赖函数 h,4,z-Ee L:Z×Z→[-1,1]拥有L00一致稳定2y,D是Z 考虑到L是无偏估计且函数h不依赖于z或 上的任意分布。如果L是关于D的无偏估计，则有 ,因此对应每个给定的z和：，有 思us64y+月 (6) 5,h4S,3=hRls]=0 即 记S是将S中的第i个元素替换为：，并设 RL(S】= 2有 長hS,=是M4s,z=0 故有 R[(S】-RSL(SJ= ,E【RLSs 24小非24w, 2是hss训水 2三4s.动-4s,d- ij1,2.,.#j 255.a-6+u6v动-6es +∑16r≤+16 .)-us. 最后， 【®S= B【RZSJ+R,LSJ-R3SDs eusm县2usa 2RS]+ 2惡®，4S-S) 2是usa 2日+16r24=64yr+月 京∑是usus小 由此，式(1)得证。 i.je1.2.--nli+j 定义本体学习算法的LOO估计为Roo(4(S)川= ∑4S.。在监督本体学习下，Z=Vxy,每 个本体样本点为z=(心，y),可将LO0估计写成 记S是将S中的第i个元素和第j个元素 分别替换为z和z而得到的新本体数据集，并设 Rol4S川=Av,同时期望误差可以 n台结合文献 [23] 中引理 1.2 可知： P S∼Dn   RD[M(S )]−Rˆ S [M(S )] ⩾ 8 √( 4γn + 1 n ) ln 8 δ   ⩽ ln 2 m ⩽ δ 从而式 (2) 成立。 L(S,z) = M(S,z)−RD[M(S )] S ∈ Z n RD[L(S )] = 0 式 (1) 证明：设 ，则易 证 L 是关于分布 D 的无偏估计，对任意 都有 。由于 M 的取值范围在 [0,1] 内，因 此 L 取值范围是 [−1,1]。由于   RD[M(S )]−RD[M(S \i )]    ⩽      E z∼D [M(S,z)− M(S \i ,z)]      ⩽ γ L 拥有 LOO 一致稳定至多为 2γ 。又因为 ∆D−S (M) = RD[M(S )]−Rˆ S [M(S )] = 1 n ∑n i=1 (RD[M(S )]− M(S,zi)) = − 1 n ∑n i=1 L(S,zi) = −Rˆ S [L(S )] 得到 E S∼Dn [ (∆D−S (M))2 ] = E S∼Dn [ (Rˆ S [L(S )])2 ] L : Z n ×Z → [−1,1] 2γ 由此，式 (1) 等价于证明：设本体数据依赖函数 拥有 LOO 一致稳定 ， D 是 Z 上的任意分布。如果 L 是关于 D 的无偏估计，则有 E S∼Dn [ (Rˆ S [L(S )])2 ] ⩽ 64γ 2 + 2 n (6) S i,z R D S [L(S )] = E z∼D   1 n ∑n i=1 L(S i,z ,zi)   记 是将 S 中的第 i 个元素替换为 z，并设 ,有   Rˆ S [L(S )]−R D S [L(S )]    =        1 n ∑n i=1 L(S,zi)− E z∼D   1 n ∑n i=1 L(S i,z ,zi)          ⩽        1 n ∑n i=1 E z∼D [ L(S,zi)− L(S i,z ,zi) ]        =        1 n ∑n i=1 E z∼D [ L(S,zi)− L(S \i ,zi)+ L(S \i ,zi)− L(S i,z ,zi) ]        ⩽        1 n ∑n i=1 E z∼D [ L(S,zi)− L(S \i ,zi) ]        +        1 n ∑n i=1 E z∼D [ L(S \i ,zi)− L(S i,z ,zi) ]        ⩽ 2γ+2γ = 4γ E S∼Dn [ (R D S [L(S )])2 ] ⩽ E S∼Dn ,z∼D     1 n ∑n i=1 L(S i,z ,zi)   2   = 1 n 2 ∑n i=1 E S∼Dn ,z∼D [ (L(S i,z ,zi))2 ] + 1 n 2 ∑ i, j∈{1,2,···,n},i,j E S∼Dn ,z∼D [ L(S i,z ,zi)L(S j,z ,zj) ] ⩽ 1 n + 1 n 2 ∑ i, j∈{1,2,···,n},i,j E S∼Dn ,z∼D [ L(S i,z ,zi)L(S j,z ,zj) ] S i, j,zi,zj zi zj 记 是将 S 中的第 i 个元素和第 j 个元素 分别替换为 和 而得到的新本体数据集，并设 h(z) = min zi,zj∈Z L(S i, j,zi,zj ,z)+4γ。 注意到： max zi,zj∈Z L(S i, j,zi,zj ,z) ⩽ min zi,zj∈Z L(S i, j,zi,zj ,z)+8γ 可知：   L(S i, j,zi,zj ,z)−h(z)    ⩽ 4γ 因此： E S∼Dn ,z∼D [ L(S i,z ,zi)L(S j,z ,zj) ] = E zi,zj,z∼D [ L(S i,z ,zi)L(S j,z ,zj) ] = E zi,zj,z∼D [ (L(S i,z ,zi)−h(zi))(L(S j,z ,zj)−h(zj))] + E zi,zj,z∼D [ h(zi)L(S j,z ,zj) ] + E zi,zj,z∼D [ h(zj)L(S i,z ,zi) ] − E zi,zj∼D [ h(zi)h(zj) ] ⩽ (4γ) 2+ E zi,zj,z∼D [ h(zi)L(S j,z ,zj) ] + E zi,zj,z∼D [ h(zj)L(S i,z ,zi) ] − ( E z ′∼D [h(z ′ )])2 zi zj zi 考虑到 L 是无偏估计且函数 h 不依赖于 或 ，因此对应每个给定的 和 z，有 E zj∼D [ h(zi)L(S j,z ,zj) ] = h(zi)RD [ L(S j,z ) ] = 0 即 E zi,zj,z∼D [ h(zi)L(S j,z ,zj) ] = E zi,zj,z∼D [ h(zj)L(S i,z ,zi) ] = 0 故有 E S∼Dn [ (R D S [L(S )])2 ] ⩽ 1 n + 1 n 2 ∑ i, j∈{1,2,···,n},i,j E S∼Dn ,z∼D [ L(S i,z ,zi)L(S j,z ,zj) ] ⩽ 1 n + 1 n 2 ∑ i, j∈{1,2,···,n},i,j   16γ 2 − ( E z ′∼D [h(z ′ )])2   ⩽ 1 n + 1 n 2 ∑ i, j∈{1,2,···,n},i,j 16γ 2 ⩽ 1 n +16γ 2 最后， E S∼Dn [ (Rˆ S [L(S )])2 ] = E S∼Dn [ (R D S [L(S )]+Rˆ S [L(S )]−R D S [L(S )])2 ] ⩽ 2E S∼Dn [ (R D S [L(S )])2 ] + 2E S∼Dn [ (Rˆ S [L(S )]−R D S [L(S )])2 ] ⩽ 2 ( 1 n +16γ 2 ) +2(4γ) 2 = 64γ 2 + 2 n 由此，式 (1) 得证。 Rˆ LOO[l(A(S ))] = 1 n ∑n i=1 l(A(S \i ),zi) Z = V ×Y z = (v, y) Rˆ LOO[l(A(S ))] = 1 n ∑n i=1 l(AS \i(vi), yi) 定义本体学习算法的 LOO 估计为 。在监督本体学习下， ，每 个本体样本点为 ， 可 将 LOO 估计写成 ，同时期望误差可以 ·475· 朱林立，等：本体学习算法的两类 LOO 一致稳定性和广义界 第 3 期