NLog-like Inference and Commonsense Reasoning Len Schubert University

NLog-like Inference and Commonsense Reasoning Len Schubert University of Rochester Student participants: Ben Van Durme, Ting Qian, Jonathan Gordon, Karl Stratos, Adina Rubinoff Support: NSF (Grants IIS-1016735 and IIS0916599), ONR STTR N00014-10-M-0297

EL & EPILOG: Representation & inference for NLU, common sense (L. Schubert, C-H Hwang, S. Schaeffer, F. Morbini, et al., 1990 – present) “A car crashed into a tree. ” (some e: [e before Now34] (some x: [x car] (some y: [y tree] [[x crash-into y] ** e]))) colormetanumber episode string set hier2 Specialist Interface LOGICAL INPUT EPILOG core time other type equalityparts LOGICAL OUTPUT “The driver of x may be hurt or killed” Episodic Logic (EL): A Montague-inspired, event-oriented extension Of FOL, with NL-like expressive devices. 2

THE EPISODIC LOGIC/EPILOG PERSPECTIVE, Reasons for hypothesizing a language-like internal representation: Anthropology, cognitive science: concurrent appearance of thinking, language Simplicity of assuming NL “Mentalese” All our symbolic representations, from logic to programming languages to semantic nets, etc., are derivative from language Can one seriously believe that its just a coincidence that entailment can be understood in terms semantic entities corresponding 1-1 with syntactic phrases (Montague, categorial grammar)? Guided the developmen t of EPISODIC LOGIC Recent progress in applying “natural logic” to inferring entailment relations. 3

Universal semantic resources of natural languages Ways of naming things And/or/not/if-then/ Every/some/no/ Ways of ascribing properties and relations to entities So, at least FOL! BUT THAT’S NOT ALL! Generalized quantifiers (Most women who smoke) Intensionality (is planning a heist; resembles a Wookiee) Event reference (Everyone asked questions; THAT prolonged the meeting) Modification of predicates and sentences (barely alive, dances gracefully, Perhaps it will rain) Reification of predicates and sentences (Xeroxing money is illegal; That there is water on the Moon is surprising) Uncertainty (It will probably rain tomorrow; The more you smoke, the greater your risk of developing lung cancer) Quotation and meta-knowledge (Say “cheese”; How much do you know about description logics?) directly enabled in EL 4

Episodic Logic (EL) examples Restricted quantifiers “Most laptops are PCs or MACs” Note: Predicate (Most x: [x laptop] [[x PC] or [x MAC]]) s are infixed Event relations “If a car hits a tree, the driver is often hurt or killed” (Many-cases e: (some x: [x car] (some y: [y tree] [[x hits y] ** e])) [[[(driver-of x) (pasv hurt)] or [driver-of x) (pasv kill)]] @ e ]) Modification and reification “He firmly maintains that aardvarks are nearly extinct” (Some e: [e at-about Now17] [[He (firmly (maintain (that [(K (plur aardvark)) (nearly extinct)])))] ** e]) 5

Representing Meta/Self-Knowledge in EL: Schemas (substitutional quantification) quasiquotes “I know the names of all CSC faculty members” ( x: [x member-of CSC-faculty] ( subst y: [‘y name-of x] [ME know (that [‘y name-of x])])) A A There is no CSC faculty member whose name I know to be ‘Alan Turing’. Therefore there is no faculty member whose name is ‘Alan Turing’. 6

Ideas behind Natural Logic (Nlog) (van Benthem, van Eijck, Sanchez Valencia, Nairn, Condoravdi, Can replace phrases by more & general [more Karttunen, MacCartney Manning, etc.) specific] ones in positive- [negative-] polarity environments; e.g., Several trucks are on their way Several vehicles are on their way; If a vehicle is on its way, turn it back If a truck is on its way, turn it back Exploiting implicatives/factives, e.g., X manages to do Y X do Y; X doesn't manage to do Y X doesn't do Y; X knows that Y Y; X doesn’t know that Y Y; Full disambiguation not required; e.g., “several”, “on their way” can remain vague and ambiguous without disabling the above inferences

