we have to compute the forward and backward probability for every destination and every state. After computing all a t n (q)'s and β t n (q)'s, parameters are updated. So, the total computation time in each iteration of the Baum-Welch algorithm is estimated as O( N 2 LT )
(Rabiner & Juang, 1993; Manning & Schütze, 1999).

To compare this result with the graphical EM algorithm, we use the HMM program DBh in Figure 4 with appropriate modifications to L, the length of a string, Q, the state set, and declarations in Fh for the output alphabets. For a string w = 0102 ···oL, hmm(n,q,[om,om+1,...,or]) in DB h reads that the HMM is in state q E Q at time n and has to output [o,,,,,,,,,,,,] until it reaches the final state. After declaring hmm/1 and hmm/3 as table predicate and translation (see Figure 5), we apply OLDT search to the goal
{ top hmm([01,...,02],Ans) w.r.t. the translated program to obtain all t-explanations for hmm([01,...,01]). For a complexity argument however, the translated program and DB h are the same, so we talk in terms of DB h for the sake of simplicity. In the search, we fix the search strategy to multi-stage depth-first strategy (Tamaki & Sato, 1986). We assume that the solution table is accessible in O (1) time. 40  Since the length of the list in the third argument of hmm/3 decreases by one on each recursion, and there are only finitely many choices of the state transition and the output alphabet, the search termin ates, leaving finitely many t-explanations in the solution table like Figure 6 that satisfy the acyclic support condition respectively. Also the sampling execution of ← hmm(L) w.r.t. DBh is nothing but a sequential decision process such that decisions made by msw atoms are exclusive, independent and generate a unique string, which means DB, satisfies the t-exclusiveness condition, the independence condition and the uniqueness condition respectively. So, the graphical EM algorithm is applicable to the set of hierarchical systems of t-explanations for hmm(w 5 ) (1 ≤ t ≤ T) produced by OLDT search for T observations w 1 , . . , w T of output string.  Put w t = d o z … o t .  It follows from

t'db, = {hmm(m,q,[o'm,...,o'k]) | 1 ≤ m ≤ L + 1,q ∈ Q} ∪ {hmm([o'i,...,o'k])} msw(out(q),m,o,n),msw(tr(q),m,q'), g' E Q ψ DB , (hmm( m ,q , [o x , . . . ,o x ] )   =  hmm(m + 1 ,q' , [o x +1 , · · ,o x ] ) (1 ≤ m ≤ L)
that for a top-goal hmm([oj, . . ,oj,]), there are at most O(N L) calling patterns of hmm/3 and each call causes at most N calls to hmm/3, implying there occur O( NL · N ) = O( N 2 L ) calls to hmm/3. Since each call is computed once due to the tabling mechanism, we have fnum = O(N 2 L). Also fmaxsize = 3. Applying Proposition 5.1, we reach Proposition 5.2  Suppose we have T strings of length L. Also suppose each table operation in OLDT search is done in O(1) time. OLDT time by DB h is O(N 2 LT) and the graphical EM algorithm takes O(N 2 LT) time per iteration where N is the number of states.

O(N²LT) is the time complexity of the Baum-Welch algorithm. So the graphical EM
algorithm runs as efficiently as the Baum-Welch algorithm. 41