PPM*言語モデルによるパープレキシティ

パープレキシティ:
ある言語モデルのもとで、対象テキスト（単語列、文字列）が生成される確率の逆数の、
単語（文字）あたりの平均。
たとえば、w1,w2,w3,w4 という単語列に対して
perplexity = ( P(w4|w1w2w3) P(w3|w1w2) P(w2|w1) P(w1) ) ^ (-1/4)
n 乗根を嫌って、
log perplexity = -1/4*( log P(w4| ) + log P(w3| ) + log P(w2| ) + log P(w1) )
もよく使われる。
言語モデルがbigram言語モデルであるときは、
perplexity = ( P(w4|w3) P(w3|w2) P(w2|w1) P(w1) ) ^ (-1/4)

PPM*言語モデル:
確率推定の際に、可変長の文脈（その文字より前の接頭辞の接尾辞）を用いる。
文脈となりうるコーパスの部分文字列の集合を保持する、文脈トライを用いる。
文脈トライは、各ノードまでの部分文字列の頻度をノードに保持する、接尾辞トライである。
ただし、頻度1となったノード以降は、頻度1がコーパスの最後まで続くため、以降をコーパスの中へのポインタとして縮約する。

PPM言語モデルである文字列中の文字が生成される確率は、それまでの文脈のうちに決定性文脈が存在する場合とそうでない場合で
異なる計算がなされる。

決定性文脈とは、それまでの文脈の次の文字が、コーパスでは1種類しかないような文脈である。
言い替えれば、ある文脈が決定性文脈ならば、それまでの文脈がコーパスに存在していなければならず、なおかつ、
コーパスで2種類以上の文字を導いていてはならない。
決定性文脈が存在する文字については、最小の決定性文脈が与える確率を採用する。

ここで、その文字が文脈から導かれている文字と異なっている場合どうするか？
エスケープ確率という考え方を導入する。Method Cにおいて、ある文脈での文字とエスケープの確率は、
その文脈での各文字の頻度（文字の確率に対応）と文字種の数（エスケープの確率に対応）の比率により計算する。
文脈からその文字が導かれていない場合、エスケープ確率と、１つ小さい文脈でのその文字の確率の積を、求める確率とする。

決定性文脈が存在しない場合、対象文字（位置）に対する、コーパスに存在する最長の文脈での確率を採用する。