Skip to Main content Skip to Navigation

Generalization Performance of Margin Multi-category Classifiers

Khadija Musayeva 1
1 ABC - Machine Learning and Computational Biology
LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : This thesis deals with the theory of margin multi-category classification, and is based on the statistical learning theory founded by Vapnik and Chervonenkis. We are interested in deriving generalization bounds with explicit dependencies on the number C of categories, the sample size m and the margin parameter gamma, when the loss function considered is a Lipschitz continuous margin loss function. Generalization bounds rely on the empirical performance of the classifier as well as its "capacity". In this work, the following scale-sensitive capacity measures are considered: the Rademacher complexity, the covering numbers and the fat-shattering dimension. Our main contributions are obtained under the assumption that the classes of component functions implemented by a classifier have polynomially growing fat-shattering dimensions and that the component functions are independent. In the context of the pathway of Mendelson, which relates the Rademacher complexity to the covering numbers and the latter to the fat-shattering dimension, we study the impact that decomposing at the level of one of these capacity measures has on the dependencies on C, m and gamma. In particular, we demonstrate that the dependency on C can be substantially improved over the state of the art if the decomposition is postponed to the level of the metric entropy or the fat-shattering dimension. On the other hand, this impacts negatively the rate of convergence (dependency on m), an indication of the fact that optimizing the dependencies on the three basic parameters amounts to looking for a trade-off.
Document type :
Complete list of metadata

Cited literature [95 references]  Display  Hide  Download
Contributor : Thèses Ul <>
Submitted on : Friday, November 29, 2019 - 3:53:20 PM
Last modification on : Sunday, December 1, 2019 - 1:19:02 AM


Files produced by the author(s)


  • HAL Id : tel-02387124, version 1


Khadija Musayeva. Generalization Performance of Margin Multi-category Classifiers. Machine Learning [cs.LG]. Université de Lorraine, 2019. English. ⟨NNT : 2019LORR0096⟩. ⟨tel-02387124⟩



Record views


Files downloads