much ambiguous so that parse trees are sparse and generated support graphs are small, which affects favorably the perforamnce of the graphical EM algorithm.

We therefore conducted the same experiment with another corpus which contains much longer sentences using a more ambiguous grammar that generates dense parse trees. We used EDR Japanese corpus (Japan EDR, 1995) containing 220,000 Japanese news article sentences. It is however under the process of re-annotation, and only part of it (randomly sampled 9,900 sentences) has recently been made available as a labeled corpus. Compared with ATR corpus, sentences are much longer (the average length of 9,900 sentences is 20, the minimum length 5, the maximum length 63) and a CFG grammar Gedr (2,687 rules, converted to Chomsky normal form grammar G*dr containing 12,798 rules) developed for it is very ambiguous (to keep a coverage rate), having 3.0 x 10 8 parses/sentence at length 20 and 6.7 × 10 19 parses/sentence at length 38.

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

Figure 17 shows the obtained curves from the experiments with EDR corpus (the graphical EM algorithm applied to Gedr vs. the Inside-Outside algorithm applied to C (* dr ) under the same condition as ATR corpus, i.e. plotting average time per iteration to process 100 ss gorithm is the average of 20 iterations whereas that for the graphical EM algorithm is the average of 100 iterations. As is clear from the middle graph, this time again, the graphical EM algorithm runs orders of magnitude faster than the Inside-Outside algorithm. At average sentence length 20, the former takes 0.255 second whereas the latter takes 339 seconds, giving a speed ratio of 1,300 to 1. At sentence length 38, the former takes 2.541 seconds but the latter takes 4,774 seconds, giving a speed ratio of 1,878 to 1. Thus the speed ratio even widens compared to ATR corpus. This can be explained by the mixed effects of O( L 3 ),
time complexity of the Inside-Outside algorithm, and a moderate increase in the total size of support graphs w.r.t. L. Notice that the right graph shows how the total size of support graphs grows with sentence length L as time per iteration by the graphical EM algorithm is linear in the total size of support graphs.