On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines

Koby CrammerYoram Singer

article2002JMLR2,385 citations

Develops a direct multiclass support vector machine framework based on a generalized margin that reduces large-scale quadratic optimization into small, single-example subproblems solved via a provably convergent fixed-point algorithm.

Listen

Many real-world machine learning systems must categorize data into more than two classes, such as recognizing digits, characters, or objects. Standard practice typically splits a multiclass problem into multiple independent two-class problems (such as 'one-against-the-rest'). However, this indirect strategy ignores natural correlations between classes and requires training and coordinating multiple separate models.

The article demonstrates a direct multiclass support vector machine (SVM) framework that solves the categorization problem in a single unified formulation. The objective was to design a computationally efficient training algorithm and prove its practical viability and accuracy on large, complex datasets.

The authors evaluated the framework through theoretical analysis and empirical benchmarking across standard machine learning datasets, including the MNIST optical character recognition benchmark containing 60,000 training and 10,000 test examples, as well as UCI repository benchmarks. The approach decomposes the large dual optimization problem into small single-example subproblems, which are solved via an iterative, provably convergent fixed-point routine combined with computational techniques such as active set tracking, cooling schedules, caching, and sparse data structures.

The findings show that the proposed direct multiclass SVM achieves state-of-the-art accuracy, consistently matching or exceeding standard one-against-the-rest SVM baselines across multiple benchmarks. Incorporating algorithmic enhancements sped up training by two orders of magnitude compared to the baseline implementation, completing MNIST training in under 3.5 hours compared to tens of hours for traditional multiclass ensembles. Furthermore, the model's learned distribution weights identify difficult or corrupted examples, providing an automated tool for data cleaning.

These results demonstrate that direct multiclass modeling can reduce system complexity and infrastructure costs without sacrificing categorization accuracy. Faster training cycles shorten deployment timelines for complex pattern recognition tasks and eliminate the operational friction of synchronizing dozens of independent binary models.

Organizations handling multiclass pattern recognition should consider adopting direct multiclass kernel formulations over independent binary ensembles, particularly for high-dimensional or multi-category applications. For large-scale implementations, engineers should deploy active set caching and sparse input representations to maximize throughput. Future efforts should focus on extending this direct prototype architecture to regression, ranking, and real-time online learning workflows.

Confidence in these findings is high for balanced classification tasks based on extensive experimental validation. However, decision-makers should exercise caution on severely class-imbalanced datasets—such as Shuttle, where boosted decision trees outperformed this formulation—and ensure appropriate kernel selection through validation.

The Hebrew University of Jerusalem binary classification constrained optimization problems optimization Multiclass Vector Vector Machines

fated/mcsvm Crammer et al (2002).pdf

Paper: A training algorithm for optimal margin classifiers, B. Boser et al. (1992). Read this foundational paper first to master the margin-maximization principles and dual optimization techniques that directly enable multiclass support vector machines.
Paper: Support-vector networks, Corinna Cortes et al. (1995). Read this essential study first to understand the quadratic optimization decomposition methods that form the computational basis for training large-margin kernel machines.

Paper: Random Features for Large-Scale Kernel Machines, Ali Rahimi et al. (2007). Read this paper next to discover how random feature mappings overcome the scaling bottlenecks of exact kernel machines by enabling fast linear training.

Cover for On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines

Abstract

In this paper we describe the algorithmic implementation of multiclass kernel-based vector machines. Our starting point is a generalized notion of the margin to multiclass problems. Using this notion we cast multiclass categorization problems as a constrained optimization problem with a quadratic objective function. Unlike most of previous approaches which typically decompose a multiclass problem into multiple independent binary classification tasks, our notion of margin yields a direct method for training multiclass predictors. By using the dual of the optimization problem we are able to incorporate kernels with a compact set of constraints and decompose the dual problem into multiple optimization problems of reduced size. We describe an efficient fixed-point algorithm for solving the reduced optimization problems and prove its convergence. We then discuss technical details that yield significant running time improvements for large datasets. Finally, we describe various experiments with our approach comparing it to previously studied kernel-based methods. Our experiments indicate that for multiclass problems we attain state-of-the-art accuracy.

Topics

