本体学习算法的RO稳定性

云南师范大学学报(自然科学版)2018年9月38卷5期(Vol.38No.5)JournalofYunnanNormalUniversityDOI:10.7699/j.ynnu.ns-2018-061本体学习算法的RO稳定性*彭波,高炜(云南师范大学信息学院,云南昆明650500)摘要:主要研究了本体学习算法在替换一个样本点(RO)情况下的稳定性.定义多个本体学习算法的稳定性相关概念并得到它们之间的相互关系.另外结果还显示RO稳定性是本体学习算法的充分必要条件.关键词:本体;相似度计算;学习算法;本体亏损函数;稳定性中图分类号:TP393.092文献标志码:A文章编号:1007-9793(2018)05-0032-071引言作为一种结构化概念存储和表示模型,在实际工程应用中,本体模型一般用图G=(V,E)来表示.其中图中每个顶点对应一个本体概念,每条边对应上层概念和下层概念之间的从属关系.本体学习算法的核心问题是根据本体图结构得到相似度计算函数Sim,从而将本体图中每一对顶点映射成正实数,该实数的大小表示两概念之间的相似度.相关研究可参考文献[1-12].有一类学习框架是通过本体函数f:V→R将本体图中每个顶点映射成实数,两个顶点对应概念之间的相似度则通过他们对应实数之间的差值进行判断,差值越小,则相似度越大.一个好的本体学习算法需要具备一定的稳定性,即在替换少量本体样本点的情况下得到的本体函数不会出现较大变化.本文的目的是对此类框架下的本体学习算法进行稳定性研究.即在替换一个本体样本(replaceonesample,简称RO)后,分析算法的特征,结果表明RO稳定性是本体学习算法的充分必要条件.2符号、定义和本体算法框架设V是欧几里得空间中的紧子集,Y是标记集合.设μ(v,y)为Z=V×Y上的未知概率分布,S={(v1,y1),…,(vn,yn)}=(vi,yi)ni=1=(zi)ni=1是由n个元素构成的本体样本集合i.i.d.服从Zn上的概率分布.本体学习的目标是使用本体样本数据S预测本体函数fS:V→R.设L:RV×V×R→R为本体亏损函数,Lf,z()是固定本体函数f在本体数据点z=(v,y)上的惩罚量.本文仅考虑L是平方亏损,即Lf,z()=fv()-y()2且存在M,对任意f∈F(这里F是假设空间)和z∈Z,满足0≤Lf,z()≤M.设lz()=Lf,z().从而lz():V×Y→R,且设F=lf():f∈F{}为本体亏损函数空间.*收稿日期:2018-03-10基金项目:国家自然科学基金资助项目(11761083)作者简介:彭波(1972-),男,云南昆明人,硕士,助理研究员,主要从事机器学习方面研究.通信作者:高炜.E-mail:13529457727@163.com.对于固定本体函数f,本体亏损函数L和概率分布μ,本体算法的期望误差为Rf()=EzLf,z().当L是平方亏损时,有R(f)=EZL(f,z)=∫V,Y(f(v)-y)2dμ(v,y)=Eμ|f(v)-y|2但是由于μ未知,Rf()无法直接计算.在工程中,一般用如下本体经验误差来代替期望误差R∧S(f)=1n∑ni=1L(f,zi).此外,在平方亏损函数框架下,有R∧S(f)=1n∑ni=1(f(vi)-yi)2=Eμn(f(v)-y)2以下设Si为从S中将第i个元素vi替换为v'i,得到的本体训练样本集(1≤i≤n).本体函数fS和fSi分别为最小化R∧S(f)和R∧Si(f)后得到的最优本体函数.本体学习算法称为对称的,如果将本体样本集中的元素重新排列而不影响学习结果.给定本体样本集合S和本体函数空间F,几乎处处本体学习算法是指对任意εE>0,存在本体函数fεES满足R∧S(fεES)≤inff∈R∧S(f)+εE(1)本体学习映射称为(广义,弱)一致的,如果对任意εc>0,有limn→¥supμP{R(fS)>inff∈R(f)+εc}=0广义一致是指上述不等式对Z上的任意测度都成立,弱一致是指只按概率收敛,而强一致是指几乎处处收敛.设F是任意函数类.说F是(弱)uGC(uniformGlivenko-Cantelli)类,若对任意正数ε,有limn→¥supμP{supf∈F|Eμnf-Eμf|>ε}=0对于本体亏损函数l来说,上述定义意味着对所有分布μ,存在εn和δεn,n使得limn→¥εn=0,limn→¥δn=0且P{supf∈F|R(f)-R∧S(f)|>εn}≤δεn,n.对任意函数空间F,称其为强uGC类,如果对任意正数ε,有limn→¥supμP{supm≥nsupf∈|Eμmf-Eμf|>ε}=0对有界本体亏损函数集合来说,弱uGC类等价于强uGC类,且弱一致等价于强一致.本体学习算法的RO一致稳定性是指对任意S∈Zn