本體學(xué)習(xí)算法的兩類LOO 一致穩(wěn)定性和廣義界

朱林立，華鋼，高煒

（1.中國礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州 221116;2.江蘇理工學(xué)院 計算機工程學(xué)院，江蘇 常州 213001;3.云南師范大學(xué) 信息學(xué)院，云南 昆明 650500）

本體的概念首先屬于西方哲學(xué)的范疇，是指客觀存在在邏輯層面上的表達和概括。作為形而上學(xué)的一個分支，本體論在哲學(xué)領(lǐng)域的主要研究問題是“是否存在非物質(zhì)事物”。20 世紀(jì)80 年代引入到人工智能領(lǐng)域，之后對本體有自己的定義。近年來，本體作為概念語義表示的工具，與其他數(shù)據(jù)庫相比，有著結(jié)構(gòu)化存儲、易于在不同本體之間建立映射和本體對齊等優(yōu)勢，因而被廣泛應(yīng)用于各個學(xué)科，在生物、化學(xué)、醫(yī)學(xué)、材料、能源等領(lǐng)域都能看到本體在特定的場景下發(fā)揮作用。

Skalle 等[1]闡述了如何使用知識建模和本體工程方法開發(fā)模型，并利用本體模型來預(yù)測鉆井過程中的井下故障。Sobral 等[2]提出了一個基于本體的框架來支持來自智能交通系統(tǒng)的數(shù)據(jù)的集成和可視化。Al-Sayed 等[3]設(shè)計了一種稱為 Cloud-FNF 的綜合云本體，根據(jù)該本體結(jié)構(gòu)，云服務(wù)被分類為若干個類別。Tebes 等[4]給出分析和記錄軟件測試本體的系統(tǒng)審查結(jié)果的方法。Pradeep等[5]在基于本體的平衡二叉樹中搜索預(yù)定的用戶查詢，最后使用 Okapi BM25 對相關(guān)結(jié)果進行排序并交付給用戶。Hema 等[6]提出了一種新的基于信任的隱私保護框架，通過本體服務(wù)排序TBPFOSR 進行用戶身份驗證。Messaoudi 等[7]給出了關(guān)于疾病治療醫(yī)學(xué)本體研究的綜述。Mantovani等[8]提出了一種本體驅(qū)動的地質(zhì)圖知識表示。本體形式語言允許通過語義類別和屬性對地球科學(xué)家的解釋進行機器可讀編碼，并支持知識共享和互操作性。Abeysinghe 等[9]通過在基因本體(gene ontology,GO)本體概念的基于序列的表示之上，利用新的術(shù)語代數(shù)以及3 個條件規(guī)則（單調(diào)性、交集和子概念規(guī)則）開發(fā)了基于包含的子項推理框架。Kossmann 等[10]提出了潛艇探測著陸器的本體驅(qū)動框架。

隨著越來越多的本體被定義和應(yīng)用，以及越來越多的本體算法被設(shè)計并嘗試用于不同的本體工程應(yīng)用領(lǐng)域，學(xué)習(xí)算法也被逐漸應(yīng)用于本體。本體學(xué)習(xí)算法就是將機器學(xué)習(xí)方法與本體自身結(jié)構(gòu)相融合，通過本體樣本的學(xué)習(xí)得到本體函數(shù)。具體地說，本體用圖結(jié)構(gòu)表示，設(shè)G=(V,E)為本體圖對應(yīng)某個本體O，其頂點對應(yīng)O中概念，頂點之間的邊對應(yīng)兩個頂點某種直接聯(lián)系。本體可以用有向圖來表示，其中邊的權(quán)值由邊的類型等因素決定。本體學(xué)習(xí)算法可以看成圖算法，通過本體樣本S按照一定的學(xué)習(xí)規(guī)則學(xué)習(xí)得到本體函數(shù)f:V→R。該本體函數(shù)的作用是將整個本體圖映射到一維實數(shù)軸，每個本體頂點（對應(yīng)本體概念）映射為一維實數(shù)。在最開始的本體數(shù)值化表示中，往往要求每個本體頂點都用一個p維向量來表示，因此本體學(xué)習(xí)算法本質(zhì)上就變成一種降維算法，目標(biāo)是得到本體函數(shù)f:Rp→R。相關(guān)本體學(xué)習(xí)這方面的研究可參考文獻[11-19]。

