多重分割框架下的兩類新本體學習算法*

朱林立

(江蘇理工學院 計算機工程學院，江蘇 常州 213001)

多重分割本體學習算法就是利用本體圖的特征，將所有本體頂點劃分成k個類.對于樹形結構的本體圖，根頂點之下的每個分支對應一個類.由領域專家指定各個類別之間的次序關系，規(guī)定a類的本體頂點在本體函數(shù)f作用下的值要大于b類本體頂點在本體函數(shù)f作用下的值，其中1≤a

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

1 符號和標記

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

記

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

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

2 兩類新本體算法描述

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

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

2.1 本體學習算法A

輸入：多重分割框架下的本體學習樣本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)驗誤差的最小化：

輸出：本體權值向量wS.

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

其中ΞSS和ΥSS分別是在對應子本體樣本集SS上進行比較求和得到的.

2.2 本體學習算法B

累加操作：

Fora=1,…,k-1

Forb=a+1,…,k

Fors=1,…,na,b

End For

End For

End For

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

輸出：本體權值向量wSS.

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

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

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

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

因此，可知

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

下面對于固定的w,計算ΦS(w)的偏差.首先根據(jù)R(w)和RS(w)的定義可以直接得到E[ΦS(w)]=0.其次利用上一節(jié)中替換一個本體樣本的方法，定義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)

最后，根據(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成立.