n-gram 言語モデルを勉強する

\( n \)-gram 言語モデルをちょっと理解したい、という気持ちの記事です。

単語列 \( w_1,\cdots,w_n \) の確率 \( P(w_1,\cdots,w_n) \) は、\( \prod^n_i P(w_i\mid w_1,\cdots,w_{i-1}) \) で求められます。 \( n \)-gram 言語モデルでは、この条件付き確率 \( P(w\mid \mathbf{c}) \) の条件部分（＝文脈 \( \mathbf{c} \) ）の長さを \( n-1 \) に固定したものです。

条件付き確率 \( P(w\mid \mathbf{c}) \) は、ある単語列のコーパス上の出現頻度を \( C(\cdot) \) として、 \[ P(w\mid \mathbf{c}) = \frac{C(\mathbf{c}w)}{C(\mathbf{c}\star)}
\] で求められます。\( \star \) は任意の単語です。

ただし、単純に出現頻度をもとに最尤推定で確率を求める、というのでは、出現頻度を数えるのに用いたコーパスに依存し、確率を過大・過小評価してしまうことがあります。 特に、\( n \) が大きければ大きいほど、\( C(\mathbf{c}w) = 0 \) となる可能性は高くなり、\( P(w\mid \mathbf{c}) = 0 \) となってしまう、など。

そのために、(i) \( n \)-gramの出現頻度を一定値 $D$ だけ引く (discount)、(ii) \( n-1 \) 以下の

Kneser-Ney smoothing

• Kneser & Ney (1995) による 絶対値ディスカウント & バックオフ法

• コア・アイデア:

  1. 高次数 n-gram の生起回数を一定値 $D$ だけ引く（discount）
  2. 残りの確率質量を 「文脈を落とした低次数モデル」へ分配（back-off / interpolation）
  3. 低次数側では「語 w が**何通りの文脈で継続（continue）**して現われたか」を使う continuation probability を推定する

式で書くと（2-gram 以上の場合）

ここで $c(\cdot)$ は生起回数，$\lambda(h)=\frac{D\,N_1^+(h*)}{c(h)}$（$N_1^+$ は語彙スムージング用の異タイプ数）です。(scribd.com)

2 ️⃣ 設計思想と狙い

なぜ「継続回数」なのか

頻度の高い機能語 (“of”, “the”) は bigram では高頻度ですが「後続語としてどこにでも現れる」とは限りません。

• Good-Turing や Katz smoothing では 低次数モデルが“頻度”に引きずられる → 語の固有バイアスが残る
• KN は 「どれだけ多様な文脈で続くか」を低次数側の確率基盤にすることで、このバイアスを抑え、高頻度語でも確率を過⼤評価しにくい

1. 2-gram Kneser-Ney の式を分解してみる

2-gram（bigram）の場合，歴史 $h=w_{i-1}$ のあとに語 $w_i$ が続く確率は

• ① 割引後の相対頻度

  • $c(hw_i)$ は bigram $h w_i$ の訓練コーパス出現回数。
  • $D$ は 定数ディスカウント（通常 $0.5!-!1.0$ 程度，データ依存で最適化）。
  • 目的は 「見えている n-gram を少しだけ減らし，未観測 n-gram 用に確率を空ける」 こと。
  • $\max{\,\cdot,0}$ で 出現 1 回だけの n-gram がマイナスにならない ようにする。
  • 分母 $c(h)$ で正規化 → 「割引後でも文脈 $h$ における確率が総和 1」。 (foldl.me)

• ② 余剰確率質量 $\lambda(h)$

  • ①で「引いたぶん」の総量を 低次数モデルへ渡すための重み。

  • 実装では

    \[\lambda(h)= \frac{D \; N_{1}^{+}(h\star)}{c(h)}\]

    ただし $N_{1}^{+}(h\star)$ は 文脈 $h$ と共起した異タイプ数（語彙のユニーク数）。

  • 文脈が多様なほど余剰も大きくなるので，未知語への配分が自然に増える。

• ③ 継続確率 $P_{\text{cont}}(w_i)$

  • 単語 $w$ が「何通りの前接文脈で“後続語”として現れたか」に比例：

    \[P_{\text{cont}}(w)= \frac{\#\{h':c(h'w)>0\}} {\sum_{w'}\#\{h':c(h' w')>0\}}\]
  • これは “頻度”ではなく“文脈の多様性” を測る指標。
  • 例： “Francisco” は出現総数は多いが ほぼ常に “San” の後に続く → 継続確率は低い。 “Wednesday” は数は少ないが 多彩な前置詞の後に続く → 継続確率は比較的高い。
  • これにより，頻度の高い機能語が低次数側で過大評価される問題を回避する。 (medium.com)

🔢 ごく小さな数値例

• “Francisco” の継続文脈は {San, Francisco} の 2 種のみ → 継続確率は低。
• “Wednesday” は {on, at} の 2 種…と少ないデータでも「多様性」が取れる。 → 未知の文脈で “Francisco” が現れる予測確率は “Wednesday” より低くなる。

2. Back-off と Interpolation は同じ？

• Back-off

  • 観測されていれば 高次数 n-gram のみ を使い，0 件なら $n!-!1$ gram へ 落とす。
  • 典型例：Katz back-off；検索コストが低い。(web.stanford.edu)

• Interpolation

  • 常に複数次数を線形結合：

    \[P = \alpha_3 P(3\text{-gram}) + \alpha_2 P(2\text{-gram}) + \alpha_1 P(1\text{-gram})\]

  • 未観測でも $\alpha$ に応じて下位モデルが寄与するので より滑らか。

違い

• 観測 n-gram が存在する場合

  • Back-off: 上位だけ使う
  • Interpolation: 上位を中心に下位も混ぜる

• Modified-Kneser-Ney は Interpolation 方式、オリジナル KN は段階的 Back-off。(scaler.com)

3. Pitman-Yor 過程と Chinese Restaurant Process (CRP)

📌 KN と Pitman-Yor の関係

• 階層 Pitman-Yor（HPYP） を n-gram の各文脈長に重ねると

  1. 各文脈 = 1 店舗（レストラン）
  2. 割引 $d$ ≈ $D/c(h)$
  3. HPYP の予測分布 = Interpolated KN（MAP 推定）になる → KN は “重み付き HPYP の最頻” を閉形式で書いたものと理解できる。(stats.ox.ac.uk)

4. まとめ・要点再掲

1. 2-gram 式の３項： ① 割引後相対頻度（見えているものを減らす） ② 余剰質量（下位モデルへの橋渡し） ③ 継続確率（文脈多様性で未知を推定）
2. Back-off ≠ Interpolation：後者は常に混ぜる点が違い，Modified-KN は後者。
3. Pitman-Yor／CRP は 確率的生成モデル。階層化すると KN がその MAP 推定形になる ― すなわち KN は“ベイズ的 HPYP の近似”。

これで「式の各部が何をしているか」「Back-off と Interpolation の違い」「ベイズ的背景」がつながるはずです。必要があれば数値例やコード例も追補いたしますのでお知らせください。