穩(wěn)定性是一個本體學(xué)習(xí)算法在具體工程應(yīng)用領(lǐng)域可以使用的基本條件，它要求算法在學(xué)習(xí)樣本集發(fā)生輕微改變時輸出結(jié)果不會發(fā)生本質(zhì)性的改變。常見的變換有：刪除一個樣本(leave one out,LOO)，刪除兩個樣本(leave two out,LTO)，替換一個樣本(place one,PO)。只有滿足穩(wěn)定性的本體學(xué)習(xí)算法才具備泛化性，才有可能對同類數(shù)據(jù)發(fā)揮作用。已有部分文獻對本體算法的穩(wěn)定性進行了討論，可參考文獻[15，20-21]。

具體地說，通常把本體數(shù)據(jù)分成兩類：訓(xùn)練集（樣本集）和測試集。通過本體樣本的訓(xùn)練，按照一定的本體學(xué)習(xí)算法得到本體函數(shù)，再將本體函數(shù)應(yīng)用于同類本體數(shù)據(jù)（測試集）。我們希望從樣本學(xué)習(xí)得到的本體函數(shù)同樣適用于同一個本體的其他本體數(shù)據(jù)，即算法具有很好的擴展性能。這必須要求本體學(xué)習(xí)算法具有穩(wěn)定性，即樣本的輕微改變對學(xué)習(xí)得到的結(jié)果影響很小。從理論上說，穩(wěn)定性是一種學(xué)習(xí)的平滑性，即最優(yōu)函數(shù)的性能隨著樣本容量n的增加而緩緩提高，其特征曲線是平滑過渡的，不會在任何一點產(chǎn)生劇烈的震蕩。而強烈的抖動意味著算法對于特定的本體樣本點有著特定的反映，進而說明本體學(xué)習(xí)算法本身不適合實驗對象數(shù)據(jù)，即這樣的算法得到的最優(yōu)本體函數(shù)不可能對訓(xùn)練集以外的數(shù)據(jù)產(chǎn)生很好的效果。

另一方面，理論研究最關(guān)心的是算法的收斂階和誤差界。本文的動機是在穩(wěn)定性和誤差界之間找到必然的聯(lián)系。因此如果一個本體學(xué)習(xí)算法有很好的穩(wěn)定性，那么它的學(xué)習(xí)誤差就會控制在某個范圍內(nèi)。也就是說，本文的理論結(jié)果暗示了穩(wěn)定性不僅是本體學(xué)習(xí)算法具有泛化性的前提，而且穩(wěn)定性參數(shù)控制了本體學(xué)習(xí)算法廣義界的上界。

本文針對刪除一個樣本的LOO 操作，給出對應(yīng)的本體學(xué)習(xí)算法穩(wěn)定性和本體函數(shù)假設(shè)空間一致穩(wěn)定性定義。并利用統(tǒng)計學(xué)方法，針對兩類不同的LOO 一致穩(wěn)定性定義，分別給出廣義界的估計值，這些界優(yōu)于之前同框架LOO 一致穩(wěn)定性設(shè)定論文中得到的廣義界。

1 本體學(xué)習(xí)算法及穩(wěn)定性

設(shè)Z為本體數(shù)據(jù)集，在非監(jiān)督本體學(xué)習(xí)中，Z即為本體圖頂點數(shù)據(jù)V，對于監(jiān)督本體學(xué)習(xí)則Z=V×Y。設(shè)本體學(xué)習(xí)算法A:Zn→F，其中F是本體函數(shù)空間，即假設(shè)空間。A(S)或者A(S,·)表示本體學(xué)習(xí)算法A作用在本體數(shù)據(jù)S的輸出函數(shù)。l:F×Z→R為本體虧損函數(shù)（也可以將其正則化，即取值限定在區(qū)間[0,1]內(nèi)，進而也可以表示為l:F×Z→[0,1]），給定本體函數(shù)f和本體樣本點v，本體虧損函數(shù)表示為l(f,z)。設(shè)S={z1,z2,···,zn}為容量為n的本體樣本。刪除樣本集S中的第i(i∈{1,2,···,n})個樣本vi，對應(yīng)的樣本集變?yōu)镾i={z1,z2,···,zi?1,zi+1,···,zn}，稱此類變換為LOO(leave one out)。在樣本S的表示中，若算法為非監(jiān)督本體學(xué)習(xí)算法，則zi=vi；在監(jiān)督本體學(xué)習(xí)下有zi=(vi,yi)。如果對于任意位置i(i∈{1,2,···,n})，任意S和Si，以及任意v∈V，有

