N-gram

概要

N-gramとは、テキストを連続する $N$ 個のトークン（単語または文字）のシーケンスとして表現する手法である。単語単体（unigram）では捉えられない局所的な語順・共起パターンを表現でき、言語モデルや文書分類、機械翻訳など幅広いNLPタスクの基礎となる。シンプルな実装と解釈しやすさが利点だが、$N$ が大きくなるほどデータスパース性の問題が深刻になる。

直感・モチベーション

「New York」という2単語は、それぞれ単独では「新しい」「ヨーク（地名）」を意味するが、隣接することで全く異なる意味（地名）を持つ。単語を独立したトークンとして扱うBag of Wordsでは、この語順情報が失われる。

N-gramはこの問題を、「直前の $N-1$ 単語の文脈を保持する」というシンプルな方法で解決する。

トレードオフは明確である。

• $N$ を大きくする → 文脈が豊かになるが、データスパース性が増す（コーパスに現れない組み合わせが急増する）
• $N$ を小さくする → データが密になるが、局所的な文脈しか捉えられない

数学的定式化

単語列 $w_1, w_2, \ldots, w_T$ に対して、N-gram言語モデルは次の連鎖律を $N-1$ 階のマルコフ仮定で近似する：

$$P(w_1, \ldots, w_T) = \prod_{t=1}^{T} P(w_t \mid w_{t-N+1}, \ldots, w_{t-1})$$

各条件付き確率は最尤推定（MLE）でコーパスから推定する：

$$P(w_t \mid w_{t-N+1}, \ldots, w_{t-1}) = \frac{\text{count}(w_{t-N+1}, \ldots, w_t)}{\text{count}(w_{t-N+1}, \ldots, w_{t-1})}$$

導出を見る

確率の連鎖律（完全な形）：

$$P(w_1, \ldots, w_T) = \prod_{t=1}^{T} P(w_t \mid w_1, \ldots, w_{t-1})$$

これをそのまま推定しようとすると、長い文脈ほどコーパスに出現する頻度が下がりゼロになる（データスパース問題）。

$N-1$ 階のマルコフ仮定を導入すると：

$$P(w_t \mid w_1, \ldots, w_{t-1}) \approx P(w_t \mid w_{t-N+1}, \ldots, w_{t-1})$$

$N=2$（bigram）のとき：

$$P(w_t \mid w_1, \ldots, w_{t-1}) \approx P(w_t \mid w_{t-1}) = \frac{\text{count}(w_{t-1}, w_t)}{\text{count}(w_{t-1})}$$

スムージング（ラプラス平滑化）：

未知のN-gramに対して確率0を割り当てないよう、分子に $\alpha$（通常1）を加える：

$$P_{\text{smooth}}(w_t \mid w_{t-1}) = \frac{\text{count}(w_{t-1}, w_t) + \alpha}{\text{count}(w_{t-1}) + \alpha |V|}$$

ここで $|V|$ は語彙サイズ。

重要な性質・注意点

• データスパース性: $N=3$ でも未知のtrigramが多数現れる。スムージング（ラプラス、Kneser-Ney等）が必須
• 計算量: N-gramの種類数は $O(|V|^N)$ となり、$N$ が増えるほど指数的に増大する
• 文字N-gram: 単語ではなく文字単位で切ると、未知語・スペルミスに強くなる。形態素解析不要な言語にも有効

まとめ

• $N$ 個の連続トークンを1単位として扱うのがN-gram
• マルコフ仮定により言語モデルとして定式化できる
• $N$ が大きいほど文脈が豊かだが、スパース性の問題が深刻
• スムージングは実用上必須。現代ではニューラル言語モデルに置き換えられつつある

実装例

pythonコピー
from collections import defaultdict

def extract_ngrams(tokens: list[str], n: int) -> list[tuple]:
    return [tuple(tokens[i:i+n]) for i in range(len(tokens) - n + 1)]

def build_ngram_model(corpus: list[list[str]], n: int, alpha: float = 1.0):
    counts = defaultdict(int)
    context_counts = defaultdict(int)

    for tokens in corpus:
        for ngram in extract_ngrams(tokens, n):
            counts[ngram] += 1
            context_counts[ngram[:-1]] += 1

    vocab = set(w for tokens in corpus for w in tokens)

    def prob(word: str, context: tuple[str, ...]) -> float:
        ngram = context + (word,)
        return (counts[ngram] + alpha) / (context_counts[context] + alpha * len(vocab))

    return prob

# 使用例
corpus = [
    ["<s>", "彼", "は", "銀行", "に", "行った", "</s>"],
    ["<s>", "私", "は", "銀行", "で", "預金", "した", "</s>"],
]
prob = build_ngram_model(corpus, n=2)
print(prob("銀行", ("は",)))   # P(銀行 | は)
print(prob("預金", ("銀行",))) # P(預金 | 銀行)

---

関連記事

前提知識

• 分散仮説 — 単語の意味は文脈によって決まるという理論的背景

派生技術

• TF-IDF — 単語の重要度を文書頻度で重み付けする手法
• Word2Vec — N-gramの限界（スパース性）をニューラルネットで克服した手法

応用事例

• スペルチェック — 文字N-gramによる誤り検出
• テキスト生成 — N-gram言語モデルによる文の補完

用語解説

用語	説明
N-gram	テキスト中の連続する $N$ 個のトークンのシーケンス
unigram / bigram / trigram	$N=1, 2, 3$ のN-gramそれぞれの呼び名
マルコフ仮定	現在の状態は直前の $N-1$ 状態のみに依存するという仮定
データスパース性	コーパスに出現しないN-gramが多く、確率推定が困難になる問題
スムージング	未観測N-gramに0でない確率を割り当てる手法の総称
ラプラス平滑化	全N-gramの頻度に一定値 $\alpha$ を加えるシンプルなスムージング