基于排序支持向量機的本體學習算法

高煒，蘭美輝

（1.云南師范大學信息學院，云南昆明650500；2.曲靖師范學院計算機科學與工程學院，云南曲靖655011）

基于排序支持向量機的本體學習算法

高煒1，蘭美輝2

（1.云南師范大學信息學院，云南昆明650500；2.曲靖師范學院計算機科學與工程學院，云南曲靖655011）

作為概念結構化表示、存儲和管理的模型，本體越來越受到計算機各領域?qū)W者的重視，并廣泛應用于生物學、醫(yī)學、制藥學、地理信息系統(tǒng)等其他學科領域。該文提出了一種基于排序支持向量機的本體學習算法，其特點是樣本集由頂點對構成，并采用帶有敏感參數(shù)的虧損函數(shù)。最后，將新本體算法應用到生物基因?qū)W本體和仿生機器人本體，分別驗證了算法對本體相似度計算和本體映射有較高的效率。

本體；相似度計算；本體映射；排序支持向量機

作為一種概念語義表示模型，本體自20世紀90年代引入計算機領域以來，一直受到極大的關注，并得到長足的發(fā)展。該模型已經(jīng)應用于信息檢索、查詢擴展、圖像檢索和數(shù)據(jù)集成等諸多領域。在近30年的發(fā)展中，本體作為一種強大的工具模型，被應用在多個學科，比如醫(yī)學、生物學、制藥學、地理科學、心理學和教育學等。一般用本體圖G=（V，E）作為模型來表示本體O，其圖中頂點表示概念，邊表示概念之間的從屬關系。本體在各學科中的應用，其核心問題是本體概念之間的相似度計算，進而在本體圖模型中使用學習方法的過程，即通過樣本得到最優(yōu)本體函數(shù)f：V→R，由此將本體圖中每個頂點映射成實數(shù)。最后，本體概念之間的相似度則通過概念對應頂點在本體函數(shù)下的像的幾何距離來衡量。最簡單的方法是通過對應實數(shù)在實數(shù)軸上的距離來衡量，距離越小，相似度越高。

文獻[1]將一般排序?qū)W習方法引入到本體映射；文獻[2]將流形上拉普拉斯算子反映到圖上，從而把問題歸結于求本體圖拉普拉斯矩陣次小特征值對應的特征向量，該向量第i個分量即為第i個頂點對應的實數(shù)；文獻[3－4]利用有向圖和無向圖上正則化模型得到本體相似度計算和本體映射學習算法；文獻[5]充分利用本體圖樹形結構特征，并充分考慮到未標記數(shù)據(jù)特征，由此提出k-部排序半監(jiān)督學習算法；此外，文獻[6]利用正則化瑞利系數(shù)，提出新的半監(jiān)督k-部排序?qū)W習算法；文獻[7]給出一類新的迭代計算方法，并將此方法應用于本體半監(jiān)督學習。

筆者利用排序支持向量機，提出一種新的本體學習算法，并將新算法應用于本體工程中的本體相似度計算和本體映射算法。實驗部分將該算法應用于生物基因領域驗證其對本體相似度計算的有效性，并應用于仿生機器人領域來驗證算法對構建本體映射的效率。

1 新算法描述

為了將本體概念的相關信息融入到學習方法中，首先需要對本體概念信息進行預處理，其中關鍵的一步是將每個概念對應頂點的信息封裝到一個固定維度的向量中。不失一般性，設每個頂點的信息都用p維向量來表示。并且在不引起混淆的情況下，用v={v1，…，vp}同時表示頂點v以及頂點v對應的向量?；谂判蚍椒ǖ谋倔w學習算法，其目標可概括為通過本體樣本集S的學習得到本體函數(shù)f：V→R，該函數(shù)是一個得分函數(shù)，將所有本體頂點均映射到實數(shù)，通過實數(shù)之間的幾何距離來衡量兩頂點對應本體概念之間的相似程度。

