基于TLP經(jīng)驗(yàn)?zāi)Ｐ偷谋倔w學(xué)習(xí)算法

何國英，高 煒

（1.云南師范大學(xué)經(jīng)濟(jì)與管理學(xué)院，昆明 650500；2.云南師范大學(xué)信息學(xué)院，昆明 650500）

作為一種結(jié)構(gòu)化存儲和表示數(shù)據(jù)的模型，本體近幾年來得到了廣泛的關(guān)注并應(yīng)用于計(jì)算機(jī)科學(xué)的各個(gè)領(lǐng)域。作為一種模型和工具，隨著本體技術(shù)的不斷完善，它又從原先的計(jì)算機(jī)領(lǐng)域應(yīng)用到生物醫(yī)學(xué)〔1〕、地理信息系統(tǒng)〔2〕、教育學(xué)〔3〕等其他學(xué)科領(lǐng)域。在具體工程應(yīng)用中，用本體圖G=（V，E）來表示本體的概念層次結(jié)構(gòu)，其中本體圖中的頂點(diǎn)集合V對應(yīng)相關(guān)概念集合，邊集合E對應(yīng)概念之間的關(guān)系集合。本體應(yīng)用的本質(zhì)概括起來可分為兩大類：本體相似度計(jì)算和本體映射。這兩種應(yīng)用的實(shí)質(zhì)問題都是本體圖頂點(diǎn)間的相似度計(jì)算。

隨著信息處理數(shù)據(jù)量的日趨龐大，學(xué)習(xí)算法被引入到本體相似度計(jì)算和本體映射中，并逐漸代替原有的啟發(fā)式算法。本體學(xué)習(xí)算法的本質(zhì)是通過樣本的學(xué)習(xí)，得到最優(yōu)函f：V →R。從而得到定義在頂點(diǎn)集V 上的實(shí)值得分函數(shù)f 將本體圖中每個(gè)頂點(diǎn)映射成對應(yīng)實(shí)數(shù)，進(jìn)而通過計(jì)算頂點(diǎn)對應(yīng)實(shí)數(shù)間的差值的大小來判定兩頂點(diǎn)對應(yīng)概念間的相似度。該技術(shù)的優(yōu)點(diǎn)在于：由于本體圖被映射到了實(shí)直線，兩頂點(diǎn)的相似度變成了它們對應(yīng)實(shí)數(shù)在實(shí)數(shù)軸上的距離，從而增加了直觀性。

文獻(xiàn)〔4〕將排序?qū)W習(xí)技術(shù)應(yīng)用于在不同本體之間建立本體映射，得到f；文獻(xiàn)〔5〕將圖學(xué)習(xí)方法與本體圖的結(jié)構(gòu)相融合，得到對應(yīng)的本體算法；文獻(xiàn)〔6〕和〔7〕給出新的本體相似度計(jì)算方法，通過圖上的正則化模型的求解得到實(shí)值得分函數(shù)f，由此得到本體相似度計(jì)算和本體映射策略；文獻(xiàn)〔8〕將k-部排序和半監(jiān)督算法相融合，提出k-部排序半監(jiān)督學(xué)習(xí)算法，并應(yīng)用于本體。文獻(xiàn)〔9〕和〔10〕對這些本體算法的收斂性進(jìn)行了理論上的分析。

文獻(xiàn)〔11〕將傳統(tǒng)的回歸方法應(yīng)用于本體相似度和本體映射并得到相應(yīng)的算法，同時(shí)給出了一些算法的理論結(jié)果。該方法與眾不同之處在于它直接得到相似度函數(shù)f：V × V → R+? {0}，即f 將每一對頂點(diǎn)映射成非負(fù)實(shí)數(shù)。在此基礎(chǔ)上，我們對文獻(xiàn)〔11〕的計(jì)算模型加以改進(jìn)，運(yùn)用特殊懲罰項(xiàng)對目標(biāo)函數(shù)的光滑性加以控制。本文的組織結(jié)構(gòu)如下：首先提出基于TCP 的新本體回歸模型；其次，得到基于TCP 學(xué)習(xí)模型的新本體相似度計(jì)算和本體映射算法；最后，將此算法應(yīng)用于生物學(xué)“GO”本體和物理教育學(xué)本體，通過實(shí)驗(yàn)數(shù)據(jù)的對比分析來說明本文所提算法的有效性。

1 新回歸算法思想

對本體圖或多本體圖中部分頂點(diǎn)對給定標(biāo)記yi∈R+?{0}，樣本集可表示為S={（v1，，y1），…，（vn，，yn）}。學(xué)習(xí)的過程是通過樣本集S的學(xué)習(xí)得到相似度函數(shù)f：V×V →R+?{0}。設(shè)虧損函數(shù)由于無法預(yù)先得知樣本分布情況，因此通過如下經(jīng)驗(yàn)?zāi)Ｐ偷玫絝〔11〕：

