Accueil  / Semaine 7 / Modèles de langue

Modèles de langue

Motivation

On peut traiter un texte comme un « sac de mots » mais la pratique nous révèle que, pour ce faire, il est utile d’avoir un « modèle de la langue », c’est-à-dire un modèle basé sur l’analyse des n-grammes.

Une façon simple de construire un tel modèle est d’estimer la fréquence des bigrammes, ce qui nous permettrait, par exemple, de trouver que la phrase « Jean beau porte » n’a pas de sens en français parce que le bigramme « beau porte » est très improbable.

Comme exemple d’application d’un modèle de la langue, notons qu’il est utile, en recherche d’informations, de faire l’étiquetage des catégories syntaxiques (Part-Of-Speech Tagging en anglais), c’est-à-dire qu’il faut distinguer les noms, les verbes, les adjectifs, les prépositions, les pronoms, les conjonctions et les interjections. On peut aussi vouloir distinguer les nombres des couleurs, etc.

Une autre application des modèles de langue est la traduction automatique qui peut être utile en recherche d’informations si tous les textes ne sont pas écrits dans la même langue. Par exemple, si on tente de traduire en français dog house de façon naïve, on arrivera peut-être à chien maison, mais une analyse statistique sur les bigrammes nous apprendra que dog house se traduit généralement par niche.

Nous avons aussi vu dans le premier module un exemple d’application simple des modèles de langue : on peut déterminer dans quelle langue est écrit un texte en considérant la fréquences des n-grammes le constituant. Par exemple, le trigramme de caractères « the » est fréquent en anglais, mais rare en français.

Définition probabiliste

Un modèle de langue est un concept probabiliste. Quelle est la probabilité que les mots « cacaouette pirouette pas de chance » apparaissent dans un texte donné ? Si nous avons un modèle de la langue, nous saurons le dire au moins approximativement.

Le modèle le plus simple consiste à calculer la probabilité de trouver les mots cacaouette, pirouette, pas, de et chance si on choisit un mot au hasard dans des textes en français. Dans ce cas, on pourra dire que la probabilité associée à l’expression « cacaouette pirouette pas de chance » est :

P(\textrm{cacaouette})P(\textrm{pirouette})P(\textrm{pas})P(\textrm{de})P(\textrm{chance})

On peut aussi travailler avec des probabilités conditionnelles plus sophistiquées.

Étant donné une séquence observée de mots comme « cacaouette pirouette », quelle est la probabilité qu’ils soient suivis du mot pas ? On note cette probabilité P(\textrm{pas}|\textrm{cacaouette}, \textrm{pirouette}).

On peut calculer les probabilités assez facilement si on a un grand ensemble de documents (un corpus) par la méthode de vraisemblance maximale. Il suffit simplement de trouver toutes les occurrences du bigramme « cacaouette pirouette » et de voir combien de fois le bigramme est suivi du mot pas, et de faire le ratio « nombre de trigrammes « cacaouette pirouette pas » » sur « nombre de trigrammes commençant par « cacaouette pirouette » ». Si le corpus est vraiment très grand, cette estimation sera fiable.

Lissage

L’estimation des probabilités par vraisemblance maximale a ses limites : quand il s’agit d’estimer de nombreuses probabilités avec une grande quantité d’exemples, mais non infinie, il y aura toujours des problèmes, parfois systématiques.

Dans les faits, il y aura toujours des expressions qui sont correctes et comprises, mais qui ne figurent pas dans un corpus, même très grand. Prenons la phrase : « Jean aime aggraver ceci ou cela. » Quelle est la probabilité de trouver le trigramme « aime aggraver ceci », même dans un corpus très important ? Malgré le fait que ce soit une expression parfaitement correcte, c’est une expression improbable.

On veut donc que notre calcul de probabilité n’associe pas une valeur nulle à un des n-grammes qui n’apparaît pas dans le corpus.

Par exemple, on peut utiliser le lissage de Laplace où on ajoute « 1 » au nombre d’occurrences de tous les n-grammes. En d’autres mots, on prend pour acquis qu’avant même de consulter le corpus, tout n-gramme apparaît au moins une fois. S’il y a trop de mots ou de n-grammes qui n’apparaissent pas ou peu dans le corpus, le lissage de Laplace devient inefficace parce que tous les mots ont pratiquement la même probabilité : 1 sur le nombre de mots. D’autres techniques plus sophistiquées peuvent être utilisées [1]. La technique la plus célèbre étant celle de Good-Turing, parce qu’elle fut utilisée durant la Deuxième Guerre mondiale pour décrypter les communications allemandes. Pour d’autres exemples et des travaux récents sur la question, voir l’article « Question de probabilités... » dans la revue Info Sciences.

La formule de Good-Turing remplace la fréquence d’un élément observé r fois par r’=(r+1) n_{r+1}/n_rn_{r+1} et n_r sont le nombre d’éléments distincts observés r+1 et r fois. Pour calculer la probabilité, on procède ensuite comme on le fait avec la vraisemblance maximale. Cette formule fonctionne bien quand nous avons beaucoup de données.