排序與之前傳統(tǒng)的分類和回歸算法有著本質(zhì)的區(qū)別，此類學習算法關注的是由排序函數(shù)得到的實數(shù)在

實數(shù)軸上的相對位置。一般來說，本體學習的樣本是一個頂點集合S={（v1，y1），…，（vn，yn）}，對應的經(jīng)驗模型可以表示為

l：RV×V×V→R為本體虧損函數(shù)，用來衡量排序出錯時的懲罰量。最優(yōu)本體函數(shù)f通過最小化R?（f，S）得到。

下面給出基于排序支持向量機（RankSVM）的本體學習算法。與經(jīng)典排序支持向量模型相比，文中針對本體的具體應用，對如下兩點作了改進：（1）傳統(tǒng)排序支持向量機模型采用部分實例集作為樣本，而在本體具體應用中，可能只需對部分本體頂點對進行相似度計算，因而文中采用一個本體頂點對的集合E′作為樣本，并且假設頂點對中前一個頂點在排序函數(shù)下的得分比后一個頂點要高；（2）傳統(tǒng)排序支持向量機模型采用平方虧損、指數(shù)虧損、對數(shù)虧損、鉸鏈虧損等虧損函數(shù)，文中考慮排序算法的實際特征，允許f（v）和標記y之間存在一定范圍的誤差，進而采用帶敏感參數(shù)的虧損函數(shù)。

具體地說，考慮上述（1），采用如下經(jīng)驗模型

其中E′是頂點對（v，v′）構成的集合，并且它們對應的標記滿足y＞y′；I是真值函數(shù)，當下標所示論斷為真時值為1，否則函數(shù)值為0。由于真值函數(shù)不可導，因此，直接計算公式（1）的難度很大。用連續(xù)凸虧損函數(shù)取代真值函數(shù)，即

其中取K：V×V→R為了核函數(shù)（比如高斯核、熱核、多項式核等），F(xiàn)即為與核函數(shù)K相關聯(lián)的再生核希爾伯特空間，C為平衡參數(shù)，項的作用是控制本體函數(shù)f的光滑性，從而使算法具有較強的泛化性。引入個變量αij，則優(yōu)化模型又可以寫成

s.t.0≤αij≤對任意（vi，vj）∈E′成立。

由統(tǒng)計學習理論中的表示理論可知，最優(yōu)解可表示成

最后，將虧損函數(shù)替換為帶敏感參數(shù)的形式，得到

其中ε>0表示誤差量，一般取值較小。優(yōu)化模型（6）可用經(jīng)典梯度下降策略得到最優(yōu)解。

特別地，當敏感參數(shù)為0或者不帶敏感參數(shù)的情況下，除了經(jīng)典梯度下降策略，文中還給出了如下迭代計算方法。

算法A：不帶敏感參數(shù)條件下基于排序支持向量機的迭代計算方法

輸入：訓練樣本E′以及樣本頂點對中每個頂點對應的標記y，核函數(shù)K，參數(shù)C，T，η

循環(huán)：For t＝1 to T do

在上述算法中，Q（α）表示公式（4）的二次目標函數(shù)。

2 實驗

下面通過兩個具體的仿真實驗來分別驗證算法對基因領域相似度計算和仿生機器人領域構建本體映射的效率。特別需要提醒的是，兩個實驗驗證的算法均是模型（6），而上節(jié)給出的迭代計算方法由于不涉及敏感參數(shù)，故不作為文中實驗的對象。

2.1 本體相似度計算實驗

由http://www.geneontology.Org網(wǎng)站構建的生物學領域GO本體（該本體為基因相關本體，記為O1），其結構如圖1所示，其目的是從語義的角度來分析原子作用、分子結構以及生物過程之間的相互關聯(lián)。對生物和基因領域工作者來說，它是個有效的數(shù)據(jù)庫，用于相關信息的檢索和查詢，并可以通過檢索來了解其他關聯(lián)信息。該實驗是驗證文中算法對GO本體進行相似度計算的效率。實驗結果的好壞用P@N[8]平均準確率來衡量。另外，還將本體回歸算法[9]、快速排序算法[10]和標準本體排序算法[1]也應用于該生物基因GO本體。表1顯示了當N取3、5、10時，四種方法得到數(shù)據(jù)的對比。

