高 煒

(云南師范大學 信息學院,云南 昆明 650500)

?

基于對偶理論的本體稀疏向量學習算法*

高 煒

(云南師范大學 信息學院,云南 昆明 650500)

作為一種語義計算和結構化信息存儲模型，本體已被廣泛應用于生物、物理、地理信息系統(tǒng)等多個領域.在本體學習算法中，本體圖頂點所對應的概念信息用一個多維向量來表示.但在大部分應用背景下，頂點之間的相似度取決于少部分分量.基于對偶理論得到本體稀疏向量的計算方法，將該算法應用于數學本體和大學本體，通過P@N準備率來說明算法的效率.

本體; 相似度計算; 本體映射; 稀疏向量

1 引 言

傳統(tǒng)的啟發(fā)式本體計算方法已經無法勝任大數據量的本體相似度計算，因而利用各種學習算法來得到本體相似度計算函數和本體映射已成為近幾年研究的重點.本體數據模型可用圖G=(V,E)來表示，一類本體學習算法其基本思想是得到一個實值本體函數f：V→.該本體函數的作用是將所有本體頂點映射到實數軸，從而頂點對應的概念之間的相似度可以用它們對應的實數在數軸上的距離來衡量.

文獻[1]提出了正則化框架下的半監(jiān)督本體算法，在計算模型中充分利用未標記數據的相關信息，同時將數據嵌入到特征空間，利用特征表示得到相關算法；文獻[2]從線性歐氏空間及再生核希爾伯特空間出發(fā)，得到有噪條件下的新正則化求解模型，同時將注意力集中到假設空間的設置上；文獻[3]給出基于優(yōu)先圖本體相似度計算方法；文獻[4]得到基于迭代拉普拉斯的半監(jiān)督本體學習算法；更多本體學習算法可參考文獻[5-7].有關本體算法的理論結果，可參考文獻[8-9].

本文利用對偶技術得到遞歸計算方法來計算本體稀疏向量，通過本體稀疏向量再得到本體函數，最后由本體函數來計算概念頂點對應實數在數軸上的距離，從而確定概念之間的相似度.

2 算法描述

當使用機器學習方法進行本體相似度計算時，需要將每個頂點的信息用一個p維向量來表示.記v={v1,…,vp}是頂點v對應的向量.為了表示方便，用v來同時表示頂點以及對應的向量.本體學習算法最終目標是獲得本體實值函數f:V→,通過頂點對應的實數在數軸上的距離來衡量頂點對應的概念之間的相似度.本體函數的本質是一種降維算子f:p→.

本體概念對應頂點的向量即包含了這個概念的所有語義信息，又涵蓋了概念在整個本體圖中的鄰域關聯信息.在實際應用中，向量的維度p會非常的大.例如在基因學本體中，所有基因信息可能都包含在一個向量中.此外，本體圖復雜的圖結構也增加了計算的復雜度，例如GIS本體.但在實際應用過程中，真正對概念之間相似度起決定作用的恰恰是p維向量中的少部分分量.例如在遺傳本體應用中，導致某種遺傳病發(fā)生的往往是少數基因，大部分基因與該遺傳病無任何關系；在交通本體的實際應用中，假設某個地點產生交通事故并造成駕駛員或者路人受傷，那么需要尋找的是和事故發(fā)生地點最近的醫(yī)院，其周邊的辦公樓和住宅與此無關，即我們的需求是尋找本體圖中滿足特定鄰域結構特征的頂點(概念).由此，稀疏學習算法恰好適合這種本體應用.

具體地說，通過本體稀疏向量的學習，本體函數可作如下表示：

(1)

這里β=(β1,…,βp)是稀疏向量，其特點是大部分分量的值等于0；δ是與噪聲有關的誤差項.在忽略δ的前提下，由(1)可知，只要得到稀疏向量就可以確定本體函數f.因此，本體函數學習就歸結為本體稀疏向量的學習.

設V∈n×p為本體信息矩陣，它的每一列對應一個頂點的向量，n為樣本容量.本體稀疏向量β的學習模型可以寫成如下矩陣形式：

(2)

l(Vβ)+λΩ(β)+l*(-κ)

本文將文獻[12]中用于圖像處理的FISTA方法加以改進，并用于本體模型(2)的求解：

輸入：初始本體稀疏向量β(0)∈p，Ω表達式，平衡系數λ>0，對偶間隙的精確度ε>0.

參數設置：w>1，L0>0.

輸出：本體稀疏向量β

初始值設置：y(1)=β(0)，t1=1，k=1.

Whileβ(k-1)對偶間隙>εdo