En résumé. Si vous observez 4 fois le bigramme « la vie » dans un texte comptant 40 bigrammes, vous estimerez, par vraisemblance maximale, qu’un bigramme sur 10 est « la vie ». Les bigrammes qui n’apparaissent pas dans ce texte se voient accorder une probabilité nulle. Supposons que votre vocabulaire comporte 500 bigrammes ; la technique de Laplace associera alors plutôt une probabilité de (4+1)/(40+500)=1 % à ce bigramme et une probabilité de 0.1 % à tout bigramme qui n’est pas présent dans votre texte. D’autres techniques, comme celle de Good-Turing, donnent des résultats différents qui peuvent être plus ou moins valables selon le cas. Si on suppose que tous les bigrammes furent observés une seule fois, sauf « la vie » qui fut compté 4 fois, alors la formule de Good-Turing accorde une probabilité nulle au bigramme « la vie » (parce que n_{5}=0) et aussi aux autres bigrammes observés (parce que n_{2}=0). Par contre, tous les bigrammes non observés obtiennent une fréquence de Good-Turing égale à 40/(500-40) pour une probabilité de 1/(500-40).

Les modèles de langue en recherche d’informations

On a vu comment, étant donné un modèle probabiliste, on peut calculer la probabilité d’un texte donné. On peut utiliser cette technique pour déterminer si un texte est en français ou pas, et ainsi de suite.

Il y a un lien direct avec la recherche d’informations. Prenons cette fois-ci la requête de l’utilisateur (par exemple, une suite de mots) comme étant le « corpus », et calculons la probabilité des divers documents à partir de ce modèle.

Par exemple, si la requête de l’utilisateur Q est « cacaouette pirouette », nous avons que les mots cacaouette et pirouette sont très probables. Supposons qu’il y a 50 mots possibles dans la langue française [2]. On a donc, avec le lissage de Laplace, 50 occurrences par défaut avec les 2 occurrences dans la requête. Tous les mots, sauf cacaouette et pirouette, ont une probabilité de 1/52 \approx 0.19, alors que les mots cacaouette et pirouette ont une probabilité de 2/52 \approx 0.38.

Supposons que la requête est constituée d’un ensemble de termes t_1, t_2, \ldots, t_n. Le modèle de Hiemstra et al. propose que l’on calcule ensuite la pertinence du document comme suit : \textrm{Score}(Q,D)=P(D|Q)=P(D|t_1 t_2 \ldots t_n). Par le théorème de Bayes, nous avons P(D|t_1 t_2 \ldots t_n) = \frac{P(D) P(t_1 t_2 \ldots t_n | D)}{ P(t_1 t_2 \ldots t_n)}. On suppose que la probabilité de la requête, P(t_1 t_2 \ldots t_n), est une constante inconnue 1/c qui ne dépend pas du document ; en supposant l’indépendance de l’occurrence des termes, nous avons \textrm{Score}(Q,D)=c P(D) \prod_{t \in Q} P(t|D).

On peut calculer P(t|D) par vraisemblance maximale : \frac{tf(t,D)}{\vert D \vert } \vert D \vert est le nombre de mots dans le document [3] et tf(t,D) est le nombre de fois que le terme t apparaît dans le document D. On peut aussi fixer P(D)=\frac{\vert D \vert }{ \vert C \vert } \vert C \vert est le nombre de mots contenus dans tous les documents.

Nous avons donc, comme modèle simple, \textrm{Score}(Q,D)=c \frac{\vert D \vert }{ \vert C \vert } \prod_{t \in Q} \frac{tf(t,D)}{\vert D \vert }.

Exemple. Pour illustrer cette version simplifiée du modèle de Hiemstra et al., considérons la requête Q « cacaouette pirouette ». Supposons que nous avons plusieurs documents (totalisant 1000 mots) dont un seul contenant les deux termes (cacaouette et pirouette). Ce dernier document contient les mots « Dans ma pirouette, j’ai perdu ma cacaoutette ». Si un document ne contient pas les deux termes, alors tf(t,D)=0 pour au moins un t et le score sera nul. Par contre, si on retient le seul document contenant les deux termes, nous avons que peu importe le terme t, tf(t,D)=1. Nous avons que \vert D \vert =8 car il y a 8 mots dans le document. Le score sera donc c \frac{8}{1000} (\frac{1}{8})(\frac{1}{8}) ou c/8000 pour le document contenant les deux termes et 0 pour les autres documents.

Le modèle proposé par Hiemstra et al. est en fait plus sophistiqué et estime la valeur de P(t|D), à la fois avec la valeur calculée à partir du document (\frac{tf(t,D)}{\vert D \vert } ), mais aussi avec la valeur calculée à partir du corpus (P(t|C)) de façon similaire à ce que nous avons décrit précédemment.

Activité amusante

- Application sur le web qui génère aléatoirement des textes sur la base de plusieurs modèles de langue.


[1Voir, par exemple, Always Good Turing : Asymptotically Optimal Probability Estimation par
Alon Orlitsky, Narayana P. Santhanam et Junan Zhang.

[2Je fais cette hypothèse parce que, autrement, le lissage de Laplace ne fonctionne pas aussi bien.

[3Dans le document "La vie est la vie", il y a 5 mots, même s’il n’y a que trois mots distincts.