Soutenance mémoire
Automatisation
L’histoire de l’informatique est fondamentalement liée à la systématisation de la résolution de problèmes en vue de leur automatisation. Il s’agit de faire effectuer par la machine des tâches fastidieuses car répétitives ou difficiles car complexes. Ces tâches sont représentées pour la machine sous forme d’une suite d’instructions, exprimées à l’aide d’un langage formel de spécification donné, qu’on appelle langage de programmation*. Les langages de programmation ont connu un fort développement depuis les premiers ordinateurs, bien que quelques uns aient été conçus avant même leur apparition, comme les diagrammes d’Ada Lovelace pour programmer la machine de Charles Babbage. Depuis lors, de nombreux travaux n’ont cessé de rapprocher ces langages de spécification de la langue naturelle. La langue naturelle est le langage utilisé par l’humain, on le distingue du langage formel par la possibilité d’utiliser l’ambiguïté. Une expression est dite ambigüe lorsqu’elle peut référer à plusieurs sens comme c’est le cas en français du mot « plan » considéré hors de son contexte par exemple. Le langage formel n’est pas ambigu, chacune des expressions est associée à une unique sémantique, ce qui n’est pas le cas de la langue naturelle comme nous venons de le voir. Cette ambiguïté semble suivre la tendance du principe d’économie des signes (cf. maximes de Grice [Grice, 1975], et la théorie de la pertinence [Ducrot, 1998]) lui-même lié à la loi du moindre effort (ou principe d’économie) [Zipf, 1935], appliquée en particulier à la phonétique [Martinet, 1956]. En effet, la réduction du nombre de signes nécessaires à la communication d’un message cause, à partir d’un certain seuil, des collisions dans la relation des signes aux sens. Le sens est alors déterminé grâce à la réutilisation d’informations partagées : le contexte de la communication. À titre d’illustration, ce chapitre lui-même vise à établir un contexte partagé de communication grâce auquel il sera possible de développer les suivants, sans nécessité de rappeler les références introduites ici en extension. On peut donc comprendre cette tendance à rapprocher les langages de spécification de la langue naturelle comme une conséquence de la loi du moindre effort appliquée à la spécification de processus de traitement de l’information. En premier lieu, le nombre de signes d’une instruction ou d’un programme peut être réduit grâce à la réutilisation d’information contenue dans le programme lui-même. Il s’agit de la factorisation. C’est un principe fondamental en programmation, appelé définition de fonction : il consiste à donner un nom à une séquence d’instructions en vue de réutiliser cette séquence à l’aide d’un seul signe. La factorisation survient bien entendu dans les langues naturelles également avec l’apparition de nouveaux mots ou expressions, i.e. de nouveaux usages (exemple : le mot laser, issu d’un acronyme anglophone décrivant son principe). En programmation, les efforts de factorisation au niveau de la compilation* ont donné lieu à l’apparition de langages de plus en plus expressifs dits de haut niveau, avec par exemple l’introduction d’opérateurs complexes, la gestion d’exceptions. Ces évolutions ont notamment permis l’apparition de nouveaux paradigmes de programmation, dont la programmation objet, logique, fonctionnelle, orientée-agent sont des exemples. L’utilisation de langages de haut niveau permet d’accélérer et de simplifier le développement de programmes grâce principalement aux propriétés suivantes permises par la compilation et décrites dans [Mogensen, 2009] :
• la notation des langages de haut-niveau est plus proche de la manière dont les humains pensent les problèmes que celle du langage machine ;
• le compilateur peut identifier et signaler des erreurs évidentes du programmeur ;
• les programmes écrits dans des langages de haut niveau sont généralement plus courts que leur équivalent en langage machine.
1. Compilation : opération de transcription d’un programme écrit dans un langage de haut niveau dans un langage de plus bas niveau.
2. Le langage machine est un langage formel représentant les instructions telles qu’elles sont exécutées par le processeur.
Ces instructions ainsi que tous les paramètres sont donc encodés en binaire. On peut également ajouter que de nombreuses erreurs de copie ou d’inattention disparaissent grâce à la factorisation. Ces mêmes arguments, à l’exception du second, motivent l’utilisation de la langue naturelle en tant que langage de spécification. Le champ de la programmation automatique rassemble les efforts dans le but de rapprocher le langage de spécification pour les instructions données au système de la langue naturelle. Des approches pour cet objectif ont été proposées dès les débuts de l’informatique. [Bobrow, 1964] décrit dans sa thèse le système STUDENT de compréhension et de résolution de problèmes d’algèbre simples formulés dans un anglais contraint, tel que présenté dans l’exemple 1.1, grâce à l’association de phrases avec des équations. Ce mode d’expression des problèmes contraint l’ensemble des tâches traitées par le système. En outre, l’approche à base de règles proposée ne permet pas une application directe à d’autres modes d’expression ou d’autres langues naturelles. La programmation est définie par Rich et Waters par : « l’expression d’un ensemble d’instructions dans un langage formel spécifique en vue de son exécution non ambigüe (généralement par une machine) ». Afin de proposer une perspective unifiée sur la programmation automatique pour le projet the Programmer’s Apprentice, Rich et Waters prennent pour modèle les choix de programmeurs experts vis-à-vis de tâches à accomplir [Rich et Waters, 1993]. Ils décrivent pour cela comment le programmeur analyse, synthétise, modifie, explique, spécifie, vérifie et documente les programmes. L’approche proposée est un système d’aide à la programmation* qui repose sur un module central de spécification. Ce dernier a pour tâche de transformer les descriptions informelles en spécifications formelles à l’aide d’une ontologie de notions prédéfinies (appelées clichés) qu’il identifie aux descriptions de l’utilisateur. Le système KBEMACS (Knowledge-Based Editor in Emacs) transcrit des listes d’instructions en langue naturelle en un programme complet en langage ADA. L’anglais utilisé pour les instructions emploie un vocabulaire spécifique de l’entreprise, relatif au traitement des informations de maintenance de machines (UNIT). L’exemple 1.2 illustre un bloc d’instructions tel que KBEMACS les traite. La base de connaissances est renseignée au préalable avec les concepts correspondants ainsi que leurs propriétés et relations. L’originalité de cette approche est sa généricité : il est possible de rendre le système compatible avec l’expression de besoins quelconques pourvu que l’anglais utilisé soit suffisamment simple et que le système dispose de la base de connaissances et du vocabulaire nécessaires. Cependant, cette adaptation requiert toujours l’intervention d’un expert pour la constitution de la nouvelle base de connaissances. Le principe de réponse à des instructions formulées en langue naturelle a également été appliqué en robotique. On peut citer [Tellex et al., 2011] qui propose une approche pour l’association d’instructions en langue naturelle, telles que lisibles dans l’exemple 1.3, à des séquences d’actions en vue d’exécuter l’instruction donnée. À cette fin, leur approche s’appuie sur la structure linguistique des requêtes pour former un plan d’action pour le robot sous forme d’un graphe d’ancrage généralisé (Generalized Grounding Graph) représentant l’objectif spécifié. Un exemple de graphe d’ancrage généralisé est donné dans la figure 1.1, extraite de [Kollar et al., 2013]. Ces graphes représentent une association entre des segments linguistiques de l’instruction et des objets, chemins, lieux et évènements de l’environnement du robot à l’aide d’une hiérarchie de clauses de description spatiales (Spatial Description Clauses). Ces clauses sont extraites à l’aide de l’analyse en dépendances produite par le Stanford Parser [De Marneffe et al.,2006]. Un modèle probabiliste est appris pour l’association entre clauses et objets par apprentissage supervisé fondé sur les CRF (Conditional Random Fields) [Lafferty et al., 2001]. Cette approche est ainsi applicable à tout type d’actions pourvu qu’on dispose d’exemples d’apprentissage qui les couvrent. Cependant, l’utilisation du Stanford Parser rend l’analyse du langage problématique car il s’agit d’un système spécifique à l’anglais . La généricité ne s’étend donc pas à toute langue naturelle pour l’expression des instructions. D’autre part l’approche ne permet pas de traiter correctement les mentions d’objets n’ayant pas d’ancrage physique tels que « l’espace vide entre les deux piles ». Nous proposons de regrouper les systèmes de programmation automatique au sens large sous la dénomination d’assistants opérationnels. Un assistant opérationnel est un système capable de comprendre des spécifications de haut niveau, en langue naturelle par exemple, et d’effectuer de manière autonome la tâche correspondante. Dans la section suivante, nous nous intéressons aux différentes méthodes envisageables pour effectuer le passage depuis la requête en langue naturelle vers une séquence d’actions appropriée à effectuer par le système. Dans un but de simplicité, nous proposons de considérer la séquence d’actions en tant que son expresion dans un langage de programmation. Cela permet de considérer le problème comme une tâche de transfert entre langages.
Transfert analogique direct
La manière naïve d’envisager le transfert de langage par analogie consiste à former des triplets directement à partir des exemples présents dans la base. Prenons par exemple la requête « Imprime 3 copies du fichier doc.pdf « , le principe est de rechercher une association requête-commande existante afin d’obtenir une équation analogique comme celle présentée dans l’exemple 5.1. On définit ainsi le transfert direct* comme la génération de l’équivalent en langue cible de l’énoncé source soumis à partir d’équations analogiques transverses, i.e. comprenant énoncés en langue source et leur association en langue cible. On applique l’algorithme de résolution analogique pour chaque équation ainsi constituée. Pour celles qui ont des solutions, on ne considère que la solution de degré minimal. Dans l’exemple présenté, il s’agit donc de la commande « lp -n 3 doc.pdf », pour un degré de 4. On obtient donc un ensemble de solutions parmi lesquelles il faut déterminer la réponse finale à proposer. Avant d’envisager des critères de tri pour cet ensemble, tentons d’abord d’estimer le nombre de solutions distinctes auquel on peut s’attendre. Rappelons qu’un quadruplet de séquences (x, y, z, t) est en proportion analogique si et seulement s’il existe un alignement dont chaque quadruplet atomique est de la forme [a : a :: b : b] ou [a : b :: a : b]. Cela implique que tous les symboles de x sont contenus dans y ou dans z. Les symboles de x absents de z sont donc nécessairement présents dans y si la proportion est vérifiée. Par ailleurs, cette règle ne dépend pas de l’atome choisi : caractères ou tokens. Pour les situations considérées dans la suite, nous utilisons les tokens comme atomes de segmentation des séquences. Par corollaire de la règle énoncée, pour qu’une solution existe tous les tokens de x absents de z sont nécessairement présents dans y. En particulier, lorsque x et z sont systématiquement des phrases du langage source, et y et t des phrases du langage cible, il ne peut pas s’agir que de tokens qui peuvent être utilisés indifféremment dans les deux langages. Autement dit, un tel token représente pour les deux langages la même unité de sens. Dans le cas particulier du transfert depuis la langue naturelle vers le langage formel, cela implique que tous les tokens de la requête z exclusifs à la langue naturelle 1 doivent être présents à la fois dans une requête de la base d’exemples. De plus, l’alignement des séquences contraint à conserver leur ordre d’apparition. Les seuls tokens qui échappent à ces contraintes sont les tokens communs aux deux langages que nous avons mentionnés. Ces tokens correspondent dans ce cas aux paramètres de la requête. Dans l’exemple précédent, il s’agit de « 3 » et « doc.pdf » qui pourront, et devront, apparaître dans la commande pour résoudre l’équation analogique et produire une solution correcte. Il s’agit donc d’une forte limitation de l’approche directe puisqu’elle nécessite, pour produire une solution, d’identifier un exemple dans la base dont la requête soit tout à fait similaire à la requête soumise. Elle doit se conformer au même modèle que la requête soumise comme vu dans l’exemple 5.1, seuls les paramètres pouvant varier. Les réponses que l’on peut attendre par cette approche directe ne sont pas uniques. En particulier, on peut obtenir des doublons dans les cas de figure suivants :
• la base contient plusieurs exemples dont la requête est construite sur le même modèle
• le modèle de requête est associé à plusieurs commandes différentes dans la base
Le premier cas ne donnera pas lieu à des réponses distinctes car les paramètres seront partout remplacés par ceux de la requête soumise. Le second cas produira des réponses distinctes, et cela conduit à une ambiguïté lorsque les différentes commandes ne sont pas synonymes. Dans ce dernier cas, plus d’informations sont nécessaires pour sélectionner la réponse attendue. Nous supposerons que la solution la plus occurrente est la plus probablement correcte car elle est plus populaire dans la base d’exemples. Cependant d’autres discriminants peuvent être utilisés tels que le degré de l’équation analogique mise en jeu, ou son succès au cours de précédentes interactions consignées dans une base d’apprentissage méta. La constitution d’une telle base permet l’utilisation de méthodes d’apprentissage artificiel afin d’identifier des critères des proportions analogiques permettant de prédire le succès de leur résolution et/ou la validité de la solution produite. L’approche de transfert par analogie directe permet donc de déterminer la correspondance cible d’un énoncé en langage source, mais requiert de former grâce à la base une équation analogique respectant une somme stricte sur les symboles. De plus la méthode impose que tout token ou expression qui n’est pas directement transféré doit se trouver dans l’énoncé source extrait de la base d’exemples. En pratique, cette approche n’est pas utilisée pour la traduction d’une langue naturelle vers une autre langue naturelle à cause de ces limitations. En effet, les variations syntaxiques sont très nombreuses dans la langue naturelle non contrainte, et il n’est donc pas réaliste de supposer qu’une base pourra contenir suffisamment de variations pour traduire efficacement des phrases plus longues que quelques tokens. D’autre part, les mots communs entre deux langues naturelles sont rares. Il s’agit d’entités nommées, par exemple des noms de personnes ou de lieux, uniquement quand elles n’ont pas de traduction/translittération (exemples d’exceptions : Londres, Il Rodano, Estados Unidos). Les cognats 2 ne rentrent pas dans cette définition car ils ont souvent des différences morphologiques ou flexionnelles. Par exemple, les mots nuit, night, et Nacht sont cognats, mais le transfert de l’un vers l’autre n’est pas trivial malgré leur parenté. La rareté de ces transferts directs d’expressions entre langues naturelles rend cette approche analogique naïve proche d’un apprentissage par cœur. Cela l’exclut donc du paysage des approches réalisables à cause du nombre extrême de formulations possibles dans la langue naturelle. D’autres approches ont été proposées pour la traduction de langues naturelles par analogie, permettant d’éviter ces limitations. Nous les présentons dans la section suivante et discutons également de leurs propriétés par rapport à l’approche directe.
Base d’exemples bash
Les tableaux 5.2 et 5.3 montrent respectivement les résultats obtenus pour les tests sur l’ensemble QUOTIDIEN et sur l’ensemble NOUVEAU, sans application de la génération par analogie. La dernière colonne (match exact), reportant les performances en s’appuyant uniquement sur la correspondance exacte d’un exemple du corpus à la requête de l’utilisateur, a été ajoutée pour comparaison. Les requêtes qui sont traitées par correspondance exacte sont également trivialement couvertes par l’approche directe et par l’approche indirecte (à l’aide d’analogies canoniques par exemple). Le score obtenu en utilisant exclusivement les analogies indirectes indique à quel point l’ensemble de test et la base d’exemples sont similaires en termes de vocabulaire (paramètres des requêtes compris). En effet, aucune proportion respectant le comptage des tokens ne peut être constituée si l’un des tokens de la requête est absent de la base d’exemples. Les tests sur l’ensemble QUOTIDIEN soulignent clairement la proximité de cet ensemble à la base d’exemples avec les 47% de bonnes réponses données. L’absence de requêtes couvertes par la méthode directe pour l’ensemble NOUVEAU atteste quant à elle de la nouveauté du vocabulaire utilisé dans cet ensemble de test, et en particulier de la variation systématique des paramètres. Le score obtenu grâce aux analogies directes seules rend compte de la proportion des requêtes de test qui sont identiques à au moins une requête du corpus à l’exception éventuelle de leurs paramètres. Les 4% obtenus sur QUOTIDIEN attestent de la variation linguistique introduite lors de la collecte de la base globale. Les scores reportés sont des bornes inférieures du nombre de proportions analogiques existantes pour résoudre les requêtes de test, car les mauvaises solutions à des équations analogiques sont également des sources d’erreurs possibles. Cependant, ces mauvaises solutions analogiques sont rares, comme en témoignent les très faibles différences entre le ratio de réponses données et le score considérant tous les silences comme des erreurs. Par ailleurs, on peut constater que le score des méthodes directe et indirecte utilisées ensemble ne correspond pas exactement à la somme des scores de chacune des méthodes prises séparément. Cela s’explique par l’existence de certaines requêtes traitées par chacune des méthodes. Les cas les plus triviaux et les plus nombreux de cette situation sont les requêtes également résolues par correspondance exacte. Les autres cas, plus rares, peuvent être illustrés par l’exemple 5.9. Le token « ps » est consiéré comme un paramètre lors de la résolution directe, mais comme un mot du lexique lors de la résolution indirecte. Cela contraint pour le cas indirect à trouver dans la base autres requêtes dont au moins l’une utilise déjà ce terme.
Analyse des résultats
La relaxation de la contrainte de comptage pour la recherche de requêtes dans la base d’exemples permet une augmentation remarquable du rappel tout en limitant l’impact sur la précision sur l’ensemble QUOTIDIEN. Le facteur le plus limitant est en réalité la durée d’exécution qui devient rapidement irréaliste pour une utilisation instantanée. C’est également un facteur à surveiller lors de l’utilisation de base d’exemples de plus grande taille ou encore pour la mise en place d’un enrichissement incrémental de la base. Au delà d’une déviation (sur la recherche) de 2, ou pour des bases plus grandes, il devient nécessaire d’utiliser des stratégies de sélection efficaces pour conserver des délais de réponse raisonnables. Les tests faisant varier ∆rchr sur l’ensemble NOUVEAU ne montrent en revanche pas une amélioration aussi spectaculaire. C’est un résultat cohérent puisque l’essentiel des réponses correctes sur cet ensemble de test sont produites grâce à des analogies directes (voir l’étude des analogies directes et indirectes présentée en section 5.6). Une faible augmentation du nombre de réponses correctes montre malgré tout que certaines requêtes de l’ensemble NOUVEAU sont suffisamment proches de la base d’exemples disponible pour être capturées après relâchement de la contrainte de comptage. Cependant, la réponse avec succès à des requêtes proches n’est possible que lorsque la commande à produire ne contient aucun symbole absent de la base d’exemples. En effet, il n’est pas pertinent de générer un symbole inconnu, car on ne peut définir une stratégie cohérente pour préférer a priori la génération d’un symbole plutôt que d’un autre parmi l’infinité des possibilités. Concernant les tests faisant varier ∆res, les réponses correctes supplémentaires ne sont obtenues qu’au prix d’une chute importante de la précision. On peut en déduire que le bruit le plus critique dans la base d’exemples se trouve dans la partie en langue naturelle. Ce n’est pas très surprenant, mais il est alors intéressant de remarquer que la relaxation de la résolution a également permis à certaines équations irrésolues de donner des solutions. L’utilisation de la résolution approchée reste en pratique nettement moins coûteuse en temps que la relaxation du comptage car sa complexité algorithmique ne dépend pas de la taille de la base d’exemples. Finalement et malgré la taille modeste des données de test, ces résultats montrent clairement que les méthodes de transfert de langage par analogie formelle ont une importante marge de progression concernant le contrôle du bruit dans la base d’exemples.
|
Table des matières
Introduction
I Objectifs et positionnement
1 Contexte
1.1 Introduction
1.2 Automatisation
1.3 Transfert d’un langage vers un autre
1.3.1 Traduction automatique
1.3.2 Transfert depuis la langue naturelle vers le langage formel
1.3.3 Le transfert comme un problème de sélection
1.4 Interactivité
1.4.1 Modélisation du dialogue
1.4.2 Systèmes de dialogue à but de communication sociale
1.4.3 Systèmes orientés tâche
1.5 Apprentissage interactif
1.5.1 PLOW : Un exemple d’assistant opérationnel incrémental
1.5.2 Problématique : vers une première modélisation
2 Collecte de bases d’exemples
2.1 Introduction
2.2 Format
2.3 Sources
2.4 Méthodes de collecte
2.4.1 Corpus R : équilibré
2.4.2 Corpus bash1 : reformulations
2.4.3 Corpus bash2 : indépendance des participants
2.5 Analyse des bases collectées
2.5.1 Le problème de la représentativité
2.5.2 Analyses
2.6 Conclusion et discussion
3 Étude préliminaire
3.1 Introduction
3.2 Approche naïve par association directe et similarité de surface
3.2.1 Topologie des associations
3.2.2 Sélection
3.2.3 Description de l’approche
3.2.4 Prétraitements syntaxiques
3.3 Application
3.3.1 Comparaison des mesures de similarité
3.3.2 Autoriser le silence
3.3.3 Combinaisons
3.4 Conclusion
3.4.1 Bilan
3.4.2 Autre application à l’approche par similarité
Bilan et nouvel axe de la problématique
II L’analogie comme moteur d’inférence incrémental
4 Raisonnement par analogie formelle
4.1 Introduction
4.2 Conventions de notation
4.3 Définitions et algorithmes
4.4 Optimisations et heuristiques
4.5 Conclusion
5 Analogie pour le transfert de langages
5.1 Introduction
5.2 Transfert analogique direct
5.3 Transfert analogique indirect
5.3.1 Principe et algorithmes
5.3.2 Optimisations et heuristiques
5.4 Complémentarité des approches
5.5 Génération par analogie
5.6 Protocole expérimental
5.7 Résultats
5.7.1 Base d’exemples bash1
5.7.2 Comparaison avec les bases R et bash2
5.7.3 Remarque sur les indicateurs considérés
5.8 Conclusion
6 Relâcher les contraintes analogiques
6.1 Introduction
6.2 Résolution analogique approchée
6.2.1 Dissimilarité analogique
6.2.2 Application dans un cadre plus général
6.3 Recherche approchée de proportions
6.4 Confrontation aux données de la tâche
6.4.1 Mise en place expérimentale
6.4.2 Résultats sur la base bash1
6.4.3 Résultats sur la base R
6.4.4 Résultats sur la base bash2
6.5 Conclusion
6.5.1 Discussion
6.5.2 Bilan
7 Vers un apprentissage incrémental
7.1 Introduction
7.2 Protocole expérimental
7.3 Influence de l’ordre d’apprentissage
7.4 Arrêt subit de l’apprentissage
7.5 Introduction d’un utilisateur nouveau
7.6 Extension automatique de la base d’exemples
7.7 Comparaison avec les bases R et bash2
7.8 Conclusion
8 . Bilan et pistes à l’étude
8.1 Bilan
8.1.1 Transferts direct et indirect
8.1.2 Extension des bases
8.1.3 Relaxation
8.1.4 Incrément
8.2 Pistes de segmentation à l’étude
8.2.1 Motivation et enjeux
8.2.2 Approches
8.2.3 Bilan et pistes
III Conclusion
9 . Conclusion générale et perspectives
9.1 Contributions
9.1.1 Recueil de bases d’exemples
9.1.2 Transfert depuis la langue naturelle vers le langage formel
9.1.3 Vue d’ensemble des résultats
9.2 Perspectives
9.2.1 Exploration
9.2.2 Exploitation
9.2.3 Voies sur le long terme
Index
Bibliographie
Télécharger le rapport complet
