本體稀疏向量衰減迭代計算策略*

蘭美輝,高煒

(1.曲靖師范學院 計算機科學與工程學院,云南 曲靖 655011;2.云南師范大學 信息學院,云南 昆明 650500)

1 引 言

本體是一種廣泛應用的數(shù)據(jù)結構化儲存和管理模型，具有強大的語義查詢和擴展檢索功能，是用一個圖G=(V,E)來表示概念集合以及集合中成員的關系.本體算法的核心問題是尋找概念之間的相互聯(lián)系和內(nèi)在關聯(lián),即在本體上的相似度計算是各種本體工程應用算法的本質(zhì)所在.一類本體學習方法是通過本體樣本的學習得到本體函數(shù)f：V→，該函數(shù)給本體圖上每個頂點(對應一個概念)分配一個分值，從而將高維幾何空間上相似度計算轉(zhuǎn)化為一維數(shù)軸上的直接距離計算.近年來，出于本體的優(yōu)越性，本體的應用領域涵蓋了整個自然科學與工程學科中，被越來越多的專家所關注并作為重點研究課題.目前，本體已成為信息檢索、數(shù)據(jù)庫、知識工程和管理學的核心內(nèi)容[1-7].

在化學、生物、制藥和材料工程相關的本體中，由于涉及基因或者復雜的分子結構，使得這些本體所要表達的信息量非常的龐大.在此類應用背景下，對本體算法的設計提出了更高的要求.為了降低計算復雜度，快速而高效地得到相似度計算結果，稀疏算法被引入到本體相似度計算和本體映射中.針對特定的應用背景和本體圖特殊的結構，設計適合本體應用的本體稀疏向量學習算法，并由此得到本體概念之間的相似度，是未來本體學習算法研究的趨勢.

本文利用核函數(shù)計算，給出一類本體稀疏向量衰減迭代方法，并將所得本體算法應用于兩個特定的工程領域來分別驗證其對本體概念相似度計算和不同本體之間映射構建的有效性.

2 新算法描述

為了構建數(shù)學模型的需要，將本體圖中每個頂點對應概念的全部信息用一個p維向量進行封裝.設v={v1,…,vp} 是頂點v對應的向量.在不引起混淆的前提下，標記v可同時表示本體圖中的頂點、該頂點對應的概念或它所對應的向量.

引入本體稀疏向量后，本體函數(shù)可表示為

(1)

其中β=(β1,…,βp) 表示稀疏向量，其特點是大部分分量的值為0或者非常小，小到可以忽略的程度； 附加項β0是一個偏移量，可用來表示噪聲或者誤差糾正項.本體稀疏向量學習模型可歸納為

(2)

其中l(wèi)(β)為虧損項，Q(β)為平衡項，用來調(diào)節(jié)本體稀疏向量β的稀疏程度.

(3)

其中β=(β1,…,βn) 表示新本體稀疏向量.可見，同樣是通過本體稀疏向量將頂點映射成實數(shù)，表達式(1)和表達式(3)有著本質(zhì)的不同：在忽略偏移量β0的前提下，公式(1)是將頂點對應向量和稀疏向量作內(nèi)積得到函數(shù)值；而公式(3)是將頂點對應向量和樣本點作核運算后與對應稀疏向量的分量相乘后再求和.前者稀疏的每個頂點對應向量的分量，其實質(zhì)是強化本體信息中最重要的特征；后者是稀疏樣本集中的樣本信息，其實質(zhì)是強化樣本信息的重要性，所得本體函數(shù)fβ對樣本的依賴性較強.因此，后者較前者更加符合機器學習的本質(zhì)，能充分挖掘所給樣本集合的潛力.

(4)

(5)

(6)

(7)

由于Lp關于β+和β-都是可導的，因此(6)的優(yōu)化條件為

(8)

(9)

從而有

(10)

(11)

從如上條件(8)、(9)、(10)和(11)可知，在核函數(shù)參數(shù)γ固定的情況下，其最優(yōu)解有如下性質(zhì)：

(ⅰ)若λ>0，則

且

(12)

i?A?|gi|<λ

(13)

(14)

(15)

(16)

(17)

(18)

(19)

可知(18)和(19)構成了m+1個線性方程.定義如下變量：

從而上面的m+1個線性方程可以寫成如下矩陣的形式：

ΩΔ=Ψ

(20)

若Ω是滿秩矩陣，則Ω-1存在且

(21)

隨著γ的變化，算法需要對稠密點集合A的變化進行如下監(jiān)控：

