HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Large Margin Multi-category Discriminant Models and Scale-sensitive Psi-dimensions

Yann Guermeur 1
1 MODBIO - Computational models in molecular biology
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In the context of discriminant analysis, Vapnik's statistical learning theory has mainly been developed in three directions: the computation of dichotomies with binary-valued functions, the computation of dichotomies with real-valued functions, and the computation of polychotomies with functions taking their values in finite sets. The case of classes of vector-valued functions used to compute polychotomies has seldom been considered independently, which is unsatisfactory, for three main reasons. First, this case encompasses the other ones, second, it cannot be treated appropriately through a naïve extension of the results devoted to the computation of dichotomies, third, it represents the situation most commonly met in practice. In this report, a new uniform convergence bound for large margin multi-class discriminant models is derived, which extends in a straightforward way a famous theorem by Bartlett. The capacity measure involved in this bound is a covering number. To bound from above this measure, original scale-sensitive extensions of the psi-dimensions are introduced. The covering numbers of interest can be bounded in terms of these dimensions thanks to generalizations of Sauer's lemma, as is illustrated in the specific case of the scale-sensitive Natarajan dimension. A bound on this latter dimension is then computed for the architecture of the multi-class SVMs.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, September 20, 2006 - 10:10:36 AM
Last modification on : Friday, February 4, 2022 - 3:34:36 AM
Long-term archiving on: : Monday, September 20, 2010 - 4:07:30 PM


  • HAL Id : inria-00070686, version 2



Yann Guermeur. Large Margin Multi-category Discriminant Models and Scale-sensitive Psi-dimensions. [Research Report] RR-5314, INRIA. 2004, pp.49. ⟨inria-00070686v2⟩



Record views


Files downloads