binary classification constrained optimization problems optimization kernel based methods multi-class problems

Keywords

Multiclass Vector Vector Machines Multiclass Kernel-based Vector Algorithm Kernel-based Vector Machines Set Optimization Problem Using Support Vector

1. Introduction
2. Preliminaries
3. Constructing multiclass kernel-based predictors
4. Decomposing the optimization problem
5. Example selection for optimization
6. Solving the reduced optimization problem
7. Implementation details
8. Experiments
9. Summary
Acknowledgments
Appendix A. Derivation of the dual optimization problem
References

Knowls

Knowl 1 — Multiclass Support Vector Machine Primal Formulation
model/method
Let $S = \{(\bar{x}_1, y_1), \dots, (\bar{x}_m, y_m)\}$ be a training set where each input vector $\bar{x}_i \in \mathbb{R}^n$ and each class label $y_i \in \{1, \dots, k\}$ . A multiclass linear predictor is defined by a prototype matrix $M \in \mathbb{R}^{k \times n}$ with row vectors $\bar{M}_r \in \mathbb{R}^n$ ( $r = 1, \dots, k$ ), assigning a label according to:

$H_M(\bar{x}) = \arg\max_{r=1}^k \{\bar{M}_r \cdot \bar{x}\}$

To construct large-margin multiclass classifiers, the empirical classification loss of each instance is upper-bounded by $\max_r \{\bar{M}_r \cdot \bar{x}_i + 1 - \delta_{y_i, r}\} - \bar{M}_{y_i} \cdot \bar{x}_i$ , where $\delta_{p,q} = 1$ if $p = q$ and $0$ otherwise. Incorporating $m$ non-negative slack variables $\xi_1, \dots, \xi_m$ , the soft-margin primal quadratic program is:

$\min_{M, \xi} \frac{1}{2}\beta \|M\|_2^2 + \sum_{i=1}^m \xi_i \quad \text{subject to } \forall i \in \{1,\dots,m\}, \forall r \in \{1,\dots,k\}: \bar{M}_{y_i} \cdot \bar{x}_i + \delta_{y_i, r} - \bar{M}_r \cdot \bar{x}_i \ge 1 - \xi_i$

where $\beta > 0$ is a regularization parameter and $\|M\|_2^2 = \sum_{r=1}^k \|\bar{M}_r\|_2^2$ . For $r = y_i$ , the constraint automatically simplifies to $\xi_i \ge 0$ . Unlike binary reduction frameworks that use $m(k-1)$ slack variables, this primal problem maintains exactly one slack variable per training instance.
Knowl 2 — Dual Formulation of Multiclass Kernel Vector Machines
model/method
Let $K(\bar{x}_i, \bar{x}_j)$ be a Mercer kernel computing inner products in a feature space. Introducing dual variables $\eta_{i,r} \ge 0$ satisfying $\sum_{r=1}^k \eta_{i,r} = 1$ for each instance $i$ , and performing the variable substitution $\bar{\tau}_i = \bar{1}_{y_i} - \bar{\eta}_i \in \mathbb{R}^k$ (where $\bar{1}_{y_i}$ is the unit coordinate vector with a $1$ at index $y_i$ ), the dual optimization problem of the multiclass support vector machine is:

$\max_{\tau} Q(\tau) = -\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m K(\bar{x}_i, \bar{x}_j) (\bar{\tau}_i \cdot \bar{\tau}_j) + \beta \sum_{i=1}^m \bar{\tau}_i \cdot \bar{1}_{y_i}$ $\text{subject to } \forall i \in \{1, \dots, m\}: \bar{\tau}_i \le \bar{1}_{y_i} \quad \text{and} \quad \bar{\tau}_i \cdot \bar{1} = 0$

where $\bar{1} \in \mathbb{R}^k$ is the all-ones vector and $\beta > 0$ is the regularization constant. Each prototype vector $\bar{M}_r$ satisfies $\bar{M}_r = \beta^{-1} \sum_{i=1}^m \tau_{i,r} \bar{x}_i$ , and the kernel-based classification decision rule becomes:

