An Algorithm for Estimating the Parameters of Unrestricted Hidden Stochastic Context-Free Grammars

An Algorithm for Estimating the Parameters of Unrestricted I-Iidden Stochastic Context-Free Grammars Julian Kupiec Xerox Palo Alto Research Center 3333 Coyote Itill Road Palo Alto, CA 94304 ABSTRACT A new algorithm is presented for estimating the pa- rameters of a stochastic context-free grammar (SCFG) from ordinary unparsed text. Unlike the Inside/Outside I/O) algorithm which requires a grammar to be spee- fled in Chomsky normal form, the new algorithm can estimate an arbitrary SCFG without ally need for trans- formation. The algorithm has worst-case cubic com- plexity in the length of a sentence and the number of nonterminais in the grammar. Instead of the binary branching tree structure used by the i/O algorithm, the new algorithm makes use of a trellis structure for com- putation. The trellis is a generalization of that used by the Baum-Welcb algorithm which is used for estimat- ing hidden stochastic regular grammars. Tile paper de- scribes tile relationship between the trellis and the more typical parse tree representation. INTRODUCTION This paper describes an iterative method for esti- mating the parameters of a hidden stochastic context- free grammar (SCFG). The "hidden" aspect arises from the fact that ~ome information is not available when the grammar is trained. When a parsed corpus is used for training, production probabilities can be estimated by counting the number of times each production is used in the parsed corpus. In the case of a hidden SCFG, the characteristic grammar is defined but the parse trees associated with the training corpus are not available. To proceed in this circumstance, some ini- tim prohabilitie~ are assigned which are iteratively re- estimated from their current values, and the training corpus. They are adjusted to (locally) maximize the likelihood of generating the training corpus. The EM algorithm (Dempster, 1977) embodies the approach just mentioned; the new algorithm can be viewed as its ap- plication to arbitrary SCFG's. The use of unparsed training corpora is desirable because changes in the grammar rules could conceivably require manually re- parsing the training corpus several times during gram- mar development. Stochastic grammarsenable ambigu- ity resolution to performed on the rational basis of niost likely interpretation. They also acconnnodate the de- velopment of more robust grammars having high cover- age where the attendant ambiguity is generally higher. Previous approaches to the problem of estimating hidden SCFG's include parsing schemes ill which MI derivations of all sentences in the training corpus are enumerated (Fujisaki et al., 1989; Chitrao & Grishman, 1990)). An efficient alternative is the Inside/Outside (I/O) algorithm (Baker, 1979) which like the new algo- rithm, is limited to cubic complexity in both the num- ber of nonterminais and length of a ~entence. The I/O algorithm requires that tile grammar be in Chonmky normal form (CNF). Tile new algorithm hal the same complexity, but does not have this restriction, dispens- ing with the need to transform to and from GNF. TERMINOLOGY The training corpus can be conwmiently segmented into sentences for puposes of training; each sentence comprisinga sequence of words. A …

Content truncated to 500 words