基于對偶理論的本體稀疏向量學(xué)習(xí)算法*

高 煒

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

?

基于對偶理論的本體稀疏向量學(xué)習(xí)算法*

高 煒

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

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

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

1 引 言

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

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

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

2 算法描述

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

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

具體地說，通過本體稀疏向量的學(xué)習(xí)，本體函數(shù)可作如下表示：

(1)

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

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

(2)

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

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

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

參數(shù)設(shè)置：w>1，L0>0.

輸出：本體稀疏向量β

初始值設(shè)置：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 本體相似度計算實驗

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

…

從而得到返回集

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

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

圖1 數(shù)學(xué)本體O1

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

3.2 本體映射實驗

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

圖2 “大學(xué)”本體O2 圖3 “大學(xué)”本體O3

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

4 結(jié)束語

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

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

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

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

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

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

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

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

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

[9] 高煒,周定軒.與一般相似度函數(shù)相關(guān)的譜聚類的收斂性[J].中國科學(xué):數(shù)學(xué)，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

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

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

高 煒.

TP

A

1007-9793(2015)04-0046-05