第17卷第3期 智能系统学报 Vol.17 No.3 2022年5月 CAAI Transactions on Intelligent Systems May 2022 D0:10.11992/tis.202101015 网络出版地址：https:/kns.cnki.net/kcms/detail/23.1538.TP.20220324.1711.008.html 本体学习算法的两类LO0一致稳定性和广义界 朱林立2，华钢，高炜 (1.中国矿业大学信息与控制工程学院，江苏徐州221116：2.江苏理工学院计算机工程学院，江苏常州 213001;3.云南师范大学信息学院，云南昆明650500) 摘要：近年来，随着本体研究的深入，各类机器学习方法被尝试应用于本体相似度计算和本体映射获取。稳 定性是本体学习算法的必要条件，它从本质上体现了算法的可用性，即要求本体学习算法的最优解不会受到本 体样本的小幅度调整而发生大的变化。本文研究了删除一个本体样本点的条件下，对本体学习算法的期望误 差与经验误差的差值产生的影响。分别在本体学习算法一致稳定和假设空间一致稳定两种不同的框架下，利 用统计学习理论的技巧，得到对应广义界的上界估计。 关键词：本体：机器学习：稳定性：广义界：本体数据依赖函数：本体样本依赖假设集：拉德马赫复杂度：经验拉 德马赫复杂度 中图分类号：TP391文献标志码：A文章编号：1673-4785(2022)03-0471-09 中文引用格式：朱林立，华钢，高炜.本体学习算法的两类L00一致稳定性和广义界J八智能系统学报，2022,17(3)： 471-479 英文引用格式：ZHU Linli,,HUA Gang,GAO Wei..Two classes of LOO uniform stability and generalization bounds of ontology learning algorithm[J].CAAI transactions on intelligent systems,2022,17(3):471-479 Two classes of LOO uniform stability and generalization bounds of ontology learning algorithm ZHU Linli,HUA Gang',GAO Wei (1.School of Information and Control Engineering,China University of Mining and Technology,Xuzhou 221116,China,2.School of Computer Engineering,Jiangsu University of Technology,Changzhou 213001,China;3.School of Information,Yunnan Normal University,Kunming 650500.China) Abstract:Recently,with deepening ontology research,efforts have been made to apply various machine-learning meth- ods to ontology similarity calculations and mapping acquisitions.Stability is a necessary condition for ontology-learn- ing algorithms.It requires that the optimal solution of the algorithm does not undergo major changes due to small adjust- ments to the ontology samples;thus,it essentially reflects the usability of the algorithm.In this study,we investigated the effect of deleting an ontology sample point on the difference between the expected and empirical errors of the onto- logy-learning algorithm.In two settings of the ontology-learning algorithm-uniform stability and hypothetical space uniform stability-obtained using statistical learning theory,the corresponding upper bound estimates of generalized bounds are determined. Keywords:ontology;machine learning;stability;generalized bound;ontology data-dependent function;ontology sample dependent hypothesis set;Rademacher complexity;empirical Rademacher complexity 本体的概念首先属于西方哲学的范畴，是指近年来，本体作为概念语义表示的工具，与其他 客观存在在逻辑层面上的表达和概括。作为形而 数据库相比，有着结构化存储、易于在不同本体 上学的一个分支，本体论在哲学领域的主要研究 之间建立映射和本体对齐等优势，因而被广泛应 问题是“是否存在非物质事物”。20世纪80年代 用于各个学科，在生物、化学、医学、材料、能源 引入到人工智能领域，之后对本体有自己的定义。 等领域都能看到本体在特定的场景下发挥作用。 Skalle等]阐述了如何使用知识建模和本体 收稿日期：2021-01-09.网络出版日期：2022-03-25. 基金项目：国家自然科学基金项目(51574232). 工程方法开发模型，并利用本体模型来预测钻井 通信作者：朱林立.E-mail:zhulinli@jsut.edu.cn 过程中的井下故障。Sobral等回提出了一个基于
DOI: 10.11992/tis.202101015 网络出版地址: https://kns.cnki.net/kcms/detail/23.1538.TP.20220324.1711.008.html 本体学习算法的两类 LOO 一致稳定性和广义界 朱林立1,2，华钢1 ，高炜3 （1. 中国矿业大学 信息与控制工程学院，江苏 徐州 221116; 2. 江苏理工学院 计算机工程学院，江苏 常州 213001; 3. 云南师范大学 信息学院，云南 昆明 650500） 摘 要：近年来，随着本体研究的深入，各类机器学习方法被尝试应用于本体相似度计算和本体映射获取。稳 定性是本体学习算法的必要条件，它从本质上体现了算法的可用性，即要求本体学习算法的最优解不会受到本 体样本的小幅度调整而发生大的变化。本文研究了删除一个本体样本点的条件下，对本体学习算法的期望误 差与经验误差的差值产生的影响。分别在本体学习算法一致稳定和假设空间一致稳定两种不同的框架下，利 用统计学习理论的技巧，得到对应广义界的上界估计。 关键词：本体；机器学习；稳定性；广义界；本体数据依赖函数；本体样本依赖假设集；拉德马赫复杂度；经验拉 德马赫复杂度 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2022)03−0471−09 中文引用格式：朱林立, 华钢, 高炜. 本体学习算法的两类 LOO 一致稳定性和广义界 [J]. 智能系统学报, 2022, 17(3): 471–479. 英文引用格式：ZHU Linli, HUA Gang, GAO Wei. Two classes of LOO uniform stability and generalization bounds of ontology learning algorithm[J]. CAAI transactions on intelligent systems, 2022, 17(3): 471–479. Two classes of LOO uniform stability and generalization bounds of ontology learning algorithm ZHU Linli1,2 ，HUA Gang1 ，GAO Wei3 (1. School of Information and Control Engineering, China University of Mining and Technology, Xuzhou 221116, China; 2. School of Computer Engineering, Jiangsu University of Technology, Changzhou 213001, China; 3. School of Information, Yunnan Normal University, Kunming 650500, China) Abstract: Recently, with deepening ontology research, efforts have been made to apply various machine-learning methods to ontology similarity calculations and mapping acquisitions. Stability is a necessary condition for ontology-learning algorithms. It requires that the optimal solution of the algorithm does not undergo major changes due to small adjustments to the ontology samples; thus, it essentially reflects the usability of the algorithm. In this study, we investigated the effect of deleting an ontology sample point on the difference between the expected and empirical errors of the ontology-learning algorithm. In two settings of the ontology-learning algorithm—uniform stability and hypothetical space uniform stability —obtained using statistical learning theory, the corresponding upper bound estimates of generalized bounds are determined. Keywords: ontology; machine learning; stability; generalized bound; ontology data-dependent function; ontology sample dependent hypothesis set; Rademacher complexity; empirical Rademacher complexity 本体的概念首先属于西方哲学的范畴，是指 客观存在在逻辑层面上的表达和概括。作为形而 上学的一个分支，本体论在哲学领域的主要研究 问题是“是否存在非物质事物”。20 世纪 80 年代 引入到人工智能领域，之后对本体有自己的定义。 近年来，本体作为概念语义表示的工具，与其他 数据库相比，有着结构化存储、易于在不同本体 之间建立映射和本体对齐等优势，因而被广泛应 用于各个学科，在生物、化学、医学、材料、能源 等领域都能看到本体在特定的场景下发挥作用。 Skalle 等 [1] 阐述了如何使用知识建模和本体 工程方法开发模型，并利用本体模型来预测钻井 过程中的井下故障。Sobral 等 [2] 提出了一个基于 收稿日期：2021−01−09. 网络出版日期：2022−03−25. 基金项目：国家自然科学基金项目 (51574232). 通信作者：朱林立. E-mail：zhulinli@jsut.edu.cn. 第 17 卷第 3 期 智 能 系 统 学 报 Vol.17 No.3 2022 年 5 月 CAAI Transactions on Intelligent Systems May 2022
第17卷 智能系统学报 ·472· 本体的框架来支持来自智能交通系统的数据的集 (样本集)和测试集。通过本体样本的训练，按照 成和可视化。Al-Sayed等设计了一种称为Cloud- 一定的本体学习算法得到本体函数，再将本体函 FNF的综合云本体，根据该本体结构，云服务被 数应用于同类本体数据（测试集）。我们希望从 分类为若干个类别。Tebes等给出分析和记录 样本学习得到的本体函数同样适用于同一个本体 软件测试本体的系统审查结果的方法。Pradeep 的其他本体数据，即算法具有很好的扩展性能。 等)在基于本体的平衡二叉树中搜索预定的用户 这必须要求本体学习算法具有稳定性，即样本的 查询，最后使用Okapi BM25对相关结果进行排序 轻微改变对学习得到的结果影响很小。从理论上 并交付给用户。Hema等提出了一种新的基于 说，稳定性是一种学习的平滑性，即最优函数的 信任的隐私保护框架，通过本体服务排序TBP℉- 性能随着样本容量n的增加而缓缓提高，其特征 OSR进行用户身份验证。Messaoudi等可给出了 曲线是平滑过渡的，不会在任何一点产生剧烈的 关于疾病治疗医学本体研究的综述。Mantovani 震荡。而强烈的抖动意味着算法对于特定的本体 等]提出了一种本体驱动的地质图知识表示。 样本点有着特定的反映，进而说明本体学习算法 本体形式语言允许通过语义类别和属性对地球科 本身不适合实验对象数据，即这样的算法得到的 学家的解释进行机器可读编码，并支持知识共享 最优本体函数不可能对训练集以外的数据产生很 和互操作性。Abeysinghe等I通过在基因本体 好的效果。 (gene ontology,GO)本体概念的基于序列的表示 另一方面.理论研究最关心的是算法的收敛阶 之上，利用新的术语代数以及3个条件规则（单调 和误差界。本文的动机是在稳定性和误差界之间 性、交集和子概念规则)开发了基于包含的子项 找到必然的联系。因此如果一个本体学习算法有 推理框架。Kossmann等1o提出了潜艇探测着陆 很好的稳定性，那么它的学习误差就会控制在某 器的本体驱动框架。 个范围内。也就是说，本文的理论结果暗示了稳 随着越来越多的本体被定义和应用，以及越 定性不仅是本体学习算法具有泛化性的前提，而 来越多的本体算法被设计并尝试用于不同的本体 且稳定性参数控制了本体学习算法广义界的上界。 工程应用领域，学习算法也被逐渐应用于本体。 本文针对删除一个样本的LO0操作，给出对 本体学习算法就是将机器学习方法与本体自身结 应的本体学习算法稳定性和本体函数假设空间一 构相融合，通过本体样本的学习得到本体函数。 致稳定性定义。并利用统计学方法，针对两类不 具体地说，本体用图结构表示，设G=(V,E)为本体 同的LOO一致稳定性定义，分别给出广义界的估 图对应某个本体O,其顶点对应O中概念，顶点 计值，这些界优于之前同框架LO0一致稳定性设 之间的边对应两个顶点某种直接联系。本体可以 定论文中得到的广义界。 用有向图来表示，其中边的权值由边的类型等因 素决定。本体学习算法可以看成图算法，通过本 1本体学习算法及稳定性 体样本S按照一定的学习规则学习得到本体函数 设Z为本体数据集，在非监督本体学习中 f:V→R。该本体函数的作用是将整个本体图映 射到一维实数轴，每个本体顶点（对应本体概念） Z即为本体图顶点数据V,对于监督本体学习则 映射为一维实数。在最开始的本体数值化表示 Z=V×Y。设本体学习算法A:Z→F,其中F是 中，往往要求每个本体顶点都用一个p维向量来 本体函数空间，即假设空间。A(S)或者A(S,)表示 表示，因此本体学习算法本质上就变成一种降维 本体学习算法A作用在本体数据S的输出函数。 算法，目标是得到本体函数f:RP→R。相关本体 :F×Z→R为本体亏损函数（也可以将其正则化， 学习这方面的研究可参考文献[11-19)。 即取值限定在区间[0,1]内，进而也可以表示为 稳定性是一个本体学习算法在具体工程应用 1:F×Z→[0,1])，给定本体函数f和本体样本点v, 领域可以使用的基本条件，它要求算法在学习样 本体亏损函数表示为f,z)。设S={1,2,…,}为 本集发生轻微改变时输出结果不会发生本质性的 容量为n的本体样本。删除样本集S中的第i(i∈ 改变。常见的变换有：删除一个样本(leave one {1,2,…,川)个样本y,对应的样本集变为S= out,LOO),删除两个样本(leave two out,LTO),替 {亿1,2，…，-l,4l,…,n,称此类变换为LOO(leave 换一个样本(place one,PO)。只有满足稳定性的 one out)。在样本S的表示中，若算法为非监督本 本体学习算法才具备泛化性，才有可能对同类数 体学习算法，则=；在监督本体学习下有 据发挥作用。已有部分文献对本体算法的稳定性 =(v,)。如果对于任意位置iie{1,2,…,n),任 进行了讨论，可参考文献[15,20-21]。 意S和S,以及任意v∈V,有 具体地说，通常把本体数据分成两类：训练集 |A(S),z)-lA(S,z≤y
本体的框架来支持来自智能交通系统的数据的集 成和可视化。Al-Sayed 等 [3] 设计了一种称为 CloudFNF 的综合云本体，根据该本体结构，云服务被 分类为若干个类别。Tebes 等 [4] 给出分析和记录 软件测试本体的系统审查结果的方法。Pradeep 等 [5] 在基于本体的平衡二叉树中搜索预定的用户 查询，最后使用 Okapi BM25 对相关结果进行排序 并交付给用户。Hema 等 [6] 提出了一种新的基于 信任的隐私保护框架，通过本体服务排序 TBPFOSR 进行用户身份验证。 Messaoudi 等 [7] 给出了 关于疾病治疗医学本体研究的综述。Mantovani 等 [ 8 ] 提出了一种本体驱动的地质图知识表示。 本体形式语言允许通过语义类别和属性对地球科 学家的解释进行机器可读编码，并支持知识共享 和互操作性。Abeysinghe 等 [9] 通过在基因本体 (gene ontology, GO) 本体概念的基于序列的表示 之上，利用新的术语代数以及 3 个条件规则（单调 性、交集和子概念规则）开发了基于包含的子项 推理框架。Kossmann 等 [10] 提出了潜艇探测着陆 器的本体驱动框架。 G = (V,E) f : V → R f : R p → R 随着越来越多的本体被定义和应用，以及越 来越多的本体算法被设计并尝试用于不同的本体 工程应用领域，学习算法也被逐渐应用于本体。 本体学习算法就是将机器学习方法与本体自身结 构相融合，通过本体样本的学习得到本体函数。 具体地说，本体用图结构表示，设 为本体 图对应某个本体 O，其顶点对应 O 中概念，顶点 之间的边对应两个顶点某种直接联系。本体可以 用有向图来表示，其中边的权值由边的类型等因 素决定。本体学习算法可以看成图算法，通过本 体样本 S 按照一定的学习规则学习得到本体函数 。该本体函数的作用是将整个本体图映 射到一维实数轴，每个本体顶点（对应本体概念） 映射为一维实数。在最开始的本体数值化表示 中，往往要求每个本体顶点都用一个 p 维向量来 表示，因此本体学习算法本质上就变成一种降维 算法，目标是得到本体函数 。相关本体 学习这方面的研究可参考文献 [11-19]。 稳定性是一个本体学习算法在具体工程应用 领域可以使用的基本条件，它要求算法在学习样 本集发生轻微改变时输出结果不会发生本质性的 改变。常见的变换有：删除一个样本 (leave one out, LOO)，删除两个样本 (leave two out, LTO)，替 换一个样本 (place one, PO)。只有满足稳定性的 本体学习算法才具备泛化性，才有可能对同类数 据发挥作用。已有部分文献对本体算法的稳定性 进行了讨论，可参考文献 [15，20-21]。 具体地说，通常把本体数据分成两类：训练集 （样本集）和测试集。通过本体样本的训练，按照 一定的本体学习算法得到本体函数，再将本体函 数应用于同类本体数据（测试集）。我们希望从 样本学习得到的本体函数同样适用于同一个本体 的其他本体数据，即算法具有很好的扩展性能。 这必须要求本体学习算法具有稳定性，即样本的 轻微改变对学习得到的结果影响很小。从理论上 说，稳定性是一种学习的平滑性，即最优函数的 性能随着样本容量 n 的增加而缓缓提高，其特征 曲线是平滑过渡的，不会在任何一点产生剧烈的 震荡。而强烈的抖动意味着算法对于特定的本体 样本点有着特定的反映，进而说明本体学习算法 本身不适合实验对象数据，即这样的算法得到的 最优本体函数不可能对训练集以外的数据产生很 好的效果。 另一方面，理论研究最关心的是算法的收敛阶 和误差界。本文的动机是在稳定性和误差界之间 找到必然的联系。因此如果一个本体学习算法有 很好的稳定性，那么它的学习误差就会控制在某 个范围内。也就是说，本文的理论结果暗示了稳 定性不仅是本体学习算法具有泛化性的前提，而 且稳定性参数控制了本体学习算法广义界的上界。 本文针对删除一个样本的 LOO 操作，给出对 应的本体学习算法稳定性和本体函数假设空间一 致稳定性定义。并利用统计学方法，针对两类不 同的 LOO 一致稳定性定义，分别给出广义界的估 计值，这些界优于之前同框架 LOO 一致稳定性设 定论文中得到的广义界。 1 本体学习算法及稳定性 Z V Z = V ×Y A : Z n → F A(S ) A(S,·) l : F ×Z → R l : F ×Z → [0,1] l(f,z) S = { z1, z2, ···, zn} i ∈ {1, 2, ··· , n} vi S \i = {z1, z2, ···, zi−1, zi+1, ···, zn} zi = vi zi = (vi , yi) i ∈ {1,2,··· ,n} S \i v ∈ V 设 为本体数据集，在非监督本体学习中， Z 即为本体图顶点数据 ，对于监督本体学习则 。设本体学习算法 ，其中 F 是 本体函数空间，即假设空间。 或者 表示 本体学习算法 A 作用在本体数据 S 的输出函数。 为本体亏损函数（也可以将其正则化， 即取值限定在区间 [0,1] 内，进而也可以表示为 ），给定本体函数 f 和本体样本点 v， 本体亏损函数表示为 。设 为 容量为 n 的本体样本。删除样本集 S 中的第 i( ) 个样本 ，对应的样本集变为 ，称此类变换为 LOO(leave one out)。在样本 S 的表示中，若算法为非监督本 体学习算法，则 ；在监督本体学习下有 。如果对于任意位置 i( )，任 意 S 和 ，以及任意 ，有 l(A(S ),z)−l(A(S \i ),z) ⩽ γ 第 17 卷 智 能 系 统 学 报 ·472·
·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 complexity) 和经验拉德马赫复杂度 (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 期
第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·
·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 期