王 進, 高延雨, 鄧 欣, 陳喬松

(重慶郵電大學 計算智能重慶市重點實驗室, 重慶 400065)

傳統(tǒng)的監(jiān)督學習方法[1]都是根據(jù)已有完整監(jiān)督信息的訓練集(即訓練集中的樣本都有精確的標記信息)建立分類模型,然后通過得到的分類模型對待測樣本進行分類.但是現(xiàn)實中受外部環(huán)境、物理特性和物理資源等各方面狀況的制約,有些場景很難得到完整的監(jiān)督信息,例如對畫作風格進行評定,不同的評定者因為知識和經(jīng)驗不同,對同一幅畫可能有不同的評定結果,最終只能確定其屬于哪幾種風格,無法精確到具體的一種風格.僅知道訓練樣本標記候選集的場景可以使用偏標記的方法來進行處理.

偏標記學習[2-3]是一種重要的弱監(jiān)督學習框架,具體定義如下:訓練集中的訓練樣本對應多個標記,其中只有1個標記是真實標記,然后根據(jù)這樣的訓練集進行學習和對測試集的類別進行預測.目前,偏標記學習已經(jīng)應用于多媒體內容分析[4]、網(wǎng)頁挖掘[5]和人臉識別[6]等多個領域.

為了解決偏標記問題,一種常用的方法是對候選標記集合中的元素平等對待,將模型在各個候選標記上的平均輸出作為模型輸出,如基于K近鄰的偏標記學習算法PL-KNN[7](partial labelKnearest neighbor)、基于凸優(yōu)化的偏標記學習算法CLPL[8](convex loss for partial labels)等,但該方法構造之模型的性能受候選標記集合中偽標記的影響較大.IPAL[9](instance-based partial label learning)算法通過辨識消歧的方式克服了該缺陷,其分類性能優(yōu)于多數(shù)的偏標記學習方法,該算法首先構建樣本近鄰的相似度圖,然后通過迭代標記傳播和CMN[10]方法對訓練樣本消歧,即實現(xiàn)每個訓練樣本只對應1個標簽,最后對測試樣本進行預測.

隨著大數(shù)據(jù)時代的到來,大數(shù)據(jù)已經(jīng)應用于網(wǎng)絡安全[11]、人工智能和機器學習等多個領域.但IPAL[9]算法需要求取每個樣本的K近鄰,耗時特別多,而且該方法在構建近鄰樣本的相似度圖時將求取每個樣本近鄰權值的問題轉化為了有約束的最小二乘法問題,計算量較大,不適合處理大規(guī)模數(shù)據(jù).

為了解決上述問題,筆者首先對IPAL算法求取近鄰樣本的方法進行改進,使用近鄰樣本間的距離替代有約束的最小二乘問題來求取近鄰樣本權值,提出基于近鄰距離加權的偏標記算法WIPAL(weighted instance-based partial label learning).然后為了進一步提升WIPAL算法的運行速率,設計基于MPI的WIPAL算法的并行方法PWIPAL(parallel weighted instance-based partial label learning).通過試驗對所提出的偏標記算法進行驗證.

1 相關工作

MPI[12-14]是1個信息傳遞應用程序接口,適用于MIMD(multiple instruction multiple data)程序,也適合于更嚴格形式的SPMD(single program multiple data)程序,主要包括進程間通信、集合操作、進程組、通信上下文、進程拓撲結構、環(huán)境管理與查詢等內容,進程間通信可以細分為點到點通信、組歸約、廣播、散射、收集、全交換等類型.MPI[14]具有高性能、大規(guī)模、可移植性、可擴展性等諸多優(yōu)點,能夠被C語言、C++和Fortran等編程語言直接調用,但MPI沒有調試設施[15],因而開發(fā)難度較大.

偏標記學習[9]就是根據(jù)含有弱監(jiān)督信息的訓練集得到1個多類分類器.IPAL算法是一種基于樣例的偏標記學習算法,主要由訓練部分和測試部分組成,訓練部分主要包括訓練集相似度圖的構建、迭代標記傳播,測試部分包括測試集相似度圖的構建和測試樣本的預測.

相似度圖的構建:本部分構建相似度圖G=(V,E),其中V為樣本,E用樣本之間的相似度表示.首先根據(jù)樣本之間的歐式距離求出訓練集D中每個樣本的K近鄰,然后使用近鄰樣本重構其對應訓練樣本的方式獲得近鄰樣本的權值,即

(1)

式中:xiα為xj的K近鄰樣本；wiα,j為樣本xiα與xj之間的相似度;N(xj)為樣本xj的K近鄰樣本索引集.

(2)

式中:yc為1個標記;Si為樣本xi的候選標記集.

(3)

每一次標記傳播結束后,根據(jù)實例的候選標記集合和計算式