成立，則稱本體算法A關(guān)于本體虧損函數(shù)l存在LOO 一致穩(wěn)定 γ。

設(shè)RD[l(A(S))]=Ez～D[l(A(S),z)]為本體算法A的期望誤差，為對應(yīng)的經(jīng)驗誤差。從而本體算法A的廣義界就定義為期望誤差和經(jīng)驗誤差的差值，記為

為了方便討論且說明本文的結(jié)果具有更加一般的規(guī)律，定理1 給出的廣義界對任意本體數(shù)據(jù)依賴函數(shù)都成立。具體地說，設(shè)M:Zn×Z→R（也可以限制其值域M:Zn×Z→[0,1]）為本體數(shù)據(jù)依賴函數(shù)(ontology data-dependent function)，它將給定本體數(shù)據(jù)集S和本體點z作為輸入，可以看作計算實值函數(shù)M(S,·)應(yīng)用到z。這里M(S)或者M(S,·)表示M作用在本體數(shù)據(jù)S上而得到的輸出函數(shù)。事實上，在本體學(xué)習(xí)框架下，有M(S,z)=l(A(S),z)，只是前者的表示有另外的數(shù)據(jù)統(tǒng)計含義，可以依賴于本體數(shù)據(jù)。在此設(shè)定下，期望誤差和經(jīng)驗誤差分別表示為RD[M(S)]=Ez～D[M(S,z)]和。對應(yīng)的廣義界表示為ΔD?S(M)=RD[M(S)]?。

考慮將本體樣本S作為輸入，本體數(shù)據(jù)依賴函數(shù)作為輸出，比如在本體監(jiān)督學(xué)習(xí)中，每個本體樣本點帶有標(biāo)記信息y，因而M(S,z)=lY(f(v),y)，即在本體樣本z=(v,y)上執(zhí)行本體學(xué)習(xí)算法A(S)。

若對所有S∈Zn，任意i∈{1,2,···,n}，任意z∈Z有≤γ成立，則稱本體數(shù)據(jù)依賴函數(shù)M:Zn×Z→R 存在LOO 一致穩(wěn)定 γ。若對所有S,S′∈Zn，其中S和S’是容量相同的兩個本體數(shù)據(jù)集且只有一個數(shù)據(jù)不相同，滿足 ?E?Y，有

P[M(S)∈E]≤eεP[M(S′)∈E]

則稱算法A:Zn→Y是ε-差分隱私（leave-one-out-ε-differentially private）的。本體學(xué)習(xí)算法的假設(shè)空間(hypothesis space)就是本體函數(shù)選取的范圍空間，也稱為假設(shè)集，它是本體學(xué)習(xí)算法設(shè)計的核心。假設(shè)空間過大意味著函數(shù)選取的范圍很大，會導(dǎo)致算法不收斂；而假設(shè)空間過小又會導(dǎo)致得到的最優(yōu)本體函數(shù)性能不佳。理想的本體學(xué)習(xí)算法都會對假設(shè)空間有精巧的設(shè)計，一般在數(shù)學(xué)上會選取凸函數(shù)空間，常見的本體假設(shè)空間有再生核希爾伯特空間、索伯列夫空間等。由于假設(shè)空間是一個抽象的函數(shù)空間，一般用抽象的工具來刻畫它的大小，比如覆蓋數(shù)(covering number)。

