N-gram
Un N-gram est une séquence contiguë de N éléments extraite d’une séquence plus longue de texte ou de parole, ou de toute autre donnée séquentielle comme des séquences biologiques. Ces éléments peuvent être des lettres, des syllabes, des mots, des paires de bases ADN, ou d’autres unités discrètes, selon le domaine d’application. La valeur de ‘N’ (un entier positif) spécifie la longueur de la sous-séquence.
Le concept fondamental des N-grams repose sur l’idée de décomposer une séquence complexe en sous-unités plus petites et gérables. Par exemple, dans la phrase « le chat est sur le tapis », les 2-grams (ou bigrammes) de mots sont « le chat », « chat est », « est sur », « sur le », « le tapis ». Les 3-grams (ou trigrammes) de mots sont « le chat est », « chat est sur », « est sur le », « sur le tapis ». Un 1-gram est appelé unigramme et correspond simplement à chaque élément individuel de la séquence (par exemple, les mots « le », « chat », « est », « sur », « le », « tapis »).
La génération de N-grams à partir d’une séquence se fait typiquement en utilisant une « fenêtre glissante » de taille N. Cette fenêtre se déplace d’un élément à la fois le long de la séquence, capturant la sous-séquence de N éléments à chaque position. Des marqueurs spéciaux de début et de fin de séquence sont souvent ajoutés pour capturer les N-grams au début et à la fin de la séquence complète.
L’importance des N-grams réside principalement dans leur capacité à capturer le contexte local au sein d’une séquence. Ils sont à la base de nombreux modèles statistiques utilisés pour analyser et prédire des séquences. En comptant la fréquence d’apparition des différents N-grams dans un grand corpus de données (par exemple, un ensemble de textes), on peut estimer la probabilité d’apparition d’un élément donné, connaissant les N-1 éléments précédents. Cette approche probabiliste est fondamentale en traitement du langage naturel et dans d’autres domaines traitant des données séquentielles.
Dans le domaine du Traitement Automatique du Langage Naturel (NLP), les N-grams sont un outil de base omniprésent. Ils permettent de modéliser la structure statistique de la langue sans nécessiter une compréhension linguistique profonde. Bien que des modèles plus complexes existent aujourd’hui, les N-grams restent pertinents pour de nombreuses tâches et servent souvent de baseline ou de composant dans des systèmes plus sophistiqués.
Une application majeure des N-grams est la construction de modèles de langage probabilistes. Un modèle de langage N-gram estime la probabilité d’une séquence de mots P(W) = P(w1, w2, …, wk) en utilisant l’approximation de Markov, qui suppose que la probabilité d’un mot ne dépend que des N-1 mots précédents : P(wi | w1, …, wi-1) ≈ P(wi | wi-N+1, …, wi-1). Ces probabilités sont estimées à partir des fréquences de N-grams observées dans un corpus.
La suggestion de mots et l’auto-complétion, courantes sur les claviers de smartphones et dans les moteurs de recherche, utilisent fréquemment des modèles N-grams. En se basant sur les derniers mots ou caractères tapés (formant un N-1 gram), le système prédit le mot ou caractère suivant le plus probable en consultant les fréquences des N-grams correspondants dans son modèle.
Les N-grams sont également utilisés dans les systèmes de correction orthographique et grammaticale. Des N-grams peu fréquents ou inexistants dans un grand corpus de référence peuvent signaler des erreurs potentielles. Par exemple, si le bigramme « le chat est » est très fréquent mais « le chat et » est rare ou absent, cela peut indiquer une faute de frappe ou une erreur grammaticale.
En traduction automatique statistique (avant l’ère des réseaux neuronaux profonds, mais toujours pertinent dans certains contextes), les N-grams jouaient un rôle crucial. Les modèles de langage basés sur les N-grams évaluaient la fluidité des phrases traduites dans la langue cible, tandis que d’autres modèles (parfois basés aussi sur des N-grams bilingues) évaluaient la fidélité de la traduction par rapport à la source.
La reconnaissance vocale utilise aussi intensivement les N-grams. Les modèles de langage N-grams aident le système à choisir entre des séquences de mots phonétiquement similaires en privilégiant celles qui sont grammaticalement ou statistiquement plus probables dans la langue considérée. Ils complètent le modèle acoustique qui traite le signal audio brut.
La détection de plagiat et la mesure de similarité entre documents peuvent employer les N-grams. En comparant les ensembles de N-grams présents dans deux documents, on peut identifier les passages communs ou évaluer à quel point les documents se ressemblent en termes de contenu séquentiel. Des N-grams longs partagés sont un indicateur fort de copie potentielle.
Pour la classification de textes (par exemple, trier des emails en spam/non-spam) ou l’analyse de sentiments (déterminer si un avis est positif ou négatif), les fréquences des N-grams (unigrammes, bigrammes, trigrammes, etc.) peuvent servir de caractéristiques (features) pour entraîner des modèles d’apprentissage automatique. Certains N-grams peuvent être de forts indicateurs d’une catégorie ou d’un sentiment particulier.
Au-delà du langage, les N-grams sont appliqués en bio-informatique pour analyser les séquences d’ADN, d’ARN ou de protéines. Par exemple, la fréquence de certains K-mers (terme équivalent à N-gram en biologie, où K est utilisé à la place de N) peut aider à identifier des régions fonctionnelles, à assembler des génomes, ou à comparer des séquences entre espèces.
Une nuance importante concerne la nature des éléments formant le N-gram. On distingue principalement les N-grams de caractères et les N-grams de mots. Les N-grams de caractères (séquences de N caractères) sont utiles pour des tâches comme l’identification de la langue, la gestion des mots inconnus ou des fautes de frappe. Les N-grams de mots (séquences de N mots) capturent mieux les relations syntaxiques et sémantiques locales.
Le choix de la valeur de N est crucial et représente un compromis. Un N petit (par exemple, 2 ou 3) produit des modèles plus robustes avec moins de problèmes de sparsité (voir inconvénients), mais capture un contexte très limité. Un N plus grand (par exemple, 4 ou 5) capture un contexte plus large, potentiellement plus informatif, mais conduit à un nombre beaucoup plus élevé de N-grams possibles, augmentant la sparsité et la complexité du modèle. Le choix optimal dépend de l’application et des données disponibles.
Il existe des variations du concept de base, comme les N-grams discontinus, souvent appelés skip-grams. Contrairement aux N-grams classiques qui requièrent la contiguïté des éléments, les skip-grams permettent des « trous » entre les éléments. Par exemple, un 2-skip-trigramme de « le chat gris est sur le tapis » pourrait être « le gris sur ». Les skip-grams peuvent capturer des dépendances non strictement adjacentes.
Le concept de N-gram est étroitement lié à celui de Modèle de Langage. Les modèles de langage N-grams sont une classe spécifique de modèles de langage statistiques qui utilisent les fréquences de N-grams pour estimer les probabilités des séquences.
Mathématiquement, les modèles de langage N-grams sont souvent formalisés en utilisant les probabilités conditionnelles et peuvent être vus comme une application des Chaînes de Markov d’ordre N-1, où l’état actuel (le mot courant) dépend des N-1 états précédents (les N-1 mots précédents).
Un défi majeur avec les N-grams, surtout pour N élevé, est la sparsité des données : de nombreux N-grams possibles n’apparaîtront jamais dans le corpus d’entraînement, même s’il est très grand. Cela conduit à des estimations de probabilité nulles pour des séquences pourtant valides. Des techniques de lissage (smoothing), comme le lissage de Laplace (add-one), le lissage de Good-Turing, ou l’interpolation et le backoff (Kneser-Ney smoothing étant une méthode avancée populaire), sont essentielles pour attribuer une probabilité non nulle aux N-grams non observés.
Bien que les N-grams soient souvent utilisés pour construire des modèles probabilistes, ils peuvent aussi être utilisés comme caractéristiques dans des représentations vectorielles de documents, par exemple en conjonction avec des pondérations comme TF-IDF (Term Frequency-Inverse Document Frequency). Dans ce cas, on calcule le score TF-IDF non seulement pour des mots individuels (unigrammes) mais aussi pour des bigrammes, trigrammes, etc.
Les N-grams contrastent avec des approches plus modernes comme les plongements lexicaux (word embeddings, ex: Word2Vec, GloVe, FastText) ou les modèles basés sur les transformeurs (ex: BERT, GPT). Ces derniers capturent des relations sémantiques plus profondes et des dépendances à longue distance, là où les N-grams se limitent principalement à la cooccurrence statistique locale et à la syntaxe de surface. Cependant, les N-grams peuvent parfois compléter ces modèles, notamment via les N-grams de caractères pour gérer les mots rares ou inconnus.
L’idée d’analyser les séquences de symboles à l’aide de statistiques de sous-séquences remonte au moins aux travaux de Claude Shannon sur la théorie de l’information dans les années 1940, où il utilisait des approximations N-gram pour modéliser l’entropie de l’anglais écrit. Le concept a ensuite été largement adopté et développé en linguistique computationnelle et en traitement du langage naturel à partir des années 1970 et 1980.
L’un des principaux avantages des N-grams est leur simplicité conceptuelle et leur facilité d’implémentation. Compter les occurrences de sous-séquences est une opération relativement simple et les modèles probabilistes de base sont bien compris.
Les N-grams sont également très efficaces pour capturer le contexte local et les collocations (mots qui apparaissent souvent ensemble, comme « fortement recommandé » ou « réseaux sociaux »). Cette information locale est souvent très prédictive dans de nombreuses tâches linguistiques.
Leur robustesse et leur large applicabilité dans divers domaines (texte, parole, bio-informatique, musique, etc.) et pour différentes tâches (modélisation, classification, génération, etc.) en font un outil fondamental dans l’arsenal de l’analyse de données séquentielles.
Cependant, les N-grams souffrent de la malédiction de la dimensionnalité. Le nombre de N-grams possibles croît exponentiellement avec N et la taille du vocabulaire (ou de l’alphabet). Pour un vocabulaire de V mots, il y a V^N N-grams possibles, ce qui devient rapidement ingérable.
Cela conduit directement au problème de la sparsité des données. Même avec des corpus de plusieurs milliards de mots, la plupart des N-grams possibles (surtout pour N >= 3) n’apparaîtront jamais. Estimer de manière fiable les probabilités de ces N-grams rares ou non observés est un défi majeur, nécessitant des techniques de lissage sophistiquées.
Un inconvénient fondamental est l’incapacité des N-grams à modéliser les dépendances à longue distance dans une séquence. Par définition, un modèle N-gram ne regarde que les N-1 éléments précédents, ignorant toute information antérieure. Or, la compréhension du langage ou l’analyse de séquences biologiques nécessite souvent de prendre en compte des contextes beaucoup plus larges.
Enfin, les modèles N-grams sont très sensibles à la taille et au domaine du corpus d’entraînement. Un modèle entraîné sur des articles de presse fonctionnera mal sur des tweets ou des textes médicaux, car les fréquences des N-grams varient considérablement entre les domaines.
En conclusion, malgré leurs limitations, notamment face aux dépendances à longue distance et à la sparsité, et l’émergence de techniques d’apprentissage profond plus puissantes, les N-grams demeurent un concept fondamental et un outil pratique précieux en traitement du langage naturel et dans d’autres domaines d’analyse de séquences. Leur simplicité, leur interprétabilité relative et leur efficacité pour capturer les phénomènes locaux assurent leur pertinence continue, soit comme méthode autonome pour certaines tâches, soit comme composant ou baseline pour des approches plus complexes.