第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 期
第17卷 智能系统学报 ·476· 写成Ro[l(A(S)川=El(As(w),yl。监督本体学习算 定理4设F=(Fs)s2为本体数据依赖假设集 法A关于本体亏损函数I存在LO0一致稳定y可 族，且存在LOO一致稳定B。设平=(Pssz如式 以重新写为(As(w,y)-1As(w),y川≤y,令g:=g(3, (7)所定义，则对任意6>0，式(8)在所有本体样本 z2,…,zn)=E(E-D(Asw(v)y)]-l(Asu(V,y)。 S,T~Z中以概率至少1-6成立： 本文第二个主要结论刻画了关于LO0估计 色(-三.（≤ a+2mp2+4rp)）log言 2 的广义界和 之间的差值可以被LO0一致稳 (8) 2n 定y所决定。 证明设本体样本T从T中得到且和T只有 定理2设监督本体学习算法A关于本体亏 一个本体样本点不同，不妨记第k个元素不同，其 损函数I存在LOO一致稳定y,且本体亏损函数 中k∈{1,2，…，n。给定n>0,对于任意拉德马赫向 1有界：1(，)≤L,有 量o,根据上确界的定义，存在f∈FS使得 R[A(S)】-Roo[lA(S)J 2o》牌2- feFsr i=1 证明通过直接计算，可得 根据F存在LOO一致稳定B的假设，存在 n(RD[I(A(S))]-RLoo[I(A(S))D= f∈FS,使得对任意z∈Z,有 f,z)-1f,z= .W.(.p)-M.0是任意的，得到 因此，定理2得证。 1 sup 定理3设本体数据依赖假设集族F=(Fs)sez 2lfz)≤ ∑0+29s n 的直径和均值直径分别为4和☑，且有LO0一致稳 22ou*9时 1 定B,则F有LOO-CV稳定4+B和LOO-均值CV 稳定☑+B。 这意味着，将T替换成T',对色s.()的影响最 证明设S∈Z,z∈S。对任意f∈Fs,f∈Fsv, 多为2B+。用相同的方法可以得到，对S改变一 由LO0一致稳定条件，存在f∈Fs使得f,)- 个本体样本点对色s(的影响最多为2B。最后， 1f",)≤B。从而 f,z)-1f,z）=1f,z)-lf”,z)+lf",z)-lf,z）≤ 利用McDiarmid不等式2得到定理4的结论。 B+sup (I(f".z)-I(f.)) 定理5用三（和来刻画本体数据依赖假设 集族LOO一致稳定本体学习算法的广义界。 进而 定理5设F=(Fs)s为本体数据依赖假设集 sup (I(f'.z)-I(f,)0， 设ps是与Fs关联的本体亏损函数族： 所有f∈F,式(9)在所有本体样本S~Z中以概率 ps={z→lf,z儿f∈Fs} (7) 至少1-6成立： 设平=(ps)sz为ps的假设集族。为了方便定 理4讨论，假设与Fs关联的本体亏损函数是1-有 Ro(f)-Rs(f)≤min(2r,2三.(}+(1+4n8) 界的，即对于任意f∈Fs,任意z~D有0≤If,)≤ 2n (9) 1。定理4是用本体数据依赖假设集族LO0一致 这里，Ro(f)=E2-Dlf,z,Rs(f)=E2-s[lf,z= 稳定和平=(pss来刻画拉德马赫复杂度和经验 拉德马赫复杂度之间的差值
RD[l(A(S ))] = E(v,y)[l(AS (v), y)] γ |l(AS (v), y)−l(AS \i(v), y)| ⩽ γ gi = gi(z1, z2,··· ,zn) = E(Ez∼D[l(AS \i(v),y)]−l(AS \i(vi),yi)) 写成 。监督本体学习算 法 A 关于本体亏损函数 l 存在 LOO 一致稳定 可 以重新写为 ， 令 。 ∑n i=1 gi γ 本文第二个主要结论刻画了关于 LOO 估计 的广义界和 之间的差值可以被 LOO 一致稳 定 所决定。 γ l(·,·) ⩽ L 定理 2 设监督本体学习算法 A 关于本体亏 损函数 l 存在 LOO 一致稳定 ，且本体亏损函数 l 有界： ，有 RD[l(A(S ))]−Rˆ LOO[l(A(S ))]− ∑n i=1 gi ⩽ nγ 证明 通过直接计算，可得 n(RD[l(A(S ))]−Rˆ LOO[l(A(S ))]) = ∑n i=1 (E(v,y)[l(AS (v), y)]−l(AS \i(vi), yi)) ⩽ nγ+ ∑n i=1 (E(v,y)[l(AS \i(v), y)]−l(AS \i(vi), yi)) ⩽ nγ+ ∑n i=1 gi 用类似的方法可以得到： n ( RD[l(A(S ))]−Rˆ LOO[l(A(S ))]) ⩾ ∑n i=1 gi −nγ 因此，定理 2 得证。 F = (FS )S ∈Z n ∆ ∆¯ β ∆+β ∆¯ +β 定理 3 设本体数据依赖假设集族 的直径和均值直径分别为 和 ，且有 LOO 一致稳 定 ，则 F 有 LOO-CV 稳定 和 LOO-均值 CV 稳定 。 S ∈ Z n z ∈ S f ∈ FS f ′ ∈ FS \i f ′′ ∈ FS l(f ′ ,z)− l(f ′′ ,z) ⩽ β 证明 设 ， 。对任意 ， ， 由 LOO 一致稳定条件，存在 使得 。从而 l(f ′ ,z)−l(f,z) = l(f ′ ,z)−l(f ′′ ,z)+l(f ′′ ,z)−l(f,z) ⩽ β+ sup f, f ′′ ∈FS (l(f ′′ ,z)−l(f,z)) 进而 sup f ∈FS , f ′∈FS \i (l(f ′ ,z)−l(f,z)) ⩽ β+ sup f, f ′′∈FS (l(f ′′ ,z)−l(f,z)) 这说明定理 3 得证。 设 ℘S是与 FS关联的本体亏损函数族： ℘S = {z 7→ l(f,z)| f ∈ FS } (7) Ψ = (℘S )S ∈Z n ℘S FS f ∈ FS z ∼ D 0 ⩽ l(f,z) ⩽ 1 Ψ = (℘S )S ∈Z n 设 为 的假设集族。为了方便定 理 4 讨论，假设与 关联的本体亏损函数是 1-有 界的，即对于任意 ，任意 有 。定理 4 是用本体数据依赖假设集族 LOO 一致 稳定和 来刻画拉德马赫复杂度和经验 拉德马赫复杂度之间的差值。 F = (FS )S ∈Z n β Ψ = (℘S )S ∈Z n δ > 0 S,T ∼ Z n 1−δ 定理 4 设 为本体数据依赖假设集 族，且存在 LOO 一致稳定 。设 如式 (7) 所定义，则对任意 ，式 (8) 在所有本体样本 中以概率至少 成立： Ξˆ S,T (Ψ)−Ξn(Ψ) ⩽ vut( (1+2nβ) 2 +4n 2β 2 ) log 2 δ 2n (8) k ∈ {1,2,··· ,n} η > 0 σ f ′ ∈ F σ S,T ′ 证明 设本体样本 T'从 T 中得到且和 T 只有 一个本体样本点不同，不妨记第 k 个元素不同，其 中 。给定 ，对于任意拉德马赫向 量 ，根据上确界的定义，存在 使得 ∑n i=1 σi l(f ′ ,z T i ) ⩾ sup f ∈F σ S,T ′ ∑n i=1 σi l(f,z T ′ i )−η F β f ∈ F σ S,T z ∈ Z 根 据 存 在 LOO 一致稳定 的假设，存在 ，使得对任意 ，有 |l(f ′ ,z)−l(f,z)| = |l(f ′ ,z)−l(f ′′ ,z)+l(f ′′ ,z)−l(f,z)| ⩽ |l(f ′ ,z)−l(f ′′ ,z)|+|l(f ′′ ,z)−l(f,z)| ⩽ 2β f ′′ 其中 来自将 S T,σ中第 k 个元素删除后得到的新 本体样本集对应的假设集。从而有 sup f ∈F σ S,T ′ ∑n i=1 σi l(f,z T ′ i ) ⩽ ∑n i=1 σi l(f ′ ,z T ′ i )+η ⩽ ∑n i=1 (σi(l(f,z T ′ i )+2β))+η 由于 η > 0 是任意的，得到 1 n sup f ∈F σ S,T ′ ∑n i=1 σi l(f,z T ′ i ) ⩽ 1 n ∑n i=1 (σi(l(f,z T ′ i )+2β)) ⩽ 1 n sup f ∈F σ S,T ∑n i=1 σi l(f,z T i )+2β+ 1 n T ′ Ξˆ S,T (Ψ) 2β+ 1 n Ξˆ S,T (Ψ) 2β 这意味着，将 T 替换成 ，对 的影响最 多为 。用相同的方法可以得到，对 S 改变一 个本体样本点对 的影响最多为 。最后， 利用 McDiarmid 不等式[24] 得到定理 4 的结论。 定理 5 用 Ξn(Ψ) 和 χ¯来刻画本体数据依赖假设 集族 LOO 一致稳定本体学习算法的广义界。 F = (FS )S ∈Z n β χ¯ Ψ = (℘S )S ∈Z n δ > 0 f ∈ FS S ∼ Z n 1−δ 定理 5 设 为本体数据依赖假设集 族，存在 LOO 一致稳定 和 LOO-均值 CV 稳定 。设 如式 (7) 所定义，则对任意 ， 所有 ，式 (9) 在所有本体样本 中以概率 至少 成立： RD(f)−Rˆ S (f) ⩽ min{2 ¯χ,2Ξn(Ψ)}+(1+4nβ) vut log 1 δ 2n (9) RD(f) = Ez∼D[l(f,z)] Rˆ S (f) = Ez∼S[l(f,z)] = 1 n ∑n i=1 l(f,zi) 这里， ， 。 第 17 卷 智 能 系 统 学 报 ·476·
·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 期
第17卷 智 能系统学报 ·478· 出具体证明。同时，通过替换证明过程中的一些 sup [I(f.a-I(f.a]s 技巧，可以得到定理7的另外一个版本如定理8 定理8设F=(Fs)s为本体数据依赖假设集 族，存在LOO一致稳定B和LOO-CV稳定X。设 平=(ps)s2如式(7)所定义，则对任意6∈(0,1)，所 有f∈Fs,式(14)在所有本体样本S~2严中以概率 含.Ee-n 至少1-6成立： R(fD-Rs(f)≤ sup [f,z）-lf",z)+ min {2三.(+8(1+4n8) I(f".a-I(f.a]s]s (14) 交.ePaS-R 2xe+4 sp,动-r,s 3结束语 本文主要从删除一个本体样本的设定出发， sup .3- 讨论具有LOO一致稳定性的本体学习算法的广 义界的统计学特征。主要从两个角度来讨论： 豆.Eno-m 1)本体学习算法关于本体亏损函数具有LO0 致稳定性； 2)本体函数假设空间稳定，即本体数据依赖 sup [l(f",z)-I(f.llS 假设集族F=(Fs)sz存在LOO一致稳定B。 22,思P4S)== 利用统计学习理论的方法，分别给出了两种假 设框架下，本体学习算法的学习率的上界。得到的 =1 理论结果表明，在算法一致稳定和假设空间一致稳 X=2 定的理论假设下，本体学习算法的误差界的上界可 以被稳定性参数很好地控制，进而保证了本体算法 其中S表示在本体数据集S,中删除元素z得到的 的收敛性。鉴于各种形式的本体学习算法已被广泛 集合。 应用于基因学、营养学、化学、地理信息系统等领域， 利用定理1中的本体多重集方法，结合定理5 本文得到的理论结果对本体学习算法的各类实际应 和定理6，可得关于用三.()和X来刻画本体数据依 用有着潜在的指导意义和参考价值。关于稳定性在 赖假设集族LO0一致稳定本体学习算法的广义界。 具体某个本体学习算法中的表现，在未来的本体算 定理7设F=(Fs)se2为本体数据依赖假设集 法执行中有待进一步实验验证。 族，存在LO0一致稳定B和LOO-CV稳定X。设 平=(pss如式(7)所定义，则对任意6∈0,1)，所 参考文献： 有f∈Fs,式(13)在所有本体样本S~Z”中以概率 [1]SKALLE P,AAMODT A.Petrol 18 946:downhole fail- 至少1-6成立： ures revealed through ontology engineering[J].Journal of Rof-R(f)≤ petroleum science and engineering,2020,191:107188. [2] SOBRAL T,GALVAO T,BORGES J.An ontology- log based approach to knowledge-assisted integration and min 1{2三.(+(1+4n) 2n visualization of urban mobility data[J].Expert systems (13) with applications,2020,150:113260. [3]AL-SAYED MM.HASSAN HA.OMARA F A.Cloud- 4 FNF:an ontology structure for functional and non-func- tional features of cloud services[J].Journal of parallel and distributed computing,2020,141:143-173. 由于证明方法与之前定理类似，我们不再给 [4]TEBES G.PEPPINO D,BECKER P,et al.Analyzing and
sup f ∈FS l , f ′∈FS z↔z ′ l [ l(f ′ ,z)−l(f,z) ] ] ⩽ ∑m l=1 E S∼Dmn [ P[A(S ) = l]× E z ′∼D,z∼S l [ sup f ∈FS l , f ′∈FS z↔z ′ l [ l(f ′ ,z)−l(f,z) ] |S ] ⩽ ∑m l=1 E S∼Dmn [P[A(S ) = l]]× E z ′∼D,z∼S l [ sup f ∈FS l , f ′∈FS z↔z ′ l , f ′′∈FS \z l [ [l(f ′ ,z)−l(f ′′ ,z)+ l(f ′′ ,z)−l(f,z) ] |S ] ] ⩽ ∑m l=1 E S∼Dmn [ P[A(S ) = l]× E z ′∼D,z∼S l [ sup f ′∈FS z↔z ′ l , f ′′∈FS \z l [ l(f ′ ,z)−l(f ′′ ,z) ] |S ]] ⩽ ∑m l=1 E S∼Dmn [ P[A(S ) = l]× E z ′∼D,z∼S l [ sup f ′∈FS z↔z ′ l , f ′′∈FS \z l [ l(f ′ ,z)−l(f ′′ ,z) ] |S ]]+ ∑m l=1 E S∼Dmn [ P[A(S ) = l]× E z ′∼D,z∼S l [ sup f ∈FS l , f ′′∈FS \z l [l(f ′′ ,z)−l(f,z)]|S ]] ⩽ 2 ∑m l=1 E S∼Dmn [ P[A(S ) = l]χ ] = 2 E S∼Dmn ∑m l=1 P[A(S ) = l] χ = 2χ S \z l 其中 表示在本体数据集 S l中删除元素 z 得到的 集合。 Ξn(Ψ) χ 利用定理 1 中的本体多重集方法，结合定理 5 和定理 6，可得关于用 和 来刻画本体数据依 赖假设集族 LOO 一致稳定本体学习算法的广义界。 F = (FS )S ∈Z n β χ Ψ = (℘S )S ∈Z n δ ∈ (0,1) f ∈ FS S ∼ Z n 1−δ 定理 7 设 为本体数据依赖假设集 族，存在 LOO 一致稳定 和 LOO-CV 稳定 。设 如式 (7) 所定义，则对任意 ，所 有 ，式 (13) 在所有本体样本 中以概率 至少 成立： RD(f)−Rˆ S (f) ⩽ min 2Ξn(Ψ)+(1+4nβ) vut log 2 δ 2n , 2χ √ e+4 √( 4β+ 1 n ) log 6 δ (13) 由于证明方法与之前定理类似，我们不再给 出具体证明。同时，通过替换证明过程中的一些 技巧，可以得到定理 7 的另外一个版本如定理 8。 F = (FS )S ∈Z n β χ Ψ = (℘S )S ∈Z n δ ∈ (0,1) f ∈ FS S ∼ Z n 1−δ 定理 8 设 为本体数据依赖假设集 族，存在 LOO 一致稳定 和 LOO-CV 稳定 。设 如式 (7) 所定义，则对任意 ，所 有 ，式 (14) 在所有本体样本 中以概率 至少 成立： RD(f)−Rˆ S (f) ⩽ min 2Ξn(Ψ)+8(1+4nβ) vut log 3 δ n , 2χ √ e+4 √( 4β+ 1 n ) log 3 δ (14) 3 结束语 本文主要从删除一个本体样本的设定出发， 讨论具有 LOO 一致稳定性的本体学习算法的广 义界的统计学特征。主要从两个角度来讨论： 1）本体学习算法关于本体亏损函数具有 LOO 一致稳定性； F = (FS )S ∈Z n β 2）本体函数假设空间稳定，即本体数据依赖 假设集族 存在 LOO 一致稳定 。 利用统计学习理论的方法，分别给出了两种假 设框架下，本体学习算法的学习率的上界。得到的 理论结果表明，在算法一致稳定和假设空间一致稳 定的理论假设下，本体学习算法的误差界的上界可 以被稳定性参数很好地控制，进而保证了本体算法 的收敛性。鉴于各种形式的本体学习算法已被广泛 应用于基因学、营养学、化学、地理信息系统等领域， 本文得到的理论结果对本体学习算法的各类实际应 用有着潜在的指导意义和参考价值。关于稳定性在 具体某个本体学习算法中的表现，在未来的本体算 法执行中有待进一步实验验证。 参考文献： SKALLE P, AAMODT A. Petrol 18 946: downhole failures revealed through ontology engineering[J]. Journal of petroleum science and engineering, 2020, 191: 107188. [1] SOBRAL T, GALVÃO T, BORGES J. An ontologybased approach to knowledge-assisted integration and visualization of urban mobility data[J]. Expert systems with applications, 2020, 150: 113260. [2] AL-SAYED M M, HASSAN H A, OMARA F A. CloudFNF: an ontology structure for functional and non-functional features of cloud services[J]. Journal of parallel and distributed computing, 2020, 141: 143–173. [3] [4] TEBES G, PEPPINO D, BECKER P, et al. Analyzing and 第 17 卷 智 能 系 统 学 报 ·478·
·479· 朱林立，等：本体学习算法的两类L00一致稳定性和广义界 第3期 documenting the systematic review results of software [18]ZHU Linli,YU Pan,FARAHANI M R,et al.Theoretic- testing ontologies[J].Information and software techno- al characteristics on scoring function in multi-dividing 1ogy,2020,123:106298. setting[J].IAENG international journal of applied math- [5]PRADEEP D.SUNDAR C.QAOC:novel query analysis ematics,2017,47(1:28-36. and ontology-based clustering for data management in [19]ZHU Linli,TAO Weige,MIN Xiaozhong,et al.Theoret- Hadoop[J].Future generation computer systems,2020, ical characteristics of ontology learning algorithm in 108:849-860. multi-dividing setting[J].IAENG international journal of [6]HEMA A M.KUPPUSAMY K.A novel trust-based pri- computer science,2016,43(2):184-191. vacy preservation framework for service handling via on- [20]GAO Wei.XU Tianwei.Stability analysis of learning al- tology service ranking[J].Wireless personal communica- gorithms for ontology similarity computation[J].Ab- tions,.2020,112(3):1339-1354. stract and applied analysis,2013,2013:174802 [7]MESSAOUDI R,MTIBAA A,VACAVANT A,et al. [21]GAO W,ZHANG Y G,XU T W,et al.Analysis for Ontologies for liver diseases representation:a systematic learning a similarity function with ontology applica- literature review[J].Journal of digital imaging,2020, tions[J].Journal of information and computational sci- 33(3):563-573. ence,2012,17(9):5311-5318. [8]MANTOVANI A,PIANA F,LOMBARDO V.Ontology- [22]BASSILY R.NISSIM K.SMITH A.et al.Algorithmic driven representation of knowledge for geological maps stability for adaptive data analysis[Cl//Proceedings of [J]Computers and geosciences,2020,139:104446. the Forty-Eighth Annual ACM Symposium on Theory of [9]ABEYSINGHE R.HINDERER III E W.MOSELEY H N Computing.Cambridge:ACM,2016:1046-1059. B,et al.SSIF:subsumption-based sub-term inference [23]STEINKE T,ULLMAN J.Subgaussian tail bounds via framework to audit gene ontology[J].Bioinformatics, stability arguments[EB/OL](2017-04-21)[2021-01-09] 2020,36(10):3207-3214 https://arxiv.org/abs/1701.03493v2. [10]KOSSMANN M.SAMHAN A,ODEH M,et al.Extend- [24]MCDIARMID C.On the method of bounded differ- ing the scope of configuration management for the de- ences[M]//SIEMONS J.Surveys in Combinatorics, velopment and life cycle support of systems of systems- 1989:Invited Papers at the Twelfth British Combinatori- an ontology-driven framework applied to the enceladus al Conference.Cambridge:Cambridge University Press, submarine exploration lander[J].Systems engineering, 1989:148-188 2020,23(3):366-391. [11]ZHU Linli,HUA Gang,ASLAM A.Ontology learning [25]WALLSTROM T C.On the application of McDiarmid's algorithm using weak functions[J].Open physics,2018, inequality to complex systems[J].SIAM-ASA journal on 16(1):910-916. uncertainty quantification,2017,5(1):240-245. [12]GAO Wei,ZHANG Yunqing,GUIRAO J L G,et al.A 作者简介： discrete dynamics approach to sparse calculation and ap- 朱林立，高级工程师，博士，主要 plied in ontology science[J].Journal of difference equa- 研究方向为人工智能、机器学习。 tions and applications,2019,25(9/10):1239-1254. [13]ZHU Linli,HUA Gang,ZAFAR S,et al.Fundamental ideas and mathematical basis of ontology learning al- gorithm[J].Journal of intelligent and fuzzy systems, 2018.35(4):4503-4516. [14]GAO Wei.GUIRAO J L G.BASAVANAGOUD B,et al.Partial multi-dividing ontology learning algorithm[J] 华钢，教授，博士，主要研究方向 Information sciences,2018,467:35-58. 为物联网、矿山监控与监管、智能信息 [15]朱林立，华钢.高炜.决定图框架下本体学习算法的稳 处理。 定性分析.计算机科学，2020,47(5)：43-50 ZHU Linli,HUA Gang,GAO Wei.Stability analysis of ontology learning algorithm in decision graph setting[J]. Computer science,2020,47(5):43-50. [16]ZHU Linli,YU Pan,FARAHANI M R,et al.Mag- 高炜，教授，博士，主要研究方向 nitude preserving based ontology regularization al- 为图论、人工智能和统计学习理论。 gorithm[J].Journal of intelligent and fuzzy systems, 2017,33(5):3113-3122 [17]ZHU Linli,YU Pan,JAMIL M K,et al.Boosting based ontology sparse vector computation approach[J].Engin- eering letters,2017,25(4):406-415
documenting the systematic review results of software testing ontologies[J]. Information and software technology, 2020, 123: 106298. PRADEEP D, SUNDAR C. QAOC: novel query analysis and ontology-based clustering for data management in Hadoop[J]. Future generation computer systems, 2020, 108: 849–860. [5] HEMA A M, KUPPUSAMY K. A novel trust-based privacy preservation framework for service handling via ontology service ranking[J]. Wireless personal communications, 2020, 112(3): 1339–1354. [6] MESSAOUDI R, MTIBAA A, VACAVANT A, et al. Ontologies for liver diseases representation: a systematic literature review[J]. Journal of digital imaging, 2020, 33(3): 563–573. [7] MANTOVANI A, PIANA F, LOMBARDO V. Ontologydriven representation of knowledge for geological maps [J] Computers and geosciences, 2020, 139: 104446. [8] ABEYSINGHE R, HINDERER III E W, MOSELEY H N B, et al. SSIF: subsumption-based sub-term inference framework to audit gene ontology[J]. Bioinformatics, 2020, 36(10): 3207–3214. [9] KOSSMANN M, SAMHAN A, ODEH M, et al. Extending the scope of configuration management for the development and life cycle support of systems of systemsan ontology-driven framework applied to the enceladus submarine exploration lander[J]. Systems engineering, 2020, 23(3): 366–391. [10] ZHU Linli, HUA Gang, ASLAM A. Ontology learning algorithm using weak functions[J]. Open physics, 2018, 16(1): 910–916. [11] GAO Wei, ZHANG Yunqing, GUIRAO J L G, et al. A discrete dynamics approach to sparse calculation and applied in ontology science[J]. Journal of difference equations and applications, 2019, 25(9/10): 1239–1254. [12] ZHU Linli, HUA Gang, ZAFAR S, et al. Fundamental ideas and mathematical basis of ontology learning algorithm[J]. Journal of intelligent and fuzzy systems, 2018, 35(4): 4503–4516. [13] GAO Wei, GUIRAO J L G, BASAVANAGOUD B, et al. Partial multi-dividing ontology learning algorithm[J]. Information sciences, 2018, 467: 35–58. [14] 朱林立, 华钢, 高炜. 决定图框架下本体学习算法的稳 定性分析 [J]. 计算机科学, 2020, 47(5): 43–50. ZHU Linli, HUA Gang, GAO Wei. Stability analysis of ontology learning algorithm in decision graph setting[J]. Computer science, 2020, 47(5): 43–50. [15] ZHU Linli, YU Pan, FARAHANI M R, et al. Magnitude preserving based ontology regularization algorithm[J]. Journal of intelligent and fuzzy systems, 2017, 33(5): 3113–3122. [16] ZHU Linli, YU Pan, JAMIL M K, et al. Boosting based ontology sparse vector computation approach[J]. Engineering letters, 2017, 25(4): 406–415. [17] ZHU Linli, YU Pan, FARAHANI M R, et al. Theoretical characteristics on scoring function in multi-dividing setting[J]. IAENG international journal of applied mathematics, 2017, 47(1): 28–36. [18] ZHU Linli, TAO Weige, MIN Xiaozhong, et al. Theoretical characteristics of ontology learning algorithm in multi-dividing setting[J]. IAENG international journal of computer science, 2016, 43(2): 184–191. [19] GAO Wei, XU Tianwei. Stability analysis of learning algorithms for ontology similarity computation[J]. Abstract and applied analysis, 2013, 2013: 174802. [20] GAO W, ZHANG Y G, XU T W, et al. Analysis for learning a similarity function with ontology applications[J]. Journal of information and computational science, 2012, 17(9): 5311–5318. [21] BASSILY R, NISSIM K, SMITH A, et al. Algorithmic stability for adaptive data analysis[C]//Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. Cambridge: ACM, 2016: 1046−1059. [22] STEINKE T, ULLMAN J. Subgaussian tail bounds via stability arguments[EB/OL](2017−04−21)[2021−01−09] https://arxiv.org/abs/1701.03493v2. [23] MCDIARMID C. On the method of bounded differences[M]//SIEMONS J. Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference. Cambridge: Cambridge University Press, 1989: 148−188. [24] WALLSTROM T C. On the application of McDiarmid’s inequality to complex systems[J]. SIAM-ASA journal on uncertainty quantification, 2017, 5(1): 240–245. [25] 作者简介： 朱林立，高级工程师，博士，主要 研究方向为人工智能、机器学习。 华钢，教授，博士，主要研究方向 为物联网、矿山监控与监管、智能信息 处理。 高炜，教授，博士，主要研究方向 为图论、人工智能和统计学习理论。 ·479· 朱林立，等：本体学习算法的两类 LOO 一致稳定性和广义界 第 3 期
