多重分割框架下的两类新本体学习算法*

朱林立

(江苏理工学院 计算机工程学院，江苏 常州 213001)

多重分割本体学习算法就是利用本体图的特征，将所有本体顶点划分成k个类.对于树形结构的本体图，根顶点之下的每个分支对应一个类.由领域专家指定各个类别之间的次序关系，规定a类的本体顶点在本体函数f作用下的值要大于b类本体顶点在本体函数f作用下的值，其中1≤a

本文的目的是在多重分割框架下给出两类新本体学习算法，并从统计学习理论的角度对算法进行分析.首先对一些需要的标记和符号进行介绍；其次，给出两类多重分割框架下的新本体学习算法；最后分别对新算法A进行理论分析，从统计学习理论的角度得到误差界的一个结果.其主要的技术是运用覆盖数逼近的证明技巧.

1 符号和标记

设本体数据(v,y)服从未知分布D，本体函数f:V→将每个本体图上的顶点映射到实数.将本体顶点v的所有信息缝装在一个p维向量内(因此本体函数又可以理解为降维函数f:p→)，v同时表示本体顶点、该顶点对应的本体概念和该顶点对应的向量，需要根据上下文的意思来确定v表示的含义.设f(v)=wTv,其中w称为参数向量，在本体学习框架下就称为本体向量.设所有的本体顶点分成1,2,…,k个类别(其中k≥2)，设va和vb分别属于a和b类的本体顶点，其中1≤af(vb).

记

根据定义，ΞS的值是实数，而ΥS是向量，其维度和每个本体顶点对应向量的维度一致.若固定分类对(a,b),可记

假设输入域是紧的，V⊆B2(V*)表示‖v‖2≤V*,且假设本体函数的定义域也是紧的，取W⊆B2(V*)满足‖w‖2≤W*.这里Bp(r)={v∈V:‖v‖p≤r}表示半径为r的lp球，W*也称为正则化参数.

2 两类新本体算法描述

设wS和wSS分别为本体学习算法A和本体学习算法B中最小化本体经验误差得到的最优本体向量.我们总是关注Ξ,ΞS,ΞSS≻0的情况，其中

这保证了wS有唯一的值.两个主要多重分割框架下的本体学习算法的伪代码描述如下.

2.1 本体学习算法A

输入：多重分割框架下的本体学习样本S=(S1,S2,…,Sk)和正则化参数W*；

初始化：ΞS←0,ΥS←(0,0,…,0)；

累加操作：

Fora=1,…,k-1

Forb=a+1,…,k

Fori=1,…,na

Forj=1,…,nb

End For

End For

End For

End For

执行本体经验误差的最小化：

输出：本体权值向量wS.

对所有的(a,b)对进行类似的操作，最终得到新样本本体记为SS.对于该新样本而言，每一对(a,b)都有固定的比较对.对应的本体经验误差表示为

其中ΞSS和ΥSS分别是在对应子本体样本集SS上进行比较求和得到的.

2.2 本体学习算法B

累加操作：

Fora=1,…,k-1

Forb=a+1,…,k

Fors=1,…,na,b

End For

End For

End For

执行本体经验误差的最小化：

输出：本体权值向量wSS.

3 多重分割本体算法A理论分析

对于量度空间M及ε>0,覆盖数C(M,ε)定义为并集可以覆盖量度空间M的半径为ε的球的最小数量.特别假设C(M,ε)为p维单位球的半径为ε的l2球的覆盖数，即量度空间M取p维单位球.本文的主要结论利用W的量度熵来描述多重分割本体学习算法A的误差界.

证明设hw(va,vb)=wT(va-vb),则本体成对平方亏损函数可以表示为

设ΦS(w)=R(w)-RS(w).对任意w1,w2∈W,有

因此，可知

|ΦS(w1)-ΦS(w2)|=|R(w1)-RS(w1)-R(w2)+RS(w2)|≤

下面对于固定的w,计算ΦS(w)的偏差.首先根据R(w)和RS(w)的定义可以直接得到E[ΦS(w)]=0.其次利用上一节中替换一个本体样本的方法，定义S′是从S=(S1,S2,…,Sk)中替换某一个样本得到的.定义

Ra,b(w)=Eva～Da,vb～Db[lφ(w,va-vb)]

进而有

对于所有的比较对每一对(a,b),其中1≤a

情况1：替换的样本点属于Sb,那么

情况2：替换的样本点属于Sa,那么类似地，有

从而有

由于本体样本服从独立分布，利用McDiarmid不等式可得

(1)

最后，根据wS和w*的定义，得到R(wS)-R(w*)≤0.且根据三角不等式和RS(wS)-RS(w*)≤0,有

R(wS)-R(w*)=[R(wS)-RS(wS)+RS(w*)-R(w*)]+[RS(wS)-RS(w*)]≤

|R(wS)-RS(wS)|+|R(w*)-RS(w*)|

综上所述，定理1成立.