基于三元糾錯輸出編碼的偏標記學習算法*

周斌斌，張敏靈+，劉胥影

1.東南大學 計算機科學與工程學院，南京 210096

2.東南大學 計算機網絡和信息集成教育部重點實驗室，南京 210096

1 引言

偏標記學習（partial label learning）是一類重要的弱監督學習（weakly supervised learning）框架，在該框架下，每個訓練樣本在輸入空間由單個示例（特征向量）描述，而在輸出空間與一組候選標記集合（candidate label set）相關聯，其中有且僅有一個是其真實標記[1-2]。偏標記學習的目標是學習一個從輸入空間到輸出空間的多類分類器。最近幾年，偏標記學習技術已經廣泛應用于真實世界的問題中，例如文本挖掘[3]、圖片分類[4]、生態信息學[5]等領域。

偏標記學習框架的形式化定義如下。設X=Rd代表樣本特征空間，Y={y1,y2,…,yq}代表樣本標記空間。給定偏標記訓練集D={(xi,Si)|1≤i≤m}，其中xi∈X為d維特征向量，Si?Y為xi的候選標記集合，xi的真實標記yi未知但滿足條件yi∈Si。偏標記學習目標是基于訓練集D學習得到多類分類器f:X→Y。

偏標記學習的難點在于樣本的真實標記隱藏在候選標記集合中，樣本的真實標記無法獲得。目前解決這個問題的基本策略是消歧。消歧思想是消除偏標記對象候選標記中偽標記引起的歧義性?，F有的消歧策略算法主要包括基于辨識的消歧（disambiguation of identification-based）和基于平均的消歧（disambiguation of averaging-based）。基于辨識的消歧將樣本的真實標記當作隱變量，通過迭代方式優化內嵌隱變量來實現消歧?；谄骄南鐚ζ珮擞洏颖镜母鱾€候選標記賦予相同的權重，通過綜合學習模型在各候選標記上的輸出來實現消歧[1,6-7]。

然而，基于消歧的偏標記學習技術很大程度上會受到偽標記（即Si?{yi}）帶來的不利影響。為了緩解這個不利影響，Zhang提出了一種基于糾錯輸出編碼（error-correcting output codes，ECOC[8-9]）的非消歧策略的偏標記學習算法PL-ECOC[10]（partial labelerror-correcting output codes），該方法將多類分類技術糾錯輸出編碼應用到偏標記學習中，通過編碼的方式將偏標記學習問題轉換為多個二類學習問題，然后對多個二類分類器集成得到最終的分類器。

很明顯，候選標記數目越多，偏標記對象的偽標記信息就會越多，偏標記學習問題的難度越大，從而不利于偏標記問題的學習。因此可以通過減少候選標記的數目來降低偏標記學習的難度，從而有利于偏標記問題的學習。本文從該角度出發，提出了一種基于三元糾錯輸出編碼的偏標記學習算法（partial labelternary error-correcting output codes，PL-TECOC），該算法類似于但不同于PL-ECOC且能獲得較好的分類性能，PL-TECOC算法采用三元編碼方式，即使用{+1,-1,0}進行編碼，在將偏標記學習問題轉換為多個二類學習問題的過程中，編碼“0”用于忽略相應的標記，只依靠非“0”標記完成二類學習問題訓練數據的構建，從而減少候選標記個數以降低偏標記學習問題的難度。

本文的組織結構如下：第2章介紹偏標記學習的相關工作；第3章介紹本文提出的PL-TECOC算法；第4章是實驗部分，最后對本文進行總結和展望。

2 相關工作

目前，關于偏標記學習的算法主要分為基于辨識的消歧策略、基于平均的消歧策略以及基于非消歧的策略。

基于辨識的消歧策略，現有方法將真實標記當作隱變量，然后通過迭代方式優化內嵌隱變量的目標函數來達成消歧。首先假設一個特定的參數模型F(x,y;θ)（θ為模型參數），然后把真實標記當作隱變量并且根據式子y?i=argmaxy∈SiF(xi,y;θ)來確定真實標記，最后通過EM[11-12]算法（expectation maximization algorithm）或其他算法來優化基于最大似然準則函數或來優化基于最大化間隔的準則函數定義的目標函數來迭代改良隱變量（真實標記）。

