Two classes of LOO uniform stability and generalization bounds of ontology learning algorithm
-
摘要: 近年来，随着本体研究的深入，各类机器学习方法被尝试应用于本体相似度计算和本体映射获取。稳定性是本体学习算法的必要条件，它从本质上体现了算法的可用性，即要求本体学习算法的最优解不会受到本体样本的小幅度调整而发生大的变化。本文研究了删除一个本体样本点的条件下，对本体学习算法的期望误差与经验误差的差值产生的影响。分别在本体学习算法一致稳定和假设空间一致稳定两种不同的框架下，利用统计学习理论的技巧，得到对应广义界的上界估计。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.
-
本体的概念首先属于西方哲学的范畴，是指客观存在在逻辑层面上的表达和概括。作为形而上学的一个分支，本体论在哲学领域的主要研究问题是“是否存在非物质事物”。20世纪80年代引入到人工智能领域，之后对本体有自己的定义。近年来，本体作为概念语义表示的工具，与其他数据库相比，有着结构化存储、易于在不同本体之间建立映射和本体对齐等优势，因而被广泛应用于各个学科，在生物、化学、医学、材料、能源等领域都能看到本体在特定的场景下发挥作用。
Skalle等[1]阐述了如何使用知识建模和本体工程方法开发模型，并利用本体模型来预测钻井过程中的井下故障。Sobral等[2]提出了一个基于本体的框架来支持来自智能交通系统的数据的集成和可视化。Al-Sayed等[3]设计了一种称为 CloudFNF 的综合云本体，根据该本体结构，云服务被分类为若干个类别。Tebes等[4]给出分析和记录软件测试本体的系统审查结果的方法。Pradeep等[5]在基于本体的平衡二叉树中搜索预定的用户查询，最后使用 Okapi BM25 对相关结果进行排序并交付给用户。Hema等[6]提出了一种新的基于信任的隐私保护框架，通过本体服务排序TBPF-OSR进行用户身份验证。 Messaoudi等[7]给出了关于疾病治疗医学本体研究的综述。Mantovani等[8]提出了一种本体驱动的地质图知识表示。 本体形式语言允许通过语义类别和属性对地球科学家的解释进行机器可读编码，并支持知识共享和互操作性。Abeysinghe等[9]通过在基因本体(gene ontology, GO)本体概念的基于序列的表示之上，利用新的术语代数以及3个条件规则（单调性、交集和子概念规则）开发了基于包含的子项推理框架。Kossmann等[10]提出了潜艇探测着陆器的本体驱动框架。
随着越来越多的本体被定义和应用，以及越来越多的本体算法被设计并尝试用于不同的本体工程应用领域，学习算法也被逐渐应用于本体。本体学习算法就是将机器学习方法与本体自身结构相融合，通过本体样本的学习得到本体函数。具体地说，本体用图结构表示，设
$ G = (V,E) $ 为本体图对应某个本体O，其顶点对应O中概念，顶点之间的边对应两个顶点某种直接联系。本体可以用有向图来表示，其中边的权值由边的类型等因素决定。本体学习算法可以看成图算法，通过本体样本S按照一定的学习规则学习得到本体函数$ f:V \to \bf{R} $ 。该本体函数的作用是将整个本体图映射到一维实数轴，每个本体顶点（对应本体概念）映射为一维实数。在最开始的本体数值化表示中，往往要求每个本体顶点都用一个p维向量来表示，因此本体学习算法本质上就变成一种降维算法，目标是得到本体函数$f:{{\bf{R}}^p} \to \bf{R}$ 。相关本体学习这方面的研究可参考文献[11-19]。稳定性是一个本体学习算法在具体工程应用领域可以使用的基本条件，它要求算法在学习样本集发生轻微改变时输出结果不会发生本质性的改变。常见的变换有：删除一个样本(leave one out, LOO)，删除两个样本(leave two out, LTO)，替换一个样本(place one, PO)。只有满足稳定性的本体学习算法才具备泛化性，才有可能对同类数据发挥作用。已有部分文献对本体算法的稳定性进行了讨论，可参考文献[15，20-21]。
具体地说，通常把本体数据分成两类：训练集（样本集）和测试集。通过本体样本的训练，按照一定的本体学习算法得到本体函数，再将本体函数应用于同类本体数据（测试集）。我们希望从样本学习得到的本体函数同样适用于同一个本体的其他本体数据，即算法具有很好的扩展性能。这必须要求本体学习算法具有稳定性，即样本的轻微改变对学习得到的结果影响很小。从理论上说，稳定性是一种学习的平滑性，即最优函数的性能随着样本容量n的增加而缓缓提高，其特征曲线是平滑过渡的，不会在任何一点产生剧烈的震荡。而强烈的抖动意味着算法对于特定的本体样本点有着特定的反映，进而说明本体学习算法本身不适合实验对象数据，即这样的算法得到的最优本体函数不可能对训练集以外的数据产生很好的效果。
另一方面，理论研究最关心的是算法的收敛阶和误差界。本文的动机是在稳定性和误差界之间找到必然的联系。因此如果一个本体学习算法有很好的稳定性，那么它的学习误差就会控制在某个范围内。也就是说，本文的理论结果暗示了稳定性不仅是本体学习算法具有泛化性的前提，而且稳定性参数控制了本体学习算法广义界的上界。
本文针对删除一个样本的LOO操作，给出对应的本体学习算法稳定性和本体函数假设空间一致稳定性定义。并利用统计学方法，针对两类不同的LOO一致稳定性定义，分别给出广义界的估计值，这些界优于之前同框架LOO一致稳定性设定论文中得到的广义界。
1. 本体学习算法及稳定性
设
$ Z $ 为本体数据集，在非监督本体学习中，Z即为本体图顶点数据$ V $ ，对于监督本体学习则$ Z = V \times Y $ 。设本体学习算法$ A:{Z^n} \to F $ ，其中F是本体函数空间，即假设空间。$ A(S) $ 或者$ A(S, \cdot ) $ 表示本体学习算法A作用在本体数据S的输出函数。$l:F \times Z \to \bf{R}$ 为本体亏损函数（也可以将其正则化，即取值限定在区间[0,1]内，进而也可以表示为$ l:F \times Z \to [0,1] $ ），给定本体函数f和本体样本点v，本体亏损函数表示为$ l(f,z) $ 。设$S{\text{ = \{ }}{z_1}{\text{,}}\;{z_2}{\text{,}} \;\cdots {\text{,}}\;{z_n}{\text{\} }}$ 为容量为n的本体样本。删除样本集S中的第i($i \in $ $ \{ 1, \;2,\;\cdots ,\;n\}$ )个样本$ {v_i} $ ，对应的样本集变为${S^{\backslash i}} = $ $ \{{z_1}{\text{,}}\;{z_2},\; \cdots {\text{,}} \;{z_{i - 1}}{\text{,}}\;{z_{i + 1}}{\text{,}}\; \cdots {\text{,}}\;{z_n}\}$ ，称此类变换为LOO(leave one out)。在样本S的表示中，若算法为非监督本体学习算法，则$ {z_i} = {v_i} $ ；在监督本体学习下有$ {z_i} = ({v_i},{y_i}) $ 。如果对于任意位置i($ i \in \{ 1,2, \cdots ,n\} $ )，任意S和$ {S^{\backslash i}} $ ，以及任意$ v \in V $ ，有$$ \left| {l(A(S),z) - l(A({S^{\backslash i}}),z)} \right| \leqslant \gamma $$ 成立，则称本体算法A关于本体亏损函数l存在LOO一致稳定
$ \gamma $ 。设
${R_D}[l(A(S))] = {{\rm{E}}_{z \sim D}}[l(A(S),z)]$ 为本体算法A的期望误差，$ {\hat R_S}[l(A(S))] = $ ${{\rm{E}}_{z \sim S}}[l(A(S),z)] =\dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {l(A(S),{z_i})}$ 为对应的经验误差。从而本体算法A的广义界就定义为期望误差和经验误差的差值，记为$$ {\varDelta _{D - S}}(l(A)) = {R_D}[l(A(S))] - {\hat R_S}[l(A(S))] $$ 为了方便讨论且说明本文的结果具有更加一般的规律，定理1给出的广义界对任意本体数据依赖函数都成立。具体地说，设
$M:{Z^n} \times Z \to \bf{R}$ （也可以限制其值域$ M:{Z^n} \times Z \to [0,1] $ ）为本体数据依赖函数(ontology data-dependent function)，它将给定本体数据集S和本体点z作为输入，可以看作计算实值函数$ M(S, \cdot ) $ 应用到z。这里$ M(S) $ 或者$ M(S, \cdot ) $ 表示M作用在本体数据S上而得到的输出函数。事实上，在本体学习框架下，有$ M(S,z) = $ $ l(A(S),z) $ ，只是前者的表示有另外的数据统计含义，可以依赖于本体数据。在此设定下，期望误差和经验误差分别表示为${R_D}[M(S)] = {{\rm{E}}_{z \sim D}}[M(S,z)]$ 和$ {\hat R_S}[M(S)] = $ ${{\rm{E}}_{z \sim S}}[M(S,z)] = \dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {M(S,{z_i})}$ 。对应的广义界表示为$ {\Delta _{D - S}}(M) = {R_D}[M(S)] - {\hat R_S}[M(S)] $ 。考虑将本体样本S作为输入，本体数据依赖函数作为输出，比如在本体监督学习中，每个本体样本点带有标记信息y，因而
$ M(S,z) = {l_Y}(f(v),y) $ ，即在本体样本$ z = (v,y) $ 上执行本体学习算法$ A(S) $ 。若对所有
$ S \in {Z^n} $ ，任意$ i \in \{ 1,2, \cdots ,n\} $ ，任意$ z \in Z $ 有$ \left| {M(S,z) - M({S^{\backslash i}},z)} \right| \leqslant \gamma $ 成立，则称本体数据依赖函数$M:{Z^n} \times Z \to \bf{R}$ 存在LOO一致稳定$ \gamma $ 。若对所有$ S,S' \in {Z^n} $ ，其中S和S’是容量相同的两个本体数据集且只有一个数据不相同，满足$ \forall E \subseteq Y $ ，有$$ {{P}}[M(S) \in E] \leqslant {e^\varepsilon }{{P}}[M(S') \in E] $$ 则称算法
$ A:{Z^n} \to Y $ 是$ \varepsilon $ -差分隐私（leave-one-out-$ \varepsilon $ -differentially private）的。本体学习算法的假设空间(hypothesis space)就是本体函数选取的范围空间，也称为假设集，它是本体学习算法设计的核心。假设空间过大意味着函数选取的范围很大，会导致算法不收敛；而假设空间过小又会导致得到的最优本体函数性能不佳。理想的本体学习算法都会对假设空间有精巧的设计，一般在数学上会选取凸函数空间，常见的本体假设空间有再生核希尔伯特空间、索伯列夫空间等。由于假设空间是一个抽象的函数空间，一般用抽象的工具来刻画它的大小，比如覆盖数(covering number)。在一般学习框架下，本体假设空间是由算法本身决定的，独立于本体样本，记为F。本文将考虑受本体数据集影响的假设空间，称为本体样本依赖假设集(ontology sample dependent hypothesis set)，也称为本体数据依赖假设集(ontology data dependent hypothesis set)，记为
$ {F_S} $ ，表示根据本体训练样本集S而选取的本体函数空间。F和$ {F_S} $ 的关系是：当S给定后，$ {F_S} $ 通常选取为F的一个子集，即$ {F_S} \subset F $ 。进而可以写成$ F = \bigcup\limits_{S \in {Z^n}} {{F_S}} $ 。这样，F表示为本体数据依赖假设集的并集，故也称$ F = {({F_S})_{S \in {Z^n}}} $ 为本体数据依赖假设集族。给定本体样本容量
$n \in \bf{N}$ 。如果对任意$i \in $ $ \{ 1,2, \cdots ,n\}$ ，任意本体样本集$ S $ 和删除一个元素后的本体样本集$ {S^{\backslash i}} $ ，存在某个$ \beta \geqslant 0 $ ，对任意$ f \in {F_S} $ ，都存在某个$ {f'} \in {F_{{S^{\backslash i}}}} $ ，使得对任意$ z \in Z $ 都有$\left| l(f,z) -\right. $ $ \left. l({f'},z) \right| \leqslant \beta$ 成立。则称本体数据依赖假设集族$ F = $ $ {({F_S})_{S \in {Z^n}}} $ 存在LOO一致稳定$ \beta $ ，简称$ \beta $ -稳定。给定本体样本容量
$n \in \bf{N}$ 。若对任意$ S \in {Z^n} $ ，都有${{ \mathop{\rm{E}}\limits_{z \sim S}}} \left[{\mathop {\sup }\limits_{f \in {F_S},{f'} \in {F_{{S^{\backslash i}}}}}} (l(f,z) - l({f'},z))\right] \leqslant \chi$ 成立，则称本体数据依赖假设集族$ F = {({F_S})_{S \in {Z^n}}} $ 存在LOO-CV稳定$ \chi $ ，其中$ \chi \geqslant 0 $ 。更进一步，若${\mathop {\rm{E}}\limits_{S \sim {D^n},z \sim S} }\left[{\mathop {\sup }\limits_{f \in {F_S},{f'} \in {F_{{S^{\backslash i}}}}}} (l(f,z) - \right.$ $l({f'},z))\Bigg] \leqslant \bar \chi$ 成立，则称$ F $ 存在LOO-均值CV稳定$ \bar \chi $ ，同样$ \bar \chi \geqslant 0 $ 。本体数据依赖假设集族
$ F = {({F_S})_{S \in {Z^n}}} $ 的直径$ \Delta $ 和均值直径$ \bar \Delta $ 分别定义为$$ \Delta = {\mathop {\sup }\limits_{S \in {Z^n}}} \mathop {\rm{E}}\limits_{z \sim S} \left[\mathop {\sup }\limits_{f,{f'} \in {F_S}} (l(f,z) - l({f'},z))\right] $$ $$ \bar \Delta = {\mathop {\rm{E}}\limits_{S \in {Z^n},z \sim S}} \left[{\mathop {\sup }\limits_{f,{f'} \in {F_S}} }(l(f,z) - l(f',z))\right]$$ 对任意两个本体样本集
$ S,T \in {Z^n} $ 以及拉德马赫向量${\boldsymbol{\sigma}}$ ，集合${S_{T,{\boldsymbol{\sigma}} }}$ 由S通过如下变换得到：对于$ i \in \{ 1,2, \cdots ,n\} $ ，若发现${{\boldsymbol{\sigma}} _i} = - 1$ ，则将S中第i个元素替换成集合T中的第i个元素。将假设集${F_{{S_{T,{\boldsymbol{\sigma }}}}}}$ 记为$ F_{S,T}^\sigma $ 。固定
$ n \in \bf{N} $ ，本体数据依赖假设集族$ F = {({F_S})_{S \in {Z^n}}} $ 关于两个本体样本集$S = \left\{ z_1^S,z_2^S, \cdots ,z_n^S\right\}$ 和$T = \left\{ z_1^T,\right. $ $ \left.z_2^T, \cdots ,z_n^T\right\}$ 的拉德马赫复杂度(Rademacher complexity)和经验拉德马赫复杂度(empirical Rademacher complexity)分别定义为$$ {\Xi _n}(F) = \frac{1}{n}{\mathop {\rm{E}}\limits_{S,T \sim {D^n},{\boldsymbol{\sigma}} }} \left[\mathop {\sup }\limits_{f \in F_{S,T}^{{\boldsymbol{\sigma}}} } \sum\limits_{i = 1}^n {{{\boldsymbol{\sigma}} _i}f({{\boldsymbol{z}}_i}^T)} \right] $$ $$ {\hat \Xi _{S,T}}(F) = \frac{1}{n}{\mathop {\rm{E}}\limits_{\sigma}} \left[\mathop {\sup }\limits_{f \in F_{S,T}^\sigma } \sum\limits_{i = 1}^n {{\sigma _i}f({\boldsymbol{z}}_i^T)} \right] $$ 2. 算法理论分析
定理1 设
$ M:{Z^n} \times Z \to [0,1] $ 为本体数据依赖函数且存在LOO一致稳定$ \gamma $ ，则对于任意Z上的概率分布D和任意$ \delta \in (0,1) $ ，有$$ {\mathop {\rm{E}}\limits_{S \sim {D^n}}} [{({\Delta _{D - S}}(M))^2}] \leqslant 64{\gamma ^2} + \frac{2}{n} $$ (1) $$ {\mathop {{P}}\limits_{S \sim {D^n}}} \left[{\Delta _{D - S}}(M) \geqslant 8\sqrt {(4\gamma + \frac{1}{n})\ln \frac{8}{\delta }}\; \right] \leqslant \delta $$ (2) 本文的第一个主要结果给出了本体数据依赖函数框架下的学习算法广义界以及广义界平方的上界，其中式(1）说明本体稳定算法的误差界的平方的期望值可以被一致稳定参数所控制在某个固定的范围内，而式(2)则说明误差界越大，它发生的概率越小。
证明 考虑m个本体数据集，每个数据集的容量均为n。为了防止混淆，称其为多重本体数据集，记为
${S}$ 。显然${S} \in {Z^{m \times n}}$ ，将每个本体子数据集分别记为${{S}_1},{{S}_2}, \cdots ,{{S}_m}$ ，且第$ l $ 个本体子数据集的第$ i $ 个元素记为${{S}_{l,i}}$ 。设$ l \in \{ 1,2, \cdots ,m\} $ ，定义$$ {f_l}({S}) = {\Delta _{D - {{S}_l}}}(M)= {R_D}[M({{S}_l})] - {\hat R_{{{S}_l}}}[M({{S}_l})] $$ (3) 设
${S}$ 和${{S}'}$ 是两个多重本体数据集，且${{S}'}$ 与${S}$ 相比仅仅是第k个本体数据子集的第i个元素不同。设${{S}^{\backslash k(i)}}$ 为多重本体数据集，它通过删除${{S}'}$ 中第k个本体数据子集的第i个元素得到。如果$ l \ne k $ ，则${{S}_l} = {{{S}}_l'}$ ，进而有${f_l}({S}) = {f_l}({{S}'})$ 。若$ l = k $ ，则$$\begin{aligned} &\;\;\;\left| {{R_D}[M({{S}_l})] - {R_D}[M({S}_l')]} \right|= |{R_D}[M({{S}_l})] - {R_D}[M({S}_l^{\backslash k(i)})]+ \\ & {R_D}[M({S}_l^{\backslash k(i)})] - {R_D}[M({S}_l')]|\leqslant \left| {{R_D}[M({{S}_l})] - {R_D}[M({S}_l^{\backslash k(i)})]} \right|+ \\ & \left| {{R_D}[M({S}_l^{\backslash k(i)})] - {R_D}[M({S}_l')]} \right|= \left| {{\mathop {\rm{E}}\limits_{z \sim D}} [M({{S}_l},z) - M({S}_l^{\backslash k(i)},z)]} \right|+\\ & \quad\quad\quad\quad\quad \left| {{\mathop {\rm{E}}\limits_{z \sim D}} [M({S}_l^{\backslash k(i)},z) - M({S}_l',z)]} \right| \leqslant 2\gamma \end{aligned}$$ $$\begin{aligned} & \quad\quad\quad\left| {{{\hat R}_{{{S}_l}}}[M({{S}_l})] - {{\hat R}_{{S}_l'}}[M({S}_l')]} \right|=\\ & \quad \left| {\frac{1}{n}\sum\limits_{j = 1}^n {M({{S}_l},{{S}_{l,j}})} - \frac{1}{n}\sum\limits_{j = 1}^n {M({S}_l',{S}_{l,j}')} } \right| \leqslant\\ & \left| {\frac{1}{n}\sum\limits_{j = 1,i \ne j}^n {M({{S}_l},{{S}_{l,j}})} - \frac{1}{n}\sum\limits_{j = 1,i \ne j}^n {M({S}_l',{S}_{l,j}')} } \right| + \\ & \quad\quad\quad \left| {\frac{1}{n}M({{S}_l},{{S}_{l,i}}) - \frac{1}{n}M({S}_l',{S}_{l,i}')} \right| \leqslant\\ & \left| {\frac{1}{n}\sum\limits_{j = 1,i \ne j}^n {M({{S}_l},{{S}_{l,j}})} - \frac{1}{n}\sum\limits_{j = 1,i \ne j}^n {M({S}_l^{\backslash k(i)},{S}_{l,j}^{\backslash k(i)})} } \right| + \\ & \left| {\frac{1}{n}\sum\limits_{j = 1,i \ne j}^n {M({S}_l^{\backslash k(i)},{S}_{l,j}^{\backslash k(i)})} - \frac{1}{n}\sum\limits_{j = 1,i \ne j}^n {M({S}_l',{S}_{l,j}')} } \right|+ \\ & \quad\quad \quad\left| {\frac{1}{n}M({{S}_l},{{S}_{l,i}}) - \frac{1}{n}M({S}_l',{S}_{l,i}')} \right|\leqslant\\ & \quad\quad\quad\quad\quad\quad\quad 2\gamma + \frac{1}{n} \end{aligned}$$ 这说明
$\left| {{f_l}({S}) - {f_l}({S}_l')} \right| \leqslant 4\gamma + \dfrac{1}{n}$ 。对任意
$ l \in \{ 1,2, \cdots ,m\} $ ，设本体数据依赖函数$ {M_l}:{Z^n} \times Z \to [0,1] $ 拥有LOO一致稳定$ \gamma $ ，$A:{Z^{n \times m}} \to $ $ \{ 1,2, \cdots ,m\}$ 是$ \varepsilon $ -差分隐私算法。设
${X_{S}} = {{\rm{E}}_{{S} \sim {D^{mn}},l = A({S})}} $ $ [{\hat R_{{{S}_l}}}[{M_l}({{S}_l})]]$ ，${{I}}( \cdot )$ 为真值函数（论断为真时取值1，否则取值0），则$$\begin{aligned} &\quad\quad\quad{X_{S}} = {{\rm{E}}_{{S} \sim {D^{mn}},l = A({S})}}\left[\frac{1}{n}\sum\limits_{i = 1}^n {{M_l}({{S}_l},{{S}_{l,i}})} \right] =\\ & \quad\quad\quad{{\rm{E}}_{A,{S} \sim {D^{mn}}}}\left[\frac{1}{n}\sum\limits_{i = 1}^n {\sum\limits_{l = 1}^m {{{I}}(A({S}) = l){M_l}({{S}_l},{{S}_{l,i}})} } \right] =\\ & \quad\quad\frac{1}{n}\sum\limits_{i = 1}^n {\sum\limits_{l = 1}^m {{{\rm{E}}_{{S} \sim {D^{mn}}}}[{{\rm{E}}_A}[I(A({S}) = l)] \cdot {M_l}({{S}_l},{{S}_{l,i}})} } ] \leqslant\\ & \quad\quad\quad\frac{1}{n}\sum\limits_{i = 1}^n {\sum\limits_{l = 1}^m {{{\rm{E}}_{{S} \sim {D^{mn}}}}[{{\rm{e}}^\varepsilon } \cdot {{\rm{E}}_A}[I(A({{S}^{l(i),z}}) = l)]} } \times\\ &\quad\quad\quad\quad\quad\quad\quad({M_l}({S}_l^{i,z},{{S}_{l,i}}) + \gamma )] =\\ &\frac{1}{n}\sum\limits_{i = 1}^n {\sum\limits_{l = 1}^m {{{\rm{E}}_{{S} \sim {D^{mn}},z \sim D}}[{{\rm{e}}^\varepsilon } \cdot {{\rm{E}}_A}[I(A({S}) = l)]} } \cdot ({M_l}({{S}_l},z) + \gamma )] = \\ & \quad\quad\quad\quad{{\rm{E}}_{{S} \sim {D^{mn}},z \sim D,l = A({S})}}[{{\rm{e}}^\varepsilon } \cdot ({M_l}({{S}_l},z) + \gamma )]= \\ & \;\;\quad\quad\quad\quad{{\rm{e}}^\varepsilon }({{\rm{E}}_{{S} \sim {D^{mn}},z \sim D,l = A({S})}}[{M_l}({{S}_l},z)] + \gamma ) \end{aligned}$$ 式中：
${{S}^{l(i),z}}$ 为多重本体数据集，它通过将第l个本体数据子集的第i个元素替换成z得到；${S}_l^{i,z}$ 是通过将${{S}_l}$ 中第i个元素替换成z得到的本体数据子集。由此可以得到
$$ {{\rm{e}}^{ - \varepsilon }}{X_{S}} - \gamma \leqslant {{\rm{E}}_{{S} \sim {D^{mn}},l = A({S})}}[{R_D}[{M_l}({{S}_l})]]\leqslant {{\rm{e}}^\varepsilon }{X_{S}} + \gamma $$ (4) 式（4）的后半部分可以用类似的方法得到。特别地，有
$$ \left| {{{\rm{E}}_{{S} \sim {D^{mn}},l = A({S})}}\left[{R_D} \left[{M_l}({{S}_l})\right] - {{\hat R}_{{{S}_l}}}\left[{M_l}({{S}_l})\right]\right]} \right|\leqslant {{\rm{e}}^\varepsilon } - 1 + \gamma $$ (5) 首先证明(2)成立。取
$m = \dfrac{{\ln 2}}{\delta }$ ，设$ {f_1},{f_2}, \cdots ,{f_m} $ 为实值函数(如式(3)定义)，${f_{m + 1}}({S}) = 0$ 。设A是${f_1}, $ $ {f_2}, \cdots , {f_m},{f_{m + 1}}$ 上的执行算法满足对任意$l \in \{ 1, 2, \cdots , $ $ m\}$ 有$\left| {{f_l}({S}) - {f_l}({S}_l')} \right| \leqslant 4\gamma + \dfrac{1}{n}$ 。注意到，对于$l \in \{ 1,2, \cdots , $ $ m\}$ 有$ {M_l} = M $ 且$ {M_{m + 1}} = 0 $ ，因此由式（5）可知：$$\begin{aligned} &\quad\quad\quad\quad\quad\quad{{\rm{E}}_{{S} \sim {D^{(m + 1)n}}}}[{{\rm{E}}_{l = A({S})}}{f_l}({S})] =\\ &{\rm{E}}_{a-D^{(m+1) m},-A(a)}\left[R_{D}\left[M_{l}\left(Q_{l}\right)\right]-\hat{R}_{m_{l}}\left[M_{l}\left({{S}}_{l}\right)\right]\right] \leqslant {{\rm{e}}^\varepsilon } - 1 + \gamma \end{aligned}$$ 运用文献[22]中引理7.1可知：
$$\begin{aligned} &{{\rm{E}}_{{S} \sim {D^{mn}}}}\left[{\rm{max}}\left\{\mathop {{\rm{max}}}\limits_{l \in \{ 1,2, \cdots ,m\} } {R_D}[M({{S}_l})] - {\hat R_{{{S}_l}}}[M({{S}_l})],0\right\} \right] =\\ &\quad\quad\quad\quad\quad\quad{{\rm{E}}_{{S} \sim {D^{mn}}}}\left[\mathop {\max }\limits_{l \in [0,m]} {f_l}({S})\right]\leqslant\\ &\quad\;\;{{\rm{E}}_{{S} \sim {D^{mn}}}}[{{\rm{E}}_{l = A({S})}}{f_l}({S})] + \dfrac{{2\left(4\gamma + \dfrac{1}{n}\right)}}{\varepsilon }\ln (m + 1)\leqslant\\ &\quad\quad\quad\quad\quad{{\rm{e}}^\varepsilon } - 1 + \gamma + \frac{{8\gamma + \dfrac{2}{n}}}{\varepsilon }\ln (m + 1) \end{aligned} $$ 选取
$\varepsilon = \sqrt {\left(4\gamma + \dfrac{1}{n}\right)\ln (m + 1)} = \sqrt {\left(4\gamma + \dfrac{1}{n}\right)\ln \left(\dfrac{{{\rm{e}}\ln 2}}{\delta }\right)}$ 当$\varepsilon \geqslant \dfrac{1}{2}$ 时式（2）显然成立。当$\varepsilon < \dfrac{1}{2}$ 时有${{\rm{e}}^\varepsilon } - 1 \leqslant 2\varepsilon$ ，进而根据$ \gamma \leqslant \sqrt \gamma $ 有$$ 4\sqrt {\left(4\gamma + \frac{1}{n}\right){\rm{ln}}\left(\frac{{{\rm{e}}\ln 2}}{\delta }\right)} + \gamma \leqslant 4\sqrt {\left(4\gamma + \frac{1}{n}\right){\rm{ln}}\left(\frac{8}{\delta }\right)} $$ 结合文献[23]中引理1.2可知：
$$ {\mathop {{P}}\limits_{S \sim {D^n}}} \left[{R_D}[M(S)] - {\hat R_S}[M(S)] \geqslant 8\sqrt {\left(4{\gamma _n} + \frac{1}{n}\right)\ln \frac{8}{\delta }}\; \right] \leqslant \dfrac{{\ln 2}}{m} \leqslant \delta $$ 从而式(2)成立。
式(1)证明：设
$L(S,z) = M(S,z) - {R_D} [M(S)]$ ，则易证L是关于分布D的无偏估计，对任意$ S \in {Z^n} $ 都有$ {R_D}[L(S)] = 0 $ 。由于M的取值范围在[0,1]内，因此L取值范围是[−1,1]。由于$$\begin{aligned} \left| {{R_D}[M(S)] - {R_D}[M({S^{\backslash i}})]} \right| \leqslant \left| {{\mathop {{\rm{E}}}\limits_{z \sim D}} [M(S,z) - M({S^{\backslash i}},z)]} \right| \leqslant \gamma \end{aligned}$$ L拥有LOO一致稳定至多为
$ 2\gamma $ 。又因为$$\begin{aligned} {\varDelta _{D - S}}(M) = {R_D}[M(S)] - {\hat R_S}[M(S)]=\quad\quad \quad\quad \quad \\ \frac{1}{n}\sum\limits_{i = 1}^n {({R_D}[M(S)] - M(S,{z_i}))} =- \frac{1}{n}\sum\limits_{i = 1}^n {L(S,{z_i})} = - {\hat R_S}[L(S)]\end{aligned}$$ 得到
$$ \mathop {\rm{E}}\limits_{S \sim {D^n}} \left[{({\Delta _{D - S}}(M))^2}\right] = \mathop {\rm{E}}\limits_{S \sim {D^n}} \left[{({\hat R_S}[L(S)])^2}\right] $$ 由此，式(1)等价于证明：设本体数据依赖函数
$ L:{Z^n} \times Z \to [ - 1,1] $ 拥有LOO一致稳定$ 2\gamma $ ，D是Z上的任意分布。如果L是关于D的无偏估计，则有$$ \mathop {\rm{E}}\limits_{S \sim {D^n}} \left[{({\hat R_S}[L(S)])^2}\right] \leqslant 64{\gamma ^2} + \frac{2}{n} $$ (6) 记
$ {S^{i,z}} $ 是将S中的第i个元素替换为z，并设$R_S^D[L(S)] = \mathop {\rm{E}}\limits_{z \sim D} \left[\dfrac{1}{n}{\displaystyle\sum\limits_{i = 1}^n} {L({S^{i,z}},{z_i})}\right]$ ,有$$\begin{aligned} &\quad\quad\quad\quad\quad\quad\left| {{{\hat R}_S}[L(S)] - R_S^D[L(S)]} \right| =\\ &\quad\quad\quad\left| {\frac{1}{n}\sum\limits_{i = 1}^n {L(S,{z_i})} - \mathop {\rm{E}}\limits_{z \sim D} \left[\frac{1}{n}\sum\limits_{i = 1}^n {L({S^{i,z}},{z_i})}\right] } \right|\leqslant\\ &\quad\quad\quad\quad\left| {\frac{1}{n}\sum\limits_{i = 1}^n {\mathop {\rm{E}}\limits_{z \sim D} }\left[L(S,{z_i}) - L({S^{i,z}},{z_i})\right]} \right|= \\ & \left|\frac{1}{n}\sum\limits_{i = 1}^n {\mathop {\rm{E}}\limits_{z \sim D} }\left[L(S,{z_i}) - L({S^{\backslash i}},{z_i}) + L({S^{\backslash i}},{z_i}) - L({S^{i,z}},{z_i})\right]\right|\leqslant\\ & \quad\quad\quad\quad \left| {\frac{1}{n}\sum\limits_{i = 1}^n {\mathop {\rm{E}}\limits_{z \sim D} }\left[L(S,{z_i}) - L({S^{\backslash i}},{z_i})\right]} \right|+ \\ & \quad \left| {\frac{1}{n}\sum\limits_{i = 1}^n {\mathop {\rm{E}}\limits_{z \sim D} }\left[L({S^{\backslash i}},{z_i}) - L({S^{i,z}},{z_i})\right]} \right|\leqslant 2\gamma + 2\gamma = 4\gamma\end{aligned}$$ $$\begin{aligned} \quad\mathop {\rm{E}}\limits_{S \sim {D^n}} \left[{(R_S^D[L(S)])^2}\right] \leqslant \mathop {\rm{E}}\limits_{S \sim {D^n},z \sim D} \left[{\left(\frac{1}{n}\sum\limits_{i = 1}^n {L({S^{i,z}},{z_i})} \right)^2}\right]=\quad\quad\quad\\ \frac{1}{{{n^2}}}\sum\limits_{i = 1}^n {\mathop {\rm{E}}\limits_{S \sim {D^n},z \sim D} \left[{{(L({S^{i,z}},{z_i}))}^2}\right]}+\quad\quad\quad\quad\quad\quad\\ \frac{1}{{{n^2}}}\sum\limits_{i,j \in \{ 1,2, \cdots ,n\} ,i \ne j} {\mathop {\rm{E}}\limits_{S \sim {D^n},z \sim D} \left[L({S^{i,z}},{z_i}) L({S^{j,z}},{z_j})\right]}\leqslant\quad\quad\quad\quad\\ \frac{1}{n} + \frac{1}{{{n^2}}}\sum\limits_{i,j \in \{ 1, 2,\cdots ,n\} ,i \ne j} {\mathop {\rm{E}}\limits_{S \sim {D^n},z \sim D} \left[L({S^{i,z}},{z_i}) L({S^{j,z}},{z_j})\right]} \quad\quad\quad\end{aligned}$$ 记
$ {S^{i,j,{z_i},{z_j}}} $ 是将S中的第i个元素和第j个元素分别替换为$ {z_i} $ 和$ {z_j} $ 而得到的新本体数据集，并设$ h(z) = \mathop {\min }\limits_{{z_i},{z_j} \in Z} L({S^{i,j,{z_i},{z_j}}},z) + 4\gamma $ 。注意到：
$$ \mathop {\max }\limits_{{z_i},{z_j} \in Z} L({S^{i,j,{z_i},{z_j}}},z) \leqslant \mathop {\min }\limits_{{z_i},{z_j} \in Z} L({S^{i,j,{z_i},{z_j}}},z) + 8\gamma $$ 可知：
$$ \left| {L({S^{i,j,{z_i},{z_j}}},z) - h(z)} \right| \leqslant 4\gamma $$ 因此：
$$\begin{aligned} &\quad\quad\quad\quad\mathop {\rm{E}}\limits_{S \sim {D^n},z \sim D} \left[L({S^{i,z}},{z_i}) L({S^{j,z}},{z_j})\right]= \\ &\quad\quad\quad\quad \mathop {\rm{E}}\limits_{{z_i},{z_j},z \sim D} \left[L({S^{i,z}},{z_i}) L({S^{j,z}},{z_j})\right]= \\ & \mathop {\rm{E}}\limits_{{z_i},{z_j},z \sim D} \left[(L({S^{i,z}},{z_i}) - h({z_i})) (L({S^{j,z}},{z_j}) - h({z_j}))\right]+\\ &\quad\quad\quad\quad\quad \mathop {\rm{E}}\limits_{{z_i},{z_j},z \sim D} \left[h({z_i})L({S^{j,z}},{z_j})\right]+\\ & \mathop {\rm{E}}\limits_{{z_i},{z_j},z \sim D} \left[h({z_j})L({S^{i,z}},{z_i})\right] - \mathop {\rm{E}}\limits_{{z_i},{z_j} \sim D} \left[h({z_i})h({z_j})\right]\leqslant {(4\gamma )^2} +\\ &\quad\quad\quad\quad\quad \mathop {\rm{E}}\limits_{{z_i},{z_j},z \sim D} \left[h({z_i})L({S^{j,z}},{z_j})\right]+\\ &\quad\quad \mathop {\rm{E}}\limits_{{z_i},{z_j},z \sim D} \left[h({z_j})L({S^{i,z}},{z_i})\right] - {\left(\mathop {\rm{E}}\limits_{z' \sim D} [h(z')]\right)^2}\end{aligned}$$ 考虑到L是无偏估计且函数h不依赖于
$ {z_i} $ 或$ {z_j} $ ，因此对应每个给定的$ {z_i} $ 和z，有$$ \mathop {\rm{E}}\limits_{{z_j} \sim D} \left[h({z_i})L({S^{j,z}},{z_j})\right] = h({z_i}){R_D}\left[L({S^{j,z}})\right] = 0 $$ 即
$$ \mathop {\rm{E}}\limits_{{z_i},{z_j},z \sim D} \left[h({z_i})L({S^{j,z}},{z_j})\right] = \mathop {\rm{E}}\limits_{{z_i},{z_j},z \sim D} \left[h({z_j})L({S^{i,z}},{z_i})\right] = 0 $$ 故有
$$\begin{aligned} &\quad\quad\quad\quad\quad\quad\mathop {\rm{E}}\limits_{S \sim {D^n}} \left[{(R_S^D[L(S)])^2}\right]\leqslant\\ & \dfrac{1}{n} + \dfrac{1}{{{n^2}}}\sum\limits_{i,j \in \{ 1,2, \cdots ,n\} ,i \ne j} {\mathop {\rm{E}}\limits_{S \sim {D^n},z \sim D} \left[L({S^{i,z}},{z_i}) L({S^{j,z}},{z_j})\right]} \leqslant\\ &\quad \dfrac{1}{n} + \dfrac{1}{{{n^2}}}\sum\limits_{i,j \in \{ 1, 2,\cdots ,n\} ,i \ne j} {\left(16{\gamma ^2} - {{\left(\mathop {\rm{E}}\limits_{z' \sim D} [h(z')]\right)}^2}\right)}\leqslant\\ &\quad\quad \dfrac{1}{n} + \dfrac{1}{{{n^2}}}\sum\limits_{i,j \in \{ 1,2, \cdots ,n\} ,i \ne j} {16{\gamma ^2}} \leqslant \dfrac{1}{n} + 16{\gamma ^2} \end{aligned}$$ 最后，
$$\begin{aligned} &\quad\quad\quad\quad\mathop {\rm{E}}\limits_{S \sim {D^n}} \left[{({\hat R_S}[L(S)])^2}\right] =\\ &\mathop {\rm{E}}\limits_{S \sim {D^n}} \left[{(R_S^D[L(S)] + {\hat R_S}[L(S)] - R_S^D[L(S)])^2}\right]\leqslant \\ &\quad\quad\quad\quad \mathop {\rm{2E}}\limits_{S \sim {D^n}} \left[{(R_S^D[L(S)])^2}\right]+ \\ & \quad\quad \mathop {\rm{2E}}\limits_{S \sim {D^n}} \left[{({\hat R_S}[L(S)] - R_S^D[L(S)])^2}\right]\leqslant\\ & \quad\quad 2\left(\frac{1}{n} + 16{\gamma ^2}\right) + 2{(4\gamma )^2} = 64{\gamma ^2} + \frac{2}{n}\end{aligned}$$ 由此，式(1)得证。
定义本体学习算法的LOO估计为
${\hat R_{\rm{LOO}}}[l(A(S))] = $ $ \dfrac{1}{n}\displaystyle \sum\limits_{i = 1}^n {l(A({S^{\backslash i}}),{z_i})}$ 。在监督本体学习下，$ Z = V \times Y $ ，每个本体样本点为$ z = (v,y) $ ，可将LOO估计写成${\hat R_{\rm{LOO}}}[l(A(S))] = \dfrac{1}{n}\displaystyle \sum\limits_{i = 1}^n {l({A_{{S^{\backslash i}}}}({v_i}),{y_i})}$ ，同时期望误差可以写成${R_D}[l(A(S))] = {{\rm{E}}_{(v,y)}}[l({A_S}(v),y)]$ 。监督本体学习算法A关于本体亏损函数l存在LOO一致稳定$ \gamma $ 可以重新写为$\left| {l({A_S}(v),y) - l({A_{{S^{\backslash i}}}}(v),y)} \right| \leqslant \gamma $ ，令${g_i} = {g_i}({z_1}, $ $ {z_2},\cdots ,{z_n}) = {\rm{E}}({{\rm{E}}_{z \sim D}}[l({{\rm{A}}_{{{\rm{S}}^{\backslash {\rm{i}}}}}}({\rm{v}}),{\rm{y}})] - l({{\rm{A}}_{{{\rm{S}}^{\backslash {\rm{i}}}}}}({{\rm{v}}_{\rm{i}}}),{{\rm{y_i}}}))$ 。本文第二个主要结论刻画了关于LOO估计的广义界和
$ \left| {\displaystyle \sum\limits_{i = 1}^n {{g_i}} } \right| $ 之间的差值可以被LOO一致稳定$ \gamma $ 所决定。定理2 设监督本体学习算法A关于本体亏损函数l存在LOO一致稳定
$ \gamma $ ，且本体亏损函数l有界：$ l( \cdot , \cdot ) \leqslant L $ ，有$$ \left| {{R_D}[l(A(S))] - {{\hat R}_{\rm{LOO}}}[l(A(S))] - \left| {\sum\limits_{i = 1}^n {{g_i}} } \right|} \right| \leqslant n\gamma $$ 证明 通过直接计算，可得
$$\begin{aligned} & \quad\quad \left| {n({R_D}[l(A(S))] - {{\hat R}_{\rm{LOO}}}[l(A(S))])} \right| =\\ &\quad\left| {\sum\limits_{i = 1}^n {({{\rm{E}}_{(v,y)}}[l({A_S}(v),y)] - l({A_{{S^{\backslash i}}}}({v_i}),{y_i}))} } \right| \leqslant \\ &n\gamma + \left| {\sum\limits_{i = 1}^n {({{\rm{E}}_{(v,y)}}[l({A_{{S^{\backslash i}}}}(v),y)] - l({A_{{S^{\backslash i}}}}({v_i}),{y_i}))} } \right| \leqslant \\ &\quad\quad\quad\quad\quad\quad n\gamma + \left| {\sum\limits_{i = 1}^n {{g_i}} } \right| \end{aligned}$$ 用类似的方法可以得到：
$$ \left| {n\left({R_D}[l(A(S))] - {{\hat R}_{{\text{LOO}}}}[l(A(S))]\right)} \right| \geqslant \left| {\sum\limits_{i = 1}^n {{g_i}} } \right| - n\gamma $$ 因此，定理2得证。
定理3 设本体数据依赖假设集族
$ F = {({F_S})_{S \in {Z^n}}} $ 的直径和均值直径分别为$\varDelta$ 和$\bar \varDelta$ ，且有LOO一致稳定$ \beta $ ，则F有LOO-CV稳定$\varDelta + \beta$ 和LOO-均值CV稳定$\bar \varDelta + \beta$ 。证明 设
$ S \in {Z^n} $ ，$ z \in S $ 。对任意$ f \in {F_S} $ ，${f'} \in {F_{{S^{\backslash i}}}}$ ，由LOO一致稳定条件，存在$ {f^{''}} \in {F_S} $ 使得$l({f'},z) - $ $ l({f{''}},z) \leqslant \beta$ 。从而$$\begin{aligned} &l({f'},z) - l(f,z) = l({f'},z) - l({f{''}},z) + l({f{''}},z) - l(f,z)\leqslant \\ &\quad\quad\quad\quad\quad \beta + \mathop {\sup }\limits_{f,{f^{''}} \in {F_S}} (l({f^{''}},z) - l(f,z)) \end{aligned}$$ 进而
$$ \mathop {\sup }\limits_{f \in {F_S},{f'} \in {F_{{S^{\backslash i}}}}} (l({f'},z) - l(f,z)) \leqslant \beta + \mathop {\sup }\limits_{f,{f{''}} \in {F_S}} (l({f{''}},z) - l(f,z)) $$ 这说明定理3得证。
设
$ {\wp _S} $ 是与$ {F_S} $ 关联的本体亏损函数族：$$ {\wp _S} = \left\{ z \mapsto l(f,z)|f \in {F_S}\right\} $$ (7) 设
$\varPsi = {({\wp _S})_{S \in {Z^n}}}$ 为$ {\wp _S} $ 的假设集族。为了方便定理4讨论，假设与$ {F_S} $ 关联的本体亏损函数是1-有界的，即对于任意$ f \in {F_S} $ ，任意$ z \sim D $ 有$ 0 \leqslant l(f,z) \leqslant $ $ 1 $ 。定理4是用本体数据依赖假设集族LOO一致稳定和$\varPsi = {({\wp _S})_{S \in {Z^n}}}$ 来刻画拉德马赫复杂度和经验拉德马赫复杂度之间的差值。定理4 设
$ F = {({F_S})_{S \in {Z^n}}} $ 为本体数据依赖假设集族，且存在LOO一致稳定$ \beta $ 。设$\varPsi = {({\wp _S})_{S \in {Z^n}}}$ 如式(7)所定义，则对任意$ \delta > 0 $ ，式(8)在所有本体样本$ S,T \sim {Z^n} $ 中以概率至少$ 1 - \delta $ 成立：$$ \left| {{{\hat \Xi }_{S,T}}(\varPsi ) - {\Xi _n}(\varPsi )} \right| \leqslant \sqrt {\dfrac{{\left({{(1 + 2n\beta )}^2} + 4{n^2}{\beta ^2}\right)\log \dfrac{2}{\delta }}}{{2n}}} $$ (8) 证明 设本体样本T'从T中得到且和T只有一个本体样本点不同，不妨记第k个元素不同，其中
$k \in \{ 1,2, \cdots ,n\}$ 。给定$ \eta > 0 $ ，对于任意拉德马赫向量${\boldsymbol{\sigma}}$ ，根据上确界的定义，存在${f'} \in F_{S,T'}^{\boldsymbol{\sigma}}$ 使得$$ \sum\limits_{i = 1}^n {{{\boldsymbol{\sigma}} _i}l({f'},{\boldsymbol{z}}_i^{T})} \geqslant \mathop {\sup }\limits_{f \in F_{S,{T'}}^{\boldsymbol{\sigma}} } \sum\limits_{i = 1}^n {{{\boldsymbol{\sigma}} _i}l(f,{\boldsymbol{z}}_i^{{T'}})} - \eta $$ 根据
$ F $ 存在LOO一致稳定$ \beta $ 的假设，存在$f \in F_{S,T}^{\boldsymbol{\sigma}}$ ，使得对任意${\boldsymbol{z}} \in Z$ ，有$$\begin{aligned} &\quad\quad\quad\quad\quad \left| {l({f'},{\boldsymbol{z}}) - l(f,{\boldsymbol{z}})} \right| = \\ &\quad \left| {l({f'},{\boldsymbol{z}}) - l({f{''}},{\boldsymbol{z}}) + l({f{''}},{\boldsymbol{z}}) - l(f,{\boldsymbol{z}})} \right|\leqslant\\ & \left| {l({f'},{\boldsymbol{z}}) - l({f{''}},{\boldsymbol{z}})} \right| + \left| {l({f{''}},{\boldsymbol{z}}) - l(f,{\boldsymbol{z}})} \right| \leqslant 2\beta \end{aligned}$$ 其中
$ {f^{''}} $ 来自将${S_{T,{\boldsymbol{\sigma}} }}$ 中第k个元素删除后得到的新本体样本集对应的假设集。从而有$$\begin{aligned} &\mathop {\sup }\limits_{f \in F_{S,{T'}}^{\boldsymbol{\sigma}} } \sum\limits_{i = 1}^n {{{\boldsymbol{\sigma}} _i}l(f,{\boldsymbol{z}}_i^{{T'}})} \leqslant \sum\limits_{i = 1}^n {{\sigma _i}l({f'},{\boldsymbol{z}}_i^{{T'}})} + \eta \leqslant\\ &\quad\quad\quad\quad\sum\limits_{i = 1}^n {({{\boldsymbol{\sigma}} _i}(l(f,{\boldsymbol{z}}_i^{{T'}}) + 2\beta ))} + \eta \end{aligned}$$ 由于
$ \eta > 0 $ 是任意的，得到$$\begin{aligned} &\frac{1}{n}\mathop {\sup }\limits_{f \in F_{S,{T'}}^\sigma } \sum\limits_{i = 1}^n {{{\boldsymbol{\sigma}} _i}l(f,{\boldsymbol{z}}_i^{{T'}})} \leqslant \frac{1}{n}\sum\limits_{i = 1}^n {({\sigma _i}(l(f,{\boldsymbol{z}}_i^{{T'}}) + 2\beta ))} \leqslant\\ &\quad\quad\quad\quad\quad \frac{1}{n}\mathop {\sup }\limits_{f \in F_{S,T}^\sigma } \sum\limits_{i = 1}^n {{\sigma _i}l(f,{\boldsymbol{z}}_i^T)} + 2\beta + \frac{1}{n} \end{aligned}$$ 这意味着，将T替换成
${T'}$ ，对${\hat \Xi _{S,T}}(\varPsi )$ 的影响最多为$2\beta + \dfrac{1}{n}$ 。用相同的方法可以得到，对S改变一个本体样本点对${\hat \Xi _{S,T}}(\varPsi )$ 的影响最多为$ 2\beta $ 。最后，利用McDiarmid不等式[24]得到定理4的结论。定理5用
${\Xi _n}(\varPsi )$ 和$ \bar \chi $ 来刻画本体数据依赖假设集族LOO一致稳定本体学习算法的广义界。定理5 设
$ F = {({F_S})_{S \in {Z^n}}} $ 为本体数据依赖假设集族，存在LOO一致稳定$ \beta $ 和LOO-均值CV稳定$ \bar \chi $ 。设$\varPsi = {({\wp _S})_{S \in {Z^n}}}$ 如式(7)所定义，则对任意$ \delta > 0 $ ，所有$ f \in {F_S} $ ，式(9)在所有本体样本$ S \sim {Z^n} $ 中以概率至少$ 1 - \delta $ 成立：$$\begin{aligned} {R_D}(f) - {\hat R_S}(f)\leqslant {\rm{min}}\{ 2\bar \chi ,2{\Xi _n}(\varPsi )\} + (1 + 4n\beta )\sqrt {\dfrac{{\log \dfrac{1}{\delta }}}{{2n}}} \end{aligned}$$ (9) 这里，
${R_D}(f) = {\rm{E}_{z \sim D}}[l(f,z)]$ ，${\hat R_S}(f) = {\rm{E}_{z \sim S}}[l(f,z)] = $ $ \dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {l(f,{z_i})}$ 。证明 对任意两个本体样本集S和
${S'}$ （只有对应第k个元素不同，分别记为$ z $ 和${z'}$ ，其他均相同），令$$ \Theta (S,{S'}) = \mathop {\rm{sup}}\limits_{f \in {F_S}} [{R_D}(f) - {\hat R_{{S'}}}(f)] $$ 利用简单计算以及本体亏损函数界为1的假设，可以得到：
$$\begin{aligned} &\quad\quad\quad\quad\Theta (S,S) - \Theta ({S'},{S'})= \\ & [\Theta (S,S) - \Theta (S,{S'})] + [\Theta (S,{S'}) - \Theta ({S'},{S'})]\\ &\quad\quad\quad\quad\Theta (S,S) - \Theta (S,{S'})\leqslant \\ & \mathop {\rm{sup}}\limits_{f \in {F_S}} \left[[{R_D}(f) - {\hat R_S}(f)] - [{R_D}(f) - {\hat R_{S'}}(f)]\right]\leqslant\\ & \quad\quad\mathop {\rm{sup}}\limits_{f \in {F_S}} \frac{1}{n}\sum\limits_{i = 1}^n {(l(f,z) - l(f,{z'}))} \leqslant \frac{1}{n} \\ & \Theta (S,{S'}) - \Theta ({S'},{S'}) = \mathop {\rm{sup}}\limits_{f \in {F_S}} [{R_D}(f) - {\hat R_{{S'}}}(f)] - \\ &\quad\quad\quad\quad\mathop {\rm{sup}}\limits_{f \in {F_{{S'}}}} [{R_D}(f) - {\hat R_{{S'}}}(f)]\end{aligned}$$ 根据上确界的定义可知，对任意
$ \eta > 0 $ ，存在$ f \in {F_S} $ ，使得$\mathop {\rm{sup}}\limits_{f \in {F_S}} [{R_D}(f) - {\hat R_{{S'}}}(f)] - \eta \leqslant [{R_D}(f) - {\hat R_{{S'}}}(f)]$ 。由
$ F = {({F_S})_{S \in {Z^n}}} $ 的LOO一致稳定$ \beta $ ，通过类似定理4中的讨论，可知存在${f'} \in {F_{{S'}}}$ 使得对任意z，有$\left| {l({f'},z) - l(f,z)} \right| \leqslant 2\beta$ 。进而$$\begin{aligned} &\quad\quad\quad\quad\quad\quad\Theta (S,{S'}) - \Theta ({S'},{S'})\leqslant\\ & [{R_D}(f) - {\hat R_{{S'}}}(f)] + \eta - \mathop {\rm{sup}}\limits_{f \in {F_{{S'}}}} [{R_D}(f) - {\hat R_{{S'}}}(f)]\leqslant\\ &\quad [{R_D}(f) - {\hat R_{{S'}}}(f)] + \eta - [{R_D}({f'}) - {\hat R_{{S'}}}({f'})]=\\ & [{R_D}(f) - {R_D}({f'})] + \eta + [{\hat R_{{S'}}}({f'}) - {\hat R_{{S'}}}(f)] \leqslant 4\beta + \eta \end{aligned}$$ (10) 由于
$ \eta > 0 $ 是任意的，式(10)意味着$\Theta (S,{S'}) - $ $ \Theta ({S'}, {S'}) \leqslant 4\beta$ 。从而有$\Theta (S,S) - \Theta ({S'},{S'}) \leqslant 4\beta + \dfrac{1}{n}$ 。通过文献[25]中的McDiarmid不等式可知，对任意
$ \delta > 0 $ ，式(11)以概率至少$ 1 - \delta $ 成立。$$ \Theta (S,S) \leqslant \mathop {\rm{E}}\limits_{S \sim {D^n}} [\Theta (S,S)] + (1 + 4n\beta )\sqrt {\dfrac{{\log \dfrac{1}{\delta }}}{{2n}}} $$ (11) 下面计算关于拉德马赫复杂度
${\Xi _n}(\varPsi )$ 和式(11)中$\mathop {\rm{E}}\limits_{S \sim {D^n}} [\Theta (S,S)]$ 项的关系：$$\begin{aligned} &\quad\quad\mathop {\rm{E}}\limits_{S \sim {D^n}} [\Theta (S,S)] = \mathop {\rm{E}}\limits_{S \sim {D^n}} \left[\mathop {\rm{sup}}\limits_{f \in {F_S}} \left[{R_D}(f) - {\hat R_S}(f)\right]\right] =\\ & \quad\quad\quad \mathop {\rm{E}}\limits_{S \sim {D^n}} \left[\mathop {\rm{sup}}\limits_{f \in {F_S}} \left[\mathop {\rm{E}}\limits_{T \sim {D^n}} \left[{\hat R_T}(f)\right] - {\hat R_S}(f)\right]\right] \leqslant\\ & \quad\quad\quad\quad \mathop {\rm{E}}\limits_{S,T \sim {D^n}} \left[\mathop {\rm{sup}}\limits_{f \in {F_S}} \left[{\hat R_T}(f) - {\hat R_S}(f)\right]\right]=\\ & \quad\quad \mathop {\rm{E}}\limits_{S,T \sim {D^n}} \left[\mathop {\rm{sup}}\limits_{f \in {F_S}} \frac{1}{n}\sum\limits_{i = 1}^n \left[l(f,z_i^T) - l(f,z_i^S)\right]\right]=\\ & \quad\quad \mathop {\rm{E}}\limits_{S,T \sim {D^n}} \left[\mathop {\rm{E}}\limits_\sigma \left[\mathop {\rm{sup}}\limits_{f \in F_{S,T}^\sigma } \frac{1}{n}\sum\limits_{i = 1}^n {{\boldsymbol{\sigma}} _i}\left[l(f,z_i^T) - l(f,z_i^S)\right]\right]\right]\leqslant\\ & \mathop {\rm{E}}\limits_{S,T \sim {D^n},\sigma } \left[\mathop {\rm{sup}}\limits_{f \in F_{S,T}^\sigma } \frac{1}{n}\sum\limits_{i = 1}^n {{{\boldsymbol{\sigma}} _i}l(f,z_i^T)} + \mathop {\rm{sup}}\limits_{f \in F_{S,T}^\sigma } \frac{1}{n}\sum\limits_{i = 1}^n { - {{\boldsymbol{\sigma}} _i}l(f,z_i^S)} \right]=\end{aligned}$$ $$\begin{aligned} & \mathop {\rm{E}}\limits_{S,T \sim {D^n},\sigma } \left[\mathop {\rm{sup}}\limits_{f \in F_{S,T}^\sigma } \frac{1}{n}\sum\limits_{i = 1}^n {{{\boldsymbol{\sigma}} _i}l(f,z_i^T)} + \mathop {\rm{sup}}\limits_{f \in F_{S,T}^{ - \sigma }} \frac{1}{n}\sum\limits_{i = 1}^n { - {{\boldsymbol{\sigma}} _i}l(f,z_i^S)} \right] =\\ & \mathop {\rm{E}}\limits_{S,T \sim {D^n},\sigma } \left[\mathop {\rm{sup}}\limits_{f \in F_{S,T}^\sigma } \frac{1}{n}\sum\limits_{i = 1}^n {{{\boldsymbol{\sigma}} _i}l(f,z_i^T)} + \mathop {\rm{sup}}\limits_{f \in F_{S,T}^\sigma } \frac{1}{n}\sum\limits_{i = 1}^n {{{\boldsymbol{\sigma}} _i}l(f,z_i^S)} \right]=\\ & \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 2{\Xi _n}(\Psi ) \end{aligned}$$ 另一方面，固定
$ \eta > 0 $ ，根据上确界的定义，对任意$ S \in {Z^n} $ ，存在$ {f_S} $ 使得$$ \mathop {\rm{sup}}\limits_{f \in {F_S}} [{R_D}(f) - {\hat R_S}(f)] - \eta \leqslant {R_D}({f_S}) - {\hat R_S}({f_S}) $$ 根据
$ {R_D}({f_S}) $ 的定义，有$$\begin{aligned} \mathop {\rm{E}}\limits_{S \sim {D^n}} [{R_D}({f_S})] = \mathop {\rm{E}}\limits_{S \sim {D^n}} [\mathop {\rm{E}}\limits_{z \sim D} [l({f_S},z)]] = \mathop {\rm{E}}\limits_{S \sim {D^n},z \sim D} [l({f_S},z)] \end{aligned}$$ 另外，可知
$$\begin{aligned} \mathop {\rm{E}}\limits_{S \sim {D^n}} [{\hat R_S}({f_S})]= \mathop {\rm{E}}\limits_{S \sim {D^n},z \sim S} [l({f_S},z)] = \mathop {\rm{E}}\limits_{S \sim {D^n},z' \sim D,z \sim S} [l({f_{{S^{z \leftrightarrow z'}}}},z')]\end{aligned}$$ 其中
${S^{z \leftrightarrow {z'}}}$ 表示将本体数据集S中的z和${z'} \sim D$ 相交换，进而有$$\begin{aligned} &\quad\quad\quad\mathop {\rm{E}}\limits_{S \sim {D^n}} [\Theta (S,S)] \leqslant \mathop {\rm{E}}\limits_{S \sim {D^n}} \left[{R_D}({f_S}) - {\hat R_S}({f_S})\right] + \eta= \\ & \quad\quad \mathop {\rm{E}}\limits_{S \sim {D^n},{z'} \sim D} [l({f_S},{z'})] - \mathop {\rm{E}}\limits_{S \sim {D^n},{z'} \sim D,z \sim S} \left[l({f_{{S^{z \leftrightarrow {z'}}}}},{z'})\right] + \eta=\\ & \quad\quad\quad \mathop {\rm{E}}\limits_{S \sim {D^n},{z'} \sim D,z \sim S} \left[l({f_S},{z'}) - l({f_{{S^{z \leftrightarrow {z'}}}}},{z'})\right] + \eta =\\ & \quad\quad\quad \mathop {\rm{E}}\limits_{S \sim {D^n},{z'} \sim D,z \sim S} [l({f_{{S^{z \leftrightarrow {z'}}}}},z) - l({f_S},z)] + \eta= \\ & \mathop {\rm{E}}\limits_{S \sim {D^n},{z'} \sim D,z \sim S} [l({f_{{S^{z \leftrightarrow {z'}}}}},z) - l({f_{{S^{\backslash z}}}},z) + l({f_{{S^{\backslash z}}}},z) - l({f_S},z)] + \eta \leqslant\\ &\quad\quad\quad \mathop {\rm{E}}\limits_{S \sim {D^n},{z'} \sim D,z \sim S} [l({f_{{S^{z \leftrightarrow {z'}}}}},z) - l({f_{{S^{\backslash z}}}},z)] + \\ & \quad\quad \mathop {\rm{E}}\limits_{S \sim {D^n},{z'} \sim D,z \sim S} [l({f_{{S^{\backslash z}}}},z) - l({f_S},z)] + \eta \leqslant 2\bar \chi + \eta \end{aligned}$$ (12) 其中，
$ {S^{\backslash z}} $ 表示在本体数据集S中删除元素z得到的集合。由于式(12)对所有$ \eta > 0 $ 成立，从而有$\mathop {\rm{E}}\limits_{S \sim {D^n}} [\Theta (S,S)] \leqslant 2\bar \chi$ 。结合
$\mathop {\rm{E}}\limits_{S \sim {D^n}} [\Theta (S,S)] \leqslant 2\bar \chi ,$ $\mathop {\rm{E}}\limits_{S \sim {D^n}} [\Theta (S,S)] \leqslant 2{\Xi _n}(\varPsi )$ 和式(11)，可知定理5成立。沿用定理1中的标记，
${S} \in {Z^{m \times n}}$ 为多重本体数据集，它由m个本体数据集${{S}_1}, {{S}_2},\cdots ,{{S}_m}$ 构成，每个数据集的容量均为n。第$ l $ 个本体子数据集的第$ i $ 个元素记为${{S}_{l,i}}$ ，其中$l \in \{ 1,2, \cdots ,m\}$ 。定理6刻画了多重本体数据集框架下LOO- CV稳定$ \chi $ 的作用。定理6 设
$ F = {({F_S})_{S \in {Z^n}}} $ 为本体数据依赖假设集族，存在LOO- CV稳定$ \chi $ ，则$$ {\displaystyle \sum _{l=1}^{m}\underset{{S}\sim {D}^{mn},{z'}\sim D,z\sim {{S}}_{l}}{\rm{E}}}\left[{P}\left[A({S})=l\right]\left[l({f}_{{{S}}_{l}^{z\leftrightarrow {z'}}},z)-l({f}_{{{S}}_{l}},z)\right]\right] \leqslant 2\chi , $$ 其中
${{S}}_l^{z \leftrightarrow {z'}}$ 将本体数据集${{S}_l}$ 中的z和${z'} \sim D$ 相交换。证明 通过推导可知
$$\begin{aligned}&\quad\quad {\displaystyle \sum _{l=1}^{m}\underset{{S}\sim {D}^{mn},{z'}\sim D,z\sim {{S}}_{l}}{\rm{E}}\left[{P}[A({S})=l]\left[l({f}_{{{S}}_{l}^{z\leftrightarrow {z'}}},z)-l({f}_{{{S}}_{l}},z)\right]\right]} \leqslant\\[-2pt] &\quad\quad\quad\quad\quad\quad\displaystyle \sum _{l=1}^{m}\underset{{S}\sim {D}^{mn},{z'}\sim D,z\sim {{S}}_{l}}{\rm{E}}\Bigg[{P}\left[A({S})=l\right] \times\end{aligned}$$ $$\begin{aligned} &\quad\quad\quad\quad\quad\quad\mathop {\sup }\limits_{f \in {F_{{{S}_l}}},{f'} \in {F_{{S}_l^{z \leftrightarrow {z'}}}}} \left[l({f'},z) - l(f,z)\right]\Bigg]\leqslant\\[-2pt] &\quad\quad\quad\quad\quad\quad\quad\quad {\displaystyle \sum _{l=1}^{m}\underset{{S}\sim {D}^{mn}}{\rm{E}}\Bigg[{P}\left[A({S})=l\right]}\times\\[-2pt] & \quad\quad\quad\quad \mathop {\rm{E}}\limits_{{z'} \sim D,z \sim {{S}_l}} \Bigg[\mathop {\sup }\limits_{f \in {F_{{{S}_l}}},{f'} \in {F_{{S}_l^{z \leftrightarrow {z'}}}}} \left[l({f'},z) - l(f,z)\right]|{S}\Bigg]\leqslant\\[-2pt] & \quad\quad\quad\quad\quad\quad\quad\quad\quad \displaystyle \sum _{l=1}^{m}\underset{{S}\sim {D}^{mn}}{\rm{E}}\left[{P}[A({S})=l]\right]\times\\[-2pt] &\quad\quad\quad\quad\underset{{z}'\sim D,z\sim {{S}}_{l}}{\rm{E}}\Bigg[\underset{f\in {F}_{{{S}}_{l}},{f}'\in {F}_{{{S}}_{l}^{z\leftrightarrow {z}'}},{f}''\in {F}_{{{S}}_{l}^{\backslash z}}}{\mathrm{sup}} \big[ \left[l({f'},z) - l({f''},z) + \right.\\[-2pt] &\quad\quad\quad\quad\quad\quad\quad\quad\left.l({f''},z) - l(f,z)\right]|{S}\big]\Bigg]\leqslant\\[-2pt] & \quad\quad\quad\quad\quad\quad\quad\quad{\displaystyle \sum _{l=1}^{m}\underset{{{S}}\sim {D}^{mn}}{\rm{E}}\Bigg[{{P}}\left[A({{S}})=l\right]} \times \\[-2pt] & \quad\quad\quad\mathop {\rm{E}}\limits_{{z'} \sim D,z \sim {{S}_l}}\Bigg[\mathop {\sup }\limits_{{f'} \in {F_{{S}_l^{z \leftrightarrow {z'}}}},{f{''}} \in {F_{{S}_l^{\backslash z}}}} \left[l({f'},z) - l({f{''}},z)\right]|{S}\Bigg]\Bigg]\leqslant\\[-2pt] & \quad\quad\quad\quad\quad\quad\quad {\displaystyle \sum _{l=1}^{m}\underset{{S}\sim {D}^{mn}}{\rm{E}}\Bigg[{P}[A({S})=l]} \times \\[-2pt] &\quad\quad\quad \mathop {\rm{E}}\limits_{{z'} \sim D,z \sim {{S}_l}}\Bigg[\mathop {\sup }\limits_{{f'} \in {F_{{S}_l^{z \leftrightarrow {z'}}}},{f{''}} \in {F_{{S}_l^{\backslash z}}}} \left[l({f'},z) - l({f{''}},z)\right]|{S}\Bigg]\Bigg]+\\[-2pt] & \quad\quad\quad\quad\quad\quad\quad {\displaystyle \sum _{l=1}^{m}\underset{{S}\sim {D}^{mn}}{\rm{E}}\Bigg[{P}[A({S})=l]} \times \\[-2pt] &\quad\quad\quad\mathop {\rm{E}}\limits_{{z'} \sim D,z \sim {{S}_l}}\Bigg[\mathop {\sup }\limits_{f \in {F_{{{S}_l}}},{f''} \in {F_{{S}_l^{\backslash z}}}} [l({f''},z) - l(f,z)]|{S}\Bigg]\Bigg]\leqslant\\[-2pt] &\quad\quad\quad\quad\quad\quad 2{\displaystyle \sum _{l=1}^{m}\underset{{S}\sim {D}^{mn}}{\rm{E}}\left[{P}[A({S})=l]\chi \right]} =\\[-2pt] &\quad\quad\quad\quad\quad2\underset{{S}\sim {D}^{mn}}{\rm{E}}\left[{\displaystyle \sum _{l=1}^{m}{P}\left[A({S})=l\right]}\right]\chi = 2\chi \end{aligned}$$ 其中
${S}_l^{\backslash z}$ 表示在本体数据集${{S}_l}$ 中删除元素z得到的集合。利用定理1中的本体多重集方法，结合定理5和定理6，可得关于用
${\Xi _n}(\varPsi )$ 和$ \chi $ 来刻画本体数据依赖假设集族LOO一致稳定本体学习算法的广义界。定理7 设
$ F = {({F_S})_{S \in {Z^n}}} $ 为本体数据依赖假设集族，存在LOO一致稳定$ \beta $ 和LOO-CV稳定$ \chi $ 。设$\varPsi = {({\wp _S})_{S \in {Z^n}}}$ 如式(7)所定义，则对任意$ \delta \in (0,1) $ ，所有$ f \in {F_S} $ ，式(13)在所有本体样本$ S \sim {Z^n} $ 中以概率至少$ 1 - \delta $ 成立：$R_{D}(f)-\hat{R}_{S}(f) \leqslant \\ \min \left\{2 \Xi_{n}(\Psi)+(1+4 n \beta) \sqrt{\frac{\log \frac{2}{\delta}}{2 n}}\right.\\ 2 \chi \sqrt{e}+4 \sqrt{\left.\left(4 \beta+\frac{1}{n}\right) \log \frac{6}{\delta}\right\}}$ (13) 由于证明方法与之前定理类似，我们不再给出具体证明。同时，通过替换证明过程中的一些技巧，可以得到定理7的另外一个版本如定理8。
定理8 设
$ F = {({F_S})_{S \in {Z^n}}} $ 为本体数据依赖假设集族，存在LOO一致稳定$ \beta $ 和LOO-CV稳定$ \chi $ 。设$\varPsi = {({\wp _S})_{S \in {Z^n}}}$ 如式(7)所定义，则对任意$ \delta \in (0,1) $ ，所有$ f \in {F_S} $ ，式(14)在所有本体样本$ S \sim {Z^n} $ 中以概率至少$ 1 - \delta $ 成立：$R_{D}(f)-\hat{R}_{S}(f) \leqslant \\ \min \left\{2 \Xi_{n}(\Psi)+8(1+4 n \beta) \sqrt{\frac{\log \frac{3}{\delta}}{n}}\right. \\ 2 \chi \sqrt{e}+4 \sqrt{\left.\left(4 \beta+\frac{1}{n}\right) \log \frac{3}{\delta}\right\}}$ (14) 3. 结束语
本文主要从删除一个本体样本的设定出发，讨论具有LOO一致稳定性的本体学习算法的广义界的统计学特征。主要从两个角度来讨论：
1）本体学习算法关于本体亏损函数具有LOO一致稳定性；
2）本体函数假设空间稳定，即本体数据依赖假设集族
$ F = {({F_S})_{S \in {Z^n}}} $ 存在LOO一致稳定$ \beta $ 。利用统计学习理论的方法，分别给出了两种假设框架下，本体学习算法的学习率的上界。得到的理论结果表明，在算法一致稳定和假设空间一致稳定的理论假设下，本体学习算法的误差界的上界可以被稳定性参数很好地控制，进而保证了本体算法的收敛性。鉴于各种形式的本体学习算法已被广泛应用于基因学、营养学、化学、地理信息系统等领域，本文得到的理论结果对本体学习算法的各类实际应用有着潜在的指导意义和参考价值。关于稳定性在具体某个本体学习算法中的表现，在未来的本体算法执行中有待进一步实验验证。
-
[1] SKALLE P, AAMODT A. Petrol 18 946: downhole failures revealed through ontology engineering[J]. Journal of petroleum science and engineering, 2020, 191: 107188. doi: 10.1016/j.petrol.2020.107188 [2] SOBRAL T, GALVÃO T, BORGES J. An ontology-based approach to knowledge-assisted integration and visualization of urban mobility data[J]. Expert systems with applications, 2020, 150: 113260. doi: 10.1016/j.eswa.2020.113260 [3] 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. doi: 10.1016/j.jpdc.2020.03.019 [4] TEBES G, PEPPINO D, BECKER P, et al. Analyzing and documenting the systematic review results of software testing ontologies[J]. Information and software technology, 2020, 123: 106298. doi: 10.1016/j.infsof.2020.106298 [5] 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. doi: 10.1016/j.future.2020.03.010 [6] 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. doi: 10.1007/s11277-020-07105-8 [7] 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. doi: 10.1007/s10278-019-00303-2 [8] MANTOVANI A, PIANA F, LOMBARDO V. Ontology-driven representation of knowledge for geological maps[J] Computers and geosciences, 2020, 139: 104446. [9] 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. doi: 10.1093/bioinformatics/btaa106 [10] KOSSMANN M, SAMHAN A, ODEH M, et al. Extending the scope of configuration management for the development and life cycle support of systems of systems-an ontology-driven framework applied to the enceladus submarine exploration lander[J]. Systems engineering, 2020, 23(3): 366–391. doi: 10.1002/sys.21532 [11] ZHU Linli, HUA Gang, ASLAM A. Ontology learning algorithm using weak functions[J]. Open physics, 2018, 16(1): 910–916. doi: 10.1515/phys-2018-0112 [12] 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. [13] 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. [14] GAO Wei, GUIRAO J L G, BASAVANAGOUD B, et al. Partial multi-dividing ontology learning algorithm[J]. Information sciences, 2018, 467: 35–58. doi: 10.1016/j.ins.2018.07.049 [15] 朱林立, 华钢, 高炜. 决定图框架下本体学习算法的稳定性分析[J]. 计算机科学, 2020, 47(5): 43–50. doi: 10.11896/jsjkx.200100129 ZHU Linli, HUA Gang, GAO Wei. Stability analysis of ontology learning algorithm in decision graph setting[J]. Computer science, 2020, 47(5): 43–50. doi: 10.11896/jsjkx.200100129 [16] 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. [17] ZHU Linli, YU Pan, JAMIL M K, et al. Boosting based ontology sparse vector computation approach[J]. Engineering letters, 2017, 25(4): 406–415. [18] 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. [19] 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. [20] GAO Wei, XU Tianwei. Stability analysis of learning algorithms for ontology similarity computation[J]. Abstract and applied analysis, 2013, 2013: 174802. doi: 10.1155/2013/174802 [21] 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. [22] 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. [23] STEINKE T, ULLMAN J. Subgaussian tail bounds via stability arguments[EB/OL](2017−04−21)[2021−01−09]https://arxiv.org/abs/1701.03493v2. [24] 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. [25] 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. doi: 10.1137/130933125
