N-Gramme

N-Gramme

N-gramme

Un n-gramme est une sous-séquence de n éléments construite à partir d'une séquence donnée. L'idée semble provenir des travaux de Claude Shannon en théorie de l'information. Son idée était que, à partir d'une séquence de lettres donnée (par exemple "par exemple") il est possible d'obtenir la fonction de vraisemblance de l'apparition de la lettre suivante. À partir d'un corpus d'apprentissage, il est facile de construire une distribution de probabilité pour la prochaine lettre avec un historique de taille n. Cette modélisation correspond en fait à un modèle de Markov d'ordre n où seules les n dernières observations sont utilisées pour la prédiction de la lettre suivante. Ainsi un bigramme est un modèle de Markov d'ordre 2.

À partir du (court) corpus "par exemple", nous obtenons :

Pas d'historique (unigramme) :

  • p : 2 occurrences sur 10 lettres = 1/5 ;
  • e : 3 occurrences sur 10 lettres = 3/10 ;
  • x : 1 occurrence sur 10 lettres = 1/10 ;

... La somme des probabilités étant nécessairement égale à 1.

Historique de taille 1 (on considère la lettre et un successeur) :

  • p-a : 1 occurrence sur 9 couples = 1/9 ;
  • p-l : 1 occurrence sur 9 couples = 1/9 ;
  • p-e : 0 occurrence sur 9 couples = 0 ;

... La somme des probabilités étant toujours nécessairement égale à 1.

Nous obtenons des probabilités conditionnelles nous permettant de connaître, à partir d'une sous-séquence, la probabilité de la sous-séquence suivante. Dans notre exemple, P(a | p) = 1 / 9 est la probabilité d'apparition de l'élément a sachant que l'élément p est apparu.

À titre d'exemple, le bi-gramme le plus fréquent de la langue française est de, comme dans l'article de, mais aussi comme dans les mots demain, monde ou moderne.

Sommaire

Usage des N-grammes

Les N-grammes sont beaucoup utilisés en traitement automatique du langage naturel mais aussi en traitement du signal. Leur utilisation repose sur l'hypothèse simplificatrice que, étant donnée une séquence de k éléments (k \ge n) la probabilité de l'apparition d'un élément en position i ne dépend que des n-1 éléments précédents.

On a donc P(wi | w1,...,wi − 1) = P(wi | wi − (n − 1),wi − (n − 2),...,wi − 1).

Avec n = 3 (cas du Trigramme), on a P(wi | w1,...,wi − 1) = P(wi | wi − 2,wi − 1).

La probabilité de la séquence : P(w_{1,k}) = P(w_1) \times P(w_2|w_1) \times P(w_3|w_1,w_2) \times ... \times P(w_k|w_1,w_2...w_{k-1})

est transformée en : P(w_{1,k}) = P(w_1) \times P(w_2|w_1) \prod_{i=3}^n P(w_i|w_{i-2, i-1}) (on notera les deux premiers termes conservés, il n'y a en effet pas d'élément en position 0 et -1 de la séquence. Ceci peut-être corrigé en introduisant des termes vides, mais ça n'a que peu d'importance).

Entraînement des N-grammes

Partant de cette hypothèse, il est alors possible d'entrainer les n-grammes à partir d'un corpus. Toujours avec n = 3, il suffit de parcourir le corpus et de noter, pour chaque apparition d'un triplet d'élément (par exemple, pour chaque triplet de caractère ou de mot) le nombre d'apparitions de ce triplet, le nombre d'apparitions du couple en début de triplet et de diviser le premier par le second.

Sur un exemple simple, partant du corpus d'apprentissage "aabaacaab", nous avons les triplets suivants :

  • aab
  • aba
  • baa
  • aac
  • aca
  • caa
  • aab

Dénombrons les, ainsi que les couples :

  • aab : 2 occurrences
  • aba : 1 occurrence
  • baa : 1 occurrence
  • aac : 1 occurrence
  • aca : 1 occurrence
  • caa : 1 occurrence
  • aa : 3 occurrences
  • ab : 1 occurrences
  • ba : 1 occurrence
  • ac : 1 occurrence
  • ca : 1 occurrence

Nous obtenons les tri-grammes suivants :

  • P(aab) = P(b|aa) = \frac{P(aab)}{P(aa)} = 2/3
  • P(aac) = P(c|aa) = \frac{P(aac)}{P(aa)} = 1/3
  • P(aba) = P(a|ab) = \frac{P(aba)}{P(ab)} = 1
  • ...


À partir de ce corpus, on déduit que, si le couple "aa" apparaît, alors la probabilité que l'élément suivant soit "b" est de 2/3, la probabilité que l'élément suivant soit "c" est de 1/3.

