Des règles aux probabilités

Faire maîtriser la langue à une machine est l’un des plus vieux rêves de l’informatique. En 1950, Alan Turing propose déjà de juger l’intelligence d’une machine à sa capacité de converser : c’est le jeu de l’imitation du Module 1. La science-fiction en a fait l’un de ses thèmes favoris :

• l’ordinateur HAL 9000 de 2001 : l’odyssée de l’espace (Stanley Kubrick, 1968), qui converse calmement avec les astronautes, avant de leur désobéir ;
• l’ordinateur de bord de Star Trek (1966), à qui l’équipage pose ses questions à voix haute ;
• le robot C-3PO de La Guerre des étoiles (1977), qui parle des millions de langues ;
• Samantha, l’assistante vocale dont s’éprend le héros de Her (Spike Jonze, 2013).

Le rêve de comprendre toutes les langues est plus ancien encore. Il remonte au récit de la tour de Babel, et la science-fiction l’a repris avec le « poisson de Babel » du Guide du voyageur galactique (Douglas Adams, 1979) : glissé dans l’oreille, il traduit instantanément tout ce qu’on entend.

Ce rêve semble aujourd’hui en partie réalisé. Les grands modèles de langage donnent l’impression d’être apparus d’un coup, en 2022. Ils sont pourtant l’aboutissement de soixante-dix ans de recherche en traitement automatique de la langue (natural language processing, NLP), le domaine qui cherche à faire lire, écrire, traduire ou transcrire la langue humaine par une machine. Cette recherche a connu trois grandes approches : écrire des règles, compter des statistiques dans de grandes collections de textes, puis entraîner des réseaux de neurones.

Ce chapitre et le suivant, « Les outils statistiques », présentent les deux premières. Les chapitres « Des mots aux nombres » et « Prédire le mot suivant » présentent la troisième. Plusieurs idées nées bien avant les réseaux de neurones sont encore au cœur des LLM : le modèle de langage lui-même, la façon de le mesurer, et l’idée de produire la suite la plus probable d’un texte.

Les règles (1954-1980)

Le 7 janvier 1954, à New York, IBM et l’Université de Georgetown présentent une machine qui traduit du russe vers l’anglais. L’ordinateur IBM 701 traduit une soixantaine de phrases choisies avec soin, à l’aide d’un vocabulaire de 250 mots et de six règles de grammaire. La démonstration fait les manchettes, et ses organisateurs prédisent que la traduction automatique sera au point d’ici trois à cinq ans. C’est la guerre froide, et traduire automatiquement les publications scientifiques soviétiques intéresse beaucoup le gouvernement américain.

En 1957, le linguiste Noam Chomsky publie Structures syntaxiques (Syntactic Structures). Il y décrit une langue par une grammaire générative (generative grammar) : un petit ensemble de règles capable de produire toutes les phrases correctes de la langue, et seulement celles-là. Analyser une phrase avec ces règles produit un arbre syntaxique (parse tree), qui montre comment elle se décompose en groupes de mots. Il y conteste aussi l’idée de décrire la langue par des probabilités, avec un exemple resté célèbre : « Colorless green ideas sleep furiously » (« D’incolores idées vertes dorment furieusement »). La phrase n’a pas de sens, mais elle est grammaticale, alors que les mêmes mots à l’envers, « Furiously sleep ideas green colorless », ne le sont pas. Or aucune des deux phrases n’avait jamais été écrite. Pour un modèle qui ne fait que compter les suites de mots déjà vues, elles seraient donc toutes deux impossibles, au même titre. L’argument pèse lourd. Pendant une vingtaine d’années, l’approche dominante consiste à écrire des règles à la main : des dictionnaires, des grammaires, des règles pour passer d’une langue à l’autre. Nous verrons plus bas comment les statistiques ont fini par répondre à Chomsky.

Les résultats déçoivent. En 1966, un comité consultatif du gouvernement américain, l’ALPAC (Automatic Language Processing Advisory Committee), conclut que la traduction automatique est plus lente, moins exacte et deux fois plus chère qu’un traducteur humain. Le financement s’effondre. C’est l’un des premiers revers de l’IA, avant les hivers présentés au Module 1. La même année, ELIZA imite un psychothérapeute avec quelques règles de reformulation, et en 1970, SHRDLU converse en anglais sur un petit monde de blocs. Les deux impressionnent, mais aucun ne sort de son domaine.