NLog-like inference in EPILOG 2 EPILOG inference is in essence polarity-based: replacing subformulas by consequences/anti-consequences in ve/ve environments (plus natural deduction rules, specialists) The equivalent of Nlog inference are readily encoded as axioms and rules in EPILOG 2. E.g., we have duplicated MacCartney & Manning’s illustrative example, Jimmy Dean refused to move without his jeans James Dean didn’t dance without pants, but also examples requiring background knowledge (beyond natural logic). Details & examples to follow.

Examples of implicative axioms (all pred p (all x ((x dare (ka p)) (x p))))), (all pred p (all x ((not (x dare (ka p))) (not (x p)))))) Similarly for other implicatives; also attitudes (stylized rules): X decline to P X not P X not decline to P (probably) X P X agrees to P X P X does not agree to P (probably) not X P X doubts that W X believes probably not W. Example of inference rules for a factive verb: (all wff w (all x ((x know (that w)) --- w)))), (all wff w (all x ((not (x know (that w))) --- w))))

Headline Vatican refused to engage child sex abuse inquiry examples (bywith Karl Stratos) (The Guardian: Dec 11, 2010). A homeless Irish man was forced to eat part of his ear (The Huffington Post: Feb 18, 2011). Oprah is shocked that President Obama gets no respect (Fox News: Feb 15, 2011). Meza Lopez confessed to dissolving 300 bodies in acid (Examiner: Feb 22, 2011) In EPILOG (neglecting tense): (s '(Vatican refuse (ka (engage-with Child-sex-abuseinquiry)))) (s '(some x (x (attr homeless (attr Irish man))) (x (pasv force) (ka (l y (some r (r ear-of y) (some s (s part-of r) (y eat s)))))))) (s '(Oprah (pasv shock) (that (not (Obama get (k respect)))))) (s '(Meza-Lopez confess (ka (l x (some y (y ((num 300) (plur body))) (x dissolve y))))). Inferred in fractions of a second (& returned in English): The Vatican did not engage with child sex abuse inquiry. An Irish man did eat part of his ear, President Obama gets no respect, and Meza Lopez dissolved 300 bodies in acid.

Larger-scale factive/implicative/attitudinal inferences in EPILOG 2 Karl Stratos has used his axiomatic factivity/ implicativity lexicon on100 EPILOG-encoded Brown corpus examples; e.g., e.g., I know that you wrote this in hurry. You wrote this in hurry. e.g., They say that our steeple is 162f high Probably they believe that our steeple is 162f high Evaluation: 108 sentences from Brown corpus, 141 inferences 92% were rated as good (75%) or fairly good (17%) (5 judges)

Pushing the limits of NLog -E.g., entailments of asking someone to do something Lexical axiom: (all pred p (all x (all y (all e1 ((x ask-of.v y (Ka p)) ** e1) ((x convey-info-to.v y (that ((x want-tbt.v (that (some e2 (e2 right-after.p e1) ((y p) ** e2)))) @ e1))) * e1))))) Given: John asked Mary to sing ((John.name ask-of.v Mary.name (Ka sing.v)) ** E1) Question: Did John convey to Mary that he wanted her to sing? ((John.name convey-info-to.v Mary.name (that ((John.name want-tbt.v (that (some e2 (e2 right-after.p E1) ((Mary.name sing.v) ** e2)))) @ E1))) * E1) Answered with YES in .001 sec

Simple inference beyond the scope of NLog (Allen's Monroe domain): Every available crane can be used to hoist rubble onto a truck. The small crane, which is on Clinton Ave, is not in use. Therefore, the small crane can be used to hoist rubble from the collapsed building on Penfield Rd onto a truck. Every available crane can be used to hoist rubble onto a truck (s '(all x (x ((attr available) crane)) (all r (r rubble) ((that (some y (y person) (some z (z truck) (y (adv-a (for-purpose (Ka (adv-a (onto z) (hoist r)))) (use x)))))) possible)))) The small crane, on Clinton Ave., is not in use. (s '(the x (x ((attr small) crane)) ((x on Clinton-Ave) and (not (x in-use))))) Every crane is a device (s '(all x (x crane) (x device))) Every device that is not in use is available (s ‘(all x ((x device) and (not (x in-use))) (x available))) Can the small crane be used to hoist rubble from the collapsed building on Penfield Rd onto a truck? (Answered affirmatively by EPILOG in .127 sec) (q (p ‘(the x (x ((attr small) crane)) (some r ((r rubble) and (the s ((s (attr collapsed building)) and (s on Penfield-Rd)) (r from s))) ((that (some y (y person) (some z (z truck) (y (adv-a (for-purpose (Ka (adv-a (onto z) (hoist r)))) (use x)))))) possible)))))

An example requiring still more world knowledge Most of the heavy resources are in Monroe-east. Therefore: - Few of the heavy resources are in Monroe-west; - Not all of the resources are in Monroe-west Some general knowledge: If most P are not Q then few P are Q: (s '(all pred P (all pred Q ((most x (x P) (not (x Q))) - (few x (x P) (x Q)))))) “Heavy” in premodifying position is subsective (s '(all pred P (all x (x ((attr heavy) P)) (x P)))) “If most P are Q, then some P are Q (existential import of “most”) (s '(all pred P (all pred Q ((most x (x P) (x Q)) - (some x (x P) (x Q)))))) All Monroe resources are in Monroe. A thing is in Monroe iff it is in Monroe-east or Monroe-west; and iff it is in Monroe-north or Monroe-south; nothing is in both Monroe-east and Monroe-west; or in both Monroe-north and Monroe-south: (s '(all x (x Monroe-resources) (x loc-in Monroe))) (s '(all x ((x loc-in Monroe) iff ((x loc-in Monroe-east) or (x loc-in Monroe-west))))) (s '(all x ((x loc-in Monroe) iff ((x loc-in Monroe-north) or (x loc-in Monroe-south))))) (s '(all x ((not (x loc-in Monroe-east)) or (not (x loc-in Monroe-west))))) (s '(all x ((not (x loc-in Monroe-north)) or (not (x loc-in Monroe-south)))))

(Example requiring still more world knowledge, cont’d) There are some heavy Monroe resources. Most of the heavy Monroe resources are located in Monroe-east (s '(some x (x ((attr heavy) Monroe-resources)))) (s '(most x (x ((attr heavy) Monroe-resources)) (x loc-in Monroe-east))) Questions: Are few heavy resources in Monroe-west? (q (p '(few x (x ((attr heavy) Monroe-resources)) (x loc-in Monroe-west)))) Answer is “yes”. Are all Monroe resources in Monroe-west? (q (p '(all x (x Monroe-resources) (x loc-in Monroe-west)))) Answer is “no”, because: Most heavy resources, hence some heavy resources, hence some resources, are in Monroe-east; but whatever is in Monroe-east is not in Monroe-west, hence not all resources are in Monroe-west.

Trying to Scale up Knowledge, Lexical (for into Nlog-like andknowledge mapping NL EL & other inference) Semantic patterns (as initial, underspecified world knowledge and for parsing/interpretation) World knowledge (for more general reasoning) Mapping Treebank parses into EL (for NLbased inference)

Entailment, synonymy, and exclusion relations among lexical Lexical Knowledge Acquisition items, by starting with distributional similarity clusters, and training a classifier to select the correct relation; initial results 80% accurate Knowledge engineering of a large collection of factive, antifactive, and implicative verbal predicates for use in EPILOG, gleaned from various sources and expanded via VerbNet, etc. (undergrad Karl Stratos has been the mainstay of this effort); 250 lexical items with their semantic “signatures” preliminary set of detailed, event-oriented lexical axioms, leveraging Palmer's VerbNet (VN); (Adina Rubinoff); three stages: - axiomatized 100 semantic “primitives” (MOVE, SEE, LEARN, MAKE, ) - creating an axiom schema for each VN class, in terms of “primitives” and “(predicate) parameters” - providing parameters for the verbs in each class (e.g., the

A starting point for world knowledge acquisition: The KNEXT project: General KNowledge EXTraction from text (L. Schubert, M. Tong, J. Sinapov, B. Van Durme, T. Qian, J. Gordon, ) General “factoids”, or semantic patterns KNEXT: Knowledge Extraction From Text A PERSON MAY BUY FOOD; A HOUSE MAY HAVE WINDOWS; A COMEDY MAY BE DELIGHTFUL; A BEHAVIOR CAN BE STRANGE; LEISURE MAY BE DEVOTED TO PLAY; 18

The KNEXT system: Functional architecture sentence & phrase [ [ I] [ had [ a terrible flu] [ last year]]] S NP VP NP NP structure identify temporal phrases, etc. 80 regular phrase patterns, paired with semantic rules proper name gazetteer; “of”knowledge, etc. adjust phrase Structure for Interpretation adjusted input [S [NP I] [VP had [NP a terrible flu] [NPtime last year]]] compute LFs sets of LFs [mePron haveV fluN], a{n} x[x (attr terribleA fluN)] extract & abstract propositions propositional LFs verbalize and filter propositions [ a{n} personN haveV fluN], [ a{n} fluN terribleA] [ a{n} personN haveV fluN], [ a{n} fluN terribleA] abstract LFs and English output A PERSON MAY HAVE A FLU A FLU CAN BE TERRIBLE “shallow” knowledge

Text corpora used, & example output Brown Corpus: 1 million words, with phrase structure ---- 117,000 factoids British National Corpus: 100 million words, analyzed with Collins parser ---- several million factoids Weblogs, Wikipedia (Jonathan Gordon): billions of words ---- 200 million factoids Selected Brown examples: A PERSON MAY BELIEVE A PROPOSITION BILLS MAY BE APPROVED BY COMMITTEES A US STATE MAY HAVE HIGH SCHOOLS CHILDREN MAY LIVE WITH RELATIVES A COMEDY MAY BE DELIGHTFUL A BOOK MAY BE WRITE-ED (i.e., written) BY AN AGENT A FEMALE-INDIVIDUAL MAY HAVE A SPOUSE AN ARTERY CAN BE THICKENED A HOUSE MAY HAVE WINDOWS PROTESTS CAN BE ADAMANT A MALE-INDIVIDUAL MAY LEAD A FIGHT A TEAM CAN BE WINLESS LEGS MAY TWITCH INDIVIDUALS MAY SHARE A BED REVELATIONS MAY EMBARRASS TOWN OFFICIALS A BRICK FAÇADE MAY BE SHEARED OFF BY A SHOCK OF A QUAKE A TV-NETWORK MAY HAVE A SPOKESMAN A BARREL MAY CONTAIN HEATING OIL A LANGUAGE MAY BE MELLIFLUOUS 20

Abstracting from, and disambiguating, factoids (Van Durme, Michalak & Schubert EACL’09) ENTITY WordNet ontology PHYSICAL ENTITY ABSTRACT ENTITY COMMUNICATIO N WRITTEN COMMUNICATION PIECE OF WRITING PHYSICAL OBJECT EXPRESSIVE STYLE TEXT PROSE REPRESENTATION DOCUMEN T LETTER1 (missive) ARTIFACT LITERAR YGEN RE WRITTEN MATTER WHOL E CREATION (phys) NONFICTION COMPOSITION PROSE (phys) ARTICLE1 (literary) LETTER2 (alphabet) LETTER3 LETTER4 (landlord) (of the law)LETTER5 (varsity) ARTICLE2 (e.g., clothing) ARTICL E ARTICLE4 (legal) (grammar ) “A CHILD MAY WRITE A LETTER” “A JOURNALIST MAY WRITE AN ARTICLE” GENERALLY, IF X WRITES Y, Y IS A 21

Obtaining inference-capable knowledge by “sharpening” factoids (J. Gordon & L. Schubert KCS’10) Engineered rules have transformed tens of thousands of textderived "possibilistic" factoids (such as that A TREE MAY HAVE A BRANCH, or A PERSON MAY EAT A SANDWICH) into "sharper" quantified formulas such as (most-or-all x: [x tree] (some y: [y branch] [x has-as-part y])) (many x: [x person] (at-least-occasional e (some y: [y sandwich] [[x eat y] ** e]))), i.e., most or all trees have at least one branch, and many people eat a sandwich at least occasionally. 1.5 million sharpened factoids have been obtained (accessible at http://www.cs.rochester.edu/research/knext/browse/); for 435 sampled sharpened factoids, about 60% were judged reasonable if based on reasonable unsharpened factoids (o/w about 40%).

Discovering commonsense entailment rules on discourse cues Use Tgrep on based parsed sentences to find patterns such as (J. Gordon & L. Schubert, TextInfer ‘11) NP VP but didn’t VP , NP VP, expecting to VP NP BE ADJP {but yet} ADJP, i.e., where an expectation is implied (and perhaps denied). Apply rules to them that create slightly simplified / abstracted conditional statements, expressed as parse trees (not yet LFs) E.g., He stood before her in the doorway, evidently expecting to be invited in If a male stands before a female in the doorway, then he may expect to be invited in. Other sample rules: If a person texts a male, then he-or-she may get a reply; If a pain is great, then it may not be manageable; If a person doesn’t like some particular store, then he-or-she may not keep going to it. About 1 out of 200 sentences yields a rule (that survives filtering); e.g., 29,000 rules from a 5.5 million sentence story corpus; of these more than 2/3 are judged

What about direct interpretation of general statements (lexicon glosses, Open Mind, Wikipedia, )? Even lexical glosses are hard to interpret; e.g., (WordNet) dance (V): move in a pattern, usually to musical accompaniment What does “in a pattern” mean? (Cf. “move into / inside a pattern”) What does “to musical accompaniment” mean? (towards?) Open Mind factoids leave much unsaid; e.g., Something you might do while driving a car is crash Who / what is crashing (into what)? Some (simple English) Wikipedia items are simple, clear, and complete; others, not so much A car (also called an automobile) is a vehicle used to transport passengers. Cars usually have four wheels and an internal combustion engine. Dance is when people move to a musical rhythm . What does “is when” mean? (Cf. “Monday is when I go home”) What does “to a musical rhythm” mean? (Towards it? And does a marching band dance?)

Computing initial logical forms in EL Some time-worn examples: “Time flies like an arrow” [(K timeN) (adv-m (likeP a{n} arrowN ) pres flyV )], [(K (plur (nn timeN flyN))) pres likeV a{n} arrowN ], readings with timeV “I saw the man with binoculars” [IPron (adv-m (withP binocularsN) ( past seeV the manN ))], [IPron past seeV the ( x [[x manN] & [x withP binocularsN ]]) ))], readings with pres sawV “Shallow knowledge” (semantic patterns) Time may fly; an arrow may fly; Seeing may be done with a viewing instrument should help with “gross ambiguities”! 25

