Calculating the Probability of a Partial Parse of a Sentence

Calculating the Probability of a Partial Parse of a Sentence bred Kochman and Joseph Kupin Center for Communications Research Institute for Defense Analyses Princeton, New Jersey 08540 ABSTRACT A standard problem in parsing algorithms is Lhe organizaLion o~ branched searches to deal with an~iguous sentences. We discuss shift- reduce parsing o£ stochastic context-Gee granlnmrs and show how Lo construct a probabilistic score for tanking compeLing parse hypotheses. The score we use is the likelihood Lhag the collection of subtrees can be completed into a l~ull parse tree by means of the steps the parser is constrained to [oUow. INTRODUCTION Stochastic context-free grammars have been suggested for a role in speech-recognition algorithms, e.g. [1, 4, 9]. In order to he fully effective as an adjunct to speech recognition, the power of the probability apparatus needs to be applied to the problem of controlling the branched search for parses of ambiguous input. The method we suggest for doing this employs shift-reduce (LR) parsing of context-free grammars together with a probabil- ity based score for ranking competing parse hypotheses. Shift- reduce parsers can be made very efficient for unambiguous gram- mars (and unambiguous inputs) and Tomita [7] shows how much of this efficiency can be maintained in the face of ambiguity. This makes this class of parsers a good candidate for many speech problems. The structural simplicity of shift-reduce parsers makes the analysis of the interaction of the parser with the stochastic properties of the language particularly clean. The score we calculate is the likelihood that the collection of subtrees constructed by the parser so far can he completed into a full parse tree by means of the steps that the parser is constrained to follow, taking into account all possibilities for the unscanned part of the input. This score is the same as that suggested by Wright [9], who also studied shift-reduce parsers. We provide an exact method for calculating the desired quantity, while Wright's calculation requires several approximations. Why do we care about this particular quantity? As a first rough answer, note that when this quantity is zero, then the hy- pothesis should be abandoned; there is no possibility that the parse tree can he completed. Furthermore, the bigger this quan- tity is, the larger the mass of the probability space that can be explored by pursuing that particular hypothesis. For a more detailed answer, consider a breadth first search of candidate hypotheses. For each one we would like to know which is the correct one, given the grammar and the text seg- ment we have observed: a,,...,at. We would like to calculate P(Hla,,... , a~). This quantity is equal to P(H&al ..... a~)/P(al,..., a~). The denominator in the above expression P(a,,..., at) is the grand probability of seeing the observations al,..., at given the grammar. This is some fixed quantity. We might not know what it is, but as long as we are only comparing hypotheses that all explain the same string ah.--, at, this quantity is a scaling factor …

Content truncated to 500 words