朱林立

(江蘇理工學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 常州 213001)

多重分割本體學(xué)習(xí)算法就是利用本體圖的特征，將所有本體頂點(diǎn)劃分成k個(gè)類.對(duì)于樹形結(jié)構(gòu)的本體圖，根頂點(diǎn)之下的每個(gè)分支對(duì)應(yīng)一個(gè)類.由領(lǐng)域?qū)＜抑付ǜ鱾€(gè)類別之間的次序關(guān)系，規(guī)定a類的本體頂點(diǎn)在本體函數(shù)f作用下的值要大于b類本體頂點(diǎn)在本體函數(shù)f作用下的值，其中1≤a

本文的目的是在多重分割框架下給出兩類新本體學(xué)習(xí)算法，并從統(tǒng)計(jì)學(xué)習(xí)理論的角度對(duì)算法進(jìn)行分析.首先對(duì)一些需要的標(biāo)記和符號(hào)進(jìn)行介紹；其次，給出兩類多重分割框架下的新本體學(xué)習(xí)算法；最后分別對(duì)新算法A進(jìn)行理論分析，從統(tǒng)計(jì)學(xué)習(xí)理論的角度得到誤差界的一個(gè)結(jié)果.其主要的技術(shù)是運(yùn)用覆蓋數(shù)逼近的證明技巧.

1 符號(hào)和標(biāo)記

設(shè)本體數(shù)據(jù)(v,y)服從未知分布D，本體函數(shù)f:V→將每個(gè)本體圖上的頂點(diǎn)映射到實(shí)數(shù).將本體頂點(diǎn)v的所有信息縫裝在一個(gè)p維向量內(nèi)(因此本體函數(shù)又可以理解為降維函數(shù)f:p→)，v同時(shí)表示本體頂點(diǎn)、該頂點(diǎn)對(duì)應(yīng)的本體概念和該頂點(diǎn)對(duì)應(yīng)的向量，需要根據(jù)上下文的意思來確定v表示的含義.設(shè)f(v)=wTv,其中w稱為參數(shù)向量，在本體學(xué)習(xí)框架下就稱為本體向量.設(shè)所有的本體頂點(diǎn)分成1,2,…,k個(gè)類別(其中k≥2)，設(shè)va和vb分別屬于a和b類的本體頂點(diǎn)，其中1≤af(vb).

記

根據(jù)定義，ΞS的值是實(shí)數(shù)，而ΥS是向量，其維度和每個(gè)本體頂點(diǎn)對(duì)應(yīng)向量的維度一致.若固定分類對(duì)(a,b),可記

假設(shè)輸入域是緊的，V?B2(V*)表示‖v‖2≤V*,且假設(shè)本體函數(shù)的定義域也是緊的，取W?B2(V*)滿足‖w‖2≤W*.這里Bp(r)={v∈V:‖v‖p≤r}表示半徑為r的lp球，W*也稱為正則化參數(shù).

2 兩類新本體算法描述

設(shè)wS和wSS分別為本體學(xué)習(xí)算法A和本體學(xué)習(xí)算法B中最小化本體經(jīng)驗(yàn)誤差得到的最優(yōu)本體向量.我們總是關(guān)注Ξ,ΞS,ΞSS?0的情況，其中

這保證了wS有唯一的值.兩個(gè)主要多重分割框架下的本體學(xué)習(xí)算法的偽代碼描述如下.

2.1 本體學(xué)習(xí)算法A

輸入：多重分割框架下的本體學(xué)習(xí)樣本S=(S1,S2,…,Sk)和正則化參數(shù)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

執(zhí)行本體經(jīng)驗(yàn)誤差的最小化：

輸出：本體權(quán)值向量wS.

對(duì)所有的(a,b)對(duì)進(jìn)行類似的操作，最終得到新樣本本體記為SS.對(duì)于該新樣本而言，每一對(duì)(a,b)都有固定的比較對(duì).對(duì)應(yīng)的本體經(jīng)驗(yàn)誤差表示為

其中ΞSS和ΥSS分別是在對(duì)應(yīng)子本體樣本集SS上進(jìn)行比較求和得到的.

2.2 本體學(xué)習(xí)算法B

累加操作：

Fora=1,…,k-1

Forb=a+1,…,k

Fors=1,…,na,b

End For

End For

End For

執(zhí)行本體經(jīng)驗(yàn)誤差的最小化：

輸出：本體權(quán)值向量wSS.

3 多重分割本體算法A理論分析

對(duì)于量度空間M及ε>0,覆蓋數(shù)C(M,ε)定義為并集可以覆蓋量度空間M的半徑為ε的球的最小數(shù)量.特別假設(shè)C(M,ε)為p維單位球的半徑為ε的l2球的覆蓋數(shù)，即量度空間M取p維單位球.本文的主要結(jié)論利用W的量度熵來描述多重分割本體學(xué)習(xí)算法A的誤差界.

證明設(shè)hw(va,vb)=wT(va-vb),則本體成對(duì)平方虧損函數(shù)可以表示為

設(shè)ΦS(w)=R(w)-RS(w).對(duì)任意w1,w2∈W,有

因此，可知

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

下面對(duì)于固定的w,計(jì)算ΦS(w)的偏差.首先根據(jù)R(w)和RS(w)的定義可以直接得到E[ΦS(w)]=0.其次利用上一節(jié)中替換一個(gè)本體樣本的方法，定義S′是從S=(S1,S2,…,Sk)中替換某一個(gè)樣本得到的.定義

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

進(jìn)而有

對(duì)于所有的比較對(duì)每一對(duì)(a,b),其中1≤a

情況1：替換的樣本點(diǎn)屬于Sb,那么

情況2：替換的樣本點(diǎn)屬于Sa,那么類似地，有

從而有

由于本體樣本服從獨(dú)立分布，利用McDiarmid不等式可得

(1)

最后，根據(jù)wS和w*的定義，得到R(wS)-R(w*)≤0.且根據(jù)三角不等式和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成立.