臺灣博碩士論文加值系統

在多標籤分類的應用中，由於標籤費用高昂的關係，使得多標籤主動學習開始成為一個熱門的研究領域，而其中一個最新被提出來的演算法 MMC (maximum loss reduction with maximum confidence)，無論是在學習還是詢問的步驟中，都高度依賴著一個特定的多標籤分類器：一對多支持向量機 (binary relevance support vector machine) ，但是MMC的這種高度依賴性並不明確是否是必要的，在本論文中，我們提出了一個一般性的多標籤主動學習框架，這個框架移除了MMC的高度依賴性，並且擁有可參數化的三個元件：用來做決策的主要學習者；用來輔助詢問的次要學習者；以及一個詢問的策略。MMC以及許多其他的演算法都可以被視為這個框架的特例。而基於這個框架，我們提出了兩個不同於以往的詢問策略，HLR (Hamming loss reduction) 和SHLR (soft Hamming loss reduction)，並在許多不同的主要/次要學習者的組合上測試了這些詢問的策略的好壞。在許多的實驗中都顯示，我們所提出的SHLR，無論是在何種衡量基準以及主要/次要學習者的組合上都擁有最穩定良好的表現。

Multi-label active learning is an important problem because of the expensive labeling cost in multi-label classification applications. A state-of-the-art approach for multi-label active learning, maximum loss reduction with maximum confidence (MMC), heavily depends on the binary relevance support vector machine in both learning and querying. Nevertheless, it is not clear whether the heavy dependence is necessary or unrivaled. In this work, we extend MMC to a more general framework that removes the heavy dependence and clarifies the roles of each component in MMC. In particular, the framework is characterized by a major learner for making predictions, an auxiliary learner for helping with query decisions and a query criterion based on the disagreement between the two learners. The framework takes MMC and several baseline multi-label active learning algorithms as special cases. With the flexibility of the general framework, we design two criteria other than the one used by MMC. We also explore the possibility of using learners other than the binary relevance support vector machine for multi-label active learning. Experimental results demonstrate that a new criterion, soft Hamming loss reduction, is usually better than the original MMC criterion across different pairs of major/auxiliary learners, and validate the usefulness of the proposed framework.

致謝 iii
中文摘要 v
Abstract vii
1 Introduction 1
2 Multi-Label Active Learning 5
2.1 Multi-Label classification...5
2.1.1 Binary relevance SVM...5
2.1.2 Stacking with logistic regression...6
2.1.3 Classifier Chain...6
2.2 Active Learning...7
2.2.1 Multi-Label Active Learning...8
2.2.2 Binary version space minimization...9
3 Multi-label Active Learning with Auxiliary Learner 11
3.1 Maximum loss reduction with maximum confidence...11
3.2 The proposed framework...12
4 Query Criterion 15
4.1 Approximate maximum loss reduction...15
4.2 MMR scoring function...17
4.3 Hamming loss reduction...18
4.4 Soft Hamming loss reduction...20
5 Experiment 23
5.1 Setting...23
5.2 Comparison using SLR/BR as Major/Auxiliary...25
5.2.1 SHLR clip operation experiment...29
5.3 Comparison using CC/BR as Major/Auxiliary...30
5.4 Comparison using SLR/CC as Major/Auxiliary...33
6 Conclusion 37
Bibliography 39

Klaus Brinker. On active learing with multi-label classification. In From Data and Infor-
mation Analysis to Knowledge Engineering, pages 206–213, 2006.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines.
ACM Transactions on Intelligent Systems and Technology, 2:27:1–27:27, 2011.
Shantanu Godbole and Sunita Sarawagi. Discriminative methods for multi-labeled clas-
sification. In Proceedings of the 8th Pacific-Asia Conference on Knowledge Discovery
and Data Mining, pages 22–30, 2004.
Rafał Grodzicki, Jacek Ma’ndziuk, and Lipo Wang. Improved multi-label classification
with neural networks. In Proceedings of the 10th International Conference on Parallel
Problem Solving from Nature, pages 409–416, 2008.
David D. Lewis and William A. Gale. A sequential algorithm for training text classifiers.
In Proceedings of the 17th ACM International Conference on Research and Develop-
ment in Information Retrieval, pages 3–12, 1994.
David D. Lewis, Yiming Yang, Tony G. Rose, and Fan Li. Rcv1: A new benchmark
collection for text categorization research. Journal of Machine Learning Research, 5:
361–397, 2004.
Xuchun Li, Lei Wang, and Eric Sung. Multi-label SVM active learning for image clas-
sification. In Proceedings of the 11th International Conference on Image Processing,
pages 2207–2210, 2004.
Hsuan-Tien Lin, Chih-Jen Lin, and Ruby C. Weng. A note on Platt’s probabilistic outputs
for support vector machines. Journal of Machine Learning Research, 68:267–276,
2007.
Andrew McCallum. Multi-label text classification with a mixture model trained by EM.
In Proceedings of the Text Learning Workshop on 15th National Conference of Artificial
Intelligence, 1999.
Andrew McCallum and Kamal Nigam. Employing EM in pool-based active learning for
text classification. In Proceedings of the 15th International Conference on Machine
Learning, pages 350–358, 1998.
Jesse Read, Bernhard Pfahringer, and Geoff Holmes. Multi-label classification using
ensembles of pruned sets. In Proceedings of the 8th IEEE International Conference on
Data Mining, pages 995 –1000, 2008.
Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank. Classifier chains for
multi-label classification. Machine Learning and Knowledge Discovery in Databases,
pages 254–269, 2009.
Nicholas Roy and Andrew McCallum. Toward optimal active learning through sampling
estimation of error reduction. In Proceedings of the 18th International Conference on
Machine Learning, pages 441–448, 2001.
Burr Settles. Active learning literature survey. Technical report, 2010.
H. Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee. In
Proceedings of the 5th Annual Workshop on Computational Learning Theory, pages
287–294, 1992.
Farbound Tai and Hsuan-Tien Lin. Multi-label classification with principle label space
transformation. In Proceedings of the 2nd International Workshop on Learning from
Multi-Label Data, pages 45–52, 2010.
Simon Tong. Active Learning: Theory and Applications. PhD thesis, 2001.
Simon Tong, Daphne Koller, and Pack Kaelbling. Support vector machine active learning
with applications to text classification. Journal of Machine Learning Research, 2:999–
1006, 2000.
Grigorios Tsoumakas and Ioannis Katakis. Multi-label classification: An overview. In-
ternational Journal of Data Warehouse and Mining, 3:1–13, 2007.
Vladimir N. Vapnik. The nature of statistical learning theory. 1995.
Mei Wang, Xiangdong Zhou, and Tat-Seng Chua. Automatic image annotation via local
multi-label classification. In Proceedings of the 7th ACM International Conference on
Image and Video Retrieval, pages 17–26, 2008.
Bishan Yang, Jian-Tao Sun, Tengjiao Wang, and Zheng Chen. Effective multi-label active
learning for text classification. In Proceedings of the 15th ACM International Confer-
ence on Knowledge Discovery and Data Mining, pages 917–926, 2009.
Cha Zhang and Tsuhan Chen. An active learning framework for content-based informa-
tion retrieval. IEEE Transactions on Multimedia, 4:260–268, 2002.
Min-Ling Zhang and Zhi-Hua Zhou. Multi-label neural networks with applications to
functional genomics and text categorization. IEEE Transactions on Knowledge and
Data Engineering, 18:1338 –1351, 2006.
Min-Ling Zhang and Zhi-Hua Zhou. ML-KNN: A lazy learning approach to multi-label
learning. Pattern Recognition, 40:2038–2048, 2007.