Les systèmes à règles réussissent pourtant quand le domaine est étroit. À l’Université de Montréal, le groupe TAUM (Traduction automatique de l’Université de Montréal) met au point TAUM-MÉTÉO, qui traduit de l’anglais vers le français les bulletins météorologiques d’Environnement Canada. La langue des bulletins est répétitive et prévisible (« nuageux avec éclaircies », « possibilité d’averses »). Mis en service à la fin des années 1970, le système traduit les bulletins de tout le pays pendant plus de vingt ans, jusqu’en 2001.

Le tournant statistique

Dans les années 1970, une autre approche naît dans les laboratoires d’IBM, autour de la reconnaissance de la parole. Plutôt que d’écrire des règles de phonétique et de grammaire, l’équipe de Frederick Jelinek apprend des probabilités à partir de grandes quantités de parole enregistrée et de texte. Les résultats sont tels qu’on attribue à Jelinek une boutade restée célèbre : « Chaque fois que je renvoie un linguiste, la performance du système augmente. » C’est le renversement présenté au Module 2 : plutôt que de dire à la machine comment faire, on lui donne des exemples, et elle apprend.

Le filtre à pourriels du Module 2, que vous construisez dans le travail noté 2, appartient à ce même tournant. Plutôt que d’écrire des règles comme « si le courriel contient gratuit, c’est un pourriel », on estime, à partir de courriels déjà triés, la probabilité de chaque mot dans les pourriels et dans les courriels ordinaires. Popularisée en 2002 par l’essai « A Plan for Spam » de Paul Graham, la méthode est vite adoptée par la plupart des messageries. Le Module 2 la replaçait d’ailleurs parmi les autres succès du tournant probabiliste, aux côtés des travaux de Jelinek.

Cette approche demande des corpus, c’est-à-dire de grandes collections de textes. Le Brown Corpus, réuni à l’Université Brown dans les années 1960, rassemble un million de mots d’anglais américain publiés en 1961. Le Penn Treebank (1993) annote des millions de mots, surtout tirés d’articles du Wall Street Journal, avec la catégorie grammaticale de chaque mot et la structure de chaque phrase. Pour la traduction, IBM utilise un corpus canadien, le Hansard, le compte rendu des débats du Parlement du Canada, publié dans les deux langues officielles. Ses millions de phrases traduites par des professionnels deviennent, vers 1990, la matière première de la traduction statistique, présentée au chapitre suivant.

Un modèle de langage

Un modèle de langage (language model) est un modèle qui donne, pour un début de texte, la probabilité de chaque mot qui pourrait venir ensuite. Après « Le chat dort sur le », il donne une probabilité élevée à « canapé », « lit » ou « tapis », une probabilité faible à « toit », et une probabilité presque nulle à « démocratie ». C’est une distribution, au sens du chapitre « Générer », et on peut y tirer des mots au hasard, chacun selon sa probabilité. C’est l’échantillonnage présenté dans ce même chapitre : les mots probables sortent souvent, les mots improbables rarement, mais aucun n’est exclu d’avance.

En notation mathématique, on écrit les mots d’un texte $w_1, w_2, w_3, \dots$ (w pour word, « mot » en anglais). Un modèle de langage donne la probabilité du mot suivant, sachant tous ceux qui le précèdent :

La barre verticale se lit « sachant », comme dans les probabilités conditionnelles de la classification bayésienne du Module 2. Dans l’exemple ci-dessus, $P(\text{canapé} \mid \text{le chat dort sur le}) = 0{,}28$.

Ces probabilités suffisent pour donner une probabilité à un texte entier : on multiplie la probabilité de chaque mot, sachant ceux qui le précèdent.

C’est la règle de la chaîne (chain rule) des probabilités. Elle est exacte : elle ne fait aucune hypothèse sur la langue. Toute la difficulté consiste à estimer chacun de ses facteurs. La même règle permet de générer un texte : on tire $w_1$, puis $w_2$ sachant $w_1$, puis $w_3$ sachant les deux premiers, et ainsi de suite.

Les modèles de langage existaient bien avant ChatGPT, mais ils jouaient un rôle de second plan. Pendant des décennies, ils ont été une pièce parmi d’autres dans des systèmes plus vastes, où d’autres composants faisaient l’essentiel du travail. Le modèle de langage y servait d’arbitre : parmi plusieurs interprétations proposées par le reste du système, il choisissait celle qui ressemble le plus à du vrai texte.