Une propriété triviale mais importante est \forall w_i, w_j, \sum_{k} P(w_i,w_j, w_k) = \sum_{k} P(w_k|w_i, w_j) = 1. Ceci se généralise trivialement pour toute valeur de n.

Nous obtenons la chaîne de Markov équivalente :

Chaine-markov-trigramme.png

Limite des N-grammes

Un premier problème se pose : certains triplets n'apparaissent pas dans le corpus d'apprentissage (leur probabilité est donc fixée à 0) mais risquent d'apparaître à l'utilisation. En effet, on sait qu'il est impossible de construire un corpus suffisamment représentatif pour contenir, de façon justement distribuée (c'est-à-dire correspondant à la distribution réelle) l'ensemble des n-grammes d'un langage (par "langage", nous entendons ici une langue naturelle, mais par extension n'importe quelle ensemble de séquences particulier que l'on voudrait soumettre à l'apprentissage par les n-grammes).

Pour pallier ce problème, les probabilités sont "lissées". Le calcul du tri-gramme est approximé et devient :

P(w_n|w_{n-2, n-1}) = \lambda_1 P(w_n) \times \lambda_2 P(w_n | w_{n-1}) \times \lambda_3 P(w_n | w_{n-2}, w_{n-1})

avec λ1 + λ2 + λ3 = 1, P(wn) la probabilité de l'unigramme et P(wn | wn − 1) la probabilité du bi-gramme.

Exploitation des N-grammes

Un exemple complet d'utilisation des N-grammes est présenté dans l'article Algorithme de Viterbi.

Voir aussi

Ce document provient de « N-gramme ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article N-Gramme de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • gramme — [ gram ] n. m. • 1793; sens étym. 1790; gr. gramma, trad. lat. scrupulum « vingt quatrième partie d une once » ♦ Unité de mesure de masse (symb. g) du système C. G. S. valant 10 3 kg. La masse d un centimètre cube d eau pure à 40 C est d environ… …   Encyclopédie Universelle

  • -gramme — ♦ Élément, du gr. gramma « lettre, écriture », signifiant « lettre » (télégramme) ou « graphique » (marégramme, organigramme). gramme élément, du gr. gramma, lettre, écriture . Suffixe de mots: dans le sens de lettre (ex. télégramme); dans le… …   Encyclopédie Universelle

  • Gramme (Begriffsklärung) — Gramme ist der Familienname folgender Personen Georges Gramme (1926–1985), belgischer Politiker Zénobe Gramme (1826–1901), belgischer Konstrukteur und Erfinder Gramme steht außerdem für Gramme, ein Fluss in Thüringen Gramme (Automarke), ehemalige …   Deutsch Wikipedia

  • Gramme — Gewässerkennzahl DE: 56434 Lage Thüringen Flusssystem Saale Abfluss über …   Deutsch Wikipedia

  • Gramme machine — Gramme ma*chine (Elec.) A kind of dynamo electric machine; so named from its French inventor, M. Gramme. Knight. [1913 Webster] …   The Collaborative International Dictionary of English

  • Gramme (Automarke) — Gramme war eine französische Automarke. Unternehmensgeschichte Das Unternehmen Société des Accumulateurs Compound aus Levallois Perret begann 1901 mit der Produktion von Automobilen, die als Gramme vermarktet wurden. Im gleichen Jahr wurde die… …   Deutsch Wikipedia

  • Gramme — Gramme, n. Same as {Gram} the weight. [1913 Webster] …   The Collaborative International Dictionary of English

  • Gramme-Aue — is a Verwaltungsgemeinschaft ( collective municipality ) in the district of Sömmerda, in Thuringia, Germany. The seat of the Verwaltungsgemeinschaft is in Großrudestedt.The Verwaltungsgemeinschaft Gramme Aue consists of the following… …   Wikipedia

  • Gramme —   [gram], Zénobe Théophile, belgischer Elektrotechniker, * Jehay Bodegnée (bei Lüttich) 4. 4. 1826, ✝ Bois Colombes (bei Paris) 20. 1. 1901; wirkte ab 1856 in Paris und war wesentlich an der Entwicklung des Elektromaschinenbaus beteiligt; er… …   Universal-Lexikon

  • Gramme — Gramme, die nominelle Einheit des neuern französischen Gewichtssystems, anstatt des ehemaligen Gros; hat die Schwere eines Cubikcentimètre destillirten Wassers (bei der größten Dichtigkeit des Wassers [+ 4,1° C. od. + 3,28° R.] in luftleerem… …   Pierer's Universal-Lexikon

  • Gramme — (spr. gramm ), Zénobe Théophile, Elektrotechniker, geb. 4. April 1826 in Jehay Bodignée in der Provinz Lüttich, gest. 20. Jan. 1901 in Bois Colombes bei Paris, widmete sich als Modelltischler der Compagnie Alliance in Paris der Elektrotechnik und …   Meyers Großes Konversations-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”