Text classification from positive and unlabeled documents

ABSTRACT

Most existing studies of text classification assume that the training data are completely labeled. In reality, however, many information retrieval problems can be more accurately described as learning a binary classifier from a set of incompletely labeled examples, where we typically have a small number of labeled positive examples and a very large number of unlabeled examples. In this paper, we study such a problem of performing Text Classification WithOut labeled Negative data TC-WON). In this paper, we explore an efficient extension of the standard Support Vector Machine (SVM) approach, called SVMC (Support Vector Mapping Convergence) [17]for the TC-WON tasks. Our analyses show that when the positive training data is not too under-sampled, SVMC significantly outperforms other methods because SVMC basically exploits the natural "gap" between positive and negative documents in the feature space, which eventually corresponds to improving the generalization performance. In the text domain there are likely to exist many gaps in the feature space because a document is usually mapped to a sparse and high dimensional feature space. However, as the number of positive training data decreases, the boundary of SVMC starts overfitting at some point and end up generating very poor results.This is because when the positive training data is too few, the boundary over-iterates and trespasses the natural gaps between positive and negative class in the feature space and thus ends up fitting tightly around the few positive training data.

REFERENCES

• 1: Kian Ming Adam Chai , Hai Leong Chieu , Hwee Tou Ng, Bayesian online classifiers for text classification and filtering, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564395]
• 2: Chih-Chung Chang , Chih-Jen Lin, Training ν-Support Vector Classifiers: Theory and Algorithms, Neural Computation, v.13 n.9, p.2119-2147, September 2001 [doi>10.1162/089976601750399335]
• 3: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 4: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 5: Thorsten Joachims, A statistical learning learning model of text classification for support vector machines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.128-136, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383974]
• 6: David Dolan Lewis, Representation and learning in information retrieval, University of Massachusetts, Amherst, MA, 1992
• 7: Bing Liu , Wee Sun Lee , Philip S. Yu , Xiaoli Li, Partially Supervised Classification of Text Documents, Proceedings of the Nineteenth International Conference on Machine Learning, p.387-394, July 08-12, 2002
• 8: Larry M. Manevitz , Malik Yousef, One-class svms for document classification, The Journal of Machine Learning Research, 2, 3/1/2002
• 9: Andrew McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, A Machine Learning Approach to Building Domain-Specific Search Engines, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.662-667, July 31-August 06, 1999
• 10: Kamal Nigam , Andrew Kachites McCallum , Sebastian Thrun , Tom Mitchell, Text Classification from Labeled and Unlabeled Documents using EM, Machine Learning, v.39 n.2-3, p.103-134, May-June 2000 [doi>10.1023/A:1007692713085]
• 11: B. Scholkopf, A. J. Smola, R. C. Williamson, and P. L. Bartlett. New support vector algorithms. Neural Computation, 12:1083--1121, 2000.
• 12: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 13: David M. J. Tax , Robert P. W. Duin, Uniform object generation for optimizing one-class classifiers, The Journal of Machine Learning Research, 2, 3/1/2002
• 14: V. N. Vapnik. Statistical Learning Theory. John Wiley and Sons, 1998.
• 15: Yiming Yang, A study of thresholding strategies for text categorization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.137-145, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383975]
• 16: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 17: H. Yu. SVMC: Single-class classification with support vector machines. In Proc. Int. Joint Conf. on Articial Intelligence (IJCAI-03), Acapulco, Maxico, 2003.
• 18: Hwanjo Yu , Jiawei Han , Kevin Chen-Chuan Chang, PEBL: positive example based learning for Web page classification using SVM, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775083]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.m Miscellaneous

General Terms:
Algorithms, Performance

Keywords:
SVM, machine learning, text classification, text filtering