Apprentissage pour l’Aide à la Décision

Dans le domaine de l’aide à la décision, de très nombreux modèles ont été développés pour aider un décideur à faire un choix parmi plusieurs alternatives. Selon qu’il s’agisse de prendre une décision sous incertitude ou non, que la décision soit séquentielle ou non, qu’elle implique un seul individu ou que la décision soit collective, les types de modèles envisagés seront différents. Dans certains domaines, il peut être souhaitable de produire des modèles interprétables par le décideur, plutôt que des « boîtes noires ».

Apprentissage de modèles combinatoires interprétables

Ainsi, dans le domaine médical, construire des modèles interprétables pour aider le médecin ou le chercheur à prendre des décisions est crucial. Nous nous sommes intéressés à la construction de modèles de prédiction du risque de développement de maladies cardio-vasculaires, à partir de données génomiques et métagénomiques. Dans ce type de problème, le nombre d’attributs (le nombre de gènes, de l’ordre de 108) est bien plus grand que le nombre d’exemples (le nombre de patients, de l’ordre de la centaine). Jusqu’à présent, la seule approche possible pour éviter le sur-apprentissage était d’utiliser des modèles linéaires parcimonieux, difficiles à interpréter par les médecins.

Pour apprendre des modèles plus facilement interprétables, nous avons introduit une contrainte supplémentaire dans ces modèles : l’algorithme d’apprentissage force les poids à ne prendre comme valeur que -1, 0, ou 1. Le problème d’apprentissage devient alors un problème combinatoire, difficile à résoudre.

Nous avons montré dans [ CI-18 , CO-15] que ce problème n’admet pas de schéma d’approximation en temps polynomial et proposé un algorithme à garantie de performance pour résoudre ce problème. Nous avons également prouvé en utilisant la complexité de Rademacher que ces contraintes permettaient de dépasser la limitation classique des modèles parcimonieux, pour lesquels le nombre d’exemples doit être de l’ordre du logarithme du nombre d’attributs.

Apprentissage et Incertitude

Nous nous sommes inéresés à l’apprentissage superviéà partir de donées incompètes dans des langages logiques d’ordre 1. Un exemple imparfaitement connu est un ensemble de clauses instanciées, qui sont des représentations candidates de cet exemple. Nous avons développé une méthodologie prenant en compte au mieux les connaissances disponibles sur de tels exemples, sous la forme de clauses exprimant des contraintes sur les valeurs que peuvent prendre simultanément les attributs des exemples, ainsi qu’un programme [LO-1] pour apprendre un prédicat cible même quand les exemples sont très incomplètement connus, à condition d’en fournir un grand nombre ainsi qu’un ensemble de clauses. Un résultat théorique de complexité d’échantillonnage donne les conditions dans lesquelles la convergence est garantie [CO-41].

Apprentissage et Planification

La planification d’une séquence d’actions peut s’effectuer en utilisant diverses techniques, notamment les Processus de Décision de Markov (PDM) ou, lorsque les applications sont de nature plus combinatoire, les modèles STRIPS.

En se basant sur le formalisme des PDMs, nous avons traité le problème de l’apprentissage des préférences de l’utilisateur dans le cadre de la planification dans l’incertain. Planifier en prenant ces préférences en compte nécessite que l’agent apprenne à la fois les préférences de l’utilisateur et les effets de ses propres actions. Nous avons développé des algorithmes pour traiter des PDMs bien plus grands que ceux de l’état de l’art et de façon plus efficace pour résoudre ces problèmes [CI-58, CO-75, CI-60, CO-76].

Nous avons également exploré l’apprentissage de modèles d’action exprimés dans un formalisme relationnel (à la STRIPS) à partir de traces d’exécution d’un agent tentant de résoudre un but. Nous avons modélisé ce type d’apprentissage comme un processus de révision de théorie guidé par les données : l’agent déclenche des actions et met à jour son modèle d’actions pour rendre compte a minima des effets observés. Nous avons proposé une stratégie d’apprentissage actif [CI-1], i.e. favorisant l’application de certaines actions dans le but de généraliser plus rapidement ces règles d’action.

Apprentissage dans le cadre collectif

Nous avons travaillé sur un modèle d’apprentissage collectif dans lequel, d’une part, la communauté forme un réseau d’agents dont les liens représentent les communications possibles, et d’autre part, les agents font des observations et communiquent en parallèle. Nous nous sommes intéressés à l’effet de la structure du réseau sur la vitesse d’apprentissage pour une tâche d’apprentissage supervisé [CI-76*], ainsi qu’à un apprentissage pleinement parallèle pour lequel nous avons obtenu des garanties de consistance globale avec les observations [CI-77*].

Par ailleurs, dans le cadre d’une communauté sans contraintes de communication, nous avons exploré l’apprentissage collectif lorsque la tâche d’apprentissage est la révision d’un modèle d’action relationnel [CO-30 , CI-27] et étudié différentes informations qu’une communauté d’agents peut apporter à un agent au moment de décider, par exemple, quelle action effectuer pour atteindre son but lorsque sa théorie ne lui permet pas de planifier [CI-63, CL-5].