Soutenance mémoire
L’informatique, d’après l’Académie française se définit comme “la science du traitement rationnel, notamment par machines automatiques, de l’information considérée comme le support des connaissances humaines et des communications dans les domaines technique, économique et social”. D’après cette définition, les outils informatiques développées le sont à deux fins : traiter certains raisonnements de manière automatique et créer des outils de communication efficaces. Une forme naturelle à l’Homme d’exprimer et de véhiculer l’information est le langage. Il est donc légitime de se poser la question du traitement par les ordinateurs d’informations véhiculées par le langage. Cette question fut donc soulevée dès l’avènement de l’informatique, comme en atteste, par exemple, le célèbre test de Turing [Turing, 1950]. Bien que largement discutable, ce test met en exergue différents défis de l’intelligence artificielle, en particulier, la possibilité pour une machine de raisonner, et de communiquer, tel un être humain. Le test se réalise de la manière suivante : une personne A communique, par le langage humain, avec deux interlocuteurs I1 et I2, dont elle est physiquement isolée. Un de ces interlocuteurs est une personne, l’autre étant une machine. Si la personne A ne peut différencier l’interlocuteur humain, de l’interlocuteur artificiel, alors le test est passé avec succès, ce qui est censé conclure à la possibilité pour une machine d’être dôtée de facultés de communication et de raisonnement similaires à celles de l’Homme. Dans cette thèse, nous nous intéressons uniquement à la faculté d’analyse et de génération de langues humaines par une machine ; en particulier, nous regarderons comment une machine peut analyser ou générer des phrases. Toute composante cognitive du langage sera donc exclue de notre étude.
En abordant cette tâche, nous pouvons constater, tout d’abord, la complexité même de cet outil qu’est la langue. Les énoncés sont effectivement des chaînes très structurées, et d’une complexité souvent élevée, comme chacun peut s’en rendre compte durant l’apprentissage d’une langue nouvelle ; par ailleurs, la complexité d’une langue se retrouve tout simplement dans l’ambiguïté de certains énoncés. Qui plus est, les mécanismes de construction de ces énoncés sont, en apparence, très différents d’une langue à une autre. Le travail des linguistes consiste, entre autre, à répertorier et à classifier les langues, d’une part, et d’autre part, à étudier les différents aspects de ces dernières. Nous pouvons ainsi citer la phonétique, qui est l’étude des sons d’une langue ; la prosodie, qui est l’étude des variations mélodiques, temporelles, . . . des sons dans un énoncé ; la morphologie qui est l’étude de la construction des mots et leur catégorisation ; la syntaxe, qui est l’étude de la correction grammaticale d’une phrase ; la sémantique, qui est l’étude du sens d’un énoncé ; la pragmatique, enfin, qui est l’étude de la relation entre un énoncé et un utilisateur de celui-ci (locuteur, auditeur, lecteur, . . . ). La question du traitement par les ordinateurs de l’information transmise par la langue peut donc également être divisée en plusieurs tâches dépendantes, consistant chacune à traiter une des facettes de la langue. Les travaux que nous présentons par la suite, se focalisent sur l’étude de l’interface entre syntaxe et sémantique de phrases. Plus exactement, nous adopterons des modèles de représentation de ces deux aspects d’une phrase, et étudierons des méthodes automatiques permettant de passer de l’une à l’autre de ces représentations .
D’un point de vue technique, une des premières questions est de connaître la puissance calculatoire nécessaire afin de traiter la langue, ou du moins, les problèmes liés à l’interface entre syntaxe et sémantique. Une des théories qui a été créé afin de décrire la notion de puissance de calcul a été exprimée dans [Church, 1936] sous une forme algébrique. Les éléments de cette algèbre, appelés des λ termes, peuvent être réécrits par itérations d’opérations représentant des étapes de calcul. Ces termes peuvent être vus comme des fonctions, la composition de fonction correspondant à un calcul. Le λ-calcul a par ailleurs été à l’origine de l’avènement d’un style de programmation particulier, la programmation fonctionnelle. Différents fragments du λ-calcul peuvent être étudiés ; nous nous intéresserons ici au λ-calcul simplement typé. De plus, cet outil sera utilisé non seulement afin de parler de puissance calculatoire mais également et sutout comme modèles de représentation pour des structures telles que les arbres et des formules de la logique du premier-ordre, ces dernières étant communément utilisées en syntaxe et sémantique formelle.
Ainsi, les travaux que nous présenterons s’intéressent à la calculabilité des sens à partir des phrases (ce que nous appellerons l’analyse grammaticale, ou génération sémantique) et inversement (ce que nous appellerons la génération de textes). Qui plus est, l’informatique met à notre disposition de nombreux outils qui traitent l’information ; en particulier, des outils d’analyse et de génération de langages différents du langage humain (langages de programmations, codes binaires, . . . ). Ainsi, le langage humain est-il si distinct des langages utilisés en informatique ? Nous est-il possible de réutiliser des techniques informatiques existantes et, en particulier, celles utilisées dans le traitement des langages informatiques ?
Richard Montague, philosophe et mathématicien américain proposa une solution partielle à cette question dans les années 1970. Selon lui, le langage humain peut être traité comme un langage informatique. Il proposa de modéliser syntaxe et sémantique sous une forme algébrique, et leur interface par des morphismes. En particulier, il introduisit le λ-calcul simplement typé dans la sémantique formelle des langues, en l’utilisant afin de représenter le sens des entrées lexicales composant une phrase. Le calcul des sens d’une phrase se réduit alors à un problème calculatoire sur le λ-calcul. Cette proposition offrit une perspective nouvelle à des travaux issus de la logique, sur l’analyse grammaticale des phrases. Ainsi, différents systèmes logiques ont été proposés par [Adjukiewicz, 1935, Bar-Hillel, 1950] puis par [Lambek, 1958], sous le nom de grammaires catégorielles, où l’analyse grammaticale des phrases se réduit à un problème de déduction logique. Or, le λ calcul simplement typé étant en lien étroit avec la logique (à travers un morphisme, à l’image de ceux décrits par Montague), l’analyse grammaticale des phrases permet donc, de vérifier la correction grammaticale de celles-ci, d’une part, et de calculer leurs représentations sémantiques, d’autre part.
Les grammaires catégorielles abstraites (ou λ-grammaires), formalisme créé indépendamment par [de Groote, 2001] et [Muskens, 2001], sont issues de ces idées. De fait, il est possible de décrire ces grammaires par la théorie de Montague : les algèbres représentant les formes syntaxiques ou les formes sémantiques des phrases sont des algèbres de construction de λ-termes simplement typés, et l’interface entre la syntaxe et la sémantique est réalisée par des morphismes de termes. Ainsi, le λ-calcul y est utilisé afin de représenter les sens d’une phrase (c.a.d. sa représentation sémantique), ses dérivations, mais aussi la structure des chaînes de caractères les composant (c.a.d. sa représentation de surface). Le formalisme des grammaires catégorielles abstraites se présente donc comme un formalisme uniforme, puisque les termes du λ-calcul simplement typé sont utilisés afin de décrire chaque forme de représentation d’une phrase. De plus, la distinction entre les dérivations d’une phrase (ses structures) et sa réalisation de surface (les chaînes de caractères la composant) y est exprimée de manière explicite. En effet, les constructions de surface sont également obtenues par image homomorphique des termes des dérivations syntaxiques. Ainsi, à l’image des idées de Montague, mais aussi de celles exprimées par [Curry, 1961], le sens et la réalisation de surface sont toutes les deux obtenues comme images homomorphiques des dérivations syntaxiques. Ce point est essentiel afin de comprendre la symétrie entre les tâches de génération de textes et d’analyse grammaticale. Dans le cadre des grammaires catégorielles abstraites, une solution au problème de l’analyse de ces grammaires offre une solution à ces deux tâches.
De plus, ces grammaires s’inscrivent dans une longue tradition de l’informatique fondamentale, puisque de nombreux travaux ont été menés sur les grammaires de chaînes, sur les grammaires d’arbres, ou encore sur les grammaires de graphes. La structure des données considérée dans le cas des grammaires catégorielles abstraites est le λ-terme. De plus, si les termes représentant les dérivations de ces grammaires ont une structure arborescente, nous parlerons de λ-grammaires non contextuelles (ou de grammaires catégorielles abstraites non-contextuelles), faisant ainsi référence au fait que les grammaires non-contextuelles de chaînes ou d’arbres construisent des dérivations qui peuvent etre représentées sous forme d’arbres. Dans le cadre des présents travaux, nous ne nous intéresserons qu’aux grammaires catégorielles abstraites non-contextuelles, entre autres raisons du fait que les dérivations syntaxiques des phrases ont généralement une forme arborescentes pour les linguistes. De plus, l’utilisation des grammaires catégorielles abstraites non contextuelles suffit à modéliser nombre de phénomènes syntaxiques ou sémantiques.
|
Table des matières
1 Introduction
partie I – λ-calcul, typage et jeux
2 λ-calcul et typage
2.1 Syntaxe et opérations du λ-calcul non-typé
2.1.1 Syntaxe du λ-calcul non-typé
2.1.2 Règles de réécriture : α-conversion, β-réduction et η-conversion
2.2 Le λ-calcul simplement typé
2.2.1 Typage à la Curry
2.2.2 Typage à la Church
2.3 Propriétés du λ-calcul simplement typé
2.3.1 Termes η-longs pour un typage
2.3.2 Préservation de typage et β-réduction
2.3.3 Normalisation
2.3.4 Structures de termes et β-expansion
2.4 Logique intuitionniste et λ-calcul simplement typé
2.4.1 Logique minimale et correspondance de Curry-Howard
2.4.2 Unicité de démonstrations en logique minimale
2.5 Conclusion
3 Jeux et λ-calcul simplement typé
3.1 Typage et interaction
3.2 Arènes et typages
3.2.1 Arènes
3.2.2 Occurrences de types et sous-arènes
3.2.3 Curryfication, substitutions de types et morphismes d’arènes
3.3 Stratégies et λ-termes
3.3.1 Justification, innocence et jeux
3.3.2 Stratégies de typage
3.3.3 Préservation de stratégies gagnantes par substitutions de coups
3.3.4 Interprétation de stratégies comme λ-termes
3.3.5 Stratégies recouvrantes et principalité
3.4 Conclusion
3.5 Annexes
3.5.1 Démonstration du Théorème 3.3.4.1
3.5.2 Démonstration du Théorème 3.3.5.1
partie II – Linguistique formelle, λ-calcul et reconnaissance
4 Linguistique formelle et grammaires de λ-termes
4.1 Syntaxe : les langages faiblement sensibles au contexte
4.1.1 La hiérarchie de Chomsky
4.1.2 Les langages faiblement sensibles au contexte
4.1.3 Quelques formalismes MCS
4.2 Sémantique : la compositionnalité
4.2.1 Compositionnalité, logique et λ-calcul
4.2.2 De la syntaxe à la sémantique
4.2.3 Quantificateurs et typage
4.3 Les grammaires catégorielles abstraites
4.3.1 Des grammaires de λ-termes simplement typés
4.3.2 ACGs et formalismes grammaticaux
4.3.3 Une hiérarchie de langages
4.3.4 Traitement de certains phénomènes linguistiques
4.4 Conclusion
5 Programmation logique et analyse grammaticale
5.1 Algorithmes de reconnaissance grammaticale
5.1.1 L’algorithme de Cocke-Younger-Kasami
5.1.2 L’algorithme de Earley
5.2 Reconnaissance grammaticale et déduction logique
5.2.1 Un langage de programmation logique : Datalog
5.2.2 L’exemple des grammaires de clauses définies
5.3 Reconnaissance grammaticale et vérification de typage
5.3.1 Identifier des λ-termes par des typages
5.3.2 Construction de reconnaisseurs Datalog pour les ACGs du second-ordre
5.3.3 Réécriture par ensembles magiques supplémentaires et algorithme de Earley
6 Conclusion
Télécharger le rapport complet