$H(\bar{x}) = \arg\max_{r=1}^k \sum_{i=1}^m \tau_{i,r} K(\bar{x}, \bar{x}_i)$
Knowl 3 — Single-Example Decomposition of the Multiclass Dual Problem
model/method
The dual multiclass optimization problem over $m k$ variables can be decomposed into $m$ independent subproblems because its constraints partition across examples into disjoint constraint sets $\{\bar{\tau}_i \mid \bar{\tau}_i \le \bar{1}_{y_i}, \bar{\tau}_i \cdot \bar{1} = 0\}$ . Fixing all dual vectors $\bar{\tau}_i$ for $i \ne p$ , the subproblem for example $p$ minimizes a quadratic objective with $k$ variables and $k+1$ constraints:

$\min_{\bar{\tau}_p} \frac{1}{2} A_p (\bar{\tau}_p \cdot \bar{\tau}_p) + \bar{B}_p \cdot \bar{\tau}_p \quad \text{subject to } \bar{\tau}_p \le \bar{1}_{y_p} \text{ and } \bar{\tau}_p \cdot \bar{1} = 0$

where $A_p = K(\bar{x}_p, \bar{x}_p) > 0$ and $\bar{B}_p = \sum_{i \ne p} K(\bar{x}_i, \bar{x}_p) \bar{\tau}_i - \beta \bar{1}_{y_p} \in \mathbb{R}^k$ .

Under the change of variables $\bar{\nu} = \bar{\tau}_p + \frac{\bar{B}_p}{A_p}$ and $\bar{D} = \frac{\bar{B}_p}{A_p} + \bar{1}_{y_p}$ , the subproblem is transformed into finding the Euclidean projection of the origin onto a simplex-like polyhedron:

$\min_{\bar{\nu}} \|\bar{\nu}\|_2^2 \quad \text{subject to } \bar{\nu} \le \bar{D} \text{ and } \bar{\nu} \cdot \bar{1} = \bar{D} \cdot \bar{1} - 1$
Knowl 4 — Exact Characterization and Optimality of the Reduced Quadratic Subproblem
theoretical result
For any target vector $\bar{D} \in \mathbb{R}^k$ , let the optimization problem be defined as $\min_{\bar{\nu}} \|\bar{\nu}\|_2^2$ subject to $\bar{\nu} \le \bar{D}$ and $\bar{\nu} \cdot \bar{1} = \bar{D} \cdot \bar{1} - 1$ .

The unique optimal solution $\bar{\nu}^* \in \mathbb{R}^k$ satisfies:

$\nu_r^* = \min\{\theta^*, D_r\} \quad \text{for } r = 1, \dots, k$

where $\theta^* \in \mathbb{R}$ is the unique root of the strictly monotonic, continuous scalar equation:

$\sum_{r=1}^k \min\{\theta^*, D_r\} = \sum_{r=1}^k D_r - 1$

For any other feasible point $\bar{\nu} \ne \bar{\nu}^*$ , $\|\bar{\nu}\|_2^2 > \|\bar{\nu}^*\|_2^2$ holds strictly.
Knowl 5 — Fixed-Point Algorithm for Solving the Reduced Subproblem
algorithm
By applying the identity $\min\{\theta, D_r\} + \max\{\theta, D_r\} = \theta + D_r$ , the threshold $\theta^*$ for the optimal subproblem solution satisfies the fixed-point equation $\theta^* = F(\theta^*)$ where $F(\theta) = \frac{1}{k} \sum_{r=1}^k \max\{\theta, D_r\} - \frac{1}{k}$ .

The fixed-point algorithm computes $\theta^*$ through successive substitutions:
FixedPointAlgorithm(D, theta_1, epsilon)
  Input: Vector D in R^k, initial scalar theta_1 <= max_r D_r, tolerance epsilon > 0
  Output: Subproblem optimal update vector tau in R^k
  l = 0
  repeat
    l = l + 1
    theta_{l+1} = (1 / k) * sum_{r=1}^k max(theta_l, D_r) - (1 / k)
  until |theta_l - theta_{l+1}| / |theta_l| <= epsilon
  for r = 1 to k do
    nu_r = min(theta_{l+1}, D_r)
  end for
  tau = nu - B / A
  return tau
