本體學習算法的兩類LOO 一致穩定性和廣義界

朱林立，華鋼，高煒

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

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

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

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

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

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

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

本文針對刪除一個樣本的LOO 操作，給出對應的本體學習算法穩定性和本體函數假設空間一致穩定性定義。并利用統計學方法，針對兩類不同的LOO 一致穩定性定義，分別給出廣義界的估計值，這些界優于之前同框架LOO 一致穩定性設定論文中得到的廣義界。

1 本體學習算法及穩定性

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

成立，則稱本體算法A關于本體虧損函數l存在LOO 一致穩定 γ。

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

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

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

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

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

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

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

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

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

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

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

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

2 算法理論分析

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

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

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

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

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

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

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

由此可以得到

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

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

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

結合文獻[23]中引理1.2 可知：

從而式(2)成立。

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

L擁有LOO 一致穩定至多為 2γ。又因為

得到

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

注意到：

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

由此，式(1)得證。

定理2設監督本體學習算法A關于本體虧損函數l存在LOO 一致穩定 γ，且本體虧損函數l有界：l(·,·)≤L，有

證明通過直接計算，可得

用類似的方法可以得到：

因此，定理2 得證。

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

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

進而

這說明定理3 得證。

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

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

根據F存在LOO 一致穩定 β的假設，存在f∈，使得對任意z∈Z，有

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

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

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

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

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

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

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

由F=的LOO 一致穩定 β，通過類似定理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，根據上確界的定義，對任意S∈Zn，存在fS使得

根據RD(fS)的定義，有

另外，可知

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

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

定理6設F=為本體數據依賴假設集族，存在LOO-CV 穩定 χ，則

證明通過推導可知

利用定理1 中的本體多重集方法，結合定理5和定理6，可得關于用和 χ來刻畫本體數據依賴假設集族LOO 一致穩定本體學習算法的廣義界。

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

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

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

3 結束語

本文主要從刪除一個本體樣本的設定出發，討論具有LOO 一致穩定性的本體學習算法的廣義界的統計學特征。主要從兩個角度來討論：

1）本體學習算法關于本體虧損函數具有LOO一致穩定性；

2）本體函數假設空間穩定，即本體數據依賴假設集族F=存在LOO 一致穩定 β。

利用統計學習理論的方法，分別給出了兩種假設框架下，本體學習算法的學習率的上界。得到的理論結果表明，在算法一致穩定和假設空間一致穩定的理論假設下，本體學習算法的誤差界的上界可以被穩定性參數很好地控制，進而保證了本體算法的收斂性。鑒于各種形式的本體學習算法已被廣泛應用于基因學、營養學、化學、地理信息系統等領域，本文得到的理論結果對本體學習算法的各類實際應用有著潛在的指導意義和參考價值。關于穩定性在具體某個本體學習算法中的表現，在未來的本體算法執行中有待進一步實驗驗證。