確率文脈自由文法(SCFG)

チョムスキー標準形の確率文脈自由文法(Stochastic Context Free Grammar; SCFG)を考える.
SCFGは以下のような確率付き生成規則(production rule)の集合からなる.
\[ \begin{align}
W_v &\rightarrow W_y W_z : &t_{v,y,z} &= p(W_v\rightarrow w_y W_z)\\
W_v &\rightarrow a : &e_{v,a} &= p(W_v\rightarrow a)
\end{align} \]
文字列 \(x=x_1,\ldots , x_T\)と構文解析木\(\sigma\)の同時確率を考えるのに、HMMと同様に,
\(W_v \rightarrow W_y W_z\) が使われた回数を\(N^t_{v,y,z}(\sigma)\)
\(W_v \rightarrow a\)が使われた回数を\(N^e_{v,a}(x,\sigma)\)
\(\theta =\{\log{t_{v,y,z}},\log{e_{v,a}}\}\)
\(\phi(x,\sigma) = \{N^t_{v,y,z}(\sigma),N^e_{v,s}(x,\sigma)\}\)
と確率変数を変換すると、
\[\begin{align}
\log{p(x,\sigma|\theta)}
&=\sum_{v,y,z\in S} N^t_{v,y,z}(\sigma) \log{t_{v,y,z}}
+\sum_{v\in S,a\in \Sigma} N^e(x,\sigma) \log{e_{v,a}} \\
&= \theta^T \cdot \phi(x,\sigma) = \log{p(\phi(x,\sigma)|\theta)}
\tag{B.2}\label{eq:scfg_log_linear}
\end{align}\]