Back-off smoothing - yasuhisa's blog

書いてるとちゅー!!

先週は言語モデル(n-gram)の話があって、パープレキシティの話をして、多項分布の最尤推定だとパープレキシティが無限大にいってしまうからどうにかしないと!!ということをやりました。

言語モデルのよさをはかる指標としてのパープレキシティ - Seeking for my unique color.

「どうにかしないと!!」の具体的な内容としては学習するときのデータには入っていない単語にもある程度確率を付与してやらないといけない、ということです。hoge、fugaという単語が学習データにあって、パープレキシティをはかる法のデータにpiyoというデータがあったら、それにも適当に確率を振るということ。しかし、学習データに出てきていないデータがどれくらいあるかなんて分からないし、どれくらい付与してあげればいいかも直感的にはよく分かりません。

そこで、Back-off smoothingが出てくるんだけど、段階としては二段階からなっています。

最尤推定量は確率を付与しすぎなので、いくらか割り引いてやらないといけない→どれくらい割り引くのか(discounting)
割り引いた確率を(出てきていない)どの単語にどれくらい割り当てるのか→分配

以下、その二つの手続きについて説明。

discounting

discountingの方法には4つくらいあるそうです。

Good-Turing discounting
Absolute discounting
Liner discounting
Witten-Bell discounting

いくつも書くのは面倒なので、Good-Turing discountingについて書こうと思います。

まず、いくつか定義します。

N: 観測事象の総数
$n_r$: r回出現した事象の種類(count-count)
$r n_r$: r回出現した事象の総数

このとき、以下が成立します。
$N = n_1 + 2 n_2 + 3 n_3 + \cdots = \sum_{r=1}^\infty r n_r$
横軸にrを、縦軸に $r n_r$ を取ると、これは指数関数的に減衰していくようなグラフになります。

いままでは一つのコーパスを使って最尤推定していましたが、discountingを計算するために二つのコーパスTとEを用意できたとしましょう(もしくはコーパスを二分割する)。このとき、Tにおいてr回出現する単語の総出現回数は $\sum_{w : C^T(w) = r} r = r n_r^T$ です。一方、同じ単語のコーパスEにおける総出現回数は $\sum_{w : C^T(w) = r} C^E(w) = r^* n_r^T$ で計算できます。これは、コーパスTにおいてr回登場した単語について、コーパスEにおいて登場回数を足し合わせるということです。

$r^* = (\sum_{w : C^T(w) = r} C^E(w)) / n_r^T$