• En reconnaissance de la parole, un premier composant analyse les sons et propose plusieurs suites de mots qui leur correspondent. « Un verre d’eau » et « un vert d’eau » se prononcent de la même façon. Le modèle de langage tranche : la première suite est beaucoup plus probable.
• En traduction automatique, le modèle de traduction propose plusieurs traductions possibles, et le modèle de langage choisit celle qui forme une phrase naturelle. C’est le canal bruité présenté au chapitre suivant.
• Le clavier prédictif d’un téléphone propose les mots les plus probables après ceux qu’on vient de taper. C’est l’un des rares usages où le modèle de langage travaille presque seul, mais il ne prédit qu’un mot à la fois, et c’est l’utilisateur qui écrit.

Personne ne demandait alors à un modèle de langage d’écrire seul un texte. Ceux qu’il produisait perdaient le fil au bout de quelques mots, comme le montre l’applet ci-dessous. Il faudra attendre les grands modèles de langage, et surtout ChatGPT, en 2022, pour que le modèle de langage passe au premier plan. Il n’est plus une pièce du système, il est le système. La même opération, prédire le mot suivant, suffit alors à répondre à des questions, à traduire, à résumer ou à écrire un programme.

Compter : les n-grammes

La façon la plus simple d’estimer ces probabilités est de compter. En 1913, le mathématicien russe Andreï Markov analyse les 20 000 premières lettres du roman en vers Eugène Onéguine, de Pouchkine. Il compte combien de fois une voyelle suit une voyelle, ou une consonne, et montre que ces enchaînements obéissent à des probabilités régulières. Ces suites où chaque élément dépend du précédent s’appellent depuis des chaînes de Markov. En 1948, Claude Shannon, le fondateur de la théorie de l’information, applique la même idée aux mots anglais. Il montre que des mots tirés au hasard en tenant compte du mot précédent produisent des suites qui ressemblent de plus en plus à de l’anglais.

On appelle n-gramme une suite de n mots consécutifs. Un modèle à n-grammes prédit chaque mot d’après les n − 1 mots qui le précèdent, en comptant dans un grand corpus de textes combien de fois chaque mot les a suivis. Le travail noté 4 construit un modèle à bigrammes (n = 2) dans un tableur.

En notation, un modèle à bigrammes remplace chaque facteur de la règle de la chaîne par une approximation qui ne garde que le mot précédent :

C’est l’hypothèse de Markov : le passé lointain est oublié, seul compte le contexte immédiat. Un modèle à trigrammes garde les deux mots précédents, et ainsi de suite. Chaque probabilité s’estime ensuite en comptant :

où $C$ désigne le nombre d’occurrences dans le corpus. Si « capitaine » apparaît 1 000 fois dans un corpus, et « capitaine Nemo » 400 fois, alors $P(\text{Nemo} \mid \text{capitaine}) = 400 / 1000 = 0{,}4$.

L’applet ci-dessous contient un modèle à n-grammes entraîné sur deux romans de Jules Verne, Le Tour du monde en quatre-vingts jours et Vingt mille lieues sous les mers. À droite, elle affiche le contexte utilisé et les mots suivants les plus probables.

Quelques manipulations à faire :

1. Avec des n-grammes de taille 1, cliquez sur « Générer 40 mots ». Le modèle tire chaque mot selon sa seule fréquence dans les romans, et le texte n’a aucun sens.
2. Passez à la taille 2 et recommencez. Les paires de mots deviennent correctes (« Le capitaine Nemo »), mais les phrases partent dans toutes les directions.
3. Passez aux tailles 3 et 4. Le texte devient plus fluide, mais les passages surlignés se multiplient. Ce sont des suites d’au moins huit mots recopiées telles quelles des romans. Avec trois mots de contexte, la plupart des contextes n’apparaissent qu’une fois dans le corpus, et le modèle ne peut que recopier ce qui les suivait.
4. Cliquez plusieurs fois sur « Mot suivant » et observez la colonne de droite. Quand le contexte n’a jamais été vu, le modèle se replie sur un contexte plus court.
5. Faites varier la température, présentée au chapitre « Générer ».

L’applet montre la limite des n-grammes. Avec 20 000 mots de vocabulaire, il existe 8 000 milliards de suites possibles de trois mots, et même un corpus immense n’en contient qu’une infime partie. Plus le contexte est long, plus il est rare, et plus le modèle recopie au lieu de généraliser. C’est le sur-apprentissage (overfitting) présenté au Module 2. Surtout, un modèle à n-grammes ne sait rien de la ressemblance entre les mots : avoir vu « le chat dort sur le canapé » ne l’aide pas à prédire la suite de « le chien dort sur le ».

Les suites jamais vues : le lissage

Un modèle à n-grammes qui ne fait que compter donne une probabilité nulle à toute suite qu’il n’a jamais vue. C’est grave, parce que la probabilité d’une phrase est le produit des probabilités de ses mots : une seule suite inconnue rend la phrase entière impossible. Or presque tout texte nouveau contient des suites de trois mots jamais vues, même dans un corpus immense.

