trNon-greedy active learning for text categorization using convex ansductive experimental design

ABSTRACT

In this paper we propose a non-greedy active learning method for text categorization using least-squares support vector machines (LSSVM). Our work is based on transductive experimental design (TED), an active learning formulation that effectively explores the information of unlabeled data. Despite its appealing properties, the optimization problem is however NP-hard and thus--like most of other active learning methods--a greedy sequential strategy to select one data example after another was suggested to find a suboptimum. In this paper we formulate the problem into a continuous optimization problem and prove its convexity, meaning that a set of data examples can be selected with a guarantee of global optimum. We also develop an iterative algorithm to efficiently solve the optimization problem, which turns out to be very easy-to-implement. Our text categorization experiments on two text corpora empirically demonstrated that the new active learning algorithm outperforms the sequential greedy algorithm, and is promising for active text categorization applications.

REFERENCES

• 1: A. C. Atkinson and A. N. Donev. Optimum experiment designs. Oxford Statistical Science Series. Oxford University Press, 1992.
• 2: O. Chapelle. Active learning for Parzen window classifier. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, pages 49--56, 2005.
• 3: D. Cohn and Z. Ghahramani. Active learning with statistical models. Journal of Arti¯cial Intelligence Research, 4:129--145, 1996.
• 4: D. Donoho. For most large underdetermined systems of linear equations, the minimal l1-norm solution is also the sparsest solution. Communications on Pure and Applied Mathematics, 59(6), 2006.
• 5: Yoav Freund , H. Sebastian Seung , Eli Shamir , Naftali Tishby, Selective Sampling Using the Query by Committee Algorithm, Machine Learning, v.28 n.2-3, p.133-168, Aug./Sept. 1997 [doi>10.1023/A:1007330508534]
• 6: Carlos Guestrin , Andreas Krause , Ajit Paul Singh, Near-optimal sensor placements in Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.265-272, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102385]
• 7: Xiaofei He , Wanli Min , Deng Cai , Kun Zhou, Laplacian optimal design for image retrieval, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277764]
• 8: Steven C. H. Hoi , Rong Jin , Jianke Zhu , Michael R. Lyu, Batch mode active learning and its application to medical image classification, Proceedings of the 23rd international conference on Machine learning, p.417-424, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143897]
• 9: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 10: David J. C. MacKay, Information-based objective functions for active data selection, Neural Computation, v.4 n.4, p.590-604, July 1992 [doi>10.1162/neco.1992.4.4.590]
• 11: David J. C. MacKay, Information-based objective functions for active data selection, Neural Computation, v.4 n.4, p.590-604, July 1992 [doi>10.1162/neco.1992.4.4.590]
• 12: A. Schein and L. Ungar. Optimality for active learning of logistic regression classi¯ers. Technical Report Technical Report MS-CIS-04-07, The University of Pennsylvania, Department of Computer and Information Science, 2004.
• 13: Greg Schohn , David Cohn, Less is More: Active Learning with Support Vector Machines, Proceedings of the Seventeenth International Conference on Machine Learning, p.839-846, June 29-July 02, 2000
• 14: J. A. K. Suykens , J. Vandewalle, Least Squares Support Vector Machine Classifiers, Neural Processing Letters, v.9 n.3, p.293-300, June 1999 [doi>10.1023/A:1018628609742]
• 15: R. Tibshirani. Regression shrinkage and selection via the lasso. J. Royal. Statist. Soc B, 58(1), 1996.
• 16: Simon Tong , Daphne Koller, Support vector machine active learning with applications to text classification, The Journal of Machine Learning Research, 2, p.45-66, 3/1/2002 [doi>10.1162/153244302760185243]
• 17: Kai Yu , Jinbo Bi , Volker Tresp, Active learning via transductive experimental design, Proceedings of the 23rd international conference on Machine learning, p.1081-1088, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143980]
• 18: Jian Zhang , Yiming Yang, Robustness of regularized linear classification methods in text categorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860471]
• 19: Tong Zhang , Frank J. Oles, Text Categorization Based on Regularized Linear Classification Methods, Information Retrieval, v.4 n.1, p.5-31, April 2001 [doi>10.1023/A:1011441423217]
• 20: Wei Vivian Zhang , Xiaofei He , Benjamin Rey , Rosie Jones, Query rewriting using active learning for sponsored search, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277942]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Performance, Theory

Keywords:
active learning, convex optimization, text categorization, transductive experimental design