(4)

最后每個樣本根據(jù)標記置信度矩陣進行消歧,即將偏標記數(shù)據(jù)集轉化為單標記數(shù)據(jù)集.在文獻[9]中IPAL算法采用了CMN(class mass normalization)策略,使消歧考慮了各類別的先驗分布,如下:

(5)

測試階段:首先求得每個測試樣本的近鄰,然后根據(jù)最小重構準則求得每個測試樣本與其近鄰間的權重向量,算法根據(jù)測試樣本近鄰中的各類別對測試樣本進行重構,重構誤差最小的類別作為測試樣本的預測標記,計算式為

(6)

2 IPAL算法的改進

文獻[9]的算法IPAL在求取近鄰樣本的權值、構建相似度圖的過程中,采用近鄰樣本重構其對應樣本的方法構建目標函數(shù),將其問題轉化為了有約束的最小二乘問題,但因訓練集和測試集的每個樣本需要處理有約束的最小二乘問題,耗時太多.為了解決該問題,文中提出了一種基于近鄰距離加權的偏標記學習方法WIPAL.

鑒于IPAL算法中求取樣本K近鄰時已經(jīng)求得了樣本與其對應近鄰樣本之間的距離,根據(jù)樣本之間距離越近、其類別相同概率就越大的思想,文中充分利用其已獲得的近鄰樣本距離,將其近鄰樣本距離的倒數(shù)除以所有近鄰樣本的倒數(shù)之和所得的值作為近鄰樣本的權值,計算式為

(7)

式中Li,j為樣本xi和xj之間的距離.處理有約束的最小二乘問題常采用迭代的方法,其時間復雜度為O(tpK(m+n)),式中p為樣本特征數(shù),K為近鄰樣本數(shù),m和n分別為訓練集和測試集樣本數(shù),t為迭代次數(shù);基于近鄰距離求取近鄰權值的方法只需要對近鄰樣本的距離進行遍歷就可獲得其近鄰權值,其時間復雜度為O(pK(m+n)).顯然該方法的運算速度比文獻[9]中處理有約束最小二乘問題獲得近鄰權值的方法快了很多.

3 并行算法PWIPAL

并行算法PWIPAL主要由讀入訓練集和測試集、構建訓練集相似度圖、迭代標記傳播、讀取測試集數(shù)據(jù)、構建測試集相似度圖和測試樣本預測等組成.

3.1 讀入訓練集和測試集

3.2 構建訓練集相似度圖

首先,開設c個進程,訓練集特征D=[D0,D1,…,Dc-1],其中Di為第i個進程存儲的訓練集特征.每個進程采用輪詢的通信方式將保存的訓練集特征傳播給相鄰的進程,具體通信方式見圖1,以4個進程為例,圖1中方塊中的數(shù)字表示進程號,箭頭上的數(shù)字表示傳播的訓練集特征對應的進程號.

然后求取其進程自身保存的訓練集樣本特征與通信收到的訓練集樣本的歐式距離,保存K個最近的距離和其對應距離的索引,重復c-1次,每個進程就獲得了訓練集樣本相對于整個訓練集的K近鄰,K近鄰的索引存入各自的N中,其中N=[N0,N1,…,Nc-1].接著每個進程根據(jù)各自的樣本及該樣本對應近鄰的距離,使用式(7)求得近鄰樣本的權值,將其存入W中.接著每個進程分別對對應的權值置信度矩陣進行量綱一化處理,結果保存到H中,量綱一化的方式是每個樣本所對應的近鄰的權值除以該樣本對應的所有近鄰的權值之和,即

(8)

圖1 輪詢通信方式

3.3 迭代標記傳播

3.3.1 迭代標記傳播中計算改寫

文獻[9]在標記迭代傳播的部分中,為了更新樣本的標記置信度,需要計算權值矩陣乘以標記置信度矩陣,即式(3)中的HTF(t-1),原文中H是m×m的二維數(shù)組,其中H中每行最多有K個數(shù),其余全部是0,K為近鄰數(shù),因此HTF(t-1)中有多處0與數(shù)相乘,造成了極大的計算資源浪費.一般的實現(xiàn)代碼常使用稀疏矩陣來存儲和計算,文中采用與稀疏計算類似的方法,用H來存儲樣本近鄰的權值,這樣H中每一行都有數(shù)值,不再稀疏;然后HTF(t-1)即樣本的近鄰權值與近鄰對應的標記相乘然后求和,所以式(3)可改為

(9)

式中:hi,k為H中第i行第k列的元素;Ni,k為第i個樣本的第k個近鄰的索引.

3.3.2 并行迭代標記傳播