在一般學(xué)習(xí)框架下，本體假設(shè)空間是由算法本身決定的，獨立于本體樣本，記為F。本文將考慮受本體數(shù)據(jù)集影響的假設(shè)空間，稱為本體樣本依賴假設(shè)集(ontology sample dependent hypothesis set)，也稱為本體數(shù)據(jù)依賴假設(shè)集(ontology data dependent hypothesis set)，記為FS，表示根據(jù)本體訓(xùn)練樣本集S而選取的本體函數(shù)空間。F和FS的關(guān)系是：當(dāng)S給定后，F(xiàn)S通常選取為F的一個子集，即FS?F。進而可以寫成F=。這樣，F(xiàn)表示為本體數(shù)據(jù)依賴假設(shè)集的并集，故也稱F=為本體數(shù)據(jù)依賴假設(shè)集族。

給定本體樣本容量n∈N。如果對任意i∈{1,2,···,n}，任意本體樣本集S和刪除一個元素后的本體樣本集Si，存在某個 β≥0，對任意f∈FS，都存在某個f′∈，使得對任意z∈Z都有|l(f,z)?l(f′,z)|≤β 成立。則稱本體數(shù)據(jù)依賴假設(shè)集族F=存在LOO 一致穩(wěn)定β，簡稱 β-穩(wěn)定。

給定本體樣本容量n∈N。若對任意S∈Zn，都有成立，則稱本體數(shù)據(jù)依賴假設(shè)集族F=存在LO O-CV 穩(wěn)定 χ，其中 χ≥0。更進一步，若成立，則稱F存在LOO-均值CV 穩(wěn)定，同樣≥0。

本體數(shù)據(jù)依賴假設(shè)集族F=的直徑 Δ和均值直徑分別定義為

對任意兩個本體樣本集S,T∈Zn以及拉德馬赫向量 σ，集合ST,σ由S通過如下變換得到：對于i∈{1,2,···,n}，若發(fā)現(xiàn) σi=?1，則將S中第i個元素替換成集合T中的第i個元素。將假設(shè)集記為。

固定n∈N，本體數(shù)據(jù)依賴假設(shè)集族F=關(guān)于兩個本體樣本集S=和T=的拉德馬赫復(fù)雜度(Rademacher complexity)和經(jīng)驗拉德馬赫復(fù)雜度(empirical Rademacher complexity)分別定義為

2 算法理論分析

定理1設(shè)M:Zn×Z→[0,1]為本體數(shù)據(jù)依賴函數(shù)且存在LOO 一致穩(wěn)定 γ，則對于任意Z上的概率分布D和任意 δ∈(0,1)，有

