對多標籤分類問題中標籤空間降維演算法進行成本導向編碼

Cost-sensitive Encoding for Label Space Dimension Reduction Algorithms on Multi-label Classification

羅國宣(Kuo-Hsuan Lo)

指導教授 ： 林軒田

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2017年)

https://doi.org/10.6342/NTU201700090

摘要

在多標籤分類問題（Multi-label Classification Problem）中，目標是同時將每個實例分類為多個類。不同的真實世界應用通常需要不同的評估標準，因此需要能夠考慮評估標準的演算法。這樣的演算法被稱為成本導向多標籤分類（Cost-sensitive Multi-label Classification）演算法。現有的演算法，如標籤空間降維法（Label Space Dimension Reduction）能夠有效地解決多標籤分類問題，但是沒有一個標籤空間降維法具成本導向性質。另一方面，當使用一般標準時，大多數現有的成本導向多標籤分類問題演算法在訓練或預測期間遭受高計算複雜性。論文中，我們提出新的演算法，使現有的標籤空間降維法具成本導向性質，同時保持其效率。我們的演算法將成本資訊嵌入到編碼空間中，並使用空間降維法減少編碼空間內的學習的計算負擔。廣泛的實驗證明，我們的演算法改進現有的標籤空間降維法，並且在不同的評估標準上，產生比最先進的成本導向多標籤分類問題演算法更好的性能或更低的標籤空間維度。

關鍵字

多標籤分類 ； 成本導向 ； 成本編碼 ； 標籤空間降維演算法

並列摘要

In the multi-label classification problem (MLC) , the goal is to classify each instance into multiple classes simultaneously. Different real-world applications often demand different evaluation criteria, and hence algorithms that are capable of taking the criteria into account are preferable. Such algorithms are called cost-sensitive multi-label classification (CSMLC) algorithms. Existing algorithms such as label space dimension reduction (LSDR) are able to solve the MLC problem efficiently, but none of the LSDR algorithms are cost-sensitive. On the other hand, most of the existing CSMLC algorithms suffer from high computational complexity during training or prediction when using general criteria. In this work, we propose a novel algorithm called Cost-Sensitive Encoding for label space Dimension Reduction (CSEDR) that makes existing LSDR algorithms cost-sensitive while keeping their efficiency. Our algorithm embeds cost information into the encoded space, and reduce the computational burden of learning within the encoded space by LSDR. Extensive experiments justify that our algorithm both improves the existing LSDR algorithms and results in better performance or lower label space dimension than state-of-the-art CSMLC algorithms across different evaluating criteria.

並列關鍵字

multi-label classification ； cost-sensitive ； cost-encoding ； label space dimension reduction

參考文獻

[5] F Briggs, B Lakshminarayanan, L Neal, XZ Fern, R Raich, SJK Hadley, AS Hadley,and MG Betts. New methods for acoustic classification of multiple simultaneousbird species in a noisy environment. InIEEE International Workshop on MachineLearning for Signal Processing, pages 1–8, 2013.

[7] Hung-Yi Lo, Ju-Chiang Wang, Hsin-Min Wang, and Shou-De Lin. Cost-sensitivemulti-label learning for audio tag annotation and retrieval.IEEE Transactions onMultimedia, 13(3):518–529, 2011.

[9] Chun-Sung Ferng and Hsuan-Tien Lin. Multi-label classification with error-correctingcodes. InACML, pages 281–295, 2011.

[10] Raj Chandra Bose and Dwijendra K Ray-Chaudhuri. On a class of error correctingbinary group codes.Information and control, 3(1):68–79, 1960.

[12] Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank. Classifier chainsfor multi-label classification.Machine learning, 85(3):333–359, 2011.