A Notion of Semantic Coherence for Underspecified Semantic Representation

A Notion of Semantic Coherence for Underspecified Semantic Representation Mehdi Manshadi∗ University of Rochester Daniel Gildea∗∗ University of Rochester James F. Allen† University of Rochester The general problem of finding satisfying solutions to constraint-based underspecified represen- tations of quantifier scope is NP-complete. Existing frameworks, including Dominance Graphs, Minimal Recursion Semantics, and Hole Semantics, have struggled to balance expressivity and tractability in order to cover real natural language sentences with efficient algorithms. We address this trade-off with a general principle of coherence, which requires that every variable introduced in the domain of discourse must contribute to the overall semantics of the sentence. We show that every underspecified representation meeting this criterion can be efficiently pro- cessed, and that our set of representations subsumes all previously identified tractable sets. 1. Introduction Quantifier scope ambiguity is a big challenge in deep language understanding systems. Consider the following conversation: Woman: I believe there is one true soulmate for every person. Man: He must be very busy.1 Most people find the man’s answer unusual (humorous, sarcastic, etc.). This is because one of the two scopings of the woman’s sentence feels so obvious that the less likely ∗ Department of Computer Science, University of Rochester, Rochester, NY 14627. E-mail: mehdih@cs.rochester.edu. ∗∗ Department of Computer Science, University of Rochester, Rochester, NY 14627. E-mail: gildea@cs.rochester.edu. † Department of Computer Science, University of Rochester, Rochester, NY 14627. E-mail: james@cs.rochester.edu. 1 dilbert.com/strip/2001-04-19. Submission received: 2 June 2016; revised version received: 13 March 2017; accepted for publication: 1 August 2017. doi:10.1162/COLI a 00307 © 2017 Association for Computational Linguistics Published under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) license Computational Linguistics Volume 44, Number 1 scoping is often missed at first glance. In the most likely interpretation, where there are many soulmates, the quantifier every has wide scope, and, in the second interpretation, where there is a unique soulmate, every has narrow scope. The following conversation is of a similar nature: Bob: How long have you and Opal been married now Earl? Earl: I’ve lost track. But I can tell you this ... I don’t regret one day of it. Bob: Which day don’t you regret?2 The difference, however, is that, in this example, the scope ambiguity is not be- tween two quantifiers, but between a quantifier (one) and a scopal operator (negation). Underspecification, that is, generating an unscoped semantic representation, has been the most common way of dealing with quantifier scope ambiguity since the early days of natural language processing. Underspecification is not adopted only because quan- tifier scope disambiguation is difficult, but also because, for most practical purposes, an underspecified representation (UR)3 will do the job. Equations (1) and (2) show an unscoped logical form (LF) for the sentences There is one soulmate for every person and I do not regret one day, respectively. ⟨One x Soulmate⟩ ⟨Every y Person⟩ Of(x, y) (1) ⟨One x Day⟩ Not(Regret(I, x)) (2) Equation (3) shows the two scopings of the unscoped LF in Equation (2): One(x, Day(x), Not(Regret(I, x))) Not(One(x, …

Content truncated to 500 words