N-gram

The most common N-gram orders capture different levels of linguistic context:

• Unigram (N=1): A single token, equivalent to a Bag-of-Words model that discards all word order. Example: ['the', 'cat', 'sat']
• Bigram (N=2): A sequence of two adjacent tokens, capturing immediate local dependencies. Example: ['the cat', 'cat sat']
• Trigram (N=3): A sequence of three tokens, often used in language modeling to predict the next word based on the previous two. Example: ['the cat sat', 'cat sat on'] Higher-order N-grams (4-grams, 5-grams) capture more context but suffer from data sparsity.

N-grams can be extracted from two distinct levels of text representation, each serving different purposes:

• Token N-grams: Operate on word-level tokens after tokenization. Used for document classification, topic modeling, and semantic analysis. Example: The phrase 'machine learning' yields the bigram machine_learning.
• Character N-grams: Operate on individual characters, ignoring word boundaries. Essential for handling out-of-vocabulary (OOV) words, spelling variation, and morphologically rich languages. Example: The word 'cat' yields character trigrams ['cat', 'at_', 't__'] with padding. Character N-grams are robust to typos and are widely used in spam detection and language identification.

N-gram language models rely on the Markov assumption: the probability of a word depends only on the preceding N-1 words, not the entire history.

• For a bigram model, P(w_i | w_1, ..., w_{i-1}) ≈ P(w_i | w_{i-1})
• For a trigram model, P(w_i | w_1, ..., w_{i-1}) ≈ P(w_i | w_{i-2}, w_{i-1}) This simplification makes computation tractable by limiting the context window. The probability of a full sentence is the product of its constituent N-gram probabilities, estimated via Maximum Likelihood Estimation from a training corpus.

As N increases, the number of possible N-grams grows exponentially, leading to zero probabilities for unseen sequences. Smoothing techniques address this:

• Laplace (Add-One) Smoothing: Adds a small count to every possible N-gram, preventing zero probabilities.
• Backoff (Katz): If an N-gram count is zero, the model recursively backs off to the (N-1)-gram probability.
• Interpolation: Combines weighted probabilities from different N-gram orders. Example: P(w_i | w_{i-2}, w_{i-1}) = λ₃P(w_i | w_{i-2}, w_{i-1}) + λ₂P(w_i | w_{i-1}) + λ₁P(w_i)
• Kneser-Ney Smoothing: The most effective method, using the diversity of contexts a word appears in rather than raw frequency.

In classical machine learning pipelines, N-grams are converted into sparse numerical vectors for models like Naive Bayes or Support Vector Machines:

• Each unique N-gram in the corpus becomes a dimension in a high-dimensional feature space.
• TF-IDF weighting is applied to downweight common N-grams (like 'of the') and upweight discriminative ones.
• Character N-gram features are particularly effective for language identification and authorship attribution, capturing stylistic fingerprints.
• Despite the rise of neural embeddings, N-gram features remain a strong, interpretable baseline for text classification tasks.

While foundational, N-gram models have inherent limitations that modern architectures address:

• Fixed Context Window: Cannot capture long-range dependencies beyond N tokens, unlike Transformer attention mechanisms.
• Vocabulary Explosion: The number of parameters grows exponentially with N, making storage and computation prohibitive for large N.
• No Semantic Generalization: Treats 'car' and 'automobile' as completely unrelated, unlike word embeddings.
• Modern Role: N-grams are now often used as a component in hybrid retrieval systems (e.g., BM25 for sparse lexical matching) or as features in production-grade spam filters and malware detectors where interpretability and speed are critical.

A text representation model that describes a document as an unordered collection of its constituent words, discarding grammar and word order but keeping track of term frequency. When combined with n-gram features, BoW can capture local word order by treating contiguous sequences as individual vocabulary entries.

• Unigram BoW: Each word is an independent feature
• Bigram BoW: Adjacent word pairs become features
• Trigram BoW: Three-word sequences are indexed

Term Frequency-Inverse Document Frequency is a statistical weighting scheme that reflects how important a word is to a document in a corpus. It increases proportionally with the word's frequency in the document but is offset by its frequency across all documents, effectively dampening common terms.

• TF: Count of term in document / total terms in document
• IDF: log(Total documents / Documents containing term)
• N-gram TF-IDF vectors are standard features for text classification

An empirical law in corpus linguistics stating that the frequency of any word is inversely proportional to its rank in the frequency table. The most frequent word occurs approximately twice as often as the second most frequent word, three times as often as the third, and so on.

• Explains why stop word removal is essential
• N-gram distributions also follow Zipfian patterns
• The long tail of rare n-grams creates sparse feature matrices

The process of transforming raw, unstructured text into a numerical feature vector that can be understood by a machine learning algorithm. N-gram features are a classic extraction method where text is represented as a vector of contiguous token sequence counts.

• Unigram features: Individual word presence/absence
• Bigram features: Capture phrases like 'New York'
• Character n-grams: Robust to spelling variations and typos

A term for any token encountered during inference that was not present in a model's fixed vocabulary. This is a critical challenge for word-level models. Character n-grams and subword tokenization strategies like BPE mitigate OOV issues by decomposing unknown words into known subword units.

• Word n-gram models suffer from OOV on rare terms
• Character n-grams never encounter true OOV tokens
• Subword tokenization balances vocabulary size and coverage