Paramètres d'ordre et sélection de modèles en apprentissage : caractérisation des modèles et sélection d'attributs
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
This thesis focuses on model selection in machine learning from two point of view. The first part of the thesis focuses on relational kernel methods, which hope to overcome the instances propositionnalisation, and to bridge the gap between relational and propositional problems. This thesis examines this objective in a particular case: the multiple instance problem (MIP), which is considered to be intermediate between relational and propositional problems. Concretely, we determine under which conditions the averaging kernel used for MIP, 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. Ln the second part of the thesis, 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 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.
Abstract FR:
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, qui 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 (PIM), 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 PIM, 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. Dans la deuxième partie de la thèse, 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 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.