UMR MISTEA

Apprentissage actif non supervisé: Dans cette thèse, nous étudions des problèmes d'apprentissage non supervisé dans un cadre actif. Dans ce cadre, un apprenant collecte séquentiellement et adaptativement des observations afin d'explorer un environnement de bandit. Nous examinons plusieurs problèmes d'exploration pure dans lesquels l'objectif est de retrouver une structure cachée dans l'environnement, avec un niveau de confiance prescrit. Le fil conducteur est la quantification du budget d'échantillonnage nécessaire pour reconstruire la structure cachée. Nous analysons cinq problèmes: le clustering actif paramétrique, le clustering non paramétrique, le clustering avec sélection adaptative de variables, l'identification du vainqueur de Condorcet en dueling bandits, et la localisation de multiples points de rupture. Pour chacun, nous proposons des algorithmes efficaces avec garanties en espérance et en quantiles sur le budget d'échantillonnage, ainsi que des bornes inférieures sur ce même budget. L'accent est mis sur des régimes de grande dimension et/ou de grande échelle. Nos résultats mettent en évidence des phénomènes invisibles dans les analyses asymptotiques: un compromis fondamental exploration-certification, des écarts structurels entre bornes en espérance et en quantiles, et des gains significatifs dus à l'adaptation, à la fois en budget d'échantillonnage et en complexité computationnelle.