We accept this thesis as conformingto the required standardA CONDITIONAL MODEL OF ABDUCTIONByVeronica BecherLic. Universidad de Buenos Aires, 1990A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEInTHE FACULTY OF GRADUATE STUDIESCOMPUTER SCIENCETHE UNIVERSITY OF BRITISH COLUMBIAMarch 1993© Veronica Becher, 1993In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature)Department of C°1-11-)1 /4--..-T-^ET-Ac-tiThe University of British ColumbiaVancouver, CanadaDate M/Niz-t: H 2_6 4n it c.‘-3 3DE-6 (2/88)AbstractWe propose sometimes very plausible hypotheses as explanations for an observation, givenwhat we know or believe. In light of new information, however, such explanations maybecome void. Under this view explanations are defeasible. In this thesis we present ageneral model of explanation in artificial intelligence based on a theory of belief revision,(or the process of expanding, correcting and contracting existing beliefs) which modelsthe dynamics of belief in a given representation. We take seriously the notion that ex-planations can be constructed from default knowledge and should be determined relativeto a background set of beliefs. Based on the idea that an explanation should not onlyrender the observation plausible but be itself maximally plausible, a preference orderingon explanations naturally arises.Our model of abduction (the process of inferring the preferred explanations) usesexisting conditional logics for default reasoning and belief revision, based on standardmodal systems. We end up with a semantics for explanation in terms of sets of possibleworlds, which are simple modal structures also suitable for other forms of defeasiblereasoning. The result of this thesis is an object-level account of abduction based on therevision of the epistemic state of a program or agent. Abductive frameworks like Theorist,and consistency based diagnosis (today's "canonical" frameworks for diagnosis) are shownto be captured in our work.iiTable of ContentsAbstract^ iiList of Figures vAcknowledgement^ vi1 Introduction 11.1 Explanations and AI ^ 21.2 Thesis Overview 62 Prelude on Explanations, Belief Revision and Conditional Logic 92.1 Logical Preliminaries ^ 92.2 Approaches to Explanation 112.2.1^Philosophical Notions of Explanation ^ 112.2.2^Can There Exist a Purely Semantic Account for Abduction? 172.2.3^Poole's Architecture For Default and Abductive Reasoning . 192.2.4^Brewka's Preferred Subtheories ^ 202.2.5^Consistency Based Diagnosis 222.3 Belief Revision ^ 242.3.1^The AGM theory of Revision ^ 252.3.2^Belief Revision and Default Reasoning ^ 292.4 Modal and Conditional Logics ^ 302.4.1^Boutilier's Logics as Calculus for Default Reasoning and Belief Re-vision ^ 313 Epistemic Explanations 41iii3.1 Predictive Explanations ^ 423.2 Non-Predictive Explanations 533.3 Preferences in terms of Plausibility ^ 563.4 Pragmatics of Explanation ^ 593.4.1 Trivial Explanations 593.4.2 Irrelevant Factors and Disjunctions in Explanations ^ 604 Capturing "Abductive" Approaches^ 624.1 Capturing Theorist ^ 624.2 Extending Theorist: Predictive Explanations ^ 694.3 Capturing Brewka's Preferred Subtheories 704.4 Preferences: Maximizing Normality ^ 765 Capturing Consistency Based Diagnosis 795.1 Recasting Consistency Based Diagnosis in CT4O ^ 795.2 On the Relation between Consistency Based and "Abductive" Diagnosis^866 Conclusions^ 896.1 Summary 896.2 Future Research ^ 92A Proofs of Theorems Chapter 3^ 100B Proofs of Theorems Chapter 4 103C Proofs of Theorems Chapter 5^ 109ivList of Figures2.1 A CO-model (left) and a CT4O-model (right)^ 342.2 K-revision model ^ 363.3 Total-order revision model for the rain-sprinkler example, where "rain"and "sprinkler" are rejected in K^ 483.4 Revision model for the rain-sprinkler example, where "rain" is accepted inK. ^ 503.5 Revision model for the rain-sprinkler example, where "rain" is rejected inK. ^ 533.6 Preorder-revision model for the bleaching-T-shirt example. ^ 554.7 Theorist model for University Students example. ^ 654.8 Theorist model for D. {a D b, a j —lb} ^ 684.9 Brewka model for University Students example. ^ 725.10 Model reflecting expectation of correct behaviour, for two components. . 82vAcknowledgementI am enormously grateful to my supervisor, Craig Boutilier, who has been a genuinemaestro, and a constant source of direction and inspiration. I am also indebted to himfor introducing me to modal logic, which has been an invaluable experience.I want to express my deepest appreciation to David Poole, for being such a supportiveand ever-present figure during my program. I also acknowledge his timely and productivereview of this thesis.For their helpful comments and aid with my perverse English I deeply acknowledgeAndrew Csinger, Michael Horsch, Richard Dearden and Art Pope.Unforeseeably, this work had its start at a seminar in belief revision at the Universityof Buenos Aires. My thanks to Rail! Carnota, Carlos AlchourrOn and Adolfo Kvitca.Above all, I want to thank my loving husband Alejandro, who has been an inex-haustible fount of encouragement, for letting me test my ideas with him, and for makingthis life-era so pleasant.Certainly, I acknowledge the funding provided by my supervisor that made this re-search possible.viChapter 1IntroductionIf we try to explain why someone who was expected at the meeting did not show up,we may say that he might have been trapped in heavy traffic, or that he simply forgotabout the meeting. But we would not be likely to say that he suddenly died. Nor wouldwe say that he was kidnapped by extraterrestrials.Given an observation we want to determine if a sentence explains why the observationoccurred. This thesis is about modeling explanations. It is clear that not any sentence willbe considered explanatory. We will elaborate some conditions that an explanation shouldsatisfy with respect to the observation and certain background knowledge or set of beliefs.But as we realize from the above example, not all explanations are equally plausible.While some explanations may seem pretty digestible, others may near absurdity. Afterall, absurdity is a matter of degree given what we believe. We will model a notion ofplausibility of beliefs, and will be able to capture preferences in terms of plausibilityamong different explanations.Going back to our example, suppose we adopt the hypothesis that he was delayed inthe traffic. If later we learn that his child was being born at the time of the meeting,we will probably give up on the previously embraced explanation. This illustrates thedefeasibility of explanations. Much of our knowledge may become void in light of newinformation; probably only tautologies can be granted indestructible standing. In light ofproper counter-evidence, any explanation will fail. We take explanations to be inherentlydefeasible. We consider them as prima facie reasons for belief in the observation, givenwhat we know. This stresses that explanations are relative to background knowledge.We propose a model of explanation based on a theory of belief revision, or the process1Chapter 1. Introduction^ 2of modeling expansions, corrections and contractions of beliefs. Another source of thedefeasibility (or nonmonotonicity) of explanations is that they may be framed based ondefault knowledge, or expectations about the world as opposed to nomological universals.The framework proposed in this work seriously contemplates that explanations can beconstructed based on defaults. For instance, defaults can have the form "usually, peopledo not suddenly die".This thesis takes as its starting-point the use of logic for knowledge representation(KR) and reasoning in artificial intelligence (AI). Our development will be in termsof conditional logic. We will use existing conditional logics for default reasoning andbelief revision, in particular, Boutilier's modal conditional logics. We inherit a standardKripkean possible worlds semantics suitable for other forms of defeasible reasoning likesubjunctive reasoning, belief revision, default reasoning and planning (Boutilier 1992a).We are able to show formal correspondence between existing abductive frameworks andour work. This thesis does not address computational methods for explanations.1.1 Explanations and AIAs David Poole points out', when solving a problem in AI, we have to develop a programthat behaves as if it were intelligent. Such a program reasons not about the problem perse, but from and about a representation of the problem. This is a crucial distinction.Explanations in AI, then, are relative to the representation of the problem. This is truefor the treatment of explanations in this thesis, and any other AI framework. The notionof what is an explanation has been widely studied in the philosophical community, anddifferent authors diverge in their interpretations. It would be nice to start with a genericdefinition of an explanation and evaluate how AI captures the idea. But such a generalstatement is a difficult enterprise in itself, and we will not pursue it in this thesis. Muchof the work in AI that relates to explanation is referred as abductive reasoning. The term"abduction", as conceived by Charles Sanders Peirce, refers to the process of formulation1 Personal communication.Chapter 1. Introduction^ 3of most plausible explanatory hypotheses. Unfortunately, this term has been specializedin the AI jargon, referring exclusively to some logic-based account. In this thesis, whenreferring to those logic based-accounts (like Theorist), we will call them "abductive"using the quotes. Otherwise, the term abduction will be used to refer to the inference tothe best explanations.Explanations in this thesis should not be regarded as a natural language construction,but as a logical abstraction, one of the two parts involved in an inferential relation: anhypothesis for some observation, or a cause for an effect, or a reason for some evidence,or a premiss for a conclusion, or more generally, an explanan for an explanandum. Thereare many AI applications that can be modeled as a form of abductive reasoning. Amongthem, diagnosis, image interpretation, natural language interpretation, learning. In diag-nosis (Peng and Reggia 1990, Reiter 1987, de Kleer Mackworth Reiter 1990, Poole 1989,1991), given an observation about the system's behaviour, an explanation (some repre-sented knowledge) of why such behaviour arose is provided by the program. In imageinterpretation (recognition) (Reiter and Mackworth 1989), given an image, the intelli-gent program should determine a scene that gave rise to such image. In natural languageinterpretation (Stickel 1990), (Hobbs 1990), given an utterance, a "story" behind suchan expression has to be determined. In learning as a process of theory formation (Mor-ris and O'Rorke 1990) given an observation that contradicts an existing theory, a newtheory should be modeled that accounts for the observation. In argumentation, given aparticular argument (or its negation), a set of reasons for it should be provided. Therange of applications seems to be very large, we add to the above list court deliberation(what set of laws and regulations would lead to a particular sentence), detective reasoning(what set of hypotheses would lead to solving the crime), financial stock exchange (whatmarket scenario may provoke a particular stock status), and economic analysis (how thevariables should be combined to reach a particular economic situation).Any account of explanation ought to resolve how to determine a set of preferred ex-planations. Some preference criteria is called for. At this point, there seems to be a lackChapter 1. Introduction^ 4of consensus. As pointed out by David Poole 2 , while in natural language understandingthe most specific explanation would be preferred, in diagnostic tasks the least presump-tive explanation would. In this work we argue for a measure of preference in terms ofplausibility. Different applications should characterize what states of affairs are moreplausible. Abductive frameworks in AI have not resolved satisfactorily the problem ofpreferences on explanations. Among the criteria used to capture preferences we foundthe following. The minimal cardinality criterion imposes that explanations consistingof fewer hypotheses should be preferred over those with a larger number of hypotheses.Peng and Reggia (1990) showed that this criterion may fail to reflect plausibility since anexplanation of a symptom consisting of a rare disease will always be preferred over oneconsisting of two common diseases. The irredundancy criterion determines that super-sets of explanations should not be preferred. Reiter's minimal diagnosis is based on thisprinciple. Component failures are modeled as abnormalities. Given an observation thatconflicts with the expected correct behaviour of the system, a set of failing componentsis conjectured to explain the discrepancy. Diagnoses consist of minimal (subset related)abnormalities. Although preferences in terms of irredundancy may reflect plausibility,it is hard to accommodate that the abnormality of one component be preferred overanother one.If numbers are available, probabilistic frameworks (de Kleer and Williams 1987, Poole1992), may derive meaningful preferences. We can see our work capturing the spirit ofprobabilistic proposals but in a qualitative fashion.Some authors like Kurt Konolige (1992a) start from a predefined set of potentialexplanations, and argue that capturing preferences is just a matter of mathematicallyexpressing a partial order on the subsets of potential explanations. We argue against thisapproach because it ignores the context dependent nature of explanations with respectto the background knowledge. A fixed ordering of conjectures is problematic because2 Personal communication.Chapter 1. Introduction^ 5it is implicitly established relative a particular state of affairs (say most normal situa-tions, past experience, or whatever). Hence, if the context changes, the ordering becomesmeaningless. But this dependency is not represented in those formalisms. Our approachovercomes these difficulties, and requires no explicit ordering of hypotheses. The pref-erence ordering on explanations will originate from a preference ordering over statesof affairs (possible worlds). We will discuss this problem of preferences further in thefollowing chapters. Hector Levesque (1989) showed the impossibility of discriminatingpreferences among explanations based on any semantic measure when using classical ma-terial implication as the connective between explanation and observation. Based on thisresult, Levesque develops a syntactic measure of "simplicity" to account for preferencesamong explanations. We will elaborate on his results in Section 2.2.2.Our account of explanation refrains from using material implication as the connective.In contrast, we will propose a conditional connective, which is not truth-functional. Anatural account of preferences in terms of plausibility becomes possible. At anotherfrontier, in most existing AI frameworks for abductive reasoning, if the observation isinconsistent with given facts or background knowledge, then it is unexplainable. Thoseframeworks do not contemplate the possibility of explaining counterfactual observations.For instance, consider the defaults "brunettes get a bronze tan" and "blonds do not geta bronze tan", and suppose as a fact that "Fred is blond, and his brother is brunette".The counterfactual observation of Fred having a bronze tan is not explainable, since thecandidate explanation of Fred being brunette as his brother conflicts with the facts. Wewill propose an account of explanations where hypothetical situations be explained, bybeing able to reason counterfactually.Some AI approaches to explanation/causation start from a causal theory, like Kono-lige's default causal networks (1992b) and bayesian nets (Pearl 1988), and are intendedand restricted to derivation of causal explanations. In order to appreciate the explana-tions arising from this thesis, we should mention that we take explanation as a broadernotion than causation. Causation is associated with an asymmetrical relation betweenChapter 1. Introduction^ 6cause and effect that can be detected by appealing to controllability of phenomena (ma-nipulating the effect will not change the cause). In the concluding chapter of this thesiswe discuss the idea of modeling causality as an extension of our framework.1.2 Thesis OverviewIn Chapter 2 we will introduce background material. The subsequent chapters will buildon the concepts of this chapter. Motivating our work we will review some work fromthe philosophical literature. We will examine Peirce, Hempel, Quine and Ullian andGdrdenfors's work. Then we will turn to existing approaches to explanation from theAI perspective. In particular, we present the Theorist architecture for default and ab-ductive reasoning, and consistency based diagnosis. We will briefly review the work ofAlchourrem, Gardenfors and Makinson on belief revision, on which we will base our anal-ysis of explanation. We will then study Boutilier's modal conditional logics, and theirrole in default reasoning and belief revision, emphasizing the possible worlds semanticsof these logics.Chapter 3 will present our model of explanation based on the revision of the epis-temic state of a program or ideal agent. We will consider a background epistemic staterepresenting an agent's beliefs. Our main concern will be to develop a general accountof abduction based on principled semantics and expressible in a logical calculus. We willmodel explanations relative to some background knowledge, respecting their inherentdefeasibility. We will provide the capability to derive preferences in terms of plausibility,and explain factual and hypothetical observations.What is to be explained (the explanandum) can either be accepted, rejected or inde-terminate in the background epistemic state. We will discuss the appropriate epistemicstatus an explanation should have for each possible status of the explanandum. Whenthe program (or ideal agent) receives an inquiry about an explanandum that is alreadybelieved (or accepted) by the program, we will argue that an explanation should also bebelieved.Chapter 1. Introduction^ 7We will analyze explanations via hypothetical changes in belief. Our strongest notionof explanation will impose that (hypothetical) belief in the explanation should result infull belief of the explanandum. We will name them predictive explanations. We willthen explore alternative weaker notions of explanation. These will be characterized bythe condition that acceptance of an explanation should make the explanandum possible.Differing in their explanatory power, will end up with a family of explanations referredas "epistemic explanations" .Via the Ramsey test for acceptance of conditionals we will be able to translate ourcharaterization of explanations in terms of changes in belief, into subjunctive condition-als. Explanations will be expressed as subjunctive conditionals relative to the agent'sepistemic state.Based on the idea that an explanation should not only make the explanadum plausiblebut the explanation itself be maximally plausible, a preference ordering on explanationswill naturally arise. We will discuss some pragmatic aspects of explanation, showing thatsemantic criteria may fall short in order to shape a simplest or most informative sentenceas an explanation for a given observation.In Chapter 4 we will take Theorist as representative of "abductive" approaches toexplanation. By interpreting the background epistemic state as a theory of expectations,we will show how Theorist can be recast in out framework. Theorist explanations willbe modeled as conditional sentences. The corrrespondence with epistemic explanationswill be drawn. Then we will explore Brewka's extension of Theorist, that provides aprioritized setting. We will elaborate on the effect of priorities over defaults when usedabductively. We will propose how to augment Theorist and also Brewka's extension inorder to provide predictive explanations, and also preferences among explanations.Chapter 5 works out the correspondence between consistency based diagnosis and ourmodel of explanation. By interpreting the expectation of correct behaviour the systemas a default of component working normally, we will map the consistency based diagnosisaccount on a Theorist model. By mapping the consistency based and the "abductive"Chapter 1. Introduction^ 8Theorist framework on the same kind of model, we will be able to highlight connectionsbetween the two.Finally, in Chapter 6 we will discuss the accomplishments of this thesis and proposeseveral avenues for further research, indicating different ways in which our account ofexplanation can be generalized or extended.Chapter 2Prelude on Explanations, Belief Revision and Conditional LogicIn this chapter, we will lay the necessary foundations to later present our semantic accountof explanations. We will review some existing approaches to explanations, mainly tomotivate this work. We will first concentrate in some philosophic perspectives, reviewingthe ideas of Peirce (1923), Hempel (1966), Gardenfors (1988), Quine and Ullian (1978)and Lewis (1973).Then we will examine some qualitative AI approaches to explanation, concentratingin Poole's architecture for default and abductive reasoning (1989), and consistency baseddiagnosis (Reiter 1987; de Kleer, Mackworth, Reiter 1990). In Chapters 4 and 5 thesetwo different accounts will be recast in our framework.We will briefly review the work of Alchournin, Gardenfors and Makinson (AGM) onbelief revision, upon which we will base our development of explanation. Then we willlook over some modal and conditional logics, in particular Boutilier's logics, emphasiz-ing their ability to handle defeasible reasoning and belief revision. We will study howBoutilier's conditional logics provide a logical calculus and a unified Kripkean semanticsfor the AGM theory of revision and default reasoning. This section will be particularlyimportant as a preliminary to the chapters to follow.2.1 Logical PreliminariesWe will refere with CPL to classical propositional logic. We take P to denote a denu-merable set of atomic variables and LCPL to denote the propositional language over thisset, based on classical propositional logic with the connectives A, V, —1, D. Capital lettersA, B, C, and greek letters a, 0, -y will be used as variables over propositional formulae.9Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^10Often the letters A, B, C will just denote propositional variables or atoms. Words suchas rain will be used in examples and indicate atomic relation symbols. Lower-case lettersr, s, q will be used similarly. The symbols T, 1. denote truth and falsity respectively. Let-ters S, T, X, Y will be used for sets. We will also consider a bimodal language LB basedon LCPL augmented with two modal operators ^ and b. The sentence Oa indicates "ais true at all accessible worlds", while ba indicates "a is true at all inaccessible worlds".Boutilier's family of bimodal conditional logics are defined over LB.The symbol F- is used to indicate derivability in different systems, using a subscriptto specify the system; so 1CPL denotes derivability in CPL, 1-c740 denotes derivabilityin CT4O(Boutilier 1992a). We will use Cn to denote the logical consequence operationin the system we are working with.We refer to propositional valuations as possible worlds or states of affairs. We willuse the letters w, v, u to designate possible worlds. For any sentence a in LCPL, we willdenote with Hall the proposition expressed by a (the set of possible worlds where thesentence a is true). Usually the letters V, W will be used to indicate sets of possibleworlds.Semantic entailment will be denoted by the symbol using subscripts to indicateentailment in different classes of models. Also will be used to indicate satisfaction offormulae more generally. We will write w a if w is a world that satisfies a, meaningthat w assigns truth to a. When w a, we will say that w is an a-world. If a is a validformulae, we will write a. We will also write w X for a set X, meaning that worldw satisfies each element of X.Motivated by clarity concerns, we will write a conditional sentence X when Xis a finite set, meaning that the conjunction of the elements of X conditionally entail asentence 0. Ditto for a a conditional sentence based on the connective —>.We will refer to the following properties of binary relations. Let X be a set, and R be abinary relation over elements of X.R is reflexive in X if and only if for all x E X : xRxR is antisymmetric in X if and only if for all x, y E X : xRy and yRx only if x = yChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^11R is transitive in X if and only if for all x, y, z E X : if xRy and yRz then xRzR is connected in X if and only if for all x, y E X if x 0 y, then xRy or yRxR is totally connected in X if and only if for all x, y E X : xRy or yRxThe relation R is a preorder on X if and only if R is reflexive and transitive. R is apartial order on X if and only if R is reflexive, transitive and antisymmetric. R is a totalorder on X if an only if R is reflexive, transitive and totally connected.2.2 Approaches to Explanation2.2.1 Philosophical Notions of ExplanationPeirce's notion of AbductionIn his "Chance, Love and Logic" (1923), Charles Sanders Peirce discusses the natureof deduction, induction and abduction' as three different forms of reasoning. He startswith a syllogism to exemplify deductive inference. He explains that the major premiseindicates a rule, as Rule. — All men are mortal, and the minor premise indicates a caseunder the rule, as Case. — Enoch was a man. The conclusion applies the rule to thecase and states the result: Result. - Enoch is mortal. He asserts "all deduction is of thischaracter; it is merely the application of general rules to particular cases." Peirce showshow by inverting the deductive syllogism, two forms of synthetic inference are obtained,hypothesis and induction. He explains that making an hypothesis is the inference of acase from a rule and result; and describes induction as the inference of the rule from thecase and result. Peirce exemplifies the three kinds of inference as follows (page 134).DEDUCTIONRule.— All the beans from this bag are white.Case.— These beans are from this bag..•. Result.— These beans are white.INDUCTIONCase.— These beans are from this bag.1 1n these essays Peirce refers to abduction with the term "hypothesis"; years later he renamed thisform of reasoning as "abduction".Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^12Result.— These beans are white..•. Rule.— All the beans from this bag are white.HYPOTHESISRule.— All the beans from this bag are white.Result.— These beans are white..•. Case.- These beans are from this bag.He considers hypotheses as explanatory suppositions (page 135):"Hypothesis is where we find some very curious circumstance, which would beexplained by the supposition that it was a case of a certain general rule ...Numberless documents and monuments refer to a conqueror named Napoleon Bona-parte. Though we have not seen the man, yet we can not explain what we haveseen, namely all these documents and monuments, without supposing he reallyexisted."Peirce calls abduction to the process of formulation and selection of hypotheses in scien-tific inquiry. As Nicholas Rescher (1978) puts it, abduction accounts for the process of"conjectural proliferation of explanatory hypothesis that merit closer scrutiny". Peircedescribes abduction as the suggestion of a theory that would render necessary (a strongsense of explanation) some surprising phenomena. But, as Rescher explains, "conjecturalfancy is limitless"; then, some guidance for effective theorizing is needed. This guidanceis given by Peirce's concept of plausibility. These quotes are extracted from (Rescher1978, page 44)."Every inquiry whatsoever takes its rise in the observation ... of some surprisingphenomenon, some experience which either disappoints an expectation, or breaksin upon some habit of expectation... At length a conjecture arises that furnishes apossible Explanation...On account of this Explanation, the inquirer is led to regard his conjecture orhypothesis, with favor. As I phrase it, he provisionally holds it to be "Plausible";this acceptance ranges in different cases -and reasonably so- from a mere expressionof it in the interrogative mood, as a question meriting attention and reply, upthrough appraisals of Plausibility, to uncontrollable inclination to believe. (CP,6.469 [1908])... By plausibility, I mean the degree to which a theory ought to recommend itselfto our belief ... "(CP, 8.223 [c. 1910])Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^13Other Philosophical Work on ExplanationsThe problem of explanations has been deeply studied by philosophers. Hempel (1966)defines two basic requirements for scientific explanations: the requirement of explanatoryrelevance and the requirement of testability. The former guarantees that the explanationbe related with the essential of the question. The latter says that an explanation shouldbe a "risky" or "non trivial" (in the sense of (Popper, 1969)) assertion of why a givenobservation occurred. An explanation consists of an explanandum sentence, the sentencedescribing the phenomenon that needs to be explained (observation), and explanan sen-tences, which specify explanatory information that account for the observation. Hempeldefines his deductive nomological explanations as formed by explanan sentences consist-ing of general laws and assertions about particular facts. Thus, in deductive-nomologicalexplanations, explanans deductively imply the explanandum, satisfying the two require-ments for scientific explanation in the strongest sense.Gdrdenfors (1988, Chapters 8 and 9, analysis of explanation and causation) requiresthat explanations be evaluated relative to a background theory or epistemic circum-stances; that is, the connection between explanan and explanandum should be givenrelative to an epistemic state. Gardenfors's view of including the role epistemic circum-stances contrasts with Hempel's deductive nomological explanations.The central idea in Gardenfors' analysis is that explanations should decrease the de-gree of surprise of the explanandum in a non-trivial way. He requires the explanandumsentence to be accepted in the epistemic state where the inquiry arises, while explanationsshould not. The power of an explanation is given by its ability to decrease the degree ofsurprise of the explanandum. Accepting an explanation should make the explanandumless surprising relative to the (possibly hypothetical) epistemic state where the explanan-dum is indeterminate. The belief value of the explanandum in this state is compared tothe belief value of the explanandum in the hypothetical state resulting after learning anexplanation.Let's see an example. If we wonder "why Victoria is tanned although it is winterChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^14here", the answer that "she has recently spent a week in the Canary Islands" is anexplanation satisfying Gardenfors' conditions. Suppose we didn't know that Victoria istanned, then, being winter here, Victoria's tan becomes less surprising if we learn thatshe spent a week in the Canary Islands.Gardenfors illustrates how his conditions on explanations account for "spurious" ex-planations. Basing his model on the dynamics of epistemic states, what has been anexplanation relative to an epistemic state may cease to be an explanation in a state con-taining more knowledge. We regard spurious explanations as characterizing the "non-monotonicity" or defeasibility of explanations (page 184)."... For example, I may be surprised by the fact that Victoria is tanned in themonth of February. If I ask for an explanation and get the answer that Victoriahas recently spent a week on the Canary Islands, I accept this as an explanationbecause I know that most people who have recently been on the Canary Islands aretanned. However, if I later learn that it had been raining on the Canary Islandsthe week Victoria was there, the old explanation is no longer satisfactory, and Ionce more lack information of why she is tanned."Our work (to be presented in the next chapter) will strongly follow Gardenfors' viewin that we will consider explanations relative to an epistemic state. However, havingdifferent ideas of explanation in mind, our account will differ from his. Gardenfors'sanalysis is formulated in a probabilistic model of epistemic states, while ours will bebased on belief sets. More important is that we have a different perspective with respectto what are necessary conditions for explanation. His view is suitable for scientific inquiry,while ours may not be. We will carefully discuss this issue in Chapter 3.Quine and Ullian's (1978) conceive explanations as plausible hypotheses. Our modelof explanation will allude to their view.(page 66) "... What we try to do in framing hypotheses is to explain some otherwiseunexplained happenings by inventing a plausible story, a plausible description orhistory of relevant portions of the world."They discuss five "virtues" that an hypothesis may enjoy in varying degrees. The firstChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^15three virtues account for the plausibility of hypotheses by appealing to their "believabil-ity" given our background beliefs. Virtue I is conservatism or compatibility with previousbeliefs.(page 66) "Acceptance of a hypothesis is of course like acceptance of any belief inthat it demands rejection of whatever conflicts with it. The less rejection of priorbeliefs required, the more plausible the hypothesis —other things being equal.... our friend the amateur magician tells us what card we have drawn. How didhe do it? Perhaps by luck, one chance in fifty-two; but this conflicts with ourreasonable belief, if all unstated, that he would not have volunteered a performancethat depended on that kind of luck. Perhaps the card were marked; but thisconflicts with our belief that he had no access to them, they being ours. Perhapshe peeked or pushed , with a help of a sleight-of-hand; but this conflicts with ourbelief in our perceptiveness. Perhaps he resorted to telepathy or clairvoyance; butthis would wreck havoc with our whole web of belief. The counsel of conservatismis the sleight-of-hand"Virtue II is modesty, stating one hypothesis more modest than another when logicallyweaker. The more modest hypothesis will be implied by the other without implying it.Another (rather different) characterization of a modest hypothesis is as assuming eventsof a more usual and familiar sort, hence more to be expected. Simplicity makes virtue III,which strives for avoiding gratuitous complications in hypotheses. Virtue IV, generality,represents the quality of having a wide range of application. In other words, generalityfights against the ad hoc. The fifth virtue is refutability, and defends hypotheses frombeing insusceptible of confirmation and useless for prediction.(page 79) "... some imaginable event, recognizable if it occurs, must suffice torefute the hypothesis. Otherwise, the hypothesis predicts nothing, is confirmed bynothing, and confers upon us no earthly good beyond perhaps a mistaken piece ofmind "Having analyzed the five virtues of an hypothesis, Quine and Ullian present the idea ofexplanatory hypotheses as "predictive explanations".(page 108) "The immediate utility of a good hypothesis is as an aid to prediction.... The relation between an explanatory hypothesis and what it explains seemsChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^16somewhat like implication; at any rate it transmits plausibility. That is, if someonebelieved the hypothesis to begin with, he should thereby be inclined to believe alsoin what it purports to explain."The spirit of our work is very much related to Lewis' (1973, 1977) counterfactualanalysis of causation. From a philosophical perspective, causation and explanation arevery related but two different problems. Causal explanations are a special case of expla-nations. Lewis (1973) argues that regularity analysis of causation suffers from confusingcausation with other causal relations such as epiphenomena, secondary effects and pre-empted causes. He proposes a counterfactual analysis of causation that attacks theseproblems, based on the following counterfactual statement: Had the cause been absent,its effects -some of them at least and usually all - would have been absent as well. Lewisdefines causal dependence among single events as two counterfactual dependences: If thecause (C) had not been, then the effect (E) never had existed, (taking > as a "generic"counterfactual connective, we shall write > -1E). And, Had the cause occurred, theeffect would have occurred as well (C > E). Then, causation is defined as "causal de-pendence among actual events": C is a cause for E if and only if both are part of theactual state of affairs, and moreover, > - E.Lewis's work has been criticized for not handling cases of multiple-causation. Whileone cause could have been absent, another cause could have occurred, thus neglectingthe counterfactual condition: Had the cause been absent, the effect had been absent aswell. We conclude that this counterfactual dependence is definitely inadequate for expla-nations, since we may expect multiple explanations for an inquiry. However, our analysisof predictive explanations will share with Lewis' work the other counterfactual depen-dence, which we phrase as: Were an explanation believed, so too would the observation.Jaegwon Kim (1973) points out a number of weaknesses in Lewis' treatment of causation,arguing that not only is causal dependence captured by counterfactual dependence, butalso analytical or logical dependence and other kinds of determination. Here are two ofhis examples. The counterfactual assertion "If yesterday had not been Monday, todaywould not be Tuesday" manifests a logical or analytical dependence, but not causal. "IfChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^17my sister had not given birth at time t, I would not have become an uncle at time t "manifests determination but not causal dependence. We conclude that logical or ana-lytical dependencies can be acceptable explanations. According to Lewis, causation is atransitive relation that occurs among actual events. But explanations are not necessarilytransitive. Just consider any of our famous examples in AI. Adults are usually employed,University students are usually adults, but University students are usually unemployed.Being a university student explains Fred being an adult. Being an adult is an explanationfor being employed; however, being a university student is not a reasonable explanationfor being employed. In our concluding chapter we will briefly discuss the extension ofour framework to account for causality.2.2.2 Can There Exist a Purely Semantic Account for Abduction?From an AI perspective this is a fundamental question. Hector Levesque (1989), definingabduction in terms of a model of belief, demonstrates the impossibility of sorting outpreferred (or say, most plausible) explanations, and discusses the need of a syntacticmeasure of simplicity to do it. Levesque sees abduction as inference from what we aretrying to explain to the simplest (or most preferred or plausible) explanations, relative toa particular model of belief (so that different models of belief give rise to different formsof abductive reasoning). However, he commits to a truth functional connective (materialimplication) to model the logical relation between explanation and observation.Levesque assumes a logical language .C* with a modal operator for belief BA, andan objective sublanguage C. Atomic sentences of C* are of the form BAa, where a is asentence of L. B A a says that a is a belief of type A. e B A a says that B A a is true atepistemic state e. Levesque defines an explanation for a sentence 0 with respect to anepistemic state e, for a type of belief A as follows:e [B A (a D 0) A -IBA-Ia]Explaining )3 is accomplished by finding all those "simplest" a (given a syntactic measureof simplicity) satisfying the above definition. Levesque presents the following example.Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^18"Suppose we know that male and (hepatitis 3 jaundice) are both true. If weobserve jaundice in a patient, we might be interested in determining what mightexplain it, based on what we know. In this case the answer is clearly hepatitis, butit is not obvious how to characterize in general the answers we are looking for.... in terms of propositions there will be propositions that are logically-too-strongand others that are logically-too-weak. For instance, (hepatitis A migraines) ac-counts for the jaundice in that it is consistent with what is known and if it weretrue, then jaundice would be too. Similarly, (hepatitis V -"male) accounts for jaun-dice since it too is consistent with what is known, and if it were true, then jaundicewould be also, since male is known to be true. Yet (hepatitis A migraines) implieshepatitis which implies (hepatitis V -male)."Then he shows that the proposition denoting hepatitis can not be distinguished fromthese other propositions."To see this, suppose the contrary that there were a function F that given a propo-sition expressed by (a 3 /3) and the one expressed by would always return the oneexpressed by a. That is, suppose that for every a and /3, F(II(a 3 /3 )11,11/3 11) =Then, we would have F(11(4 3 011, 11q11) = 11q11, and F(114 3 011, hip = II-LII. How-ever, 11(q 3 q) 11 = 11(- 1- 3 011 since the two sentences are logically equivalent. Butthis implies that I1LII = 11q11, which is incorrect. Such a function F cannot exist,and we are forced to go beyond the logic of the sentences (that is beyond the propo-sitions expressed) to differentiate hepatitis from other potential explanations."We take Levesque's demonstration of the non-existence of such a function F as an indi-cation of the inappropriateness of material implication to represent explanations. Thisactually motivates our account for explanations which will not be based on a truth func-tional connective, allowing for preferences in terms of plausibility, and capturing thempurely logically. Still, "pragmatic" concerns with respect to the usefulness of explana-tions may call for some syntactic measure of simplicity. We will elaborate on this inChapter 3.In Levesque's account, explanations can not be disbelieved in the background epis-temic state. This is necessary since the link between explanation and explanandum ismaterial implication. As a consequence, a sentence that is rejected in the backgroundepistemic state is not explainable. We aim for a more general approach to explanationthat permits the explanation and explanandum be hypothetical beliefs.Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^192.2.3 Poole's Architecture For Default and Abductive ReasoningPoole (1988, 1989, 1990), in his pioneer Theorist framework for default and abductive rea-soning, considers two activities, explaining observations and predicting what is expectedto be true. Explanations are modeled as arising from a process of theory formation;given some observations, the system constructs a theory which would explain those ob-servations. Poole assumes a standard first order language. An instance of a formulais a substitution of terms in this language for free variables in the formula. Theoristframework is elegantly defined in terms of two sets of formulae. The set of facts .F, whichare taken to be true of the domain, and the set of "possible hypotheses" 7-1 . The poolof hypotheses 7-1 consists of two sets, defaults D and conjectures C. Defaults in D areconsidered "normality assumptions" that can be assumed to be true given no evidenceto the contrary. Defaults can be used in prediction and explanation. C is the set ofconjectures, which are considered "abnormality assumptions". Conjectures are possiblehypotheses which can be used only for explaining observations.We will refer with the pair (T, 7-1) to a default theory. We will slightly modify Poole'snotation in the next definitions. A scenario is defined as a set of hypotheses that couldbe true based on the given facts.Definition 2.1 (Poole 1989) A scenario of a default theory of (.T, 7-1) is a set H ofground instances of elements of 7-t such that H U is consistent.An extension of a default theory is a maximal scenario.Definition 2.2 (Poole 1989) An extension of (F, D) is the set of logical consequencesof .7- together with a maximal (with respect to set inclusion) scenario of (F, 7").Predictions are skeptical conclusions from a default theory that are expected to be truegiven the facts, no matter which defaults are assumed. Predictions are based on thenormality assumptions or expectations about the world, that are consistent with thefacts. Conjectures do not participate in forming predictions.Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^20Definition 2.3 (Poole 1989) -y is predicted iff -y is in all extensions of (F, D).Poole defines an explanation of an observation as a scenario of the default theory thatgives rise to the observation.Definition 2.4 (Poole 1989) If 0 is a closed formula, an explanation of 0 is a scenariothat together with F implies /3.So, an explanation for an observation 0 from (F, f) is formed by sets C and D instancesof elements of C and D respectively, such that.FUCUDII, and F U C U D is consistentthen, C U D is an explanation of 0. Notice that depending on the default theory,even contradictory explanations can be drawn for a given observation. For example,let (1.,7-1) such that 1' = {} and 7-1 = D U C, D = {(A A Q) D B,(-,A A R) D B},C = {A, -IA, Q, R}. A A Q is an explanation for B and so is --,A A R. Notice also that forsome default theories, the same explanation can explain contradictory conclusions. Forexample, let (T,7-1) such that li = D U C, where F = {}, D = {A D B, A D -B}, andC = {A}. A explains B and and also A explains -, A.The following theorem demonstrates that whenever an observation is explainable,there is an explanation consisting of a maximal set of defaults.Theorem 2.1 (Poole) There is an explanation of /3 if /3 is in some extension.2.2.4 Brewka's Preferred SubtheoriesGerhard Brewka (1989) extends Poole's Theorist framework by introducing prioritiesamong defaults. To preserve an homogeneous notation we will adapt Brewka's notationto make it consistent with our exposition of Theorist. Brewka presents his framework fordefault reasoning considering a set of defaults with different degrees of reliability, allowingto express that one default may have priority over another one. That is, defaults haveChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^21the ability to block other defaults. Brewka does not isolate facts from defaults, arguingthat facts can always be expressed in the rank of the most reliable formulae. Withoutloss of generality, we will introduce a set .7", possibly empty, of sentences of true facts,that we consider non-defeasible. We then define a Brewka theory as follows.Definition 2.5 A Brewka theory is a pair (.7', B) such that F is a set of true facts, andB = (B1, B2, . Bn ) is a set of defaults where the rank B 2 is more reliable than Bi iffi < j, and no rank of B needs to be consistent.A Theorist default theory (with no conjectures) (.7' ,D) corresponds to a Brewka theory(. , B) when B possesses a unique level of reliability, i.e. B = (D). Brewka definesa preferred subtheory as the counterpart of an extension . We will adapt Brewka'sdefinition of a preferred subtheory to allow for the facts calling it an extension.Definition 2.6 Let a Brewka theory (T, B), such that B = (B1, , B,i ) . Then S =Si U .0 Sn is an extension of (.7', B) iff for all k such that 1 < k < n, S = .7"U S1 U • • • U Skis a maximal consistent subset of .7' U B1 U . • • U Bk.In case of conflicting evidence, a Brewka theory will generate multiple extensions in thesame way Theorist would. Brewka defines two notions of provability from a default theory.Strong provability corresponds to containment in all extensions (preferred subtheories),while weak provability corresponds to containment in some extensions. Boutilier (1992f)studied a notion of entailment for Brewka theories, corresponding to strong provability,that he called B-entailment. We will rename B-entailment as Strong B-entailment, anddefine Weak B-entailment as the counterpart for weak provability. We should specifyhow premises interact with a Brewka theory. We take a premiss to be a consistentsentence that should not be violated. Now extensions should contain a base set formedby the facts F together with some premiss a.Definition 2.7 Let B = (B1, . , B,i ). S = U a) U S1 U U S, is an extension of((Y. U a), B) iff for all k such that 1 < k < n, S = U a) U S1 U U Sk is a maximalconsistent subset of (F U a) U B 1 U^U Bk.Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^22Definition 2.8 0 is Brewka- Strongly entailed by a with respect to (T , B) ( writtenTUal- BS 13) iff /3 is entailed by all extensions of ((.T U a), /3).Brewka-Strong entailment corresponds to the notion of predictions.Definition 2.9 0 is Brewka-Weakly entailed by a with respect to (T, B) ( writtenF U a E-BW 0) iff 0 is entailed by some extension of ((Y. U a), B) .2.2.5 Consistency Based DiagnosisThe diagnostic task is to determine why a correctly designed system is not functioningas it was intended. Raymond Reiter's (1987) theory of diagnosis from first principlesrelies on the so called "Principle of Parsimony": If we don't know of any deviationsfrom normal behaviour, we will assume that every component is working normally. If weknow of deviations from normal behaviour, we should presume as few faults as possible.Reiter starts with a description of the system (SD) that specifies how the system normallybehaves on the assumption that all components (COMPS) are working correctly. If anobservation (OBS) is logically inconsistent with the system description, then not allcomponents can be working correctly. A diagnosis is called for. A set of componentsassumed to be functioning abnormally should explain the discrepancy. But accordingto the parsimony principle, such set of abnormal components is assumed to be minimal.The formalism assumes a predicate ab() that applies to components to denote that theyare functioning abnormally.Definition 2.10 (Reiter) A diagnosis for (SD, COMPS, OBS) is a minimal set A CCOMPS s.t. SDUOBSU{ab(c)Ic E AI U { -iab(c)Ic E COMPS — AI is consistent.The following are consequences of the definition.Proposition 2.2 (Reiter) A diagnosis exists if SDU OBS is consistent.As a result, if the observation is inconsistent with the system description then the obser-vation is not explainable.Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^23Proposition 2.3 (Reiter) A = 0 is a diagnosis (and the only diagnosis) for (SD,COMPS, OBS) if SDU OBS U{-'ab(c)Ic E COMPS} is consistent.Then, if the observation does not conflict with normal behaviour of the system, weconclude that all components are behaving correctly.Proposition 2.4 (Reiter) A is a diagnosis if for each ci E A,SDUOBSU{—iab(c)Ic E COMPS — A} ab(ci )The faulty components are determined by the normal components in COMPS—A, giventhe system description and the observation.Reiter gives the following correspondence of minimal diagnosis in default logic. Thepredicted behaviour of the system given a diagnosis is denoted by H. A set of defaultsexpresses that each component should be acting normally, unless it is inconsistent toassume so.Theorem 2.5 (Reiter) E is an extension for the default theory({ T÷ci^E COMPS} , SD U OBS) if for some diagnosis A for (SD, COMPS, OBS),such that SDUOBSU{ab(c)Ic E A} U {-iab(c)Ic E COMPS —^ H, Ede Kleer, Mackworth Reiter (dKMR) (1990) showed that when the system descriptionmodels exclusively the correct behaviour (that is, it includes no fault models nor exon-eration axioms), assuming a superset of the abnormal components in A leads also to adiagnosis, although not a minimal one. So, specifying a minimal diagnosis, all diagnoseswere automatically characterized. However, if fault models and/or exoneration axiomsare included in SD, then a superset of the abnormal components in a diagnosis may notlead to a diagnosis. de Kleer, Mackworth and Reiter (1990) proposed a more generaldefinition of a consistency based diagnosis that contemplates that the system descrip-tion may include fault models and/or exoneration axioms. A diagnosis is denoted by aconjunction of ab-literals, which explicitly indicates whether each component is normalChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^24or abnormal. The set of components COMPS is partitioned in two sets C p and Cn .D(Cp , Cn ) is defines as the conjunction:A ab(c) A A —,ab(c)]cEC,,^cEC.Definition 2.11 (dKMR) Let A CCOMPS. A diagnosis for (SD, COMPS, OBS) isD(A, COMPS — A) such that SDUOBSU{D(A, COMPS—A)} is satisfiable.This definition characterizes all diagnosis for a given observation. dKMR define a minimaldiagnosis for an observation as a diagnosis that assumes a minimal (subset related) setof abnormal components. This definition corresponds precisely to Reiter's definition ofdiagnosis (Definition 2.10).Definition 2.12 (dKMR) A diagnosis D(A, COMPS—A) is a minimal diagnosis if forno proper subset A' of A is D(A', COMPS—A') a diagnosis.They show that whenever there is a diagnosis D(A, COMPS — A), there is a minimaldiagnosis, D(A', COMPS — A'), such that A' is minimal A' C A.2.3 Belief RevisionWhen solving problems in AI we start from a representation of a problem. But such arepresentation may only be applicable if we can understand and model how to updatethe representation in light of new information. A theory governing the dynamics of thegiven representation is required. Theories of belief revision are relevant to AI addressingthis issue.We aim for a theory of explanation that is relative to a background knowledge orepistemic state of a program. Such a notion of explanation is defeasible in the sensethat as the background epistemic state changes, certain explanations may no longerhold. The epistemic state of a program or agent is expected to be in constant change,reflecting the diverse inputs from the world. Then an account of explanation respectingChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^25its defeasible nature shall be based on a theory of belief revision. Our cornerstone onexplanations will be given by the following notion: "were the explanation believed, theexplanandum should become plausible". To evaluate this conditional relative to thebackground epistemic state, some hypothetical change in belief must operate. For thesereasons we will base our account of explanation on a theory of belief revision. We willtalk about a knowledge base or a belief set indistinguishably. No differences should beascribed to our use of the terms of knowledge and belief.Different approaches have been proposed to capture the process of revising beliefs.We will concentrate in the work of AlchourrOn, Gardenfors and Makinson (AGM), whoseaccount of belief revision has been widely accepted. The AGM theory models how anideal agent or program corrects its beliefs about the world when it finds them to bemistaken. It results suitable to model hypothetical changes in belief. We will adopt it asthe underlying theory of revision in our account of explanation.Other approaches to revision have been presented in the AI literature. For example,contrasting with the AGM belief revision, which can be described as modeling changesin belief in a static world, Katsuno and Mendelzon's (1991a,b) notion of belief updatecaptures changes in belief about a changing world. In Chapter 6, we will briefly discussa counterpart notion of explanation based on update semantics as an avenue of investi-gation. Among others, Doyle's Truth Maintenance System (TMS) (1979) was pioneer inAI embedding the foundations theory of revision which keeps track of all the reasons forbelief. This approach contrasts to the coherence tradition with which the AGM theoryidentifies.2.3.1 The AGM theory of RevisionThe AGM theory (AGM 1985, Gardenfors 1988) models the dynamics of belief as gov-erned by the logic of theory change. We will follow the AGM formalization of beliefrevision in terms of belief sets, which assumes an ideal reasoner, whose beliefs are to-tally consistent and closed under logical consequence. Belief sets represent a particularChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^26belief state by a deductively closed set of sentences (we will assume the underlying logicof beliefs is CPL, but nothing crucial depends on this). An arbitrary belief set will bedenoted with K. If K is a consistent belief set, then for any sentence A only three dif-ferent epistemic attitudes concerning A can be expressed. If A E K, A is accepted orbelieved; if -A E K, A is rejected, or disbelieved; and, if A 0 K and -.A 0 K, A isindeterminate. Belief sets admit three kinds of epistemic changes: expansions, revisionsand contractions. Expansions consist in adding a new belief A (and its consequences)into K. Expansions are defined as .1-C1 = Cn(K U {A}); then, to obtain a new consistentbelief set K1 it is required that A be consistent with K.Revisions model the process of introducing in K a new belief A, that may contradictbeliefs already in K. Certain beliefs from K should be given up in order to make place forA, and maintain consistency. Following the principle of informational economy, the ideais that "as few" beliefs as possible and the "least entrenched" beliefs should be given upin order to preserve consistency. By "few" it is meant that the change in informationalcontent in theory K be minimal. The AGM theory proposes the following eight postulatesthat constrain the revised belief set.(K*1) For any sentence A and any belief set K, Ii:4 is a belief set(K*2) A E ICA(K*3) K::i C K,t(K*4) If -A 0 K, then Ifl a. K'il(K*5) KA = 1 if and only if I- -,A(K*6) If I- A ::-..-. B, then IC:i = K*13(K*7) ICA& B C (K:1 )13-(K*8) If -'B 0 KA, then (K:4 ) -{B" C K ,*4&BContractions are changes in a belief state that involve giving up some beliefs withoutincorporating new ones. Contractions model the resulting belief state after the idealagent "forgets" some information. Given a belief set K, the contraction of K by AChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^27is notated as K. In this contracted belief state the agent should not hold belief inA. When retracting a belief A from K, there may be other beliefs in K that entail A(or other beliefs that jointly entail A without separately doing so). In order to keepK -ii. closed under logical consequences, it is necessary to give up A and other beliefs aswell. The problem is to determine which beliefs should be given up and which should beretained. The AGM theory provides eight postulates (K -1) to (K-8) that characterizecontractions.(K-1) For any sentence A and any belief set K, K,T is a belief set(K-2) I-Ci C K(K-3) If A 4% K, then .K71 = K(K-4) If not I- A, then A cl K A—(K-5) If A E K, then K C (1Q)A.(K-6) If I- A .=-. B, then K -",", = IC(K-7) K,T. n xi C K;isiB(K-8) If A 0 K;is,B, then K;IszB C Kii"By the Levi identity revisions can be defined in terms of contractions and expansions:K:1 = (.K.TA )AThe Levi identity defines revisions as first pruning away all potential inconsistencies, andthen adding the new belief. The Harper identity provides a definition of contractions interms of revisions:IQ = (K n KzA )The state where we become ignorant about A is captured as what K and KZA have incommon. To abandon belief in A is just to make both A and - ,21 epistemically possible.Gardenfors et al. propose two different ways to construct a contraction function satisfying(K- 1) to (K-8). By means of the Levi identity, a revision function that satisfies (K*1) toChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^28(K*8), is automatically determined. The first approach to define a contraction functionto get K -ii form K, and a sentence A, is based on maximal subsets of K that do notentail A. KIA denotes the set of all these maximal subsets. It is assumed that there issome ordering of maximal subsets in K_LA. By means of a selection function S the mostrelevant subsets from K_LA are picked. They define a Partial Meet contraction functionas follows:Definition 2.13 (Gardenfors) IC71 = n S(K1A)The second approach to construct a contraction function to obtain K -,i is based on someordering of the sentences in K. The ordering is associated with the epistemic entrench-ment of sentences. For sentences A, B, A <EE B means that "B is at least as episte-mologically entrenched as A relative to epistemic state K". Gardenfors indicates thatthe epistemic entrenchment of a sentence is tied to its overall informational value withinthe belief set. For example, lawlike sentences generally have grater epistemic entrench-ment than accidental generalizations. When forming contractions, the sentences that areretracted are those with the lowest epistemic entrenchment. Tautologies are the mostentrenched beliefs; hence they are never given up. He proposes the following postulatesthat constrain an ordering of entrenchment.(EE1) If A <EE B and B <EE C, then A <EE C (Transitivity)(EE2) If A I- B then A <EE B (Dominance)(EE3) For any A and B, A <EE A A B or B <EE A A B (Conjunctiveness)(EE4) When K ^ K1 , A V K if A <EE B for all B (Minimality)(EE5) If B <EE A for all B, then I- A(EE1)-(EE3) imply connectivity, namely, either A <EE B or B <EE A (the epistemicentrenchment ordering will cover all the sentences).Adam Grove (1988) has given a concrete modeling for theory change in terms ofhis "system of spheres" , furnishing the AGM theory with a possible worlds semantics.Grove's system of spheres (similar to Lewis') consists in sets of possible worlds orderedChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^29concentrically. The system of spheres is ordered under inclusion. The set of worlds inthe center of the system forms the inner sphere that represents a theory of interest K.Distance to the centered sphere means departure from theory K.2.3.2 Belief Revision and Default ReasoningDefault reasoning is the process of jumping to conclusions in the presence of incompleteknowledge. It has been been commonly agreed and re-agreed that the process is non-monotonic since in light of new information, old conclusions may be no longer valid.Makinson and Gardenfors (1990, 1991), revealed the relation between skeptical defaultreasoning and belief revision. The idea is that the underlying theory being object ofrevision be interpreted as a theory of expectations (or defaults) about the world. Then,conclusions in default reasoning correspond to the revision of a theory of expectationsby the facts. Gardenfors and Makinson developed a non-monotonic inference relation,proving a unified treatment of nonmonotonic logics and belief revision. Their nonmono-tonic inference (I--) is based on a notion of "expectations". Now K represents a theoryof expectations about the world. Expectations include not only our firm beliefs, but alsothe propositions that are regarded as plausible enough to be used as a basis for inferenceas long as they don't give rise to inconsistency. Gardenfors and Makinson's thesis is:0 E IC* is translated into a l-sdif 0, and conversely.In terms of this inference relation they establish the connection with Poole's Theoristframework with respect to the process of default prediction or intersection of all extensionsof a default theory.Boutilier (1992a)(1992c) pushed the connection even further, showing that the log-ics governing belief revision and conditional default reasoning are indeed identical. Hedeveloped a family of modal conditional logics (see below) suitable for both types of rea-soning, providing a uniform semantic framework based on standard (Kripkean) models.He drew the connection between default reasoning and belief revision by defining norma-tive and subjunctive conditionals (see below) in his bimodal conditional logic CO*. TheChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^30subjunctive conditional, via the Ramsey test, characterizes AGM revisions, while defaultrules of the form "A normally implies B" are modeled as normative conditionals A B.Boutilier showed the two conditionals to be the same, and how default reasoning can beviewed as a special case of belief revision.2.4 Modal and Conditional LogicsConditionals have the form "If A were the case, then B would be the case" or "If A is thecase, then B is (will be) the case" , where A may or may not contradict our knowledge orbeliefs. Conditional logics were initially developed for modeling "if ... then" statementsin natural language. Robert Stalnaker (1968) gives a possible worlds semantics for hisconditional logic. The subjunctive conditional A > B, is read as "if A were true B wouldbe true" . Stalnaker's conditional is non-transitive (from A > B and B > C one cannot infer A > C), hence, it does not satisfy the strengthening rule (from A > B onecan not infer A A C > B). And it does not satisfy the contraposition rule (from A > Bone can not infer --,B > --IA). These qualities make the conditional connective suitablefor subjunctive reasoning. For instance, we accept the conditional "If this match werestruck, it would light" , while we deny that "If this match were wet and struck, it wouldlight" . Stalnaker gives the following "recipe" based on the Ramsey test to evaluate aconditional in a given state of belief:"First, add the antecedent (hypothetically) to your stock of beliefs; second, makewhatever adjustments are required to maintain consistency (without modifyingthe hypothetical belief in the antecedent); finally, consider whether or not theconsequent is then true." (Stalnaker 1968, page 44)The connection between belief changes and conditional sentences is given by the Ramseytest. A conditional A > B is accepted in an epstemic state K if B is accepted inthe revision of K by A. This connection is foundational in our conditional theory ofexplanation.David Lewis (1973) proposes a conditional theory of counterfactuals (differing in someaspects to Stalnaker's), giving a possible worlds semantics based on a "system of spheres" .Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^31Any particular sphere around a world w contains the worlds that resemble to w at least toa certain degree, and, of course, ties are permitted. The system is nested, in that for anytwo spheres around w, one is included in the other. Lewis provides the following truthcondition for his "would" counterfactual conditional relative to the system of spheresaround a world w. A > B is true at w if and only if either (a) no A-world belongs to anysphere, or (b) some sphere S contains at least one A-world, and A D B holds at everyworld in S. Then, A > B is non-vacuously true at w if some world accessible to w inwhich A and B hold resembles to w more than any other world satisfying A and —43.Lewis also defines a "might" counterfactual in terms of his "would" counterfactual, asA -,--> C =df --i(A > —, C). The truth condition for the might-conditional, relative to thesystem of spheres around a world w, is as follows. A -'-b C is true at w if and only if someA-world belong to some sphere, and every sphere S that contains at least one A-world,contains at least one world where A A B holds. If the "would" counterfactual A > B isnon-vacuously true, then the "might" counterfactual A -,- B is also true. If A > B andA > —43 are both false, then A -•-+ B and A -,- —43 are both true. However, when A > Bis false, but A > —113 is true, then B holds at none of the closest A-worlds, hence A -,-> Bis false. Finally, if there are no A-worlds, the conditional A ,,-4 B is also false.Matthew Ginsberg (1986) discussed the role of counterfactuals in AI, describing howapplications like planning and automated diagnosis can be modeled via counterfactualreasoning.2.4.1 Boutilier's Logics as Calculus for Default Reasoning and Belief Revi-sionWe will focus on two of Boutilier's logics, CT4O and CO. These logics, suitable forrevision and default reasoning, possess a possible worlds semantics based on standardmodels (Kripke models). CT4O and CO are based on a bimodal language LB, with themodal operators ^ for truth at accessible worlds, and b for truth at inaccessible worlds.The following connectives are defined in terms of ^ and b: Oa - -df —,0—,a; :5 -dfChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^32-'b-ia; -=df pa A ba; O =df <>a V '<5.a. Oa is true at a world iff a holds at someaccessible world; 4.5a is true at a world iff a holds at some inaccessible world; ba holds iffa holds at all worlds. Oa holds iff a holds at some worlds. Notice that the connectivesO and express global statements in a model.We will use extensively the term cluster to indicate a maximal set of mutually acces-sible worlds. The following is a general definition of a cluster that applies to any reflexiveand transitive model.Definition 2.14 Given any model M (W, R, co), for which R is reflexive and transitivea cluster is defined to be a subset U C W such that each member of U is mutuallyaccessible (i.e. if u, v E U, then uRv and vRu), and no proper superset has this property.The logic CT4O characterizes the class of models where R induces a partially orderedset of clusters of mutually accessible worlds (S4 structures).Definition 2.15 (Boutilier) A CT4O-model is a triple M^(W, R, co) where W isa set of worlds with valuation function ( 02 and R is a reflexive and transitive binaryaccessibility relation over W. Satisfaction is defined in the usual way, with the truth ofa modal formula at a world defined as: K, Oa iff for each v such that wRv, M kt, aand M iff for each v such that not wRv, M a.Definition 2.16 (Boutilier) The conditional logic CT4O is the smallest SC LB suchthat S contains CPL (and its substitution instances) and the following axiom schemata,and is closed under the following rules of inference:K ^(A D B) D (^A D ^B)K' b(A D B) D (SA ^ bB)T DA D A4 OA D ^^AH^A bB) D b(A V B)Nes From A infer tIA.MP From A D B and A infer B.Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^33Provability and derivability are defined in the standard fashion, in terms of theoremhood.Theorem 2.6 (Boutilier) 1-cT4o a if CT40 a•In many circumstances we want to ensure that all logically possible worlds are taken intoconsideration. The logic CT4O* characterizes such full models.Definition 2.17 (Boutilier) CT4O* is the smallest extension of CT4O containing in-stances of the following axiom: LP^for all satisfiable propositional a.Theorem 2.7 (Boutilier) 1-cT4o- a iff CT40* a.The other logic that we are interested in is CO which characterizes structures consistingof a totally ordered set of clusters of mutually accessible worlds (S4.3 structures).Definition 2.18 (Boutilier) A CO -model is a triple M = (W, R, co) where W is a setof worlds with valuation function (,o and R is a transitive and connected (transitivity andconnectivity imply reflexivity) accessibility relation over W.The conditional logic CO is the smallest S C LB such that S contains CPL (and itssubstitution instances) and the following axiom schemata K, K', T, 4, H andS A D b0,4and is closed under the rules of inference Nes and MP. Provability and derivability aredefined in the standard fashion, in terms of theoremhood.Theorem 2.8 (Boutilier) I-co a if lco a.The logic CO* is based on full CO-models. CO* is the smallest extension of CO containinginstances of the axiom LP. CO* is also sound and complete.We should notice that CO models are a special case of CT4O models. The differencebetween the two lies in that the accessibility relation in CT4O models is transitive andreflexive, while in CO it also requires to be connected. A CT4O-model is formed by aMorePlausibleChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^34Figure 2.1: A CO-model (left) and a CT4O-model (right).lattice of clusters, a CO-model by a unique "chain" of clusters. Figure 2.1 shows a COand a CT4O model.Revision Models and Models of NormalityBoutilier (1992a)(1992c) demonstrated that the formal processes of belief revision anddefault reasoning are governed by the same logic. But he showed that practical consid-erations distinguish the two types of reasoning. He captured the difference between thetwo with a different interpretation on the accessibility relation R among possible worlds.In models for default reasoning, worlds or states of affairs have a fixed ordering accordingto a measure of normality, or typicality. The accessibility relation R is interpreted asfollows: world v is accessible to world w if and only if v is at least as normal a w.In models for revision, worlds are ordered respecting a plausibility measure relative toa belief set K that will be the object of revision. Boutilier defines models for revision byimposing an interpretation on accessibility relation R over possible worlds as a measureof closeness to theory K, or plausibility with respect to theory K. Plausibility reflectsthe degree to which one would accept w as a possible state of affairs given that belief inChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^35K may have to be given up. R is defined as follows: wRv iff v is as plausible as w giventheory K. v is more plausible than w iff wRv but not vRw. R is required to be reflexive,since every world is as plausible as itself, and transitive, since if w is as plausible as v,and v is as plausible as u, then w is as plausible as u. In some cases R is required to beconnected, namely, all worlds be comparable in terms of plausibility (either wRv or wRvfor all w, v). CT4O-models seem appropriate for revision; however, in order to use them,the theory K should be adequately represented. Boutilier achieves this by insisting thatthose worlds consistent with K should be exactly those minimal in R. That is,vRw for all v E W if and only if M KThis condition ensures that no world is more plausible than any other world consistentwith K, and that all K-worlds are equally plausible. Models that satisfy this constraintare called K -revision models. If we let IIKII to denote the set of worlds satisfying eachformula in K, a model M is a K-revision model if and only if IIKII forms a minimal clusterat the bottom of the model. Boutilier states this constraint in the bimodal language LB,in the case of CO-models, for any K that is finitely expressible as KB as:O(KB) d(KB D (^KB A b--,KB))This ensures that any KB-world sees every other KB-world (b—KB), and that it seesonly KB-worlds (^KB). The sentence O(KB) is intended to mean we "only know" KB(Levesque).Let K = Cn(K B), such that KB = B} . Figure 2.2 shows a K-revision model.The minimal cluster satisfies B; hence, A is rejected in K, B is accepted in K, whileC is just considered epistemically possible.We will work with two versions of K-revision models, differing in the properties ofthe accessibility relation. If the accessibility relation is just reflexive and transitive,Boutilier denotes them preorder revision-models. In contrast, if in addition the acces-sibility relation is totally connected, the models are called total order revision-models.The difference between the two is simply that in total-order revision models every pairChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^36all and only^'A B CK-worlds lli WICFigure 2.2: K-revision modelof worlds are comparable with respect to plausibility or closeness to theory K, while inpreorder revision-models, some worlds may be incomparable. Full models (all proposi-tional valuations are represented) should be considered in order to allow every consistentsentence be capable of generating a consistent revision (this relates to the AGM postu-late K-5, see below). Full total-order revision models are CO* models, and full preorderrevision-models are CT4O* models. Boutilier defines a modality for belief. The modal-ity B is defined equivalently in CT4O and CO (although in CO it can have a simplerdefinition):Ba a-df dO^aBa is read as a is believed (or accepted) in K. The definition says that every world inthe model should regard possible that a is true at all accessible worlds. This is the casewhen a holds at every world in the minimal clusters.Boutilier defines the plausibility of a proposition relative to a revision-model M. Aproposition A is at least as plausible as B when for every B-world w there is some Aworld that is at least as plausible as w.Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^37Definition 2.19 (Boutilier) Let M a CT4O-model. A is at least as plausible as B incontext of M (written A < B) if and only if M II(B D 0A).Proposition A is more plausible than B just when A < B and not B < A. When inter-preting the accessibility relation R as an ordering of normality among possible worlds,A < B may reflect a comparative measure of normality. The notion of plausibilitynormality will be used extensively in our account of explanations.We are ready to introduce the conditional connective In models for revision thisconnective will be used to represent and reason about subjunctives and revision policies.The connective^is defined equivalently in the two logics, CT4O and CO.Definition 2.20 (Boutilier) A B^V 0.(A A ^(A D B)))The conditional A B (in a model M) says that for every world w, either w has noaccess to any A-world, or there is some A-world v accessible to w such that for everyworld u accessible to v, H t, A D B holds. Notice that has a "global" nature, or inother words, the truth of the conditional is not defined relative to a particular world, butrelative to the whole model.Referring to figure 2.1, let's call M 1 to the CO-model (on the left) and M2 to theCT4O-model (on the right). In model M1 there is a unique R-minimal cluster of A-worlds. In contrast, in model M2 there are two R-minimal clusters of A-worlds. In bothmodels satisfaction of the conditional A B occurs since B holds at each of the mostplausible (R-minimal) A-worlds.Now we can see how Boutilier captures AGM revision. Let a M be a K-revisionmodel. When revising K by A, we adopt as representative of the revised belief set K: tthe set P/(A), of most plausible A-worlds in M. Using the Ramsey test for acceptanceof conditionals B E ICA is equated with M = A B, both capturing that B is trueat each of the most plausible A-worlds. Given the Ramsey test, is nothing morethan a subjunctive conditional, interpreted as "If K were revised by A, then B would bebelieved". For any propositional A E LCPL, the belief set resulting from revision of K byA is:Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^38IC;1 = {B E LcpL : M A B}In the model of figure 2.2 the conditional M A -,B holds, meaning that -,B wouldbe accepted as a result of revising K by A. The belief set KA is characterized by the twoclusters in the top of the model. Notice that M A C, which says that if we reviseK by A, C will not become accepted.Boutilier demonstrates that the revision function determined by a full total-orderrevision-model satisfies the eight AGM postulates for revision (K*1 - K*8), while therevision function determined by a preorder revision-model satisfies K*1 - K*7.Let's see the semantic correspondence of AGM contraction in K-revision models. Leta belief set K such that A is rejected (namely, --,A is accepted). To contract belief in--iil implies to give A a possibility; that is, to move into an epistemic state in which Ais epistemically possible. The belief set resulting for contracting K by -IA is determinedby the set of worlds IIKII U P1(A). In the model of figure 2.2 the belief set KI:A ischaracterized by three clusters, the minimal cluster together with the two clusters in thetop of the model. Notice that the proposition (B D C) is accepted in K_TA .We will present now another of Boutilier's conditionals, that we will notate as —>.This conditional has also a global nature but expresses a weaker notion than . A —> Ccaptures the idea that "at some set of equally most plausible states of affairs where Aholds, C holds as well". The conditional —> is defined as follows, in both logics, COand CT4O.Definition 2.21 (Boutilier) A --> C - cif tj -,A V 46(A A DO D C))The sentence A —> C says that either -IA holds universally, or there is some A-worldw such that for every world v accessible to w, k u A D C holds. Then, the conditionalA —> C holds in a CT4O-model whenever C holds at least at one of the R-minimalclusters of A-worlds. However, in a CO-model, since clusters of worlds are totally ordered,there can only be a unique R-minimal cluster of A-worlds. Then A —> C will besatisfied in a CO-model, whenever C holds at the R-minimal cluster of A-worlds. ButChapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^39this is precisely the same requirement for satisfaction of the stronger conditional A^C.Consequently the two connectives,^and —>, become equivalent in CO-models, as thefollowing proposition shows.Proposition 2.9 (Boutilier) 1- COA--C_ACBoutilier (1990)(1992a) observed that this weak conditional connective is paraconsis-tent in CT4O-models. Since it is possible to assert A —> C and A —> --,C whileA 7i—* (C A -, C); that is, without A entailing an inconsistency. The CT4O-model in fig-ure 2.1 satisfies both A ---> C and A ------> -IC, while the CO-model satisfies neither. Ina CO-models the conditional —+ does not behave paraconsistently since it just becomesequivalent to the stronger connective =, hence loosing its intended meaning.According to the interpretation of the accessibility relation in terms of normality, thereading of the conditional A B is stated as "in the most normal situations in whichA holds, B holds as well", or "A normally implies B". Default rules like "birds fly" and"penguins don't fly" are naturally expressed as bird fly and penguin --1 f ly. . Thenonmonotonicity of default reasoning is nicely captured, since these conditional defaultrules are exception allowing. Boutilier shows how skeptical default reasoning can beviewed as the revision of a theory of expectations (defaults) by the facts.In the next chapters we will only be concerned with CO and CT4O models thatsatisfy the so-called Limit Assumption. This assumption states that in each model thereexists some minimal A-world for any proposition A. Pictorially, we can say that modelsthat satisfy the Limit Assumption have are "bottommed"; that is, they have a set ofminimal clusters.' The following propositions will be of use in many of the proofs of thenext chapters. The propositions describe truth conditions for conditionals A B andA ----> B relative to CT4O-models that satisfy the Limit Assumption.Proposition 2.10 Let M = (W, R, 0 a CT40 well founded model (R is transitive andreflexive, and satisfies the Limit Assumption). M A B if every minimal A-clusterin M satisfies B.2 The Limit Assumption is discussed in detail in Lewis (1973) and Boutilier (1992a).Chapter 2. Prelude on Explanations, Belief Revision and Conditional Logic^40Proposition 2.11 Let M = (W, R, (p) a CT4O well founded model (R is transitive andreflexive, and satisfies the Limit Assumption). M = A ---+ B if either there are nominimal A-clusters, or there is a minimal A-cluster in M that satisfies B.The two conditional connectives^and ---4 will be used as connectives for explanationin our model of abduction.Chapter 3Epistemic ExplanationsWhy would Fred contract AIDS? Compare the following two explanatory answers. 1 ByFred's practicing unsafe sex. By Fred's being exposed to the HIV virus. The secondanswer has a predictive nature. If we believed that Fred was exposed to the virus, wewould predict that Fred contracted AIDS. The first explanation is not predictive, sinceeven though it may be somewhat probable that Fred contracted AIDS, practicing unsafesex is not enough of a reason for us to believe that Fred actually contracted AIDS. Itcould have perfectly been the case that the persons that Fred had met were not infectedwith the virus. We will just say that Fred might have contracted AIDS. Based on thisdistinction we will differentiate predictive explanations from non-predictive ones.Our modeling of explanation assumes an ideal agent or program, which is logicallyomniscient and perfectly consistent, inconsistency being an a intolerable state for it. LetK be a deductively closed set of objective beliefs representing knowledge or beliefs' aboutthe world held by the agent. We also expect some conditional beliefs (and maybe someother preferences too) that constrain the manner in which the agent is willing to reviseits beliefs. These are revision policies, subjunctive conditionals, of the form "If the agentwere to believe in A, then it would believe in B."We assume the agent will be confronted with explanation-seeking- "why" questions,for which it would give explanations relative to its epistemic state K. Namely, we aremodeling external inquiries that "consult" the agent's credences. We will attempt toexplain two kinds of objective sentences, beliefs and non-beliefs. 3 We will generically use'Thanks to David Poole and Craig Boutilier for proposing and analyzing this example.'For the purpose of this thesis we will consider belief and knowledge as interchangeable concepts.'As future work we contemplate explaining conditional statements. For example ("The Little Prince"page 53), "Why would an explorer who told lies bring disaster on the books of the geographer ?" We41Chapter 3. Epistemic Explanations^ 42the word explanandum and sometimes observation to refer to the object of inquiry. Wewill use the greek letter 0 to denote a generic explanandum or observation, and a willrefer to an explanation for 13. Through this chapter will assume a, i3 E LcpL.Along with the idealizations of our modeling, we will assume that did the agent learna new piece of information, it would automatically incorporate some explanation for it (atworst, a disjunction of reasons, or the trivial explanation). Such an explanation wouldarise from the closure of its beliefs together with the newly incorporated knowledge. Itmay not be a "single" reason, but a disjunction of possible reasons. The request toexplain 13 is interpreted by the agent as "Why do/would 0 be true, based on what Iknow?" Then, if 13 was already accepted in the epistemic state, whatever reason for #already incorporated in the epistemic state should be an explanation for /3. Then, weargue that when the agent receives an inquiry about an explanandum that it believestrue, an explanation should also be believed true. Namely,"Were the object of inquiry already believed, an explanation for it would be believed too."The following condition reflects our commitment.(Commit) if 0 E K then a E KAs Boutilier has pointed out4 , this view is not tenable for scientific inquiry, where obser-vations are believed, but explanations are yet unknown. The explanations to be studiedin this chapter are based on this commitment. A notion of scientific explanation may bemodeled by denying it.We will study with two notions of explanation: predictive and non-predictive.3.1 Predictive ExplanationsPredictive explanations render necessary the explanandum. This is a strong notion ofan explanation: belief in the explanation will induce belief in the explanandum. Thealso contemplate conditional statements being an explanation. See Chapter 6.4 Personal communication.Chapter 3. Epistemic Explanations^ 43slogan will be Were the explanation believed, so too would the explanandum. A numberof conditions follow, defining when a explains /3, relative to a background epistemic stateK, where the inquiry arises. The explanandum /3 may either be rejected, indeterminateor accepted in K. According to Commit, if 0 is an observation that is already acceptedin K, an explanation a should also be accepted in K. The agent must have incorporatedsome reason along with the observation; if modeling the physical world, an actual causemay account for the observation.Imagine now /3 rejected in K, that is -'/3 E K. We seek an explanation a, such thata predictively accounts for 0. We argue that a should necessarily be rejected in K aswell. Otherwise, were a accepted or indeterminate, any a-world in K would still satisfy-,0 (since 0 is rejected). Then, a would hardly make sense as a predictive explanationfor 0.Finally, suppose 0 indeterminate in K. Were a rejected in K, then in every epistem-ically possible world where /3 holds, a would be absent, hence a would not be accountingthe possibility of 0. If a were accepted while /3 is not (0 is actually indeterminate),how can a "predict" /3? We conclude that a should be indeterminate in K. Hence, wepropose:"The object of inquiry and the explanation should have the same epistemic status in K".We translate the above statement into the following condition:(EpStatus) a, /3 E K; or -la, 73 E K; or a, -'a, g,-,0 0 KBut obviously EpStatus is not enough. Even though we may disbelieve both, that thegrass is wet and that Fred is a drug-addict, one does not explain the other. We need torefer to some "connection" between a and 0. Reflecting our predictive desideratum, wepropose:"Were the explanation believed, the explanandum would be believed too".Chapter 3. Epistemic Explanations^ 44The idea is that at all most plausible a-worlds, /3 should also hold; for otherwise, a wouldnot predictively account for 0.(Predict) 0 E K:However, once we have adopted EpStatus, if /3 is already accepted in K, Predict dilutes orbecomes automatically satisfied by considering any arbitrary belief. To evaluate Predictnon-trivially, we should hypothetically suspend belief in the explanandum, moving intoan epistemic state where /3 is not accepted. This hypothetical state is K. From theAGM contraction postulates, we know that if /3 0 K, then G = K, then we canre-express Predict as follows,(Predict') /3 E (Kin:i.e., we hypothetically suspend belief in /3 and ask "What would "cause" its belief?" Ifa fails to satisfy Predict', then clearly, a can not be a predictive explanation for /3.Consider now the following situation. Suppose we believed Fred was infected withthe HIV virus. This would predictively explain Fred having AIDS. Had we believed thatFred did not have AIDS, we would have positively believed that Fred was not exposed tothe HIV virus. We propose a third condition on predictive explanations, that we phraseas follows:"Had the observation been absent, the explanation would be absent too".Candidate hypotheses violating this condition clearly fail to be explanations. For in-stance, the fact the the grass is wet does not explain that Fred is in love. Since evenif the grass were not wet, our belief about Fred being enamored would remain. We ar-gue, then, that the wet grass does not explain Fred's being in love. We can express ourproposed condition as:(Absent)^ —,a E Ki,'0Chapter 3. Epistemic Explanations^ 45Absent requires an explanation to be rejected in those "closest" states of affairs where theobservation is rejected. Otherwise, if a were accepted in some states of affairs where -1,3holds, such an explanation would also be accounting for the negation of the observation,so it would be deprived of its predictive explanatory power. Unfortunately, if the objectinquiry is disbelieved (i.e. -'/3 E K), Condition Absent becomes automatically satisfied,once we accept EpStatus. The truth of Absent can be non-trivially tested in an epistemicstate where we suspend belief in the explanation. That is, by hypothetically moving to the"closest" states of affairs where the potential explanation is indeterminate (epistemicallypossible). This state is From K_Ta we should evaluate whether disbelief in theobservation induces disbelief in the explanation. Again, from the AGM postulates forcontractions, we know that if K then Ka = K. So we can re-express Absent as:(Absent') E (K=„„)!,0So far we have proposed EpStatus, Predict', and Absent' as three necessary conditionsto determine when a sentence a explains an explanandum /3.We will now present logical counterparts of the conditions described above usingBoutilier's logic CT4O. We will assume a plausibility ordering over possible worlds, in-duced by the agent's objective belief set K, together with its revision policies and possiblyother preferences too. We will assume the existence of a K-revision model capturing theordering. As we discussed in Section 2.4.1, via the Ramsey test, revision policies are justsubjunctive conditionals of the form A B and plausibility comparisons can have theform C < D. We will work with two versions of the plausibility ordering, one determininga preorder revision model, and the other a total order revision model (see Section 2.4.1).Unless specified, we will consider indifferent whether the underlying model is a preorderor total order revision-model.We should notice that, in general, there are multiple admissible orderings among pos-sible worlds. As shown by Boutilier, a fixed ordering worlds reflecting an ordering ofnormality identifies the epistemic state K with a theory of expectations. Models basedon this fixed ordering of normality are suitable for default reasoning. The counterpartChapter 3. Epistemic Explanations^ 46explanations arising from these models will be the object of study in the next two chap-ters.Let's assume a K-revision model M. Condition Commit is easily formulated usingBoutilier's modality for belief B,(3.1)^M 13 /3 D Baand condition EpStatus as,(3.2)^M (Ba a 1313) A (B-la a B-0)Predict' sanctions that /3 should be accepted in the belief state resulting from the revisionof (K -g) by a. This complicates matters since in order to capture revisions over thisepistemic state, the corresponding model Mi suitable for revision of G has to be defined.While the semantic model of AGM contraction constrains the ordering of possible worldsin the contracted state, it fails to provide a new ordering. Let's leave AV underspecified,taking it as any model such that the worlds in G form the minimal cluster. 5 Followingthe Ramsey test, Predict' is translated as(3.3)^Mi3- Hcx^/3Let's recall that we needed to evaluate Predict with respect to IC in order to avoidautomatic satisfaction when /3 was already accepted in K. Let's start from /3 E K, andassume EpStatus is satisfied; hence, a E K. The belief set G contains all K-worldstogether with all most plausible -0-worlds in M. Then, since each K-world was an a-world, -'a cl K. Then, revising G by a is just a consistent revision (or an expansion),selecting the a-worlds from G. (3 belongs to (K/3- ): if and only if none of the a-worldsis a -0-world. This will only be the case if and only if each of the "closest" -0-worlds inM is -1a-world. But this is exactly what Condition Absent tests for, namely, -la E K!,,3We have just proved:5 Boutilier's (1992e) work on "natural revision models" extends the AGM theory of revision.Boutilier's natural revision function allows for iterated revisions, preserving a maximum conditionalinformation. The models M:4, and Mi for K''f;, K_,-0 respectively, are fully defined and subsequentrevisions and contractions become possible to calculate.Chapter 3. Epistemic Explanations^ 47Proposition 3.1 Let a, 3 E K . Then, /3 E (IC): if -,a E IC,',3 .This proposition has a crucial consequence. It says that whenever the explanandum isalready believed, non trivial testing of Predict is equivalent to testing Condition Absent.As a result, we can discard equation 3.3. We will keep a formulation of Predict(3.4) Ma,13A similar situation holds for Absent. In order to test it non-trivially it should be evaluatedwith respect to K= a ; that is, we should test whether -,a E (K;(,) *_93 . Again we confrontthe problem that in order to calculate revisions of K::„, the model Ma is underdefined.Following the Ramsey test, Absent' is translated as(3.5) M..:,, k -'/3 -'aAs with condition Predict, we can show that we can get away without defining M.Assume 73 E K. By EpStatus -'a E K as well. The set If_.,, consists of all K-worldstogether with the most plausible a-worlds in M. As a result, it is guaranteed that/3 ft K:;a . Now, revising .K:Ta by 73 is just a consistent revision (or an expansion);(K=c,)*_,0 is formed by the -, 13 worlds in K=0,. Evaluating Absent is just to test whethersuch -'/3-worlds are -,a worlds. This would be the case if and only if none of the mostplausible a-worlds in M are 73 worlds; in other words, each of the most plausible a-worlds should be a /3-world. But this is precisely what Predict states. Thus, we haveproved the following proposition:Proposition 3.2 Let -1°1, -1,3 E K. Then, a E (K_;,)!93 if M = a /3.Then, we just express Absent:(3.6) M -, 13 --TaGiven propositions 3.1 and 3.2, if Conditions EpStatus, Predict and Absent are satisfied,so are Predict' and Absent'. This allows for a pretty simple definition of predictiveexplanation, just relative to the K-revision model M.Chapter 3. Epistemic Explanations^ 48Definition 3.1 Let a, /3 E LcpL. a is a predictive explanation for /3 relative to K if(i) M = (Ba -. BO) A (B-'a .a B-0); (ii) M a^/1; and (iii) M = -0^-'a.MorePlausibleFigure 3.3: Total-order revision model for the rain-sprinkler example, where "rain" and"sprinkler" are rejected in K.Consider the following example. Suppose we know that "if it rained the grass wouldbe wet. So would be the case if the sprinkler had been on". In addition we know that the"sprinkler" and "rain" are mutually exclusive conditions, since we live in an area wherepeople do not water in the rain. Suppose we know that presently "the grass is wet",and being in winter Vancouver, "rain" is more plausible than "sprinkler". Let's denote"sprinkler", "rain", and "wet-grass" with the lower-case letters s, r, w, respectively. Werepresent the above knowledge as KB = {-qv, -'r, -, s} and the conditionals s w,r^w, r^-is and s^-'r and the plausibility statement r < s. Figure 3.3 shows acorresponding K-revision model. Even though the grass is not wet, we may question,Chapter 3. Epistemic Explanations^ 49"Why would the grass get wet?" "Rain" is a predictive explanation for "wet-grass", andso is "sprinkler". Notice that in the model r, s and w are all rejected in K (hence, theyhave the same epistemic status) and r w, s w, and triviallyAlso, r A s explains w, and r V s explains w.According to Propositions 3.1 and 3.2, for the cases E K and -0 E K, we just needto test only one of conditions Predict or Absent, the other being trivial. We can showthat when is indeterminate in K the same simplification holds.Proposition 3.3 Let a be a predictive explanation for such that a is indeterminatein K. Then, Predict and Absent are equivalent.We will now examine some extra conditions on explanations that may be of interest.Once we have identified a predictive explanation, we may want to determine whether itcovers all the most plausible situations where the explanandum arises. We propose:"Had the explanation been absent, the observation would have been absent as well".This condition can be expressed as:(Cover) ECover can be seen as the requirement that the explanation cover all possible hypothesesthat could account for the explanandum. As it stands, Cover trivially holds when theexplanation and explanandum are rejected in K. Therefore, non-trivial evaluation ofit requires us to move into an hypothetical epistemic state where the explanandum isindeterminate, K73 . Again, we know that K170 = K when -0 0 K, and Cover can bere-expressed as:(Cover') EVia the Ramsey test we formulate Cover' as(3.7)Chapter 3. Epistemic Explanations^ 50It is interesting to notice what it means for an explanation a to fail to obey to Cover.Such a situation arises if at some of the most plausible states of affairs where 0 holds,a does not. This may tell us that either there is another explanation accounting for /3when a fails to do so.Figure 3.4: Revision model for the rain-sprinkler example, where "rain" is accepted inK.Let's see it with one example. Assume again the situation of our previous rain-sprinkler example, but suppose that it is presently raining. We have KB = {w, r, -is},the conditionals s w, r w, r -is and s -,r, and the plausibility statementr < s. Figure 3.4 shows a corresponding K-revision model. Then, "rain" is a predictiveexplanation for "wet-grass" (r, w are accepted in K, r w, and -'w -ir). However,"rain" fails to cover all possible reasons for "wet-grass", for instance "sprinkler" couldChapter 3. Epistemic Explanations^ 51also be a candidate. Therefore, "rain" is not a covering (predictive) explanation for "wet-grass" , since even if it didn't rain, the grass could have been wet anyway. This is preciselyindicated by -ir 0 -rw. A predictive explanation a may fail the covering condition if ais too specific an instance of an actual explanation that would fully account for the ex-planandum. Imagine an explanation conjoined with any irrelevant detail, that by chancehappens to be true. For example, "hepatitis would fully account for jaundice", while"hepatitis_and_wet_grass" is an irrelevant coincidence. At the most plausible situationswhere the conjunction "hepatitis_and_wet_grass" does not hold we expect "hepatitis" stillbe true. Then, "jaundice" is perfectly consistent with the situations where the conjunc-tion "hepatitis_and_wet_grass" does not hold. We return to this in Section 3.4.2.Shortly, we will see that Cover is very closely related to the following condition, whichwe name Correl that checks for the correlation between the explanation and explanan-dum. Let's recall that Predict demands that whenever an explanation a holds, /3 shouldhold. a and 3 are correlated, if, in addition, whenever p holds a holds as well. Wepropose,"Were the explanandum believed, so too would the explanation".This can be expressed as:(Correl) a E igiAs can be expected, Correl is trivial for inquiries that are already in K. Non-trivialevaluation of it should be performed from the epistemic state where the explanation isindeterminate, i.e. K- a. When a ft K, K; = K; then, we reformulate Correl as(Correl') a E (K;)73We express Correl' as(3.8)^ M; )3 aWith similar reasoning used to relate Predict' and Absent', we can relate Cover' andCorrel'.Chapter 3. Epistemic Explanations^ 52Proposition 3.4 Let a be a predictive explanation for f3, such that -/3 E K. Then,E (K:r3 )% iff M^a.Proposition 3.5 Let a be a predictive explanation for 13, such that /3 E K. Then,a E (1(;)75 iff MProposition 3.6 Let a be a predictive explanation for 13, such that /3 is indeterminatein K. Then, Correl and Cover are equivalent.We can give the following definition of a "covering" explanation.Definition 3.2 a is a covering explanation for /3 iff (i) a is a predictive explanation for/3; (ii) M^a; and (iii) MCovering explanations are really strong. They give all possible reasons that predict theexplanandum.By weakening Condition EpStatus into Commit, we can give an alternative definitionof an explanation, that we will call quasi -predictive. As we can expect, quasi-predictive ex-planations are intimately related to their predictive cousins. But we will see later, that thequasi-predictive notion will accommodate explanation that will not be preferred. Quasi-predictive explanations satisfy Commit, Predict and Absent (that is, expressions 3.1, 3.4and 3.6).Definition 3.3 a is a quasi -predictive explanation for /3 relative to K iff (i) MBa; (ii) M^/3; and (iii) M^-113Let's use our rain-sprinkler example to illustrate a quasi-predictive explanation. Sup-pose now that we positively know that it did not rain. But we don't know whether thegrass is wet, nor whether the sprinkler is on. Then KB = {-"r}, and s w, r w,r —is and s —Ir. Notice that we have to give up the plausibility statement r < s.Figure 3.5 shows the corresponding K-revision model. "Rain" is a quasi-predictive ex-planation for wet grass. But not a predictive one, since "rain" is considered epistemicallyimpossible while "wet grass" is not. In contrast, "sprinkler" is a predictive explanationfor "wet grass" ( "sprinkler" and "wet grass" have the same epistemic status).Chapter 3. Epistemic Explanations^ 53Figure 3.5: Revision model for the rain -sprinkler example, where "rain" is rejected in K.3.2 Non-Predictive ExplanationsIn this section we will concentrate in non-predictive explanations, capturing the notionthat an explanation might yield the explanandum. We will call them "might" explana-tions. In defining them, we will keep our commitment to Condition Commit which assuresthat if the object of inquiry is already believed, an explanation should also be believed."Might" explanations are not predictive. Here is an example. As we illustrated before,if we ask: "Why might Fred contract AIDS?" The answer: "Fred practicing unsafe sex"is just a "might" explanation. The notion asserts that an explanation is consistent withthe explanandum; that is, it mkes it possible. "Might"-explanations can be associatedwith the idea of excuses: believing in the excuse may not be sufficient to induce beliefin the explanandum. Excuses just render the explanandum possible. This idea will turnout to be related with consistency based diagnosis, where some components assumed tobe abnormal make the unexpected observation possible.Chapter 3. Epistemic Explanations^ 54Capturing the notion of "might" explanations we propose,"Were an explanation believed, the explanandum might be believed"This says the explanandum should be regarded possible once we accept an explanation.The following condition reflects this consistency notion of "might" explanations.(Might)As expected, if is already epistemically possible (i.e., accepted or indeterminate), anyarbitrary belief a satisfies Might. However, it is not clear how to avoid this triviality, orwhether it makes any sense to ask for a "might" explanation of something we alreadyconsider possible. This also points the weak character of "might" explanations. Might isexpressed as:(3.9)^ M 6 a 73We give the following definition of "might" explanations.Definition 3.4 a is a might explanation for if (i) M^D Ba; and (ii) M a -O.Let's contrast a "might"-explanation with a non-explanation. Believing in a "might"-explanation should make the explanandum at least somewhat possible; then, a non-explanation should make the explanandum impossible. That is, a is a non-explanation ifaFinally, we introduce another kind of non-predictive explanation. Consider this example.Fred wants to discolour his T-shirt. He bought a new bleaching product thatonly works in hot water. Fred is about to do his laundry, and he recalls that theplumbing has just been under repair, so the water may not be hot enough. WereFred to wash his T-shirt with the product, it might not discolour. However, it isequally plausible to say, that were Fred to wash his T-shirt with the new product,it might discolour.These are a special kind of "might" explanations. They capture the idea that in someset of equally plausible situations, the explanation accounts for the explanandum. UsingMorePlausibleVChapter 3. Epistemic Explanations^ 55the product explains in this sense a discoloured T-shirt, since in all of the most normalsituations where Fred uses the bleaching liquid and the water is not too cool, the T-shirtgets bleached. However, using the product also explains a non-bleached T-shirt, since inall of the most normal situations where the bleaching liquid is in cold water, we expectno bleaching power. We will call these explanations "weak" explanations. In order toshape them in a logical calculus, we are required to think in terms of preorder-revisionmodels (CT4O models). These models allow us to reason about incomparable scenariosmodeled as different sets of plausible states of affairs. The weak conditional connective—i in CT4O can be used to map weak-explanations.Definition 3.5 a is a weak explanation for 0 iff (i) M^BO D Ba; (ii) M^B -,a DB-10; and, (iii) M a —+ 0.Figure 3.6: Preorder-revision model for the bleaching-T-shirt example.Let's analyze Fred's bleaching-problem. We know that "if the bleaching product isused in hot water, the T-shirt gets bleached" and "if the bleaching product is not usedChapter 3. Epistemic Explanations^ 56in hot water, the T-shirt does not get bleached". Let's denote "new-product", "hot-water" , and "bleached-T-shirt" with the lower-case letters n, p and b respectively. Wewill represent the fact that we don't know whether the water might be hot enough,as incomparable scenarios in a CT4O-model. We represent the circumstance that Fredhas not yet used the bleaching-product and that the T-shirt is not bleached as KB ={-in, -,14, and the conditional knowledge as: n A h b, n A -ph -.b. Figure 3.6 showsthe corresponding preorder revision-model. "New-product" is a weak-explanation for"bleached-T-shirt" since the model satisfies n ---4 b, and n and b are rejected in K (then,B-in j B-,b, and trivially Bb j Bn). Notice also that the model satisfies the conditionaln .— -,b which indicates that under some set of equally most plausible situations whereFred uses the new product, the T-shirt does not get bleached (namely in cool water).This is why "new product" is a weak-explanation instead of a predictive one.As we studied in Section 2.4.1, in total-order revision models (CO-models) ----- be-comes equivalent to its stronger cousin =. Then, if the model M is a total-order-revisionmodel, then a weak explanation is just a quasi-predictive explanation. It is clear thatpredictive explanations are the strongest explanations we presented, and automaticallysatisfy the conditions of the non-predictive; that is, a predictive explanation is always aweak explanation and a might explanation. Similarly, a weak explanation is automati-cally a might explanation.3.3 Preferences in terms of PlausibilityWe have studied a number of conditions that relate explanation and explanandum. How-ever, they provide us no indication of preference among the many possible explanations.A preferred explanation should not only make the explanandum less surprising but beitself as unsurprising as possible. We will base our notion of preference on the plausi-bility ordering of states of affairs (which is just induced by the objective belief set andthe conditionals held by the agent). We propose a definition of comparative preferenceamong explanations based on Boutilier's definition of plausibility. In this section we willChapter 3. Epistemic Explanations^ 57refer generically to "an explanation" without qualification, to mean that it can be of anytype, i.e., predictive, might, etc.Definition 3.6 Let a and a' be explanations for O. a is at least as preferred as a', iffa < a' (namely, M b(a' D 0a)).a is considered at least as preferred as a' just when a is at least as plausible as a'. a anda' are equally preferred whenever a < a', and a' < a. In preorder revision-models not allpropositions are comparable; then, we can have explanations a, a' that are incomparable.We will define an explanation as a preferred one if it is in the cut of the most preferredexplanations for II.Definition 3.7 Let a be an explanation for 0. a is a preferred explanation for 0 iffthere is no other explanation a' such that a' < a.In our rain-sprinkler example of Figure 3.3, we have "rain" and "sprinkler" predictiveexplanations for "wet-grass" , where "rain" is a preferred explanation, while "sprinkler" isnot. Let's notice that the trivial explanation is always a preferred predictive explanationfor itself (it is trivially quasi-predictive as well).Proposition 3.7 0 is always a preferred (quasi)-predictive explanation for 0 .And /3 is always at least as preferred as any other (quasi)-predictive explanation.Proposition 3.8 For any predictive or quasi-predictive explanation a for 0 , 0 < a.In the case of predictive and quasi-predictive explanations we can provide a test thatdetermines whether a is a preferred explanation for /3. We should simply ask for anexplanation a to be consistent with all the most normal scenarios where the explanandum0 holds.Proposition 3.9 Leta a (quasi)-predictive explanation fond. a < /3 iff M 0 71-4 -Ia.Chapter 3. Epistemic Explanations^ 58Equivalently, an explanation a is not preferred iff M 0 -- -Ia.The following proposition shows that preferred quasi-predictive explanations and pre-ferred predictive ones coincide. This means that the difference between the predictiveand quasi-predictive notions arises among non-preferred explanations.Proposition 3.10 a is a preferred quasi-predictive explanation for 0 if a is a preferredpredictive explanation for 0.A criterion of preference in terms of plausibility sanctions that epistemically possibleexplanations be preferred over the epistemically impossible. It also indicates preferencesamong the different epistemically impossible explanations, suggesting the least divergentfrom theory K. However, such a criterion provides absolutely no indication of prefer-ences among explanations that are already epistemically possible. If a is accepted orindeterminate, it already enjoys the highest plausibility, since a-worlds are among themost plausible worlds. Consequently, we have the next proposition.Proposition 3.11 Let -10 0 K, (i.e, g is accepted or indeterminate), and a, a' be anypredictive explanations for g. Then, a < a' and a' < a.At first view, we could argue that one way to compare explanations that are accepted orindeterminate in K, is to perform the comparison with respect to a hypothetical epistemicstate where the explanandum / is rejected, namely If'4,3 . Then, preference should arisefrom the ordering of worlds in the revised model. Once again, we confront the problemthat M:; i3 is left underspecified by the AGM semantics. By assuming Boutilier's naturalrevision function, which defines it, we can show that the idea of comparing predictiveexplanations in such a model is rapidly defeated.Proposition 3.12 Let -ij3 0 K. If a, a' are predictive explanations for 0, then a, a' areequally plausible in M.We conclude that there can be no grounds for preferences for explanations of epistemicallypossible explanandums.Chapter 3. Epistemic Explanations^ 593.4 Pragmatics of ExplanationIn any system for explanations ultimately a sentence has to be returned. Not all the sen-tences sanctioned by the semantic conditions we proposed look exactly as we may expect.That is, several explanatory sentences may denote the same proposition that satisfies ourdesiderata. In this section we will briefly discuss trivial explanations, explanations in-cluding irrelevant information, and some problem with disjunctions in explanations. Wethink it might be useful to rule these problems out as a matter of pragmatics of explana-tion, much like Gricean maxims. We regard them as pragmatic issues since they relateto how explanations are used in different contexts or applications.3.4.1 Trivial ExplanationsIn many applications, when non-trivial explanations are possible, trivial explanations arenot desirable. As expected, trivial explanations "trivially" satisfy the required condi-tions for predictive explanations, hence, for the weaker counterparts as well. EpStatusis automatically satisfied, since 0 has the same epistemic status as 0. So are Predictand Absent, since M /3 0 (theorem ID is derivable in CO and CT4O). Moreover, atrivial explanation satisfies Correl and Cover.Proposition 3.13 A trivial explanation for /3 is a predictive covering explanation for /3.In order to address the issue of trivial explanations from a semantic perspective, we mayexplore the following question. Given an epistemic state K, When does there exist anon- trivial explanation for 0 ? Or, conversely, When does # have only a trivial explana-tion? Levesque (1989) suggested that if K is completely ignorant, nothing is predictivelyexplainable but trivially. In the same line of reasoning, if 0 E K and 0 is all we knowin K, /3 is only trivially explainable. And, if -70 is all we know in K, 0 is only triv-ially predictively explainable. There are possibly many cases other than the ones justdescribed. Identifying them may illuminate how to attack semantically the problem ofChapter 3. Epistemic Explanations^ 60trivial explanations. In general trivial explanations are undesirable for their uninforma-tive nature; however, when non-trivial explanations are non-existent, trivial explanationsmay be desirable. Besides, in certain applications the trivial explanation may be a truecandidate.We speculate that explanations that subsume the explanandum, and those that aresubsumed by the explanandum may also lead to a notion of uninformativeness. (Namely,given an explanandum /3, a lies in this class if either the proposition denoted by a isincluded in the one denoted by 0, or the other way around: Hall C 11011 or3.4.2 Irrelevant Factors and Disjunctions in ExplanationsExplanation sentences that have incorporated irrelevant factors (say, they are a con-junction of a proposition that accounts for the observation and a completely irrelevantproposition that just happens to be consistent) sanction commitment on issues thatshould be irrelevant, hence not part of an explanation. Say, if rain is an explanationfor wet_grass, so could be rain A my_car_is_red, if at the set of most plausible statesof affairs where rain holds, rain A my_car_is_red also holds; then at the most plausiblescenarios, the two denote the same proposition.A related problem is that explanations may include background beliefs. With back-ground belief we refer to those accepted and non-contingent credences; an example canour belief "the day has 24 hours". According to the conditions we imposed on expla-nations, if -y is a background belief, a A 7 is an explanation for /3 whenever a is. So,rain A the_day_has24_hs is as good an explanation as rain. The sibling case is given bythe disjunction of an explanation with the negation of a background belief; namely a V -17is as good an explanation for 0 as a is. Then, rain V -, (the_day_has_24_hs) is as good asrain. Background beliefs may be captured by the schema M n(7 D ^7), (indicatingthat if y holds at some world w then it holds at every world at least as plausible as w).Our semantic analysis points to a preferred set of propositional valuations in therevision model where explanation and explanandum hold. We can see such valuationsChapter 3. Epistemic Explanations^ 61indicating a "plain" explanation sentence, that would include background beliefs. Fromthis plain sentence some "filtering" may be applied. A "simplest" sentence may be for-mulated, for example, using the comparison of sentence-simplicity as defined by Levesque(1989). Interestingly, not all applications based on abductive reasoning seek the samekind of explanations. For example, in image interpretation, an explanation (i.e. an inter-pretation of an image) conjoined with background beliefs about what the scene is likelyto be, may be desirable.Chapter 4Capturing "Abductive" ApproachesIn this chapter we take Theorist as a representative of the "abductive" approachesto explanation and recast it in our framework. We will achieve this by interpretingthe background epistemic state of the agent (or program) as a theory of expectations((Gardenfors 1990),(Makinson and Gardenfors 1990) (Gardenfors and Makinson 1991),(Boutilier 1992c),(Boutilier 1992f)). Instead of attributing a subjunctive interpretationto conditionals, they will denote defaults or expectations. We will show why Theoristexplanations are paraconsistent and non-predictive, and how they can be made predic-tive. Then we will map in our model Brewka's extension of Theorist, which providesa prioritized default setting. We will define a weak and a predictive notion of explana-tion in Brewka setting. We will elaborate on the effect of priorities over defaults whenused abductively. We will propose how to augment Theorist and also Brewka's exten-sion to provide preferences among explanations. Capturing the Theorist framework andBrewka's extension will evidence the expressive power and generality of our modeling ofexplanation.4.1 Capturing TheoristOur goal is to express Theorist explanations as conditional sentences. We will first definea Kripke model for the Theorist framework that we will call MD . Then we will identifya class of models to which MD belongs to, a modal system that characterizes such classand allows us to express global conditional statements. As Theorist defines a frameworkfor both default and abductive reasoning, we should construct a model that satisfies the62Chapter 4. Capturing "Abductive" Approaches^ 63conditionals corresponding to both skeptical default inferences as well as abductive infer-ences. Our modeling should contemplate that Theorist's sets of defaults and conjecturesneed not be consistent, and are not closed under (classical) logical consequence. Theoristframework is based on maxiconsistent constructions from the set of defaults. This makesit syntax-sensitive with respect to the defaults (since depending on how the defaultsare expressed, different maximal subsets of defaults may be derived). Our mapping ofTheorist will not consider constraints.As usual, we take P a denumerable set of atomic variables, and IL cpL denotes thepropositional language over this set. Sets .F, D, C will be taken as sets of propositionalsentences, consisting of ground instances of the formulae sanctioned by the Theorist facts,defaults and conjectures. We should assume a fixed set of defaults 1). 1We will define a Kripke model MD , based on Boutilier's (1992f) key the idea ofcounting default violations. This model will be just relative to the set of defaults D;then, it will be suitable for any set of facts .7'. Following Theorist syntax-sensitive spirit,we define for each world its default violation set.Definition 4.1 For any valuation w E W, the set of defaults violated by w is denotedV(w)= Id : w falsifies default formulae d E D }.Now, the ordering of worlds is induced by the set inclusion ordering among each world'sdefault-violation-set. If we interpret defaults as normality assumptions, the accessibilityrelation orders worlds according to their degree of normality.Definition 4.2 The Theorist model for D is denoted by MD = (W, R, (,o), where W isthe set of possible worlds such that all propositional valuations are present 2 ; v maps Pinto 2' (v(A) is the set of worlds where A holds); and R is defined as follows: for eachv, w E W, wRy iff V(v) c V(w).'This requirement could be relaxed if we defined a "revision" of the Theorist model M D by a newdefault sentence d', hence, obtaining a new model M4, = (Mv)71,. We could define the contraction ofMD by an existing default sentence, obtaining a new model MC, = (MD) d- , where the old default d hasbeen "forgotten". However, forgetting defaults is not contemplated in Theorist.'Modeling Theorist with constraints may require to exclude some propositional valuations from W.Chapter 4. Capturing "Abductive" Approaches^ 64It should be clear that wRv and vRw if and only if V(v) = V(w). The situation wherewRv, but not vRw arises only when V(v) C V(w). The definition gives rise to a modelforming a lattice. R divides the set of worlds into clusters. Those worlds violating exactlythe same set of defaults are in the same cluster. A world w can "see" another world v ifand only if the set of defaults violated by w contains the set of defaults violated by v. Aworld w is in a minimal cluster of the lattice if there are no other worlds that violate aproper subset of defaults violated by w. Not all worlds are "comparable" with respect toR. For any two worlds w, v, if the default-violation set of world v is not included in thedefault-violation set of w, nor the other way around, then w can not see v, and v can notsee w. Therefore, the accessibility relation R is not connected on W. MD lies within theclass of reflexive and transitive models. Our definition of a model MD corrects Boutilier's(1992f) modeling of Theorist, which assumed total connectedness a (CO-model).Proposition 4.1 MD is a CT40* model.Theorist models are well-founded models, which means that they satisfy the so-calledLimit Assumption. This assumption states that in each model there exists some minimalA-world for any proposition A. That is, Theorist models are "bottomed".Proposition 4.2 Let MD = (W,R,co) be the Theorist model for D. Let each singledefault formula d E D be satisfiable. MD possesses a single R-minimum cluster iff D isconsistent.As the set of defaults D is finite, the corresponding model MD will have a finite number ofR-minimal clusters. Let's analyze the famous University Students example. Let u denote"university student" , a denote "adult" , and e denote "employed". Figure 4.7 shows theCT4O* model for the set of defaults D= {u D a, u D -le, a D e}. For convenience wename the defaults as follows: hl : u D a, h2 : u D h3 : a D e. Let's write for eachworld its default-violation set.Chapter 4. Capturing "Abductive" Approaches^ 65Figure 4.7: Theorist model for University Students example.wl = { u a e} V (wl) = {h2} w2 = { u a-ie} V(w2) = {h3}w3 = { u-ia e} V (w3) = {hi ,h2} w4 = {^u--a-ie} V(w4) = {hl}w5 = {-iu a e} V (w5) = {} w6 = {-u a-iel V(w6) = {h3}w7 = hu-ia e} V (w7) = {} w8 = {-iu-ia-e} V(w8) = {}The key concept is to characterize extensions of (.7',D) in MD . According to Poole'sdefinition, an extension (see definition 2.2) is the set of logical consequences of 2 togetherwith a maximal consistent subset of defaults of D. Then, each extension results inminimal (subset related) default violations. We will introduce some terminology. Let'sassume a X to be any consistent set of propositional formulae.Definition 4.3 Let M = (147, Rop) any model for which R is transitive (and we willalways assume reflexive). A world w E W is R -minimal X -world iff M ti, X, and forevery world v E W, such that wRv but not vRw, M 1= -,X.A minimal X-cluster is a maximal set of mutually accessible R-minimal X-worlds. WeChapter 4. Capturing "Abductive" Approaches^ 66say that a set of worlds U characterizes a set Y such that Y = Cn(Y) if an only ifU = Di.Lemma 4.3 S is an extension of (X, D) if there is a minimal X-cluster that charac-terizes S.Theorist predictions correspond to what all extensions have in common. As shown byBoutilier, if we see a default theory as a theory of expectations, skeptical default conclu-sions can be understood as the revision of the default theory by the facts, where we wantto keep as many expectations as possible without forcing inconsistency. Under this read-ing, predictions correspond to the AGM revision of the default theory by the facts. TheRamsey test equates B E if:1 with A B. The next theorems, lemmas and propositionsassume a Theorist pair (F, D), MD the model for D, and denote with F the conjunctionof F. The next theorem embodies Boutilier's (1992f) result for Theorist predictions, inour CT4O-model.Theorem 4.4 7 is predicted in Theorist sense from (F, D) if MD F y, and F issatisfiable.Let's illustrate predictions with the university-student example. If we assume as factthat Fred is an adult, that is .7" = {a}, we predict Fred is employed and that he's not auniversity student. This is reflected in the model MD of Figure 4.7 since MD a eand MD a --iu. In contrast, if we take as fact that Fred is a university student,that is .7. = {u}, we can not predict him being an adult, nor being employed. We haveMD ik u a, and mi, K u e. Notice also that MD K u -'a, and mi, lik u -, e.We should now explore the correspondence of Theorist explanations in MD . A The-orist explanation for an observation 3 (see definition 2.4) is a subset D of defaults anda subset of conjectures C that together with the facts entail the observation, providedthat the facts together with the defaults and conjectures are consistent (F U C U D 0'and F U C U D is consistent). Let's recall that our definition of a Theorist model is justChapter 4. Capturing "Abductive" Approaches^ 67relative to the set of defaults D; hence, facts .7' and conjectures C play no role in the defi-nition of MD . We would like to express Theorist explanations in CT4O, without makingexplicit which particular defaults are considered. Poole (see theorem 2.1) states that -yis explainable if 7 is in some extension of the default theory. Consequently, 0 is in someextension containing C. Obviously we can not use the same connective that we have usedfor predictions, since a statement (.7- U C) /3 would involve every extension containingthe facts .7' and conjectures C. Theorist explanations allow just some particular defaultsto be assumed. The connective .— gives the desired behaviour in CT4O.Theorem 4.5 Let D C D and C C C. D U C is a Theorist explanation for /3. ifMD (F U C) --* 13 and (F U C) is consistent. 3 .Theorist sanctions that observations inconsistent with the facts are not explainable. Thisfollows from theorem 4.5.Corollary 4.6 If .7- CPL 73 then there is no C such that MD^(.F U C) ----4 /3 and(F U C) is consistent.As we noticed when studying Boutilier's logics (Section 2.4.1) the conditional —> be-haves paraconsistently in CT4O. The next example illustrates that Theorist explana-tions are in some sense paraconsistent, hence, nicely captured by --4. Let .7 - = Cn(0),D = {a D b, a D —lb}, and C = {a}. Figure 4.8 shows the MD model for D. The followingconditionals are satisfied: MD a ---- b, and MD = a —* -'b. So, a is an explanationfor b and simultaneously a is an explanation for -,b. On the Theorist side we have the twocounterpart explanations. For D = {a D b}, and C = {a}, C U D explains b. While forD = {a D -,b}, and C = {a}, C U D explains -, b. This means Theorist explanations areweak explanations, and motivates our development of a stronger notion. Theorist expla-nations are the counterpart of our "`weak"-epistemic explanations when the backgroundepistemic theory is interpreted as a theory of expectations.'Since (.F U C) is a set of formulae, the conditional (F U C) --- # should be understood as theconjunction of the elements in F U C entailing #Chapter 4. Capturing "Abductive" Approaches^ 68Figure 4.8: Theorist model for D = {a D b, a DBefore turning our attention to predictive explanations we illustrate the aptness ofour modeling of Theorist explanation. In Theorist, if -y is predicted from (.F, D) then 7is explainable with no conjectures, and is not explainable with no conjectures. Thefollowing proposition shows that our mapping obeys this behaviour.Proposition 4.7 If MD F^and F is satisfiable then (a) is explainable with noconjectures, and (b) -93 is not explainable with no conjectures.Notice that the converse of this proposition does not necessarily hold. Assume in ouruniversity-student example, that Fred is not employed and he's a university student oran adult, that is, .F = (u V a)}. We can weakly explain that Fred is universitystudent (by assuming the contrapositive of the default a D e, we conclude -la and u).The model MD of Figure 4.7 sanctions the conditional .7 - —> u, or in other words, u is insome extension of the default theory. However, we can not explain since is in noextension of the default theory (since .F is consistent with u e and u D^and u D a,we can not conclude -, u). This is reflected in the Theorist model since MD^—> -'u(notice that the pair of worlds labeled w2 and w6 in Figure 4.7 denote an extension).Chapter 4. Capturing "Abductive" Approaches^ 694.2 Extending Theorist: Predictive ExplanationsIn this section we will explore the notion of "predictive" explanations. Predictive expla-nations arise as the "natural" abductive side of default predictions. If some conjecturespredictively explain an observation, such conjectures shall not explain its negation. Atfirst view, we could propose C C C as a predictive explanation for an observation /3, iffor any D C D, .T U D U C ci,} 1, 0, while .F U D U C is consistent. However, 0 C D,so the notion of predictive explanation would be trivial, since it would just reduce toclassical entailment (i.e., .7 . U C Hon, /3). A better statement of predictive explanationsin the Theorist setting is given by the following definition.Definition 4.4 Let the Theorist triple (T,D,C), and an observation O. C is a predictiveexplanation for /3, if /3 belongs to all extensions of ((.7. U C), V).An observation is predictively explained by some conjectures if the observation is en-tailed by the facts together with every maximal set of defaults consistent with the factsand conjectures. The next theorem proves that the conditional connective capturesprecisely such notion of a predictive explanation in the Theorist setting.Theorem 4.8 C is a predictive explanation for 0 if MD = (.F U C) /3, and (.T U C)is consistent.This theorem demonstrates that our notion of a predictive explanation naturally lead toour extension of Theorist of Definition 4.4.Let's give one example using the university-student model of Figure 4.7. Let's assumea set of conjectures C = {u, -,u,e,--, e,a, -,al. Suppose as fact that Fred is an adult, ,F ={a}, then we predict that Fred is employed and he's not a university student (MD a eand MD = a^-, u). If we observe that Fred is not employed then we can explain it(weakly) by conjecturing that he is a university student, since M D^a A u -- --,e.But also by conjecturing that he's a university student we can weakly explain that he isemployed (MD aAu ---* e), contrary to our observation. Then, we can not predictivelyChapter 4. Capturing "Abductive" Approaches^ 70explain that he is employed, which is reflected by MD a A u^e.Assume now as a fact that Fred is a university student, so^= {u}. By conjecturingthat Fred is employed we can predictively explain that he is an adult, as MD u A e a.Clearly, we can also weakly explain his adulthood, since MD u A e a. The nextproposition shows that predictive explanations are a subset of Theorist (non-predictive)explanations. It also stresses the non-paraconsistent nature of predictive explanations.We say that a Theorist explanation for 13 assumes conjectures C if and only if there isD C 7.") such that .T U C U D and U D U C is consistent.Proposition 4.9 Let C C C. If C is a predictive explanation for then (a) there is aTheorist explanation for 13 assuming C; and (b) — , 13 is not explainable assuming C.Notice that the converse of this proposition does not necessarily hold, for the same reasonthat the converse of Proposition 4.4 does not necessarily hold.4.3 Capturing Brewka's Preferred SubtheoriesIn this section we will concentrate in Brewka's extension of Theorist (presented in Sec-tion 2.2.4, which adds priorities to defaults. A Brewka theory is a pair (T, B) such that.7' is a set of true facts, and B = (B1 , B2, . Bn ) is a set of defaults where the rank B,is more reliable than ./3; if i < j, and no rank of B needs to be consistent. As we havedone with Theorist, we will first define a Kripke model for Brewka's framework that wewill call MB. Boutilier (1992f) stated how Brewka's framework can be modeled countingdefault rule violations. We propose a model MB very related to Boutilier's; however, hisassumption that the model was connected was not right. Each world possesses, for eachrank of the default theory B, a hypotheses-violation set.Definition 4.5 For any valuation w E W, the set of defaults of rank i violated by w isdenoted V =^E 13, : w falsifies default formula d }.Given a default theory B = (Br , . , B„), each world will have associated n hypothesis-violation sets, one per rank, and we will consider (for technical convenience) an emptyChapter 4. Capturing "Abductive" Approaches^ 71violation set for (non-existent) rank n + 1, i.e. V.7+ 1 = {}.We shall induce a normality ordering among worlds, from the reliability ordering ofthe hypotheses in B. Given a pair of worlds v, w we will determine the rank i such thatthe set of hypotheses violated by w strictly contains the set of hypotheses violated byv at rank i, and for all the ranks more reliable than i, the violation sets for w and vcoincide. We will identify such rank i with min(v, w). Let's recall that the hypotheseswith the highest reliability are in 131 , the next to the highest priority are in 82, so on.Definition 4.6 Let a default theory 13 = , B.). For worlds w, v, letmin(v, w) = min 1 is (^c Vt: or V: c V:,) and Vj such that 1 < j <^=If the above set is empty, let min(v, w) = n + 1.If a world w violates a hypothesis from a more reliable rank than any of the hypothesesviolated by world v, then v should be considered a more normal world than w. However,if v and w violate the same hypotheses up to rank i — 1, world v should be consideredmore normal than w only if the violation set of v for rank i is strictly included in theviolation set of w, independently of other hypothesis violations at any less reliable rank.Definition 4.7 The Brewka model for B = (Br , ... ,B„) is denoted by the triple MB =(W, R, (p), where W is the set of possible worlds such that all propositional valuations arepresent; co maps P into 2w (v(A) is the set of worlds where A holds); and R is definedas follows: for each v, w E W, wRz, if '1/": C V„i , Vi s.t. 1 < i < min(v, w).The definition gives rise to a CT4O-model. Those worlds violating exactly the samehypotheses are in the same cluster. A world w can "see" another world v if and only if theset of hypotheses violated by w at rank min(v, w) strictly contains the set of hypothesesviolated by v that rank, and for all more reliable ranks the violation sets for w and vcoincide. A world w is in a minimal cluster of the lattice if there are no other worldsthat violate a proper subset of hypotheses violated by w.Proposition 4.10 MB is a CT40* model.u a -e-" - - ....... ---u a -e1-u a e-xi -a e-a -e26Chapter 4. Capturing "Abductive" Approaches^ 72As expected MB models satisfies the Limit Assumption (in each model there is someminimal A-world for any proposition A). Next example shows a MB model for theFigure 4.9: Brewka model for University Students example.University Students example, assuming 13 = (51 , 52 ), Si = {hl : u D a, h2 : u D^,52 = {h3 : a D e}. Let's write for each world its hypotheses violation sets. Thecorrespondent MB model is shown in Figure 4.9.Chapter 4. Capturing "Abductive" Approaches^ 73wl =^fu a e} Vvii = 021^Vu,21 = 0 w2=^fu a -iel V111,2 = 0^VI = 031w3 = 1u --la el Vu1,3 = {h1, h2} VI = 0 w4 = fu -, a -,e} 171= {hi} VI = 0w5= hu a el Vt!5 = 0^Vw26 = 0 w6= hu a -,e1 V1,1,6 = 0^VI = 031w7 = hu -, a, el Vula = 0^Vw27 = 0 w8 = { -iu --la --ie} V„,18 = 0^VI = 0Let's characterize extensions in MB. An extension S is formed by maximal sub-sets of hypotheses preferring the most reliable ranks; then it seems natural that thecharacterization of S in MB be given by most normal worlds. Similar results to thoseobtained for Theorist hold for Brewka models. Let MB the model for a default theory13 = . ,13,x ). Let's assume a X to be any consistent set of propositional formulae.Lemma 4.11 S is an extension of (X , B) if there a is minimal X -cluster characterizing S.For the following propositions, lemmas and theorems we shall assume a Brewka theory(.F, T), such that B = (Br , . . . , Bn ), MB = (W, R, co) the Brewka model for B and Fdenoting the conjunction of .F.Proposition 4.12 Let each single default formula d E 13 be satisfiable. MB possesses asingle R-minimum cluster if B is consistent.Predictions (skeptical default conclusions) are specified by what all extensions havein common, and correspond to Strong B-entailment given the facts. The next theoremshows the correspondence in MB.Theorem 4.13 .7' has -y iff MB F -y, and F satisfiable.Assume the default theory of the university-students example and^= {u} Thenu -'e, since is entailed by all extensions of (.F,B). Notice that there is only oneextension of (.7', B) and it corresponds to the shaded area in Figure 4.9, the most normalworld where u holds. Hence MB uChapter 4. Capturing "Abductive" Approaches^ 74Given a theory (F, 8), and an observation /3 we can ask What's a premiss a thattogether with the facts Strongly-B-entails p ? Equivalently, What's a premiss a such thatall extensions of ((..F U a), 13) entail /3? In a belief revision style, this idea results inthe question: By what premiss (together with the facts) should the expectation-theory berevised, such that the observations become believed? The Ramsey test equates /3 E B;-uc,with (F A a) /3. We will elaborate on the two notions of explainability from Brewka-theories, that arise from an abductive reading of the two kinds of entailment. Explana-tions arising from Strong B-entailment will be referred to as predictive explanations. Asa consequence of Theorem 4.13, the following holds:U a I-Bs -y iff MB (F A a) -y and (F A a) satisfiable.We say a is a predictive explanation for -y.The explainability notion arising from Weak B-entailment is non-predictive. For anobservation /3 we can ask What's a premiss a such that there is at least one extension of((Y. U a), B) that entails /3? This notion corresponds to Theorist explanations but in aprioritized default theory. The conditional (.F U a) —> /3 expresses that there is someextension of ((.7 . U a), B) in which /3 holds. A non-predictive explanation accounts forthe observation in some of the maximally plausible scenarios.Theorem 4.14 ..F U a I BW /3 if MB (F A a) —> /3 and (F A a) satisfiable.Due to the close correspondence between Theorist and Brewka's frameworks, Theo-rems 4.13, and 4.14 are not surprising. The same insight about the paraconsistencyof —> in CT4O applies to Weak B-entailment.Let's discuss how a prioritized default theory affects the abductive activity. SinceBrewka's framework is a prioritized version of Theorist, and we have provided CT4Omodels for both, we are able to make a legitimate comparison of the explanations thatarise in each. Let's compare the University Students example. The following conditionalsare sanctioned in the Theorist model MD (see Figure 4.7): (u A a) e, (u A a) —>u^e, u^u^a, u --+^T^(u A -la)Chapter 4. Capturing "Abductive" Approaches^ 75The Brewka model MB sanctions the following conditionals. (u A a) —+ -,e; moreover,(uAa)^-,e, a^-,u, (uA-,a)^--,e; however, MB (uAa) 7/-- e and MB^(uAa) ,^- e.In the model of a prioritized default theory, at least as many constraints on theordering of worlds are imposed as in the model of the flat theory. Even though a Brewkamodel isn't necessarily connected (i.e. CT4O-model), the rate of connectedness may behigher than the counterpart Theorist model. For the next propositions let's assume aBrewka theory (.7- , B), where 13 = (131i . . . , BO , and a Theorist pair (..F, D), such thatD = U7_ 1 13i . MD = (W, RD, y") denotes the Theorist model for a D, and MB = (W, RB, co)the Brewka model for B. The following proposition shows that MB is at least as connectedas MD .Proposition 4.15 If wriDv then wR5v.Proposition 4.16 MD and MB have the same clusters.Proposition 4.17 Every RB -minimal cluster in MB is a RD-minimal cluster in MD .Proposition 4.18 If D is consistent, then MD and MB have the same unique minimalcluster.We can now show that predictive explanations in Theorist setting are predictive expla-nations in Brewka's framework.Proposition 4.19 If MD a 0 then MB a /3.We can now show that non-predictive explanations in Brewka's framework are non-predictive explanations Theorist setting. Thus Brewka model adds (possibly) predictiveexplanations. The prioritized default setting together with the notion of preferences (seebelow) can be viewed as "restricting' what counts as a good explanation.Proposition 4.20 If MB a ---4 0 then MD a —> /3.Chapter 4. Capturing "Abductive" Approaches^ 764.4 Preferences: Maximizing NormalityNone of the two notions of explanation (predictive and non-predictive) give any indicationof preferences among the many different possible choices of what can be hypothesizedin order to account for an observation; and as Rescher (1978) pointed out "conjecturalfancy is limitless" . In this section we introduce a natural notion of preference amongexplanations, that arises from the ordering of worlds in the model. Roughly, a worldis "lower" in the ordering if it violates "fewer" defaults. Now, if defaults representexpectations, normality assumptions or statements of high probability then a world thatviolates fewer hypotheses is to be considered more "normal". It seems natural thatpreferred explanations be sanctioned by those most normal worlds where the observationholds. We will define a notion of comparative preference for predictive explanations inTheorist /Brewka setting, where conjectures that are consistent with more (under setinclusion) defaults are preferred. This notion naturally arises from the preferences interms of plausibility on epistemic explanations that we studied in Chapter 3. NeitherTheorist nor Brewka's framework provide a notion of preference; so our proposal reallyaugments their capabilities. Let F denote the conjunction of .F, and a, a' the conjunctionof elements in C, C' C C (or just premisses in LcpL ).Definition 4.8 Let a, a' be predictive Theorist explanations for /3 given a theory (.7', 7)).a is a at least as preferred as a' (written a ‹ ..F a') if each maximal subset of defaultsD' consistent with a' U .7. is contained in some in some maximal subset of defaults Dconsistent with a U Y.In certain cases two predictive explanations may result incomparable; that is, the maximalsubset of defaults consistent with one may not be contained in any of the maximal subsetsof the other one, nor the other way around. Then we may want to say that both arepreferred. So we define a notion of a preferred predictive explanation.Definition 4.9 Let a be a predictive Theorist explanation for /3 given a theory (Y, D).a is a preferred explanation for /3 iff there is no other predictive explanation a' such thatChapter 4. Capturing "Abductive" Approaches^ 77each maximal subset of defaults D consistent with a U .7' is strictly contained in somemaximal subset of defaults D' consistent with a' U .Identical counterpart definitions can be given in Brewka setting. For the theorems andpropositions to follow, let's assume a CT4O model M that indistinctively may reflect aBrewka or a Theorist model. We can show that the definition of comparative preferencecorresponds to comparative normality in model M (i.e. the corresponding MD/MB ).Since the propositions and lemmas that follow hold for both Theorist and Brewka mod-eling we will refer generically to "predictive explanations" and "non-predictive explana-tions" without making explicit under which system.Theorem 4.21 Let a, a' be predictive explanations for 3. a <,7- a' iffM 1 b((a'AF) D0(a A F)).This theorem crystallizes the connection with our notion of preferences on epistemic ex-planations. In Chapter 3 we defined preferences on predictive explanations by comparingthe plausibility of the explanations. We based our notion on the idea that an explanationshould not only make the observation plausible but be itself maximally plausible. If de-faults reflect assumptions of normality, then a preferred explanation in a default settingshould be maximally normal; that is, be consistent with as many defaults as possible.We can now show the counterpart results from the ones obtained in Chapter 3 for thispreference in terms of normality.Corollary 4.22 The preference relation <.7- is reflexive and transitive.An observation is at least as preferred as any predictive explanation for it. A predictiveexplanation a for an observation Q sanctions that /3 should belong to all the extensionsconsistent with a and the facts. Then it is clear that the observation must be consistentwith at least as many defaults as the explanation a is. This is shown in the followingproposition.Proposition 4.23 Let a a predictive explanation for 0, then <y- a.Chapter 4. Capturing "Abductive" Approaches^ 78We may be also interested in preferences among non-predictive explanations. We canapply the idea of maximizing normality. Conjectures a that are consistent with more(under set inclusion) defaults should be preferred. But as non-predictive explanations areparaconsistent (in the sense that they can explain both an observation and its negation),then there can be some extensions of satisfying 0 and others satisfying -0. So whencomparing the "normality" of two non-predictive explanations we may want to restrictthe comparison to the respective maximal sets of defaults consistent with the observation.When modeling a prioritized set of defaults (as for example obtaining the prioritiesby Pearl's (1990) Z ranking of default rules), the ordering of worlds induced by the pri-orities determines a meaningful preference ordering of worlds in the structure. One canspeculate that in a prioritized framework, the inverse of the priority ordering among de-faults must play a significant role when drawing explanations. That is, when explainingan observation, a least "exceptional" explanation may be preferred. It seems natural todraw it from the least exceptional rank of hypotheses. This makes sense, as long as weare not violating any of the most reliable hypotheses. This is precisely captured by givingpreferring explanations that hold at most normal worlds, since such worlds violate thefewest hypotheses. We have seen that the degree of comparability of states of affairs ina model of a prioritized default theory may be richer than in the correspondent modelwith no priorities. Predictive and non-predictive explanations that are incomparable ina model of a flat default theory, may be comparable in the model for the correspondentprioritized theory. We also conclude that the priorities in a default framework act as apruning mechanism, restricting the non-predictive explanations and increasing the pre-dictive ones. A prioritized default setting should give rise to more meaningful preferredpredictive explanations.Chapter 5Capturing Consistency Based DiagnosisModel-based diagnosis is an application of abductive reasoning, that brought the atten-tion of many researchers in AI. Different models of diagnosis have been proposed in theliterature. "Abductive" diagnosis (as formalized in the Theorist framework) and con-sistency based diagnosis ((Reiter 1987b),) are today's canonical qualitative approaches.Poole (1989b), (1990) and Konolige (1992b),(1992a) have investigated in detail the con-nections between the two frameworks. In this chapter we will recast the consistencybased diagnosis framework (presented in Section 2.2.5) in CT4O. We will achieve this bymapping the consistency based model onto a Theorist model, obtaining a unified seman-tic account for the two approaches to diagnosis. We will demonstrate that a consistencybased diagnosis correspond to the idea of an excuse for the conflictive observation, anddraw the connection with our (epistemic) "might" explanations of Chapter 3. We showformal correspondence between our proposed notion of preferences on explanations andminimal diagnosis.5.1 Recasting Consistency Based Diagnosis in CT4OWhen doing diagnosis, we want to find out what is wrong with some system. The goalis to explain an observation that conflicts with our expectation of normal behaviour ofthe system. de Kleer Mackworth Reiter (dKMR) in their consistency based frameworkassume a system with set of components COMPS, represented as a set of constants; asystem description, axiomatized as a set of first order sentences; and a set of observationOBS, represented as a set of first order sentences. The system description axiomatizesthe correct behaviour of the system, under the explicit assumption that each component79Chapter 5. Capturing Consistency Based Diagnosis^ 80is working correctly. Knowledge about how problems (symptoms, diseases) manifestthemselves can also be included as part of the system description. That is, fault modelsand/or exoneration axioms can be involved in the description of the system. The setof observations OBS has to be explained. If the observations do not conflict with theexpected (correct) behaviour of the system, then every component is assumed to benormal and it is concluded that there is nothing wrong with the system. If, howeverthe observations do conflict with the correct behaviour, then some components mustbe malfunctioning. Guided by the "principle of parsimony" with respect to componentfailures, the set of faulty components is considered minimal. This minimal set of abnormalcomponents renders OBS consistent.Let a toy system of a lamp, formed by a plug and a bulb, such that if both componentsare working correctly we expect light to be produced. This is encoded in the followingsystem description:-iab_bulb A -iab_plug D lightAdd the constraint that dark and light are mutually exclusive. If we observe OBS=light, this is consistent with our expectation of components being normal; then, OBSis a consistent observation. In contrast, OBS= dark is an inconsistent observation.Evidently, some component must be wrong.We should define a suitable Kripke model for the consistency based diagnosis frame-work. We will consider SD a propositional sentence denoting the conjunction of theground instances of the first order axiomatization of the system description. We denotewith /3 the conjunction of the (ground instances of the) sentences in OBS. dKMR usethe literal ab(c) to indicate that component c is functioning abnormally, and -, ab(c) toindicate that component c is working correctly. We will just refer to the propositionalvariable ab_c and to its negation -, ab_c. dKMR denote a diagnosis for an observationwith a sentence D(Cp, Ca):[A ab(c)] A [ A -Iab(c)]cE0 cEcomPs-0Chapter 5. Capturing Consistency Based Diagnosis^ 81where the components in A C COMPS are assumed to be malfunctioning while the rest,i.e. COMPS—A, are assumed to be working correctly, such thatSDUD(Cp , C,i )U OBS is consistentReiter (1987) showed formal correspondence between his theory of diagnosis from firstprinciples and default logic. He assumed a set of defaults stating that each component isnot malfunctioning. Based on his connection, we will assume a set D containing as manydefaults as components, indicating that each component is not abnormal. We expressthe defaults in propositional language, so D = , . The principle ofparsimony with respect to component failure shall induce a plausibility ordering over pos-sible worlds. Worlds reflecting fewer (under set inclusion) failing components should beregarded as more "normal" than those with more failures. This ordering is precisely cap-tured by a Theorist model for D. We assume a model MD for D = , 1,as defined in Chapter 4 (Definitions 4.1 and 4.2). We obtained a model that is definedjust relative to the set of expectations of normal component behaviour. The model pos-sess a minimal cluster at the bottom denoting all the worlds where all components areassumed normal. Figure 5.10 illustrates a model MD for 7, = -,ab_c21, indicat-ing the expectation that each of the two components, cl, c2 are working correctly. Aswe studied, MD is a CT40*-model. Worlds violating the same normality assumptionsare in the same cluster. Worlds with violating more (set inclusion) normalities haveaccess to worlds violating fewer normalities. Since the model MD is defined solely withrespect to the defaults D, all worlds satisfying the system description SD are scatteredin each cluster. If there are SD-worlds in the minimal cluster of MD , then those worldscorrespond to models of the system with no failures. Obviously such SD-worlds in theminimal cluster (which involve no abnormalities) exist if and only if SDU-iab(c) for allcomponents c ECOMPS is consistent. In order to derive diagnosis we will only be con-cerned in worlds satisfying the system description 1 SD; that is, worlds violating SD (i.e.'Allowing -SD-worlds be eligible to explain conflicting observations suggests a way of modeling whatpeople in hardware-verification do. Given an observation that conflicts with the system description mayChapter 5. Capturing Consistency Based Diagnosis^ 82Figure 5.10: Model reflecting expectation of correct behaviour, for two components.—6D-worlds) will not be of interest. 2 We can see that the system description SD plays asimilar role than the set of facts F in Theorist setting.For the purpose of our presentation, we will denote with a E LCPL the conjunction ofabnormal-components, and with 7 E LCPL the conjunction of not-abnormal-components.Namely, a = A i ab_ci for the components ci E A, and y = Ai —,ab_ci for the componentscj E COMPS—A. The conjunction a A y is always satisfiable, and denotes a uniquepossible "state" of the system, such that each component is known to be normal orabnormal.Let's assume that all components are working normally. If an observation conflictswith the expected behavior of the system, we conclude that the assumption of correctbehaviour for all components can not hold. We define an excuse3 for the observation, asbe explained by some components being abnormal or by suggesting that the system could be badlydesigned. An explanation that involves no abnormalities and contradicts the current system descriptionproposes a new system design.'This suggests a simplification of the model MD for consistency based diagnosis. A model MD =(W, R, (p), such that the set of possible worlds W includes exclusively just SD-worlds (MD BSD),obtaining a model that is not full.'The term "excuse" is borrowed from Konolige (1992b).Chapter 5. Capturing Consistency Based Diagnosis^ 83an hypothesis about some components being faulty, which makes the observation possible.Definition 5.1 a is an excuse for # if MD SD A a^such that a = A i ab_ci forcomponents c i E A C COMPS.If we interpret D as a theory of expectations, excuses for an observation 8 relative to amodel MD are equated via the Ramsey test with:'13 D*S Da is an excuse for /3, when by revising our expectations of normal behaviour accepting a(together with the system description), we can not regard the observation as impossible.Excuses in MD have their correspondence to "might" explanations in revision models(studied in Chapter 3). We defined A as a "might" explanation for B relative to abelief set K when -'B K. Let's see one example of an excuse for our lamp system.Figure 5.10 shows the MD model for the set of defaults D = {-, ab_plug, -, ab_bulb} , byrepresenting ab_plug with abl, ab_bulb with ab2, and light with 1. Worlds satisfying thesystem description SD are shaded. Let's assume SD = -iab_bulb A --I ab_plug D light. Letdark = -ilight. Given our definition of an excuse, ab_bulb is an excuse for dark, so isab_plug, and so is the conjunction ab_plug A ab_bulb, since MD SD A ab_bulbMD SD A ab_plug -idark and MD SD A ab_bulb A ab_bulb 74- -'dark. The nexttheorem demonstrates that the concept of an excuse captures precisely the notion of adiagnosis in the consistency based framework.Theorem 5.1 a is an excuse for /3 iff a A -y is a diagnosis for /3, where a = A i ab_ci forci E A, and 'y = -iab_ci for ci E COMPS - A.dKMR show that there exists a diagnosis for an observation if and only if the observationis consistent with the system description. The same result holds for excuses in MD.Proposition 5.2 There exists an excuse for /3 iff SD A /3 is satisfiable.Chapter 5. Capturing Consistency Based Diagnosis^ 84Based on Boutilier's notion comparative normality we can derive preferred excuses relativeto model MD . Preferred excuses will be those maximally normal; that is, preferred excusesare determined by the most normal worlds consistent with the observation. These arethe worlds where as few components as possible are considered abnormal, and render theobservation possible.Definition 5.2 Let a an excuse for /3. a is a preferred excuse for if there is no excusea' such that a' < a (namely, there is no a' such that M b(a ^ Oa') A Z>+ (a' A ^—,a)).dKMR define a minimal diagnosis as a diagnosis consisting of minimal set A C COMPSof components assumed to be working abnormally, given the system description and theobservation. We can show formal correspondence between preferred excuses and minimaldiagnoses.Theorem 5.3 a is a preferred excuse for ,0 if a A -y is a minimal diagnosis,where a = A i ab_ci for ci E A, and y = Ai —,ab_ci for ci E COMPS—A.We have the following obvious corollary, that asserts that whenever there is an excuse for0, there is always some preferred excuse assuming a minimal set of abnormal components.Corollary 5.4 If there is some excuse for 13 then, there is a' a preferred excuse for 13.The empty diagnosis is the only minimal diagnosis when the observation does not conflictwith what the system should do if all its components were behaving correctly. That is,if there is nothing wrong there is no reason to conjecture a faulty component.Proposition 5.5 a = T is a preferred excuse for iff SD —0 and SDU{-iab(c)}is consistent for all components c E COMPS.de Kleer Mackworth Reiter observed the following when the system description allowsfault models and/or exoneration axioms. Not every superset of the faulty componentsinvolved in a minimal diagnosis need provide a diagnosis. Let's modify the previous bulbexample. Let's assume two bulbs, and the following system description (which includesa description of the system behaviour when components are faulty):Chapter 5. Capturing Consistency Based Diagnosis^ 85-,ab_bulbl A -'ab_bulb2 D bright_light ab_bulbl A ab_bulb2 D darkLet's add that tenuous light, bright _light and dark are mutually inconsistent. ab_bulbl A-'ab_bulb2 is a minimal diagnosis for tenuous light and so is (ab_bulb2 A --iab _bulbl);however, ab_bulbl A ab_bulb2 is not a diagnosis for tenuous light.Consider the set of defaults D = {-ab_bulbl, -,ab_bulb2} and the correspondingmodel MD . Then, MD SD A ab_bulbl^-itenuous_light, MD^SD A ab_bulb2 7$.-tenuous light; however, MD^SD A ab_bulbl A ab_bulb2^--itenuous _light. The ex-ample demonstrates the following proposition.Proposition 5.6 If a is an excuse for 3, (a A a') need not be an excuse, where a =A i ab_ci for ci E A, and a' = Aj ab_ci for cj E A', for any A' C COMPS.We can characterize minimal diagnosis as preferred excuses in MD . While an ordinaryexcuse should render the observation consistent, a preferred excuse should be as normalas possible. However there could be several scenarios consistent with the observationthat assume a minimal number of failing components. The next theorem uses the weakconditional connective -p, that allows us to reason with incomparable scenarios. Let'srecall that the conditional B^C is read as "at some maximal set of most normalworlds where B is true, C is also true". The assertion B^C is perfectly consistentwith the existence of other most normal situations where B holds, but C does not. Inour semantic model, we can identify preferred excuses exactly when they are entailed bysome maximal scenario where the observation holds.Theorem 5.7 . MD SD A 3 --4 a if f a A y is a minimal diagnosis for 13.where a = A i ab_ci for ci E A and y = A3 -, ab_ci for ci E COMPS - A.The set of all preferred excuses gets naturally identified.Corollary 5.8 Let W ={ a s.t. MD SD A ,3^a, where a = A i ab_ci for ci E A}.MD^SD A^VT if for each a E ‘11, any is a minimal diagnosis for 3, s.t.= Ai -iab_cj for cj E COMPS - A.Chapter 5. Capturing Consistency Based Diagnosis^ 86Our characterization of preferred excuses seems intimately related with dKMR's char-acterization of minimal diagnosis in terms of minimal conflicts. Given SDUOBS, theydefine a conflict as a disjunction of ab-literals entailed by SDU OBS. When SD and OBSare propositional, a conflict is an ab-clause which is an implicate of SDU OBS. A minimalconflict is any ab-clause which is a prime implicate of SDU OBS. A minimal conflict ispositive if its ab-literals are all positive. Their principal theorem characterizing mini-mal diagnosis states that a A 'y is a minimal diagnosis iff a is a prime implicant of theset of positive minimal conflicts, where a = A i ab_ci for ci E A and -y = A; forE COMPS — A. Since preferred excuses have absolute correspondence with minimaldiagnosis, then, we dKMR's characterization of all minimal diagnosis should hold for allpreferred excuses. Let H be the set of all positive conflicts of SDUOBS. For each element(clause) it E 11 we have (SDUOBS 7r). The following relation seems to hold for eachconflict 7r and any excuse a:Mr, ri0(7 A b(ir D a)).It seems obvious that the R-minimal worlds in MD where all 7r E 11 hold characterizesthe set of preferred excuses. In other words, the R-minimal worlds where the conjunctionof all minimal conflicts hold (A H) characterizes precisely the disjunction of all minimaldiagnoses (V tIf, for W the set of all minimal diagnoses).5.2 On the Relation between Consistency Based and "Abductive" DiagnosisWe have mapped the consistency based diagnosis framework on a Theorist model MD , fora set of defaults D =^—,ab_cn} . By assuming .T = SD, and a set of conjecturesC = {ab_ci , ab_cn l, we are able to draw legitimate comparisons between the diagnosesarising from the two frameworks. We can show that if a is a Theorist explanation forin MD , then a is an excuse for /3.Proposition 5.9 If^SD A a^3 then MD SD Aa#Chapter 5. Capturing Consistency Based Diagnosis^ 87While the result is trivial, the proposition states the following. Given the same system de-scription —descriptive enought to draw a Theorist is explanation for 0— then, the sameTheorist explanation is an excuse (i.e. a diagnosis in consistency based). We concludethat the "abductive" explanation is logically stronger than the consistency based expla-nation. However, as David Poole (1990),(1989b) spelled out, the explanations/diagnosesderivable from each framework depend on the knowledge provided in the system descrip-tion.In order to derive diagnoses from the consistency based framework the correct be-haviour of the system (making explicit the -iab-assumptions) has to be defined. In orderto derive diagnosis in Theorist (at least some) fault models should be encoded in thesystem description. It is clear that if no fault models are included in the system descrip-tion SD, that is, SD just axiomatizes the correct behavior of the system, assuming someabnormalities ab_c excuses an observation 0 but will not entail that observation. Namely{A ,EA ab_c} U SD U 0 is consistent, but {A ce ,a, ab_c} U SD K p.We conclude that when enough fault models are included as part of the system descrip-tion, diagnoses arising from the consistency based framework become more "predictive" .Namely, when fault models are encoded, consistency based diagnoses do not just excusethe observation, but are inconsistent with the negation of the observation.Konolige (1992b) extended the consistency based diagnosis framework allowing fordiagnoses that are based not only on "abnormalities". For instance, suppose we considerthat "If the switch is off we expect no light"; however, we don't regard the switch beingoff (or on) an abnormality. Konolige determines a set of possible primitive "causes"consisting of ab-literals and other literals as well. For the two-bulbs example, let's addto the system descriptionswitch_of f J darkLet's consider a set of possible primitive "causes" {ab_bulbl, ab_bulb2, switch_o f f } . Nowswitch_of f explains dark and involves no abnormalities. Konolige draws preferencesamong explanations, based on the notion of "maximizing normality" . Our account ofChapter 5. Capturing Consistency Based Diagnosis^ 88preferences among excuses seems to be related to Konolige's concept of the adjunct of anexplanat ion . 4He also extends dKMR's framework allowing for normality conditions other thanthe expectations of components being normal. These normality conditions are modeledas defaults, and are explicitly stated in the system description. Our mapping of theconsistency based diagnosis framework naturally accounts for these extensions, becomingmore "Theorist like" .4 An explanation A is associated with the set the normality conditions that A violates. Such normalityconditions are collected in what is called the adjunct of A. Then, explanations violating more normalityconditions are not preferred (namely, explanations with minimal -subset related- adjuncts are preferred).Konolige's concept of the adjunct of an explanation is not entirely semantic. For instance, assume thesystem description (considered undefeasible knowledge) consisting of ab_plug D ab_bulb, ab_plug j darkand ab_bulb D dark. The explanation ab_plug is preferred over the explanation ab_plug A ab_bulb, andover ab_bulb arguing that the sentence ab_plug "excuses" ab_bulb.Chapter 6Conclusions6.1 SummaryIn this thesis we presented a general model of explanation based on the revision ofthe epistemic state of a program or agent. A natural ordering on explanations wasprovided based exclusively on semantic criteria. The result was an object-level accountof abduction that respects the inherent defeasibility of explanations.We proposed a notion of explanation relative to the background epistemic state of anagent or program. We first considered the background epistemic state as an agent's beliefsabout the actual state of the world. Explanations were modeled as subjunctive condition-als relative to the agent's epistemic state. We expressed our desiderata on explanationsas hypothetical changes in belief and translated them as subjunctive conditionals viathe Ramsey test. We identified a family of explanations which we called "epistemic ex-planations", modeled by different subjunctive conditional connectives (and respectively,different kinds of changes in belief). Varying in their predictive explanatory power, wedistinguished "predictive", "weak", and "might" explanations. Predictive explanationswere conceived as the strongest in the family and require that the explanation be suffi-cient to induce full belief in the explanandum. This predictive but "defasible" notion ofexplanation generalizes most current accounts, which require some deductive relationshipbetween explanation and observation. "Might" explanations modeled as the weakest ex-planation, just guaranteeing that by believing in the explanation the explanandum notbe discarded (namely, the explanandum be regarded possible).Factual and counterfactual explananda were shown to be distinguishable and explain-able in our framework. In this sense our model of abduction broadens the abilities of89Chapter 6. Conclusions^ 90most abductive frameworks. The majority of existing accounts of explanation do notadmit explanations of counterfactual observations; namely, they must refrain to accountfor explananda that conflicts with the current facts.As Rescher (1978) said "conjectural fancy is limitless"; then, lack preferences in anyaccount of explanations may result chaotic. From the many possible competing explana-tions, some may be quite implausible. We proposed a very natural preference orderingon explanations. Founded on the idea that an explanation should not only make theobservation plausible but itself be maximally plausible, we derived preferences on expla-nations. We based our account of explanation on Boutilier's models for belief revision.The objective belief state of the agent, together with the revision policies (and possi-bly other preferences too) determine a plausibility ordering over possible worlds. Thepreference ordering on explanations in terms of plausibility arose from the plausibilityordering over possible worlds. The same conditional information that accounted for thedefeasibility of explanations induced preferences.We identified that not every sentence satisfying the semantic criteria resembles a"simplest" or "most informative" explanation. We observed that preferences in thisrespect vary among different applications (e.g. natural language, image interpretation),and go beyond semantical considerations. Trivial explanations, explanations includingirrelevant factors, and explanations involving some disjunction with some implausiblebelief fall in this category. Interestingly, these explanations may be circumstantiallypreferred in certain applications. Contrasting to our semantic qualifications we referredto these considerations as pragmatics of explanations, but they haven't been explored toany extent.We then showed how we can capture the Theorist and the consistency based diagnosisframeworks, which are today's canonical AI approaches to abduction based on defaultassumptions. By recasting them in our model of abduction we illustrated the expressivepower and generality our framework. The relation between Theorist explanations andepistemic explanations arose by interpreting the background epistemic state of the agentChapter 6. Conclusions^ 91or program as a theory of expectations or a normative set of defaults. The Theoristframework was captured as a reflexive and transitive Kripke model (CT4O-structure),ranking worlds by counting default rule violations. In a similar fashion we provideda mapping for Brewka's extension of the Theorist system, that contemplates prioritiesamong defaults. Our accomplishment in this aspect goes further than the exercise ofproviding a mapping of these frameworks in terms of possible worlds. We showed howthe Theorist and Brewka's frameworks can be extended to provide predictive explanationsand preferences among explanations.We first identified Theorist explanations with the paraconsistent conditional connec-tive in CT4O, and we drew the relation to weak epistemic explanations. We discussed theweak nature of Theorist explanations, showing them to be in some sense paraconsistent.We proposed a stronger notion of explanation in Theorist (and Brewka) setting: apredictive Theorist/Brewka explanation. This predictive notion was based on the ideathat an explanation together with every maximal set of expectations (defaults) shouldaccount for the observation. We elaborated on the effect of priorities when a defaultframework is used abductively, noticing that predictive explanations become more mean-ingful in the prioritized setting, and also that the number of predictive explanations mayincrease.Our extension of Theorist to account for preferences was based on a simple andprincipled conception. Explanations satisfying more (under set inclusion) expectations(defaults) were preferred. We showed that this notion of preference precisely matches ournotion of preference in terms of plausibility on epistemic explanations. The correspon-dence was immediate given the relation between models for belief revision and models fordefault reasoning ((Boutilier 1992a), (1992c), (1992f)). The theory of expectations (de-faults) induces a fixed ordering over possible worlds, interpreted as a normality ordering.Worlds satisfying more (under set inclusion) expectations (defaults) are more normal inthe ordering. A comparative preference ordering on explanations naturally arose basedexclusively on the conditionals (defaults) sanctioned by the expectation theory.Chapter 6. Conclusions^ 92We then mapped the consistency based diagnosis framework onto a Theorist modelby assuming a set of defaults consisting in each component not being abnormal. Weshowed consistency based diagnoses to be related to "might" epistemic explanations wheninterpreting the background epistemic state as the expectation that each component beworking correctly. By recasting consistency based diagnosis and Theorist on the samekind of model, we were able to highlight connections between the two.We proposed a very clear and natural semantics for our model of abduction, andexpressed our desiderata of explanations as purely logic constraints. The development ofthis thesis was done entirely using existing modal conditional logics for belief revision anddefault reasoning. By using Boutilier's logics CO and CT4O, we inherited a principledsemantics and a logical calculus for our semantic considerations about explanations.6.2 Future ResearchWe have explored very little of what we called the pragmatics of explanation. Morework needs to be done in terms of studying the possibility of filtering explanations toavoid triviality, irrelevant (but consistent) information, background information and theproblem of disjunctions with implausible beliefs. Also, worthy of further investigationis the problem of preferences among explanations in the case of the explanandum beingaccepted or indeterminate in the epistemic state where the inquiry arises. We haveshown that all explanations that are epistemically possible with respect to a backgroundepistemic state are ranked as maximally plausible. Hence the plausibility criterion is notadequate for drawing a preference ordering between epistemically possible explanations.Other criteria might be of use. For instance, Levesque (1989) proposes a syntactic criteriafor simplicity.In our development of epistemic explanations we have committed to providing anexplanation that is accepted (in the epistemic state) whenever the explanandum is ac-cepted. Then, if 0 was already accepted in the agent's epistemic state, whatever reasonfor 0 being accepted should be an explanation for 0. In many cases that explanation canChapter 6. Conclusions^ 93be a disjunction of all possible implicants of /3, or ultimately the trivial explanation. AsBoutilier pointed out, when modeling a notion of scientific explanation, an observation/3 may have been accepted with no explanation for it. Then, when seeking an explana-tion for some already believed explanandum /3, some not yet accepted belief a can be acandidate scientific explanation. A notion of scientific explanation may be modeled byrelaxing our commitment for explanation be believed when explanandum is.Our account of explanation has limited itself to explaining objective beliefs' with otherobjective beliefs. That is, explanation and observation have to be propositional sentences.It would be interesting to allow for an explanandum belonging to the bimodal language(p in LB ). For example, in the question, "Why if postmen were on strike would my letternot arrive?", the object of inquiry is itself a conditional sentence. Along the same lineof generalization, the study of explanations that are conditionals (or other statementsin LB ) may prove interesting. For example, assume the following beliefs: "Fred hatesthe rain" and "If it rains, Fred is unhappy". Suppose "It rains". If we question "Howwould Fred be happy?" , one answer can be "were not raining" . But another explanatoryanswer can be "if it were not the case that if it rains Fred is unhappy". In this case,the denial of a conditional, may provide an explanation. An account of conditionalexplanations allowing a, /3 E LB, would require the machinery of iterated conditionals(nested revisions), formulating a very general account of explanation.Our notion of predictive explanation is based on AGM revision semantics. The AGMrevision models changes in mistaken beliefs about a static world. In contrast, Katsunoand Mendelzon's update semantics focuses on changes in beliefs about a changing ordynamic world. Understanding the dual or "abductive" side of belief updates may giverise to a different notion of explanation. Suppose we know that Fred loves either rockmusic or blues, but not both. We could explain Fred liking rock if we knew that he didnot like blues. Two years later we met Fred at a party and we see him captivated byrock music. What do we conclude about his like for blues? Only if he didn't change his'Objective beliefs are those expressible in the object language.Chapter 6. Conclusions^ 94musical taste, we conclude that he doesn't like blues. By revision semantics, we oughtto assume a static world, and we could explain Fred's not liking blues by his liking rock.But things could have changed. By update semantics, this is not a valid "explanation".A parallel between abduction as belief revision and planning as belief update seemsworthy of study. Revising a belief set with an explanation should make the observation(explanandum) believed. By updating the state of the world by an action, a goal canbe reached. Namely, the interpretation of sequences actions as sequences of updates canlead to a principled semantic approach to planning in AI.On another frontier, following the same line of this work, it seems possible to attackthe counterpart problem of causation, maybe following Lewis's (1973) counterfactualanalysis of causation. Causal relations may be understood as a special kind of a "nor-mative conditional" as opposed to a subjunctive conditional. The following exampleexplains the distinction. Assume the causal relation that "low pressure causes low baro-metric readings", and suppose that "today there is low pressure but the barometer readshigh". Evidently the barometer is malfunctioning. As sanctioned by controllability con-cerns, "low pressure" causes "low barometer reading" . In contrast, solely "low pressure"does not explain (the counterfactual circumstance) "the barometric reading low". This isbecause today the pressure is low, but the barometer reads high. In terms of epistemic ex-planations, "low pressure and barometer not malfunctioning" explains (in a hypotheticalfashion) "low barometer reading".Finally, a comparison of our approach with quantitative frameworks of causation/explanationmay prove to be enlightening.REFERENCES^ 95ReferencesAlchourrOn, C., Ghrdenfors, P., and Makinson, D. 1985. On the logic of theory change:Partial meet contraction and revision functions. Journal of Symbolic Logic, 50:510-530.Alchourr6n, C. and Makinson, D. 1980. Hierarchies of regulations and their logic. NewStudies in Deontic Logic. R. Hilpinien ed. Dodrecht:Reidel, 148:123-143.Boutilier, C. 1990. Conditional logics of normality as modal systems. In Proceedings ofthe Eighth National Conference on Artificial Intelligence, pages 594-599, Boston.Boutilier, C. 1992a. Conditional logics for default reasoning and belief revision. TechnicalReport KRR-TR-92-1, University of Toronto, Toronto. Ph.D. thesis.Boutilier, C. 1992b. A logic for revision and subjunctive queries. In Proceedings of theTenth National Conference on Artificial Intelligence, pages 609-615, San Jose.Boutilier, C. 1992c. Normative, subjunctive and autoepistemic defaults: Adopting theRamsey test. In Proceedings of the Third International Conference on Principles ofKnowledge Representation and Reasoning, pages 685-696, Cambridge.Boutilier, C. 1992d. The probability of a possibility: Adding degrees of belief to condi-tionals. Technical report, University of British Columbia, Vancouver. (Forthcom-ing).Boutilier, C. 1992e. Sequences of revisions: On the semantics of nested conditionals.Technical Report 92-24, University of British Columbia, Vancouver. (submitted toIJCAI-93).Boutilier, C. 1992f. What is a default priority? In Proceedings of Canadian Society forComputational Studies of Intelligence Conference, pages 140-147, Vancouver.Boutilier, C. and Becher, V. 1993. Abduction as belief revision: A model of preferredexplanations. In Proceedings of the Eleventh National Conference on Artificial In-telligence, Washington D.C. To appear.Brewka, G. 1989. Preferred subtheories: An extended logical framework for default rea-soning. In Proceedings of the Eleventh International Joint Conference on ArtificialIntelligence, pages 1043-1048, Detroit.REFERENCES^ 96Chellas, B. F. 1980. Modal Logic: An Introduction. Cambridge University Press, Cam-bridge.de Kleer, J., Mackworth, A. K., and Reiter, R. 1990. Characterizing diagnoses. InProceedings of the Eighth National Conference on Artificial Intelligence, pages 324-330, Boston.de Kleer, J. and Williams, B. C. 1987. Diagnosing multiple faults. Artificial Intelligence,32:97-130.Doyle, J. 1979. A truth maintenance system. Artificial Intelligence, 12:231-272.Essays, C. S. P. P. 1923. Chance, Love and Logic. Kegan Paul, Trench, Turbner &Co.,Ltd., London.Gardenfors, P. 1988. Knowledge in Flux: Modeling the Dynamics of Epistemic States.MIT Press, Cambridge.Gardenfors, P. 1990. Belief revision and nonmonotonic logic: Two sides of the same coin?In Proceedings of the European Conference on Artificial Intelligence, pages 768-773.Gardenfors, P. and Makinson, D. 1991. Nonmonotonic inference based on expectations.To appear.Gettier, E. 1963. Is knowledge justified true belief? Analysis, 23:121-123.Ginsberg, M. L. 1986. Counterfactuals. Artificial Intelligence, 30(1):35-79.Grove, A. 1988. Two modellings for theory change. Journal of Philosophical Logic,17:157-170.Harper, W. L. and Skyrms, B. 1988. Causation in Decision, Belief Change, and Statistics.Kluwer Academic Publishers, Dordrecht, The Netherlands.Hempel, C. G. 1966. Philosophy of Natural Science. Prentice-Hall, Englewood Cliffs,NJ.Hobbs, J. R. 1990. An integrated abductive framework for discourse interpretation. InWorking Notes of the AAAI Spring Symposium Series on Automated Abduction,pages 10-12, Stanford University.REFERENCES^ 97Hughes, G. E. and Cresswell, M. J. 1968. An Introduction to Modal Logic. Methuen,London.Hughes, G. E. and Cresswell, M. J. 1984. A Companion to Modal Logic. Methuen,London.Katsuno, H. and Mendelzon, A. 0. 1991a. On the difference between updating a knowl-edge database and revising it. In Proceedings of the Second International Conferenceon Principles of Knowledge Representation and Reasoning, pages 387-394, Cam-bridge.Katsuno, H. and Mendelzon, A. 0. 1991b. Propositional knowledge base revision andminimal change. Artificial Intelligence, 52:263-294.Konolige, K. 1992a. Abduction versus closure in causal theories. Artificial Intelligence,53:255-272.Konolige, K. 1992b. Using default and causal reasoning in diagnosis. In Proceedings ofthe Third International Conference on Principles of Knowledge Representation andReasoning, pages 509-520, Cambridge.Lehmann, D. 1989. What does a conditional knowledge base entail? In Proceedings ofthe First International Conference on Principles of Knowledge Representation andReasoning, pages 212-222, Toronto.Levesque, H. J. 1984. Foundations of a functional approach to knowledge representation.Artificial Intelligence, 23:155-212.Levesque, H. J. 1989. A knowledge level account of abduction. In Proceedings of theEleventh International Joint Conference on Artificial Intelligence, pages 1061-1067,Detroit.Lewis, D. 1973a. Causation. Journal of Philosophy, 70:556-567.Lewis, D. 1973b. Counterfactuals. Blackwell, Oxford.Lewis, D. 1979. Counterfactual dependance as time's arrow. Nais, 13:455-476.Makinson, D. Handbook in Artificial Intelligence and Logic Programming. Volume II.Chapter 2: General patterns in non-monotonic reasoning. Oxford University Press,Oxford. to appear.REFERENCES^ 98Makinson, D. and Cardenfors, P. 1990. Relations between the logic of theory changeand nonmonotonic logic. In Fuhrmann, A. and Morreau, M., editors, The Logic ofTheory Change, pages 185-205. Springer-Verlag, Berlin.Morris, S. and O'Rorke, P. 1990. An approach to theory revision using abduction. InWorking Notes of the AAAI Spring Symposium Series on Automated Abduction,pages 33-37, Stanford University.Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of PlausibleInference. Morgan Kaufmann, San Mateo.Pearl, J. 1990. System Z: A natural ordering of defaults with tractable applicationsto default reasoning. In Vardi, M., editor, Proceedings of Theoretical Aspects ofReasoning about Knowledge, pages 121-135. Morgan Kaufmann, San Mateo.Peng, Y. and Reggia, J. A. 1990. Abductive Inference Models for Diagnostic Problem-Solving. Springer-Verlag, New York.Pollock, J. L. 1987. Defeasible reasoning. Cognitive Science, 11:481-518.Poole, D. 1988. A logical framework for default reasoning. Artificial Intelligence, 36:27—47.Poole, D. 1989a. Explanation and prediction: An architecture for default and abductivereasoning. Computational Intelligence, 5:97-110.Poole, D. 1989b. Normality and faults in logic based diagnosis. In Proceedings of theEleventh International Joint Conference on Artificial Intelligence, pages 1304-1310,Detroit.Poole, D. 1990. A methodology for using a default and abductive reasonig system.International Journal of Intelligent Systems, 5:521-548.Poole, D. 1991. Representing diagnostic knowledge for probabilistic horn abduction. InProceedings of the Twelfth International Joint Conference on Artificial Intelligence,pages 1129-1135, Sydney.Popper, K. R. 1959. The Logic of Scientific Discovery. Basic Books, New York.Putnam, H. 1970. Is semantics possible? In Kiefer, H. E. and Munitz, M. K., editors,Language, Belief and Metaphysics, pages 50-63. SUNY Press, Albany.REFERENCES^ 99Quine, W. and Ullian, J. 1978. The Web of Belief Random House, New York.Reiter, R. 1980. A logic for default reasoning. Artificial Intelligence, 13:81-132.Reiter, R. 1987a. Nonmonotonic reasoning. Annual Reviews of Computer Science, 2:147-186.Reiter, R. 1987b. A theory of diagnosis from first principles. Artificial Intelligence,32:57-95.Rescher, N. 1978. Peirce's Philosophy of Science: Critical Studies in his Theory ofInduction and Scientific Method. University of Notre Dame Press, Notre Dame.Selman, B. and Levesque, H. 1990. Abductive and default reasoning: A computationalcore. In Proceedings of the Eighth National Conference on Artificial Intelligence,pages 343-348, Boston.Stalnaker, R. C. 1968. A theory of conditionals. In Harper, W., Stalnaker, R., andPearce, G., editors, Ifs, pages 41-55. D. Reidel, Dordrecht. 1981.Stickel, M. E. 1990. A method for abductive reasoning in natural-language interpretation.In Working Notes of the AA AI Spring Symposium Series on Automated Abduction,pages 5-9, Stanford University.Appendix AProofs of Theorems Chapter 3Proposition 3.3 Let a be a predictive explanation for # such that a is indeterminatein K. Then, Predict and Absent are equivalent.Proof a, -,a 0 K. By EpStatus, 13,-0 0 K. Then, M a # iffM B(a D 0) iffM^B(-10 D --,a) iffM -,0 -'a.Proposition 3.4 Let a be a predictive explanation for /3, such that -'/3 E K. Then,---,0 E (1C93 )!,„ iff M H 0^a.Proof M^B---,a, B-0, a^/3. IIK:o II = IIKII U Pl(/3). Then, a 0 IC:0 , therefore,(KT,# )!,a is a consistent revision. Then,MH13aifffor every w E Pl(/3), w a iff(# D a) E K=,-,3 iff(-icx D --0) E K=0 iff-Ifi E (K=,-0 )!,a .Proposition 3.5 Let a be a predictive explanation for /3, such that /3 E K. Then,a E (K;)sh iff M H -,a -O.Proof M^Ba, B/3, -'/3^-'a. IIK;11 = IIKII U Pl(-,a). Then, -'/3 0 Kam. , therefore,(K;); is a consistent revision. Then,M -la nO ifffor every w E Pl(-, a), w^-i/3 iff(-ict D -0) E K; iff(0 D a) E K; iffa E (1(;)73 .Proposition 3.6 Let a be a predictive explanation for /3, such that /3 is indeterminatein K. Then, Correl and Cover are equivalent.100Appendix A. Proofs of Theorems Chapter 3^ 101Proof /3, 73 0 K. By EpStatus a, -ia 0 K. Then,M 0 a iff M B(0 D a) iffM B(-ia D -10) iffM -,a -0.Proposition 3.7 /3 is always a preferred (quasi) -predictive explanation for /3.Proof According to Definition 3.7 /3 is a preferred explanation for /3 if there is noexplanation a such that a < 0.Suppose there is as (quasi)-predictive explanation a such that a < /3. Then asatisfies M a beta, so every R-minimal a satisfies /3; but this contradictsa < ,3. Then such a can not exist.Proposition 3.8 For any predictive or quasi-predictive explanation a for , 3, /3 < a.Proof If a is a quasi-predictive or predictive explanation, then M a /3. Then eachR-minimal a-world is a /3-world. Then, M ti(a D 00).Proposition 3.9 Leta be a (quasi) -predictive explanation for ,3. a < /3 iff M /3 7/-- -,a.Proof By hypothesis, M a /3.M6 /3 71-- -,a ifat each minimal /3-cluster there is some a-world ifM b(0 D 0a).Proposition 3.10 a is a preferred quasi-predictive explanation for /3 iff a is a preferredpredictive explanation for /3.Proof (left to the right). Let a be a preferred quasi-predictive explanation for /3; thena, /3 satisfy Conditions Commit, Predict and Absent.By Predict a /3, then b(a D 00, hence a < /3.By Proposition 3.8/3 is a preferred quasi-predictive explanation for /3, then a /3;so a < 13 and 0 < a.Then, if -'B-i/3 then there is at least a /3-world in IIKII,then since a < /3, -43-0 D -43-,a.By contraposition, B-ia D B-0.And, by Absent, B-10 D B-iaby Commit, B/3 D Ba, andby Predict, Ba D B/3.Appendix A. Proofs of Theorems Chapter 3^ 102Then (Ba B/3) A (B-la a- B-,0), thus a satisifies Epstatus, hencea is a preferred predictive explanation for /3The proof right to left is trivial.Proposition 3.11 Let --,3 ft K, (i.e, /3 accepted or indeterminate), and a, a' any pre-dictive explanations for /3. Then, a < a' and a' < a.Proof By hypothesis -10 0 K. By EpStatus -la, -'a' 0 K. Then there is some v, w EIIKII such that w a, and some v = a'. v, w are R-minimal worlds in M. Then,wRv and wRv, so a < a' and a' < a.Proposition 3.12 Let -'/31 cl K. If a, a' are predictive explanations for /3, then a, a'are equally plausible in 111::0 .Proof (sketch) We present the case for explanandum indeterminate in K. Exactly thesame reasoning applies if /3 is accepted in K.Let /3 be indeterminate in K. Then, there are some /3-worlds in the minimal clusterin M. As a, a' are predictive explanations for /3, then a, a' are also indeterminatein K. Then there are some a-worlds and some a'-worlds in the minimal cluster inM.Let M: f3 the model after the revision of K by 73. Then, the minimal cluster in ilt,',3is formed by all --10-worlds satisfying --,a, -la', since by hypothesis M = -13 - , a,M k --0 -, a'.According to the natural revision function, the next to the minimal cluster is formedprecisely by all the /3-worlds from K. Among those /3-worlds are the a-worlds andthe a'-worlds. Then M:0 = tl(ce' D 0a), and 111:;0 = ti(a D Oa'). Thus a, a' areequally preferred.Proposition 3.13 A trivial explanation for /3 is a predictive covering explanation for /3.Proof The proof is trivial. /3 has the same epistemic status as /3. Besides, Predict and Ab-sent, Gomel and Cover, are trivially satisfied since M /3 /3 and M = -,0 73(ID is a theorem in CT4O, and CO).Appendix BProofs of Theorems Chapter 4Proposition 4.1 MD is a CT40* model.Proof We have to show that R is reflexive and transitive; this is obvious from defini-tion 4.2.wRw for all w E W since V(w) C V(w); then R is reflexive.Assume wRv and vRu. Then, V(w) C V(v), and V(v) C V(u). Therefore V(w) CV(u); so wRu. Hence R is transitive.Proposition 4.2 Let MD = (W, R, cp) be the Theorist model for D. Let each singledefault formula d E D be satisfiable. MD possesses a single R-minimum cluster if D isconsistent.Proof Suppose w, v are minimal in R. Since D is consistent both V(w) = 0 and V(v) =0. So wRv and vRw.there is a unique minimal cluster.Lemma 4.3 S is an extension of (X ,D) if there is a minimal X -cluster that characterizes S.Proof (left to right) Assume S is an extension of (X,D), and let IISII C W the propo-sition denoted by S in MD .S = Cn(X U D), s.t. D is a maximal subset of D consistent with X, theneach w E IISII , w X and w D, soeach w E IISII violates the same defaults d' E (D — D), thusfor any v, w E 11811, V(w) = V(v), hence wRv and vRw.Since D is a maximal subset of D consistent with X, then there can be no u E W,uX,uH D' such that D C D' C D. Then, IISII is an R-minimal X-cluster.(right to left) Let IISII C W a minimal X-cluster in MD .Since IISII is a cluster, for every u, w E IISII wRu and uRw, thus V(w) = V(u),thenu, w violate the same defaults; hence, u, w satisfy the same defaults from D.Since HMI is an X-cluster minimal in R, then for each w E IISII103Appendix B. Proofs of Theorems Chapter 4^ 104w X, and for every other v E W such that wRv but not vRw, v i k X, thenif V(w) C V(v) then v does not satisfy X , thenw D such that D is a maximal subset of D consistent with X. Hence,11,511 characterizes S = Cn(X U D) s.t. D is a maximal subset of D consistent withX,thus, S is an extension of (X, D).Theorem 4.4 y is predicted in Theorist sense from (F, D) iff MD F -y, and F issatisfiable.Proof -y is predicted in Theorist sense iff7 belongs to all extensions of (.7 ,D) and .7. consistent iffby Lemma 4.3, 'y is satisfied by each R-minimal F-cluster in MD and F satisfiableiffby Proposition 2.10, MTh F^-y and F satisfiable.Theorem 4.5 Let D C D and C C C. D U C is a Theorist explanation for 13 iffMD (Y. U C) -4 /3 and (F U C) is consistent.Proof D U C is a Theorist explanation for /3 iffF U D U C C131., /3 and .7- UDUC is consistent iffby Poole's theorem 2.1, /3 is in some extension of ((,F U C), D) iffby Lemma 4.3, there is an R-minimal (F U C)-cluster in MD satisfying /3, iffby Proposition 2.11 MD (.7" U C) -- /3, and (.7- U C) is consistent.Corollary 4.6 If .F ICPL -0 then there is no C such that MD (..7. U C) -- 0 and(.7- U C) is consistent.Proof We show the contrapositive of the assertion. Namely, if /3 is explainable then.7- K -0.Assume /3 is explainable. By theorem 4.5, there exists C such that MD (.T U C) —4and (F U C) is consistent.Then, there exists w E W such that MD „ (F U C U beta);so, there exists a world w satisfying F and /3; then, F K -0.Proposition 4.7 If MD = F . /3 and F is satisfiable then (a) /3 is explainable withno conjectures, and (b) -'/3 is not explainable with no conjectures.Proof Assume MD k F /3, and F satisfiable.Appendix B. Proofs of Theorems Chapter 4^ 105(a) we have to show that MD^F^/3, but this is obvious since AB j A^B is a theorem in CT4O.(b) Since MD^F^/3, by Proposition 2.10 every minimal F-clustersatisfies /3.Then, there is no minimal F-cluster that satisfies -, 13, while F is satisfi-able. By Proposition 2.11, MD FBy theorem 4.5, -1 /3 is not explainable from (F, D, {}) .Theorem 4.8 C is a predictive explanation for if MD (.1 U C) #, and (F U C)is consistent.Proof C is a predictive explanation for /3 iff#' belongs to every extension of ((F U C), D) iffby Lemma 4.3, /3 is satisfied by every R-minimal (F U C)-cluster in MD iffby Proposition 2.10, MD^U C)^/3.Proposition 4.9 Let C C C. If C is a predictive explanation for /3 then (a) there is aTheorist explanation for /3 assuming C; and (b) -1# is not explainable assuming C.Proof By hypothesis C is a predictive explanation for /3.Then, MD (.7* U C)^and (F U C) is consistent.(a) Since A^A^B is a theorem in CT40, then (.F U C)^D^U C)By theorem 4.5 there is D C D, such that C U D) is an explanation for(b) By Proposition 2.10 all R-minimal (FU C)-clusters in MD are /3-clusters.Then no minimal (F U C)-cluster verifies - , 13.by Proposition 2.11 MD^U C)by theorem 4.5 there is no D E D such that C U D is a Theorist expla-nation for -i/3.Proposition 4.10 MB is a CT40* model.Proof We have to show that R is reflexive and transitive.For every w E W wRw iff Vi, 1 < i < n^=^By definitions 4.5 and 4.7, R isreflexive.Assume wRv, and vRu.There are three possible cases:Appendix B. Proofs of Theorems Chapter 4^ 106(a) min(u, v) = min(v, w)Vmin(") C^and vvniin(u ,v) c v:in(um,then min(u, w) = min(u, v) = min(v, w), andVm in ( um ) C min(u,w) and Vk = V' Vk,1 < k < min(u, v); hence, wRu.(b) min(u, v) > min(v, w)Vum in (" ) C Vmin(u 'v) , and Vk^Vk, 1 < k < min(u, v);in particular, Vumin(v9w) = Vmin(v,w)Vmin(v 'w) C Vjunin(v 'w) , then Vum in(vm) C Vt nin(vm )then min(u, w) = min(v, w)and Vk, 1 < k < min(v, w), Vk = Vk = Vtvk ; hence, wRu.(c) min(u, v) < min(v, w)Vmin(v ,w) C Vtr iri("v) , and Vk = Vk,, Vk, 1 < k < min(v, w);in particular, vmin(u,v ) = vimin (u,v)uVm in (" ) c Vum in (" ) , then Vmin (u'v ) C V: in (u'v )then min(u, w) = min(u, v)and Vk, 1 < k < min(u, v), Vk = Vk 17,1:; hence, wRu.Lemma 4.11 S is an extension of (X, B) if there is a minimal X -cluster characterizing S.Proof The proof is exactly alike the one of Lemma 4.3.Proposition 4.12 Let each single default formula d E B be satisfiable. MB possesses asingle R-minimum cluster if B is consistent.Proof The proof is exactly alike the one of Proposition 4.2.Theorem 4.13 I- Bs 7 if MB F -y , and F satisfiable.Proof .F 1Bs -y ifevery extension of (.F, B) contains y and .7' is consistent ifby Lemma 4.11, every R-minimal F-cluster satisfies -y and F is satisfiable ifby Proposition 2.10, MB F 7, and F satisfiable.Theorem 4.14 .7. U a haw 0 if MB (F A a)^and (F A a) satisfiable.Appendix B. Proofs of Theorems Chapter 4^ 107Proof J U a I— Bw iffsome extension of ((.T U a), 5) contains /3 and TU a is consistent iffby Lemma 4.11, some R-minimal F A a-cluster satisfies iffby Proposition 2.11, MB (F A a)^0, and (F A a) satisfiable.Proposition 4.15 If wRDv then wRBv.Proof Since D = U7_ 1 8i , then for every u E W V(u) = UTiL iVi!Assume wRDv. By definition 4.2 V(v) C V(w), thenC Vw , Vi, 1 < i < n, then wRBv.Proposition 4.16 MD and MB have the same clusters.Proof We have to show that for any v, w E W wRDv and vRDw iff wRBv and vRBw.By Proposition 4.15, if wRDv and vRDw then wRBv and vRBw.By definition 4.7 if wRBv and vR8w then .17,^Vi, 1 < i < nSince D = U4 1 131 i then for every u E W V(u) = U11_ 1 1/j; then,V(v) = V(w); thus wRDv and vRvw.Proposition 4.17 Every RB -minimal cluster in MB is a RD -minimal cluster in MD .Proof By Proposition 4.16 MB and MD possess the same clusters.Since D =^then for every u E W V(u) = U7_ 1 17,1, then,Let U C W a cluster in MD that is not RD-minimal.Then there is some RD-minimal world w E W, w U, such that for each u E U,uRDw and not wRDu ifffor each u E U, V(w) C V(u), thenViT in(w'' ) c Vr in (") iffby definition 4.7, for each u E U, uRBw but not wRBu, thenU is not an RB-minimal cluster in MB.Proposition 4.18 If D is consistent, then MD and MB have the same unique minimalcluster.Proof Assume D is consistent.By Propositions 4.2, and 4.12, MD and MB have a single minimal cluster.Then, for every u such that V(u) = 0 u is in the R D-minimal cluster.Since D = U2 1 131 , then for every u E W V(u) =Hence, MD and MB have the same unique minimal cluster.Appendix B. Proofs of Theorems Chapter 4^ 108Proposition 4.19 If MD a /3 then MB a /3.Proof If MD a /3 then every RD-minimal a-cluster satisfies /3;By Proposition 4.17 every R8-minimal a-cluster in MB is a RD-minimal a-clusterin MD.Since every every RD-minimal a-cluster in MD satisfies /3, then each RB-minimala-cluster satisfies /3, then,by Proposition 2.10 MB a 0.Proposition 4.20 If MB a--.– 0 then MD a.—*0.Proof Assume MB a --4 /3by Proposition 2.11, there is some RB-minimal a-cluster in MB satisfying /3;by Proposition 4.17, every RB-minimal cluster in MB is an RD-minimal cluster inMD,so there is some RD-minimal a-cluster in MD satisfying 0,then by Proposition 2.11 MD a ---> /3.Theorem 4.21 Let a, a' be predictive explanations for /3. a <g- a' if M^ti((a' AF) J 0(a A F)).Proof By hypothesis (F A a)^/3, (F A a')^/3, and (F A a), (F A a') are satisfiable.a <g- a' iffeach maximal set of defaults consistent with F A a' is contained in some maximalset of defaults consistent with a ifeach R-minimal (F A a')-world w has access to some R-minimal (F A a)-world v,namely wRv ifM b ((a' A F) D 0(a A F)).Corollary 4.22 The preference relation <g- is reflexive and transitive.Proof This is evident since Boutiler's plausibility ordering is reflexive and transitive.Proposition 4.23 Let a a predictive explanation for /3, then /3 < 7- a.Proof By hypothesis (F A a) /3, thenby Proposition 2.10, every R-minimal (F A a)-cluster, satisfies /3, theneach (F A a)-world has access to some R-minimal (F A a A /3)-world, thenM ti((F A a) D 0(F A /3)).Appendix CProofs of Theorems Chapter 5Theorem 5.1 a is an excuse for /3 if a A -y is a diagnosis for /3, where a = A i ab_cifor ci E A, and -y = A; -iab_ci for ci E COMPS - A.Proof Let a = A i ab_ci for ci E A CCOMPS.a is an excuse for /3 iffMD SD A a -1 /3 iffthere is some w E W such that w is a R-minimal SDAa-world, and w satisfies 3 iffthere is some w E W such that w SD A a A /3 and w violates minimal set ofdefaults consistent with SDAa, namely w y, y = A; -lab_ci for cj E COMPS - AiffSD A a A-y A-- ,0 is satisfiable iffa is a diagnosis for /3.Proposition 5.2 There exists an excuse for /3 if SDA0 is satisfiable.Proof There is no a such that SDAa^iffthere is no w E W such that w is a R-minimal SD A a-world satisfying /3 ifffor every w E W such that w SD, then w = SD A a, for different a; hence,there is no w E W, satisfying SD A /3,iff SD A is not satisfiable.Theorem 5.3 a is a preferred excuse for /3 if a A -y is a minimal diagnosis,where a = A 2 ab_ci for ci E A, and -y = A; —tab_c; for cj E COMPS - A.Proof According to the definition 4.2, each cluster in MD satisfies satisfies the samedefaults. As defaults have the form -'ab_c3 and excuses have the form A ab_ci ; then,each cluster uniquely determines an excuse "complementary" to the conjunction ofall the normality assumptions in that cluster.a is a preferred excuse for /3, a = A i ab_ci for ci E A iffa is an excuse for /3 and there is no excuse a', such that (SD A a') < (SD A a) inMD iff109Appendix C. Proofs of Theorems Chapter 5^ 110a is an excuse for /3 and there is no excuse a' satisfying strictly more defaults thana iffa is an excuse for and there is no excuse a' = A i ab_ci such that for ci E^C Aiffa A -y is a diagnosis for (theorem 5.1), and for no proper subset A' C A is a' A -y' adiagnosis (where a' = A i ab_ci for ci E A' and y' = Ai -Iab_cj for ci E COMPS-A')iffa A -y is a minimal diagnosis.Proposition 5.5 a = T is a preferred excuse for /3 if MD SD^and SDU{-iab(c)}is consistent for all components c E COMPS.Proof MD SD O. and MD T SD iffthere is some minimal SD-world w in MD such that V(w) =(w violates no defaults D) and w^iffa = T is an excuse for /3 and there is no other a' involving strictly less abnormalitiesiffa = T is a minimal diagnosis for /3.Theorem 5.7 MD SD A /3^a iff a A -y is a minimal diagnosis for /3.(where a = A i ab_ci for c2 E A and -y = A; -, ab_ci for ci E COMPS - A).Proof Since MD divides worlds into clusters that satisfy the same defaults, then eachcluster characterizes the same excuse.Then 0-clusters are always subclusters of a-clusters.MD ^ SDA/3 -^aiffthere is an R-minimal SDA/3-cluster C satisfying awhere a = A i ab_ci for c2 E A.Then cluster C satisfies -y = A; -, ab_cj for ci E COMPS - A iffSD A /3 A a A -y is satisfiable and for any w E W and for any u E C,such that uRw and not wRu, w -i(SD A 0).Then w is strictly more normal that u, that is, w A a' and w ACEA' -COMPSwhere a' = A i ab_ci for ci E^Cthen, a A -y is a diagnosis for butthere is no a' A that is diagnosis for /3, s.t. a' = A i ab_ci for c2 E^C A and7' = Ai ab_ci for c; E COMPS - C A iffa A -y is a minimal diagnosis for O.Appendix C. Proofs of Theorems Chapter 5^ 111Corollary 5.8 Let .{ a s.t. MD SD A^a, where a = A i ab_ci for ci E A}.MD^SD A^V klf iff for each a E W, a A ry is a minimal diagnosis for /3, s.t.ry = A, -lab_cj for c3 E COMPS - A.Proof Different clusters satisfy different defaults, and a set of defaults determines a setof excuses, then each minimal SDA/3-cluster satisfies a different a.Let W ={ a s.t. MD SD A^a, where a = A i ab_ci for ci E A}.MD SD A^V a iff each R-minimal SDA/3-world satifies V W iffby theorem 5.7, each R-minimal SD A /3-cluster determines a preferred excuse a iffby theorem 5.3 each a A -y is a minimal diagnosis for 0, where a E a = A i ab_cifor ci E A and -y = A3 --iab_ca for cj E COMPS -Proposition 5.9 If MD SD Aa —4 then MD SD Aa0-,(3.Proof A^B D A -B is a theorem in CT4O.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A conditional model of abduction
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A conditional model of abduction Becher, Verónica 1993
pdf
Page Metadata
Item Metadata
Title | A conditional model of abduction |
Creator |
Becher, Verónica |
Date Issued | 1993 |
Description | We propose sometimes very plausible hypotheses as explanations for an observation, given what we know or believe. In light of new information, however, such explanations may become void. Under this view explanations are defeasible. In this thesis we present a general model of explanation in artificial intelligence based on a theory of belief revision, (or the process of expanding, correcting and contracting existing beliefs) which models the dynamics of belief in a given representation. We take seriously the notion that explanations can be constructed from default knowledge and should be determined relative to a background set of beliefs. Based on the idea that an explanation should not only render the observation plausible but be itself maximally plausible, a preference ordering on explanations naturally arises. Our model of abduction (the process of inferring the preferred explanations) uses existing conditional logics for default reasoning and belief revision, based on standard modal systems. We end up with a semantics for explanation in terms of sets of possible worlds, which are simple modal structures also suitable for other forms of defeasible reasoning. The result of this thesis is an object-level account of abduction based on the revision of the epistemic state of a program or agent. Abductive frameworks like Theorist, and consistency based diagnosis (today's "canonical" frameworks for diagnosis) are shown to be captured in our work. |
Extent | 5167110 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2008-08-06 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0051358 |
URI | http://hdl.handle.net/2429/1281 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1993-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1993_spring_becher_veronica.pdf [ 4.93MB ]
- Metadata
- JSON: 831-1.0051358.json
- JSON-LD: 831-1.0051358-ld.json
- RDF/XML (Pretty): 831-1.0051358-rdf.xml
- RDF/JSON: 831-1.0051358-rdf.json
- Turtle: 831-1.0051358-turtle.txt
- N-Triples: 831-1.0051358-rdf-ntriples.txt
- Original Record: 831-1.0051358-source.json
- Full Text
- 831-1.0051358-fulltext.txt
- Citation
- 831-1.0051358.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051358/manifest