Article

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

Authors:

Shantanu Godbole,

Sunita Sarawagi,

Soumen ChakrabartiAuthors Info & Claims

KDD '02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 513 - 518

https://doi.org/10.1145/775047.775122

Published: 23 July 2002 Publication History

Get Access

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]

E. L. Allwein, R. E. Schapire, and Y. Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. In 17th ICML, 2000.

Digital Library

Google Scholar

[2]

S. Chakrabarti, B. Dom, R. Agrawal, and P. Raghavan. Scalable feature selection, classification and signature generation for organizing large text databases into hierarchical topic taxonomies. The VLDB Journal, 1998.

Digital Library

Google Scholar

[3]

T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via ECOCs. JAIR, 2:263--286, 1995.

Digital Library

Google Scholar

[4]

S. Dumais, J. Platt, D. Heckerman, and M. Sahami Inductive learning algorithms and representations for text categorization. In 7th CIKM, 1998.

Digital Library

Google Scholar

[5]

Rayid Ghani. Using error-correcting codes for text classification. In 17th ICML, 2000.

Digital Library

Google Scholar

[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

Google Scholar

[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.

Google Scholar

[8]

T. Joachims. A statistical learning model of text classification for SVMs. In SIGIR 2001, volume 24, ACM.

Digital Library

Google Scholar

[9]

D. Koller and M. Sahami. Hierarchically classifying. documents using very few words. In 14th ICML, 1997.

Digital Library

Google Scholar

[10]

U. Kressel. Pairwise classification and support vector machines. In Advances in Kernel Methods: Support Vector Learning, MIT Press, 1999.

Digital Library

Google Scholar

[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

Google Scholar

[12]

J. Platt, N. Cristianini, and J. Shawe-Taylor. Large margin DAGs for multiclass classification. In Advances in NIPS 12, MIT Press, 2000.

Google Scholar

[13]

M. F. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.

Crossref

Google Scholar

[14]

V. N. Vapnik. The nature of statistical learning theory. Springer Verlag, 1995.

Digital Library

Google Scholar

Cited By

View all

Gao TChen HChen W(2022)MCMS-STM: An Extension of Support Tensor Machine for Multiclass Multiscale Object Recognition in Remote Sensing ImagesRemote Sensing10.3390/rs1401019614:1(196)Online publication date: 2-Jan-2022
https://doi.org/10.3390/rs14010196
Sunkara RSingh AKadambi GN P(2022)Hyperspectral Image Classification using Digital Signature Comparison based Classifier2022 IEEE International Conference on Distributed Computing and Electrical Circuits and Electronics (ICDCECE)10.1109/ICDCECE53908.2022.9793137(1-6)Online publication date: 23-Apr-2022
https://doi.org/10.1109/ICDCECE53908.2022.9793137
Noor T(2021)A service classification model for IoT services discoveryComputing10.1007/s00607-021-01007-8Online publication date: 30-Aug-2021
https://doi.org/10.1007/s00607-021-01007-8
Show More Cited By

Index Terms

Scaling multi-class support vector machines using inter-class confusion
1. Mathematics of computing

Recommendations

Boosting One-Class Support Vector Machines for Multi-Class Classification

AdaBoost.M1 has been successfully applied to improve the accuracy of a learning algorithm for multi-class classification problems. However, it may be hard to satisfy the required conditions in some practical cases. An improved algorithm called ...
Half-Against-Half multi-class support vector machines
MCS'05: Proceedings of the 6th international conference on Multiple Classifier Systems

A Half-Against-Half (HAH) multi-class SVM is proposed in this paper. Unlike the commonly used One-Against-All (OVA) and One-Against-One (OVO) implementation methods, HAH is built via recursively dividing the training dataset of K classes into two ...
Wagging for Combining Weighted One-class Support Vector Machines

Most of machine learning problems assume, that we have at our disposal objects originating from two or more classes. By learning from a representative training set a classifier is able to estimate proper decision boundaries. However, in many real-life ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

KDD '02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining

July 2002

719 pages

ISBN:158113567X

DOI:10.1145/775047

Conference Chair:
Osmar R. Zaïane
University of Alberta, Canada
,
General Chair:
Randy Goebel
University of Alberta, Canada
,
Program Chairs:
David Hand
Imperial College, UK
,
Daniel Keim
AT&T
,
Raymond Ng
University of British Columbia, Canada

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

KDD02

Sponsor:

KDD02: The Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

July 23 - 26, 2002

Alberta, Edmonton, Canada

Acceptance Rates

KDD '02 Paper Acceptance Rate 44 of 307 submissions, 14%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
710
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gao TChen HChen W(2022)MCMS-STM: An Extension of Support Tensor Machine for Multiclass Multiscale Object Recognition in Remote Sensing ImagesRemote Sensing10.3390/rs1401019614:1(196)Online publication date: 2-Jan-2022
https://doi.org/10.3390/rs14010196
Sunkara RSingh AKadambi GN P(2022)Hyperspectral Image Classification using Digital Signature Comparison based Classifier2022 IEEE International Conference on Distributed Computing and Electrical Circuits and Electronics (ICDCECE)10.1109/ICDCECE53908.2022.9793137(1-6)Online publication date: 23-Apr-2022
https://doi.org/10.1109/ICDCECE53908.2022.9793137
Noor T(2021)A service classification model for IoT services discoveryComputing10.1007/s00607-021-01007-8Online publication date: 30-Aug-2021
https://doi.org/10.1007/s00607-021-01007-8
Molitor DNeedell D(2019)Hierarchical Classification Using Binary DataAI Magazine10.1609/aimag.v40i2.284640:2(59-65)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1609/aimag.v40i2.2846
Chen ZSingla KGibson JCan DImel ZAtkins DGeorgiou PNarayanan S(2019)Improving the Prediction of Therapist Behaviors in Addiction Counseling by Exploiting Class ConfusionsICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP.2019.8682885(6605-6609)Online publication date: May-2019
https://doi.org/10.1109/ICASSP.2019.8682885
Seale MHines ANabholz GRuvinsky AEslinger ORigoni NVega-Maisonet L(2019)Approaches for Using Machine Learning Algorithms with Large Label Sets for Rotorcraft Maintenance2019 IEEE Aerospace Conference10.1109/AERO.2019.8742027(1-8)Online publication date: Mar-2019
https://doi.org/10.1109/AERO.2019.8742027
Cavalin POliveira L(2019)Confusion Matrix-Based Building of Hierarchical ClassificationProgress in Pattern Recognition, Image Analysis, Computer Vision, and Applications10.1007/978-3-030-13469-3_32(271-278)Online publication date: 3-Mar-2019
https://doi.org/10.1007/978-3-030-13469-3_32
Sun YWang LSun M(2017)Label-Driven Learning Framework: Towards More Accurate Bayesian Network Classifiers through Discrimination of High-Confidence LabelsEntropy10.3390/e1912066119:12(661)Online publication date: 3-Dec-2017
https://doi.org/10.3390/e19120661
Wang JLiu JKong L(2017)Ontology Construction Based on Deep LearningAdvances in Computer Science and Ubiquitous Computing10.1007/978-981-10-7605-3_83(505-510)Online publication date: 20-Dec-2017
https://doi.org/10.1007/978-981-10-7605-3_83
Wang YLi SKot A(2015)DeepBag: Recognizing Handbag ModelsIEEE Transactions on Multimedia10.1109/TMM.2015.248022817:11(2072-2083)Online publication date: Nov-2015
https://doi.org/10.1109/TMM.2015.2480228
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Boosting One-Class Support Vector Machines for Multi-Class Classification

Half-Against-Half multi-class support vector machines

Wagging for Combining Weighted One-class Support Vector Machines