基于間隔準則的優化排序多標記學習算法

金亞洲,張正軍,顏子寒,王雅萍

(南京理工大學 理學院,南京 210094)

0 概述

目前,針對多標記學習分類問題的多標記學習算法可大致分為問題轉換方法和算法適應方法2類[5-6]。問題轉換方法解決此類問題的思想是對多標記學習訓練樣本數據進行處理,將該問題轉化為已知的學習問題,例如一個或多個單標記問題或者回歸問題。算法適應方法解決此類問題的思想是對已有的傳統監督學習算法進行改進或擴展,使其能夠適應多標記數據的學習。

在問題轉化方法的研究中,BR(Binary Relevance)算法[3]較簡單,該算法將多標記學習問題轉化為若干個獨立的二分類問題,其計算復雜度較低,但由于忽略了標記之間內在的相關信息,因此泛化性能較差。分類器鏈(Classifier Chain,CC)算法[7-8]在BR算法的基礎上,將獨立的二分類器進行串聯形成一條鏈,該算法考慮了標記之間的相關性等信息,但鏈表順序直接影響最終的分類效果,且其考慮的相關性信息有時并不符合樣本數據的標記本質相關性信息,文獻[7]利用CC算法的集成框架ECC來緩解由隨機確定鏈表順序帶來的不利影響。LP(Label Power-set)算法[9]是一種標記組合算法,其基本思想是將多標記數據集中每個唯一的標記集合均作為一個整體標記,訓練和預測過程中的輸入和預測輸出均為一個整體標記,多標記學習問題即被轉化為一個單標記多分類問題。但是,當標記空間較大時,LP算法的訓練樣本數據中標記集合對應的示例數量較少,會引起類不平衡問題,進而影響分類效果。

在算法適應方法的研究中,Rank-SVM算法[10-11]通過對傳統的SVM算法[12]進行擴展,采用最大化間隔策略,通過一組線性分類器來最小化排序損失評價指標,并引入“核技巧”來處理非線性多標記問題。BP-MLL(Back-Propagation Multi-Label Learning)算法[13-14]基于經典的反向傳播(Back-Propagation,BP)算法,通過采用一種新的誤差函數從而適應于多標記問題,并使用梯度下降法更新網絡中的參數。ML-KNN方法[15-16]基于傳統的KNN方法,根據測試集中每個示例與訓練集樣本的相似度來確定其K個近鄰,并通過最大后驗概率(MAP)原理來預測樣本的標記集合。

本文基于間隔準則提出2種優化的多標記學習算法,兩者均可歸納為算法適應方法。第1種算法通過優化模型在相關標記集合中最小輸出與不相關標記集合中最大輸出的間隔損失來進行標記排序。考慮到該算法對標記信息利用不足的問題,第2種算法不僅優化上述間隔損失,同時還優化模型在相關標記集合中平均輸出與不相關標記集合中最大輸出的間隔損失,以及優化模型在相關標記集合中最小輸出與不相關標記集合中平均輸出的間隔損失,從而進行標記排序。上述2種算法均采用改進的次梯度Pegasos算法[17-18]進行參數學習,以提高分類效果。

1 相關工作

1.1 間隔準則

本文算法以基于間隔準則的多分類算法[19-20]為基礎。在多分類算法中,令L={(x1,y1),(xn,yn)}表示訓練集,其中,yi屬于有限數目的類別集合,該算法的目標為最小化正則化經驗風險損失,即:

(1)

(2)

其中,Ω(·)為正則項,其是一個單調增凸函數,L(·)用于計算模型在訓練樣本數據上的經驗風險,λ為平衡參數,用于平衡模型正則項與經驗損失對目標函數的影響。多分類支持向量機(multiclass-SVM)利用模型參數的L2范數作為正則項,即:

(3)

在經驗損失設置上,損失函數l(xi,yi,w)被設置為鉸鏈損失,即:

(4)

其中,Φ(·,·)為一個映射函數,其將每一個示例-標記對(x,y)映射為:

(5)

其中,Ι(·)為指示函數。在multiclass-SVM中引入松弛變量ξi,式(1)最小化問題可以轉化為:

s.t.

?(xi,yi)∈L