本文的主要貢獻(xiàn)體現(xiàn)在對算法（1）的改進(jìn)，著眼于懲罰項(xiàng)λN(f)的討論。關(guān)于懲罰項(xiàng)的選擇，一般可選取融合懲罰項(xiàng)，其中函數(shù)h可選擇為Lq泛數(shù)，例如選擇L1-泛數(shù)后該懲罰項(xiàng)為

文獻(xiàn)〔12〕指出：在回歸經(jīng)驗(yàn)?zāi)Ｐ椭惺褂肔asso懲罰可得到無偏參數(shù)估計(jì)。文獻(xiàn)〔13〕提出縮減Lasso懲罰（truncated Lasso penalty，簡稱TLP）如下：

其中參數(shù)τ 事先給定。本文將算法（1）的框架和縮減Lasso 懲罰項(xiàng)相融合，并采用L2-泛數(shù)來計(jì)算α，得到如下經(jīng)驗(yàn)?zāi)Ｐ停?/p>

算法（2）與算法（1）相比，改進(jìn)之處在于使用了L2-泛數(shù)縮減Lasso 懲罰，使得算法理論上成立無偏參數(shù)估計(jì)，同時(shí)與一般Lasso懲罰相比簡化了模型，降低了計(jì)算量。

2 本體算法描述

由以上分析我們得到基于TLP 經(jīng)驗(yàn)?zāi)Ｐ偷谋倔w算法，其整體描述如下。

算法A 基于TLP經(jīng)驗(yàn)?zāi)Ｐ偷谋倔w相似度計(jì)算算法

A1：對本體圖進(jìn)行預(yù)處理。將本體圖中每個(gè)頂點(diǎn)的信息用一個(gè)向量表示。

A2：選取樣本集，計(jì)算標(biāo)記從而得到S。

A3：通過模型（2）得到最優(yōu)本體函數(shù)f。

A4：將實(shí)值得分函數(shù)f 作用于本體圖G 中的每個(gè)頂點(diǎn)對，得到頂點(diǎn)對應(yīng)概念之間的相似度。

算法B 基于TLP經(jīng)驗(yàn)?zāi)Ｐ偷谋倔w映射算法

B1：對多本體圖進(jìn)行預(yù)處理。設(shè)圖G1，G2，…，Gm分別對應(yīng)本體 O1，O2，…，Om，令G=G1+G2+…+Gm。將G中每個(gè)頂點(diǎn)的相關(guān)信息用一個(gè)向量來表示。

B2：選取樣本集，計(jì)算標(biāo)記從而得到S。

B3：通過模型（2）得到最優(yōu)本體函數(shù)f。

B4：將實(shí)值得分函數(shù)f 作用于G 中來自不同本體間的頂點(diǎn)對，得到不同本體頂點(diǎn)對應(yīng)概念之間的相似度。

B5：根據(jù)B4得到的相似度，選擇映射策略生成本體映射。

3 實(shí)驗(yàn)

在這一節(jié)中，我們將通過兩個(gè)具體的實(shí)驗(yàn)來分析新算法的有效性。對于平衡參數(shù)λ，可用cross validation 技術(shù)〔14〕來得到最優(yōu)的λ。為了簡化計(jì)算，這里我們統(tǒng)一取γ=10-1。在兩個(gè)實(shí)驗(yàn)中，第一個(gè)實(shí)驗(yàn)本體頂點(diǎn)數(shù)量龐大，第二個(gè)實(shí)驗(yàn)本體頂點(diǎn)數(shù)較少，因此τ的值分別取0.2 和0.5。在選擇了頂點(diǎn)對后，標(biāo)記yi的值采用如下計(jì)算方法得到：

其中vi和分別表示頂點(diǎn)vi和對應(yīng)的向量。

3.1 本體相似度實(shí)驗(yàn)第一個(gè)實(shí)驗(yàn)是采用生物GO本體O1（其數(shù)據(jù)來自http：//www.geneontology.org，大致結(jié)構(gòu)可參考圖1）來驗(yàn)證算法A 的效率。實(shí)驗(yàn)結(jié)果采用P@N〔15〕平均準(zhǔn)確率來衡量。

另外，分別將本體回歸算法〔11〕、快速排序算法〔16〕和標(biāo)準(zhǔn)本體排序算法〔4〕作用于GO 本體。將這3種算法得到的P@N準(zhǔn)確率與本文算法A得到的準(zhǔn)確率進(jìn)行比較，部分?jǐn)?shù)據(jù)見表1。

表1 實(shí)驗(yàn)1部分?jǐn)?shù)據(jù)

