Le lundi 23 septembre à 09h30 en salle C005 au Loria. La soutenance aura lieu en anglais.

Rapporteurs :
Sana Louhichi, Professeur, Université de Grenoble Alpes
Younès Bennani, Professeur, Université Paris 13

Examinateurs :
Anne Boyer, Professeur, Université de Lorraine
Myriam Maumy-Bertrand, Maı̂tre de Conférences, Université de Strasbourg

Directeurs de thèse :
Yann Guermeur, Directeur de Recherche CNRS, Nancy
Fabien Lauer, Maı̂tre de Conférences, Université de Lorraine

Résumé :

Cette thèse porte sur la théorie de la discrimination multi-classe à marge. Elle a pour cadre la théorie statistique de l’apprentissage de Vapnik et Chervonenkis. L’objectif est d’établir des bornes de généralisation possédant une dépendances explicite au nombre C de catégories, à la taille m de l’échantillon et au paramètre de marge gamma, lorsque la fonction de perte considérée est une fonction de perte à marge possédant la propriété d’être lipschitzienne. La borne de généralisation repose sur la performance empirique du classifieur ainsi que sur sa “capacité”. Dans cette thèse, les mesures de capacité considérées sont les suivantes : la complexité de Rademacher,les nombres de recouvrement et la dimension fat-shattering. Nos principales contributions sont obtenues sous l’hypothèse que les classes de fonctions composantes calculées par le classifieur ont des dimensions fat-shattering polynomiales et que les fonctions composantes sont indépendantes.

Dans le contexte du schéma de calcul introduit par Mendelson, qui repose sur les relations entre les mesures de capacité évoquées plus haut (chaînage, résultats combinatoires…), nous étudions l’impact que la décomposition au niveau de l’une de ces mesures de capacité a sur les dépendances (de la borne de généralisation) à C, m et gamma. En particulier, nous démontrons que la dépendance à C peut être considérablement améliorée par rapport à l’état de l’art si la décomposition est reportée au niveau du nombre de recouvrement ou de la dimension fat-shattering. Ce changement peut affecter négativement le taux de convergence (dépendance à m), ce qui souligne le fait que l’optimisation par rapport aux trois paramètres fondamentaux se traduit par la recherche d’un compromis.

_______________

Title : “Generalization performance of margin multi-category classifiers”

Monday September 23 at 09h30 in room C005, Loria. The defense will be in English.

Referees:
Sana Louhichi, Professor, University of Grenoble Alpes
Younès Bennani, Professor, University of Paris 13

Examiners:
Anne Boyer, Professor, University of Lorraine
Myriam Maumy-Bertrand, Assistant Professor, University of Strasbourg

Advisors:
Yann Guermeur, Research Scientist CNRS, Nancy
Fabien Lauer, Assistant Professor, University of Lorraine

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 (guaranteed risks) 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.