Admin CliCours
Apprendre par imitation : applications à quelques problèmes d’apprentissage structuré en traitement des langues
Prédiction
Problématique
On suppose donnés deux ensembles X et Y de nature quelconque que l’on appellera respectivement ensemble d’entrée et de sortie, ainsi qu’une boite noire qui à chaque entrée x ∈ X associe la sortie y ∈ Y qui lui correspond. Cette boite noire représente généralement un expert humain capable de réaliser ces associations parfaitement. Par exemple, dans le cas du problème de l’identification d’un objet à partir de sa photo, la photo est une entrée x et le nom de l’objet représenté est une sortie y. On peut imaginer de nombreuses tâches qui entrent dans ce modèle. Si beaucoup de ces tâches sont naturelles pour un humain, elles peuvent être très complexes à réaliser de manière automatique. La prédiction automatique [Duda et al., 2000] consiste à reproduire automatiquement le comportement de cette boite noire, c’est-à-dire d’être capable de trouver la sortie y pour de nouvelles entrées x inconnues. Pour cela, on se basera sur un ensemble limité d’exemples de son fonctionnement : E = (xm, ym) M m=1 (1.1) Autrement dit, on cherche une fonction de prédiction f : X → Y qui, pour chaque entrée x renvoie la sortie y correcte. On note f(x) le résultat de l’application de cette fonction. Lorsque l’entrée x et la fonction de prédiction f sont claires à partir du contexte, on utilisera la notation yˆ. Idéalement, cette fonction de prédiction devrait toujours reproduire les résultats de la boite noire. En pratique, cela est rarement possible et il est nécessaire d’évaluer la qualité des prédictions réalisées. Cette évaluation s’effectue à l’aide d’une fonction de perte L : Y × Y → R + permettant de mesurer la perte réelle L(y, yˆ) obtenue en prédisant la sortie yˆ à la place de la sortie y donnée par la boite noire. Par définition, L(y, y) = 0. Afin de formaliser le problème, en suivant [Vapnik, 1995], on introduit la distribution D˜ (inconnue) sous laquelle les couples d’exemple sont en- gendrés x ∈ X, y ∈ Y : (x, y) ∼ D˜. L’ensemble (1.1) est en fait un tirage selon cette distribution. La quantité reflétant l’espérance de la perte selon la distribution D˜ s’appelle la fonction de risque : E(x,y)∼D˜ [L(f(x), y)] (1.2) Trouver la fonction de prédiction qui permette de minimiser (1.2) est l’objectif de l’apprentissage.
Classification
Dans ce travail, nous nous intéresserons principalement aux problèmes de prédiction o`u l’ensemble de sortie Y est fini, autrement dit aux problèmes de classification. La classification a pour objectif de choisir une sortie parmi un ensemble fini d’alternatives y 0 ∈ Y ayant chacune une perte L(y, y0 ) associée. Une fonction de perte très utilisée dans les problèmes de classification est la fonction 0 − 1 qui attribue une perte identique à toutes les réponses à l’exception de la réponse correcte : L(y, y0 ) = ( 0 si y 0 = y 1 si y 0 6= y (1.3) Cette fonction de perte peut être utilisée par exemple pour la tâche de reconnaissance d’une personne à partir de l’enregistrement de sa voix, et de manière générale pour toutes les tâches o`u aucune erreur n’est plus grave qu’une autre. Dans les situations o`u différentes erreurs amènent à des conséquences différentes, d’autres fonctions de perte doivent être utilisées. Par exemple, dans le cas de la reconnaissance de maladie grave à partir d’un dossier médical, les conséquences associées à un faux positif sont généralement bien plus faibles que celles associées à une non-détection. En effet, le premier type d’erreur implique une inquiétude inutile et des examens supplémentaires, alors que pour le deuxième les conséquences peuvent aller jusqu’au décès du malade. Dans cette situation, on utilisera plutˆot une fonction de perte telle que : L(y, y0 ) = 0 si y 0 = y 1 si y = pas de maladie et y 0 = maladie 1000 si y = maladie et y 0 = pas de maladie (1.4) Nous utiliserons par la suite le terme étiquette pour désigner la sortie y 0 ∈ Y , et le terme classer pour la procédure de choix d’une étiquette à associer à une entrée donnée. Afin de classer une entrée, il est nécessaire d’estimer la perte de chaque étiquette possible en lui attribuant un score, puis de choisir la sortie ayant le score le plus bas 1 . La fonction de prédiction a donc la forme suivante : f(x) = arg min y 0∈Y F(x, y0 ) (1.5) o`u F(x, y0 ) est une fonction de score, qui idéalement associe le plus petit score à l’étiquette impliquant la perte minimale. La qualité de la fonction de prédiction dépend alors directement de la qualité de la fonction de score utilisée.
Représentation vectorielle
Afin de pouvoir définir la fonction de score, il est nécessaire de transformer chaque couple abstrait (x, y0 ) sous une forme mathématiquement utilisable. Pour réaliser une tâche donnée, un expert humain va le plus souvent se concentrer sur un ensemble limité d’informations discriminantes qui lui permettent de déterminer la bonne étiquette. Pour offrir les mêmes possibilités au système automatique, chaque couple (x, y0 ) est représenté par un vecteur de caractéristiques φ(x, y0 ) ∈ R L . Ce vecteur contient des valeurs réelles qui représentent différentes informations pertinentes sur le couple (x, y0 ), par exemple la forme et la couleur des différentes parties d’une image que l’on souhaite identifier. Le choix d’un bon ensemble de caractéristiques est crucial pour que la tâche soit réalisable. En effet, toute l’information présente dans les données d’origine qui n’est pas mise sous la forme d’une caractéristique ne pourra pas être utilisée par le système. Reconnaˆıtre des fruits à partir de photos est ainsi quasiment impossible si aucune information de couleur n’est donnée. En utilisant une représentation sous forme d’un vecteur de caractéristiques, la fonction de prédiction prend la forme suivante : fw(x;w) = arg min y 0∈Y F(φ(x, y);w) (1.6) o`u F : R N → R est une fonction de score pour le vecteur de paramètres w, dont le choix sera explicité à la section 1.3.1. 1. Les scores représentant ici des pertes, il est normal de chercher à les minimiser.
Prédiction structurée
Deux facteurs principaux influencent la complexité du calcul de (1.6) : la difficulté de calcul des scores F(φ(x, y)) ainsi que la taille de l’ensemble des sorties Y . Si la complexité due au calcul des scores peut être mitigée par un choix approprié des fonctions F et φ, le deuxième facteur est plus difficile à maitriser : lorsque la taille de l’ensemble de sortie Y est telle que la recherche de l’élément qui minimise le score ne peut être réalisée en un temps raisonnable, une méthode approchée doit être utilisée. L’introduction de ce type d’approximations a un coût qui se traduit généralement par une baisse de qualité des prédictions et il peut être difficile, voir impossible, d’obtenir des prédictions satisfaisantes. Dans cette section nous allons nous intéresser à un type particulier de problèmes où la taille de Y rend les calculs exacts impossibles, mais où des méthodes approchées de bonne qualité existent.
Structures de dépendances
Lorsque l’ensemble de sortie Y est de très grande taille, les différentes étiquettes qui le composent ont généralement une structure interne que l’on peut exploiter afin de simplifier les calculs. Ces étiquettes peuvent être découpées en plus petites unités ayant un nombre limité de dépendances entre elles. On peut alors profiter de ce petit nombre de dépendances et du fait qu’un grand nombre de ces unités vont être partagées par plusieurs étiquettes, afin de réduire la quantité de calcul en utilisant par exemple des techniques de programmation dynamique. La prédiction structurée est donc un cas particulier de prédiction où l’on fait l’hypothèse que la sortie y se compose de plusieurs variables aléatoires liées entre elles. Chaque variable représente une unité de prédiction et les éventuelles dépendances entre les variables relient les différentes unités. Il est important que les unités, ainsi que les liens entre elles, soient choisis en fonction de la nature de la tâche mais aussi de manière à permettre une factorisation efficace des calculs. Nous appellerons structure de dépendances le graphe dont les nœuds représentent les variables aléatoires et dont les arcs représentent les dépendances entre les variables. Ce graphe de dépendances peut avoir une structure arbitraire, adaptée à une tâche donnée ; dans le cas de la prédiction structurée on retrouve le plus souvent des structures telles que des séquences ou des arbres.
Espace de recherche
L’espace de recherche est un ensemble d’instances 2 de la structure de dépendances représentant l’ensemble de sortie Y organisé de manière à rendre les calculs efficaces. L’espace de recherche sur les séquences permet une présentation simple ; ce type d’espace de recherche est le plus courant en pratique, et le seul que nous utiliserons dans ce travail 3 , c’est pourquoi nous allons concentrer notre présentation sur celui-ci. L’extension à des structures telles que les arbres ou graphes se fait naturellement et nous les ́évoquerons lorsque des points particuliers seront à noter. En supposant donc que la structure de dépendances soit une séquence, l’espace de recherche est un graphe comportant un nœud initial et un nœud final qui sont reli ́es par des chemins repre ́ sentant les diff ́ rentes predictions possibles. Les arcs de ce graphe sont pond ́er ́es de manère à ce que la somme des poids des arcs d’un chemin repre ́ sente la perte totale associe ́ ea ̀ la prediction correspondante. La r ́esolution du problème de minimisation (1.6) est ́équivalenteà la recherche du plus court chemin dans cet espace de recherche. Sous sa forme la plus na ̈ıve, l’espace de recherche est un graphe dans lequel chaque chemin est indépendant des autres (n’a aucun nœud commun avec un autre chemin). Il comporte donc un nombre de nœuds proportionnel à la taille de l’ensemble Y et le calcul de son plus court chemin n’est donc pas plus efficace qu’une prédiction non-structurée. Mais si les dépendances le permettent, il est possible de factoriser ce graphe en exploitant la structure commune des chemins de manière à obtenir un treillis de recherche comme illustré dans la figure 1.1. Sous cette forme, chaque nœud est partagé par un grand nombre de chemins et la recherche du plus court chemin peut être réalisée de manière plus efficace.
Introduction |
