Acquisition de grammaires lexicalisées pour les langues naturelles

Grammatical inference consists in discovering the rules governing how sentences of a language are formed, that is a grammar of this language. In Gold's model of learning, examples given as input are only sentences belonging to the language. The algorithm must provide a grammar which represents the enumerated language. Categorial grammars are one of the numerous existing formalisms used to represent languages. Kanazawa has shown that some subclasses of these grammars are learnable, but his results do not apply directly to natural languages. In a theoretical viewpoint, we propose to generalize Kanazawa's results to different kinds of gram- mars. General combinatory grammars are a flexible model that permits to define grammatical systems based on rewriting rules. In this framework, we show that some classes of languages are learnable. In order to be maximally general, our results are expressed in the form of criteria on the grammati- cal system rules. These results are applied to several formalisms which are quite well suited for the representation of natural languages. We also address the problem of implementing learning algorithms with real data. Indeed, existing algorithms that are able to learn rich classes of languages are NP-complete. We propose a more flexible learning framework, called partial learning, to bypass this obstacle: the context in which learning takes place is modified, in order to obtain a more realistic algorithmic complexity. We test this approach with some average size data, and obtain quite encouraging results.L'inférence grammaticale désigne le problème qui consiste à découvrir les règles de formation des phrases d'un langage, c'est-à-dire une grammaire de celui-ci. Dans le modèle d'apprentissage de Gold, les exemples fournis sont constitués uniquement des phrases appartenant au langage. L'algorithme doit fournir une grammaire qui représente le langage énuméré. Les grammaires catégorielles sont l'un des nombreux formalismes existants pour représenter des langages. Kanazawa a montré que certaines sous-classes de ces grammaires sont apprenables, mais ses résultats ne sont pas applicables directement aux langues naturelles. Sur le plan théorique, nous proposons de généraliser les résultats de Kanazawa à différents types de grammaires. Les grammaires combinatoires générales sont un modèle flexible permettant de définir des systèmes grammaticaux à base de règles de réécriture. Nous démontrons dans ce cadre que certaines classes de langages sont apprenables. Dans un souci de généralité maximale, nos résultats sont exprimés sous forme de critères sur les règles des systèmes grammaticaux considérés. Ces résultats sont appliqués à plusieurs formalismes relativement adaptés à la représentation des langues naturelles. Nous abordons également le problème de la mise en œuvre de l'apprentissage sur des données réelles. En effet, les algorithmes existants capables d'apprendre des classes de langages intéressantes sont NP-complets. Afin de contourner cet obstacle, nous proposons un cadre d'apprentissage plus souple, l'apprentissage partiel : le contexte d'utilisation est modifié dans le but d'obtenir une complexité algorithmique plus réaliste. Nous testons cette approche sur des données de taille moyenne, et obtenons des résultats relativement encourageants