A maximal figure-of-merit learning approach to text categorization

ABSTRACT

A novel maximal figure-of-merit (MFoM) learning approach to text categorization is proposed. Different from the conventional techniques, the proposed MFoM method attempts to integrate any performance metric of interest (e.g. accuracy, recall, precision, or F1 measure) into the design of any classifier. The corresponding classifier parameters are learned by optimizing an overall objective function of interest. To solve this highly nonlinear optimization problem, we use a generalized probabilistic descent algorithm. The MFoM learning framework is evaluated on the Reuters-21578 task with LSI-based feature extraction and a binary tree classifier. Experimental results indicate that the MFoM classifier gives improved F1 and enhanced robustness over the conventional one. It also outperforms the popular SVM method in micro-averaging F1. Other extensions to design discriminative multiple-category MFoM classifiers for application scenarios with new performance metrics could be envisioned too.

REFERENCES

• 1: Bellegarda, J. R., Exploiting latent semantic information in statistical language modeling, In Proceedings of the IEEE, Vol.88, No.8, pp.1279--1296, August, 2000.
• 2: Michael Berry , Theresa Do , Gavin O''Brien , Vijay K %A , Sowmini Varadhan, SVDPACKC (Version 1.0) User''s Guide, University of Tennessee, Knoxville, TN, 1993
• 3: Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C.J., Classification and Regression Trees, Wadsworth Int. 1984.
• 4: Carla E. Brodley , Paul E. Utgoff, Multivariate Decision Trees, Machine Learning, v.19 n.1, p.45-77, April 1995 [doi>10.1023/A:1022607123649]
• 5: Chris Buckley , Gerard Salton , James Allan, The effect of adding relevance information in a relevance feedback environment, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.292-300, July 03-06, 1994, Dublin, Ireland
• 6: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 7: Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K. and Harshman, R., Indexing by latent semantic analysis, In Journal of the American Society for Information Science, Vol.41, No. 6, pp.391--407, 1990.
• 8: Denoyer, L., Zaragoza, H. and Gallinari, P., HMM-based passage models for document classification and ranking, In ECIR'01, 2001.
• 9: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 10: Guo, H. and Gelfand S. B., Classification trees with neural network feature extraction, In IEEE Trans. on Neural Networks, Vol. 3, No. 6, pp.923--933, Nov., 1992.
• 11: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 12: Thorsten Joachims, A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.143-151, July 08-12, 1997
• 13: Thorsten Joachims, Learning to Classify Text Using Support Vector Machines: Methods, Theory and Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 14: 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
• 15: Juang, B.-H., Chou, W. and Lee, C.-H., Minimum classification error rate methods for speech recognition, In IEEE Trans. on Speech and Audio Processing, Vol.5, No. 2, pp.257--265, March, 1997.
• 16: Katagiri, S., Juang, B.-H. and Lee, C.-H., Pattern recognition using a family of design algorithm based upon the generalized probabilistic descent method, In Proceedings of the IEEE, Vol.86, No.11, pp.2345--2373, 1998.
• 17: Kuo, H. K. J. and Lee, C.-H., Discriminative training of natural language call routers, In IEEE Trans. on Speech and Audio Processing, Vol.11, No.1, pp.24--35, 2003.
• 18: Lee, C.-H. and Huo, Q., On adaptive decision rules and decision parameter adaptation for automatic speech recognition, In Proceedings of the IEEE, Vol.88, No.8, pp.1241--1269, August, 2000.
• 19: Chin-Hui Lee , Frank K. Soong , Kuldip K. Paliwal, Automatic Speech and Speaker Recognition: Advanced Topics, Kluwer Academic Publishers, Norwell, MA, 1999
• 20: Lewis, D. and Ringuette, M., A comparison of two learning algorithms for text categorization. In The Third Annual Symposium on Document Analysis and Information Retrieval, pp.81--93, 1994.
• 21: Li, Y. H. and Jain, A. K., Classification of text documents, In The Computer Journal, Vol.41, No.8, pp.537--546, 1998.
• 22: Jimin Liu , Tat-Seng Chua, Building semantic perceptron net for topic spotting, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.378-385, July 06-11, 2001, Toulouse, France [doi>10.3115/1073012.1073061]
• 23: Makoto Iwayama , Takenobu Tokunaga, Cluster-based text categorization: a comparison of category search strategies, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.273-280, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215371]
• 24: Brij Masand , Gordon Linoff , David Waltz, Classifying news stories using memory based reasoning, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.59-65, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133177]
• 25: McCallum, A. and Nigam, K., A comparison of event models for Naive Bayes text classification, In AAAI-98 Workshop on Learning for Text Categorization, pp.41--48, 1998.
• 26: David R. H. Miller , Tim Leek , Richard M. Schwartz, A hidden Markov model information retrieval system, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.214-221, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312680]
• 27: Hwee Tou Ng , Wei Boon Goh , Kok Leong Low, Feature selection, perception learning, and a usability case study for text categorization, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.67-73, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 28: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 29: Miguel E. Ruiz , Padmini Srinivasan, Hierarchical neural networks for text categorization (poster abstract), Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.281-282, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312700]
• 30: Robert E. Schapire , Yoram Singer, BoosTexter: A Boosting-based Systemfor Text Categorization, Machine Learning, v.39 n.2-3, p.135-168, May-June 2000 [doi>10.1023/A:1007649029923]
• 31: Hinrich Schütze , David A. Hull , Jan O. Pedersen, A comparison of classifiers and document representations for the routing problem, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.229-237, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215365]
• 32: 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]
• 33: Paul E. Utgoff , Carla E. Brodley, Linear Machine Decision Trees, University of Massachusetts, Amherst, MA, 1991
• 34: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 35: Haoran Wu , Tong Heng Phang , Bing Liu , Xiaoli Li, A refinement approach to handling model misfit in text categorization, 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.775078]
• 36: 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]
• 37: Yiming Yang, Expert network: effective and efficient learning from human decisions in text categorization and retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.13-22, July 03-06, 1994, Dublin, Ireland

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
decision tree, generalized probabilistic descent method, latent semantic indexing, maximal figure-of-merit, support vector machines, text categorization