Witten-Bell smoothingのおぼえ書き

NLP

witten-bell smoothingを実装することがあったのだが、「えっ、何するんだっけ？」となってしまったので、忘れないうちに書いておく。

そもそもスムージングとは？

確率的言語モデルを使うときに役に立つ便利道具。

もっともベーシックな言語モデルは学習コーパスから、モデルを構築する。

で、N-gram系列の確率を計算して、実際に利用する。

でも、実際は、実際に利用するN-gram系列が学習コーパスに出現しないことは、普通にありえる。

じゃあ、学習コーパスにほとんど出現しないN-gram系列の確率はどうすんの？たまたま学習コーパスに出現しなかっただけじゃないの？

「それは違うよね。学習コーパスに出現しなかっただけで、真の確率ではないよね」という思想で、学習コーパスにほとんど出現しなかったN-gram系列にも確率を割り当てる作業のことをスムージングという。

例えば(bi-gramの例)

Tokyo city is big city in Japan と Nara city is big city in Japanというテスト文を考えてみる。 学習コーパスが東京に偏ったコーパスだったとしたら、学習コーパスの中にTokyo cityはよく出現するが、Nara cityはそんなに出現しない。

でも、確率は学習コーパスに依存するので、このままだとNara cityが低確率になってしまう。（もしかしたら０になってしまうかもしれない。）

で、Nara cityに確率をもうちょい割り当ててやりましょう。

って感じ。

どうやって確率を割り当てるの？

線形補完っていう黒魔術を使う。

黒魔術の正体はただの式なのだが、bi-gramの場合、式は

P(w_i | w_{i-1}) = lambda_2 * P-ML(w_i | w_{i-1}) + lambda_1 * P(w_i)[1]

ただし、

P(w_i) = lambda_1 * P-ML(w_i) + (1 - lambda_1) * (1 / N)

P-ML(w_i | w_{i-1})が学習コーパスでのbi-gram確率

P-ML(w_i)が学習コーパスでのunigram確率

Nがテストコーパスの総語数

で、lambda_1とlambda_2は何？っていう話になるのだが、このパラメタを調整できるのが、線形補完のミソ。

で、lambdaを推定するために、witten-bell smoothingが出現する。

つまり、witen-bell smoothingはlambdaを計算するアレ

witten-bell smoothingの基本的な考え方は、「後に続く単語の種類数も考えてやろうよ」という考え方。で、種類数が大きほど、lambdaは低くなるはずだよね。と考える。

式は

lambda = 1 - (unique_after(w_i) / (unique_after(w_i) + freq(w_i))[2]

※ 1 - lambda = unique_after(w_i) / (unique_after(w_i) + freq(w_i)) と紹介しているスライドもあるけど、要は同じ

ただし、

unique_after(w_i)はw_iの後(+1インデックス)に出現する単語種類数を返す関数

freq(w_i)はw_iが出現する回数を返す関数

天下りになるが、ここにめっちゃわかりやすいpdfの資料があったので、この例に従う。

splitとconstantは両方ともEuroparlコーパスで993回出現する。

でも後に続く単語も考えてみると，splitの後（+1インデックス）には９種類の単語しかなかった。対して、constantの後には268種類の単語があった。

後につづく(+1インデックス)に出現する種類が多い方ほど、lambdaも小さくすべきだろう。（lambdaを小さくすると、確率が低くなるので）

witten-bell smoothingの式では、後につづく単語種類数が増えると、分子が大きくなって、1 - (unique_after(w_i) / (unique_after(w_i) + freq(w_i))の数値が小さくなる仕組みになっている。

で、計算されたlambdaを線形補完式[1]に代入して、bi-gramの確率を計算する。

まとめ

これで、黒づくめの組織に追い詰められたときも「へっ・・・バーロォ・・・言語モデルはスムージングされてるんだよ・・・」ってセリフは吐けると思います。