Hierarchical document categorization with support vector machines

ABSTRACT

Automatically categorizing documents into pre-defined topic hierarchies or taxonomies is a crucial step in knowledge and content management. Standard machine learning techniques like Support Vector Machines and related large margin methods have been successfully applied for this task, albeit the fact that they ignore the inter-class relationships. In this paper, we propose a novel hierarchical classification method that generalizes Support Vector Machine learning and that is based on discriminant functions that are structured in a way that mirrors the class hierarchy. Our method can work with arbitrary, not necessarily singly connected taxonomies and can deal with task-specific loss functions. All parameters are learned jointly by optimizing a common objective function corresponding to a regularized upper bound on the empirical loss. We present experimental results on the WIPO-alpha patent collection to show the competitiveness of our approach.

REFERENCES

• 1: A. Cardoso-Cachopo and A. L. Oliveira. An empirical comparison of text categorization methods. In Proceedings of the 10th International Symposium on String Processing and Information Retrieval (SPIRE'03), number 2857 in Lecture Notes in Computer Science, pages 183--196. Springer Verlag, 2003.
• 2: Soumen Chakrabarti , Byron Dom , Rakesh Agrawal , Prabhakar Raghavan, Using Taxonomy, Discriminants, and Signatures for Navigating in Text Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.446-455, August 25-29, 1997
• 3: Koby Crammer , Yoram Singer, On the algorithmic implementation of multiclass kernel-based vector machines, The Journal of Machine Learning Research, 2, 3/1/2002
• 4: Susan Dumais , Hao Chen, Hierarchical classification of Web content, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345593]
• 5: 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
• 6: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 7: David D. Lewis, Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval, Proceedings of the 10th European Conference on Machine Learning, p.4-15, April 21-23, 1998
• 8: Andrew McCallum , Ronald Rosenfeld , Tom M. Mitchell , Andrew Y. Ng, Improving Text Classification by Shrinkage in a Hierarchy of Classes, Proceedings of the Fifteenth International Conference on Machine Learning, p.359-367, July 24-27, 1998
• 9: D. Mladenić and M. Grobelnik. Feature selection for classification based on text hierarchy. In Proceedings of the Conference on Automated Learning and Discovery, 1998.
• 10: Miguel E. Ruiz , Padmini Srinivasan, Hierarchical Text Categorization Using Neural Networks, Information Retrieval, v.5 n.1, p.87-118, January 2002 [doi>10.1023/A:1012782908347]
• 11: 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]
• 12: Robert E. Schapire , Yoram Singer , Amit Singhal, Boosting and Rocchio applied to text filtering, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.215-223, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290996]
• 13: Aixin Sun , Ee-Peng Lim, Hierarchical Text Classification and Evaluation, Proceedings of the 2001 IEEE International Conference on Data Mining, p.521-528, November 29-December 02, 2001
• 14: Kristina Toutanova , Francine Chen , Kris Popat , Thomas Hofmann, Text classification in a hierarchical mixture model for small training sets, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502604]
• 15: Ioannis Tsochantaridis , Thomas Hofmann , Thorsten Joachims , Yasemin Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the twenty-first international conference on Machine learning, p.104, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015341]
• 16: R. J. Vanderbei. LOQO: An interior point code for quadratic programming. Optimization Methods and Software, 11:451--484, 1999.
• 17: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 18: Ke Wang , Senqiang Zhou , Shiang Chen Liew, Building Hierarchical Classifiers Using Class Proximity, Proceedings of the 25th International Conference on Very Large Data Bases, p.363-374, September 07-10, 1999
• 19: Andreas S. Weigend , Erik D. Wiener , Jan O. Pedersen, Exploiting Hierarchy in Text Categorization, Information Retrieval, v.1 n.3, p.193-216, October 1999 [doi>10.1023/A:1009983522080]
• 20: J. Weston and C. Watkins. Multi-class support vector machines. Technical Report CSD-TR-98-04, Department of Computer Science, Royal Holloway, University of London, 1998.
• 21: World Intellectual Property Organization. International patent classification. URL, 2001. http://www.wipo.int/classifications/en/.
• 22: World Intellectual Property Organization. Wipo-alpha sataset. URL, 2003. http://www.wipo.int/ibis/datasets.
• 23: 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
• 24: 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]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Experimentation, Theory

Keywords:
SVM, class relationship, document categorization, hierarchical loss, subspace optimization, taxonomy