Motivations

L'apprentissage automatique intervient dans des processus de décision et doit permettre de répondre à des questions aussi diverses que :

• mon patient aura-t-il un accident cardio-vasculaire dans les cinq ans à venir ?
• quel sera le résultat du prochain Marseille - Bastia ?
• la molécule que je désire commercialiser est-elle cancérigène ?
• quel est l'auteur de cette page HTML ?
• à quelle espèce appartient cet oiseau ?
• quel sera le cours de l'action Toto dans une semaine ?
• quelle note dois-je mettre à cette copie ?
• cette phrase est-elle grammaticalement correcte ?
• qui a gagné cette partie de morpion ?
• quelle sera la taille de cet enfant à l'âge adulte ?

Notons que des experts humains peuvent être consultés sur bon nombre de ces questions (un médecin pour déterminer le risque encouru par un patient, un amateur de football pour le résultat du match, etc.). Cependant, il s'agit ici d'automatiser cette prise de décision et donc d'en exclure toute intervention humaine.

Cette motivation a conduit à la définition de systèmes experts (ou systèmes à base de connaissance) : ceux-ci sont capables de mener un raisonnement à partir de faits décrivant le problème à résoudre et d'une expertise sous forme de règles. La difficulté est alors d'obtenir ces règles et, à nouveau, il est naturel de se tourner vers les experts humains. Malheureusement, cette étape est apparue très difficile : les experts humains sont le plus souvent incapables d'expliciter leurs raisonnements, en particulier sous une forme contrainte de règles.

C'est l'objectif de l'apprentissage automatique : produire automatiquement des règles. Pour cela, on se donne des exemples de cas déjà traités. Cette fois, les experts humains sont plus à l'aise : on leur demande simplement de fournir leurs réponses sur des cas précis, sans avoir à se justifier. On parle ici d'apprentissage supervisé.

