《TOP20: Multi-Label Learning Algorithms（一）<簡述>》

論文：《A Review on Multi-Label Learning Algorithms》

src：IEEE

摘要：通常我們學習的標籤演算法都是一個例子對應於一個標籤，例如中文分詞、命名實體識別等，而多標籤學習是一個例子對應於一個標籤集合。本文在三個方面對近年來的多標籤學習演算法進行綜述，

1.多標籤學習演算法的原理，包括正式定義與評估準則；

2.分析和討論八個代表性的多標籤學習演算法；

3.總結相關學習設置。

任務簡介：傳統的監督學習，都是先將一個example表示為一個例子，例如feature vector，然後關聯於單個標籤，即表示例子空間，表示標籤空間，目標是學習函數， 訓練集為。表示特徵，表示語義標籤。它假設每個例子都對應於一個獨一無二的語義概念。

而多標籤學習則意味著一個例子對應於多個標籤。例如文本分類中，一個文件可能包括 "sport" 、"London Olympics"、"torch relay"等主題。這個問題的解決方法之一是直接的去安排一個標籤集合來表達該example的語義。我們將會去學習一個函數來預測正確的標籤集合。

範例：首先介紹多標籤學習演算法中形式定義。

1）學習框架：多標籤學習演算法常用的數學標記如圖：

多標籤學習演算法的符號定義為：

對於例子空間和標籤集合,從訓練集學習一個函數，（對於每個例子，有和）令為的正確標籤集。

針對多標籤數據集的性能，我們有幾個常規的指示函數來描述其特性：

標籤基數：;標籤密度：，標籤多樣性：，歸一化多樣性：。

在我們的實現多標籤演算法中，分類函數的實現是依靠一個實值函數，可以理解為是的正確標籤的信任值。對於一個多標籤例子，其中表示相關標籤，表示無關標籤，應該有。這樣我們就能定義分類函數

，其中是閾值函數，把標籤歸入相關或不相關集。

2）主要挑戰：正如上文中提到的，多標籤演算法的輸出空間維度為2的指數形式，意味著當處理大量數據時，例如如果標籤集合的維度20，那麼每個例子的可能輸出空間的維度即為，是非常巨大的。為了解決這個問題，我們的解決辦法是發現標籤之間的相關性或依存關係。例如如果一個例子有標籤「巴西」，那麼它也有很大的概率有標籤「熱帶雨林」、「足球」。目前主要的方法可以歸為三類，依據相關性的順序：

·First-order：忽略標籤相關性，label-by-label處理；

·Second-order：處理成對關係的標籤。

·High-order：考慮標籤集中所有詞的相關性。

每個策略的詳細內容我們在具體演算法中考慮。

另外對於閾值函數的設置，我們既可以將其設為固定值，例如0.5。也可以通過訓練集得到：

。其中參數通過最小化函數：

，其中為使錯誤標籤集最小的閾值。

其次我們介紹多標籤學習演算法的評價指標，大體分為兩種：基於輸入實例指標和基於標籤的指標。如圖所示：

這些評價指標不僅限於本任務，大多數標籤任務都可以用這些指標。我們來一一介紹。

①基於實例的指標：

1.子集準確率：，其中[[ ]]為指示函數。

2.Hamming Loss：，其中返回兩個集合的不同元素。

3.

4.One-error：

5.Coverage：，即統計每個樣本的標籤rank最低的值的平均。

6.Ranking Loss：

7.Average Precision:

②基於標籤的指標：首先介紹幾個重要的標籤集合：

其中為分類函數。令為二分類評價指標，其中。有兩種計算模式：

ps:和基於例子的計算方式相比其實只是順序不同而已。

另外還有Area under the ROC curve(AUC)指標，符號定義為：

其中，。

3)理論結果：

現有的演算法大都針對某一個特定的指標進行優化。然而為了得到更好的評估，同時需要對多種指標進行測試，而不僅僅是用優化的指標。現在的研究發現用最大化子集準確率來優化的模型在hamming loss中評估較差。

本文還指出由於多標籤指標是非凸的和不連續的，在實踐中演算法要去優化凸surrogate指標。並且描述了ranking loss最小化有其特殊的一致性優勢。

總結：本文為多標籤學習演算法綜述的第一部分，主要目的在介紹本任務的內容、符號定義及評價標準，後續將繼續更新具體的演算法模型等。

推薦閱讀：