Critéres d'importance supervisés pour l'apprentissage statistique à grande échelle // Supervised importance criteria for large-scale learning

Cette thèse s'intéresse au développement de méthodes d'apprentissage supervisé
non-paramétriques utilisables sur de grands volumes de données. Les méthodes à
noyaux constituent un formalisme puissant pour définir des modèles
d'apprentissage non- paramétriques ; elles sont largement utilisées en pratique,
et leurs propriétés théoriques ont été amplement étudiées [1]. Toutefois, leur
coût calculatoire limite fortement leur intérêt pour une utilisation sur de
larges vo- lumes de données. Une technique standard pour réduire ce coût est
d'utiliser des approximation matricielles de faible rang randomisées. Le
principal exemple d'une telle approximation est la méthode de Nyström [2]
(égale- ment appelée approximation CUR), dont la définition repose sur le choix
d'un sous-échantillon représentatif du jeu de données. Ce dernier peut être tiré
aléatoirement de manière uniforme, mais une meilleure approximation est
généralement obtenue en échantillonnant les données proportionnellement aux
scores d'importances (leve- rage scores) des observations. Ces derniers peuvent
s'interpréter comme une mesure de l'importance relative de chaque point au sein
du jeu de données, et possèdent un rôle important également en théorie de
l'approxi- mation [3] ou pour la détection de valeurs aberrantes.
L'approximation de Nyström basée sur cette technique d'échantillonnage permet de
construire des estimateurs qui, p.ex. sur un problème comme la régression ridge
à noyau, ont un taux d'erreur optimal [4] tout en ayant un coût de calcul
limité. Toutefois, bien que largement utilisés pour des problèmes
d'apprentissage supervisé, les scores d'importance ne dépendent pas de la
variable expliquée ; p.ex. pour un problème de régression ou l'on cherche à
identifier une relation de la forme 𝑦 = 𝑓(𝑥) à partir d'observations (𝑥𝑖,
𝑦𝑖)1≤𝑖≤𝑛, les scores d'importance ne dépendent que des points (𝑥𝑖)1≤𝑖≤𝑛 mais pas
des mesures (𝑦𝑖)1≤𝑖≤𝑛, et une partie de l'information est donc ignorée dans la
construction de l'approximation. En outre, leur calcul est connu pour être
relativement coûteux, ce qui limite leur intérêt en pratique et appelle au
développement d'algorithmes d'échantillonnage approchés.

Les deux axes proposés pour cette thèse sont les suivants :

• Critères d'importance supervisés – La première direction de recherche consiste
en la définition de critères d'importance pour des problèmes d'apprentissage
supervisés. En partant d'un problème largement étudié comme la régression ridge
à noyau, nous proposerons de nouveaux critères d'importance tirant parti de
l'information issue de la variables expliquée. Nous quantifierons la qualité de
l'approximation induite, et étudierons les performances empiriques de la méthode
proposée. Ces travaux s'inspireront de la littérature existante sur la
construction de coresets par sous-échantillonnage, ou la notion de sensitivité
joue un rôle proche des scores d'importances [5].

• Algorithmes d'échantillonnage – Le calcul de scores d'importance étant connu
pour être particulière- ment coûteux, il conviendra de s'intéresser également au
développement d'algorithmes efficaces permettant d'échantillonner
proportionnellement aux scores d'importance supervisés nouvellement introduits.
Pour ce- la, nous nous appuierons sur les algorithmes itératifs existants dans
le cas non supervisé [6]. Nous nous intéresserons également au développement
d'algorithmes distribués.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

This thesis focuses on the development of non-parametric supervised on large volumes of data. Kernel methods are a powerful formalism for defining non-parametric learning models; they are widely used in practice, and their theoretical properties have been extensively studied [1]. However, their computational cost severely limits their suitability for use on large data sets. A standard technique for reducing this cost is to use randomized low-rank matrix approximations. The main example of such an approximation is Nyström's method [2] (also called CUR approximation). (also known as the CUR approximation), whose definition is based on the choice a representative sub-sample of the dataset. The latter can be drawn uniformly, but a better approximation is generally obtained by obtained by sampling the data in proportion to the importance scores leve- rage scores of the observations. The latter can be be interpreted as a measure of the relative importance of each point in the the dataset, and also play an important role in approximation theory. approximation [3] or for outlier detection.

In this thesis we will explore the use of supervised criteria for the selection of inducing points in the Nyström approximation.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2025

Concours Labex

Université Grenoble Alpes

220 EEATS - Electronique, Electrotechnique, Automatique, Traitement du Signal

M2 Mathématiques appliquées ou équivalent, connaissance préalable des méthodes à noyaux et de l'analyse fonctionnelle, plus particulièrement des espaces à noyau reproduisant, capacité à implémenter des algorithmes dans le domaine dans les langages Python ou Julia.
Master's degree in applied mathematics, prior experience in kernel methods, knowledge of functional analysis, in particular Reproducible Kernel Hilbert Spaces. Experience with implementing kernel algorithms in Python or Julia.