首先,對于每個進程(以第i個進程為例)令訓練集標簽矩陣Pi=Yi,其中Yi為第i個進程的訓練集標簽.對Pi進行量綱一化處理,其方法與式(8)類似.令Fi=Pi,其中Fi為第i個進程的迭代標簽置信度矩陣.

替代是翻譯漢語文化負載詞的一種有效方法。許多漢語諺語和典故在英語讀者的認知系統(tǒng)中不存在，但它們可能有相似的表達方式。因此，譯者可以找到一種相似的表達方式代替原有表達方式，從而達到更好的認知效果。

然后,每個進程根據(jù)式(9)和(4)進行標簽置信度矩陣F的更新,如第i進程對Fi進行更新,在更新過程中采用輪詢的通信方式,每個進程將自身的標簽矩陣發(fā)送給相鄰的進程,重復c-1次,對于整個更新過程重復迭代T次.

3.4 構建測試集相似度圖

此部分采用與3.2節(jié)相同的方式構建相似度圖,在其過程中每個進程保存了其樣本對應的近鄰樣本的特征信息.

3.5 測試集樣本的預測

每個進程采用輪詢的通信方式將各自的訓練集標簽信息發(fā)送給相鄰的進程,進而每個進程獲得自身訓練樣本對應近鄰樣本的標簽信息.接著每個進程分別使用各自測試樣本的K近鄰中各類別的特征根據(jù)式(6)對測試樣本進行重構,重構誤差最小的類別作為測試樣本的真實類別.

通過對算法的分析得知并行算法PWIPAL算法的通信時間復雜度為O((2np+Tq)(c-1)/c),計算時間復雜度為O((n2p+nK(p+Tq)+mpK(n+1+q))/c),其中n和m為訓練樣本數(shù)和測試樣本數(shù),p為特征數(shù),q為標簽數(shù),K為近鄰數(shù),T為迭代數(shù),c為進程數(shù);串行WIPAl算法的計算時間復雜度為O(n2p+nK(p+Tq)+mpK(n+1+q)).顯然當n越來越大時,計算量比通信量增長速率高;當n無限大時通信量忽略不計,即開設c個進程,并行算法PWIPAL的運行速率比串行算法WIPAL快c倍,而且并行算法每個進程耗費的內存為串行算法的1/c,由此可見,PWIPAl算法可以處理大規(guī)模數(shù)據(jù).

PWIPAL算法偽代碼見下面,其中,Dr和Yr分別為第r個進程分到的訓練集樣本特征和標簽.

過程:

每個MPI進程r∈0,1,…,c-1啟動

讀取Dr,Yr

根據(jù)歐式距離和自身訓練集特征獲得Dr中每個樣本的K近鄰

Forj=1 toc-1 do

采用輪詢通信方式,將Dr傳播給其他進程,接收其他進程傳遞的訓練集特征

根據(jù)現(xiàn)有的K近鄰信息和收到的其他進程訓練集特征更新Dr中每個樣本的K近鄰

End for

根據(jù)式(9)計算Dr的近鄰權值矩陣Wr

根據(jù)式(8)對近鄰權值矩陣Wr進行量綱一化處理

根據(jù)式(2)初始化標簽置信度矩陣Pr

對Pr進行量綱一化處理,令Fr(0)=Pr

Fort=1 toTdo

Fori=0 toc-1 do

輪詢通信方式將Fr傳播給其他進程,獲得其他進程的迭代標簽置信度矩陣

根據(jù)式(9)和式(4)迭代更新Fr

End for

End for

根據(jù)式(5)和Fr對訓練集樣本進行消歧

Forj=1 toc-1 do

采用輪詢通信的方式,將Dr傳播給其他進程,獲得其他進程的訓練集特征

End for

Fori=0 toc-1 do

通過輪詢通信的方式,將Yr傳播給其他進程,同時獲得其他進程的訓練集標簽

根據(jù)測試集樣本的近鄰索引,獲得每個測試樣本的近鄰標簽

End for

關閉所有的MPI進程

4 試驗與結果

4.1 數(shù)據(jù)集

使用8個不同規(guī)模的UCI數(shù)據(jù)集和5個真實數(shù)據(jù)集進行對比試驗,其中UCI數(shù)據(jù)集經(jīng)過人工處理轉換為偏標記數(shù)據(jù)集.將UCI數(shù)據(jù)集構造成偏標記數(shù)據(jù)集的處理方法如下:根據(jù)文獻[5-6,8,16],使用參數(shù)p,r,ε控制生成的數(shù)據(jù)集,其中參數(shù)p控制數(shù)據(jù)集中偏標記訓練樣本的比例,參數(shù)r控制每個偏標記樣本的偽標記個數(shù),ε控制1個額外的偏標記與真實標記共同發(fā)生的概率.具體數(shù)據(jù)集信息見表1.

表1 數(shù)據(jù)集信息

4.2 試驗環(huán)境

