Échantillonnage pour l’accélération des méthodes à noyaux et sélection gloutonne pour les représentations parcimonieuses

Thèse en préparation à Aix-Marseille , dans le cadre de Mathématiques et informatique de Marseille (184) , en partenariat avec Laboratoire d’informatique et systèmes (équipe de recherche Qarma) depuis le 25-09-2018 .

Membres du jury :
– Charles Soussen, CentraleSupélec, rapporteur
– Massih-Reza Amini, Université de Grenoble, rapporteur
– Cécile Capponi, Université d’Aix-Marseille, examinatrice
– Elisa Fromont, Université de Rennes 1, examinatrice
– Matthieu Kowalski, Université Paris-Sud, examinateur
– Liva Ralaivola, Université d’Aix-Marseille, directeur de thèse
– Sandrine Anthoine, Université d’Aix-Marseille, co-directrice de thèse
– Thomas Peel, GSK, co-directeur de thèse

Résumé : Les contributions de cette thèse sont divisées en deux parties. Une première partie dédiée à l’accélération des méthodes à noyaux et une seconde à l’optimisation 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 d’accé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 à l’optimisation avec contrainte de parcimonie pour l’approximation de signaux et l’élagage de forêts aléatoires. Tout d’abord, nous prouvons sous certaines conditions sur la cohérence du dictionnaire, les propriétés de reconstruction et de convergence de l’algorithme 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 d’un sous-ensemble d’arbres de la forêt initiale sélectionnés et pondérés par OMP de manière à minimiser son erreur empirique de prédiction.

Sampling for acceleration of kernel methods and gluttonous selection for parsimonious representations

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 the optimization with parsimony constraint.
Kernel methods are widely known and used in machine learning. However, 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 Nyström method in order to speed up the kernel methods. We then propose a new framework based on kernels to represent and compare probability distributions. We then exploit the link between our framework and Maximum Mean Discrepancy to propose an accurate and less expensive approximation of the latter.
The second part of this thesis is devoted to optimization with parsimony constraint for signal approximation and pruning of random forests. First, we prove under certain conditions on the coherence of the dictionary, the reconstruction and convergence properties of the Frank-Wolfe algorithm. Finally, we use the OMP algorithm to reduce the size of random forests. 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.

Liens :
https://www.univ-amu.fr/system/files/2019-08/DRV_portraits_jeunes_chercheurs_CEC_pdf_FarahCherfaoui_FichePortrait.pdf
https://www.researchgate.net/scientific-contributions/Farah-Cherfaoui-2151077308
https://scholar.google.fr/citations?user=hgYecToAAAAJ&hl=fr
http://www.theses.fr/en/s208953
https://college-doctoral.univ-amu.fr/inscrit/10959
https://adum.parisnanterre.fr/as/ed/cv.pl?mat=100706&site=adumR