多標籤（multi-label）數據的學習問題，常用的分類器或者分類策略有哪些？

01-07

多標籤（multi-label）數據常用的分類器有哪些？
多標籤（multi-label）數據常用的分類策略有哪些？

其實A Review on Multi-Label Learning Algorithms也並不長，只有19頁，而且還介紹得比較全面。

Multi-Label 和傳統的分類問題的區別主要在於多Label下，輸出空間呈現指數級增長。那麼目前對於Multi-Label的這類特性，學界一般是集中在更好的分析Label之間的相關性，就可以避免這種指數增長。

主要的Strategy大致可以分為三類：

First-Order Strategy: 考慮的是label之間相互獨立，那麼就可以把Multi-label問題轉換為普通的分類問題。如果一個Label有多類的話，那麼就用傳統的One vs All來解決。

Second-Order Strategy: 這一類是考慮Label之間的兩兩相關性，結果會導致計算複雜度有顯著的增加。

High-Order Strategy: 這個就是考慮多Label之間的相關性，計算複雜度會更高。

目前有的一些分類演算法：Binary Relevance，如名字所寫，這是一個First-Order Strategy；Classifier Chains，把原問題分解成有先後順序的一系列Binary Classification，然後前邊的Binary Classification會對後邊的產生影響；Calibrated label ranking，這個有點像Multi-Classification中One vs One的策略，就是通過兩兩對比，然後進行投票決定分類效果。

題主還是最開始提到的那篇論文吧，寫得蠻全面的。

常用分類器：meta的演算法常用分類器就是二類，多類的分類器；非meta的演算法通常是現有二類，多類分類器的改造。大部分多標記演算法主要是針對數據的特性，從機制上去優化解決這個問題，並不發明新的分類器出來。

剩下的，直接看論文吧。綜述有非常多篇了。

早期較好的：Mining multi-label data，優點：短；

現在較好的：A Review on Multi-Label Learning Algorithms，優點：長；

又一篇：A Tutorial on Multilabel Learning，優點：實踐出發，最適合你。

其他的不推介，別看了。

多標記分類和傳統的分類問題相比較，主要難點在於以下兩個方面：

(1)類標數量不確定，有些樣本可能只有一個類標，有些樣本的類標可能高達幾十甚至上百個。

(2)類標之間相互依賴，例如包含藍天類標的樣本很大概率上包含白雲，如何解決類標之間的依賴性問題也是一大難點。

對於多標記學習領域的研究，國外起步較早，起源於2000年Schapire R E等人提出的基於boost方法的文本多分類，著名的學者有G Tsoumakas、Eyke Hüllermeier、Jesse Read，Saso Dzeroski等等。在國內，南京大學的周志華和張敏靈和哈工大的葉允明等等學者在這一領域較都有很好研究成果。

目前有很多關於多標籤的學習演算法，依據解決問題的角度，這些演算法可以分為兩大類：一是基於問題轉化（Problem Transformation）的方法，二是基於演算法適應的方法和演算法適應方法（Algorithm Adaptation）。基於問題轉化的多標記分類是轉化問題數據，使之適用現有演算法；基於演算法適應的方法是指針對某一特定的演算法進行擴展，從而能夠直接處理多標記數據，改進演算法，適應數據。基於這兩種思想，目前已經有多種相對成熟的演算法被提出，如下圖所示：

問題轉化方法（Problem Transformation）：該類方法的基本思想是通過對多標記訓練樣本進行處理，將多標記學習問題轉換為其它已知的學習問題進行求解。代表性學習演算法LP[[1]]，Binary Relevance[[2]]，Calibrated Label Ranking[[3]]， Random k-labelsets[[4]]。總體來說，這類方法有考慮類標之間的聯繫，但是對於類標較多、數據量較大的數據集，這類方法的計算複雜度是一個很明顯的缺陷。

演算法適應方法與問題轉化方法不同，問題轉化方法是將多標記問題轉化成一個或者多個單類標問題，演算法適應方法是在多標記的基礎上研究演算法。近年來，用於多標記的演算法適應的演算法越來越多，代表性學習演算法ML-kNN[[5]]，Rank-SVM[[6]]，LEAD[[7]]，CML。

對於分類策略，基於考察標記之間相關性的不同方式，已有的多標記學習演算法的策略思路大致可以分為以下三類[[8]]：

a) 「一階（first-order）」策略：該類策略通過逐一考察單個標記而忽略標記之間的相關性，如將多標記學習問題分解為個獨立的二類分類問題，從而構造多標記學習系統。該類方法效率較高且實現簡單，但由於其完全忽略標記之間可能存在的相關性，其系統的泛化性能往往較低。

b) 「二階（second-order）」策略：該類策略通過考察兩兩標記之間的相關性，如相關標記與無關標記之間的排序關係，兩兩標記之間的交互關係等等，從而構造多標記學習系統。該類方法由於在一定程度上考察了標記之間的相關性，因此其系統泛化性能較優。