Further disambiguating and elaborating the initial LF . Finding referents of pronouns and other terms “He tried to steal Donald Trump’s identity but couldn’t pull it off” . Scoping quantifiers “Every man admires a certain woman” (his mother? Rosa Parks?) . Recovering “missing arguments” & comparison classes “Some carbon monoxide leaked into the car, but its concentration was too low to pose a serious hazard . Expanding metonymy “THIS LANE MUST EXIT” (vehicles travelling in this lane ) . Inferring temporal, causal, & other coherence relations “I told Rocky he was a wimp. When I regained consciousness, ” . Determining what is presupposed, and what is new “Cro-Magnons usually roasted meat on a spit over a fire” (i.e., usually when preparing to eat meat!) . Inferring speaker/author intent “Sir, you’re sitting in my seat” all depend profoundly on lexical & world knowledge, and context 26

Discussion The most important remaining problems are KB build-up reliable mapping from English to a structurally unambiguous, deindexed, reference-resolved EL form. Does Nlog escape these problems? Not really: A large KB is essential in either case We need to generate inferences, not just verify them. This cannot be done by alignment word-level editing We need deindexed representations for general inference. If “I will soon stop talking”, were true in perpetuity, I would never stop – nor would anyone else using the pronoun “I”! Ambiguity/vagueness can be tolerated only to a limited extent, even in Nlog; “John had gerbils as a child” should not be regarded as entailing that John consumed, or gave birth to, small rodents as a child. If we actually want to understand language, we need to let world knowledge, not only lexical knowledge,

Conclusions . The representational and inferential style of EL / EPILOG is close to that of Nlog; . EL / EPILOG also allow for more complex inferences from lexical and world knowledge; . Ambiguity resolution and knowledge accumulation remain issues for both EL / EPILOG and Nlog. 28

Reference s Schubert, Van Durme, & Bazrafshan, “Entailment inference in a naturallogic-like general reasoner”, AAAI Fall Symp. On Commonsense Knowledge (CSK’10), November 2010; Stratos, Schubert, and Gordon, “Episodic Logic: Natural Logic Reasoning”, to appear. Gordon and Schubert, “Quantificational Sharpening of commonsense knowledge”, AAAI Fall Symp. On Commonsense Knowledge CSK’10), November 2010; Gordon and Schubert, “Discovering commonsense entailment rules implicit in sentences”, TextInfer 2011.