第17卷 智能系统学报 ·474· B【ap-sM0]≤64Y+2 (1) (论断为真时取值1，否则取值0)，则 Xs Es-D-J-A(S) MA(S1.S) ≤ (2) n 本文的第一个主要结果给出了本体数据依赖 Exs-o 函数框架下的学习算法广义界以及广义界平方的 上界，其中式(1)说明本体稳定算法的误差界的 H∑BBaS)=1-MSsl≤ 平方的期望值可以被一致稳定参数所控制在某个 固定的范围内，而式(2)则说明误差界越大，它发 生的概率越小。 22kE6四= 证明考虑m个本体数据集，每个数据集的 (Mi(S,S)+y)]= 容量均为n。为了防止混淆，称其为多重本体数 片22 E..ole-EaS)=1-(Md+川- 据集，记为S。显然S∈Zm,将每个本体子数据集 分别记为S1,S2,…,Sm,且第1个本体子数据集的第 Es-D--DJ-AS)[e.(M(S1)+y)]= ef(Es-D--D/=AS)[M(S1]+y) i个元素记为Su。设1e{l,2,…,m,定义 式中：S为多重本体数据集，它通过将第1个本体 fS)=△o-s,(M)=R[MS】-Rs,[M(S](3) 数据子集的第i个元素替换成：得到；S“是通过 设S和S是两个多重本体数据集，且S与S相 将S,中第i个元素替换成：得到的本体数据子集。 比仅仅是第k个本体数据子集的第ⅰ个元素不 由此可以得到 同。设So为多重本体数据集，它通过删除S'中 第k个本体数据子集的第i个元素得到。如果 eX-y≤Es-pm=As[Rn[M(Sl]≤eX+y(4) 式(4)的后半部分可以用类似的方法得到。 I≠k,则S,=S,进而有fS)=fS)。若1=k,则 特别地，有 IR[MS】-R[MS]=lR[MS】-R[MSo]+ RDIM(S)]-RD[M(SilI<RD[M(S)]-RD[M(S)]+ E-A5)RD[MS】-R,[MS≤e-1+y(5) IR[M(SY)]-Rp[M(S]=E[M(S1)-M(SY] 首先证明(2)成立。取m-号，设6 为实值函数（如式(3）定义)，fm+(S)=0。设A是f, l5MS,-MS-训s2y ,…,fm,fm1上的执行算法满足对任意1E1,2,…, |R,[MS】-R[MS2]= m有S)-训小≤4y+京。注意到.对于11.2 m有M,=M且Mm+1=0,因此由式(5)可知： 1 Es-DE=sf(S】= 非目2sw-之ss E-p--A[Ro[M:(Q)]-Rm[Mi(S)]]e-1+y 运用文献[22]中引理7.1可知： 月MG.5-msi.ss n Emax RofM(S]-R.IM(S10]- MSS）-∑MS,S Es-o(S) n 1】 24y+元 M(So,S)- ∑MS1,Si+ n Es-D-[E=-As)fi(S)】+ ln(m+1)≤ E 1,计j 8y+ MS,Su)-=M(Si,S)≤ n n e-1+y+- n In(m+1) 2* 1 n 这说明fS)-fS≤4y+。 当e≥时式(2)显然成立。当e<时有e-1≤2s, 对任意1∈1,2，·，m,设本体数据依赖函数 M:Z”×Z→0,1]拥有LO0一致稳定y,A:Zm→ 进而根据y≤V厅有 {1,2,…,m是s-差分隐私算法。 设X=Es-Dm=as[R,[MS],I为真值函数 +s4+E S∼Dn [(∆D−S (M))2 ] ⩽ 64γ 2 + 2 n (1) P S∼Dn   ∆D−S (M) ⩾ 8 √ (4γ+ 1 n )ln 8 δ   ⩽ δ (2) 本文的第一个主要结果给出了本体数据依赖 函数框架下的学习算法广义界以及广义界平方的 上界，其中式 (1）说明本体稳定算法的误差界的 平方的期望值可以被一致稳定参数所控制在某个 固定的范围内，而式 (2) 则说明误差界越大，它发 生的概率越小。 S S ∈ Z m×n S 1,S 2,··· ,S m l i S l,i l ∈ {1,2,··· ,m} 证明 考虑 m 个本体数据集，每个数据集的 容量均为 n。为了防止混淆，称其为多重本体数 据集，记为 。显然 ，将每个本体子数据集 分别记为 ，且第 个本体子数据集的第 个元素记为 。设 ，定义 fl(S ) = ∆D−S l (M) = RD[M(S l)]−Rˆ S l [M(S l)] (3) S S ′ S ′ S S \k(i) S ′ l , k S l = S ′ l fl(S ) = fl(S ′ ) l = k 设 和 是两个多重本体数据集，且 与 相 比仅仅是第 k 个本体数据子集的第 i 个元素不 同。设 为多重本体数据集，它通过删除 中 第 k 个本体数据子集的第 i 个元素得到。如果 ，则 ，进而有 。若 ，则   RD[M(S l)]−RD[M(S ′ l )]    = |RD[M(S l)]−RD[M(S \k(i) l )]+ RD[M(S \k(i) l )]−RD[M(S ′ l )]| ⩽   RD[M(S l)]−RD[M(S \k(i) l )]   +   RD[M(S \k(i) l )]−RD[M(S ′ l )]    =      E z∼D [M(S l ,z)− M(S \k(i) l ,z)]      +      E z∼D [M(S \k(i) l ,z)− M(S ′ l ,z)]      ⩽ 2γ   Rˆ S l [M(S l)]−Rˆ S ′ l [M(S ′ l )]    =        1 n ∑n j=1 M(S l ,S l, j)− 1 n ∑n j=1 M(S ′ l ,S ′ l, j )        ⩽        1 n ∑n j=1,i,j M(S l ,S l, j)− 1 n ∑n j=1,i,j M(S ′ l ,S ′ l, j )        +      1 n M(S l ,S l,i)− 1 n M(S ′ l ,S ′ l,i )      ⩽        1 n ∑n j=1,i,j M(S l ,S l, j)− 1 n ∑n j=1,i,j M(S \k(i) l ,S \k(i) l, j )        +        1 n ∑n j=1,i,j M(S \k(i) l ,S \k(i) l, j )− 1 n ∑n j=1,i,j M(S ′ l ,S ′ l, j )        +      1 n M(S l ,S l,i)− 1 n M(S ′ l ,S ′ l,i )      ⩽ 2γ+ 1 n    fl(S )− fl(S ′ l )    ⩽ 4γ+ 1 n 这说明 。 l ∈ {1,2,··· ,m} Ml : Z n ×Z → [0,1] γ A : Z n×m → {1,2,··· ,m} ε 对任意 ，设本体数据依赖函数 拥有 LOO 一致稳定 ， 是 -差分隐私算法。 XS = ES∼Dmn ,l=A(S ) [Rˆ S l 设 [Ml(S l)]]，I(·) 为真值函数 （论断为真时取值 1，否则取值 0），则 XS = ES∼Dmn ,l=A(S )   1 n ∑n i=1 Ml(S l ,S l,i)   = EA,S∼Dmn   1 n ∑n i=1 ∑m l=1 I(A(S ) = l)Ml(S l ,S l,i)   = 1 n ∑n i=1 ∑m l=1 ES∼Dmn [EA[I(A(S ) = l)]· Ml(S l ,S l,i)] ⩽ 1 n ∑n i=1 ∑m l=1 ES∼Dmn [eε ·EA[I(A(S l(i),z ) = l)]× (Ml(S i,z l ,S l,i)+γ)] = 1 n ∑n i=1 ∑m l=1 ES∼Dmn ,z∼D[eε ·EA[I(A(S ) = l)]·(Ml(S l ,z)+γ)] = ES∼Dmn ,z∼D,l=A(S )[eε ·(Ml(S l ,z)+γ)] = e ε (ES∼Dmn ,z∼D,l=A(S )[Ml(S l ,z)]+γ) S l(i),z S i,z l S l 式中： 为多重本体数据集，它通过将第 l 个本体 数据子集的第 i 个元素替换成 z 得到； 是通过 将 中第 i 个元素替换成 z 得到的本体数据子集。 由此可以得到 e −εXS −γ ⩽ ES∼Dmn ,l=A(S )[RD[Ml(S l)]] ⩽ e εXS +γ (4) 式（4）的后半部分可以用类似的方法得到。 特别地，有    ES∼Dmn ,l=A(S ) [ RD [Ml(S l)]−Rˆ S l [Ml(S l)] ]     ⩽ e ε −1+γ (5) m = ln 2 δ f1, f2,··· , fm fm+1(S ) = 0 f1, f2,··· , fm, fm+1 l ∈ {1,2,··· , m}    fl(S )− fl(S ′ l )    ⩽ 4γ+ 1 n l ∈ {1,2,··· , m} Ml = M Mm+1 = 0 首先证明 (2) 成立。取 ，设 为实值函数 (如式 (3) 定义)， 。设 A 是 上的执行算法满足对任意 有 。注意到，对于 有 且 ，因此由式（5）可知： ES∼D(m+1)n [El=A(S ) fl(S )] = Ea−D(m+1)m,−A(a) [ RD [Ml(Ql)]−Rˆ ml [Ml(S l)] ] ⩽ e ε −1+γ 运用文献 [22] 中引理 7.1 可知： ES∼Dmn [ max{ max l∈{1,2,···,m} RD[M(S l)]−Rˆ S l [M(S l)],0 }] = ES∼Dmn [ max l∈[0,m] fl(S ) ] ⩽ ES∼Dmn [El=A(S ) fl(S )]+ 2 ( 4γ+ 1 n ) ε ln(m+1) ⩽ e ε −1+γ+ 8γ+ 2 n ε ln(m+1) ε= √( 4γ+ 1 n ) ln(m+1)= √( 4γ+ 1 n ) ln( eln 2 δ ) ε ⩾ 1 2 ε < 1 2 e ε −1 ⩽ 2ε γ ⩽ √ γ 选 取 当 时式（2）显然成立。当 时有 ， 进而根据 有 4 √( 4γ+ 1 n ) ln( eln 2 δ ) +γ ⩽ 4 √( 4γ+ 1 n ) ln( 8 δ ) 第 17 卷 智 能 系 统 学 报 ·474·