conversational sentences, whose minimum length, average length and maximum length are respectively 2, 9.97 and 49. As a skeleton of PCFG, we employed a context free grammar Gatr comprising 860 rules (172 nonterminals and 441 terminals) manually developed for ATR corpus (Tanaka et al., 1997) which yields 958 parses/sentence.

Because the Inside-Outside algorithm only accepts a CFG in Chomsky normal form, we converted Gatr into Chomsky normal form G
atr. G
atr contains 2,105 rules (196 nonterminals and 441 terminals). We then divided the corpus into subgroups of similar length like (L = 1; 2); (L = 3; 4); : : : ; (L = 25; 26), each containing randomly chosen 100 sentences.

After these preparations, we compare at each length the graphical EM algorithm applied to Gatr and G
atr against the Inside-Outside algorithm applied to G
atr in terms of time per iteration by running them until convergence.

![0_image_0.png](0_image_0.png)

Curves in Figure 16 show the learning results where an x-axis is the length L of an input sentence and a y-axis is average time taken by the EM algorithm in one iteration to update all parameters contained in the support graphs generated from the chosen 100 sentences

(other parameters in the grammar do not change). In the left graph, the Inside-Outside algorithm plots a cubic curve labeled \I-O". We omitted a curve drawn by the graphical EM algorithm as it drew the x-axis. The middle graph magnies the left graph. The curve labeled \gEM (original)" is plotted by the graphical EM algorithm applied to the original grammar Gatr whereas the one labeled \gEM (Chomsky NF)" used G
atr. At length 10, the average sentence length, it is measured that whichever grammar is employed, the graphical EM algorithm runs several hundreds times faster (845 times faster in the case of Gatr and 720 times faster in the case of G
atr) than the Inside-Outside algorithm per iteration.

The right graph shows (almost) linear dependency of updating time by the graphical EM

algorithm within the measuared sentence length.

Although some dierence is anticipated in their learning speed, the speed gap between the Inside-Outside algorithm and the graphical EM algorithm is unexpectedly large. The most conceivable reason is that ATR corpus only contains short sentences and Gatr is not