Le lissage (smoothing) retire un peu de probabilité aux suites observées pour la redistribuer aux suites jamais vues. Plusieurs méthodes se sont succédé.

• Ajouter un. On fait comme si chaque suite possible avait été vue une fois de plus qu’en réalité. C’est la règle de Laplace, du XVIIIᵉ siècle. Pour des bigrammes, avec un vocabulaire de $V$ mots :

  $$P(w_i \mid w_{i-1}) = \frac{C(w_{i-1}\, w_i) + 1}{C(w_{i-1}) + V}$$

  Une suite jamais vue reçoit ainsi une probabilité de $1 / (C(w_{i-1}) + V)$, petite mais pas nulle. La méthode est simple, mais avec un vocabulaire de dizaines de milliers de mots, elle donne beaucoup trop de probabilité aux suites inconnues.

• Good et Turing. Pendant la Seconde Guerre mondiale, à Bletchley Park, en déchiffrant Enigma, Alan Turing et son assistant I. J. Good mettent au point une façon d’estimer la probabilité de rencontrer un élément jamais vu, à partir du nombre d’éléments vus une seule fois. Si beaucoup de suites n’ont été vues qu’une fois, il en reste sans doute beaucoup à découvrir. Good publie la méthode en 1953.

• Le repli (backoff, Slava Katz, 1987). Quand le contexte de trois mots n’a jamais été vu, on se replie sur les deux derniers mots, puis sur le dernier. C’est ce que fait l’applet de la section précédente.

• Kneser et Ney (1995). Leur méthode tient compte de la variété des contextes dans lesquels un mot apparaît. « Francisco » est un mot fréquent, mais il ne suit presque jamais autre chose que « San ». Dans un contexte inconnu, il doit donc recevoir une probabilité faible, alors que « lunettes », moins fréquent mais qui suit toutes sortes de mots, doit en recevoir une forte. Quand il faut se replier, la probabilité d’un mot ne dépend donc pas de sa fréquence, mais du nombre de mots différents qui le précèdent. Cette méthode reste la meilleure jusqu’à l’arrivée des réseaux de neurones.

Le lissage permet aussi de répondre à Chomsky. En 2000, Fernando Pereira entraîne un modèle lissé qui regroupe les mots en classes de mots semblables. Ce modèle juge « Colorless green ideas sleep furiously » environ 200 000 fois plus probable que la même phrase à l’envers. Un modèle statistique peut donc distinguer deux phrases qu’il n’a jamais vues, à condition de généraliser au-delà des suites observées. C’est précisément ce que feront les modèles neuronaux du chapitre « Prédire le mot suivant ».

Mesurer un modèle : la perplexité

Pour comparer deux modèles de langage, il faut, comme pour les classificateurs du Module 2, une métrique, mesurée sur des données que le modèle n’a jamais vues, l’équivalent de l’ensemble de test. On présente donc aux modèles un texte mis de côté. Le taux de bonnes réponses conviendrait mal : avec des dizaines de milliers de mots possibles, même un bon modèle devine rarement le mot exact qui suit. On mesure plutôt la probabilité que chaque modèle donne aux mots qui viennent vraiment. Un bon modèle leur donne une probabilité élevée, même quand ce n’est pas le mot qu’il jugeait le plus probable.

La mesure habituelle est la perplexité (perplexity). Elle s’interprète simplement : une perplexité de 150 signifie que le modèle est, en moyenne, aussi incertain que s’il devait choisir chaque mot au hasard parmi 150 mots également probables. Plus elle est basse, mieux le modèle prédit. Sur des articles de journaux en anglais, un bon modèle à trigrammes lissé atteint une perplexité d’environ 150. Les modèles neuronaux l’ont fait baisser par étapes, et les grands modèles actuels descendent à quelques dizaines, ou moins, selon les textes et la façon de les découper en jetons.

La perplexité n’appartient pas au passé. L’erreur que les grands modèles de langage réduisent pendant leur entraînement est directement liée à leur perplexité : un LLM qui progresse est un LLM dont la perplexité baisse.

La suite de l’histoire

Les n-grammes ne voient que deux ou trois mots, et ils ne savent rien du sens. Le chapitre suivant présente les autres outils de l’ère statistique, qui ont dominé le traitement de la langue jusqu’au début des années 2010 : les modèles de Markov cachés, la traduction statistique, la représentation des documents, et les modèles qui étiquettent les mots.