Scaling multi-class support vector machines using inter-class confusion

ABSTRACT

Support vector machines (SVMs) excel at two-class discriminative learning problems. They often outperform generative classifiers, especially those that use inaccurate generative models, such as the naïve Bayes (NB) classifier. On the other hand, generative classifiers have no trouble in handling an arbitrary number of classes efficiently, and NB classifiers train much faster than SVMs owing to their extreme simplicity. In contrast, SVMs handle multi-class problems by learning redundant yes/no (one-vs-others) classifiers for each class, further worsening the performance gap. We propose a new technique for multi-way classification which exploits the accuracy of SVMs and the speed of NB classifiers. We first use a NB classifier to quickly compute a confusion matrix, which is used to reduce the number and complexity of the two-class SVMs that are built in the second stage. During testing, we first get the prediction of a NB classifier and use that to selectively apply only a subset of the two-class SVMs. On standard benchmarks, our algorithm is 3 to 6 times faster than SVMs and yet matches or even exceeds their accuracy.

REFERENCES

• 1: Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers, Proceedings of the Seventeenth International Conference on Machine Learning, p.9-16, June 29-July 02, 2000
• 2: Soumen Chakrabarti , Byron Dom , Rakesh Agrawal , Prabhakar Raghavan, Scalable feature selection, classification and signature generation for organizing large text databases into hierarchical topic taxonomies, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.3, p.163-178, August 1998 [doi>10.1007/s007780050061]
• 3: T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via ECOCs. JAIR, 2:263--286, 1995.
• 4: 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]
• 5: Rayid Ghani, Using Error-Correcting Codes for Text Classification, Proceedings of the Seventeenth International Conference on Machine Learning, p.303-310, June 29-July 02, 2000
• 6: Shantanu Godbole. Exploiting confusion matrices for automatic generation of topic hierarchies and scaling up multi-way classifiers. Technical Report, IIT Bombay, 2002. http://www.it.iitb.ac.in/~shantanu/work/aps2002.pdf
• 7: Ryan Rifkin and Jason D. M. Rennie. Improving multi-class text classification with the support vector machine, AI Memo, AIM-2001-026, MIT, 2001.
• 8: Thorsten Joachims, A statistical learning learning model of text classification for support vector machines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.128-136, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383974]
• 9: 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
• 10: Ulrich H.-G. Kreßel, Pairwise classification and support vector machines, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 11: T. M. Mitchell. Conditions for the equivalence of hierarchical and non-hierarchical Bayesian classifiers. Technical note, 1998. Online at http://www.cs.cmu.edu/~tom/hierproof.ps
• 12: J. Platt, N. Cristianini, and J. Shawe-Taylor. Large margin DAGs for multiclass classification. In Advances in NIPS 12, MIT Press, 2000.
• 13: M. F. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.
• 14: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Measurement, Performance