Paramètres d'ordre et sélection de modèles en apprentissage : caractérisation des modèles et sélection d'attributs
Résumé
This thesis focuses on model selection in Machine Learning from two points of view. The first part of the thesis focuses on relational kernel methods. Kernel methods hope to overcome the instances propositionalization, and to bridge the gap between relational and propositional problems. This thesis examines this objective in a particular case : the multiple instance problem, which is considered to be intermediate between relational and propositional problems. Concretely, we determine under which conditions the averaging kernel used for multiple instance problems, allows to reconstruct the target concept. This study follows the standard sketch of phase transition studies and relies on a new criterion to test the efficiency of of the propositionalization induced by the averaging kernel. The second part of the thesis focuses on feature selection. A solution to solve multiple instance problems, as presented in the first part, is to construct a propositionalization where each instance of the problem leads to a feature. This propositionalization constructs a huge number of features, which implies the need to look for a subset of features with only relevant features. Thus, the second part of the thesis presents a new framework for feature selection. Feature Selection is formalized as a Reinforcement Learning problem, leading to a provably optimal though intractable selection policy. This optimal policy is approximated, based on a oneplayer game approach and relying on the Monte-Carlo tree search UCT (Upper Confidence bound applied to Trees) proposed by Kocsis and Szepesvári (2006). The Feature Uct SElection (FUSE) algorithm extends UCT to deal with i) a finite unknown horizon (the target number of relevant features) ; ii) the huge branching factor of the search tree, reflecting the size of the feature set. Finally, a frugal reward function is proposed as a rough but unbiased estimate of the relevance of a feature subset. A proof of concept of FUSE is shown on benchmark data sets.
Nous nous intéressons à la sélection de modèle en apprentissage automatique, sous deux angles différents. La première partie de la thèse concerne les méthodes à noyau relationnel. Les méthodes à noyau permettent en principe de s’affranchir de la représentation des instances, et de combler le fossé entre apprentissage relationnel et apprentissage propositionnel. Cette thèse s’intéresse à la faisabilité de cet objectif dans un cas particulier : les problèmes à instances multiples, qui sont considérés comme un intermédiaire entre les problèmes propositionnels et les problèmes relationnels. Concrètement, nous déterminons sous quelles conditions le noyau-somme, utilisé sur des problèmes à instances multiples, est en mesure de reconstruire le concept-cible. Cette étude suit le schéma standard des études de transition de phase et s’appuie sur un critère nouveau pour caractériser l’efficacité de la propositionnalisation induite par le noyau-somme. La deuxième partie de la thèse porte sur la sélection d’attributs. Une solution pour résoudre les problèmes à instances multiples, tels que présentés en première partie, passe par une propositionnalisation associant un attribut à chaque instance présente dans le problème. Le nombre d’attributs ainsi construits étant gigantesque, il est alors nécessaire de sélectionner un sous-ensemble d’attributs ne contenant que des attributs pertinents. La deuxième partie de la thèse propose donc une nouvelle approche pour la sélection d’attributs. La sélection d’attributs est réécrite comme un problème d’apprentissage par renforcement, conduisant ainsi à une politique de sélection optimale mais non-calculable en un temps raisonnable. Cette politique est approchée en se fondant sur une approche de jeu à un joueur et en utilisant la méthode Monte-Carlo pour les arbres UCT (Upper Confidence bound applied to Trees), qui a été proposée par Kocsis et Szepesvári (2006). L’algorithme FUSE (Feature Uct SElection) étend UCT pour gérer (1) l’horizon fini mais inconnu, et (2) le facteur de branchement élevé de l’arbre de recherche reflétant la taille de l’ensemble d’attributs. Finalement, une fonction de récompense frugale est proposée en tant qu’estimation grossière mais non-biaisée de la pertinence d’un sous-ensemble d’attributs. Une preuve de concept de FUSE est fournie sur des bases de données de référence.