A Trellis-Based Algorithm For Estimating The Parameters Of Hidden Stochastic Context-Free Grammar

A A Trellis-Based Algorithm For Estimating The Parameters Of Hidden Stochastic Context-Free Grammar Julian Kupiec Xerox Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, CA 94304 ABSTRACT The paper presents a new algorithm for estimating the pa- rameters of a hidden stochastic context-free grammar. In con- trast to the Inside/Outside (I/O) algorithm it does not require the grammar to be expressed in Chomsky normal form, and thus can operate directly on more natural representations of a gram- mar. The algorithm uses a trellis-based structure as opposed to the binary branching tree structure used by the I/O algorithm. The form of the trellis is an extension of that used by the For- ward/Backward algorithm, and as a result the algorithm reduces to the latter for components that can be modeled as finite-state networks. In the same way that a hidden Markov model (HMM) is a stochastic analogue of a finlte-state network, the represen- tation used by the new algorithm is a stochastic analogue of a recursive transition network, in which a state may be simple or itself contain an underlying structure. INTRODUCTION The algorithm described in this paper is concerned with using hidden Markov methods for estimation of the param- eters of a stochastic context-free grammar from free text. The Forward/Backward (F/B) algorithm (Baum, 1972) is capable of estimating the parameters of a hidden Markov model (i.e. a hidden stochastic regular grammar) and has been used with success to train text taggers (Jehnek, 1985). In the tagging apphcation the observed symbols are words and their underlying lexical categories are the hidden states of the model. A context-free grammar comprises both lexical (termi- nai) categories and grammatical (nonterminai) categories. One iterative method of estimation in this case involves parsing each sentence in the training corpus and for each derivation, accumulating counts of the number of times each rule is used. This method has been used by Fujisald et ai. (1989), and Chitrao & Grishman (1990). A more efficient method is the Inside/Outside algorithm, devised by Baker (1979) for grammars that are expressed in Chomsky nor- mal form. The algorithm described in this paper relaxes the requirement for a grammar to be expressed in a nor- mal form, and it is based on a trellis representation that is closely related to the F/B algorithm, and which reduces to it for finite-state networks. The development of the algorithm has various motiva- tions. Grammars must provide a large coverage to accom- modate the diversity of expression present in large collec- tions of unrestricted text. As a result they become more ambiguous. A stochastic grammar provides the capability to resolve ambiguity on a probabilistic basis, providing a practical approach to the problem. It also provides a way of modeling conditional dependence for incomplete grammars, or in the absence of any specific structural information. The latter is exemplified by the approach taken in many current taggers, which have a uniform model of second-order depen- dency between word categories. Kupiec (1989) has experi- mented with the …

Content truncated to 500 words