Large Margin DAG's for Multiclass Classification
John C. Platt, Nello Cristianini, John S. Shawe-Taylor · 1999
We present a new learning architecture: the Decision Directed Acyclic Graph (DDAG), which is used to combine many two-class classifiers into a multiclass classifier. For an-class problem, the DDAG contains � classifiers, one for each pair of classes. We present a VC analysis of the case when the node classifiers are hyperplanes; the resulting bound on the test error depends on and on the margin achieved at the nodes, but not on the dimension of the space. This motivates an algorithm, DAGSVM, which operates in a kernel-induced feature space and uses two-class maximal margin hyperplanes at each decision-node of the DDAG. The DAGSVM is substantially faster to train and evaluate than either the standard algorithm or Max Wins, while maintaining comparable accuracy to both of these algorithms. 1
Cited by 1,631 works.
Authors
References
- Statistical Learning Theory
- UCI Repository of machine learning databases
- Estimation of Dependences Based on Empirical Data
- Fast Training of Support Vector Machines Using Sequential Minimal Optimization
- Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms
- Pairwise Classification and Support Vector Machines
- Another approach to polychotomous classification
- Single-layer learning revisited: a stepwise procedure for building and training a neural network
- Enlarging the Margins in Perceptron Decision Trees
- Data Dependent Structural Risk Minimization for Perceptron Decision Trees