Inside Algorithm

チョムスキー標準形のSCFG

非終端記号\(W_1,\ldots,W_M\)の添え字を\(v,y,z\)とする. 開始非終端記号は\(W_1\).
確率付き生成規則の形は以下のいずれかの形
遷移確率 \(t_v(y,z)\): \(W_v \rightarrow W_yW_z\)
出力確率 \(e_v(a)\): \(W_v \rightarrow a\) 
配列\(x_{1\ldots L}=x_1,\ldots,x_L\)の添え字を\(i,j,k\)とする.

内側アルゴリズム

\(x_{i\ldots j}=x_i,\ldots,x_j\)が\(M_v\)で構文解析される確率\(\alpha(i,j,v)\)の動的計画法

初期化: for \(i = 1\) to \(L\), \(v = 1\) to \(M\):
\( \alpha(i,i,v) = e_v(x_i) \)
再帰: for \(\ell=1\) to \(L\), \(i=1\) to \(L-\ell\), (\(j=i+\ell)\),\(v=1\) to \(M\)
\(
\alpha(i,j,v) = \sum_{y,z=1}^M \sum_{k=i}^{j-1}
\alpha(i,k,y)\alpha(k+1,j,z)t_v(y,z)
\)
終了処理: \(P(x|\theta) = \alpha(1,L,1)\)

状態\(v\)を根とする構文解析部分木の位置\(i\)から\(j\)までの部分配列に対する内側確率\(\alpha(i,j,v)\)の計算の様子.
\(v \rightarrow yz\)の遷移確率で重みづけし, 状態\(y\)が部分配列\(x_i,\ldots x_k\), 状態\(z\)が部分配列\(x_{k+1},\ldots x_j\)を
生成するような構文解析部分木を, すべての状態\(y,z\)と部分配列の境目\(k\)について足し込むことにより,
再帰的に計算される.