Error-driven generalist+experts (edge): a multi-stage ensemble framework for text categorization

ABSTRACT

We introduce a multi-stage ensemble framework, Error-Driven Generalist+Expert or Edge, for improved classification on large-scale text categorization problems. Edge first trains a generalist, capable of classifying under all classes, to deliver a reasonably accurate initial category ranking given an instance. Edge then computes a confusion graph for the generalist and allocates the learning resources to train experts on relatively small groups of classes that tend to be systematically confused with one another by the generalist. The experts' votes, when invoked on a given instance, yield a reranking of the classes, thereby correcting the errors of the generalist. Our evaluations showcase the improved classification and ranking performance on several large-scale text categorization datasets. Edge is in particular efficient when the underlying learners are efficient. Our study of confusion graphs is also of independent interest.

REFERENCES

• 1: 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]
• 2: Rich Caruana , Alexandru Niculescu-Mizil, Data mining in metric space: an empirical analysis of supervised learning performance criteria, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014063]
• 3: Vitor R. Carvalho , William W. Cohen, Single-pass online learning: performance, voting schemes and online feature selection, 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.1150466]
• 4: Koby Crammer , Ofer Dekel , Joseph Keshet , Shai Shalev-Shwartz , Yoram Singer, Online Passive-Aggressive Algorithms, The Journal of Machine Learning Research, 7, p.551-585, 12/1/2006
• 5: Koby Crammer , Yoram Singer, A family of additive online algorithms for category ranking, The Journal of Machine Learning Research, 3, 3/1/2003
• 6: 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]
• 7: 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]
• 8: A. Esuli, T. Fagni, and F. Sebastiani. TreeBoost.MH: A boosting algorithm for multi-label hierarchical text categorization. In Proc of 13th Int'l Conf on String Processing and Information Retrieval (SPIRE), 2006.
• 9: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 10: Yoav Freund , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, Using and combining predictors that specialize, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.334-343, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258616]
• 11: Shantanu Godbole , Sunita Sarawagi , Soumen Chakrabarti, Scaling multi-class support vector machines using inter-class confusion, 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.775122]
• 12: William Hersh , Chris Buckley , T. J. Leone , David Hickam, OHSUMED: an interactive retrieval evaluation and new large test collection for research, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.192-201, July 03-06, 1994, Dublin, Ireland
• 13: S. Sathiya Keerthi , Dennis DeCoste, A Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs, The Journal of Machine Learning Research, 6, p.341-361, 12/1/2005
• 14: 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
• 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: O. Madani and M. Connor. Large-scale many-class learning. In SIAM Conf on Data Mining (SDM), 2008.
• 17: O. Madani, W. Greiner, D. Kempe, and M. R. Salavatipour. Recall systems: Efficient learning and use of category indices. In Proceedings of the 11th International Conference on Artificial Intelligence and Statistics (AISTATS), 2007.
• 18: Omid Madani , Jian Huang, On updates that constrain the features' connections during learning, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401954]
• 19: M. E. J. Newman. Mixing patterns in networks. Physical Review E, 67:026126, 2003.
• 20: J. Rennie, L. Shih, J. Teevan, and D. Karger. Tackling the poor assumptions of naive Bayes text classifiers. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 616--623, 2003.
• 21: Ryan Rifkin , Aldebaro Klautau, In Defense of One-Vs-All Classification, The Journal of Machine Learning Research, 5, p.101-141, 12/1/2004
• 22: F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 56(6):386--408, 1958.
• 23: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]
• 24: 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]
• 25: K. Tumer and J. Ghosh. Analysis of decision boundaries in linearly combined neural classifiers. Pattern Recognition, 29(2):341--348, 1996.
• 26: K. Tumer and J. Ghosh. Robust combining of disparate classifiers through order statistics. Pattern Analysis & Applications, 5(2):189--200, 2002.
• 27: D. J. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.
• 28: David H. Wolpert, Stacked generalization, Neural Networks, v.5 n.2, p.241-259, 1992 [doi>10.1016/S0893-6080(05)80023-1]
• 29: L. Xu, A. Krzyzak, and C. Y. Suen. Methods of combining multiple classifiers and their applications to handwriting recognition. IEEE Transactions on Systems, Man and Cybernetics, 22(3):418--435, 1992.
• 30: Yiming Yang, An Evaluation of Statistical Approaches to Text Categorization, Information Retrieval, v.1 n.1-2, p.69-90, 1999 [doi>10.1023/A:1009982220290]
• 31: Yiming Yang , Jian Zhang , Bryan Kisiel, A scalability analysis of classifiers in text categorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860455]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
ensemble learning, many class classification, text categorization