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.
Type de document :
[Research Report] RR-5314, INRIA. 2004, pp.49
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 20 septembre 2006 - 10:10:36
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51
Document(s) archivé(s) le : lundi 20 septembre 2010 - 16:07:30



  • 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〉



Consultations de la notice


Téléchargements de fichiers