An Improved Redundancy Elimination Algorithm for Underspecified Representations

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 409–416, Sydney, July 2006. c⃝2006 Association for Computational Linguistics An Improved Redundancy Elimination Algorithm for Underspecified Representations Alexander Koller and Stefan Thater Dept. of Computational Linguistics Universität des Saarlandes, Saarbrücken, Germany {koller,stth}@coli.uni-sb.de Abstract We present an efficient algorithm for the redundancy elimination problem: Given an underspecified semantic representation (USR) of a scope ambiguity, compute an USR with fewer mutually equivalent read- ings. The algorithm operates on underspec- ified chart representations which are de- rived from dominance graphs; it can be ap- plied to the USRs computed by large-scale grammars. We evaluate the algorithm on a corpus, and show that it reduces the de- gree of ambiguity significantly while tak- ing negligible runtime. 1 Introduction Underspecification is nowadays the standard ap- proach to dealing with scope ambiguities in com- putational semantics (van Deemter and Peters, 1996; Copestake et al., 2004; Egg et al., 2001; Blackburn and Bos, 2005). The basic idea be- hind it is to not enumerate all possible semantic representations for each syntactic analysis, but to derive a single compact underspecified represen- tation (USR). This simplifies semantics construc- tion, and current algorithms support the efficient enumeration of the individual semantic representa- tions from an USR (Koller and Thater, 2005b). A major promise of underspecification is that it makes it possible, in principle, to rule out entire subsets of readings that we are not interested in wholesale, without even enumerating them. For in- stance, real-world sentences with scope ambigui- ties often have many readings that are semantically equivalent. Subsequent modules (e.g. for doing in- ference) will typically only be interested in one reading from each equivalence class, and all oth- ers could be deleted. This situation is illustrated by the following two (out of many) sentences from the Rondane treebank, which is distributed with the English Resource Grammar (ERG; Flickinger (2002)), a large-scale HPSG grammar of English. (1) For travellers going to Finnmark there is a bus service from Oslo to Alta through Swe- den. (Rondane 1262) (2) We quickly put up the tents in the lee of a small hillside and cook for the first time in the open. (Rondane 892) For the annotated syntactic analysis of (1), the ERG derives an USR with eight scope bearing op- erators, which results in a total of 3960 readings. These readings are all semantically equivalent to each other. On the other hand, the USR for (2) has 480 readings, which fall into two classes of mutu- ally equivalent readings, characterised by the rela- tive scope of “the lee of” and “a small hillside.” In this paper, we present an algorithm for the redundancy elimination problem: Given an USR, compute an USR which has fewer readings, but still describes at least one representative of each equivalence class – without enumerating any read- ings. This algorithm makes it possible to compute the one or two representatives of the semantic equivalence classes in the examples, so subsequent …

Content truncated to 500 words