ξi≥0

(6)

1.2 Pegasos算法

傳統二分類支持向量機問題的學習任務均被轉化為有約束的二次規劃問題,該問題的最初形式為無約束、帶有懲罰項的經驗損失最小化問題,且損失函數通常選擇鉸鏈損失,可用如下的優化模型表示:

(7)

l(w;(xi,yi))=max(0,1-yi〈w,xi〉)

(8)

其中,〈w,xi〉表示向量w和xi的內積。

Pegasos算法是隨機梯度下降方法在解決上述問題時的一個應用,該算法不需要轉化為對偶形式進行求解,直接在原始的目標函數上通過選取合適的步長并采用隨機梯度下降方法對參數進行學習。Pegasos算法主要分為梯度下降和投影2個階段,其主要思想如下:

在模型參數的初始值設置時,令w1=0,設置迭代輪數為T,在Pegasos算法的每輪迭代t中,隨機選取一個訓練樣本(xit,yit),將選取的訓練樣本近似代替式(7)所表示的目標函數,如下:

(9)

上述近似目標函數的次梯度可用下式表示:

(10)

其中,I[yit·〈wt,xit〉<1]為指示函數。更新wt+1/2←wt-ηtt,步長ηt=1/(λt),更新后的模型參數可表示如下:

(11)

投影階段的模型參數更新可以表示為:

(12)

當迭代輪數達到T時,wT+1即為學習到的模型參數。

2 優化排序多標記學習算法

2.1 最小輸出與最大輸出間的間隔優化

s.t.

ξi≥0,?i∈{1,2,…,N}

(13)

在上述優化問題中,目標函數的第一項為正則項約束,用以衡量模型的復雜度,第二項為損失函數,衡量模型在不滿足約束條件時的經驗損失。約束條件度量了每個示例對象相關標記集合中最小輸出與不相關標記集合中最大輸出的間隔。

式(13)優化問題在本文中通過改進的次梯度Pegasos算法來解決,可通過梯度下降與投影2個階段實現。在每輪迭代中,隨機從訓練數據集中抽取一個樣本,判斷該樣本是否滿足式(14):

(14)

(15)

根據梯度下降策略,模型參數的更新為:

(16)

(17)

在模型的預測階段,給定未知示例對象x,模型預測出的標記集合為:

h(x)=sign(f1(x)-t(x),f2(x)-t(x),…,fq(x)-t(x))

(18)

其中,t(x)為閾值函數,本文通過文獻[10]算法,即學習一個線性回歸函數來計算t(x)。

優化最小輸出與最大輸出的間隔損失的多標記學習算法具體步驟如下:

輸入訓練數據集D,平衡參數λ,迭代終止次數T或迭代終止條件ε

輸出學習到的參數w

步驟2隨機從訓練集中抽取一個樣本,檢測該樣本是否滿足式(14)約束條件。

步驟3若不滿足約束條件,則根據式(16)和式(17)更新w;否則,根據式(19)和式(17)更新w。

wt+1/2=(1-ηtλ)wt

(19)

步驟4重復步驟2和步驟3,直到滿足判定條件‖w‖F≤ε或迭代次數大于T,終止迭代計算并輸出w。

2.2 改進的優化排序多標記學習算法

本文2.1節算法只考慮優化示例對象相關標記集合最小輸出與不相關標記集合最大輸出之間的間隔,該間隔也即距離分界面最近的標記輸出之間的差異。然而,上述算法對示例所擁有的全部標記信息利用不足,同時易出現過擬合現象,因此,本節對該算法進行改進,改進算法不僅優化上述間隔,同時優化模型在示例相關標記集合中的平均輸出與不相關標記集合中最大輸出之間的間隔,以及優化模型在示例相關標記集合中的最小輸出與不相關標記集合中的平均輸出之間的間隔。在上述模型的基礎上,再引入2個松弛變量ξ′={ξ′1,ξ′2,…,ξ′N}和υ′={υ′1,υ′2,…,υ′N}用來表示示例對象沒有滿足上述間隔要求所產生的損失,則改進模型所求解的優化問題為:

s.t.

ξi≥0,ξ′i≥0,υ′i≥0,?i∈{1,2,…,N}

