本論文研究三個重要且實際的議題:線上更新,標籤空間維度下 降,以及成本導向性,在多標籤分類問題上。目前的多標籤分類問題 演算法並未被設計來同時處理這三個議題。在本論文中,我們提出了 一個創新的演算法,成本導向動態特徵投影,來同時解決這三個議題。 本方法是基於一個將領先的標籤空間維度下降演算法利用線上主成份 分析延伸到線上更新的框架。詳細的說,本方法使用矩陣隨機梯度下 降法作為處理線上主成份分析問題的方法,並在與精心設計得線上回 歸學習者結合時建立其理論骨幹。另外,本方法將成本資訊嵌入標籤 權重之中以達有理論保證的成本導向性。我們也研究了本方法的實際 改進以提高效率。實驗結果表明,本方法在不同的評估標準上達到比 現有的多標籤分類演算法更好的實際表現,也證明了同時解決這三個 問題的重要性。

We study multi-label classification (MLC) with three important real-world issues: online updating, label space dimensional reduction (LSDR), and cost-sensitivity. Current MLC algorithms have not been designed to address these three issues simultaneously. In this paper, we propose a novel algorithm, cost- sensitive dynamic principal projection (CS-DPP) that resolves all three issues. The foundation of CS-DPP is a framework that extends a leading LSDR algorithm to online updating with online principal component analysis (PCA). In particular, CS-DPP investigates the use of matrix stochastic gradient as the on- line PCA solver, and establishes its theoretical backbone when coupled with a carefully-designed online regression learner. In addition, CS-DPP embeds the cost information into label weights to achieve cost-sensitivity along with theoretical guarantees. Practical enhancements of CS-DPP are also studied to improve its efficiency. Experimental results verify that CS-DPP achieves better practical performance than current MLC algorithms across different evaluation criteria, and demonstrate the importance of resolving the three issues simultaneously.

Contents
誌謝 i
摘要 ii
Abstract iii
1 Introduction 1
2 Preliminaries and Related Work 4
3 Dynamic Principal Projection 7
3.1 Principal LabelS pace Transformation ................... 7
3.2 Online PCA................................. 8
3.3 Proposed Approach............................. 9
3.4 Practical Variant and Implementation ................... 12
4 Cost-Sensitive Extension 14
5 Experiments 17
5.1 Experiments Setup ............................. 17
5.2 Necessity of LSDR ............................. 18
5.3 Experiments on Basis Drifting ....................... 19
5.4 Experiments on Cost-Sensitivity ...................... 20
6 Conclusion 23
A 24
A.1 Proof of Theorem2............................. 24
A.2 Proof of Lemma3.............................. 27
A.3 Proof of Lemma4.............................. 28
A.4 Proof of Theorem5............................. 29
A.5 Details of Experiments ........................... 31
A.5.1 Datasets and Parameters ...................... 31
A.5.2 Necessity of LSDR......................... 31
A.5.3 Experiments on BasisDrifting................... 32
A.5.4 Experiments on Cost-sensitivity .................. 33
Bibliography 36