基于平均的消歧策略，現有方法對偏標記樣本的各個候選標記賦予相同的權重，通過綜合學習模型在各候選標記上的輸出來實現消歧。常見方法包括基于k近鄰的偏標記方法，該方法通過對樣本近鄰的候選標記集合進行加權投票來預測樣本的類別標記，即，其中 I(·)為指示函數，N(x*)為樣本x*的近鄰。基于凸優化的偏標記學習方法通過最小化偏標記樣本在候選標記集合上經驗損失（由決定）以及在非候選標記集合上的經驗損失（由F(x,y;θ)y?Si決定）[1]來進行偏標記學習。

以上是消歧策略，Zhang近年來提出了一種全新的非消歧策略算法PL-ECOC，它將多類學習的糾錯輸出編碼應用到偏標記學習中，通過編碼的方式將偏標記學習問題轉換為多個二類學習問題，最后對多個二類分類器集成以得到最終的學習器。

3 基于三元糾錯輸出編碼的偏標記學習算法

偏標記學習的任務是學習一個多類分類器f:X→Y，本質上這是一個多類學習問題。在傳統監督學習框架下，解決多類學習問題一種常見方式就是將多類學習問題分解為多個二類學習問題進行求解。常見的分解方式有一對一（one-vs-one）、一對多（one-vs-rest）和糾錯輸出編碼（ECOC），在偏標記學習問題中，由于訓練樣本的真實標記未知，無法直接使用一對一和一對多的分解策略，而糾錯輸出編碼可以多對多，因此可用為分解策略。

本文提出的PL-TECOC算法旨在通過減少候選標記的數目來降低偏標記學習的難度。它對基于二元編碼的PL-ECOC算法進行擴展，采用三元編碼方式，即使用{+1,-1,0}進行編碼。在將偏標記學習問題轉換為多個二類學習問題的過程中，編碼“0”用于忽略相應的標記，只依據非0標記完成二類學習問題訓練數據的構造，從而減少候選標記個數以降低偏標記學習問題的難度。PL-TECOC算法主要分為編碼和解碼階段。

在編碼階段，首先隨機生成一個編碼矩陣M∈{+1,0,-1}q×L，其中q為類別標記個數，L為編碼長度。編碼矩陣M的每一行即M(j,:)是類別yi的一個L位編碼字，矩陣的每一列M(:,?)=σ=[σ1,σ2,…,σq]T代表q位的列編碼，其中 [σ1,σ2,…,σq]T∈{+1,0,-1}q，它根據式（1）將標記空間Y={y1,y2,…,yq}劃分為3個部分

根據式（2）得知，對于偏標記訓練集的每個樣本xi，如果其候選標記集合包含于組成的并集合中且與的交集不為空時，則將該樣本歸為正類樣本；如果其候選標記集合包含于組成的并集合中且與的交集不為空時，則將該樣本歸為負類樣本，否則丟棄該樣本。這樣偏標記訓練集中的部分樣本可能既不屬于也不屬于因此，為了避免二類訓練集樣本數過少的問題，PL-TECOC設置一個閾值τ來減少其影響，即二類訓練集大小須要大于等于閾值τ。此外構建的二類訓練集存在類別不平衡問題，即一類樣本明顯少于另一類樣本。PLTECOC設置閾值υ來解決這個問題，即二類訓練集中兩類樣本數比例須小于等于參數υ。

在解碼階段，類似于ECOC的解碼，將未知樣本x*預測為其編碼字h(x*)與標記編碼字最近的標記，見式（3）。

其中h(x*)=[h1(x*),h2(x*),…,hL(x*)]，關于如何計算h(x*)具體見算法1的算法偽碼。dist(·,·)為距離函數，針對三元解碼，常見的方式有減弱的歐式解碼（attenuated Euclidean decoding，AED）、基于損失的解碼（lossbased decoding）以及基于概率的解碼（probabilisticbased decoding）等方式[15]。PL-TECOC采用減弱的歐式解碼，其定義為：

PL-TECOC算法不同于PL-ECOC，主要體現在以下兩方面：（1）本算法采用三元編碼方式將偏標記學習問題轉換為多個二類學習問題，編碼“0”用于忽略相應的標記，只依據非0標記完成二類學習問題訓練數據的構造，從而減少候選標記個數以降低偏標記學習問題的難度。（2）在構建的二類訓練集存在類別不平衡問題，本算法通過設置一個閾值τ來減少其帶來的影響。

算法1PL-TECOC算法

輸入：D={(xi,Si)|1≤i≤m}為偏標記訓練集，L為編碼長度，Ψ為二類分類器，τ為二類訓練集大小的閾值，υ為二類訓練集不平衡比例的閾值，x*為測試樣本。

輸出：y*為樣本x*的預測標記。

訓練

1.?=0

2.While?≠L

