Problèmes structurés en traitement automatique des langues

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. 

Table des matières

Introduction
1 Apprentissage supervisé
1.1 Prédiction
1.1.1 Problématique
1.1.2 Classification
1.1.3 Représentation vectorielle
1.2 Prédiction structurée
1.2.1 Structures de dépendances
1.2.2 Espace de recherche
1.2.3 Inférence dans un espace de recherche
1.3 Apprentissage simple et structuré
1.3.1 Fonctions paramétriques
1.3.2 Risque empirique
1.3.3 Recherche du modèle idéal
1.3.4 Risque empirique régularisé
1.3.5 Optimisation et garanties
1.3.6 Apprentissage structuré
1.4 Conclusion
2 Problèmes structurés en traitement automatique des langues
2.1 Introduction
2.2 Les fondations : les mots
2.2.1 Reconnaissance de l’écriture manuscrite
2.2.2 Prédiction de la prononciation
2.3 Les murs : les phrases
2.3.1 Etiquetage morpho-syntaxique
2.3.2 Traduction automatique
2.3.3 Réinflexion
2.4 Le toit : le texte
2.4.1 Identification structurée du locuteur
2.5 Conclusion
3 Apprendre à chercher
3.1 Définitions de base
3.1.1 Espace de recherche
3.1.2 Politique et notions associées
3.1.3 Présentation de l’expert et du tuteur
3.1.4 Fonction objectif
3.2 Méthodes non-itératives
3.2.1 Apprendre sur la trajectoire de l’expert : l’effet d’avalanche
3.2.2 Apprendre sur l’espace complet : le gaspillage de ressources
3.3 Itération de politique
3.3.1 Notions de base
3.3.2 Algorithme ITERATE
3.4 Famille AGGRAVATE
3.4.1 Description de l’algorithme
3.4.2 Analyse .
3.4.3 S’éloigner progressivement de l’expert
3.4.4 Conclusion
3.5 Famille SEARN .
3.5.1 Politique non-stationnaire .
3.5.2 Politique stationnaire : SEARN
3.5.3 Conclusion
3.6 Conclusion et références supplémentaires
4 SEARN pour l’étiquetage de séquences
4.1 Espace de recherche
4.1.1 Décodage en ordre fixe
4.1.2 Espace de recherche pour décodage en ordre libre
4.2 SEARN et l’expert non-déterministe
4.2.1 Choix de la politique de l’expert
4.2.2 Adaptation de SEARN au cas de l’expert non déterministe
4.3 Expérimentations
4.3.1 Mise en œuvre de SEARN
4.3.2 Les tâches d’étiquetage de séquences considérées
4.3.3 Résultats
4.3.4 La procédure d’adaptation de l’expert est-elle efficace ?
4.4 Conclusion
5 Traduction
5.1 Généralités, traduction automatique à base de segments
5.1.1 Objectif d’un système de traduction automatique : le score BLEU
5.1.2 Le système NCODE
5.1.3 Le score LinBLEU et la traduction oracle
5.2 Traduction automatique séquentielle avec SEARN
5.2.1 Traduction automatique séquentielle
5.2.2 Mise en œuvre de SEARN
5.2.3 Premiers résultats
5.3 Les étapes de l’analyse du système
5.3.1 Système et politique de référence .
5.3.2 Première étape : Performances en régression .
5.3.3 Deuxième étape : Performances en classification
5.3.4 Troisième étape : Performance en classification sur le chemin d’inférence
5.3.5 Quatrième étape : Evaluation en BLEU
5.4 Evaluation
5.4.1 Première évaluation
5.4.2 Deuxième évaluation
5.4.3 Troisième évaluation
5.5 Conclusion et perspectives
Conclusion
Bibliographie

projet fin d'etude

Télécharger le document complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *