Towards History-based Grammars: Using Richer Models for Probabilistic Parsing

Towards History-based Grammars: Using Richer Models for Probabilistic Parsing* Ezra Black Fred Jelinek John Lafferty David M. Magerman Robert Mercer Salim Roukos IBM T. J. Watson Research Center Abstract We describe a generative probabilistic model of natural language, which we call HBG, that takes advantage of detailed linguistic information to re- solve ambiguity. HBG incorporates lexical, syn- tactic, semantic, and structural information from the parse tree into the disambiguation process in a novel way. We use a corpus of bracketed sentences, called a Treebank, in combination with decision tree building to tease out the relevant aspects of a parse tree that will determine the correct parse of a sentence. This stands in contrast to the usual ap- proach of further grammar tailoring via the usual linguistic introspection in the hope of generating the correct parse. In head-to-head tests against one of the best existing robust probabilistic pars- ing models, which we call P-CFG, the HBG model significantly outperforms P-CFG, increasing the parsing accuracy rate from 60% to 75%, a 37% reduction in error. Introduction Almost any natural language sentence is ambigu- ous in structure, reference, or nuance of mean- ing. Humans overcome these apparent ambigu- ities by examining the contez~ of the sentence. But what exactly is context? Frequently, the cor- rect interpretation is apparent from the words or constituents immediately surrounding the phrase in question. This observation begs the following question: How much information about the con- text of a sentence or phrase is necessary and suffi- cient to determine its meaning? This question is at the crux of the debate among computational lin- guists about the application and implementation of statistical methods in natural language under- standing. Previous work on disambiguation and proba- bilistic parsing has offered partial answers to this question. Hidden Markov models of words and *Thanks to Philip Resnik and Stanley Chen for their valued input. their tags, introduced in (5) and (5) and pop- ularized in the natural language community by Church (5), demonstrate the power of short-term n-gram statistics to deal with lexical ambiguity. Hindle and Rooth (5) use a statistical measure of lexical associations to resolve structural am- biguities. Brent (5) acquires likely verb subcat- egorization patterns using the frequencies of verb- object-preposition triples. Magerman and Mar- cus (5) propose a model of context that combines the n-gram model with information from dominat- ing constituents. All of these aspects of context are necessary for disambiguation, yet none is suf- ficient. We propose a probabilistic model of context for disambiguation in parsing, HBG, which incor- porates the intuitions of these previous works into one unified framework. Let p(T, w~) be the joint probability of generating the word string w~ and the parse tree T. Given w~, our parser chooses as its parse tree that tree T* for which T" =arg maxp(T, w~) (1) T6~(~) where ~(w~) is the set of all parses produced by the grammar for the sentence w~. Many aspects of the input sentence that might be relevant to the decision-making …

Content truncated to 500 words