Ecole Doctorale
Mathématiques et Informatique de Marseille
Spécialité
Informatique
Etablissement
Aix-Marseille Université
Mots Clés
approximation de Nyström,Ridge Leverage Scores,accélération méthodes à noyaux,Frank-Wolfe,representation parcimonieuse,élagage de forêts aléatoires
Keywords
Nyström approximation,Ridge Leverage Scores,fast kernel methods,Frank-Wolfe,sparse representation,prunning random forest
Titre de thèse
échantillonnage pour laccélération des méthodes à noyaux et sélection gloutonne pour les représentations parcimonieuses.
sampling for fast kernel methods and greedy selection for sparse representation.
Date
Lundi 11 Juillet 2022 à 14:00
Adresse
3 Place Victor Hugo, 13003 Marseille Amphi science naturelle
Jury
Directeur de these |
M. LIVA RALAIVOLA |
Aix-Marseille université |
Rapporteur |
M. Charles SOUSSEN |
CentraleSupélec |
Rapporteur |
M. Massih-Reza AMINI |
Université Grenoble Alpes |
Examinateur |
M. Matthieu KOWALSKI |
Université Paris-Sud |
Examinateur |
Mme Elisa FROMONT |
Université de Rennes 1 |
Examinateur |
Mme Cécile CAPPONI |
Aix-Marseille université |
CoDirecteur de these |
Mme Sandrine ANTHOINE |
CNRS |
Examinateur |
M. Thomas PEEL |
GSK |
Résumé de la thèse
Les contributions de cette thèse sont divisées en deux parties. Une première partie dédiée à laccélération des méthodes à noyaux et une seconde à loptimisation avec contrainte de parcimonie.
Les méthodes à noyaux sont largement connues et utilisées en apprentissage automatique. Toutefois, elles deviennent inutilisables lorsque le nombre de données est grand. Nous proposons dans un premier temps une approximation des Ridge Leverage Scores. Nous utilisons ensuite ces scores pour définir une distribution de probabilité pour la méthode de Nyström afin daccélérer les méthodes à noyaux. Nous proposons dans un second temps un nouveau framework basé sur les noyaux, permettant de représenter et de comparer les distributions de probabilités. Nous exploitons ensuite le lien entre notre framework et la Maximum Mean Discrepancy pour proposer une approximation précise et moins coûteuse de cette dernière.
La deuxième partie de cette thèse est consacrée à loptimisation avec contrainte de parcimonie pour lapproximation de signaux et lélagage de forêts aléatoires. Tout dabord, nous prouvons sous certaines conditions sur la cohérence du dictionnaire, les propriétés de reconstruction et de convergence de lalgorithme Frank-Wolfe. Enfin, nous utilisons l'algorithme OMP pour réduire la taille de forêts aléatoires. La forêt élaguée est constituée dun sous-ensemble darbres de la forêt initiale sélectionnés et pondérés par OMP de manière à minimiser son erreur empirique de prédiction.
Thesis resume
The contributions of this thesis are divided into two parts. The first part is dedicated to the acceleration of kernel methods and the second to optimization under sparsity constraints.
Kernel methods are widely known and used in machine learning. However, the complexity of their implementation is high and they become unusable when the number of data is large. We first propose an approximation of Ridge Leverage Scores. We then use these scores to define a probability distribution for the sampling process of the Nyström method in order to speed up the kernel methods. We then propose a new kernel-based framework for representing and comparing discrete probability distributions. We then exploit the link between our framework and the Maximum Mean Discrepancy to propose an accurate and fast approximation of the latter.
The second part of this thesis is devoted to optimization with sparsity constraint for signal optimization and random forest pruning. First, we prove under certain conditions on the coherence of the dictionary, the reconstruction and convergence properties of the Frank-Wolfe algorithm. Then, we use the OMP algorithm to reduce the size of random forests and thus reduce the size needed for its storage. The pruned forest consists of a subset of trees from the initial forest selected and weighted by OMP in order to minimize its empirical prediction error.