Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithms
This paper studies the generalization performance of multi-class classification algorithms, for which we obtain, for the first time, a data-dependent generalization error bound with a logarithmic dependence on the class size, substantially improving the state-of-the-art linear dependence in the existing data-dependent generalization analysis. The theoretical analysis motivates us to introduce a new multi-class classification machine based on $\ell_p$-norm regularization, where the parameter $p$ controls the complexity of the corresponding bounds. We derive an efficient optimization algorithm based on Fenchel duality theory. Benchmarks on several real-world datasets show that the proposed algorithm can achieve significant accuracy gains over the state of the art.
Code (0)
등록된 구현이 없습니다.
Tasks
General ClassificationGeneralization BoundsMulti-class ClassificationSimilar Papers 제목 키워드 기반
Mean field variational Bayesian inference for support vector machine classification
A mean field variational Bayes approach to support vector machines (SVMs) using the latent variable representation on Polson & Scott (2012) is presented. This representation allows circumvention of many of the shortcomin…
Bayesian InferenceClassificationGeneral ClassificationVariable SelectionDistributed Optimization of Multi-Class SVMs
Training of one-vs.-rest SVMs can be parallelized over the number of classes in a straight forward way. Given enough computational resources, one-vs.-rest SVMs can thus be trained on data involving a large number of clas…
Image ClassificationSignature Verification Approach using Fusion of Hybrid Texture Features
In this paper, a writer-dependent signature verification method is proposed. Two different types of texture features, namely Wavelet and Local Quantized Patterns (LQP) features, are employed to extract two kinds of trans…
Joint calibration of Ensemble of Exemplar SVMs
We present a method for calibrating the Ensemble of Exemplar SVMs model. Unlike the standard approach, which calibrates each SVM independently, our method optimizes their joint performance as an ensemble. We formulate jo…
object-detectionObject Detection$p$SVM: Soft-margin SVMs with $p$-norm Hinge Loss
Support Vector Machines (SVMs) based on hinge loss have been extensively discussed and applied to various binary classification tasks. These SVMs achieve a balance between margin maximization and the minimization of slac…
Binary ClassificationMulti-class Classification