(20)

從上述優化問題可以看出,當約束條件第一項成立時,第二項與第三項顯然成立;當約束條件第一項不成立時,第二項與第三項存在成立的可能性,且在算法優化過程中的初始階段,可以對全部標記所對應的模型參數進行更新,加快收斂速度。隨著迭代次數的增加,約束條件第二項及第三項在模型參數更新過程中所起的作用越來越小甚至不起作用,同時第二項及第三項約束條件可以緩和過擬合現象,該優化問題的求解同樣采用改進的次梯度Pegasos算法。

2.3 算法分析

3 實驗結果與分析

3.1 實驗設置

為了驗證本文算法的有效性,使用來自開源項目Mulan[22]所提供的4個數據集,其中,emotions來自于音樂情感分類領域,image與scene來自于自然場景分類領域,langlog來自于文本分類領域。數據集的統計信息如表1所示。

表1 實驗數據集信息

在多標記學習問題中,常用的評價指標為海明損失(Hamming Loss,HL)、排序損失(Ranking Loss,RL)、最前端錯誤率(One-Error,OE)、覆蓋率(Coverage rate,CV)和平均準確率(Average Precision,AP)。各指標具體如下:

1)HL指標考察樣本在單個標記上的誤分類情況,即對某個示例對象而言,不相關的標記被預測為相關或相關的標記被預測為不相關的情況。HL計算如下:

(21)

2)RL指標考察在樣本的語義標記排序序列中出現排序錯誤的情況。RL計算如下:

(22)

3)OE指標考察在樣本的語義標記排序序列中,序列最前端的標記不屬于樣本相關標記集合的情況。OE計算如下:

(23)

4)CV指標考察在樣本的語義標記排序序列中,覆蓋隸屬于樣本的所有相關標記所需的搜索深度。CV計算如下:

(24)

5)AP指標考察在樣本的語義標記排序序列中,排在隸屬于該樣本的相關標記之前的標記仍屬于樣本相關標記集合的情況。AP計算如下:

(25)

在分類器效果評估中,HL、RL、OE和CV 4個評價指標的指標值越小,則算法性能越優,AP評價指標的指標值越大,則算法性能越優。

3.2 結果分析

本文將提出的第1種算法表示為Proposed1,第2種算法表示為Proposed2,平衡參數λ的取值范圍為{0.001,0.01,0.1,1,10,100},將本文2種算法與現有的多標記學習算法ML-RBF[23]、BP-MLL[13]和ML-KNN[15]進行對比,實驗結果如表2～表6所示,其中,結果均為3次交叉驗證后的均值,以排除隨機性,最優結果加粗表示。

表2 海明損失結果對比

表3 排序損失結果對比

表4 最前端錯誤率結果對比

表5 覆蓋率結果對比

表6 平均準確率結果對比

從表2～表6可以看出,在4個多標記數據集中,本文提出的2種算法的5個評價指標均取得了較好的效果,與3種多標記學習算法相比,評價指標結果接近,表明本文2種算法可以實現多標記分類。實驗結果也表明,考慮相關標記集合的平均輸出與不相關標記集合的平均輸出,即本文第2種算法在5種評價指標表現上均優于本文第1種算法,表明考慮平均輸出的算法能夠提升基于間隔準則的分類器性能。

4 結束語

受基于間隔準則的多分類支持向量機的啟發,本文通過優化示例相關標記集合中最小輸出與不相關標記集合中最大輸出的間隔損失,以實現示例對應的標記集合排序。為了在模型參數訓練過程中充分利用標記空間的全部標記信息,進一步優化示例相關標記集合平均輸出與不相關標記集合中最大輸出的間隔損失,以及示例相關標記集合中最小輸出與不相關標記集合中平均輸出的間隔損失。實驗結果表明,與ML-RBF、BP-MLL和ML-KNN多標記學習算法相比,本文提出的2種算法在4個多標記數據集上均取得了相近的分類性能。本文假設訓練樣本與標記之間呈線性關系,且算法未考慮標記之間存在的相關性,下一步考慮將特征空間擴展到再生核希爾伯特空間中進行學習,并結合標記之間的相關性來提高分類效果。