Setting $\theta_1 = \min_{r=1}^k D_r$ guarantees $\theta_1 \le \max_r D_r$ and gives $\theta_2 = \frac{1}{k} \sum_{r=1}^k D_r - \frac{1}{k}$ , which ensures fast early convergence.
Knowl 6 — Linear Convergence Rate of the Subproblem Fixed-Point Algorithm
theoretical result
Let $\theta^* \in \mathbb{R}$ be the unique fixed point satisfying $\theta^* = F(\theta^*)$ where $F(\theta) = \frac{1}{k} \sum_{r=1}^k \max\{\theta, D_r\} - \frac{1}{k}$ . If the sequence of iterates $\{\theta_l\}_{l=1}^\infty$ is generated via $\theta_{l+1} = F(\theta_l)$ starting from any initial suggestion $\theta_1 \le \max_{r=1}^k D_r$ , then for all iterations $l \ge 1$ :

$\frac{|\theta_{l+1} - \theta^*|}{|\theta_l - \theta^*|} \le 1 - \frac{1}{k}$

where $k$ is the number of classification classes. The convergence is strictly linear with a contraction factor bounded by $(1 - 1/k)$ .
Knowl 7 — KKT-Based Example Selection and Stopping Criterion
algorithm
For each training instance $i \in \{1, \dots, m\}$ and class label $r \in \{1, \dots, k\}$ , define the auxiliary confidence variables $F_{i,r} = \sum_{j=1}^m K(\bar{x}_i, \bar{x}_j) \tau_{j,r} - \beta \delta_{y_i, r}$ .

The Karush-Kuhn-Tucker (KKT) conditions for example $i$ are satisfied if and only if the violation parameter $\psi_i = 0$ , where:

$\psi_i = \max_{r=1}^k F_{i,r} - \min_{r : \tau_{i,r} < \delta_{y_i, r}} F_{i,r}$

The multiclass support vector machine training procedure iteratively identifies and optimizes the example with the highest violation until $\max_i \psi_i < \epsilon \beta$ :
MulticlassSVMTrain(S, beta, epsilon)
  Input: S = {(x_1, y_1), ..., (x_m, y_m)}, regularization beta > 0, tolerance epsilon > 0
  Output: Dual variables tau_1, ..., tau_m in R^k
  for i = 1 to m do
    tau_i = 0 in R^k
    for r = 1 to k do
      F_{i,r} = -beta * delta_{r, y_i}
    end for
    A_i = K(x_i, x_i)
  end for
  repeat
    for i = 1 to m do
      psi_i = max_r F_{i,r} - min_{r : tau_{i,r} < delta_{y_i, r}} F_{i,r}
    end for
    p = argmax_i {psi_i}
    if psi_p < epsilon * beta then
      break
    end if
    for r = 1 to k do
      D_r = F_{p,r} / A_p - tau_{p,r} + delta_{r, y_p}
    end for
    theta_1 = (1 / k) * sum_{r=1}^k D_r - (1 / k)
    tau_p_new = FixedPointAlgorithm(D, theta_1, epsilon / 2)
    Delta_tau_p = tau_p_new - tau_p
    for i = 1 to m do
      for r = 1 to k do
        F_{i,r} = F_{i,r} + Delta_tau_{p,r} * K(x_p, x_i)
      end for
    end for
    tau_p = tau_p_new
  until false
  return tau
Knowl 8 — Algorithmic Acceleration via Active Sets, Accuracy Cooling, and Caching
model/method
Three primary algorithmic enhancements enable the multiclass decomposition algorithm to scale to large datasets:
1. Active Set Maintenance: Examples are divided into an active set $\mathcal{A} = \{i \mid \bar{\tau}_i \ne \bar{0}\}$ and inactive set $\mathcal{A}^c = \{i \mid \bar{\tau}_i = \bar{0}\}$ . The main loop updates examples strictly within $\mathcal{A}$ until $\forall i \in \mathcal{A}, \psi_i < \epsilon$ . Only then is $\mathcal{A}^c$ scanned to identify new violators $(\psi_p > \epsilon)$ to add to $\mathcal{A}$ .
2. Accuracy Parameter Cooling: To avoid slow convergence caused by premature fine-tuning of support pattern weights, the tolerance parameter is scheduled dynamically starting from $\epsilon_0 = 0.999$ . A logarithmic cooling schedule $\epsilon(t) = \epsilon_0 / \log_{10}(t + 10)$ (where $t$ is the iteration index) keeps $\epsilon(t)$ large initially to rapidly populate $\mathcal{A}$ , reducing overall optimization iterations by up to an order of magnitude.
3. Kernel Caching and Sparse Storage: Inner products are maintained in a cache managed by a Least-Recently-Used (LRU) eviction strategy. Instances are stored as sparse linked lists, which yields both memory and execution time speedups whenever input instance sparsity exceeds 20%.
Combined, these improvements reduce overall training time by over two orders of magnitude relative to naive sequential cycling.

