A Novel Disambiguation Method for Unification-Based Grammars Using Probabilistic Context-Free Approximations

A Novel Disambiguation Method For Unification-Based Grammars Using Probabilistic Context-Free Approximations Bernd Kiefer, Hans-Ulrich Krieger, Detlef Prescher � kiefer|krieger|prescher � @dfki.de Language Technology Lab, DFKI GmbH Stuhlsatzenhausweg 3 66123 Saarbr¨ucken, Germany Abstract We present a novel disambiguation method for unification-based grammars (UBGs). In contrast to other methods, our approach obviates the need for probability models on the UBG side in that it shifts the responsibil- ity to simpler context-free models, indirectly obtained from the UBG. Our approach has three advantages: (i) training can be effectively done in practice, (ii) parsing and disambiguation of context-free readings requires only cubic time, and (iii) involved probability distributions are mathematically clean. In an experiment for a mid-size UBG, we show that our novel approach is feasible. Using unsupervised training, we achieve 88% accuracy on an exact-match task. 1 Introduction This paper deals with the problem of how to dis- ambiguate the readings of sentences, analyzed by a given unification-based grammar (UBG). Apparently, there are many different approaches for almost as many different unification-based grammar formalisms on the market that tackle this difficult problem. All approaches have in common that they try to model a probability distribution over the readings of the UBG, which can be used to rank the competing analyses of a given sentence; see, e.g., Briscoe and Carroll (1993), Eisele (1994), Brew (1995), Abney (1997), Goodman (1997), Bod and Kaplan (1998), Johnson et al. (1999), Riezler et al. (2000), Osborne (2000), Bouma et al. (2001), or Schmid (2002). Unfortunately, most of the proposed probability models are not mathematically clean in that the probabilities of all possible UBG readings do not sum to the value 1, a problem which is discussed intensively by Eisele (1994), Abney (1997), and Schmid (2002). In addition, many of the newer approaches use log-linear (or exponential) models. Schmid (2002) outlines a serious problem for these models: log- linear models prevent the application of dynamic programming methods for the computation of the most probable parse, if complex features are incor- porated. Therefore the run-time complexity of the disambiguation algorithm is linear in the number of parses of a sentence. If the number of parses grows exponentially with the length of the sentence, these approaches are simply impractical. Our approach obviates the need for such models on the UBG side in that it shifts the responsibility to simpler CF models, indirectly obtained from the UBG. In more detail, the kernel of our novel disam- biguation method for UBGs consists of the appli- cation of a context-free approximation for a given UBG (Kiefer and Krieger, 2000) and the exploita- tion of the standard probability model for CFGs. In contrast to earlier approaches to disambigua- tion for UBGs, our approach has several advantages. Firstly, probabilistic modeling/training of context- free grammars is theoretically well-understood and can be effectively done in practice, using the inside- outside algorithm (Lari and Young, 1990). Sec- ondly, the Viterbi algorithm enables CFG pars- ing and disambiguation in cubic time, exploiting dynamic programming techniques to specify the maximum-probability parse …

Content truncated to 500 words