c) 「高階（high-order）」策略：該類策略通過考察高階的標記相關性，如處理任一標記對其它所有標記的影響，處理一組隨機標記集合的相關性等等，從而構造多標記學習系統。該類方法雖然可以較好地反映真實世界問題的標記相關性，但其模型複雜度往往過高，難以處理大規模學習問題。

[[1]] Madjarov G, Kocev D, Gjorgjevikj D, et al. An extensive experimental comparison of methods for multi-label learning[J]. Pattern Recognition, 2012, 45(9): 3084-3104.

[[2]] Boutell M R, Luo J, Shen X, Brown C M. Learning multi-label scene classification. Pattern Recognition, 2004, 37(9): 1757-1771.

[[3]] Fürnkranz J, Hüllermeier E, Loza Mencía E, Brinker K. Multilabel classification via calibrated label ranking. Machine Learning, 2008, 73(2): 133-153.

[[4]] Tsoumakas G, Vlahavas I. Random k-labelsets: An ensemble method for multilabel classification. In: Kok J N, Koronacki J, de Mantaras R L, Matwin S, Mladeni? D, Skowron A, eds. Lecture Notes in Artificial Intelligence 4701, Berlin: Springer, 2007, 406-417.

[[5]] Zhang M-L, Zhou Z-H. ML-kNN: A lazy learning approach to multi-label learning. Pattern Recognition, 2007, 40(7): 2038-2048.

[[6]] Elisseeff A, Weston J. A kernel method for multi-labelled classification. In: Dietterich T G, Becker S, Ghahramani Z, eds. Advances in Neural Information Processing Systems 14 (NIPS』01), Cambridge, MA: MIT Press, 2002, 681-687.

[[7]] Zhang M-L, Zhang K. Multi-label learning by exploiting label dependency. In: Pro ceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD』10), Washington, D. C., 2010, 999-1007.

[[8]] Zhang M L, Zhang K. Multi-label learning by exploiting label dependency[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2010:999-1008.

BY 余文禮

其他人回答的基本都是周老師和張敏靈老師那篇Multi-Label綜述裡面的內容，除了基本的方法之外，這裡我列一下自己感覺比較好的幾篇Multi-Label的paper：

（1）LEML： Large-scale Multi-label Learning with Missing Labels 一種針對弱標記數據的多標記學習方法

（2）TRAM：Transductive Multilabel Learning via Label Set Propagation 利用標記集合傳遞的直推式的多標記學習方法

（3）WELL(Multi-Label Learning with Weak Label)：http://ai2-s2-pdfs.s3.amazonaws.com/4642/916ee5c2697356d02afdb3cd13b30b8051ba.pdf能夠處理missing label

這幾種方法都是比較新的，在我跑實驗的時候效果比較好而且速度還不錯的方法。良心推薦

如果是classification的問題：推薦兩個方法

0層或多層的hidden layer + Softmax：label弄成向量如[0 1 0 1 0 0 1]，Loss Function是CE的話做加和(/sum(label))就行，Softmax求導裡面有一個點乘label，所以參數矩陣W迭代會更新到對應W的行(或列)上面--完全的Deep Learning套路，沒理解錯的話就是Hinton的Distilling the Knowledge in a Neural Network https://www.cs.toronto.edu/~hinton/absps/distillation.pdf 中提的 the soft targets
Multi-dimension Logistic Regression[0層或多層的hidden layer + Sigmoid, 類Deep Learning方法] 訓練過程如上，與Softmax的差別：訓練過程最後層概率不做 Normalization

Softmax訓練完概率做不做Normalization已經不重要了，完全可以取Top K作為預測

MD-LR的最後輸出都在[0, 1]之間，可以設定個閾值，大於它的都可以作為預測

有一篇綜述是介紹多標籤演算法的A review on multilabel algorithm，主要介紹了關於機器學習如何處理多標籤問題。MLKNN是在KNN的基礎上修改了方法，處理多標籤問題。

機器學習的多標籤庫有一個是meka。

我自己用的是MLKNN方法，處理的多標籤問題，效果比較好。

多標籤問題，需要把標籤寫成二進位編碼形式，1代表屬於該分類，0代表不屬於該分類。

深度學習方面：首先想到的是通過softmax層輸出每個分類的概率，通過設定閾值，來判斷屬於哪種分類，但是親自試過，效果不是很好。

然後，可以通過編寫多個二進位分類來判斷是否屬於這個分類，但是這種方法對於分類數目較多的情況下不太適用。

然後深度學習可以在softmax層之前加入一個coding層，每一種分類用一個bit位表示。

可以使用交叉熵損失函數(Caffe里叫做Sigmoid Cross Entropy Loss)，效果不錯，使用起來也很簡單

去找了下數據集，怎麼網上都是標籤空格 FT1：VAL1格式啊。。。raw text呢？？？誰讓你擅自給我提取feature的？T_T

今天剛剛聽了講座，搜extreme classification。。。