Knowl 9 — Classification Accuracy of Multiclass SVM Compared to One-vs-Rest

empirical result

The direct multiclass support vector machine was evaluated against the standard one-against-rest (OvR) binary SVM decomposition across several benchmarks using Gaussian kernels (with $\beta$ and Gaussian bandwidth $\sigma$ tuned via cross-validation and stopping threshold $\epsilon = 0.001$ ). The direct multiclass formulation consistently matches or outperforms the OvR strawman, with substantial error rate reductions on datasets having high example-to-class ratios (e.g., Satimage, Shuttle, Letter, Vowel).

When evaluated on complete datasets, multiclass SVM achieved the following test error rates:

Additionally, evaluating on MNIST using a normalized polynomial kernel of degree 9 reduced test error to 1.24%.

Knowl 10 — Dual Distribution Interpretation of Support Patterns and Noise Detection
definition
For each training instance $\bar{x}_i$ , the vector $\bar{\eta}_i = \bar{1}_{y_i} - \bar{\tau}_i$ satisfies $\eta_{i,r} \ge 0$ and $\sum_{r=1}^k \eta_{i,r} = 1$ , functioning as a probability distribution over all class labels $\{1, \dots, k\}$ .
- Support Pattern Definition: An instance $\bar{x}_i$ is a support pattern if and only if $\bar{\eta}_i \ne \bar{1}_{y_i}$ (equivalently $\bar{\tau}_i \ne \bar{0}$ ), meaning its dual distribution is not fully concentrated on the true class $y_i$ .
- Confusable Classes: The non-zero components of $\bar{\eta}_i$ identify the specific classes that compete with the correct label $y_i$ for input $\bar{x}_i$ .
- Noise and Outlier Detection: Instances with a large $l_2$ -norm $\|\bar{\tau}_i\|_2$ correspond to patterns that attain a margin strictly less than $\beta$ . In practice, these instances correspond to corrupted inputs, ambiguous samples, or mislabeled training examples, allowing $\|\bar{\tau}_i\|_2$ to serve as an automated criterion for data cleaning.

Coverage note — Appendix A (algebraic derivation of the dual objective from the Lagrangian) was omitted as it constitutes intermediate mathematical derivation rather than standalone results.

References

