Without a ’doubt’? Unsupervised Discovery of Downward-Entailing Operators

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 137–145, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Without a ‘doubt’? Unsupervised discovery of downward-entailing operators Cristian Danescu-Niculescu-Mizil, Lillian Lee, and Richard Ducott Department of Computer Science Cornell University Ithaca, NY 14853-7501 cristian@cs.cornell.edu, llee@cs.cornell.edu, rad47@cornell.edu Abstract An important part of textual inference is mak- ing deductions involving monotonicity, that is, determining whether a given assertion en- tails restrictions or relaxations of that asser- tion. For instance, the statement ‘We know the epidemic spread quickly’ does not entail ‘We know the epidemic spread quickly via fleas’, but ‘We doubt the epidemic spread quickly’ entails ‘We doubt the epidemic spread quickly via fleas’. Here, we present the first algorithm for the challenging lexical-semantics prob- lem of learning linguistic constructions that, like ‘doubt’, are downward entailing (DE). Our algorithm is unsupervised, resource-lean, and effective, accurately recovering many DE operators that are missing from the hand- constructed lists that textual-inference sys- tems currently use. 1 Introduction Making inferences based on natural-language state- ments is a crucial part of true natural-language un- derstanding, and thus has many important applica- tions. As the field of NLP has matured, there has been a resurgence of interest in creating systems ca- pable of making such inferences, as evidenced by the activity surrounding the ongoing sequence of “Recognizing Textual Entailment” (RTE) competi- tions (Dagan, Glickman, and Magnini, 2006; Bar- Haim, Dagan, Dolan, Ferro, Giampiccolo, Magnini, and Szpektor, 2006; Giampiccolo, Magnini, Dagan, and Dolan, 2007) and the AQUAINT knowledge- based evaluation project (Crouch, Saur´ı, and Fowler, 2005). The following two examples help illustrate the particular type of inference that is the focus of this paper. 1. ‘We know the epidemic spread quickly’ 2. ‘We doubt the epidemic spread quickly’ A relaxation of ‘spread quickly’ is ‘spread’; a re- striction of it is ‘spread quickly via fleas’. From statement 1, we can infer the relaxed version, ‘We know the epidemic spread’, whereas the restricted version, ‘We know the epidemic spread quickly via fleas’, does not follow. But the reverse holds for statement 2: it entails the restricted version ‘We doubt the epidemic spread quickly via fleas’, but not the relaxed version. The reason is that ‘doubt’ is a downward-entailing operator;1 in other words, it al- lows one to, in a sense, “reason from sets to subsets” (van der Wouden, 1997, pg. 90). Downward-entailing operators are not restricted to assertions about belief or to verbs. For example, the preposition ‘without’ is also downward entail- ing: from ‘The applicants came without payment or waivers’ we can infer that all the applicants came without payment. (Contrast this with ‘with’, which, like ‘know’, is upward entailing.) In fact, there are many downward-entailing operators, encompassing many syntactic types; these include explicit nega- tions like ‘no’ and ‘never’, but also many other terms, such as ‘refuse (to)’, ‘preventing’, ‘nothing’, ‘rarely’, and ‘too [adjective] to’. 1Synonyms for “downward entailing” include downward- monotonic and monotone decreasing. Related concepts include anti-additivity, veridicality, …

Content truncated to 500 words