l(prox[λΩ](y(k))≤l(y(k))+(Δ(k))T

End while

返回β←β(k-1).

3 實 驗

3.1 本體相似度計算實驗

第一個實驗是采用數學本體O1(其結構可參考圖1)來驗證本體稀疏向量學習算法對本體相似度計算的效率.采用P@N準確率[13]來評判實驗結果的好壞.即對于本體圖中任意頂點v∈V(G).設N∈表示實驗中取與頂點v最相似的N個頂點.記

…

從而得到返回集

return(v)={v1,v2,…,vN}

再將return(v)與專家給出的與頂點v最相似的N個頂點進行匹配，計算準確率.最后計算所有頂點的平均準確率.

圖1 數學本體O1

實驗結果顯示，P@1的平均準確率為30.77%，P@3的平均準確率為51.28%，P@5的平均準確率為69.23%.從而可知本算法對數學本體的相似度計算是有效的.

3.2 本體映射實驗

第二個實驗是驗證本文稀疏向量學習算法對構建本體映射的效率.實驗的目的是在兩個“大學”本體O2和O3之間建立本體映射.實驗結果同樣采用P@N準確率來衡量.需要注意的是，本體映射中相似頂點的選取是在不同本體之間進行.

圖2 “大學”本體O2 圖3 “大學”本體O3

實驗結果顯示，P@1的平均準確率為46.43%，P@3的平均準確率為63.10%，P@5的平均準確率為85.71%.因此可知本文算法對兩大學本體之間構建本體映射是有效的.

4 結束語

利用對偶理論，對文獻[12]中用于圖像處理的FISTA方法加以改進，從而得到本體計算模型(2)的循環(huán)計算策略.同時，通過實驗數據驗證了本體稀疏向量學習算法對數學本體相似度計算和大學本體之間構建本體映射是有效的.

[1] 朱林立，戴國洪，高煒.正則化框架下半監(jiān)督本體算法[J].微電子學與計算機,2014,31(3):126-129.

[2] 朱林立，吳訪升，葉飛躍，等.有噪條件下基于正則化模型的本體學習算法[J].西北師范大學學報:自然科學版,2014,50(6):41-45.

[3] 蘭美輝，徐堅，高煒.基于優(yōu)先圖的本體相似度計算[J].科學技術與工程，2014,14(28):252-255.

[4] 彭波，徐天偉，李臻，等.迭代拉普拉斯半監(jiān)督學習本體算法[J].計算機工程與科學，2014,36(11):2164-2168.

[5] 高煒,梁立,徐天偉,等.半監(jiān)督k-部排序算法及在本體中的應用[J].中北大學學報：自然科學版，2013,34(2):140-146.

[6] 高煒，梁立，徐天偉.基于正則化瑞利系數的半監(jiān)督k-部排序學習算法及應用[J].西南師范大學學報：自然科學版，2014,39(4):124-128.

[7] 高煒，高云，梁立.基于ε-鄰域方法的本體映射算法[J].云南師范大學學報：自然科學版，2011,31(3):37-40.

[8] 高煒,張云港,梁立.Cs相似度函數下正則譜聚類的收斂階[J].蘭州大學學報：自然科學版，2011,47(2):109-111.

[9] 高煒,周定軒.與一般相似度函數相關的譜聚類的收斂性[J].中國科學:數學，2012,42(10):985-994.

[10]BORWEINJM,LEWISAS.Convexanalysisandnonlinearoptimization:theoryandexamples[M].Publisher:Springer,2006,50-60.

[11]JENATTONR,MAIRALJ,OBOZINSKIG,etal.Proximalmethodsforsparsehierarchicaldictionarylearning[C].InProceedingsoftheInternationalConferenceonMachineLearning,Haifa,Israel,487-494.

[12]BECKA,TEBOULLEM.Afastiterativeshrinkage-thresholdingalgorithmforlinearinverseproblems[J].SIAMJournalonImagingSciences,2009,2(1):183-202.

[13]CRASWELLN,HAWKINGD.OverviewoftheTREC2003webtrack[C].ProceedingsoftheTwelfthTextRetrievalConference，Gaithersburg,Maryland,NISTSpecialPublication,2003:78-92.

Duality Theory Based Ontology Sparse Vector Learning Algorithm

GAO Wei

(School of Information,Yunnan Normal University,Kunming 650500,China)

As a semantic computing and structured information storage model,ontology has been widely used in many fields of biological,physical,geographical information systems.In ontology learning algorithm,ontology graph vertices correspond to the information concept expressed as a multi-dimensional vector.However,in most application backgrounds,the similarity between vertices depends on small part of the component.In this paper,ontology sparse vector learning algorithm is obtained in terms of duality arguments.The algorithm is applied to the mathematics ontology and the university ontology, the efficiency of the algorithm is illustrated byP@Nratio.

Ontology; Similarity measure; Ontology mapping; Sparse vector

2015-01-25

國家自然科學青年基金資助項目(11401519).

高 煒(1981-)，男，浙江紹興人，博士，講師，主要從事機器學習和圖論方面研究.

高 煒.

TP

A

1007-9793(2015)04-0046-05