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 lan- guage, which we call HBG, that takes advantage of detailed linguistic information to resolve ambiguity. HBG incorpo- rates lexical, syntactic, 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 Tree- bank, 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 approach 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 probabflistic parsing 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. 1. Introduction Almost any natural language sentence is ambiguous in structure, reference, or nuance of meaning. Humans overcome these apparent ambiguities by examining the con~ezt of the sentence. But what exactly is context? Frequently, the correct 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 context of a sentence or phrase is necessary and sufficient to de- termine its meaning? This question is at the crux of the debate among computational linguists about the ap- plication and implementation of statistical methods in natural language understanding. Previous work on disambiguation and probabilistic pars- ing has offered partial answers to this question. Hidden Markov models of words and their tags, introduced in [1] and [11] and popularized in the natural language commu- nity by Church [5], demonstrate the power of short-term n-gram statistics to deal with lexical ambiguity. Hindle and Rooth [8] use a statistical measure of lexical asso- ciations to resolve structural ambiguities. Brent [2] ac- quires likely verb subcategorization patterns using the *Thanks to Philip Resnik and Stanley Chen for their valued input. frequencies of verb-object-preposition triples. Mager- man and Marcus [10] propose a model of context that combines the n-gram model with information from dom- inating constituents. All of these aspects of context are necessary for disambiguation, yet none is sufficient. We propose a probabilistic model of context for disam- biguation in parsing, HBG, which incorporates the intu- itions 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* = argmaxp(T, w~) (1) TeP(wN where "P(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 process participate in the probabilistic model, provid- …

Content truncated to 500 words