チョムスキー標準形の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,x_L\)の添え字を\(i,j,k\)とする.

外側アルゴリズム

\(x_{i\ldots j}=x_i,\ldots,x_j\)が\(M_v\)で構文解析されるとき（条件付き確率），
その外側の\(x_{1\ldots i-1}, x_{j+1\ldots L}=x_1,\ldots,x_{i-1}, x_{j+1},\ldots,x_L\)の
あらゆる構文解析の確率の和\(\beta(i,j,v)\)（外側確率）の動的計画法

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

位置\(i\)から\(j\)の部分配列(白丸)を生成し非終端記号\(v\)に根を持つ部分木を除くすべての構文解析木の確率の合計\(\beta(i,j,v)\)（外側確率）の再帰的計算の様子． 上図は外側アルゴリズムの再帰式の第1項に相当し， 非終端記号\(y\)と部分配列\(1,\ldots,k-1,j+1,\ldots,L\)に対する外側確率， 部分配列\(k,\ldots,i-1\)を埋める非終端記号\(z\)に対する内側確率， \(y \rightarrow zv\)の遷移確率を\(\beta(i,j,v)\)にまとめている． 下図は再帰式の第2項に相当し， 除外部分配列\(i,\ldots,k\)の非終端記号\(y\)に対する外側確率， 部分文字列\(j+1,\ldots,k\)を埋める状態\(z\)の内側確率， \(y \rightarrow vz\)の遷移確率をまとめている．