Computing Weakest Readings

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 30–39, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Computing weakest readings Alexander Koller Cluster of Excellence Saarland University koller@mmci.uni-saarland.de Stefan Thater Dept. of Computational Linguistics Saarland University stth@coli.uni-saarland.de Abstract We present an efficient algorithm for com- puting the weakest readings of semantically ambiguous sentences. A corpus-based eval- uation with a large-scale grammar shows that our algorithm reduces over 80% of sen- tences to one or two readings, in negligible runtime, and thus makes it possible to work with semantic representations derived by deep large-scale grammars. 1 Introduction Over the past few years, there has been consid- erable progress in the ability of manually created large-scale grammars, such as the English Resource Grammar (ERG, Copestake and Flickinger (2000)) or the ParGram grammars (Butt et al., 2002), to parse wide-coverage text and assign it deep seman- tic representations. While applications should ben- efit from these very precise semantic representa- tions, their usefulness is limited by the presence of semantic ambiguity: On the Rondane Treebank (Oepen et al., 2002), the ERG computes an aver- age of several million semantic representations for each sentence, even when the syntactic analysis is fixed. The problem of appropriately selecting one of them to work with would ideally be solved by statistical methods (Higgins and Sadock, 2003) or knowledge-based inferences. However, no such approach has been worked out in sufficient detail to support the disambiguation of treebank sentences. As an alternative, Bos (2008) proposes to com- pute the weakest reading of each sentence and then use it instead of the “true” reading of the sentence. This is based on the observation that the readings of a semantically ambiguous sentence are partially ordered with respect to logical entailment, and the weakest readings – the minimal (least informative) readings with respect to this order – only express “safe” information that is common to all other read- ings as well. However, when a sentence has mil- lions of readings, finding the weakest reading is a hard problem. It is of course completely infeasible to compute all readings and compare all pairs for entailment; but even the best known algorithm in the literature (Gabsdil and Striegnitz, 1999) is only an optimization of this basic strategy, and would take months to compute the weakest readings for the sentences in the Rondane Treebank. In this paper, we propose a new, efficient ap- proach to the problem of computing weakest read- ings. We follow an underspecification approach to managing ambiguity: Rather than deriving all semantic representations from the syntactic analy- sis, we work with a single, compact underspecified semantic representation, from which the semantic representations can then be extracted by need. We then approximate entailment with a rewrite sys- tem that rewrites readings into logically weaker readings; the weakest readings are exactly those readings that cannot be rewritten into some other reading any more (the relative normal forms). We present an algorithm that computes the relative nor- mal forms, …

Content truncated to 500 words