[1] R. Arora, A. Cotter, and N. Srebro. Stochastic optimization of PCA with capped MSG. In NIPS, pages 1815–1823, 2013.
[2] K. Balasubramanian and G. Lebanon. The landmark selection method for multiple output prediction. In ICML, 2012.
[3] P. Bartlett. Online convex optimization: ridge regression, adaptivity, 2008.
[4] J. P. Bello, E. Chew, and D. Turnbull. Multilabel classification of music into emotions. In ICMIR, pages 325–330, 2008.
[5] K. Bhatia, H. Jain, P. Kar, M. Varma, and P. Jain. Sparse local embeddings for extreme multi-label classification. In NIPS, pages 730–738, 2015.
[6] W. Bi and J. T. Kwok. Efficient multi-label classification with many labels. In ICML, pages 405–413, 2013.
[7] Y. Chen and H. Lin. Feature-aware label space dimension reduction for multi-label classification. In NIPS, pages 1538–1546, 2012.
[8] T. Chua, J. Tang, R. Hong, H. Li, Z. Luo, and Y. Zheng. NUS-WIDE: a real-world web image database from national university of singapore. In CIVR, 2009.
[9] K.Crammer,O.Dekel,J.Keshet,S.S.-S.,andY.Singer. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551–585, 2006.
[10] K. Dembczynski, W. Cheng, and E. Hüllermeier. Bayes optimal multilabel classification via probabilistic classifier chains. In ICML, pages 279–286, 2010.
[11]K.Dembczynski,W.Waegeman,W.Cheng,andE.Hüllermeier.Anexactalgorithm for F-measure maximization. In NIPS, pages 1404–1412, 2011.
[12] A. Elisseeff and J. Weston. A kernel method for multilabelled classification. In NIPS, 2001.
[13] D.Hsu,S.Kakade,J.Langford,andT.Zhang.Multi label Prediction Via Compressed sensing. In NIPS, pages 772–780, 2009.
[14] A. Kapoor, R. Viswanathan, and P. Jain. Multilabel classification using bayesian compressed sensing. In NIPS, pages 2654–2662, 2012.
[15] C. Li and H. Lin. Condensed filter tree for cost-sensitive multi-label classification. In ICML, pages 423–431, 2014.
[16] C.Li,H.Lin,andC.Lu.Rivalry of two families of algorithms for memory restricted streaming PCA. In AISTATS, 2016.
[17] Z. Lin, G. Ding, M. Hu, and J. Wang. Multi-label classification via feature-aware implicit label space encoding. In ICML, pages 325–333, 2014.
[18] H. Lo, J. Wang, H. Wang, and S. Lin. Cost-sensitive multi-label learning for audio tag annotation and retrieval. IEEE Trans. Multimedia, 13(3):518–529, 2011.
[19] J.Nie, W.Kotlowski, and M.K.Warmuth. Online PCA with optimal regrets.Journal of Machine Learning Research, 17:194–200, 2016.
[20] A. P. P. Osojnik and D. S. Multi-label classification via multi-target regression on data streams. Machine Learning, 2017.
[21] J.Read, A.Bifet,G.Holmes, and B.Pfahringer. Streaming multi-label classification. In Proceedings of the Workshop on Applications of Pattern Analysis (WAPA), pages 19–25, 2011.
[22] J. Read, B. Pfahringer, G. Holmes, and E. Frank. Classifier chains for multi-label classification. Machine Learning, 85(3):333–359, 2011.
[23] L. Sun, S. Ji, and J. Ye. Canonical correlation analysis for multilabel classification: A least-squares formulation, extensions, and analysis. IEEE TPAMI, 33(1):194–200, 2011.
[24] F.Tai and H.Lin. Multilabel classification with principal label space transformation. Neural Computation, 24(9):2508–2542, 2012.
[25] G. Tsoumakas, I. Katakis, and I. P. Vlahavas. Mining multi-label data. In Data Mining and Knowledge Discovery Handbook, 2nd ed., pages 667–685. 2010.
[26] G. Tsoumakas and I. P. Vlahavas. Random k -labelsets: An ensemble method for multilabel classification. In ECML, pages 406–417, 2007.
[27] J.Wang,P.Zhao, and S.C.H.Hoi. Cost-sensitive online classification.IEEETrans. Knowl. Data Eng., 26(10):2425–2438, 2014.
[28] M. K. Warmuth and D. Kuzmin. Randomized online pca algorithms with regret bounds that are logarithmic in the dimension. Journal of Machine Learning Re- search, 9:2287–2320, 2008.
[29] Y. Wu and H. Lin. Progressive k-labelsets for cost-sensitive multi-label classification. Machine Learning, 2016. Accepted for Special Issue of ACML 2016.
[30] E. S. Xioufis, M. Spiliopoulou, G. Tsoumakas, and I. P. Vlahavas. Dealing with concept drift and class imbalance in multi-label stream classification. In IJCAI, pages 1583–1588, 2011.
[31] H. Yu, P. Jain, P. Kar, and I. S. Dhillon. Large-scale multi-label learning with miss- ing labels. In ICML, pages 593–601, 2014.
[32] X. Zhang, T. Graepel, and R. Herbrich. Bayesian online learning for multi-label and multi-variate performance measures. In AISTATS, 2010.