1.E.L. Allwein, R.E. Schapire, and Y. Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. In Machine Learning: Proceedings of the Seventeenth International Conference, 2000.
2.Bernhard E. Boser, Isabelle M. Guyon, and Vladimir N. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, pages 144–152, 1992.
3.E. J. Bredensteiner and K. P. Bennet. Multicategory classification by support vector machines. Computational Optimizations and Applications, 12:53–79, 1999.
4.L. M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7:200–217, 1967.
5.Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Wadsworth & Brooks, 1984.
6.C.J.C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):1–47, 1998.
7.Yair Censor and Stavros A. Zenios. Parallel optimization: Theory, Algorithms and Applications. Oxford University Press, 1997.
8.Ronan Collobert and Samy Bengio. SVMtorch: Support vector machines for large-scale regression problems. Journal of Machine Learning Research, 1:143–160, 2001.
9.Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20(3): 273–297, September 1995.
10.Koby Crammer and Yoram Singer. On the learnability and design of output codes for multiclass problems. In Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, 2000.
11.Koby Crammer and Yoram Singer. Ultraconservative online algorithms for multiclass problems. In Proceedings of the Fourteenth Annual Conference on Computational Learning Theory, 2001.
12.Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge University Press, 2000.
13.Dennis DeCoste and Bernhard Schölkopf. Training invariant support vector machines. Machine Learning, 46(1–3):133–168, 2001.
14.Thomas G. Dietterich. An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization. Machine Learning, 40(2):139–158, 2000.
15.Thomas G. Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263–286, January 1995.
16.Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, August 1997.
17.Y. Guermeur, A. Elisseeff, and H. Paugam-Moisy. A new multi-class svm based on a uniform convergence result. In V. Piuri et al., editor, Proceedings of IJCNN-2000, 2000.
18.Klaus-U. Höffgen and Hans-U. Simon. Robust trainability of single neurons. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, pages 428–439, Pittsburgh, Pennsylvania, July 1992.
19.Thorsten Joachims. Making large-scale support vector machine learning practical. In B. Schölkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods - Support Vector Learning. MIT Press, 1998.
20.S.S. Keerthi and E.G. Gilbert. Convergence of a generalized smo algorithm for svm classifier design. Technical Report CD-00-01, Control Division Dept. of Mechanical and Production Engineering National University of Singapore, 2000.
21.C.-J. Lin. Stopping criteria of decomposition methods for support vector machines: a theoretical justification. Technical report, Depratment of Computer Science and Information Engineering, National Taiwan University, May 2001.
22.J.C. Platt. Fast training of Support Vector Machines using sequential minimal optimization. In B. Schölkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods - Support Vector Learning. MIT Press, 1998.
23.J.C. Platt, N. Cristianini, and J. Shawe-Taylor. Large margin DAGs for multiclass classification. In Advances in Neural Information Processing Systems 12, pages 547–553. MIT Press, 2000.
24.J. Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
25.Robert E. Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3):1–40, 1999.
26.B. Schölkopf. Support Vector Learning. PhD thesis, GMD First, 1997.
27.B. Schölkopf, C. Burges, and A. Smola, editors. Advances in Kernel Methods - Support Vector Learning. MIT Press, 1998.
28.B. Schölkopf, K. Sung, C. Burges, F. Girosi, P. Niyogi, T. Poggio, and V. Vapnik. Comparing support vector machines with Gaussian kernels to radial basis function classifiers. Technical Report A.I. Memo No. 1599, Massachusetts Institute of Techology, 1996.
29.Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998.
30.J. Weston and C. Watkins. Support vector machines for multi-class pattern recognition. In Proceedings of the Seventh European Symposium on Artificial Neural Networks, April 1999.

Citation

MLA

Crammer, K., and Y. Singer. “On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines”. Journal of Machine Learning Research, vol. 2, no. 2, 2002, pp. 265–92, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.334.5237.

APA

Crammer, K., & Singer, Y. (2002). On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research, 2(2), 265–292. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.334.5237

Chicago

Crammer, K., and Y. Singer. 2002. “On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines”. Journal of Machine Learning Research 2 (2): 265–92. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.334.5237.

Harvard

Crammer, K. and Singer, Y. (2002) “On the algorithmic implementation of multiclass kernel-based vector machines”, Journal of Machine Learning Research, 2(2), pp. 265–292. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.334.5237.

Vancouver

1. Crammer K, Singer Y (2002) On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research 2:265–292

BibTeX

@article{crammer2002the,
  title = {On the algorithmic implementation of multiclass kernel-based vector machines},
  author = {Crammer, Koby and Singer, Yoram},
  year = {2002},
  journal = {Journal of Machine Learning Research},
  volume = {2},
  number = {2},
  pages = {265-292},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.334.5237}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Dataset	Multiclass SVM Test Error (%)
MNIST	1.42
USPS	4.38
Shuttle	0.12
Letter	1.95

On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Multiclass Support Vector Machine Primal Formulation

Knowl 2 — Dual Formulation of Multiclass Kernel Vector Machines

Knowl 3 — Single-Example Decomposition of the Multiclass Dual Problem

Knowl 4 — Exact Characterization and Optimality of the Reduced Quadratic Subproblem

Knowl 5 — Fixed-Point Algorithm for Solving the Reduced Subproblem

Knowl 6 — Linear Convergence Rate of the Subproblem Fixed-Point Algorithm

Knowl 7 — KKT-Based Example Selection and Stopping Criterion