Refined experts: improving classification in large taxonomies

ABSTRACT

While large-scale taxonomies--especially for web pages--have been in existence for some time, approaches to automatically classify documents into these taxonomies have met with limited success compared to the more general progress made in text classification. We argue that this stems from three causes: increasing sparsity of training data at deeper nodes in the taxonomy, error propagation where a mistake made high in the hierarchy cannot be recovered, and increasingly complex decision surfaces in higher nodes in the hierarchy. While prior research has focused on the first problem, we introduce methods that target the latter two problems--first by biasing the training distribution to reduce error propagation and second by propagating up "first-guess" expert information in a bottom-up manner before making a refined top down choice. Finally, we present an empirical study demonstrating that the suggested changes lead to 10--30% improvements in F1 scores versus an accepted competitive baseline, hierarchical SVMs.

REFERENCES

• 1: Paul N. Bennett , Susan T. Dumais , Eric Horvitz, The Combination of Text Classifiers Using Reliability Indicators, Information Retrieval, v.8 n.1, p.67-100, January 2005 [doi>10.1023/B:INRT.0000048491.59134.94]
• 2: C. M. Bishop and M. Svensén. Bayesian hierarchical mixtures of experts. In UAI '03, 2003.
• 3: Lijuan Cai , Thomas Hofmann, Hierarchical document categorization with support vector machines, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031186]
• 4: Nicolò Cesa-Bianchi , Claudio Gentile , Luca Zaniboni, Hierarchical classification: combining Bayes with SVM, Proceedings of the 23rd international conference on Machine learning, p.177-184, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143867]
• 5: Nicolò Cesa-Bianchi , Claudio Gentile , Luca Zaniboni, Incremental Algorithms for Hierarchical Classification, The Journal of Machine Learning Research, 7, p.31-54, 12/1/2006
• 6: Ofer Dekel , Joseph Keshet , Yoram Singer, Large margin hierarchical classification, Proceedings of the twenty-first international conference on Machine learning, p.27, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015374]
• 7: Susan Dumais , Edward Cutrell , Hao Chen, Optimizing search by showing results in context, Proceedings of the SIGCHI conference on Human factors in computing systems, p.277-284, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365116]
• 8: 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]
• 9: 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
• 10: Michael I. Jordan , Robert A. Jacobs, Hierarchical mixtures of experts and the EM algorithm, Neural Computation, v.6 n.2, p.181-214, March 1994 [doi>10.1162/neco.1994.6.2.181]
• 11: A. R. Klivans and A. A. Sherstov. Improved lower bounds for learning intersections of halfspaces. In COLT '06, 2006.
• 12: 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
• 13: 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
• 14: Wei Li , Andrew McCallum, Pachinko allocation: DAG-structured mixture models of topic correlations, Proceedings of the 23rd international conference on Machine learning, p.577-584, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143917]
• 15: Tie-Yan Liu , Yiming Yang , Hao Wan , Hua-Jun Zeng , Zheng Chen , Wei-Ying Ma, Support vector machines classification with a very large-scale taxonomy, ACM SIGKDD Explorations Newsletter, v.7 n.1, p.36-43, June 2005 [doi>10.1145/1089815.1089821]
• 16: 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
• 17: David Mimno , Wei Li , Andrew McCallum, Mixtures of hierarchical topics with Pachinko allocation, Proceedings of the 24th international conference on Machine learning, p.633-640, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273576]
• 18: Netscape Communication Corporation. Open directory project. http://www.dmoz.org.
• 19: J. C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In Advances in Large Margin Classifiers, 1999.
• 20: 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]
• 21: Shai Shalev-Shwartz , Yoram Singer , Nathan Srebro, Pegasos: Primal Estimated sub-GrAdient SOlver for SVM, Proceedings of the 24th international conference on Machine learning, p.807-814, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273598]
• 22: 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
• 23: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 24: Gui-Rong Xue , Dikan Xing , Qiang Yang , Yong Yu, Deep classification in large-scale text hierarchies, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390440]
• 25: 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]
• 26: Benyu Zhang , Hua Li , Yi Liu , Lei Ji , Wensi Xi , Weiguo Fan , Zheng Chen , Wei-Ying Ma, Improving web search results using affinity graph, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076120]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms

Keywords:
large-scale hierarchy, text classification