3. 隨機生成q位的列編碼σ=[σ1,σ2,…,σq]T∈{+1,0,-1}q

5.根據式（2）將偏標記訓練集D={(xi,Si)|1≤i≤m}轉換為二類訓練集Bσ

6. If|Bσ|≥τ并且

7. ?=?+1

8. 令M(:,?)=σ

9.基于二類訓練集Bσ學習一個二類分類器即h?←Ψ(Bσ)

10. End If

11.End While

測試

12.根據訓練階段學習的二類分類器得到樣本x*的編碼字h(x*)=[h1(x*),h2(x*),…,hL(x*)]

13.根據式（3）得到測試樣本x*的標記y*=f(x*)

4 實驗及實驗結果

4.1 實驗設置

本文在人工數據集[16]和真實數據集上分別進行了實驗。數據集信息分別見表1和表2，包括樣本數、屬性數、類別數，另外真實數據集還給出了樣本的平均候選標記集合大小。

Table 1 UCI datasets表1 人工數據集

對于人工數據集，根據常用的設置方法[1,5,10]，通過控制ρ、r、ε這3個參數從多類數據集中生成人工偏標記數據集，其中ρ控制偏標記訓練樣本的比例（即|Si|＞1），r控制候選標記中偽標記的個數（|Si|=r+1），ε控制一個額外候選標記y′≠y與真實標記y同時出現的概率。由表1可見，對于每個人工數據集，總共有28（4×7）個參數設置，于是生成28組不同設置的偏標記數據集。

對于真實數據集，Lost[1]、Soccer Player[4]、LYN（Labeled Yahoo!News）[17]數據集來自于自動人臉識別，MSRCv2[5]數據集來自于目標分類，BirdSong[18]數據集來自于鳥類音節分類。對于自動人臉識別任務，將圖片或視頻上出現的人臉作為示例，然后從標題或字幕上抽取的人名作為候選標記，特別地，保留LYN數據集出現數目最多的Num（Num∈{10,20,50,100,200}）個人物名字作為標記空間，這樣可以生成5個版本的LYN數據集，數據集命名為LYN Num。對于目標分類，MSRCv2數據集包括23個類別的1 758個圖像分割區域，每個圖分割區域代表一個示例，而其候選標記集合為出現在同一圖像的所有對象類別。對于鳥類音節分類，BirdSong數據集將鳥叫聲的音節作為一個示例，而將出現在音節10 s期間的鳥類當作候選標記集合。

Tabel 2 Real-world datasets表2 真實數據集

為了驗證提出算法的有效性，本文將和以下幾個常用的偏標記學習算法進行對比。

（1）基于k近鄰的偏標記學習算法PL-KNN（partial labelknearest neighbor）[6]：一種基于平均消歧策略的偏標記學習算法，參數k設置為10。

（2）基于凸優化的偏標記學習算法CLPL（convex learning from partial labels）[1]：一種基于平均消歧策略的偏標記學習算法，二類分類器采用基于L2正則化鉸鏈損失（hingeloss）的SVM算法，使用Liblinear工具包實現。

（3）基于最大間隔的偏標記學習算法PL-SVM（partial label support vector machine）[14]：一種基于辨識策略的偏標記學習算法，正則化參數從{10-3,10-2,…,103}這個范圍內選擇，使用線性核。

（4）基于最大似然的偏標記學習算法LSB-CMM（logistic stick-breaking conditional multinomial model）[5]：一種基于辨識策略的偏標記學習算法，其中混合成分個數設為q（即類別標記個數）。

（5）基于非消歧策略的偏標記學習算法PLECOC[10]：編碼長度設，二類訓練集大小閾值設為

對于PL-TECOC算法，二類基分類器采用Libsvm[19]工具箱實現的支持向量機，二類訓練集大小閾值參數τ設為偏標記訓練集大小的1/10，即，編碼長度設為，二類訓練集不平衡的比例閾值υ設為4。在本文中，對于人工數據集和真實數據集均采用10倍交叉驗證實驗，并記錄各對比算法的準確率以及標準差。

4.2 人工數據集實驗

圖1到圖3展示了PL-TECOC和各種對比算法分別在r=1,2,3，ρ以步長0.1從0.1到0.7變化時的分類準確率。圖4展示了PL-TECOC和各種對比算法在ρ=1,r=1，ε以步長0.1從0.1到0.7變化時的分類準確率。（a）～（d）分別是4個數據集上對應的結果圖。

