Interpolated Kneser-Ney smoothingについて解説する

やぎです．先日スムージング手法について調べる機会があり，その際にInterpolated Kneser-Ney smoothingについて日本語でまとめているサイトがなかったので，ここに自分なりにまとめます．

Interpolated Kneser-Ney smoothing

Kneser-Ney smoothingは，絶対割引補間から発展した．2-gram言語モデルの絶対割引補間は， $c(w _ {i - 1})$ を $w _ {i - 1}$ のトレーニングコーパスにおける出現回数，固定割引値を $d$ ，正規化定数を $\alpha$ として，以下の式で与えられる．

$\displaystyle{ \begin{eqnarray} P_{\mathrm{abs}}(w_i|w_{i - 1}) = \frac{\mathrm{max}\bigl(c(w_{i - 1}, w_i) - d, 0\bigr)}{c(w_{i - 1})} + \alpha P_{\mathrm{abs}}(w_i). \tag{1} \end{eqnarray} }$

ここで，San Franciscoの例を考える．このフレーズが，与えられたトレーニングコーパスに豊富にあると仮定する．以下の2つの文

I can't see without my reading glasses.

I can't see without my reading Francisco.

では，上の文の確率のほうが高くなってほしいが，上記仮定より， $P _ {\mathrm{abs}}(\mathrm{glasses})$ < $P _ {\mathrm{abs}}(\mathrm{Francisco})$ となり，式(1)より，与えられたトレーニングコーパスにreading glassesという2-gramがあまり存在しなければ，下の文の確率のほうが高くなってしまうかもしれない．このような問題を解決するために，Kneser-Ney smoothingは，絶対割引補間の2番目の項を以下のように書き換える．

$P_{\mathrm{abs}}(w_i) \to P_{\mathrm{continuation}}(w_i).$

与えられたトークン $w$ に対するこの確率は，その $w$ が完成させる2-gramの語彙数に比例する．

$P_{\mathrm{continuation}}(w) \propto \Bigl|\bigl\{w_{i - 1}: c(w_{i - 1}, w) > 0\bigr\}\Bigr|.$

この量は，2-gramの語彙数で割ることによって正規化される（ $j$ は自由変数）．

$\displaystyle{ P_{\mathrm{continuation}}(w) = \frac{\Bigl|\bigl\{w_{i - 1}: c(w_{i - 1}, w) > 0\bigr\}\Bigr|}{\Bigl|\bigl\{(w_{j - 1}, w_j): c(w_{j - 1}, w_j) > 0\bigr\}\Bigr|}. }$

$P _ {\mathrm{abs}}(w_i)$ は単に， $w_i$ が出現する可能性がどれほどあるのかを表すのに対して， $P_{\mathrm{continuation}}(w_i)$ は， $w_i$ がunfamiliarな2-gramの文脈の中に出現する可能性がどれほどあるのかを表す．以上をまとめて，2-gram言語モデルのKneser-Ney smoothingは， $u(w _ {i - 1})$ を $w _ {i - 1}$ の後に続く語彙数として，以下の式で与えられる．

$\displaystyle{ P_{\mathrm{kn}}(w_i|w_{i - 1}) = \frac{\mathrm{max}\bigl(c(w_{i - 1}, w_i) - d, 0\bigr)}{c(w_{i - 1})} + \lambda(w_{i - 1})P_{\mathrm{continuation}}(w_i), }$

$\displaystyle{ P_{\mathrm{continuation}}(w_i) = \frac{\Bigl|\bigl\{w_{i - 1}: c(w_{i - 1}, w_i) > 0\bigr\}\Bigr|}{\Bigl|\bigl\{(w_{j - 1}, w_j): c(w_{j - 1}, w_j) > 0\bigr\}\Bigr|}, }$