?其中一個βA(i)(i=1,…,m)達到0；

?有一個標記i?A加入A，即|gi|=λ發(fā)生.

通過監(jiān)控，計算在事件發(fā)生的情況下使得γ<γl成立的最大γ.這個γ值是一個斷點并記為γl+1，然后更新稠密點集合A并繼續(xù)算法直到整個算法結束.下面給出整個算法的過程.

算法A.本體稀疏向量衰減迭代計算算法

A3:whileγ>γmin

A4:設r=θ;

A5:whiler<1-ε

A6:γ=γtr;

A7:通過公式(21)計算(β(γ),β0(γ));

A9:end while

A10:更新集合A;

A11:end while

A12:輸出滿足γmin<γ<γ0的解序列(β(γ),β0(γ)).

3 實 驗

在下面兩個實驗中，將分別驗證新本體稀疏向量學習算法對特定應用領域本體相似度計算和構建本體映射的可行性.在得到最優(yōu)稀疏向量后，再通過該向量把本體頂點映射成實數(shù)值，最后本體概念之間的相似度關系通過它們對應實數(shù)之間的一維距離來判斷：距離越大，則相似度越??；距離越小，則相似度越大.

3.1 本體相似度計算實驗

第一個實驗驗證本文本體稀疏向量衰減迭代算法是否可應用于植物學領域，采用的數(shù)據(jù)來自http://www.plantontology.org網(wǎng)站構建的植物學PO本體O1(其基本結構可參考圖1).該本體其實是一個植物學數(shù)據(jù)庫，或者可理解為一本植物學字典.用戶可利用網(wǎng)站的搜索功能進行概念查找，并由此知道對應的含義和與其他概念的關聯(lián).將以下三類經(jīng)典本體學習算法也同時作用于植物學PO本體：基于一般排序?qū)W習方法的本體算法[8]、基于快速排序?qū)W習的本體算法[9]和基于NDCG測度計算的本體算法[10].使用傳統(tǒng)的P@N[11]平均準確率來衡量四種算法的有效性，并取N為3、5和10，將四類準確率進行對比，結果如表1所示.

圖1 PO本體O1Fig.1 PO ontology O1

表1 實驗1部分數(shù)據(jù)Table 1 Part of the data in experiment 1

通過表1對比分析可知，當N的取值為3、5和10時，本文本體稀疏向量衰減迭代學習算法得到的P@N準確率要明顯高于其他三類算法，即新本體算法對于植物學PO本體上進行相似度計算是可行的，并且是高效的.

3.2 本體映射實驗

第二個實驗對象的是仿生學領域中構造的兩個“仿生機器人”本體O2和O3，其目的是在它們之間構造本體映射，從而來了解它們各自概念之間的相互關聯(lián).構造這兩個本體的依據(jù)是機器人的各個部件的連接和它們之間的相互關聯(lián).為了進行實驗數(shù)據(jù)對比，將基于k-部排序的本體學習算法[12]、基于NDCG測度計算的本體學習算法[10]和基于超圖調(diào)和分析的本體學習算法[13]也應用于“仿生機器人”本體O2和O3，并根據(jù)得到的相似度構建本體映射策略.實驗結果同樣采用傳統(tǒng)的P@N準確率來進行對比，當N的取值為1、3和5時數(shù)據(jù)對比可參考表2.

圖2 “仿生機器人”本體O2 圖3 “仿生機器人”本體O3Fig.2 Biomimetic robot ontology O2 Fig.3 Biomimetic robot ontology O3

表2 實驗2部分數(shù)據(jù)Table 2 Part of the data in experiment 2

由表2數(shù)據(jù)可知，本文本體稀疏向量衰減迭代算法對于在“仿生機器人”本體O2和O3間建立基于相似度的本體映射而言，其效率要明顯高于其他三類傳統(tǒng)本體學習算法.當N的取值為1、3和5時，P@N準確率數(shù)據(jù)對比說明了本文提出的本體學習新算法的高效性和有效性.

4 結束語

本體已廣泛應用于教育學、心理學、測量學、地理信息系統(tǒng)、化學、制藥學和材料科學等諸多領域，且作為核心內(nèi)容的本體概念相似度計算受到各個學科的廣泛關注.本文從學習算法的角度給出一類學習本體稀疏向量的衰減迭代策略，并由此間接計算本體概念之間的相似度.通過兩個具體工程應用實例，說明新算法對于特定領域的本體工程應用是有效的，有廣泛的應用前景.