A Basic Logic for Textual Inference

of 5
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Biography

Published:

Views: 15 | Pages: 5

Extension: PDF | Download: 0

Share
Description
A Basic Logic for Textual Inference
Tags
Transcript
  A Basic Logic for Textual Inference  ∗ D. Bobrow, C. Condoravdi, R. Crouch, R. Kaplan, L. Karttunen, T. King, V. de Paiva, A. Zaenen Palo Alto Research Center3333 Coyote Hill RoadPalo Alto 94304 Abstract This note describes a logical system based on concepts andcontexts, the system  TIL  for textual inference logic. Thesystem  TIL  is the beginnings of a logic that is a kind of “con-texted”descriptionlogic, designedtosupportlocallinguisticinferences. This logic pays attention to the intensionality of linguistic constructs and to the need for tractability of infer-ence in knowledge representation formalisms. Introduction This note describes the basics of a logical system based onconcepts and contexts. The aim of this system is to serveas a representation language for meanings of natural lan-guage sentences in the implemented system that we are de-veloping as part of the Aquaint framework. Some higherlevel discussion of our system and the rationale behind itcan be found in (Crouch 2005; Condoravdi  et al.  2003;Crouch  et al.  2002). As explained in (Crouch 2005), oursystem maps English sentences to the  f  -structures of Lexi-calFunctionalGrammar(Kaplan&Bresnan1982)andtheseto logical formulae, using the “Glue language” approach forthe construction of the meanings of the sentences (Dalrym-ple 2003). The output of glue semantics is then flattened toproduce sets of clauses of the logic we discuss in this paper.In this note we simply describe the logical system asit can be distilled from the implemented system’s output.This logic is based on the idea of using events in a neo-Davidsonian style. We will not discuss how pre-theoreticalnotions of event (especially in natural language semantics)relate to the events here, which are just formal strings of symbols describing predications.We start by describing the language of the proposed logic,called  TIL  for textual inference logic. The system  TIL  is asimplified logic of concepts and contexts, that is, a kind of “contexted” description logic (Baader  et al.  2003), one thatdoes not make use of instances or individuals. Our contextsare similar to McCarthy’s contexts (McCarthy 1993) in thatour contexts are intended to be representations of first-order ∗ This work was partially supported by the Advanced Researchand Development Activity (ARDA)’s Advanced Question Answer-ing for Intelligence (AQUAINT) Program.Copyright c   2005, American Association for Artificial Intelli-gence (www.aaai.org). All rights reserved. propositional entities that can also be given as argumentsto predicates. We give ourselves a collection of contexts,which we write as  top,c 1 ,c 2 ,... , the whole collection iswritten as  Context . We also have a collection of   concepts ,for which, to avoid difficulties with names, we use variables t 1 ,t 2 ,... , thinking of types. The whole collection we writeas  Concept .Our concepts are of two different kinds: primitive andconstructed. Primitive concepts are given a priori, basedon the hierarchy underlying the  CYC  knowlege base (Lenat1995). These concepts we write using a typescript font, like MovementTranslationEvent  or  City . Constructed con-cepts are built from the primitive ones via a series of op-erations which we describe in the next section. They alsosit in the same hierarchy, whose most underspecified con-cept is called  Thing . These constructed concepts, whichwe write in italics, are dynamically created by the imple-mented system in the process of interpreting the input text.So they come with names with arbitrary numbers that cor-respond to skolem constants. For example, for a sentencelike  Ed arrived in the city , we will create an arrival eventconcept, written as  arriveEv 1 , a concept for the person Ed,written as  Ed 2 , and a concept for city,  city 3  related in thepredictable manner specified in the next section.Wehaveseveralrelationsbetweenconcepts, betweencon-texts, and between concepts and contexts. First, we discussrelations between concepts, then relations between conceptsand contexts, and finally relations between contexts. Thenwe discuss some of the inferences that our logic supports. Relations Between Concepts We start by describing the basic relations between conceptsin  Concept . We have two main kinds of relations, first the subconcept   relation between two concepts and second, thenotion of a  role  between two concepts. Subconcepts Our concepts are organized into a hierarchy and the sub-concept relation just expresses this given order. We writethis as  subconcept ( t 1 ,t 2 ) , instead of the traditional descrip-tion logics  t 1    t 2 . For example, if we consider a specificclass of arrival events which we write as  arriveEv 1 , thenwe place this in the hierarchy by declaring that  arriveEv 1  is a subconcept of   ArrivingAtAPlace , subconcept ( arriveEv 1 , ArrivingAtAPlace ) The notion of subconcept serves to locate the new con-ceptsofourlogicalsystemwithrespecttotheconceptsgivenby the  CYC  hierarchy, but the relation is general and con-structed concepts like  arriveEv 1  and  arriveEv 100  can berelated as well. We assume that concepts inherit from one ormore concepts and that there are no circularities or inconsis-tencies in the given hierarchy. Roles We also take as given a collection of relations between con-cepts that we think of as  roles , relating concepts. For exam-ple, if we consider the previous concept of an arrival event arriveEv 1  and the concept of a person called Ed, whichwe write as a concept  Ed 2 , then an example of a role re-lation between these two concepts is that the concept  Ed 2 might play the role of   objectMoving  for the arrival event arriveEv 1 . This we will write as objectMoving ( arriveEv 1 ,Ed 2) subconcept ( Ed 2 , Person ) subconcept ( arriveEv 1 , ArrivingAtAPlace ) Note that the roles are always binary relations and arewritten in a prefix notation, i.e.  role ( t 1 ,t 2 )  and are gener-ally (but not always)  actor slots  in  CYC . In general we writethese relations between concepts as  role 1 ,role 2 ,...  and thewhole collection is written as  Role . Syntax so far The logical system we are describing looks like a descrip-tion logic. We have concepts  Concept  with their own partialorder  subconcept  and roles  Role , which are binary relationson  Concept . We write  clauses  that either relate concepts viasubconcept relations or relate roles to pairs of concepts, like objectMoving ( arriveEv 1 ,Ed 2) . Note that these rolesare obtained in the mapping from language to logical formsfrom the grammatical relations that relate verbs to their ar-guments.We operate on these collections of subconcept and roleclauses by adding some more of the same. Adding to theexample above, we could say that the same arrival event arriveEv 1  was connected via a  toLocation  role to theconcept of a city, say  city 3 , which we would write as objectMoving ( arriveEv 1 ,Ed 2) toLocation ( arriveEv 1 ,city 3) subconcept ( arriveEv 1 , ArrivingAtAPlace ) subconcept ( Ed 2 , Person ) subconcept ( city 3 , City ) This intuitively says that there was an arrival event, whoseobject moving is Ed and whose location of arrival is a par-ticular city. It is thus a logical representation of the sentence  Ed arrived in the city , disregarding tense, for example.More generally, given concepts  t 1 ,t 2 ,... , together withclauses such as  subconcept ( t 1 ,t 2 ) ,  subconcept ( t 3 ,t 4 )  and role 1 ( t 1 ,t 2 ) ,  role 2 ( t 1 ,t 3 ) , we can add new concepts t 7 ,t 8  ...  new roles  role 3 ,...  and new subconcept relations. Contexts and Concepts Our simple logic has contexts  Context , as well as con-cepts. Contexts in our logic support making statementsabout whether there are entities that satisfy the intensionaldescriptions specified by our concepts.There is a first initial context (written as  top ) that corre-sponds roughly to what we take the world to be like. Moreprecisely, in an interpretation of a sentence, the top contextcorresponds to what the author of the sentence is committedto, about the world she is describing. Since this circumlo-cution is awkward, we will usually talk about this top levelcontext as the “true” context.Apart from the true context, what other contexts are therein our logic? We first discuss the class of propositional atti-tude contexts. Propositional Attitudes In our approach  propositional attitudes  relate contexts andconcepts corresponding to the holder of the attitude and thetypeoftheattitude. Thusconceptslike‘knowing’or‘believ-ing’ or ‘saying’ introduce contexts that represent the propo-sition that is known, believed or said.For example, if we want to represent the sentence  Ed be-lieves that the diplomat arrived  , we will need concepts forthe arrival event, for the believing event, for the diplomatand for Ed. Assuming all of these to be subconcepts of rea-sonable concepts, we end up with roles that describe howthey relate. Thus there might be a role  believer  of the be-lieving event and this should relate the believing event to theconcept associated with Ed,  believer ( believeEv 1 ,Ed 2) .There is a role  whatsBelieved  which relates the concept believeEv1  to (the contents of) a context  c 1 , giving us whatsBelieved ( believeEv 1 ,c 1 ) . Also the content of whatis believed in the believing event is the proposition that  Thediplomat arrived  .We represent the concepts (intensional descriptions) usedin this sentence as: believer ( believeEv 1 ,Ed 2) whatsBelieved ( believeEv 1 ,c 1 ) subconcept ( Ed 2 , Person ) subconcept ( believeEv 1 , CognitionEvent ) objectMoving ( arriveEv 3 ,diplomat 4) subconcept ( diplomat 4 , Diplomat ) subconcept ( arriveEv 3 , ArrivingAtAPlace ) In this set of clauses, the first four lines represent the believ-ing event, and the last three ones represent the arrival event.One motivation for introducing contexts in our logic isto be able to localize reasoning. While the existence of thebelieving concept and of Ed are supposed to be true in thereal world, the existence of the arrival of the diplomat isonly supposed to be true in those worlds compatible withwhat Ed believes. Thus we introduce two new classes of clauses,  instantiable  and  contextRelation  clauses. Intu-itively the  instantiable  predicate takes a context and a con-cept and specifies that the concept is instantiable in that con-text. The  contextRelation  clauses indicate the relation-ship between two contexts induced by the meaning of thelexical item:  contextRelation ( believe,top,c 1 )  says that  there is a relation induced by the believing concept betweenthe contexts  top  and  c 1 , where  c 1  is the context of what isbelieved by Ed.The following clauses augment the representation aboveas follows: top  :  contextRelation ( believe,top,c 1 ) instantiable ( believeEv 1) instantiable ( Ed 2) c 1  :  instantiable ( diplomat 4) instantiable ( arriveEv 3) This representation is not faithful to our intuitions, as theexistence of the diplomat is not restricted to the context  c 1 .It is the arrival of the diplomat that needs to exist only in theworld of the things believed by Ed. Thus we push the clause instantiable ( diplomat 4)  to the  top  context, but we keepthe instantiability of the arrival event  arriveEv 3  restrictedto the context  c 1 . top  :  contextRelation ( believe,top,c 1 ) instantiable ( Ed 2) instantiable ( believeEv 1) instantiable ( diplomat 4) c 1  :  instantiable ( arriveEv 3) We present one further example of a propositional attitudecontext that is perhaps less familiar to logicians. Considerthe sentence  Ed said that the diplomat arrived  . This alsosets up a context containing the contents of the informationtransferred by Ed, hence we get the new concepts: senderOfInfo ( sayEv 1 ,Ed 2) informationTransferred ( sayEv 1 ,c 1 ) subconcept ( Ed 2 , Person ) subconcept ( sayEv 1 , InformCommunicationAct ) and the statements about instantiability top  :  contextRelation ( infTransfer  ,top,c 1 ) instantiable ( Ed 2) instantiable ( sayEv 1) instantiable ( diplomat 4) c 1  :  instantiable ( arriveEv 3) As before the claim about the existence of the diplomatis not restricted to the context  c 1 . The  top  context tells usthat Ed said that the diplomat arrived; things Ed says maywell be false, even if Ed is a very reliable source. So whileit is perfectly fine to say that the arrival of the diplomat isinstantiable in the context,  c 1  of the things said by Ed, wecertainly do not want to push the instantiability clause up tothe  top  context.The examples lead us to a new kind of relation betweencontexts. We say that the context  c 1  introduced by the be-lieving concept, like the one introduced by the saying event,is  averidical  with respect to the initial context  top . In thenext sections we consider also  veridicality  and  antiveridi-cality  between contexts. Negation Contexts Consider the sentence  The diplomat did not arrive . One wayof representing the information conveyed by this sentenceis to consider all the worlds where the particular diplomatwe talked aboutdid arrive (at the appropriate place) and then‘subtract’ 1 the collection of worlds where this event takesplace from the collection of all possible worlds. In this casewe have the same concepts of diplomat and of an arrivingevent that we had before, but we have two contexts, the top(or true) one where there was no arrival by the diplomat andthe negated context, where the arrival of the diplomat didhappen.For the sentence  The diplomat did not arrive , we knowthat the concept  arriveEv 1  is instantiable in the negatedcontext, but not in the top or true one. We end up with a rep-resentation like the one below, where we place the clausesdefiningconceptsandrolesbeforetheinstantiabilityclauses,which are context-sensitive. objectMoving ( arriveEv 1 ,diplomat 2) subconcept ( diplomat 2 , Diplomat ) subconcept ( arriveEv 1 , ArrivingAtAPlace ) top  :  contextRelation ( not,top,c 1 ) antiveridical ( c 1 ,top ) instantiable ( diplomat 2) c 1  :  instantiable ( arriveEv 1) As with the saying event, we expect that the concept diplomat 2  can be instantiable in the true context, but thearrival event should not. Moreover, in this case, since thenegated context is  antiveridical , instead of simply say-ingthatthe arriveEv 1 isinstantiableinthenegatedcontext,we want to say that it is  not   instantiable in the top context.Thus we simplify the instantiability clauses above to top  :  contextRelation ( not,top,c 1 ) antiveridical ( c 1 ,top ) instantiable ( diplomat 2) uninstantiable ( arriveEv 1) Having introduced relations between two contexts, wehave expanded the expressive power of our language of rep-resentations considerably. So far, we have a fairly general(nestable) mechanism that can represent some positive andsome negative information, mostly in a ‘conjunctive’ form.In the next section we discuss possible ways of representingdisjunctive and implicative information. Other Logical Relations Between Contexts To deal with disjunctive information like “Either the diplo-mat arrived or the car broke” we introduce a version of the contextRelation  predicate relating the srcinal context totwo sub-contexts that are the ‘arms’ of the disjunction – inthe example below,  orA  and  orB , are arms of the disjunc-tion introduced in the context  top . 1 This view of negation is constructively appealing, as it trans-forms negation into some sort of implication into  falsum  ( ⊥ ). Wethink of implication in possible worlds as assuming the antecedent,checking where the worlds that satisfy the antecedent can take usand verifying that the consequent is satisfied there.  objectMoving ( arriveEv 1 ,diplomat 4) objectActedOn ( breakEv 2 ,car 6) subconcept ( arriveEv 1 , ArrivingAtAPlace ) subconcept ( diplomat 4 , Diplomat ) subconcept ( breakEv 2 , BreakingEvent ) subconcept ( car 6 , Automobile ) top  :  contextRelation ( or,top, [ orA 3 ,orB 4]) instantiable ( diplomat 4) instantiable ( car 6) orA 3 :  instantiable ( arriveEv 1) orA 4 :  instantiable ( breakEv 2) Wecanhaveadisjunctionofeventssharingoneargument.For example, if we have  “The diplomat watched televisionor slept” , our representation will construct a new event,here  group-ev1 , of which the events of watching televi-sion and sleeping are sub-events. The representation will be: evmember ( ev 4 ,groupEv 1) evmember ( ev 7 ,groupEv 1) performedBy ( ev 4 ,diplomat 6) perceivedThings ( ev 4 ,television 5) bodilyDoer ( ev 7 ,diplomat 6) subconcept ( ev 4 , WatchingSomething ) subconcept ( diplomat 6 , Diplomat ) subconcept ( ev 7 , Sleeping ) top  :  contextRelation ( or,top, [ orA 2 ,orB 3]) instantiable ( diplomat 6) instantiable ( television 5) orA 2 :  instantiable ( ev 7) orB 3 :  instantiable ( ev 4) In this case the disjunctive event  groupEv1  has twosubevents  ev4  and  ev7 , respectively the watching andthe sleeping events, but these happen in  separate  contexts, orA2  and  orB3 , respectively.Similarly, conditionals, treated currently as logical impli-cations, introduce new contexts, one antecedent context andone consequent context, which have to be connected to therelevant whole context. In the example “If the reporter ar-rived the diplomat will leave” we have objectMoving ( arriveEv 2 ,reporter 5) objectMoving ( leaveEv 1 ,diplomat 6) subconcept ( arriveEv 2 , ArrivingAtAPlace ) subconcept ( leaveEv 1 , LeavingAPlace ) subconcept ( reporter 5 , Journalist ) subconcept ( diplomat 6 , Diplomat ) top  :  contextRelation ( if,top, [ ante 4 ,consq  3]) precondForEvents ( arriveEv 2 ,leaveEv 1) instantiable ( diplomat 6) instantiable ( reporter 5) ante 4 :  instantiable ( arriveEv 2) consq  3 :  instantiable ( leaveEv 1) Inferences Our aim in this section is to show the kinds of inferences thatthis simple logic of concepts and contexts already allows.The reason for introducing events (here treated as con-cepts) in Davidsonian semantics was the fact that it makesit very easy to make inferences that can be complicated inother semantic traditions. For example, it is easily seen that “Ed arrived in the city”  is entailed by  “Ed arrived in the cityby bus” . This is clearly so in our logic, where this inferencecorresponds simply to clause (conjunction) dropping.The sentence  “Ed arrived in the city by bus”  correspondsto the set of clauses top  :  objectMoving ( arriveEv 1 ,Ed 4) toLocation ( arriveEv 1 ,city 3) vehicle ( arriveEv 1 ,bus 2) subconcept ( arriveEv 1 , ArrivingAtAPlace ) subconcept ( Ed 4 , Person ) subconcept ( city 3 , City ) subconcept ( bus 2 , BusRoadVehicle ) From these clauses we can infer top  :  objectMoving ( arriveEv 1 ,Ed 4) toLocation ( arriveEv 1 ,city 3) subconcept ( arriveEv 1 , ArrivingAtAPlace ) subconcept ( Ed 4 , Person ) subconcept ( city 3 , City ) which corresponds to  “Ed arrived in the city”  omitting thetwo clauses: top  :  vehicle ( arriveEv 1 ,bus 2) subconcept ( bus 2 , BusRoadVehicle ) Note that a limited amount of ‘going up and down the tax-onomy’ can also be accounted for in this framework, at leastin principle. So  “Ed arrived in the city”  does entail that “A person arrived in the city” , since  Ed4  is a subconceptof   Person . Finally since “arriving” is a kind of movementevent,  “Ed arrived in the city”  can be ‘generalized’ to  “Ed went to the city” , assuming that  went   maps to a super con-cept of   ArrivingAtAPlace .The clauses we construct satisfy the usual monotonicitypatterns, both in positive and in negative form. Thus  “Ed arrived in the city by bus”  entails that  “Ed arrived in thecity” . But  “Ed did not arrive in the city”  entails that  “Ed did not arrive in the city by bus” , while  “Ed did not arrivein the city by bus”  does  not   entail that  “Ed did not arrive inthe city” . Inferences and Contexts The main reason for introducing contexts in our logic is tocreate boundaries corresponding loosely to the idea that con-textscreatecertain opaqueboxesthat purely extensional rea-soning should respect. Thus the top context corresponds towhat the author of the sentence takes the described worldto be like and when confronted with intensional notions like‘knowledge’ or ‘believe’ or ‘desire’, we create one of theseboxes and segregate what is known, believed or wanted intothat box. The idea of segregating the contents of a propo-sitional atittude predicate into its own context correspondsto the semantic notion that propositional atittudes introducealternative worlds into the discourse.We want to keep the restrictions on what we know aboutthese boundaries as underspecified as possible, minimizingthe number of conditions (or axioms) on these boxes. We  therefore assume that these boxing operators satisfy simplythe usual  K  axiom (Chellas 1980), which can be read as say-ing that this notion of context distributes over conjunction(or if one prefers, as saying that this very weak notion of context respects modus ponens).While it seems important to keep our system as generaland underspecified as possible, it would be better for rea-soning with our representations if we had more informationabout different kinds of contexts.As a simple example of the kind of inferences that theinteraction between contexts brings about, consider the sen-tence  Ed knows that the diplomat arrived  . As before we willneed concepts for the arrival event, for the knowing event,for the diplomat and for Ed. Assuming all of these conceptsand roles, as before, we represent this sentence as: knower ( knowEv 1 ,Ed 2) whatsKnown ( knowEv 1 ,c 1 ) subconcept ( Ed 2 , Person ) subconcept ( knowEv 1 , CognitionEvent ) objectMoving ( arriveEv 3 ,diplomat 4) subconcept ( diplomat 4 , Diplomat ) subconcept ( arriveEv 3 , ArrivingAtAPlace ) top  :  contextRelation ( know,top,c 1 ) instantiable ( knowEv 1) instantiable ( Ed 2) instantiable ( diplomat 4) c 1  :  instantiable ( arriveEv 3) In principle the arrival of the diplomat is only sup-posed to be true in these worlds compatible with whatEd knows. However, on the common understanding of  know , we can make the further assumption that everythingtrue in a  know  context is also true in the containing con-text. This notion of veridicality of the contained con-text,  c 1  with respect to its container  top  is represented by veridical ( c 1 ,top ) . This veridicality assumption allows usto move  instantiable ( arriveEv 3)  to the top context.More formally, if   contextRelation ( know,c 1 ,c 2 ) holds then we may want to say that all instantiability state-ments in  c 2  can be moved up to context  c 1 . We plan to buildon the distinctions beween contexts introduced by “know”,“say” and other classes with different implicational import.The kind of reasoning mechanism at play here seems to beof the following form. If   c  is a veridical context with respectto the context  top  and if   t  is a concept instantiable in  c  then t  is instantiable in the more general context  top  too, or: c  :  instantiable ( t )  veridical ( c,top ) top  :  instantiable ( t ) More generally: c i  :  instantiable ( t )  veridical ( c i ,c j ) c j  :  instantiable ( t ) In our discussion of negation we used: c i  :  instantiable ( t )  antiveridical ( c i ,c j ) c j  :  uninstantiable ( t ) More work is required to check whether all inferences wewant can be accounted for using such simple mechanisms. Further Work This short note only starts the discussion of the kinds of in-ferences that we expect to be able to make using a simplelogic of concepts and contexts. Amongst the issues we havenot discussed are the following: how to deal with tempo-ral modifiers and temporal interpretation in general; how todeal with presupposition and conventional implicatures ingeneral; what to say about cardinality and plurality as wellas about adjectival and adverbial modification. We intend todiscuss these as the project unfolds. References Baader, F.; Calvanese, D.; McGuiness, D.; Nardi, D.; andPatel-Schneider, P. 2003.  The Description Logic Hand-book  . Cambridge University Press.Chellas, B. F. 1980.  Modal Logic: an Intorduction . Cam-bridge University Press.Condoravdi, C.; Crouch, D.; Stolle, R.; de Paiva, V.; andBobrow, D. 2003. Entailment, intensionality and text un-derstanding. In  Proceedings Human Language Technol-ogy Conference, Workshop on Text Meaning, Edmonton,Canada .Crouch, D.; Condoravdi, C.; Stolle, R.; King, T.; de Paiva,V.; O.Everett, J.; and Bobrow, D. 2002. Scalabilityof redundancy detection in focused document collections.In  Proceedings First International Workshop on Scalable Natural Language Understanding (ScaNaLU-2002), Hei-delberg, Germany .Crouch, R. 2005. Packed rewriting for mapping seman-tics to kr. In  Proceedings Sixth International Workshop onComputational Semantics, Tilburg, The Netherlands .Dalrymple, M. 2003.  Lexical Functional Grammar  . Syn-tax and Semantics, vol. 34. Academic Press.Kaplan, R., andBresnan, J. 1982. Lexical-functionalgram-mar: A formal system for grammatical representation. InBresnan, J., ed.,  The Mental Representation of Grammati-cal Relations . Reprinted in Dalrymple et al. (editors), For-mal Issues in Lexical-Functional Grammar. CSLI, 1995.Lenat, D. 1995. Cyc: A large-scale investment inknowledege infrastructure.  Communications of the ACM,38(11):33–38  .McCarthy, J. 1993. Notes on formalizing context. In Proc. of the 13th Joint Conference on Artificial Intelligence(IJCAI-93) .
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks