内側アルゴリズムとは

チョムスキー標準形（W_v -> W_x W_y or W_v -> a）の確率文脈自由文法（Stochastic context-free grammar, SCFG)

HMMの前向き、内向きアルゴリズムに対応するアルゴリズム。

ここで、以下のように確率を定義する

• W_v -> W_x W_y に遷移する確率 t_v(x, y)

• W_v -> aと出力する確率 e_v(a)

• 部分文字列x_i...x_jがW_vを根に持つ確率 α(i, j, v) 内側アルゴリズムはこれを全てのi,j,vに対して算出する。

ここで長さLの文字列を考え、Wの総数をMとする

部分文字列x_i...x_jをW_yとW_zを根に持つ部分に分ける。 分け目の数字をiとjの間の数字kであるとすると文字列xi...xkとxk+1...xjに分かれる。

この時求めたい確率（x_i...x_jがW＿vを根に持つ確率）は、上で定義したαを用いて以下のように表される式をすべてのk, y, zに対して足し合わせたものである。

α(i, k, y) * α(k+1, j, z) * t_v(y, z)

ここでα(i, k, y)は配列x_i...x_kがW_yを根に持つ確率、α(k+1, j, z)は配列x_k+1...x_jがW_zを根に持つ確率、t_v(y, z)はW_v -> W_y W_zに遷移する確率である。

内側アルゴリズムは上の式を全てのi,j,vに対して計算するものである。

以下の図に以上の手順をまとめてある。

外側アルゴリズムとは

以下の画像参照