Since we implemented the Inside-Outside algorithm faithfully to Baker (1979), Lari and Young (1990), there is much room for improvement. Actually Kita gave a refined Inside¬
Outside algorithm (Kita, 1999). There is also an implementation by Mark Johnson of the Inside-Outside algorithm down-loadable from http://www.cog.brown.edu/%7Emj/. The use of such implementations may lead to different conclusions.  We therefore conducted learning experiments with the entire ATR corpus using these two implementations and measured updating time per iteration (Sato et al., 2001). It turned out that both implementations run twice as fast as our naive implementation and take about 630 seconds per iteration while the graphical EM algorithm takes 0.661 second per iteration, which is still orders of magnitude faster than the former two. Regrettably a similar comparison using the entire EDR corpus available at the moment was abandoned due to memory overflow during parsing for the construction of support graphs.

Learning experiments so far only compared time per iteration which ignore extra time for search (parsing) required by the graphical EM algorithm. So a question naturally arises w.r.t. comparison in terms of total learning time. Assuming 100 iterations for learning ATR corpus however, it is estimated that even considering parsing time, the graphical EM algorithm combined with MSLR parser runs orders of magnitude faster than the three implementations (ours, Kita's and Johnson's) of the Inside-Outside algorithm (Sato et al.,
2001). Of course this estimation does not directly apply to the graphical EM algorithm combined with OLDT search, as the OLDT interpreter will take more time than a parser and how much more time is needed depends on the implementaiton of OLDT search. 63 Conversely, however, we may be able to take it as a rough in dication of how far our approach, the graphical EM algorithm combined with OLDT search via support graphs, can go in the domain of EM learning of PCFGs.

## 6.3  Examing The Performance Gap

In the previous subsection, we compared the performance of the graphical EM algorithm against the Inside-Outside algorithm when PCFGs are given, using two corpora and three implementations of the Inside-Outside algorithm. In all experiments, the graphical EM algorithm considerably outperformed the Inside-Outside algorithm despite the fact that both have the same time complexity. Now we look into what causes such a performance gap.

Simply put, the Inside-Outside algorithm is slow (primarily) because it lacks parsing.

Even when a backbone CFG grammar is explicitly given, it does not take any advantage of the constraints imposed by the grammar. To see it, it might help to review how the inside probability e(s,t,A), i.e. P(nonterminal A spans from s-th word to t-th word) (s < t ), is calculated by the Inside-Outside algorithm for the given grammar.

$$e(s,t,\,A)=\sum_{B,C{\mathrm{~s.t.~}}A\to B\,C{\mathrm{~in~the~gram}}\,{\mathrm{m}}\,{\mathrm{a r}}}\sum_{r=s}^{r=t-1}\mathrm{P}(A\to B C)e(s,r,\,B)e(r+1,t,C)$$

Here P(A → BC) is a probability associated with a production rule A → BC . Note that for a fixed triplet (s,t,A), it is usual that the term P(A → BC)c(s,r,B)e(r+1,t,C) is non-zero 63. We cannot answer this question right now as the implementation of OLDT search is not completed.