Parsing the Wall Street Journal with the Inside-Outside Algorithm

Parsing the Wall Street Journal with the Inside-Outside Algorithm Yves Schabes Michal Roth Randy Osborne Mitsubishi Electric Research Laboratories Cambridge MA 02139 USA (schabes/roth/osborne@merl.com) Abstract We report grammar inference experiments on partially parsed sentences taken from the Wall Street Journal corpus using the inside-outside algorithm for stochastic context-free grammars. The initial grammar for the inference process makes no ,assumption of the kinds of structures and their distributions. The inferred grammar is evaluated by its predicting power and by com- paring the bracketing of held out sentences imposed by the inferred grammar with the par- tial bracketings of these sentences given in the corpus. Using part-of-speech tags as the only source of lexical information, high bracketing accuracy is achieved even with a small subset of the available training material (1045 sen- tences): 94.4% for test sentences shorter than 10 words and 90.2% for sentences shorter than 15 words. 1 Introduction Most broad coverage natural language parsers have been designed by incorporating hand-crafted rules. These rules are also very often further refined by statisti- cal training. Furthermore, it is widely believed that high performance can only be achieved by disambiguating lexically sensitive phenomena such as prepositional attachment ambiguity, coordination or subcategoriza- don. So far, grammar inference has not been shown to be effective for designing wide coverage parsers. Baker (1979) describes a training algorithm for sto- chastic context-free grammars (SCFG) which can be used for grammar reestimation (Fujisaki et al. 1989, Sharrnan et al. 1990, Black et al. 1992, Briscoe and Wae- gner 1992) or grammar inference from scratch (Lari and Young 1990). However, the application of SCFGs and the original inside-outside algorithm for grammar infer- ence has been inconclusive for two reasons. First, each iteration of the algorithm on a gr,-unmar with n nontermi- nals requires O(n31wl 3) time per t~ning sentence w. Sec- ond, the inferred grammar imposes bracketings which do not agree with linguistic judgments of sentence struc- ture. Pereira and Schabes (1992) extended the inside-out- side algorithm for inferring the parameters of a stochas- tic context-free grammar to take advantage of constituent bracketing information in the training text. Although they report encouraging experiments (90% bracketing accuracy) on h'mguage transcriptions in the Texas Instrument subset of the Air Travel Information System (ATIS), the small size of the corpus (770 brack- eted sentences containing a total of 7812 words), its lin- guistic simplicity, and the computation time required to vain the grammar were reasons to believe that these results may not scale up to a larger and more diverse cor- pus. We report grammar inference experiments with this algorithm from the parsed Wall Street Journal corpus. 341 The experiments prove the feasibility and effectiveness of the inside-outside algorithm on a htrge corpus. Such experiments are made possible by assumi'ng a right br~mching structure whenever the parsed corpus leaves portions of the parsed tree unspecified. This pre- processing of the corpus makes it fully bracketed. By taking adv~mtage of this fact in the implementation of the inside-outside ~dgorithm, its complexity becomes …

Content truncated to 500 words