圖1到圖4表明在所有情況下PL-TECOC的性能優于或持平于其他對比算法?；陲@著程度為0.05的成對t檢驗，表3給出了在4個數據集上所有設置情況下PL-TECOC優于/持平/劣于其各對比算法的次數。從表3可以得出以下結論：

（1）在所有參數設置下的人工數據集上，對比算法的性能劣于PL-TECOC。

Tabel 3 Win/tie/loss counts on classification performance of PL-TECOC against each compared algorithm表3 PL-TECOC分類性能優于/持平/劣于其他對比算法的次數統計

Fig.1 Classification accuracy of each compared algorithm under configurationr=1,ρ∈{0 .1,0.2,…,0.7}圖1 對應設置為r=1,ρ∈{0 .1,0.2,…,0.7}時各種算法的分類準確率

Fig.2 Classification accuracy of each compared algorithm under configurationr=2,ρ∈{0 .1,0.2,…,0.7}圖2 對應設置為r=2,ρ∈{0 .1,0.2,…,0.7}時各種算法的分類準確率

Fig.3 Classification accuracy of each compared algorithm under configurationr=3,ρ∈{0 .1,0.2,…,0.7}圖3 對應設置為r=3,ρ∈{0 .1,0.2,…,0.7}時各種算法的分類準確率

Fig.4 Classification accuracy of each compared algorithm under configuration ρ=1,r=1,ε∈{0.1,0.2,…,0.7}圖4 對應設置為 ρ=1,r=1,ε∈{0 .1,0.2,…,0.7}時各種算法的分類準確率

（2）和基于平均消歧策略方法相比，PL-TECOC分別在83.0%和86.6%的情況下優于PL-KNN和CLPL。

（3）和基于辨識消歧策略方法相比，PL-TECOC分別在100.0%和76.7%的情況下優于PL-SVM和LSB-CMM。

（4）和非消歧策略方法相比，PL-TECOC基本上與PL-ECOC持平。

4.3 真實數據集實驗

基于顯著程度為0.05時的成對t檢驗，表4給出了在真實數據集上PL-TECOC和各對比算法的性能表現。從表4可以看出：

（1）在MSRCv2數據集上，PL-TECOC算法性能優于其他所有對比算法。

（2）在LYN100和LYN200數據集上，PL-TECOC持平于PL-ECOC，優于其他對比算法。在LYN20數據集上，PL-TECOC持平于LSB-CMM，優于其他對比算法。在BirdSong數據集上，PL-TECOC持平于PL-ECOC和LSB-CMM，優于其他對比算法。

（3）在Lost數據集上，PL-TECOC劣于CLPL和PL-SVM，優于PL-KNN，持平于其他對比算法。在Soccer Player數據集上，PL-TECOC劣于PL-ECOC和LSB-CMM，優于CLPL，持平于其他對比算法。

（4）在LYN50數據集上，PL-TECOC劣于LSBCMM，優于其他對比算法。

4.4 算法的參數敏感性分析

對PL-TECOC算法關于參數υ及L的敏感性進行了分析，圖5展示了PL-TECOC算法性能在不同參數設置下的變化情況。本文選擇了Lost、MSRCv2、BirdSong 3個數據集來進行參數的敏感性分析，對于其他的數據集也有類似的觀察結果。圖5（a）表示PL-TECOC隨著以步長10改變時分類準確率的變化。圖5（b）表示PL-TECOC隨著υ從3到7以步長1改變時分類準確率的變化。

Table 4 Classification accuracy of each algorithm on real-world datasets表4各算法在真實數據集上的分類準確度

Fig.5 Parameter sensitivity analysis for PL-TECOC on Lost,MSRCv2 and BirdSong datasets圖5 PL-TECOC在Lost、MSRCv2、BirdSong 3個數據集上的參數敏感性分析

由圖5可見：對于參數L，PL-TECOC性能先提高后趨于穩定。對于參數υ，PL-TECOC性能先呈現下降趨勢，最終趨于穩定?？偟膩碚f，參數υ對于算法性能影響明顯，因此對于該參數的選擇非常重要。

5 總結與展望

為了減少候選標記的數目以降低偏標記學習的難度，本文提出了一種基于三元糾錯輸出編碼技術的偏標記學習方法PL-TECOC。實驗表明該算法在人工數據集和真實數據集上均表現良好的性能。

PL-TECOC算法的一個潛在缺點是在構建二類訓練集時一些偏標記訓練樣本會被剔除（見算法1步驟5），未來工作方向之一是如何有效地利用這些被踢除的偏標記樣本。另外，如何設計更好的編碼方式來解決偏標記學習問題也是一個值得研究的方向。