由表1準(zhǔn)確率對比可知，算法A對于GO本體的效率明顯高于本體回歸算法、快速排序算法和標(biāo)準(zhǔn)排序算法。

3.2 本體映射實(shí)驗(yàn)本文的第二個(gè)實(shí)驗(yàn)是采用下面兩個(gè)“物理教育”本體O2和O3（這2 個(gè)本體由文獻(xiàn)〔16〕構(gòu)建）來驗(yàn)證算法B的效率。

圖2 “物理教育”本體O2

圖3 “物理教育”本體O3

同樣地，分別將本體回歸算法、快速排序算法和標(biāo)準(zhǔn)本體排序算法作用于“物理教育”本體，將這3種算法得到的P@N準(zhǔn)確率與本文算法B得到的準(zhǔn)確率進(jìn)行比較，部分?jǐn)?shù)據(jù)見表2。

表2 實(shí)驗(yàn)2部分?jǐn)?shù)據(jù)

由表2 準(zhǔn)確率對比可知，算法B 對于“物理教育”本體O2和O3間建立本體映射的效率明顯高于本體回歸算法、快速排序算法和標(biāo)準(zhǔn)排序算法。

4 結(jié)束語

本文利用對懲罰項(xiàng)的改進(jìn)進(jìn)而得到新的經(jīng)驗(yàn)計(jì)算模型，由此得到基于TLP經(jīng)驗(yàn)?zāi)Ｐ偷谋倔w相似度計(jì)算和本體映射算法。由于新模型采用了TLP作為懲罰項(xiàng)，使得算法在理論上具有參數(shù)無偏估計(jì)的特征，進(jìn)而在一定程度上提高了效率。

〔1〕MORK P，BERNSTEIN P. Adapting a generic match algorithm to align ontologies of human anatomy〔C〕//20th International Conferrence on Data Engineering. 2004：787-790.

〔2〕FONSECA F，EGENHOFER M，DAVIS C，et al. Semantic Granularity in Ontology-Driven Geographic Information Systems〔J〕.AMAI Annals of Mathematics and Artificial Intelligence- Special Issue on Spatial and Temporal Granularity，2002，36（1-2）：121-151.

〔3〕BOUZEGHOUB A，ELBYED A. Ontology mapping for web-based educational systems interoperability〔J〕. Interoperability in Business Information Systems，2006，1（1）：73-84.

〔4〕高煒，蘭美輝.基于排序?qū)W習(xí)方法的本體映射算法〔J〕.微電子學(xué)與計(jì)算機(jī)，2011，28（9）：59-61.

〔5〕高煒，梁立，張?jiān)聘?基于圖學(xué)習(xí)的本體概念相似度計(jì)算〔J〕.西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，36（4）：64-67.

〔6〕高煒，梁立.基于超圖正則化模型的本體概念相似度計(jì)算〔J〕.微電子學(xué)與計(jì)算機(jī)，2011，28（5）：15-17.

〔7〕高煒，朱林立，梁立. 基于圖正則化模型的本體映射算法〔J〕.西南大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，34（3）：118-121.

〔8〕高煒，梁立，徐天偉，等.半監(jiān)督k-部排序算法及在本體中的應(yīng)用〔J〕. 中北大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，34（2）：140-146.

〔9〕高煒，張?jiān)聘?，梁?Cs相似度函數(shù)下正則譜聚類的收斂階〔J〕. 蘭州大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，47（2）：109-111.

〔10〕高煒，周定軒.與一般相似度函數(shù)相關(guān)的譜聚類的收斂性〔J〕.中國科學(xué)：數(shù)學(xué)，2012，42（10）：985-994.

〔11〕GAO Y，GAO W.Ontology similarity measure and ontology mapping via learning optimization similarity function〔J〕. International Journal of Machine Learning and Computing，2012，2（2）：107-112.

〔12〕FAN J，LI R. Variable selection via nonconcave penalized likelihood and it oracle properties〔J〕. JASA，2001（96）：1348-1360.

〔13〕SHEN X，PAN W，ZHU Y. Likelihood-based selection and sharp parameter estimation〔J〕. JASA，2012（107）：223-232.

〔14〕CAPONNETTO A，YAO Y. Cross validation based adaptation for regularization operators in learning theory〔J〕.Anal Appl，2010（8）：161-183.

〔15〕CRASWELL N，HAWKING D. Overview of the TREC 2003 web track〔C〕//Proceedings of the Twelfth Text Retrieval Conference.2003：78-92.

〔16〕HUANG X，XU T，GAO W，et al. Ontology Similarity Measure and Ontology Mapping Via Fast Ranking Method〔J〕.International Journal of Applied Physics and Mathematics，2011，1（1）：54-59.