本文的第一個主要結(jié)果給出了本體數(shù)據(jù)依賴函數(shù)框架下的學(xué)習(xí)算法廣義界以及廣義界平方的上界，其中式(1）說明本體穩(wěn)定算法的誤差界的平方的期望值可以被一致穩(wěn)定參數(shù)所控制在某個固定的范圍內(nèi)，而式(2)則說明誤差界越大，它發(fā)生的概率越小。

證明考慮m個本體數(shù)據(jù)集，每個數(shù)據(jù)集的容量均為n。為了防止混淆，稱其為多重本體數(shù)據(jù)集，記為S。顯然S∈Zm×n，將每個本體子數(shù)據(jù)集分別記為S1,S2,···,Sm，且第l個本體子數(shù)據(jù)集的第i個元素記為Sl,i。設(shè)l∈{1,2,···,m}，定義

設(shè)S和S′是兩個多重本體數(shù)據(jù)集，且S′與S相比僅僅是第k個本體數(shù)據(jù)子集的第i個元素不同。設(shè)Sk(i)為多重本體數(shù)據(jù)集，它通過刪除S′中第k個本體數(shù)據(jù)子集的第i個元素得到。如果l≠k，則Sl=，進而有fl(S)=fl(S′)。若l=k，則

對任意l∈{1,2,···,m}，設(shè)本體數(shù)據(jù)依賴函數(shù)Ml:Zn×Z→[0,1]擁有LOO 一致穩(wěn)定 γ，A:Zn×m→{1,2,···,m}是 ε-差分隱私算法。

設(shè)XS=，I(·)為真值函數(shù)（論斷為真時取值1，否則取值0），則

式中：Sl(i),z為多重本體數(shù)據(jù)集，它通過將第l個本體數(shù)據(jù)子集的第i個元素替換成z得到；是通過將Sl中第i個元素替換成z得到的本體數(shù)據(jù)子集。

由此可以得到

式（4）的后半部分可以用類似的方法得到。特別地，有

首先證明(2)成立。取m=，設(shè)f1,f2,···,fm為實值函數(shù)(如式(3)定義)，fm+1(S)=0。設(shè)A是f1,f2,···,fm,fm+1上的執(zhí)行算法滿足對任意l∈{1,2,···,m}有。注意到，對于l∈{1,2,···,m}有Ml=M且Mm+1=0，因此由式（5）可知：

運用文獻[22]中引理7.1 可知：

結(jié)合文獻[23]中引理1.2 可知：

從而式(2)成立。

式(1)證明：設(shè)L(S,z)=M(S,z)?RD[M(S)]，則易證L是關(guān)于分布D的無偏估計，對任意S∈Zn都有RD[L(S)]=0。由于M的取值范圍在[0,1] 內(nèi)，因此L取值范圍是[?1,1]。由于

L擁有LOO 一致穩(wěn)定至多為 2γ。又因為

得到

由此，式(1)等價于證明：設(shè)本體數(shù)據(jù)依賴函數(shù)L:Zn×Z→[?1,1]擁有LOO 一致穩(wěn)定 2γ，D是Z上的任意分布。如果L是關(guān)于D的無偏估計，則有

注意到：

考慮到L是無偏估計且函數(shù)h不依賴于zi或zj，因此對應(yīng)每個給定的zi和z，有

由此，式(1)得證。

定理2設(shè)監(jiān)督本體學(xué)習(xí)算法A關(guān)于本體虧損函數(shù)l存在LOO 一致穩(wěn)定 γ，且本體虧損函數(shù)l有界：l(·,·)≤L，有

證明通過直接計算，可得

用類似的方法可以得到：

因此，定理2 得證。

定理3設(shè)本體數(shù)據(jù)依賴假設(shè)集族F=的直徑和均值直徑分別為 Δ 和，且有LOO 一致穩(wěn)定 β，則F有LOO-CV 穩(wěn)定 Δ+β和LOO-均值CV穩(wěn)定。

證明設(shè)S∈Zn，z∈S。對任意f∈FS，f′∈，由LOO 一致穩(wěn)定條件，存在f′′∈FS使得l(f′,z)?l(f′′,z)≤β。從而

進而

這說明定理3 得證。

定理4設(shè)F=為本體數(shù)據(jù)依賴假設(shè)集族，且存在LOO 一致穩(wěn)定 β。設(shè)Ψ=如式(7)所定義，則對任意 δ>0，式(8)在所有本體樣本S,T～Zn中以概率至少1?δ成立：

證明設(shè)本體樣本T'從T中得到且和T只有一個本體樣本點不同，不妨記第k個元素不同，其中k∈{1,2,···,n}。給定η>0，對于任意拉德馬赫向量 σ，根據(jù)上確界的定義，存在f′∈使得

根據(jù)F存在LOO 一致穩(wěn)定 β的假設(shè)，存在f∈，使得對任意z∈Z，有

其中f′′來自將ST,σ中第k個元素刪除后得到的新本體樣本集對應(yīng)的假設(shè)集。從而有

由于η>0是任意的，得到

這意味著，將T替換成T′，對的影響最多為 2β+。用相同的方法可以得到，對S改變一個本體樣本點對的影響最多為 2β。最后，利用McDiarmid 不等式[24]得到定理4 的結(jié)論。

定理5設(shè)F=為本體數(shù)據(jù)依賴假設(shè)集族，存在LOO 一致穩(wěn)定 β和LOO-均值CV 穩(wěn)定。設(shè)Ψ=如式(7)所定義，則對任意 δ>0，所有f∈FS，式(9)在所有本體樣本S～Zn中以概率至少1?δ成立：

證明對任意兩個本體樣本集S和S′（只有對應(yīng)第k個元素不同，分別記為z和z′，其他均相同），令

利用簡單計算以及本體虧損函數(shù)界為1 的假設(shè)，可以得到：

根據(jù)上確界的定義可知，對任意 η>0，存在f∈FS，使得。

由F=的LOO 一致穩(wěn)定 β，通過類似定理4 中的討論，可知存在f′∈使得對任意z，有|l(f′,z)?l(f,z)|≤2β。進而

由于η>0是任意的，式(10)意味著Θ(S,S′)?Θ(S′,S′)≤4β。從而有Θ(S,S)?Θ(S′,S′)≤4β+。

通過文獻[25]中的McDiarmid 不等式可知，對任意δ>0，式(11)以概率至少1?δ成立。

另一方面，固定η>0，根據(jù)上確界的定義，對任意S∈Zn，存在fS使得

根據(jù)RD(fS)的定義，有

另外，可知

其中，Sz表示在本體數(shù)據(jù)集S中刪除元素z得到的集合。由于式(12)對所有 η>0成立，從而有。

沿用定理1 中的標(biāo)記，S∈Zm×n為多重本體數(shù)據(jù)集，它由m個本體數(shù)據(jù)集S1,S2,···,Sm構(gòu)成，每個數(shù)據(jù)集的容量均為n。第l個本體子數(shù)據(jù)集的第i個元素記為Sl,i，其中l(wèi)∈{1,2,···,m}。定理6 刻畫了多重本體數(shù)據(jù)集框架下LOO-CV 穩(wěn)定 χ的作用。

定理6設(shè)F=為本體數(shù)據(jù)依賴假設(shè)集族，存在LOO-CV 穩(wěn)定 χ，則

證明通過推導(dǎo)可知

利用定理1 中的本體多重集方法，結(jié)合定理5和定理6，可得關(guān)于用和 χ來刻畫本體數(shù)據(jù)依賴假設(shè)集族LOO 一致穩(wěn)定本體學(xué)習(xí)算法的廣義界。

定理7設(shè)F=為本體數(shù)據(jù)依賴假設(shè)集族，存在LOO 一致穩(wěn)定 β和LOO-CV 穩(wěn)定 χ。設(shè)Ψ=如式(7)所定義，則對任意δ∈(0,1)，所有f∈FS，式(13)在所有本體樣本S～Zn中以概率至少1?δ成立：

由于證明方法與之前定理類似，我們不再給出具體證明。同時，通過替換證明過程中的一些技巧，可以得到定理7 的另外一個版本如定理8。

定理8設(shè)F=為本體數(shù)據(jù)依賴假設(shè)集族，存在LOO 一致穩(wěn)定 β和LOO-CV 穩(wěn)定 χ。設(shè)Ψ=如式(7)所定義，則對任意 δ∈(0,1)，所有f∈FS，式(14)在所有本體樣本S～Zn中以概率至少1?δ成立：

3 結(jié)束語

本文主要從刪除一個本體樣本的設(shè)定出發(fā)，討論具有LOO 一致穩(wěn)定性的本體學(xué)習(xí)算法的廣義界的統(tǒng)計學(xué)特征。主要從兩個角度來討論：

1）本體學(xué)習(xí)算法關(guān)于本體虧損函數(shù)具有LOO一致穩(wěn)定性；

2）本體函數(shù)假設(shè)空間穩(wěn)定，即本體數(shù)據(jù)依賴假設(shè)集族F=存在LOO 一致穩(wěn)定 β。

利用統(tǒng)計學(xué)習(xí)理論的方法，分別給出了兩種假設(shè)框架下，本體學(xué)習(xí)算法的學(xué)習(xí)率的上界。得到的理論結(jié)果表明，在算法一致穩(wěn)定和假設(shè)空間一致穩(wěn)定的理論假設(shè)下，本體學(xué)習(xí)算法的誤差界的上界可以被穩(wěn)定性參數(shù)很好地控制，進而保證了本體算法的收斂性。鑒于各種形式的本體學(xué)習(xí)算法已被廣泛應(yīng)用于基因?qū)W、營養(yǎng)學(xué)、化學(xué)、地理信息系統(tǒng)等領(lǐng)域，本文得到的理論結(jié)果對本體學(xué)習(xí)算法的各類實際應(yīng)用有著潛在的指導(dǎo)意義和參考價值。關(guān)于穩(wěn)定性在具體某個本體學(xué)習(xí)算法中的表現(xiàn)，在未來的本體算法執(zhí)行中有待進一步實驗驗證。