文中的并行試驗在由8臺服務器搭建的MPI集群上進行,串行試驗在集群中的1臺服務器上進行,集群中每臺服務器的環(huán)境配置都如下:Cathe為15 MB,RAM為64 GB,Clock speed為2.0 Hz,CPU核心數(shù)為6,每個core支持雙線程.操作系統(tǒng)為Centos 6.5,MPI版本號為3.1.4,GCC版本為4.4.7.

4.3 評價指標

文中將分類準確率、程序運行時間、加速比作為評價標準.其中分類準確率=預測正確的樣本數(shù)/測試樣本數(shù),加速比=串行運行時間/并行運行時間.

4.4 試驗結果與分析

本部分首先使用4個小規(guī)模的UCI數(shù)據(jù)集和5個真實數(shù)據(jù)集來驗證算法WIPAL的分類準確率.將算法WIPAL與IPAL進行對比,試驗中WIPAL和IPAL的平衡系數(shù)α=0.95,近鄰數(shù)K=10,迭代次數(shù)T=100,求取K近鄰時均采用線性掃描的方式.IPAL中使用開源庫ipopt來解決有約束的最小二乘問題,HSL選擇版本MA27.表2為UCI數(shù)據(jù)集中WIPAL與算法IPAL關于分類準確率的對比,其中ε=0表示不考慮偏標記與真實標記共同發(fā)生的概率.

表2 UCI數(shù)據(jù)集分類準確率對比 %

由表2可見WIPAL算法的分類性能與算法IPAL相比有好有壞.表3為真實數(shù)據(jù)集中WIPAL與IPAL算法分類準確率的對比,由表3可見WIPAL算法在數(shù)據(jù)集Lost和Soccer Player上分類準確率性能優(yōu)于IPAL,在其他數(shù)據(jù)集中,其分類準確率與算法IPAL相差很少.總體而言,WIPAL算法分類準確率與IPAL相當.

表4為在UCI數(shù)據(jù)集和真實數(shù)據(jù)集上算法WIPAl和IPAL關于運行時間的對比,UCI數(shù)據(jù)集的參數(shù)為r=1,p=1,其運行時間為十折交叉驗證中一折的運行時間.

表3 真實數(shù)據(jù)集分類準確率對比 %

表4 運行時間 s

由表4可見在相同數(shù)據(jù)集的情況下，WIPAL算法運行時間較短,真實數(shù)據(jù)集的最后2個數(shù)據(jù)集中IPAL與WIPAL運行時間相差比例較小是因為這兩個數(shù)據(jù)集比較大,IPAL和WIPAL計算每個樣本近鄰耗費的時間占據(jù)了總運行時間很大部分.為了測試并行算法PWIPAL的運行效率,文中選取了4個樣本數(shù)規(guī)模從2萬到90多萬的UCI數(shù)據(jù)集,控制參數(shù)是r=1,p=1,通過設置不同的進程數(shù)進行對比試驗,其運行時間為十折交叉驗證中一折的運行時間,見表5,其中c為進程數(shù).

表5 算法PWIPAL不同進程時的運行時間和加速比

由表5可見,對于數(shù)據(jù)集gas,當進程數(shù)由1增長為64的過程中,算法PWIPAL的運行時間逐漸縮短,由原來的18 677.41 s變?yōu)榱?89.82 s,加速比由1.00變?yōu)榱?7.91,根據(jù)數(shù)據(jù)集不變,進程數(shù)增加時，算法PWIPAL的運行時間和加速比可以看出對于相同的數(shù)據(jù)集,隨著開設進程數(shù)的增多,PWIPAL的運行時間逐漸減少,加速比逐漸增多.根據(jù)數(shù)據(jù)集的不同規(guī)模可以看出,隨著數(shù)據(jù)集規(guī)模的變大,在相同進程數(shù)時加速比在增多,例如當進程數(shù)為8時,數(shù)據(jù)集的加速比按照數(shù)據(jù)集規(guī)模遞增的順序逐漸增大.表中數(shù)據(jù)集shuttle在64個進程時運行時間變多是由于此時單個進程計算時間的減少量低于通信時間的增加量引起的.

5 結 論

首先對偏標記算法IPAL進行改進,提出了基于近鄰距離加權的WIPAL算法;然后為了處理大規(guī)模數(shù)據(jù),進一步提出了WIPAL的并行方法PWIPAL.在不同數(shù)據(jù)集下將WIPAL與IPAL的運行時間和分類準確率進行對比,得知WIPAL的分類準確率與IPAL相當,但運行效率要高于IPAL;然后在不同規(guī)模數(shù)據(jù)和不同進程數(shù)的情況下對PWIPAL的運行時間和加速比進行對比,驗證了該并行算法的高效性,其可用來處理大規(guī)模數(shù)據(jù).