Notons cependant que pour certains problèmes, il n'existe pas d'expertise humaine (par exemple pour décider d'emblée si une nouvelle molécule est cancérigène ou non). Dans de tels cas, les exemples étiquetés nous seront fournis par les expériences passées (par exemple en utilisant les molécules qui ont été déterminées cancérigènes ou non par de longs tests en laboratoire sur des rats). Il ne s'agit plus ici d'expliciter une expertise humaine mais bien de découverte scientifique.

Les types de réponse

Si l'on revient sur les questions données en exemple au début de cette introduction, on peut constater qu'elles attendent des types de réponses différents. On peut distinguer :

• les réponses binaires : oui ou non, ou tout autre paire de valeurs pour les questions suivantes :
  • mon patient aura-t-il un accident cardio-vasculaire dans les cinq ans à venir ?
  • la molécule que je désire commercialiser est-elle cancérigène ?
  • cette phrase est-elle grammaticalement correcte ?
  • qui a gagné cette partie de morpion ?
• les réponses discrètes à plus de deux valeurs :
  • quel sera le résultat du prochain Marseille - Bastia ?
  • quel est l'auteur de cette page HTML ?
  • à quelle espèce appartient cet oiseau ?
• les réponses continues :
  • quelle note dois-je mettre à cette copie ?
  • quel sera le cours de l'action Toto dans une semaine ?
  • quelle sera la taille à l'âge adulte de cet enfant ?

Quand la réponse attendue prend des valeurs discrètes, on parle de classe à prédire. Dans la suite de ce cours, les problèmes à réponses continues, plus couramment appelés problèmes de régression seront laissés de côté. Un moyen ad hoc mais pas toujours pertinent de traiter ce type de problème consiste à discrétiser les réponses possibles : on coupe en différents segments l'intervalle des réponses possibles pour se ramener à un problème discret (par exemple, plutôt que de prédire la taille d'un individu, on pourra se contenter de lui associer l'une des classes petit, moyen ou grand).

La représentation des exemples

Une autre distinction qui peut être faite sur les questions posées portent sur la complexité des objets concernés ou plus exactement sur la complexité de la représentation que nous allons nous donner de ces objets. Nous avons à considérer : un patient, un match de football, une molécule, une page HTML, un oiseau, une valeur boursière, une copie, une phrase, une fin de partie au morpion et un enfant. Une répartition possible (et discutable) de ces objets est la suivante :

• une liste de descripteurs non ordonnée pour le patient, le match de football, l'oiseau, la valeur boursière, la copie, une fin de partie au morpion et l'enfant ;
• une liste ordonnée (ou séquence) pour la phrase ;
• un arbre pour la page HTML ;
• un graphe pour la molécule.

Nous nous intéresserons essentiellement à la première de ces représentations aussi appelée représentation attributs-valeurs. Signalons tout de même que la problématique de la classification supervisée sur les autres représentations a donné lieu à des domaines de recherche à part entière :

• l'inférence grammaticale sur les séquences (et plus récemment sur les arbres également) ; aujourd'hui des algorithmes d'apprentissage sur les séquences sont également développés dans le cadre de la bioinformatique ;
• la programmation logique inductive sur les arbres et graphes.

Une fois la puissance du langage choisie, il reste à déterminer les descripteurs :

• l'âge, le sexe, la taille, le poids, le taux de cholestérol pour le patient ;
• la catégorie grammaticale pour chaque mot de la phrase ;
• deux prédicats, atome et liaison, pour la molécule.

Cette étape est sans doute la plus cruciale dans un processus d'apprentissage, la description doit aider l'apprenant qui va inférer des règles ensuite : elle doit être assez riche pour permettre de discriminer les différentes classes mais pas trop pour ne pas noyer l'information pertinente.

Autres problématiques de l'apprentissage automatique supervisé

Le test de subsomption

Il s'agit d'une opération centrale en apprentissage qui permet de décider si une règle couvre un exemple ou non (on peut dire indifféremment qu'une règle couvre / explique / est plus générale que / subsume un exemple). Ce test étant intensivement utilisé par les algorithmes d'apprentissage sa complexité est un point crucial.

S'il reste peu coûteux pour les représentations attributs-valeurs, la complexité du test de subsomption croît avec la complexité de la représentation. Ainsi, en programmation logique inductive, l'implication logique est indécidable entre clauses de Horn et est remplacée par un test moins puissant, la theta-subsomption, qui est tout de même NP-difficile.

L'évaluation des règles apprises

L'objectif de l'apprentissage automatique est naturellement de pouvoir utiliser les règles apprises sur de nouveaux exemples non étiquetés. Dans ce cadre, on aimerait avoir une idée de la qualité du classifieur appris, autrement dit de la fréquence avec laquelle il va se tromper et cela avant toute utilisation sur de nouveaux cas.

La mesure de cette fréquence sur les exemples fournis pour l'apprentissage donne souvent une valeur bien trop optimiste. L'idée est alors de partitionner les exemples disponibles en deux groupes : l'un pour l'apprentissage, l'autre pour l'évaluation du classifieur. Plusieurs protocoles existent : le 70/30, la validation croisée, le leave-one-out, etc.

Les concepts disjonctifs

Cette difficulté est bien illustrée par le problème déjà évoqué du morpion, où l'on cherche à décider en fin de partie qui a gagné. Dans ce cas, nous avons simplement deux classes : positive si la partie est remportée par les croix, négative sinon. Nous avons suggéré de coder ce problème en attributs-valeurs. La fin de partie positive suivante :

pourra être codée par x,x,x,x,o,b,o,o,b,positive. Avec cette représentation, il est impossible de trouver une unique règle qui reconnaisse tous les exemples positifs : il faut recourir à une disjonction de huit règles, autrement dit identifier les huit sous-concepts correspondant aux huit manières de faire une ligne de croix au morpion :

Si le concept à découvrir ne nécessite pas une telle disjonction, le concept est dit conjonctif et a priori est facile à trouver. Au contraire, plus la taille de la disjonction cible est élevée plus l'apprentissage est difficile et nécessite des algorithmes dédiés.

Les données bruitées

Enfin, il faut prendre compte que l'essentiel des données réelles nous parviennent corrompues, les erreurs pouvant porter sur les valeurs des attributs (erreur de saisie ou de mesure) et sur les classes des exemples (faute du superviseur).

À nouveau, la difficulté de l'apprentissage croît avec le niveau de bruit dans les données et des méthodes plus sophistiquées doivent être utilisées.