Fast logistic regression for text categorization with variable-length n-grams

ABSTRACT

A common representation used in text categorization is the bag of words model (aka. unigram model). Learning with this particular representation involves typically some preprocessing, e.g. stopwords-removal, stemming. This results in one explicit tokenization of the corpus. In this work, we introduce a logistic regression approach where learning involves automatic tokenization. This allows us to weaken the a-priori required knowledge about the corpus and results in a tokenization with variable-length (word or character) n-grams as basic tokens. We accomplish this by solving logistic regression using gradient ascent in the space of all ngrams. We show that this can be done very efficiently using a branch and bound approach which chooses the maximum gradient ascent direction projected onto a single dimension (i.e., candidate feature). Although the space is very large, our method allows us to investigate variable-length n-gram learning. We demonstrate the efficiency of our approach compared to state-of-the-art classifiers used for text categorization such as cyclic coordinate descent logistic regression and support vector machines.

REFERENCES

• 1: Kenji Abe , Shinji Kawasoe , Tatsuya Asai , Hiroki Arimura , Setsuo Arikawa, Optimized Substructure Discovery for Semi-structured Data, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.1-14, August 19-23, 2002
• 2: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 3: H. Cheng, X. Yan, J. Han, and C.-W. Hsu. Discriminative frequent pattern analysis for effective classification. In Proceedings of ICDE, pages 716--725, 2007.
• 4: J. G. Cleary and W. J. Teahan. Unbounded length contexts for PPM. Computer Journal, 3(40):67--75, 1997.
• 5: O. Dekel, S. Shalev-Shwartz, and Y. Singer. The power of selective memory: Self-bounded learning of prediction suffix trees. In Proceedings of NIPS, Vancouver, Canada, 2004.
• 6: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 7: B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. Annals of Statistics, 32(2)(4047499), 2004.
• 8: Eibe Frank , Chang Chui , Ian H. Witten, Text Categorization Using Compression Models, Proceedings of the Conference on Data Compression, p.555, March 28-30, 2000
• 9: A. Genkin, D. Lewis, and D. Madigan. Large-scale Bayesian logistic regression for text categorization. Technometrics, 49(3):291--304, 2007.
• 10: J. Goodman. A bit of progress in language modeling. In Technical report. Microsoft Research, 2001.
• 11: J. Goodman. A bit of progress in language modeling. In Technical report. Microsoft Research, 2001.
• 12: Ji He , Ah-Hwee Tan , Chew-Lim Tan, On Machine Learning Methods for Chinese Document Categorization, Applied Intelligence, v.18 n.3, p.311-322, May-June 2003 [doi>10.1023/A:1023202221875]
• 13: D. Holmes and R. Forsyth. The Federalist revisited: New directions in authorship attribution. Literary and Linguistic Computing, 2(10):111--127, 1995.
• 14: G. Ifrim and G. Weikum. Transductive learning for text classification using explicit knowledge models. In Proceedings of PKDD, Springer Lecture Notes in Artificial Intelligence, pages 223--234, Berlin, Germany, 2006.
• 15: R. Jin, R. Yan, J. Zhang, and A. Hauptmann. A faster iterative scaling algorithm for conditional exponential model. In Proceedings of ICML, 2003.
• 16: 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
• 17: Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150429]
• 18: Brett Kessler , Geoffrey Numberg , Hinrich Schütze, Automatic detection of text genre, Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and Eighth Conference of the European Chapter of the Association for Computational Linguistics, p.32-38, July 07-12, 1997, Madrid, Spain
• 19: P. Komarek and A. Moore. Fast robust logistic regression for large sparse datasets with binary outputs. In Proceedings of the International Workshop on Artificial Intelligence and Statistics, New York, NY, 2003.
• 20: Arnd Christian König , Eric Brill, Reducing the human overhead in text categorization, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150474]
• 21: T. Kudo. An implementation of freqt (frequent tree miner). http://chasen.org/~taku/software/freqt/, 2003.
• 22: T. Kudo and Y. Matsumoto. A boosting algorithm for classification of semi-structured text. In Proceedings of EMNLP, pages 301--308, Barcelona, Spain, July 2004. Association for Computational Linguistics.
• 23: Yong-Bae Lee , Sung Hyon Myaeng, Text genre classification with genre-revealing and subject-revealing features, 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.564403]
• 24: Huma Lodhi , Craig Saunders , John Shawe-Taylor , Nello Cristianini , Chris Watkins, Text classification using string kernels, The Journal of Machine Learning Research, 2, p.419-444, 3/1/2002
• 25: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 26: J. Nocedal and S. Wright. Numerical Optimization. Springer Series in Operation Research and Financial Engineering, 2006.
• 27: Fuchun Peng , Dale Schuurmans , Shaojun Wang, Augmenting Naive Bayes Classifiers with Statistical Language Models, Information Retrieval, v.7 n.3-4, p.317-345, September-December 2004 [doi>10.1023/B:INRT.0000011209.19643.e2]
• 28: R. Rosenfeld. Two decades of statistical language modeling: Where do we go from here? Proceedings of the IEEE, 88(8):1270--1278, 2000.
• 29: B. Scholkopf and A. J. Smola. Learning with Kernels. MIT Press, Cambridge, MA, 2002.
• 30: S. K. Shevade and S. S. Keerthi. A simple and efficient algorithm for gene selection using sparse logistic regression. Bioinformatics, 19:2246--2253, 2003.
• 31: 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]
• 32: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 33: Mohammed J. Zaki, Efficiently mining frequent trees in a forest, 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.775058]
• 34: Dell Zhang , Wee Sun Lee, Extracting key-substring-group features for text classification, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150455]
• 35: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Experimentation, Performance

Keywords:
fast logistic regression, n-gram learning, text categorization, variable-length n-grams