Various probabilities and the Q function are computed by using Proposition A.2 in Appendix A together with our assumptions as follows.

 $P_{DB}\left(G_{l}\mid\boldsymbol{\theta}\right)\quad=\\ \\ \\ P_{\texttt{msv}}\left(S\mid\boldsymbol{\theta}\right)\quad=\\ \\ \\ Q(\boldsymbol{\theta}\mid\boldsymbol{\theta}^{\prime})\quad\stackrel{\mathrm{def}}{=}\\ \\ \\ \\ =\\ \\ \text{where}\\ \\ \eta(i,v,\boldsymbol{\theta})\quad\stackrel{\mathrm{def}}{=}\\ \\$. 
V VDB (Gt) | U (8) PDB ( Pmsw(S 0) SEVDB(Gr) i E I v E Vi PDB(S | G t , 0 ′ ) ln P DB (S, G t | 0 ) t = 1 SEVOB η(i, v, θ ′ η( i, v, θ ′ ) In θ i, v η( i, v, θ ) In v'EVi I)(i, v', 0 i E I v E Vi Pm=w(S | 0) σ i v (S') I'DB ( U', SEVDB (Gc)
Here we used Jensen's inequality to obtain (9).  Note that PDB(Gt | 0)-1 LSE¥DB(Gt)
Pmmv(S | 0) σi,v(S) is the cxpected count of msw(i, ,v) in an SLD refutation of G t . Speaking of the likelihood function L ( θ ) = Π t =1 PDB ( G t | θ ), it is already shown in Subsection 2.2
(footnote) that Q(0 | 0') ≥ Q(0' | 0') implies L(0) ≥ L(0'). Hence from (9), we reach the procedure learn-naive(DB,G) below that finds the MLE of the parameters. The array variable n[i, v] stores n(i, v, 0) under the current 0.

1: procedure learn-naive(DB,G) begin 2: Initialize 0 with appropriate values and ε with a small positive number ;
% Compute the log-likelihood.

3: $\lambda^{(0)}:=\sum_{t=1}^{T}\ln P_{DB}(G_{t}\mid\mathbf{\theta})$; % C 4: **repeat** 5: **foreach**$i\in I,v\in V_{i}$**do** 6: $\eta[i,v]:=\sum_{t=1}^{T}\frac{1}{P_{DB}(G_{t}\mid\mathbf{\theta})}\sum_{S\in\psi_{DB}(G_{t})}$ 7: **foreach**$i\in I,v\in V_{i}$**do** 8: $\theta_{i,v}:=\frac{\sum_{v^{\prime}\in V_{i}}\eta[i,v^{\prime}]}{\sum_{v^{\prime}\in V_{i}}\eta[i,v^{\prime}]}$; % 9: $m:=m+1$; 10: $\lambda^{(m)}:=\sum_{t=1}^{T}\ln P_{DB}(G_{t}\mid\mathbf{\theta})$ % C 11: **until**$\lambda^{(m)}-\lambda^{(m-1)}<\varepsilon$ %
$P_{\bf{max}}(S\mid\theta)\sigma_{i,v}(S)$;  $(G_{t})$  % Update the p armeters.  % Compute the log-likelihood again. % Terminate if converge d.  
This EM algorithm is simple and correctly calculates the MLE of 0, but the calculation of PDB(G t | 0) and η [ i,v ](Line 3, 6 and 10) may suffer a combinatorial explosion of explanations. That is, l ψ DB ( G t )     often grows exponentially in the complexity of the model.

For instance, | ψ DB ( G t ) | for an HMM with N states is O ( N L ), exponential in the length L
of an input/output string. Nonetheless, suppressing the explosion to realize efficient computation in a polynomial order is possible, under suitable conditions, by avoiding multiple computations of the same subgoal as we see next.