臺灣博碩士論文加值系統

在多標籤分類問題（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.

1 Introduction P.1
2 Related work P.4
2.1 Multi-Label Classification P.4
2.2 Cost-Sensitive Multi-Label Classification P.7
3 Proposed framework P.11
3.1 Framework Structure P.12
3.2 Label Space Expansion Codec P.13
3.2.1Lazy Codec P.14
3.2.2Extreme Codec P.14
3.2.3RAkEL Codec P.14
3.3 Cost Information Embedding P.14
3.3.1Reference Rule P.15
3.3.2Proposed Algorithm P.15
3.3.3For Lazy Codec P.16
3.3.4For Extreme and RAkEL Codec P.16
3.3.5For Off-the-shelf ECC Codec P.17
3.4 Sub-problem Dimension Reduction Trick P.20
3.5 Feasibility of Cost Vector Space Dimension Reduction P.21
3.6 Analysis of Time Complexity P.22
3.7 Analysis of Error bound P.24
4 Experiments P.27
4.1 Experimental Setup P.27
4.1.1Dataset P.27
4.1.2Algorithms and the Parameters P.28
4.1.3Base learner and the Parameter Selection P.28
4.1.4Cost Function P.29
4.2 Comparison on Existing LSDR Algorithms P.29
4.3 Comparison among the variants of CSEDR P.29
4.4 Comparison with State-of-the-art Algorithms P.31
4.4.1Comparison with PRAkEL P.33
4.4.2Comparison with CFT P.35
5 Conclusion P.37
Bibliography P.38

[1] Grigorios Tsoumakas, Ioannis Katakis, and Ioannis Vlahavas. Mining multi-labeldata. InData mining and knowledge discovery handbook, pages 667–685. Springer,2009.
[2] Ioannis Katakis, Grigorios Tsoumakas, and Ioannis Vlahavas. Multilabel text classi-fication for automated tag suggestion.ECML PKDD discovery challenge, 75, 2008.
[3] Konstantinos Trohidis, Grigorios Tsoumakas, George Kalliris, and Ioannis P Vla-havas. Multi-label classification of music into emotions. InISMIR, volume 8, pages325–330, 2008.
[4] Andr ́e Elisseeff and Jason Weston. A kernel method for multi-labelled classification.InAdvances in neural information processing systems, pages 681–687, 2001.
[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.
[6] Yu-Ping Wu and Hsuan-Tien Lin. Progressivek-labelsets for cost-sensitive multi-labelclassification.Machine Learning, 2016. Accepted for Special Issue of ACML 2016.
[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.
[8] Yi Zhang and Jeff G Schneider. Multi-label output codes using canonical correlationanalysis. InAISTATS, pages 873–882, 2011.43
[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.
[11] Chun-Liang Li and Hsuan-Tien Lin. Condensed filter tree for cost-sensitive multi-label classification. InICML, pages 423–431, 2014.
[12] Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank. Classifier chainsfor multi-label classification.Machine learning, 85(3):333–359, 2011.
[13] Grigorios Tsoumakas and Ioannis Vlahavas. Random k-labelsets: An ensemblemethod for multilabel classification. InEuropean Conference on Machine Learning,pages 406–417. Springer, 2007.
[14] Farbound Tai and Hsuan-Tien Lin. Multilabel classification with principal label spacetransformation.Neural Computation, 24(9):2508–2542, 2012.
[15] Yao-Nan Chen and Hsuan-Tien Lin. Feature-aware label space dimension reductionfor multi-label classification. InAdvances in Neural Information Processing Systems,pages 1529–1537, 2012.
[16] Zijia Lin, Guiguang Ding, Mingqing Hu, and Jianmin Wang. Multi-label classificationvia feature-aware implicit label space encoding. InICML, pages 325–333, 2014.
[17] Weiwei Cheng, Eyke H ̈ullermeier, and Krzysztof J Dembczynski. Bayes optimal mul-tilabel classification via probabilistic classifier chains. InProceedings of the 27thinternational conference on machine learning (ICML-10), pages 279–286, 2010.
[18] Alina Beygelzimer, John Langford, and Pradeep Ravikumar. Multiclass classificationwith filter trees.Preprint, June, 2, 2007.
[19] Grigorios Tsoumakas, Eleftherios Spyromitros-Xioufis, Jozef Vilcek, and Ioannis Vla-havas. Mulan: A java library for multi-label learning.Journal of Machine LearningResearch, 12:2411–2414, 2011.
[20] Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin.LIBLINEAR: A library for large linear classification.Journal of Machine LearningResearch, 9:1871–1874, 2008.
[21] Andy Liaw and Matthew Wiener. Classification and regression by randomforest.Rnews, 2(3):18–22, 2002.
[22] Han-Hsing Tu and Hsuan-Tien Lin. One-sided support vector regression for multiclasscost-sensitive classification. InProceedings of the 27th International Conference onMachine Learning (ICML-10), pages 1095–1102, 2010.
[23] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector ma-chines.ACM Transactions on Intelligent Systems and Technology, 2:27:1–27:27, 2011.Software available athttp://www.csie.ntu.edu.tw/~cjlin/libsvm