Van Harmelen F., Lifschitz V., Porter B. Handbook of Knowledge Representation
Подождите немного. Документ загружается.
772 19. Nonmonotonic Causal Logic
default rules to express commonsense inertia in reasoning about action did not appear
until [43, 44]. (This use of such default rules was derived from a similar application in
the setting of knowledge update [39, 40].) In this connection, it may be helpful to men-
tion the historically important “Yale Shooting” paper of Hanks and McDermott [19],
who argued that neither default logic nor circumscription were suitable formalisms for
reasoning about action. The Yale Shooting paper considered a rather different attempt
to solve the frame problem in default logic, and demonstrated that that attempt was
unsatisfactory. A brief account of this appears in [26]. For more detail, see [44].
19.7 Causal Theories in Higher-Order Classical Logic
Lifschitz [24] extended causal theories to the nonpropositional case using higher-order
classical logic to express the fixpoint condition on a model, much in the manner of
circumscription. His definition can be understood to provide a general method for
translating finite Boolean causal theories into classical propositional logic.
Begin with a signature of classical logic, with a finite subset of the nonlogical
constants designated “explainable”. A nonpropositional causal rule is an expression
of the form
φ ⇐ ψ
where φ and ψ are classical formulas. A nonpropositional causal theory is a finite set
of nonpropositional causal rules.
The special case of nonpropositional causal theories in which all nonlogical con-
stants are explainable propositional constants coincides with the special case of the
previously defined (finite-domain propositional) causal theories in which all constants
are Boolean and causal theories are assumed to be finite.
In what follows, let
N be a list of all explainable nonlogical constants. We say that
a list of nonlogical constants or variables is similar to
N if it has the same length as N
and each of its members is of the same sort as the corresponding member of
N. We can
denote a formula (in which none, some, or all explainable nonlogical constants appear)
by φ(
N). Then for any list M that is similar to N , we can write φ(M) to denote the
formula obtained by simultaneously replacing each occurrence of each member of
N
by the corresponding member of
M.
Consider a nonpropositional causal theory T with rules
φ
1
(N,x
1
) ⇐ ψ
1
(N,x
1
)
.
.
.
φ
k
(N,x
k
) ⇐ ψ
k
(N,x
k
)
where
x
i
is the list of all free variables for the ith causal rule. Let n be a list of new
variables that is similar to
N.ByT
∗
(n) we denote the formula
1ik
∀x
i
(ψ
i
(N,x
i
) ⊃ φ
i
(n, x
i
)).
An interpretation is a model of T if it is a model of
(19.15)∀
n(T
∗
(n) ≡ n = N)
H. Turner 773
where
n = N stands for the conjunction of the equalities between members of n and
the corresponding members of
N.
Where the definitions overlap syntactically, this definition of model of a causal
theory agrees with the definition given earlier.
Notice that for finite Boolean propositional causal theories the corresponding sen-
tence (19.15) is a quantified Boolean formula, from which quantifiers can be elim-
inated (with worst-case exponential increase in size). Thus this approach yields a
general translation of finite Boolean propositional causal theories into classical propo-
sitional logic.
The completion method from Section 19.3 can be extended to “definite” nonpropo-
sitional causal theories, so that a “first-order” causal theory T has the same models as
the corresponding completion (which is a classical first-order formula) [24].
19.8 A Logic of Universal Causation
UCL is a modal nonmonotonic logic obtained from standard S5 modal logic (see
Chapter 15) by imposing a simple fixpoint condition that reflects the “principle of
universal causation”—the requirement that everything true in a model have a cause.
In [45], UCL was defined not only in the (Boolean) propositional case, but also for
nonpropositional languages, and was shown to subsume the nonpropositional causal
theories described in the previous section. Here, we consider a different extension of
(Boolean) propositional UCL, introduced in [46], built from finite-domain proposi-
tional formulas.
The fundamental distinction in UCL—between propositions that have a cause and
propositions that (merely) obtain—is expressed by means of the modal operator
C,
read as “caused”. For example, one can write
(19.16)ψ ⊃
Cφ
to say that φ is caused whenever ψ obtains. UCL formula (19.16) corresponds to the
causal rule φ ⇐ ψ. This claim is made precise in the UCL Theorem below.
UCL formulas are obtained by extending the recursive definition of a formula with
an additional case for the modal operator
C, in the usual way for modal logic:
• If φ is a U CL formula, then so is
Cφ.
A UCL theory is a set of UCL formulas.
An S5-structure is a pair (I, S) such that I is an interpretation and S is a set of
interpretations (all of the same signature) to which I belongs. Satisfaction of a UCL
formula by an S5-structure is defined by the standard recursions over the propositional
connectives, plus the following two conditions:
• if φ is an atom, (I, S) |= φ iff I |= φ,
• (I, S) |=
Cφ iff for all J ∈ S, (J, S) |= φ.
For a UCL theory T ,if(I, S) |= T , we say that (I, S) is an I -model of T , thus em-
phasizing the distinguished interpretation I .
We say that I is causal model of T if (I, {I }) is the unique I -model of T .
774 19. Nonmonotonic Causal Logic
UCL Theorem. For any causal theory T , the models of T are precisely the causal
models of the corresponding UCL theory
{ψ ⊃
Cφ : φ ⇐ ψ ∈ T }.
It is possible to characterize strong equivalence for UCL theories, much as was
done in Section 19.2 for causal theories. Interestingly, this requires a slight strength-
ening of S5. The SE-models of a UCL theory are a subset of the S5 models: those S5
models (I, S) such that (I, {I }) is also an S5 model [46].
Acknowledgement
Many thanks to my collaborators on this topic: Enrico Giunchiglia, Joohyung Lee,
Vladimir Lifschitz, and Norm McCain. This work partially supported by NSF
CAREER Grant #0091773.
Bibliography
[1] V. Akman, S. Erdo
˘
gan, J. Lee, V. Lifschitz, and H. Turner. Representing the Zoo
World and the Traffic World in the language of the Causal Calculator. Artificial
Intelligence, 153:105–140, 2004.
[2] A. Artikis, M. Sergot, and J. Pitt. An executable specification of an argumentation
protocol. In Proc. of Artificial Intelligence and Law (ICAIL), pages 1–11, 2003.
[3] A. Artikis, M. Sergot, and J. Pitt. Specifying electronic societies with the Causal
Calculator. In F. Giunchiglia, J. Odell, and G. Weiss, editors. Proc. of Workshop
on Agent-Oriented Software III (AOSE), LNCS, vol. 2585, pages 1–15. Springer,
2003.
[4] A. Bochman. A logic for causal reasoning. In Proc. IJCAI-03, pages 141–146,
2003.
[5] A. Bochman. A causal approach to nonmonotonic reasoning. Artificial Intelli-
gence, 160(1–2):105–143, 2004.
[6] J. Campbell and V. Lifschitz. Reinforcing a claim in commonsense reasoning.
In Logical Formalizations of Commonsense Reasoning: Papers from 2003 AAAI
Spring Symposium, pages 51–56, 2003.
[7] A. Chopra and M. Singh. Nonmonotonic commitment machines. In F. Dignum,
editor. Workshop on Agent Communication Languages, Lecture Notes in Com-
puter Science, vol. 2922, pages 183–200. Springer, 2004.
[8] K. Clark. Negation as failure. In H. Gallaire and J. Minker, editors. Logic and
Data Bases, pages 293–322. Plenum Press, New York, 1978.
[9] R. Craven and M. Sergot. Distant causation in C+. Studia Logica, 79:73–96,
2005.
[10] S. Dogandag, P. Ferraris, and V. Lifschitz, Almost definite causal theories. In
Logic Programming and Nonmonotonic Reasoning: Proc. of Seventh Internat.
Conf., pages 74–86, 2004.
[11] T. Eiter and T. Lukasiewicz. Probabilistic reasoning about actions in non-
monotonic causal theories. In Proceedings of the 19th Conference on Uncertainty
in Artificial Intelligence (UAI-2003), pages 192–199, 2003.
H. Turner 775
[12] R. Fikes and N. Nilsson. STRIPS: A new approach to the application of theorem
proving to problem solving. Artificial Intelligence, 2(3–4):189–208, 1971.
[13] A. Finzi and T. Eiter. Game-theoretic reasoning about actions in nonmonotonic
causal theories. In Logic Programming and Nonmonotonic Reasoning: 8th Inter-
national Conference, LNCS, vol. 3662, pages 185–197. Springer, 2005.
[14] H. Geffner. Causal theories of nonmonotonic reasoning. In Proc. of AAAI-90,
pages 524–530, 1990.
[15] H. Geffner. Reasoning with Defaults: Causal and Conditional Theories.MIT
Press, Cambridge, MA, 1992.
[16] M. Gelfond and V. Lifschitz. Representing action and change by logic programs.
Journal of Logic Programming, 17:301–322, 1993.
[17] E. Giunchiglia and V. Lifschitz. An action language based on causal explanation:
Preliminary report. In Proc. AAAI-98, pages 623–630, 1998.
[18] E. Giunchiglia, J. Lee, V. Lifschitz, N. McCain, and H. Turner. Nonmonotonic
causal theories. Artificial Intelligence, 153(1–2):49–104, 2004.
[19] S. Hanks and D. McDermott. Nonmonotonic logic and temporal projection. Arti-
ficial Intelligence, 33(3):379–412, 1987.
[20] J. Lee and V. Lifschitz. Describing additive fluents in action language C+. In
Proc. IJCAI’03, pages 1079–1084, 2003.
[21] J. Lee. Definite vs. nondefinite causal theories. In Logic Programming and Non-
monotonic Reasoning: Proc. of Seventh Internat. Conf., pages 141–153, 2004.
[22] V. Lifschitz, N. McCain, E. Remolina, and A. Tacchella.Getting to the airport: the
oldest planning problem in AI. In Logic-Based Artificial Intelligence, pages 147–
165. Kluwer, 2000.
[23] V. Lifschitz, D. Pearce, and A. Valverde. Strongly equivalent logic programs.
ACM Transactions on Computational Logic, 2:526–541, 2001.
[24] V. Lifschitz. On the logic of causal explanation. Artificial Intelligence, 96:451–
465, 1997.
[25] V. Lifschitz. Situation calculus and causal logic. In Proc. of the Sixth Internat.
Conf. on Principles of Knowledge Representation and Reasoning, pages 536–
546, 1998.
[26] V. Lifschitz. Success of default logic. In H. Levesque and F. Pirri, editors. Log-
ical Foundations of Cognitive Agents: Contributions in Honor of Ray Reiter,
pages 208–212. Springer-Verlag, 1999.
[27] V. Lifschitz. Missionaries and cannibals in the Causal Calculator. In Proc. of the
7th Internat. Conf. on Principles of Knowledge Representation and Reasoning,
pages 85–96, 2000.
[28] F. Lin. Embracing causality in specifying the indirect effects of actions. In
Proc. of IJCAI-95, pages 1985–1991, 1995.
[29] N. McCain and H. Turner. A causal theory of ramifications and qualifications. In
Proc. of IJCAI-95, pages 1978–1984, 1995.
[30] N. McCain and H. Turner.Causal theories ofaction and change.In Proc.of AAAI-
97, pages 460–465, 1997.
[31] N. McCain and H. Turner. Satisfiability planning with causal theories. In Prin-
ciples of Knowledge Representation and Reasoning: Proc. of the Sixth Internat.
Conference, pages 212–223, 1998.
[32] N. McCain. Causality in commonsense reasoning about actions. PhD Disserta-
tion, University of Texas at Austin, Department of Computer Sciences, 1997.
776 19. Nonmonotonic Causal Logic
[33] J. McCarthy and P. Hayes. Some philosophical problems from the standpoint
of artificial intelligence. In B. Meltzer and D. Michie, editors. Machine Intel-
ligence, vol. 4, pages 463–502. Edinburgh University Press, Edinburgh, 1969,
Reproduced in [34].
[34] J. McCarthy. Formalizing Common Sense: Papers by John McCarthy.Ablex,
Norwood, NJ, 1990.
[35] J. Pearl. Embracing causality in default reasoning. Artificial Intelligence, 35:259–
271, 1988.
[36] J. Pearl. Causality: Models, Reasoning and Inference. Cambridge University
Press, 2000.
[37] E. Pednault. ADL: Exploring the middle ground between STRIPS and the situa-
tion calculus. In R. Brachman, H. Levesque, and R. Reiter, editors, Proc. of the
First Internat. Conf. on Principles of Knowledge Representation and Reasoning,
pages 324–332, 1989.
[38] E. Pednault. ADL and the state-transition model of action. Journal of Logic and
Computation, 4:467–512, 1994.
[39] T. Przymusinski and H. Turner. Update by means of inference rules. In Proc. of
the 3rd Internat. Conf. on Logic Programming and Nonmonotonic Reasoning,
pages 156–174, 1995.
[40] T. Przymusinski and H. Turner. Update by means of inference rules. Journal of
Logic Programming, 30(2):125–143, 1997.
[41] R. Reiter. A logic for default reasoning. Artificial Intelligence, 13(1,2):81–132,
1980.
[42] M. Sergot and R. Craven. Some logical properties of nonmonotonic causal the-
ories. In Logic Programming and Nonmonotonic Reasoning: 8th International
Conference, LNCS, vol. 3662, pages 198–210. Springer, 2005.
[43] H. Turner. Representing actions in default logic: A situation calculus approach.
In Working Papers of the Third Symposium on Logical Formalizations of Com-
monsense Reasoning, 1996.
[44] H. Turner. Representing actions in logic programs and default theories: A situa-
tion calculus approach. Journal of Logic Programming, 31(1–3):245–298, 1997.
[45] H. Turner. A logic of universal causation. Artificial Intelligence, 113:87–123,
1999.
[46] H. Turner. Strong equivalence for causal theories. In Logic Programming and
Nonmonotonic Reasoning: Proc. of Seventh Internat. Conf., pages 289–301,
2004.
[47] G. White. A modal formulation of McCain and Turner’s theory of causal rea-
soning. In Logics in Artificial Intelligence: Proc. 8th European Conference
(JELIA’02), pages 211–222, 2002.
Part III
Knowledge Representation
in Applications
This page intentionally left blank
Handbook of Knowledge Representation
Edited by F. van Harmelen, V. Lifschitz and B. Porter
© 2008 Elsevier B.V. All rights reserved
DOI: 10.1016/S1574-6526(07)03020-9
779
Chapter 20
Knowledge Representation and
Question Answering
Marcello Balduccini, Chitta Baral, Yuliya Lierler
20.1 Introduction
Consider an intelligence analyst who has a large body of documents of various kinds.
He would like answers to some of his questions based on the information in these
documents, general knowledge available in compilations such as fact books, and com-
monsense. A search engine or a typical information retrieval (IR) system like Google
does not go far enough as it takes keywords and only gives a ranked list of documents
which may contain those keywords. Often this list is very long and the analyst still
has to read the documents in the list. Other reasons behind the unsuitability of an IR
system (for an analyst) are that the nuances of a question in a natural language cannot
be adequately expressed through keywords, most IR systems ignore synonyms, and
most IR systems cannot reason. What the intelligence analyst would like is a system
that can take the documents and the analyst’s question as input, that can access the
data in fact books, and that can do commonsense reasoning based on them to provide
answers to questions. Such a system is referred to as a question answering system or
a QA system. Systems of this type are useful in many domains besides intelligence
analysis. Examples include a Biologist who needs answers to his questions, say about
a particular set of genes and what is known about their functions and interactions,
based on the published literature; a lawyer looking for answers from a body of past
law cases; and a patent attorney looking for answers from a patent database.
A precursor to question answering is database querying where one queries a data-
base using a database query language. Question Answering takes this to a whole other
dimension where the system has increasing body of documents (in natural languages,
possibly including multimedia objects and possibly situated in the web and described
in a web language) and it is asked a query in natural language. It is expected to give an
answer to the question, not only using the documents, but also using appropriate com-
monsense knowledge. Moreover, the system needs to be able to accommodate new
additions to the body of documents. The interaction with a question answering system
780 20. Knowledge Representation and Question Answering
can also go beyond a single query to a back and forth exchange where the system may
ask questions back to the user so as to better understand and answer the user’s original
question. Moreover, many questions that can be asked in English can be proven to be
inexpressible in most existing database query languages.
The response expected from a QA system could also be more general than the
answers expected from standard database systems. Besides yes/no answers and factual
answers, one may expect a QA system to give co-operative answers, give relaxed
answers based on user modeling and come back with clarifying questions leading
to a dialogue. An example of co-operative answering [31] is that when one asks the
question “Does John teach AI at ASU in Fall’06”, the answer “the course is not offered
at ASU in Fall’06”, if appropriate, is a co-operative answer as opposed to the answer
“no”. Similarly, an example of relaxed answering [30] is that when one asks for a
Southwest connection from Phoenix to Washington DC National airport, the system
realizing that Baltimore is close to DC, and Southwest does not fly to DC, offers the
flight schedules of Southwest from Phoenix to Baltimore.
QA has a long history and [53] contains an overview of that as well as various
papers on the topic. Its history ranges from early attempts on natural language queries
for databases [39], deductive question answering [40], story understanding [19],web
based QA systems [4], to recent QA tracks in TREC [72], ARDA supported QA
projects and Project Halo [29]. QA involves many aspects of Artificial Intelligence
ranging from natural language processing, knowledge representation and reasoning,
information integration and machine learning. Recent progress and successes in all of
these areas and easy availability of software modules and resources in each of these
areas now make it possible to build better QA systems. Some of the modules and re-
sources that can be used in building a QA system include natural language parsers,
WordNet [54, 26], document classifiers, text extraction systems, IR systems, digital
fact books, and reasoning and model enumeration systems. However, most QA sys-
tems built to date are not strong in knowledge representation and reasoning, although
there has been some recent progress in that direction. In this chapter we will dis-
cuss the role of knowledge representation and reasoning in developing a QA system,
discuss some of the issues and describe some of the current attempts in this direc-
tion.
20.1.1 Role of Knowledge Representation and Reasoning in QA
To understand the role of knowledge representation and reasoning in a QA system
let us consider several pairs of texts and questions. We assume that the text has been
identified by a component of the QA system from among the documents given to it, as
relevant to the given query.
1. Text: John and Mike took a plane from Paris to Baghdad. On the way, the plane
stopped in Rome, where John was arrested.
Questions: Where is Mike at the end of this trip? Where is John at the end of
this trip? Where is the plane at the end of this trip? Where would John be if he
was not arrested?
Analysis: The commonsense answers to the above questions are Baghdad,
Rome, Baghdad and Baghdad respectively. To answer the first and the third
M. Balduccini, C. Baral, Y. Lierler 781
question the QA system has to reason about the effect of the action of taking a
plane from Paris to Baghdad. It has to reason that at the end of the action the
plane and its occupants will be in Baghdad. It has to reason that the action of
John getting arrested changes his status as an occupant of the plane. To reason
about John’s status if he was not arrested, the QA system has to do counterfac-
tual reasoning.
2. Text: John, who always carries his laptop with him, took a flight from Boston to
Paris on the morning of Dec 11th.
Questions: In which city is John’s laptop on the evening of Dec 10th? In which
city is John’s laptop on the evening of Dec 12th?
Analysis: The commonsense answers to the above questions are Boston and
Paris respectively. Here, as in the previous case, one can reason about the effect
of John taking a flight from Boston to Paris, and conclude that at the end of
the flight, John will be in Paris. However, to reason about the location of John’s
laptop one has to reason about the causal connection between John’s location
and his laptop’s location. Finally, the QA system needs to have an idea about
the normal time it takes for a flight from Boston to Paris, and the time difference
between them.
3. Text: John took the plane from Paris to Baghdad. He planned to meet his friend
Mike, who was waiting for him there.
Question: Did John meet Mike?
Analysis: To answer the above question, the QA systems needs to reason about
agent’s intentions. From commonsense theory of intentions [18, 22, 74], agents
normally execute their intentions. Using that one can conclude that indeed John
met Mike.
4. Text: John, who travels abroad often, is at home in Boston and receives a call
that he must immediately go to Paris.
Questions: Can he just get on a plane and fly to Paris? What does he need to do
to be in Paris?
Analysis: The commonsense answer to the first question is ‘no’. In this case the
QA system reasons about the precondition necessary to perform the action of
flying and realizes that for one to fly one needs a ticket first. Thus John cannot
just get on a plane and fly. To answerthe second question, one needsto construct
a plan. In this case, a possible plan is to buy a ticket, get to the airport and then
to get on the plane.
5. Text: John is in Boston on Dec 1. He has no passport.
Question: Can he go to Paris on Dec 4?
Analysis: With the general knowledge that it takes more than 3 days to get a
passport the commonsense answer to the above is ‘no’.