·473· 朱林立，等：本体学习算法的两类L00一致稳定性和广义界 第3期 成立，则称本体算法A关于本体亏损函数1存在 依赖假设集(ontology sample dependent hypothesis LO0一致稳定y。 set),也称为本体数据依赖假设集(ontology data 设Rol(A(S)川=E。-DA(S),z为本体算法A的期 dependent hypothesis set)),记为Fs,表示根据本体训 望误差，4S川=Es[AS,=∑AS.2) 练样本集S而选取的本体函数空间。F和Fs的关 n 系是：当S给定后，Fs通常选取为F的一个子集， 为对应的经验误差。从而本体算法A的广义界就 即FsCF。进而可以写成F=UFs。这样，F表示 定义为期望误差和经验误差的差值，记为 为本体数据依赖假设集的并集，故也称 Ap-s(I(A))=Rp[I(A(S))]-Rs[I(A(S))] F=(Fs)sez为本体数据依赖假设集族。 为了方便讨论且说明本文的结果具有更加一 给定本体样本容量n∈N。如果对任意i∈ 般的规律，定理1给出的广义界对任意本体数据 {1,2,…,以，任意本体样本集S和删除一个元素后 依赖函数都成立。具体地说，设M:Z×Z→R(也 的本体样本集S￥，存在某个B≥0，对任意f∈Fs,都 可以限制其值域M:Z×Z→[0,1])为本体数据依 存在某个P∈Fsv,使得对任意z∈Z都有l(f,z) 赖函数(ontology data-dependent function),它将给 f,z训≤B成立。则称本体数据依赖假设集族F= 定本体数据集S和本体点：作为输入，可以看作 (Fs)se存在LOO一致稳定B,简称B-稳定。 计算实值函数MS,)应用到z。这里M(S)或者 给定本体样本容量n∈N。若对任意S∈Z,都 M(S,)表示M作用在本体数据S上而得到的输出 有Esup(f,)-1f,z)≤x成立，则称本体数 函数。事实上，在本体学习框架下，有M(S,z)= 1A(S),z),只是前者的表示有另外的数据统计含 据依赖假设集族F=(Fs)sez存在LOO-CV稳定X, 义，可以依赖于本体数据。在此设定下，期望误 其中X>0。更进一步，若。E。 sup ((f,)- 差和经验误差分别表示为R[M(S】=E.-D[M(S,z] -D-S fEFs.fEF 和R[MS】=EsMS,】=是∑MS,z。对应的 1f,z)≤成立，则称F存在LOO-均值CV稳定， 广义界表示为△-s(M=Rn[M)]-R[M(S)]。 同样≥0。 考虑将本体样本S作为输入，本体数据依赖 本体数据依赖假设集族F=(Fs)se2的直径△和 函数作为输出，比如在本体监督学习中，每个本 均值直径分别定义为 体样本点带有标记信息y,因而M(S,2)=l(f(v),), △=sup E sup(lfz)-1f,z》 即在本体样本z=(w,y)上执行本体学习算法A(S)。 SeZ-SffEFs 若对所有S∈Z",任意ie{1,2,…,m,任意z∈Z A=.E。sup(f-lf',z》 有M(S,z)-M(Sv,z≤y成立，则称本体数据依赖 对任意两个本体样本集S,T∈Z"以及拉德马 函数M:Z×Z→R存在LOO一致稳定y。若对所 有S,S∈Z严，其中S和S'是容量相同的两个本体数 赫向量σ，集合Sr。由S通过如下变换得到：对于 据集且只有一个数据不相同，满足YE二Y,有 ie{1,2,…,,若发现o=-l,则将S中第i个元素 P[M(S)∈E≤eP[M(S)∈E] 替换成集合T中的第i个元素。将假设集Fs,记 则称算法A:Z"→Y是s-差分隐私(leave-one-out-&- 为FSro differentially private)的。本体学习算法的假设空 固定n∈N,本体数据依赖假设集族F=(Fs)sez 间(hypothesis space)就是本体函数选取的范围空 关于两个本体样本集S={z,,…}和T={, 间，也称为假设集，它是本体学习算法设计的核 牙，…，)的拉德马赫复杂度(Rademacher complex- 心。假设空间过大意味着函数选取的范围很大， ity)和经验拉德马赫复杂度(empirical Rademacher 会导致算法不收敛；而假设空间过小又会导致得 complexity)分别定义为 到的最优本体函数性能不佳。理想的本体学习算 三，(F)= sup 法都会对假设空间有精巧的设计，一般在数学上 会选取凸函数空间，常见的本体假设空间有再生 1 色s.(F)=EsuP 核希尔伯特空间、索伯列夫空间等。由于假设空 na feFs:i=1 间是一个抽象的函数空间，一般用抽象的工具来 2 算法理论分析 刻画它的大小，比如覆盖数(covering number)o 在一般学习框架下，本体假设空间是由算法 定理1设M:Z"×Z→[0,1]为本体数据依赖 本身决定的，独立于本体样本，记为F。本文将考 函数且存在LO0一致稳定y,则对于任意Z上的 虑受本体数据集影响的假设空间，称为本体样本 概率分布D和任意6∈(0,1)，有γ 成立，则称本体算法 A 关于本体亏损函数 l 存在 LOO 一致稳定 。 RD[l(A(S ))] = Ez∼D[l(A(S ),z)] Rˆ S [l(A(S ))] =Ez∼S [l(A(S ),z)] = 1 n ∑n i=1 l(A(S ),zi) 设 为本体算法 A 的期 望误差， 为对应的经验误差。从而本体算法 A 的广义界就 定义为期望误差和经验误差的差值，记为 ∆D−S (l(A)) = RD[l(A(S ))]−Rˆ S [l(A(S ))] M : Z n ×Z → R M : Z n ×Z → [0,1] M(S,·) M(S ) M(S,·) M(S,z) = l(A(S ),z) RD[M(S )] = Ez∼D[M(S,z)] Rˆ S [M(S )] =Ez∼S [M(S,z)] = 1 n ∑n i=1 M(S,zi) ∆D−S (M) = RD[M(S )]−Rˆ S [M(S )] 为了方便讨论且说明本文的结果具有更加一 般的规律，定理 1 给出的广义界对任意本体数据 依赖函数都成立。具体地说，设 （也 可以限制其值域 ）为本体数据依 赖函数 (ontology data-dependent function)，它将给 定本体数据集 S 和本体点 z 作为输入，可以看作 计算实值函数 应 用 到 z。这里 或 者 表示 M 作用在本体数据 S 上而得到的输出 函数。事实上，在本体学习框架下，有 ，只是前者的表示有另外的数据统计含 义，可以依赖于本体数据。在此设定下，期望误 差和经验误差分别表示为 和 。对应的 广义界表示为 。 M(S,z) = lY (f(v), y) z = (v, y) A(S ) 考虑将本体样本 S 作为输入，本体数据依赖 函数作为输出，比如在本体监督学习中，每个本 体样本点带有标记信息 y，因而 ， 即在本体样本 上执行本体学习算法 。 S ∈ Z n i ∈ {1,2,··· ,n} z ∈ Z   M(S,z)− M(S \i ,z)    ⩽ γ M : Z n ×Z → R γ S,S ′ ∈ Z n ∀E ⊆ Y 若对所有 ，任意 ，任意 有 成立，则称本体数据依赖 函数 存在 LOO 一致稳定 。若对所 有 ，其中 S 和 S’是容量相同的两个本体数 据集且只有一个数据不相同，满足 ，有 P[M(S ) ∈ E] ⩽ e εP[M(S ′ ) ∈ E] A : Z 则称算法 n → Y 是ε-差分隐私（leave-one-out-ε- differentially private）的。本体学习算法的假设空 间 (hypothesis space)就是本体函数选取的范围空 间，也称为假设集，它是本体学习算法设计的核 心。假设空间过大意味着函数选取的范围很大， 会导致算法不收敛；而假设空间过小又会导致得 到的最优本体函数性能不佳。理想的本体学习算 法都会对假设空间有精巧的设计，一般在数学上 会选取凸函数空间，常见的本体假设空间有再生 核希尔伯特空间、索伯列夫空间等。由于假设空 间是一个抽象的函数空间，一般用抽象的工具来 刻画它的大小，比如覆盖数 (covering number)。 在一般学习框架下，本体假设空间是由算法 本身决定的，独立于本体样本，记为 F。本文将考 虑受本体数据集影响的假设空间，称为本体样本 FS FS FS FS ⊂ F F = ∪ S ∈Z n FS F = (FS )S ∈Z n 依赖假设集 (ontology sample dependent hypothesis set)，也称为本体数据依赖假设集 (ontology data dependent hypothesis set)，记为 ，表示根据本体训 练样本集 S 而选取的本体函数空间。F 和 的关 系是：当 S 给定后， 通常选取为 F 的一个子集， 即 。进而可以写成 。这样，F 表示 为本体数据依赖假设集的并集，故也称 为本体数据依赖假设集族。 n ∈ N i ∈ {1,2,··· ,n} S S \i β ⩾ 0 f ∈ FS f ′ ∈ FS \i z ∈ Z |l(f,z)− l(f ′ ,z)| ⩽ β F = (FS )S ∈Z n β β 给定本体样本容量 。如果对任意 ，任意本体样本集 和删除一个元素后 的本体样本集 ，存在某个 ，对任意 ，都 存在某个 ，使得对任意 都 有 成立。则称本体数据依赖假设集族 存在 LOO 一致稳定 ，简称 -稳定。 n ∈ N S ∈ Z n E z∼S   sup f ∈FS , f ′∈FS \i (l(f,z)−l(f ′ ,z))   ⩽ χ F = (FS )S ∈Z n χ χ ⩾ 0 E S∼Dn ,z∼S   sup f ∈FS , f ′∈FS \i (l(f,z)− l(f ′ ,z))] ⩽ χ¯ F χ¯ χ¯ ⩾ 0 给定本体样本容量 。若对任意 ，都 有 成立，则称本体数 据依赖假设集族 存在 LOO-CV 稳定 ， 其 中 。更进一步，若 成立，则称 存在 LOO-均值 CV 稳定 ， 同样 。 F = (FS )S ∈Z n ∆ ∆¯ 本体数据依赖假设集族 的直径 和 均值直径 分别定义为 ∆ = sup S ∈Z n E z∼S [ sup f, f ′∈FS (l(f,z)−l(f ′ ,z))] ∆ =¯ E S ∈Z n ,z∼S [ sup f, f ′∈FS (l(f,z)−l(f ′ ,z))] S,T ∈ Z n σ S T,σ i ∈ {1,2,··· ,n} σi = −1 FS T,σ F σ S,T 对任意两个本体样本集 以及拉德马 赫向量 ，集合 由 S 通过如下变换得到：对于 ，若发现 ，则将 S 中第 i 个元素 替换成集合 T 中的第 i 个元素。将假设集 记 为 。 n ∈ N F = (FS )S ∈Z n S = { z S 1 ,z S 2 ,··· ,z S n } T = { z T 1 , z T 2 ,··· ,z T n } 固定 ，本体数据依赖假设集族 关于两个本体样本集 和 的拉德马赫复杂度 (Rademacher complex￾ity) 和经验拉德马赫复杂度 (empirical Rademacher complexity) 分别定义为 Ξn(F) = 1 n E S,T∼Dn ,σ   sup f ∈F σ S,T ∑n i=1 σi f(zi T )   Ξˆ S,T (F) = 1 n E σ   sup f ∈F σ S,T ∑n i=1 σi f(z T i )   2 算法理论分析 M : Z n ×Z → [0,1] γ δ ∈ (0,1) 定理 1 设 为本体数据依赖 函数且存在 LOO 一致稳定 ，则对于任意 Z 上的 概率分布 D 和任意 ，有 ·473· 朱林立，等：本体学习算法的两类 LOO 一致稳定性和广义界 第 3 期