圖1 GO本體O1

表1 GO本體上四種方法數(shù)據(jù)對比

由表1中P@3、P@5、P@10準確率對比可知，文中算法對于生物基因GO本體而言，其效率高于其他三類算法。

2.2 本體映射實驗

為驗證文中算法對建立本體映射的有效性，下面采用仿生機器人本體O2（如圖2）和O3（如圖3）作為實驗對象。其目標是在O2和O3之間建立基于相似度的本體映射。將標準本體排序算法[1]、快速排序算法[10]和基于NDCG測度的本體學習算法[11]也分別應用于仿生機器人本體，并同樣采用P@N準確率作為標準對實驗結果進行對比。取N的值分別為1、3、5，部分數(shù)據(jù)見表2。

圖2 仿生機器人本體O2

圖3 仿生機器人本體O3

表2 仿生學本體四種方法數(shù)據(jù)對比

根據(jù)表2中準確率對比可知，文中基于排序支持向量機的本體算法對于在仿生機器人本體O2和O3間建立本體映射的效率明顯要高于其他三種學習算法。

3 結語

筆者提出一種基于排序支持向量機的本體算法，其特點是學習樣本由本體頂點對構成，并在虧損函數(shù)的選擇上選取帶敏感參數(shù)的虧損函數(shù)。兩個實驗結果表明基于排序支持向量機的本體算法對本體相似度計算和本體映射構建都有較高的效率。從而說明算法在本體應用領域有廣泛的前景。

[1]高煒，蘭美輝.基于排序?qū)W習方法的本體映射算法[J].微電子學與計算機，2011，28（9）：59-61.

[2]高煒，梁立，張云港.基于圖學習的本體概念相似度計算[J].西南師范大學學報（自然科學版），2011，36（4）：64-67.

[3]高煒，梁立.基于超圖正則化模型的本體概念相似度計算[J].微電子學與計算機，2011，28（5）：15-17.

[4]高煒，朱林立，梁立.基于圖正則化模型的本體映射算法[J].西南大學學報（自然科學版），2012，34（3）：118-121.

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

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

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

[8]CRASWELL N,HAWKING D.Overview of the TREC 2003 web track[C]//Proceedings of the Twelfth Text Retrieval Conference.Gaithersburg, Maryland，NIST Special Publication，2003：78-92.

[9]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.

[10]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.

[11]GAO W，LIANG L.Ontology similarity measure by optimizing NDCG measure and application in physics education[J].Future Communication，Computing，Control and Management，2011，142：415-421.

Ontology learning algorithm based on ranking SVM

GAO Wei1，LAN Meihui2
（1.School ofInformation，Yunnan Normal University，Kunming 650500，China；2.Department of Computer Science and Engineering，Qujing Normal University，Qujing 655011，China）

As a conceptual structure representation,storage and management model,ontology has raised increasing attention among scholars in various fields of computer,and been widely used in other disciplines such as biology,medicine,pharmaceutics,and geographic information system.In this paper,we have presented a class of ontology learning algorithm based on ranking SVM in which the sample set is consisted of vertex pairs and the loss function is applied with sensitive parameters.The new algorithm is applied to biological gene ontology and humanoid robot ontology.The results have verified that the algorithm has a higher efficiency in calculating the similarity of ontology and constructing ontology mapping.

ontology；similarity measuring；ontology mapping；ranking SVM

TP393.092

A

1672－0687（2016）04－0052－05

責任編輯：艾淑艷

2015－09－18

國家自然科學基金資助項目（11401519）

高煒（1981-），男，浙江紹興人，副教授，博士，研究方向：機器學習，圖論。