Actual Causality
Joseph Y. Halpern% \thanks{Supported in part by NSF under grants IRI-96-25901 and 0090145.}
Dept. of Computer Science
Ithaca
NY 14853
http://www.cs.cornell.edu/home/halpern
Judea Pearl% \thanks{Supported in part by grants from NSF, ONR, AFOSR, and MICRO.}
Los Angeles
CA 90095
http://www.cs.ucla.edu/$\sim$judea
%We propose a new definition of {\em actual causality} %joe1: %jp8: rewording We propose new definitions of %joe18: added (causal) %joe20: made appropriate for part II {\em (causal) explanation}, using {\em structural equations\/} to model counterfactuals. The definition is based on the notion of {\em actual cause\/}, as %joe20 %motivated in a companion paper. defined and motivated in a companion paper. %joe17: added %joe20 %The basic idea is that Essentially, an explanation is a fact that is not known for certain but, if found to be true, would constitute an actual cause of the fact to be explained, regardless of the agent's initial uncertainty. We show that the definition handles well a number of problematic examples from the literature.
actcaus1.tex

%% received 10/2/01
\documentstyle[12pt,chicagob]{article}
%\renewcommand\baselinestretch{1.5}
%\input{spage.tex}
%\input{defn.tex}

\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.25in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
%\setlength{\itemsep}{-\parsep}
\setlength{\itemsep}{0pt}
\renewcommand{\topfraction}{.9}
\renewcommand{\textfraction}{.1}
\setlength{\parskip}{\smallskipamount}

%  THEOREM-LIKE ENVIRONMENTS

\newtheorem{THEOREM}{Theorem}[section]
\newenvironment{theorem}{\begin{THEOREM} \hspace{-.85em} {\bf :} }%
                        {\end{THEOREM}}
\newtheorem{LEMMA}[THEOREM]{Lemma}
\newenvironment{lemma}{\begin{LEMMA} \hspace{-.85em} {\bf :} }%
                      {\end{LEMMA}}
\newtheorem{COROLLARY}[THEOREM]{Corollary}
\newenvironment{corollary}{\begin{COROLLARY} \hspace{-.85em} {\bf :} }%
                          {\end{COROLLARY}}
\newtheorem{PROPOSITION}[THEOREM]{Proposition}
\newenvironment{proposition}{\begin{PROPOSITION} \hspace{-.85em} {\bf :} }%
                            {\end{PROPOSITION}}
\newtheorem{DEFINITION}[THEOREM]{Definition}
\newenvironment{definition}{\begin{DEFINITION} \hspace{-.85em} {\bf :} \rm}%
                            {\end{DEFINITION}}
\newtheorem{CLAIM}[THEOREM]{Claim}
\newenvironment{claim}{\begin{CLAIM} \hspace{-.85em} {\bf :} \rm}%
                            {\end{CLAIM}}
\newtheorem{EXAMPLE}[THEOREM]{Example}
\newenvironment{example}{\begin{EXAMPLE} \hspace{-.85em} {\bf :} \rm}%
                            {\end{EXAMPLE}}
\newtheorem{REMARK}[THEOREM]{Remark}
\newenvironment{remark}{\begin{REMARK} \hspace{-.85em} {\bf :} \rm}%
                            {\end{REMARK}}
%\newenvironment{proof}{\noindent {\bf Proof:} \hspace{.677em}}%
%                      {}

%theorem
\newcommand{\thm}{\begin{theorem}}
%lemma
\newcommand{\lem}{\begin{lemma}}
%proposition
\newcommand{\pro}{\begin{proposition}}
%definition
\newcommand{\dfn}{\begin{definition}}
%remark
\newcommand{\rem}{\begin{remark}}
%example
\newcommand{\xam}{\begin{example}}
%corollary
\newcommand{\cor}{\begin{corollary}}
%proof
\newcommand{\prf}{\noindent{\bf Proof:} }
%end theorem
\newcommand{\ethm}{\end{theorem}}
%end lemma
\newcommand{\elem}{\end{lemma}}
%end proposition
\newcommand{\epro}{\end{proposition}}
%end definition
\newcommand{\edfn}{\bbox\end{definition}}
%end remark
\newcommand{\erem}{\bbox\end{remark}}
%end example
\newcommand{\exam}{\bbox\end{example}}
%end corollary
\newcommand{\ecor}{\end{corollary}}
%end proof
\newcommand{\eprf}{\bbox\vspace{0.1in}}
%begin equation
\newcommand{\beqn}{\begin{equation}}
%end equation
\newcommand{\eeqn}{\end{equation}}
% white box
\newcommand{\wbox}{\mbox{$\sqcap$\llap{$\sqcup$}}}
%black box
\newcommand{\bbox}{\vrule height7pt width4pt depth1pt}
\newcommand{\qed}{\eprf}
\newcommand{\clm}{\begin{claim}}
\newcommand{\eclm}{\end{claim}}
% (not)member of
\let\member=\in
\let\notmember=\notin
% \sub will be used for subscript.
\newcommand{\sub}{_}
% \su will be used for superscript.
\def\su{^}
%right arrow
\newcommand{\rarrow}{\rightarrow}
%left arrow
\newcommand{\larrow}{\leftarrow}
%bold face lower-case letters
%for bold Greek symbols in math mode (with \boldsymbol{\sigma}, etc.)
\newcommand{\boldsymbol}[1]{\mbox{\boldmath $\bf #1$}}
\newcommand{\bolda}{{\bf a}}
\newcommand{\boldb}{{\bf b}}
\newcommand{\boldc}{{\bf c}}
\newcommand{\boldd}{{\bf d}}
\newcommand{\bolde}{{\bf e}}
\newcommand{\boldf}{{\bf f}}
\newcommand{\boldg}{{\bf g}}
\newcommand{\boldh}{{\bf h}}
\newcommand{\boldi}{{\bf i}}
\newcommand{\boldj}{{\bf j}}
\newcommand{\boldk}{{\bf k}}
\newcommand{\boldl}{{\bf l}}
\newcommand{\boldm}{{\bf m}}
\newcommand{\boldn}{{\bf n}}
\newcommand{\boldo}{{\bf o}}
\newcommand{\boldp}{{\bf p}}
\newcommand{\boldq}{{\bf q}}
\newcommand{\boldr}{{\bf r}}
\newcommand{\bolds}{{\bf s}}
\newcommand{\boldt}{{\bf t}}
\newcommand{\boldu}{{\bf u}}
\newcommand{\boldv}{{\bf v}}
\newcommand{\boldw}{{\bf w}}
\newcommand{\boldx}{{\bf x}}
\newcommand{\boldy}{{\bf y}}
\newcommand{\boldz}{{\bf z}}
%bold face upper-case letters
\newcommand{\boldA}{{\bf A}}
\newcommand{\boldB}{{\bf B}}
\newcommand{\boldC}{{\bf C}}
\newcommand{\boldD}{{\bf D}}
\newcommand{\boldE}{{\bf E}}
\newcommand{\boldF}{{\bf F}}
\newcommand{\boldG}{{\bf G}}
\newcommand{\boldH}{{\bf H}}
\newcommand{\boldI}{{\bf I}}
\newcommand{\boldJ}{{\bf J}}
\newcommand{\boldK}{{\bf K}}
\newcommand{\boldL}{{\bf L}}
\newcommand{\boldM}{{\bf M}}
\newcommand{\boldN}{{\bf N}}
\newcommand{\boldO}{{\bf O}}
\newcommand{\boldP}{{\bf P}}
\newcommand{\boldQ}{{\bf Q}}
\newcommand{\boldR}{{\bf R}}
\newcommand{\boldS}{{\bf S}}
\newcommand{\boldT}{{\bf T}}
\newcommand{\boldU}{{\bf U}}
\newcommand{\boldV}{{\bf V}}
\newcommand{\boldW}{{\bf W}}
\newcommand{\boldX}{{\bf X}}
\newcommand{\boldY}{{\bf Y}}
\newcommand{\boldZ}{{\bf Z}}
%double turnstile
\newcommand{\sat}{\models}
\newcommand{\dtur}{\models}
%single turnstile
\newcommand{\infers}{\vdash}
\newcommand{\stur}{\vdash}
%fat right arrow
\newcommand{\rimp}{\Rightarrow}
%fat left arrow
\newcommand{\limp}{\Leftarrow}
%fat double arrow
\newcommand{\dimp}{\Leftrightarrow}
%big or
\newcommand{\bor}{\bigvee}
%big and
\newcommand{\band}{\bigwedge}
%union
\newcommand{\union}{\cup}
%intersection
\newcommand{\inter}{\cap}
%bold letters
\newcommand{\xx}{{\bf x}}
\newcommand{\yy}{{\bf y}}
\newcommand{\uu}{{\bf u}}
\newcommand{\vv}{{\bf v}}
\newcommand{\FF}{{\bf F}}
\newcommand{\natnum}{{\sl N}}
%\newfont{\sqi}{cmssqi8}
\newcommand{\IR}{\mbox{$I\!\!R$}}
\newcommand{\IP}{\mbox{$I\!\!P$}}
\newcommand{\IN}{\mbox{$I\!\!N$}}
\newcommand{\IC}{\mbox{$C\!\!\!\!\raisebox{.75pt}{\mbox{\sqi I}}$}}
%Use $\IC \;\;$
% multivalued arrow
\newcommand{\marrow}{\hbox{$\rightarrow$ \hskip -10pt
                      $\rightarrow$ \hskip 3pt}}
% phi
\renewcommand{\phi}{\varphi}
%\renewcommand{\Diamond}{{\bf Large \diamond}}
\newcommand{\Circ}{\mbox{{\small $\bigcirc$}}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\all}{\forall}
\newcommand{\infinity}{\infty}
%binomial coefficient:
\newcommand{\bc}[2]{\left( \begin{array}{c} #1 \\ #2 \end{array} \right)}
\newcommand{\cross}{\times}
\newcommand{\bigfootnote}[1]{{\footnote{\normalsize #1}}}
\newcommand{\medfootnote}[1]{{\footnote{\small #1}}}
\newcommand{\bd}{\bf}

% Joe's Section

\newcommand{\imp}{\Rightarrow}

%\H, \L, \O, \P and \S already taken; but we're redefining \P anyway
\newcommand{\A}{{\cal A}}
\newcommand{\B}{{\cal B}}
\newcommand{\C}{{\cal C}}
\newcommand{\D}{{\cal D}}
\newcommand{\E}{{\cal E}}
\newcommand{\F}{{\cal F}}
\newcommand{\G}{{\cal G}}
%\newcommand{\H}{{\cal H}}
\newcommand{\I}{{\cal I}}
\newcommand{\J}{{\cal J}}
\newcommand{\K}{{\cal K}}
%\newcommand{\L}{{\cal L}}
\newcommand{\M}{{\cal M}}
\newcommand{\N}{{\cal N}}
%\newcommand{\O}{{\cal O}}
\newcommand{\Ocal}{{\cal O}}
\newcommand{\Hcal}{{\cal H}}
\renewcommand{\P}{{\cal P}}
\newcommand{\Q}{{\cal Q}}
\newcommand{\R}{{\cal R}}
%\newcommand{\S}{{\cal S}}
\newcommand{\T}{{\cal T}}
\newcommand{\U}{{\cal U}}
\newcommand{\V}{{\cal V}}
\newcommand{\W}{{\cal W}}
\newcommand{\X}{{\cal X}}
\newcommand{\Y}{{\cal Y}}
\newcommand{\Z}{{\cal Z}}

\newcommand{\Kone}{{\cal K}_1}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\Ki}{{\cal K}_i}
\newcommand{\Kn}{{\cal K}_n}
\newcommand{\st}{\, \vert \,} %vertical bar with space around it
\newcommand{\stc}{\, : \,} %colon with space around it
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\<}{\langle}
\renewcommand{\>}{\rangle}
\newcommand{\lang}{\mbox{${\cal L}_n$}}
\newcommand{\langd}{\mbox{${\cal L}_n^D$}}

%\renewcommand{\Box}{\mathbin{\vcenter{\hrule
%    \hbox{\vrule \kern .6em
%          \vbox to .6em{}\vrule}\hrule}}\hspace{.17ex}}
\newtheorem{nlem}{Lemma}
\newtheorem{Ob}{Observation}
\newtheorem{pps}{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{crl}{Corollary}
\newtheorem{cl}{Claim}
\newcommand{\pf}{\par\noindent{\bf Proof}~~}
\newcommand{\eg}{e.g.,~}
\newcommand{\ie}{i.e.,~}
\newcommand{\vs}{vs.~}
\newcommand{\cf}{cf.~}
\newcommand{\etal}{et al.\ }
\newcommand{\resp}{resp.\ }
\newcommand{\respc}{resp.,\ }
\newcommand{\comment}[1]{\marginpar{\scriptsize\raggedright #1}}
\newcommand{\wrt}{with respect to~}
\newcommand{\re}{r.e.}
\newcommand{\nind}{\noindent}
\newcommand{\distributed}{distributed\ }
\newcommand{\bn}{\bigskip\markright{NOTES}
%\nind{\bf Notes:} \ }
%\newcommand{\bn}{
\section*{Notes}}
\newcommand{\Exer}{
\bigskip\markright{EXERCISES}
%\nind{\bf Exercises} \ }
\section*{Exercises}}
\newcommand{\DG}{D_G}
\newcommand{\Sm}{{\rm S5}_m}
\newcommand{\Smc}{{\rm S5C}_m}
\newcommand{\Smi}{{\rm S5I}_m}
\newcommand{\Smic}{{\rm S5CI}_m}
\newcommand{\Martin}{Mart\'\i n\ }
\newcommand{\ol}{\setlength{\itemsep}{0pt}\begin{enumerate}}
\newcommand{\eol}{\end{enumerate}\setlength{\itemsep}{-\parsep}}
\newcommand{\ul}{\setlength{\itemsep}{0pt}\begin{itemize}}
\newcommand{\dl}{\setlength{\itemsep}{0pt}\begin{description}}
\newcommand{\edl}{\end{description}\setlength{\itemsep}{-\parsep}}
\newcommand{\eul}{\end{itemize}\setlength{\itemsep}{-\parsep}}
\newtheorem{fthm}{Theorem}
\newtheorem{flem}[fthm]{Lemma}
\newtheorem{fcor}[fthm]{Corollary}
\newcommand{\slidehead}[1]{
\eject
\Huge
\begin{center}
{\bf #1 }
\end{center}
\vspace{.5in}
\LARGE}

%chck macros
\newcommand{\subG}{_G}
\newcommand{\If}{{\bf if}}

\newcommand{\attime}{{\tt \ at\_time\ }}
\newcommand{\hatell}{\skew6\hat\ell\,}
\newcommand{\Then}{{\bf then}}
\newcommand{\Until}{{\bf until}}
\newcommand{\Else}{{\bf else}}
\newcommand{\Repeat}{{\bf repeat}}
\newcommand{\cA}{{\cal A}}
\newcommand{\cE}{{\cal E}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cI}{{\cal I}}
%\newcommand{\IcR}{{\cal I}_{\cal R}}
%\newcommand{\IRca}{{\cal I}_\Rca}
%\newcommand{\Rca}{{\cR_{ca}}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cR}{{\cal R}}
\newcommand{\cS}{{\cal S}}
\newcommand{\BN}{B^{\scriptscriptstyle \cN}}
\newcommand{\BS}{B^{\scriptscriptstyle \cS}}
\newcommand{\cW}{{\cal W}}
\newcommand{\EG}{E_G}
\newcommand{\CG}{C_G}
\newcommand{\CN}{C_\cN}
\newcommand{\ES}{E_\cS}
\newcommand{\EN}{E_\cN}
\newcommand{\CS}{C_\cS}
%\newcommand{\RP}{{\cR_P}}
%\newcommand{\IRP}{{\cal I}_\RP}
%\newcommand{\RSBA}{{\cR_{\it sba}}}
%\newcommand{\IRSBA}{{\cal I}_\RSBA}

\newcommand{\attack}{\mbox{{\it attack}}}
\newcommand{\attacking}{\mbox{{\it attacking}}}
\newcommand{\delivered}{\mbox{{\it delivered}}}
\newcommand{\exist}{\mbox{{\it exist}}}
\newcommand{\decide}{\mbox{{\it decide}}}
\newcommand{\clean}{{\it clean}}
\newcommand{\diff}{{\it diff}}
\newcommand{\Failed}{{\it failed}}
%\newcommand{\RF}{\cR_{\scriptscriptstyle {\cal F}}}
%\newcommand\eqdef{\buildrel {\rm def}\over =}
\newcommand\eqdef{=_{\rm def}}
\newcommand{\true}{\mbox{{\it true}}}
\newcommand{\false}{\mbox{{\it false}}}

%book macros
\newcommand{\DN}{D_{\cN}}
\newcommand{\DS}{D_{\cS}}
\newcommand{\tyme}{{\it time}}
\newcommand{\fp}{f}

%chguide macros
\newcommand{\Kax}{{\rm K}_n}
\newcommand{\Kaxc}{{\rm K}_n^C}
\newcommand{\Kaxd}{{\rm K}_n^D}
\newcommand{\Tax}{{\rm T}_n}
\newcommand{\Taxc}{{\rm T}_n^C}
\newcommand{\Taxd}{{\rm T}_n^D}
\newcommand{\fourax}{{\rm S4}_n}
\newcommand{\fouraxc}{{\rm S4}_n^C}
\newcommand{\fouraxd}{{\rm S4}_n^D}
\newcommand{\fiveax}{{\rm S5}_n}
\newcommand{\fiveaxc}{{\rm S5}_n^C}
\newcommand{\fiveaxd}{{\rm S5}_n^D}
\newcommand{\Dax}{{\rm KD45}_n}
\newcommand{\Daxc}{{\rm KD45}_n^C}
\newcommand{\Daxd}{{\rm KD45}_n^D}
\newcommand{\LP}{{\cal L}_n}
\newcommand{\LCP}{{\cal L}_n^C}
\newcommand{\LDP}{{\cal L}_n^D}
\newcommand{\LCDP}{{\cal L}_n^{CD}}
\newcommand{\MP}{{\cal M}_n}
\newcommand{\MPr}{{\cal M}_n^r}
%\newcommand{\MPrt}{{\cal M}_n^{rt}}
\newcommand{\MPrt}{\M_n^{\mbox{\scriptsize{{\it rt}}}}}
%\newcommand{\MPrst}{{\cal M}_n^{rst}}
\newcommand{\MPrst}{\M_n^{\mbox{\scriptsize{{\it rst}}}}}
%\newcommand{\MPelt}{{\cal M}_n^{elt}}
\newcommand{\MPelt}{\M_n^{\mbox{\scriptsize{{\it elt}}}}}
\renewcommand{\lang}{\mbox{${\cal L}_{n} (\Phi)$}}
\renewcommand{\langd}{\mbox{${\cal L}_{n}^D (\Phi)$}}
\newcommand{\fiveaxdu}{{\rm S5}_n^{DU}}
\newcommand{\LPD}{{\cal L}_n^D}
\newcommand{\fiveaxu}{{\rm S5}_n^U}
\newcommand{\fiveaxcu}{{\rm S5}_n^{CU}}
\newcommand{\LPU}{{\cal L}^{U}_n}
\newcommand{\LPCU}{{\cal L}_n^{CU}}
\newcommand{\LDPU}{{\cal L}_n^{DU}}
\newcommand{\LCPU}{{\cal L}_n^{CU}}
\newcommand{\LPDU}{{\cal L}_n^{DU}}
\newcommand{\LPCDU}{{\cal L}_n^{\it CDU}}
\newcommand{\Cn}{\C_n}
%\newcommand{\CSn}{\I_n^{cs}(\Phi)}
%\newcommand{\CSn}{\I_n^{oa}(\Phi)}
%\newcommand{\CSnm}{\I_n^{oa}}
%\newcommand{\CSnp}{\I_n^{cs}(\Phi')}
\newcommand{\CSnp}{\I_n^{oa}(\Phi')}
%\newcommand{\CSc}{\C_n^{cs}(\Phi)}
\newcommand{\CSc}{\C_n^{oa}(\Phi)}
%\newcommand{\Ccs}{\C_n^{cs}}
\newcommand{\Ccs}{\C_n^{oa}}
%ron
%\newcommand{\CSAX}{CS$_{{{n}},\Phi}$}
%\newcommand{\CSAXN}{CS$_{{{n}},\Phi}'$}
\newcommand{\CSAX}{OA$_{n,\Phi}$}
\newcommand{\CSAXN}{OA$_{n,{\Phi}}'$}
%\newcommand{\IKB}{\I_n^{KB}}
\newcommand{\untill}{U}
\newcommand{\until}{\, U \,}
\newcommand{\amp}{{\rm a.m.p.}}
\newcommand{\commentout}[1]{}
\newcommand{\msgc}[1]{ @ #1 }
\newcommand{\Camp}{{\C_n^{\it amp}}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\rarrowr}{\stackrel{r}{\rightarrow}}
\newcommand{\ack}{\mbox{\it ack}}
\newcommand{\Gz}{\G_0}
\newcommand{\denselist}{\itemsep 0pt\partopsep 0pt}
\def\seealso#1#2{({\em see also\/} #1), #2}
\newcommand{\cents}{\hbox{\rm \rlap{/}c}}


\newcommand{\PrB}{\Pr}
\renewcommand{\S}{{\cal S}}
\newcommand{\ML}{\mbox{{\it ML}}}
\newcommand{\FS}{\mbox{{\it FS}}}
\newcommand{\SE}{\mbox{{\it SE}}}
\newcommand{\Mer}{\mbox{{\it Mer}}}
\newcommand{\Mor}{\mbox{{\it Mor}}}
\newcommand{\MerE}{\mbox{{\it MerE}}}
\newcommand{\MorE}{\mbox{{\it MorE}}}
\renewcommand{\FF}{\mbox{{\it FF}}}
\newcommand{\LL}{\mbox{{\it LL}}}
\newcommand{\LC}{\mbox{{\it LC}}}
\newcommand{\WB}{\mbox{{\it WB}}}
\newcommand{\BMC}{\mbox{{\it BMC}}}
\newcommand{\TT}{\mbox{{\it TT}}}
\newcommand{\TD}{\mbox{{\it TD}}}
\newcommand{\ST}{\mbox{{\it ST}}}
\newcommand{\SST}{\mbox{{\it SST}}}
\newcommand{\SPT}{\mbox{{\it SPT}}}
\newcommand{\SPS}{\mbox{{\it SPS}}}
\newcommand{\LSS}{\mbox{{\it LSS}}}
\newcommand{\BPT}{\mbox{{\it BPT}}}
\newcommand{\HPT}{\mbox{{\it HPT}}}
\newcommand{\MT}{\mbox{{\it MT}}}
\newcommand{\LE}{\mbox{{\it LE}}}
\newcommand{\FB}{\mbox{{\it FB}}}
\newcommand{\AS}{\mbox{{\it AS}}}
\renewcommand{\ES}{\mbox{{\it ES}}}
\renewcommand{\BS}{\mbox{{\it BS}}}
\newcommand{\BH}{\mbox{{\it BH}}}
\newcommand{\BT}{\mbox{{\it BT}}}
\newcommand{\SH}{\mbox{{\it SH}}}
\newcommand{\LT}{\mbox{{\it LT}}}
\newcommand{\RT}{\mbox{{\it RT}}}

\begin{document}

%joe3: cut for UAI
\begin{titlepage}
%joe6*: I'd like to promote explanation more, since I now feel rather
%excited about it.
%\title{Actual Causality}
%jp7: me too, but the  title you suggested sounds like
%we are merely translating an existing definition to the language
%of structural equations. How about the following
%\title{Defining Actual Causality and Explanation Using Structural
%Equations}
%\title{Actual Causation and Causal Explanation}
%jp7: or even "Causes  and Explanations" ? simple  and devastating .
%joe7: I like the last version: how about
\title{Causes and Explanations: A
%joe8: what about the following?
%New
%jp9 fancier:
%joe9: OK
% Structural-Equations
Structural-Model
Approach.
%joe20
Part II: Explanations}
\author{Joseph Y. Halpern%
\thanks{Supported in part by NSF under
grants IRI-96-25901 and 0090145.}\\
Cornell University\\
Dept. of Computer Science\\
Ithaca, NY 14853\\
halpern@cs.cornell.edu\\
http://www.cs.cornell.edu/home/halpern\\
\and
Judea Pearl%
\thanks{Supported in part by grants from NSF,
ONR, AFOSR, and MICRO.}\\
Dept. of Computer Science\\
University of California, Los Angeles\\
Los Angeles, CA 90095\\
judea@cs.ucla.edu\\
http://www.cs.ucla.edu/$\sim$judea
}

%jp8: adding
\date{\today}
%joe: cut for UAI
\setcounter{page}{0}
\thispagestyle{empty}
\maketitle
\thispagestyle{empty}

\begin{abstract}
%We propose a new definition of {\em actual causality}
%joe1:
%jp8: rewording
We propose new definitions of 
%joe18: added (causal)
%joe20: made appropriate for part II
{\em (causal) explanation},
using
{\em structural equations\/} to model counterfactuals.
The definition is based on the notion of {\em actual
cause\/}, as 
%joe20
%motivated in a companion paper.  
defined and motivated in a companion paper.  
%joe17: added
%joe20
%The basic idea is that 
Essentially,
an explanation is a fact
that is not known for certain but, if found to be true,
would constitute an actual cause of the  fact to
be explained, regardless of the agent's initial uncertainty.   
We show that the definition handles well
a number of problematic examples from the literature.
\end{abstract}
%joe3: cut for UAI
\end{titlepage}

%joe20: this section is expanded from the IJCAI paper
\section{Introduction}
The automatic generation of adequate explanations is
a task essential in planning, diagnosis and natural language processing.
A system doing inference must be able to explain its
findings and recommendations to evoke 
%joe20
%confidence on the part of a user.  
a user's confidence.
However, getting a good definition of explanation is a
notoriously difficult problem, which has been studied 
%joe17
%by philosophers, and more recently the AI community, 
for years.
(See \cite{CH97,Gardenfors1,Hempel65,Pearl,Salmon89} and the references
therein for an introduction to and discussion of the issues.)

%joe20
In Part I of this paper \cite{HP01b}
%joe17
%we have given 
we give
a definition of actual causality
using structural equations.  Here we show how the ideas behind that
definition can be used to give an elegant definition of (causal)
explanation that deals well with many of the problematic examples discussed in the
literature.  The basic idea is that an explanation is a fact
that is not known for certain but, if found to be true,
would constitute an actual cause of the {\em explanandum\/} (the fact to
be explained), regardless of the agent's initial uncertainty.   

%joe20
Note that our definition involves causality and knowledge.
Following G\"ardenfors \citeyear{Gardenfors1}, we take the notion of
explanation to be relative to an agent's epistemic state.  What counts
as an explanation for one agent may not count as an explanation for
another agent.  We also follow G\"ardenfors in allowing explanations to
include (fragments of) a causal model.  To borrow an example from
G\"ardenfors, an agent seeking 
an explanation of why Mr.\ Johansson has been taken ill with lung cancer
will not consider the fact that he worked for years in asbestos
manufacturing a part of an explanation if he already knew this fact.
%joe23
%On the other hand, for such an agent, an explanation of
For such an agent, an explanation of Mr.~Johansson's illness may
include a causal model describing  the connection between asbestos
fibers and lung cancer.  On the other hand, for someone who already
knows the causal model but does not know that Mr.\ Johansson worked in
asbestos manufacturing, the explanation would involve Mr.\ Johansson's
employment but would not mention the causal model.

%Where our definition differs from that of G\"ardenfors (and all other in
%jp0 others
Where our definition differs from that of G\"ardenfors (and all others in
the literature) is in the way it is formulated in terms of 
%joe23
%the underlying notion of causality.   This definition is not based on
%jp0 elaborating in the next few lines.
%an underlying notion of causality.   The definition is not based on
the underlying notions of knowledge, causal models, actual
causation, and counterfactuals. The definition is not based on
probabilistic dependence, ``statistical relevance'', or
logical implication, and thus
is able to deal with the directionality inherent in common explanations.
While it seems reasonable to say ``the height of the flag pole explains 
the length of the shadow'', it would sound awkward if one
were to explain the former with the latter.  Our definition is able to
capture this distinction easily.

The best judge of the
adequacy of an approach are the intuitive appeal of the definitions and
how well it deals with examples; we 
%joe13:
%hope this paper shows that our
believe that this paper shows that our
approach fares well on both counts.


The remainder of the paper is organized as follows.  In
Section~\ref{sec:models}, we review the basic definitions of causal
models based on structural equations, which are the basis for our 
definitions of causality and explanation, and then review the definition
of causality from the companion paper.  We have tried to include enough
detail here to make the paper self-contained, but we encourage the
reader to consult the companion paper for more motivation and discussion.
In Section~\ref{sec:explanation} we give the basic definition of 
%joe24
%explanation. We first give the basic definitions under the assumption %that
explanation, under the assumption that
the causal model is known.
In Section~\ref{s:partialexp}, probability is added to the picture, to
%joe+
%give a 
%  We also show how probability can be used to 
give notions of {\em partial explanation} and {\em explanatory power}.
The general definition, which dispenses with the assumption that the
causal model is known,
%joe24
is discussed in Section~\ref{sec:general}.
We conclude in Section~\ref{sec:discussion} with some discussion.

\section{Causal Models and the Definition of Actual Causality: A
Review}\label{sec:models} 
To make this paper self-contained, this section repeats material
%joe20: more line shaving
%from the companion paper; we
from the companion paper; we
review the basic definitions of causal models,
as defined in terms of structural equations, 
the syntax and semantics of a language for reasoning about
causality and explanations, and the definition of actual cause.

\subsection{Causal models}

The use of structural equations as a model for causal relationships
is standard in the social sciences,
and seems to go back to the work of Sewall Wright in the 1920s (see
\cite{Goldberger72} for a discussion);
the particular framework that we use here
is due to Pearl \citeyear{Pearl.Biometrika}, and is further developed in
%joe19:
%\cite{GallesPearl97,galles:pea98,Hal20,pearl:2k}.  
\cite{pearl:2k}.  

The basic picture 
%joe20
%here 
is that the world is described by random variables,
some of which may have a causal
influence on others. This influence
is modeled by a set of {\em structural equations}.
%joe20
%, where each
Each equation represents a distinct mechanism (or law) in the
%joe20
%world, one that may be modified (by external actions) without
world, which may be modified (by external actions) without
altering the others.
%continue with: "In practice, ..."
In practice, it
seems useful to split the random variables into two sets, the {\em
exogenous\/} variables, whose values are determined by factors outside
the model, and the {\em endogenous\/} variables,
%joe20
whose values are ultimately determined by the exogenous variables.
It is these endogenous
variables whose values are described by the structural equations.

%jp0. Joe, I think the next three paragraphs should be taken
%from the final revision of part I, where they have a clearer
%relation to the "closest world" paradigm.
%joe26: OK; made some minor changes to make it consistent with the final
%version.
Formally, a {\em signature\/} $\S$ is a tuple $(\U,\V,\R)$,
where $\U$ is a 
%joe26
%finite 
set of exogenous variables, $\V$ is a finite 
set of endogenous variables,
and $\R$ associates with every variable $Y \in
\U \union \V$ a nonempty set $\R(Y)$ of possible values for $Y$
(that is, the set of values over which $Y$ {\em ranges}).
%A {\em causal model\/} (or {\em structural model\/})
A {\em causal\/} (or {\em structural\/}) {\em model\/} 
over signature $\S$ is a tuple $M=(\S,\F)$,
where $\F$ associates with each variable $X \in \V$ a function denoted
$F_X$ such that $F_X: (\times_{U \in \U} \R(U))
\times (\times_{Y \in \V - \{X\}} \R(Y)) \rightarrow \R(X)$.
%joe23: made the same changes as in Part I
$F_X$ determines the value of $X$
given the values of all the other variables in $\U \union \V$.
%joe26: rewrote as in part I
%For example, if $F_X(Y,U) = Y+U$ (which we usually write as $X=Y+U$), then
%if $Y = 3$ and $U = 2$, then $X=5$. 
For example, if $F_X(Y,Z,U) = Y+U$ (which we usually write 
as $X=Y+U$), then if $Y = 3$ and $U = 2$, then $X=5$,
regardless of how $Z$ is set.

These equations can be thought of as representing 
%joe26
%physical 
processes (or mechanisms) by which values are assigned to
variables.  Hence, like physical laws, they support a
counterfactual interpretation.  For example, the equation above
claims that, in the context $U = u$,
if $Y$ were $4$, then $X$ would
be $u+4$ (which we write as $(M,u) \sat 
%joe+
%[Y \gets 4](X=u+4)$), regardless of what value 
[Y \gets 4](X=u+4)$), regardless of what values 
%joe26
%Y and X 
$X$, $Y$, and $Z$
actually take in the real world. 

%joe23: inserted material from Part I
The counterfactual interpretation and the causal
asymmetry associated with the structural equations are best
seen when we consider external interventions (or spontaneous
changes), under which some equations in $F$ are modified. 
An equation such as 
$x = F_X(\vec{u},y)$ should be thought of as saying
that in a context where the exogenous variables have values $\vec{u}$,
if $Y$ were set to $y$ 
by some means (not specified in the model), 
then $X$ would take on the value 
$x$, as dictated by $F_X$. The same does not hold when we intervene
directly on $X$; 
such an intervention amounts to assigning a value to $X$ by
external means, thus overruling the assignment specified
by $F_X$. 

For those more comfortable with thinking of counterfactuals in terms of
possible worlds, this modification of equations  
may be given a simple ``closest world'' interpretation:  
the solution of the equations obtained
%joe26
%by removing the equation for $Y$ and setting $Y$ to $y$ in all other
%equations gives the closest ``world'' to the actual world where $Y=y$.
replacing the equation for $Y$ with the equation $Y = y$,
while leaving all other equations unaltered,
gives the closest ``world'' to the actual world where $Y=y$.


%joe16: cut for abstract
\commentout{
We typically write $X = F_X(\U,\V-\{X\})$, to show that $X$ is
determined by the setting of the remaining variables.
%joe10
%We think of the functions $F_X$ as defining a set of {\em (modifiable)
The functions $F_X$ define a set of {\em (modifiable)
structural equations}, relating the values of the variables.  Because
$F_X$ is a function, there is a unique value of $X$ once we have set all
the other variables.
Notice that we have such functions only for the endogenous variables.
The exogenous variables
are taken as given; it is their effect on the endogenous
variables (and the effect of the endogenous variables on each other)
that we are modeling with the structural equations.
}
%joe8: added paragraph below; I think we need to slow down here
%joe10
%An equation such as $X = F_X(\vec{u},y)$ should be that of as saying
%joe16: cut for abstract


We can describe (some salient features of) a causal model $M$ using a
{\em causal network}.  
This is a graph
%with nodes corresponding to the random variables in $\U \union \V$
with nodes corresponding to the random variables in $\V$ and an edge
from a node labeled $X$ to one labeled $Y$ if $F_Y$ depends on the value
of $X$.
%joe4: added
%joe16: cut for abstract
%This graph is a {\em dag\/}---a directed, acyclic graph.  The
%acyclicity follows from the assumption that the equations are recursive.}
Intuitively, variables can have a causal effect only on their
descendants in the causal network; if $Y$ is not a descendant of $X$,
%joe+
%then a change in the value of $X$ has no affect on the value of $Y$.
then a change in the value of $X$ has no effect on the value of $Y$.
%joe24*: added
Causal networks  are similar in spirit to Lewis's
%joe**
%{\em neuron diagrams} \citeyear{Lewis86a}, but there are significant
{\em neuron diagrams} \citeyear{Lewis73}, but there are significant
%joe**
%differences as well (see \cite{HP01b} for a discussion).
differences as well (see Part I for a discussion).
%Notice that, in general, there may not be a unique vector of values that
%simultaneously satisfies the equations in $M_{\vec{X} \gets
%%\vec{x}}(\vec{u})$; indeed, there may not be a solution at all.  For
%\vec{x}}$; indeed, there may not be a solution at all.  For
%simplicity 
In this paper, 
we restrict attention to what are called {\em
recursive\/} (or {\em acyclic\/}) equations; 
%joe16: easier definition
these are ones that can be
%joe24: explained dag
described with a causal network that is a directed acyclic graph (that
is, a graph that has no  cycle of edges).
It should be clear that if $M$ is a recursive causal model,
then there is always a
unique solution to the equations in
%joe24*: a little premature
%$M_{\vec{X} \gets \vec{x}}$, given a setting $\vec{u}$ for the
$M$, given a setting $\vec{u}$ for the
variables in $\U$.%
\footnote{In the companion paper, there is some discussion on how to
extend the definition of causality to nonrecursive models.  It seems
that these ideas should apply to our definition of explanation as well.
However, we do not pursue this issue here.}
Such a setting is called a {\em context}.  Contexts will play the role
of possible worlds when we model uncertainty.
For future reference, a pair $(M,\vec{u})$ consisting of a causal model
and a context is called a {\em situation}.

\xam\label{xam:arson}
Suppose that two arsonists
drop lit matches in different parts of a dry forest, and both
cause trees to start burning.
%joe1: rewrote and expanded material
Consider two scenarios.  In the first, called 
%joe24
%``disjunctive,''
the {\em disjunctive scenario},
either match by itself
suffices to burn down the whole forest.  That is, even if only one
match were lit, the forest would burn down.  In the second scenario,
%joe24
%called ``conjunctive,'' both matches are necessary to burn down
called the {\em conjunctive scenario}, both matches are necessary to burn down
the forest; if only one match were lit, the fire would die down
before the forest was consumed.
We can describe the essential structure of these two
scenarios using a causal model with four variables:
\begin{itemize}
\item an exogenous variable $U$ that determines,
among other things, the motivation and state of mind of
the arsonists.  For simplicity, assume that $\R(U) = \{u_{00}, u_{10},
u_{01}, u_{11}\}$; if $U=u_{ij}$, then the first arsonist intends to
start a fire iff $i=1$ and the second arsonist intends to start a fire
iff $j=1$.  In both scenarios $U=u_{11}$.
\item endogenous variables $\ML_1$ and $\ML_2$, each either 0 or 1, where
$\ML_i=0$ if arsonist $i$ doesn't drop the match and $\ML_i=1$ if he does,
for $i =1, 2$.
\item an endogenous variable $\FB$ for forest burns down, with values 0
(it doesn't) and 1 (it does).
\end{itemize}
Both scenarios have the same causal network
(see Figure \ref{fig1m});
they differ only in the equation for $\FB$.
%joe2: shrunk for abstract
%For the disjunctive scenario (Figure \ref{fig1m}(a))
For the disjunctive scenario
we have $F_{FB}(u,1,1) = F_{FB}(u,0,1) =
F_{FB}(u,1,0) = 1$ and $F_{FB}(u,0,0) = 0$ (where $u \in \R(U)$);
%joe2: for abstract
%for the conjunctive scenario (Fig.\ \ref{fig1m}(b))
for the conjunctive scenario
we have $F_{FB}(u,1,1) = 1$ and
$F_{FB}(u,0,0) = F_{FB}(u,1,0) = F_{FB}(u,0,1) = 0$.

In general, we expect that the causal
model for reasoning about forest fires would involve many other
variables; in particular, variables for other potential causes
%joe+
%of forest fires such lightning and unattended campfires.  Here we focus
of forest fires such as lightning and unattended campfires.  Here we focus
on that part of the causal model that involves forest fires started by
arsonists.  Since for causality we assume that all the relevant facts
are given, we can assume here that it is known that there were no
unattended campfires and there was no lightning, which makes it safe to
ignore that portion of the causal model.

Denote by $M_1$ and $M_2$ the
%joe6*
(portion of the)
causal models associated with
the disjunctive and conjunctive scenarios, respectively.  The causal
network for the relevant portion of $M_1$ and $M_2$ is described in
Figure~\ref{fig1m}.
\begin{figure}[htb]
\input{psfig}
%\hspace*{.75in}
\centerline{\psfig{figure=figure1m.eps}}
%joe8
%\caption{Disjunctive ($M_1$) and conjunctive ($M_2$) scenarios
%of Example~\ref{xam:arson}.} %%example 3.2
\caption{The causal network for $M_1$ and
$M_2$.}
\label{fig1m}
\end{figure}
The diagram emphasizes that the value of $FB$ is determined by the
values of $\ML_1$ and $\ML_2$ (which in turn are determined by the
value of the exogenous variable $U$.
\exam

%joe24: moved this material after the example (it used to be before)
As we said,
a causal model has the resources to determine counterfactual effects.
Given a causal model $M = (\S,\F)$, a (possibly
empty)  vector
$\vec{X}$ of variables in $\V$, and vectors $\vec{x}$ and
$\vec{u}$ of values for the variables in
$\vec{X}$ and $\U$, respectively, we can define a new causal model
denoted
%$M_{\vec{X} \gets \vec{x}}(\vec{u})$ over the signature $\S_{\vec{X}}
$M_{\vec{X} \gets \vec{x}}$ over the signature $\S_{\vec{X}}
= (\U, \V - \vec{X}, \R|_{\V - \vec{X}})$.
Formally, $M_{\vec{X} \gets \vec{x}} = (\S_{\vec{X}},
\F^{\vec{X} \gets \vec{x}})$,
where $F_Y^{\vec{X} \gets \vec{x}}$ is obtained from $F_Y$
by setting the values of the
variables in $\vec{X}$ to $\vec{x}$.
Intuitively, this is the causal model that results when the variables in
$\vec{X}$ are set to $\vec{x}$ by some external action
that affects only the variables in $\vec{X}$;
we do not model the action or its causes explicitly.
%joe24*: added
For example, if $M_1$ is the model for the disjunctive scenario in
Example~\ref{xam:arson}, then $(M_1)_{{\it ML}_1 \gets 0}$ is the model
where $\FB = \ML_2$: if the first match is not dropped, then there is a
fire if and only if the second match is dropped.
Similarly,
%joe+
%$(M_2)_{{\it ML}_2 \gets 0}$ is the model where $\FB = $: if the first
%match is not dropped, then there is no fire in the conjunctive scneario.
$(M_2)_{{\it ML}_2 \gets 0}$ is the model where $\FB = 0$: if the first
match is not dropped, then there is no fire in the conjunctive scenario.
Note that if $M$ is a recursive causal model, then there is always a
unique solution to the equations in $M_{\vec{X} \gets \vec{x}}$ for all
$\vec{X}$ and $\vec{x}$.

%%Intuitively, this is the causal model that results when the variables in
%%$\vec{X}$ are set to $\vec{x}$.
%and the variables in $\U$ are set to $\vec{u}$.
%Formally, $M_{\vec{X} \gets \vec{x}}(\vec{u} = (\S_{\vec{X}},
%\F^{\vec{X} \gets \vec{x},\vec{u}}\})$,
%where $F_Y^{\vec{X} \gets \vec{x},\vec{u}}$ is obtained from $F_Y$
%and the values of the variables in $\U$ to $\vec{u}$.

%joe4: cut for UAI
\subsection{Syntax and Semantics:}
%To make the definition of actual
%causality precise, it is helpful to have a logic with a formal syntax.
%joe17: uncut the next line (it was cut by accident)
Given a signature $\S = (\U,\V,\R)$, a formula of the form $X = x$, for
$X \in V$ and $x \in \R(X)$, is called a {\em primitive event}.   A {\em
basic causal formula\/} 
%joe20: line shaving
%(over $\S$)\/} 
is one of the form
%$[Y_1 \gets y_1, \ldots, Y_k \gets y_k] \phi(\vec{u})$
%joe20: added comma at end of line
$[Y_1 \gets y_1, \ldots, Y_k \gets y_k] \phi$,
where 
%joe10: itemized to make it easier to parse
%joe16: unitemized to save space
\begin{itemize}
\item 
$\phi$ is a Boolean
%where $\phi(\vec{u})$ is a Boolean
%combination of formulas of the form $X(\vec{u}) = x$, where $Y_1,
%joe20: changed commas to semi-colons
combination of primitive events;
%joe10: redundant
%formulas of the form $X = x$, 
%\item 
%joe20
%\ldots, Y_k, X$ are variables in $\V$ with $Y_1, \ldots, Y_k$ distinct;
%joe24: no X
%\ldots, Y_k, X$ are variables in $\V$;  $Y_1, \ldots, Y_k$ are distinct;
\item $Y_1,\ldots, Y_k$ are distinct variables in $\V$;  and
\item 
%$x \in \R(X)$; and 
%\item 
$y_i \in \R(Y_i)$.
\end{itemize}
%and $\vec{u}$ is a vector of values for all the variables in $\U$.
Such a formula is 
%joe17
%typically 
abbreviated
%as $[\vec{Y} \gets \vec{y}]\phi(\vec{u})$.
as $[\vec{Y} \gets \vec{y}]\phi$.
The special
case where $k=0$
%joe4
%(which is allowed)
is abbreviated as
%$[\true]\phi(\vec{u})$. Intuitively, $[\true]\phi(\vec{u})$ says that
$\phi$.
%joe4
%Intuitively, $\phi$ says that $\phi$ holds in the actual world.
%$[Y_1 \gets y_1, \ldots, Y_k \gets y_k] \phi(\vec{u})$ says that
Intuitively, $[Y_1 \gets y_1, \ldots, Y_k \gets y_k] \phi$ says that
%$\phi(\vec{u})$ holds in the counterfactual world that would arise if
$\phi$ holds in the counterfactual world that would arise if
%the endogenous variables are set to $\vec{u}$ and $Y_i$ is set to
%joe+
%$Y_i$ is set to $y_i$, $i = 1,\ldots,k$.
$Y_i$ were set to $y_i$, $i = 1,\ldots,k$.
%Following Galles and Pearl's notation, I often write
%$[\vec{Y} \gets \vec{y}]X(\vec{u}) = x$ as
%$X_{\vec{Y}
%joe17
%As we now show, the semantics guarantees that
%this counterfactual world is the one where the values of the variables
%are those in the unique
%solution to the equations obtained after setting the variables
%in $\vec{Y}$ to the values $\vec{y}$.
%joe17: added
A {\em causal formula\/} is a Boolean combination of basic causal
formulas.%
%joe24
\footnote{
If we write $\rightarrow$ for conditional implication, then
a formula such as $[Y\gets y] \phi$ can be written as $Y = y \rightarrow
\phi$: if $Y$ were $y$, then $\phi$ would hold.  We use the present
notation to emphasize the fact that, although we are viewing $Y \gets y$
as a modal operator, we are not giving semantics using the standard
%joe+
%possible worlds approach.}
possible-worlds approach.}


%joe17
%A basic causal formula is true or false in a causal model, given a
%context $\vec{u}$. 
A causal formula $\phi$ is true or false in a causal model, given a context.
We write $(M,\vec{u}) \sat \phi$ if
%joe17
%the causal formula 
$\phi$ is true in
causal model $M$ given context $\vec{u}$.
%joe16
\commentout{
\footnote{We remark that in \cite{GallesPearl97,Hal20},
the context $\vec{u}$ does not appear on the left-hand side of $\sat$;
rather, it is incorporated in the formula $\phi$ on the right-hand (so
that a basic formula becomes $X(\vec{u}) = x$).  
%jp13 Adding a pacifying sentence that I owe to the faithful 
%readers of my book who invested time in acquiring the 
%subscript notation -- a very useful one after all.
Additionally, Pearl \citeyear{pearl:2k} abbreviated
$(M,\vec{u}) \sat [\vec{Y} \gets \vec{y}](X = x)$
%joe12:
% to read:
as
$X_{y}(u)=x$. The presentation here
%seems more natural for our purposes, although they are technically
makes certain things more explicit, although they are technically
equivalent.}}%\end{commentout}
$(M,\vec{u}) \sat [\vec{Y} \gets \vec{y}](X = x)$ if 
%joe17: 
the variable $X$ has value $x$ 
in the
%joe4
%(unique, since we are dealing with recursive equations) solution
%joe20
unique (since we are dealing with recursive models) solution
to
%joe8
the equations in
$M_{\vec{Y} \gets \vec{y}}$ in context $\vec{u}$ (that is, the
unique vector
of values for the exogenous variables that simultaneously satisfies all
equations $F^{\vec{Y} \gets \vec{y}}_Z$, $Z \in \V - \vec{Y}$,
with the variables in $\U$ set to $\vec{u}$).
%joe20: shrunk
%$(M,\vec{u}) \sat
%[\vec{Y} \gets \vec{y}]\phi$ for an arbitrary 
%Boolean combination $\phi$ of formulas of the form $\vec{X} = \vec{x}$ 
%similarly.
%%joe17: added
We extend the definition to arbitrary causal formulas
%joe20:
%, i.e., Boolean combinations of basic causal formulas, in the standard way.
in the obvious way.

%joe20: added
Thus, in Example~\ref{xam:arson}, we have
%joe+
%$M_{1}, u_{11} \sat [\ML_1 = 0] \FB = 1$ and 
%$\M_2, u_{11} \sat [\ML_1 = 0] \FB = 0$.  In the disjunctive model, in
$(M_{1}, u_{11}) \sat [\ML_1 = 0](\FB = 1)$ and 
$(\M_2, u_{11}) \sat [\ML_1 = 0](\FB = 0)$.  In the disjunctive model, in
the context where both arsonists drop a match, if the first arsonist
does not drop a match, the forest still burns down.  On the other hand,
in the conjunctive model, if the first arsonist does not drop a match (in
the same context), the forest does not burn down.

Note that the structural equations are deterministic.  
%joe16:
%We can make
%sense out of probabilistic counterfactual statements, even conditional
%ones (the probability that
%$X$ would be 3 if $Y_1$ were 2, given that $Y$ is in fact 1) in this framework
%(see \cite{BalkePearl94}), by putting a probability
%%joe6*
%measure on the set of possible values of the exogenous variables,
%on the set of possible contexts.
%but this will not be
%necessary for our discussion.
%This is not necessary for our discussion of causality, although it
%plays a more significant role in the discussion of explanation.
We later add probability to the picture by putting a probability on the set
of contexts (i.e., on the possible worlds).  This probability is not
%joe24
%relevant to 
needed in
the definition of causality, but will be useful in the
discussion of explanation.


\subsection{The Definition of Cause}\label{sec:actcaus}

With all this notation in hand, we can
now give a definition of actual cause (``cause'' for
short).  We want to make
sense out of statements of the form ``event $A$ is
an actual cause of
event $\phi$ (in context $\vec{u}$)''.%
\footnote{Note that we are using the word ``event'' here in the
standard sense of ``set of possible worlds''
(as opposed to ``transition between states of affairs''); 
essentially we are
identifying events with propositions.}
The picture here is that the context (and the structural equations) are
given.
%joe10
Intuitively, they encode the background knowledge.
All the relevant 
%joe10
%facts 
events
are known.  The only question is picking
out which of them are the causes of $\phi$
%jp7: added
or, alternatively, testing whether a given set of 
%joe10
%facts
events
can be considered the cause of $\phi$.

%joe1: simplified!
%jp5: reintroducing vector causes.
The types of events that we 
%joe16
%consider 
allow
as actual causes are ones of
the form
$X_1 = x_1 \land \ldots \land X_k = x_k$---that is, conjunctions of
primitive events; we typically abbreviate this as $\vec{X} = \vec{x}$.
%joe2:
%or, even more succinctly, as $x$.
%Only a primitive event of the form $X=x$ can be an actual cause.
The events that can be caused are arbitrary Boolean combinations
%of primitive events.
%jp5
%joe2: shortened
%of primitive events, to be denoted by the symbol $\phi$.
%joe16
%$\phi$ 
of primitive events.
We do not believe that we lose much by disallowing disjunctive
causes here.   
%joe24*: I'm not sure I believe this.  It's in the causality paper, but
%I'd rather not repeat it here.
%Since for causality we are
%assuming that the structural model and all the relevant facts are known,
%the only reasonable definition of ``$A$ or $B$ causes $\phi$'' seems to
%be that ``either $A$ causes $\phi$ or $B$ causes $\phi$''.  There are
%no truly disjunctive causes once all the relevant facts are known.
%joe20: 
%joe24: italicized
Disjunctive {\em explanations}, however, are certainly of interest.

Roughly speaking, $\vec{X} = \vec{x}$ is a {\em sufficient cause of
$\phi$ in situation $(M,\vec{u})$\/} if 
(a) $\vec{X} = \vec{x} \land \phi$ is true in $(M, \vec{u})$ and (b) 
there is some set $\vec{x}'$
of values of $\vec{X}$ and some other variables $\vec{W}$ 
%joe24: added next line
(satisfying some constraints) 
%jp0, see if it does not sound better:
%such that changing $\vec{X}$ to $\vec{x}'$ and 
%$\vec{W}$ to $\vec{w}'$ results in $\neg \phi$ being true
such that setting $\vec{W}$ to $\vec{w}'$ and
changing $\vec{X}$ to $\vec{x}'$ results in $\neg \phi$ being true
(that is,  $(M,\vec{u}) \sat [\vec{X} \gets \vec{x}', \vec{W} \gets
\vec{w}'] \neg \phi$).  
Part (b) is very close to the standard counterfactual
%joe**
%definition of causality, advocated by Lewis \citeyear{Lewis86a} and
definition of causality, advocated by Lewis \citeyear{Lewis73} and
others: $\vec{X} = \vec{x}$ is the cause of $\phi$ if,
had $\vec{X}$ not been equal to $\vec{x}$, $\phi$ would not have been
%joe+
%the case).  The difference is that we allow setting some other
%variables
the case.  The difference is that we allow setting some other variables
$\vec{W}$ to $\vec{w}$.  
As we said,
the formal definition 
%joe24*
%puts some restrictions on $\vec{W}$.  Among other things, it must be the
%case that setting $\vec{X}$ to $\vec{x}$ is enough to force $\phi$, even
puts some constraints on $\vec{W}$.  Among other things, it must be the
case that setting $\vec{X}$ to $\vec{x}$ is enough to force $\phi$ to be
true when $\vec{W}$ is set to $\vec{w}'$.  That is, it must be the case that
$(M,\vec{u}) \sat [\vec{X} \gets \vec{x}, \vec{W} \gets \vec{w}'] \phi$.
(See the appendix for the formal definition.)

$\vec{X} = \vec{x}$ is an {\em actual cause of $\phi$ in $(M,\vec{u})$\/} if
it is a sufficient clause with no irrelevant conjuncts.  That is,
$\vec{X} \gets \vec{x}$ is an actual cause of $\phi$ in $(M,\vec{u})$ if
it is a sufficient cause and no subset of $\vec{X}$ is also a sufficient
cause.   Eiter and Lukasiewicz \citeyear{EL01}
and, independently, Hopkins \citeyear{Hopkins01} have shown that actual
causes are always single conjuncts.  As we shall see, this is not the
case for explanations. 

Returning to Example~\ref{xam:arson}, note that $\ML_1 = 1$ is an actual
cause of $\FB=1$ in both the conjunctive and the disjunctive scenarios.
This should be clear in the conjunctive scenario.  Setting $\ML_1$ to 0
results in the forest not burning down.  To see that $\ML_1 = 1$ is also
a cause in the disjunctive scenario, let $W$ be $\ML_2$.  Note that
$(M_1, u_{00}) \sat [\ML_1 \gets 0, \ML_2 \gets 0] \FB = 0$, so the
counterfactual condition is satisfied.  Moreover, 
$(M_1, u_{00}) \sat [\ML_1 \gets 1, \ML_2 \gets 0] \FB = 1$; that is, in
the disjunctive scenario, if the first arsonist drops the match, that is
enough to burn down the forest, no matter what the second arsonist does.
%joe24
%In either scenario, the both arsonists dropping the match 
In either scenario, both arsonists dropping a lit match 
constitutes a sufficient cause for the forest fire, as does the first
arsonist dropping a lit match and sneezing.  Given an actual cause, a
sufficient cause can be obtained by adding arbitrary conjuncts to it.

Although  each arsonist is a cause of the forest burning
down in the conjunctive scenario, under reasonable assumptions about the
knowledge of the agent wanting an explanation, each arsonist alone is not
an {\em explanation\/} of the forest burning down.  Both arsonists
together provide the explanation in that case;
%jp0 I think we had a persuasive argument here in one of
%the early versions, something like:
identifying arsonist 1 would only trigger 
%joe26
a
%joe+
%further quest for the identity her accomplice.
further quest for the identity of her accomplice.
In the disjunctive
scenario, each arsonist alone is an explanation of the forest burning down.


We hope that this informal discussion of the definition of causality
will suffice for 
%joe+
%readers who mainly want to focus on explanation.
readers who want to focus mainly on explanation.
For completeness, we give the formal definitions of sufficient and
actual cause  in the appendix.  
%(Of course, the interested reader should
%consult \cite{HP01b} for more discussion and motivation.) 
The definition is motivated, discussed, and defended in much more detail in 
%joe**
%\cite{HP01b}, where it is also compared to other definitions of
%causality.  
%joe+
%Part I, where it is also compared to other definitions of causality.  
Part I, where it is also compared with other definitions of causality.  
In particular, it is shown to avoid a number of problems
that have been identified with Lewis's account (e.g., see
\cite[Chapter 10]{pearl:2k}), such as commitment to transitivity of
causes.
For the purposes of this paper, we ask that the reader accept 
%joe24
%the definition.  
%joe+
%our definition of causaility.
our definition of causality.
We note that, to some extent, our definition of explanation
is modular in its use of causality, in that another 
definition of causality could be substituted for the one we use in the
definition of explanation (provided it was given in the same framework).

%joe24
%\section{Explanation}\label{sec:explanation}
\section{Explanation: The Basic Definition}\label{sec:explanation}
As we said in the introduction, many definitions of causal explanation
have been given in the literature. 
The ``classical'' approaches in the philosophy literature,
such as Hempel's \citeyear{Hempel65} {\em deductive-nomological\/}
model and 
Salmon's \citeyear{Salmon89} {\em statistical relevance\/} model (as
well as many other approaches), because they are based on 
%probabilistic correlation, fail to exhibit the directionality inherent in common
logical implication and probabilistic dependence,
%joe+
%respectively, and , fail to exhibit the directionality inherent in
%common
respectively, fail to exhibit the directionality inherent in common
explanations.  Despite all the examples in the philosophy literature on
the need for 
taking causality and counterfactuals into account, and the extensive work
on causality defined in terms of counterfactuals in 
the philosophy literature, as Woodward \citeyear{Woodward01} observes,
philosophers have been reluctant to build a theory of
explanation on top of a theory of  causality. The concern seems to be
one of circularity.
In this section, we give a definition of explanation based on the
definition of causality discussed in Section~\ref{sec:actcaus}.  
%jp0 Elaborating
%It should be clear that the definition is noncircular.  
%joe26: rewrote
%Circularity is avoided  because the latter invokes strictly 
%formal features of a causal model, void of the notion of explanation.
Circularity is avoided  because the definition of explanation invokes strictly 
%joe+
%formal features of a causal model, that do not in turn depend on the
formal features of a causal model that do not in turn depend on the
notion of explanation. 

Our definition of causality assumed that the causal model and all the
relevant facts were given; the problem was to figure out which of the
given facts were causes.
%jp7: I am adding a more contrasting sentence and rearranging.
In contrast, the role of explanation is to provide the
%joe7: this didn't read right to me.
%knowledge needed for figuring out such problems.
%%information needed to decide what the causes.
%jp8. our explanations already come with the identity of the cause
%thus, I am elaborating:
information needed to establish causation.
%joe8: hedging, since this isn't quite right.
%In other words,
Roughly speaking,
we view an explanation as a fact
that is not known for certain but, if found to be true,
would constitute a genuine
cause of the {\em explanandum\/} (fact to be explained), regardless of
the agent's initial uncertainty.  Roughly speaking, the role of
explanation is to provide the information needed to establish causation.
Thus, as we said in the introduction,
%jp0 changed to third person
what counts as an explanation depends on what one already knows (or
believes---we largely blur the distinction between knowledge and belief
%joe24
%in this paper) and, naturally, the definition of 
in this paper).  As a consequence, the definition of 
an {\em explanation\/} should be relative to the agent's
epistemic state (as in G\"ardenfors \citeyear{Gardenfors1}).
It is also  natural, from this viewpoint, that an
%joe+
%explanation will include fragments of the causal model M,
explanation will include fragments of the causal model $M$
or reference to the physical laws underlying the
connection between the cause and the effect.

%joe24
%\subsection{The Basic Definition}
%joe10: added intuition, per Chris's note
The definition of explanation is motivated by the
following intuitions.  An individual in a given epistemic state $K$ asks
why $\phi$ holds.  What constitutes a good answer to his
question?  A good answer must (a) provide information that goes beyond
$K$ and (b) be such that the individual can see that it would, if true, be
(or be very likely to be) a cause of $\phi$.  We may also want to
require that (c) $\phi$ be true (or at least probable).  Although our
basic definition does not insist on (c), it is easy to add this requirement.

How do we capture an agent's epistemic state in our framework?  
For ease of exposition, we first consider
the case where the causal model is known
%jp11 adding
and only the context is uncertain.  (The minor
modifications required to deal with the general case
are described in Section~\ref{sec:general}.)  In that case, one way of
describing an agent's epistemic state 
%joe16
is
by simply describing the set
of contexts the agent considers possible.

\dfn\label{def:explanation1} (Explanation)  Given a structural model
$M$, {\em $\vec{X} = \vec{x}$ is an explanation
of $\phi$ relative to a set $\K$ of contexts\/} if the following
conditions hold:
\begin{description}
\item[{\rm EX1.}] $(M,\vec{u}) \sat \phi$ for each context $\vec{u} \in \K$.
(That is, $\phi$ must hold in all contexts the agent considers
%jp7: suggests rephrasing, because phi also has implications.
%possible---the agent knows what she is trying to explain.)
possible---the agent considers what she is trying to explain
as an established fact.)
%or, how about:
%possible---the agent considers the explanadum as...
\item[{\rm EX2.}] $\vec{X} = \vec{x}$ is a
%joe8: this is now formally correct
%joe18: italicized
%joe20
{\em sufficient cause\/} of $\phi$ in $(M,\vec{u})$
for each $\vec{u} \in \K$ such that $(M,\vec{u}) \sat \vec{X} = \vec{x}$.
\item[{\rm EX3.}] $\vec{X}$ is minimal; no  subset of $\vec{X}$
satisfies EX2.
\item[{\rm EX4.}]
$(M,\vec{u}) \sat \neg (\vec{X}=\vec{x})$ for some $\vec{u} \in \K$ and
$(M,\vec{u}') \sat \vec{X}=\vec{x}$ for some $\vec{u}' \in \K$.
(This just says that the agent considers
a context possible where the explanation is false, so the explanation
is not known to start with, and considers a context possible where the
explanation is true, so that it is not vacuous.) \eprf
\end{description}
\end{definition}



%joe8: added in light of your comment:
Our requirement EX4 that the explanation is not known may seem
incompatible with linguistic usage.  Someone discovers some fact $A$ and
says ``Aha! That explains why $B$ happened.''  Clearly, $A$ is not
an explanation of why $B$ happened
relative to the epistemic state {\em after\/} $A$ has been discovered,
since at that point $A$ is known.  However, $A$ can legitimately be
considered an explanation of $B$ relative to the epistemic state before
$A$ was discovered.  
%joe24*: added rest of paragraph
Interestingly, as we shall see, although there is a cause for every
event $\phi$ (although sometimes it may be the trivial cause $\phi$),
one of the effects of the requirement 
EX4 is that some events may have no explanation.  This seems to us quite
consistent with standard usage of the notion of explanation.  After all,
we do speak of ``inexplicable events''.

What does the definition of explanation tell us for the arsonist example?
%joe24*: added next sentence
What counts as a cause is, as expected, very much dependent on the
causal model and the agent's epistemic state.
If the causal model has only arsonists as the cause of the fire, there are two
%jp0 added (i) and (ii)
%joe26: changed to (1) and (2) 
%joe+
%possible explanations in the disjunctive scenario: (1) arsonist 1 
%did it and (2) 
possible explanations in the disjunctive scenario: (a) arsonist 1 
did it and (b) 
arsonist 2 did it (assuming $\K$ consists of three contexts, where
either 1, 2, or both set the fire).  In the conjunctive scenario, no
explanation is necessary, since the agent knows that both arsonists must
have lit a match if arson is the only possible cause of the fire
%jp7: adding:
%joe7: ML stands for "match lit", so we need to change this
%(and $\ML_1$ and $\ML_2$ are the only arsonists in existence).
(assuming that the agent considers the two arsonists to be the only
possible arsonists).  
%joe25: expanded
That is, if the two arsonists are the only possible cause of the fire
%joe+
%and the fire is observed, the $\K$ can consist of only one context,
%namely the one where both arsonists started the fire.  No explanation
and the fire is observed, then $\K$ can consist of only one context,
namely, the one where both arsonists started the fire.  No explanation
can satisfy EX4 in this case.

Perhaps more interesting is to consider a causal model with other
possible causes, such as lightning and unattended campfires.
Since the agent knows that there was a fire, in each of the contexts in
$\K$, at least one of the potential causes must have actually occurred.
%joe24
%If we assume that there is a context where only arsonist 1 lit a fire
%(and, say, there was lightning) and another where only arsonist 2 lit
If there is a context in $\K$ where only arsonist 1 dropped a lit match
(and, say, there was lightning), another where only arsonist 2
dropped a lit match,
%joe24
and a third where both arsonists dropped matches,
then, in the conjunctive scenario, $\ML_1 = 1 \land \ML_2 = 1$ 
is an
explanation of $\FB=1$, but neither $\ML_1=1$ nor $\ML_2=1$ by itself is
an
explanation (since neither by itself is a cause in all contexts in $\K$
that satisfy the formula).  On the other hand, in the disjunctive
scenario,
both $\ML_1 = 1$ and $\ML_2=1$ are explanations.


Consider the following example, due to Bennett (see
%joe**
%\cite[pp.~222--223]{sosa:too93}), which is analyzed in \cite{HP01b}.
\cite[pp.~222--223]{sosa:too93}), which is analyzed in Part I.
\xam\label{xam1}   Suppose that there was a heavy rain
in April and electrical storms in the following two months; and in June
the lightning took hold.  If it hadn't been for the heavy rain in April,
the forest would have caught fire in May.  The first question is 
whether the April rains caused the forest fire.  According to  a
naive counterfactual analysis, they do,
since if it hadn't rained, there wouldn't have
been a forest fire in June.   In our framework,
it is not the case that the April rains caused
the fire, but they were a cause of there being a fire
in June, as opposed to May.  This seems to us intuitively right.

The situation can be captured using a model with three
endogenous random variables:
\begin{itemize}
\item $\AS$ for ``April showers'', with two
values---0 standing for did {\em not\/} rain heavily in April and 1
standing for rained heavily in April;
\item $\ES$ for ``electric storms'', with four possible values: $(0,0)$
(no electric storms in either May or June), (1,0) (electric storms in
May but not June), (0,1) (storms in June but not May), and (1,1)
(storms in both April and May);
\item and $F$ for ``fire'', with three possible values: 0 (no fire at
all), 1 (fire in May), or 2 (fire in June).
\end{itemize}
We do not describe the context explicitly.   Assume its value
$\vec{u}$ is such that it ensures that there is a shower in April, there
are electric storms in both May and June,
there is sufficient oxygen, there are no other potential causes of fire
(like dropped matches), no other inhibitors of fire (alert campers
setting up a bucket brigade), and so on.  That is, we choose $\vec{u}$
so as to allow us to focus on the issue at hand and to ensure that the
right things happened (there was both fire and rain).
%joe24
%The structural equations should also be obvious, given the story.
We will not bother writing out the details of the structural
equations---they should be obvious, given the story (at least, for the
context $\vec{u}$); this is also the case for all the other examples in
this section. The causal network is simple: there are edges from
%joe**
%$\AS$ to  $F$ and from $\ES$ to $F$.  As observed in \cite{HP01b}, 
$\AS$ to  $F$ and from $\ES$ to $F$.  As observed in Part I,
%joe+
%each of the following hold.
each of the following holds.
\begin{itemize}
%joe2: I'd prefer to call it *a* cause, not the cause
%\item $\AS=1$ is the actual cause of the June fire $(F=2)$,
\item $\AS=1$ is a cause of the June fire $(F=2)$.
\item $\AS=1$ is {\em not\/} a cause of the fire ($F=1 \lor F=2$).  If
$\ES$ is set 
%joe+
%(0,1),  (1,0) or (1,1), then there will be a fire (in either May or
(0,1),  (1,0), or (1,1), then there will be a fire (in either May or
June) whether $\AS=0$ or $\AS=1$.  On the other hand, if $\ES$ is set to
(0,0), then there is no fire, whether $\AS=0$ or $\AS=1$.
\item $\ES = (1,1)$ is a cause of both $F=2$ and $(F=1 \lor F=2)$.
Having electric storms in both May and June caused there to be a fire.
\item $\AS=1 \land \ES=(1,1)$ is a sufficient cause of $F=2$; each
individual conjunct is an actual cause.
\end{itemize}

Now consider the problem of explanation.
Suppose that the agent knows that there was an electric
storm, but does not know when, and does not know whether there were
April showers.  Thus, $\K$ consists of six contexts,
one corresponding to each of the values
(1,0), (0,1), and (1,1) of $\ES$ and the values 0 and 1 of $\AS$.
Then it is easy to see that $\AS=1$ is not an explanation of fire ($F=1
\lor F=2$), since it is
not a cause of fire in any context in $\K$.  Similarly, $\AS=0$ is
not an explanation of fire.  On the other hand, each of $\ES=(1,1)$,
$\ES=(1,0)$, and $\ES=(0,1)$ is an explanation of fire.

Now suppose that we are looking for an explanation of the June fire.
Then the set $\K$ can consist only of contexts
compatible with there being a fire in June.  Suppose that $\K$ consists
of three contexts, one where $\AS=1$ and $\ES = (0,1)$, one where $\AS=1$
and $\ES=(1,1)$, and one where $\AS=0$ and $\ES=(0,1)$.  In this case, each
of $\AS=1$, $\ES=(0,1)$, and $\ES=(1,1)$ is
%joe8
%a cause
an explanation
of the June fire.
(In
the case of $\AS=1$, we need to consider the setting where $\ES=(1,1)$.)

Finally, if the agent knows that there was an electric storm in May and
June and heavy rain in April (so that $\K$ consists of only one
context), then there is no explanation of either fire or the fire in
June.  Formally, this is because it is impossible to satisfy EX4.
Informally, this is because the agent already knows why there was a
%joe10
%storm in June.
fire in June.
\exam

Note that, as for causes, we have disallowed disjunctive explanations.
Here the motivation is less clear cut.  It does make perfect sense to
say that the reason that $\phi$ happened is either $A$ or $B$ (but I
don't know which).  There are some technical difficulties with
disjunctive explanations, which suggest philosophical problems.  For
example,
consider the conjunctive scenario of the arsonist example again. Suppose
that the structural model is such that the only  causes of fire are the
arsonists, lightning, and unattended campfires and that $\K$ consists of
contexts where each of these possibilities is the actual cause of the
fire.  Once we allow disjunctive explanations, what is the explanation
of fire?  One candidate is ``either there were two arsonists or there
was lightning or there was an unattended campfire (which got out of
hand)''.  But this does not satisfy EX4, since the disjunction is true
in every context in $\K$.  
%joe24*: rewrote rest of paragraph
%On the other hand, if we do not allow the
%disjunction of all possible causes, which disjunction should be allowed
%as an explanation?  
On the other hand, the disjunction of any two of the three clauses does
satisfy EX4.  As we add more and more potential causes of the fire
(explosions, spontaneous combustion, \ldots) larger and larger
disjunctions will 
count as explanations.  The only thing that is not allowed is the
disjunction of all possible causes.  
This distinction between the dijsunction of all potential causes and
the disjunction of all but one of the potential causes seems artificial,
to say the least.
To make matters worse,
%joe24
%As a technical matter, how should the minimality condition EX3 be rewritten?  
there is the technical problem of reformulating the minimality condition
EX3 to deal with disjunctions.
We could not see any reasonable way to
%joe24
%allow some disjunctions in this case without allowing the disjunction of
%all causes 
%(which will not in general satisfy EX4).
%jp0 deleting dups
%to deal with these technical problems, so we ban disjunctive disjunctive
deal with these technical problems, so we ban disjunctive
explanations.


We believe that, in cases where disjunctive explanations seem
appropriate, it is best to capture this directly in the causal model
%joe13
by having a variable that represents the disjunction.
(Essentially the same point is made 
%joe24
%in \cite{CH97}.)  For
by Chajewska and Halpern \citeyear{CH97}.)  For
example, consider the disjunctive scenario of the arsonist example,
where
there are other potential causes of the fire.  If we want to allow
``there was an arsonist'' to be an explanation without specifically
mentioning who the arsonist is, then it can be easily accomplished by 
%joe13
%adding a variable $\ML$ to the structural model, which
replacing the variables $\ML_1$ and $\ML_2$ in the model by a variable
$\ML$ which is 
%jp14 deleting "is"
%is 1 iff at least one arsonist drops a match.
%joe+: reinserted next line!
1 iff at least one arsonist drops a match.
%on $\ML_1$ and $\ML_2$ is 1.
Then $\ML=1$ becomes an explanation, without requiring disjunctive
explanations.

%joe13
%joe24*: cut this paragraph; we actually don't have a problem with logical
%dependencies, since we can declare them to be impossible contexts in
%our new improved framework.  There is a problem with the model not being
%recursive, but I think we can deal with that too.  On the other hand,
%I'd just rather avoid this can of worms.
\commentout{
Why not just add $\ML$ to the model rather than using it to replace
$\ML_1$ and $\ML_2$?  We have implicitly assumed in our framework that 
all possible combinations of assignments to the variables are possible
(i.e., there is a structural contingency for any setting of the
variables).  If we add $\ML$ and view it as being logically equivalent to
$\ML_1 \lor \ML_2$ (that is, $\ML=1$ {\em by definition\/} iff at least
one of $\ML_1$ and $\ML_2$ is 1) then, for example, it is logically
impossible for there to be a structural contingency where $\ML_1 = 0$,
$\ML_2 = 0$, and $\ML = 1$.  Thus, in the presence of logical
dependences, it seems that we need to restrict the set of contingencies
that can be considered to those that respect the dependencies.  We have
not yet considered the implications of such a change for our framework,
so we do not pursue the matter here.%
\footnote{As a related
matter, note a model with logical dependencies means the model is no longer
recursive.}
}%\end{commentout}

One other point regarding the definition of explanation:
When we ask for an explanation of $\phi$, we usually expect that it not
only explains $\phi$, but that it is true in the actual world.
Definition~\ref{def:explanation1} makes no reference to the ``actual
world'', only to the agent's epistemic state.  There is no difficulty
adding an actual world to the picture and requiring that the explanation
be true in the world.  We can simply talk about an explanation relative
to a pair $(\K,\vec{u})$, where $\K$ is a set of contexts.
%joe24*: no reason to require this here.
%and $\vec{u} \in \K$.  
Intuitively, $\vec{u}$ describes the context in the actual world.  The
requirement that the explanation be true in the actual world then 
becomes $(M,\vec{u}) \sat \vec{X} = \vec{x}$.  Although we have not made
this requirement part of the definition, adding it would 
%joe10
%joe24
%not affect any of our other comments.
have no significant effect on our discussion.
%joe24
%The requirement that $\vec{u} \in \K$ essentially says that $\K$
Once we have the actual world as part of the model, we could also 
require that $\vec{u} \in \K$.  This condition would entail that $\K$ 
represents the agent's knowledge rather than the agent's beliefs: the
actual context is one of the ones the agent considers possible.  

%joe24
%\subsection{Partial Explanations and Explanatory Power}
\section{Partial Explanations and Explanatory Power}\label{s:partialexp}
Not all explanations are considered equally good.  Some
explanations are more likely than others.  
%joe24
%An obvious way to
One way to
%joe8
%deal with this is to bring
define the ``goodness'' of an explanation is by bringing
probability into the picture.  Suppose that the
agent has a probability on the set $\K$ of possible contexts.  In this
case, we can consider the probability of the set of contexts where the
explanation $\vec{X} = \vec{x}$ is true.   For example, if the agent has
reason to believe that electric storms are quite common in both May and
June, then the set of contexts where $\ES=(1,1)$ holds would have greater
probability than the set where either $\ES=(1,0)$ or $\ES=(0,1)$ holds.
Thus, $\ES=(1,1)$ would be considered a better explanation.

%joe20: added
Formally, suppose that there is a probability $\Pr$ on the set $\K$ of
possible contexts.  Then the probability of explanation $\vec{X} = \vec{x}$
is just $\Pr(\vec{X} = \vec{x})$.  While the probability of an
explanation clearly captures some important aspects of how good the
explanation is, it is only part of the story.
%jp9 satisfying the reader curiosity:
The other part concerns the degree to which an explanation
fulfills its role (relative to $\phi$) in the various contexts
considered.
%joe9: better glue, given your addition
%Once we have probability in the picture, we can consider partial
%explanations.
This becomes clearer when we consider {\em partial\/} explanations.
The following example, taken from \cite{Gardenfors1},
%joe9
%gives one case where partiality might be applicable.
is one where partial explanations play a role.


\xam\label{xam7}  Suppose I see that Victoria is tanned and I seek an
explanation.  Suppose that the causal model includes variables for
``Victoria took a vacation in the Canary Islands'', ``sunny in the
Canary
Islands'',  and ``went to a tanning salon''.
%jp8 explicitly preventing my previous misunderstanding
%joe8: moved this down one sentence (I think it's the wrong place for it)
%where going on vacation does not exclude going to a tanning salon.
The set $\K$ includes
contexts for all settings of these variables compatible with Victoria
being tanned.
%joe8
%joe+
%Note that, in particular, there is a context where Victoria both went
Note that, in particular, there is a context where Victoria went both
to the Canaries (and didn't get tanned there, since it wasn't sunny)
and to a tanning salon. G\"ardenfors points out that we normally accept
``Victoria took a vacation in the Canary Islands'' as a satisfactory
explanation of Victoria being tanned and, indeed, according to his
definition, it is an explanation.
%jp8. removing
%(G\"ardenfors' definition is discussed in the next section.)
Victoria taking a vacation is not an
explanation (relative to the context $\K$) in our framework,
since
%joe8: named the context for easy reference
there is a context $\vec{u}^* \in \K$ where Victoria went to the Canary
Islands but it was not sunny,
%jp8 completing the sentence for dummies like me
and in $\vec{u}^*$ the actual cause of her tan is
the tanning salon, not the vacation.
%jp7: Joe, for once, I must agree with Gardenfors; I am
%writing  this comment after two related ones in the
%sequel. Recall that our set $\K$ includes ONLY
%contexts that are compatible with Victoria being tanned. Hence,
%"not sunny" and "on vacation" is  NOT IN K.
%joe24*: rewrote rest of paragraph
Thus, EX2 is not satisfied.  However, intuitively, it is ``almost''
satisfied, since it is satisfied by every context in $\K$  in which
Victoria goes to the Canaries but $u^*$.
%In this case we can view ``Victoria went to the Canary Islands'' as a
%partial explanation
%(in a formal sense to be defined below).
%joe24
The only complete explanation according to our definition is
%For us, the explanation would have to be 
``Victoria went to the Canary Islands {\em and\/} it was sunny.''
``Victoria went to the Canary Islands'' is  a {\em partial\/}
explanation, in a sense to be defined below.
%jp it feels like the next phrase should be deleted??
%, but we are just omitting obvious details.
\exam

%jp8 now that I understand "partial explanation"
%let me try to shorten the description -- it took
%me awful long time to understand the gist of the TV
%set example.
%888
In Example~\ref{xam7}, the partial explanation can be extended to a complete
explanation by adding a conjunct.
But not every partial explanation can be extended
%joe8:
%(by refinement) to a full explanation,
%joe24: changed this consistently below
%to a full explanation.
to a complete explanation.
%joe8
%because the refinement
%needed may involve variables residing outside $\V$.
Roughly speaking, the complete explanation may involve exogenous factors,
which are not permitted in explanations.
 Assume, for example, that going to a tanning
%joe24
%salon was not considered an endogenous variable in our model but,
%rather, the model simply had an exogenous variable $U_s$ that could make
salon was not an endogenous variable in the model;
instead, the model simply had an exogenous variable $U_s$ that could make
Victoria suntanned even in the absence of sun
%joe+
%in Canary islands. Likewise, assume that the weather in
%Canary island was also part of the background context.
in the Canary Islands. Likewise, assume that the weather in
the Canary Islands was also part of the background context.
In this case,  
%joe24* rewrote rest of paragraph
%we would  still consider Victoria's vacation to provide a
Victoria's vacation would still be a 
%joe+
%partial explanation of her sun tan, since the context where
%it fails  to be a cause (no sun in the Canary island)
partial explanation of her suntan, since the context where
it fails  to be a cause (no sun in the Canary Islands)
is fairly unlikely, but we cannot add conjuncts to this
event to totally exclude that context from the
agent's realm of possibilities.
%joe24: added
Indeed, in this model there is no (complete) explanation for Victoria's
tan; it is inexplicable!
%joe24
%This is quite common, as the following example shows.
Inexplicable events are not so uncommon, as the following example shows.

%joe6*: I suspect we can come up with a better story here.
\xam\label{xam8} Suppose that the sound on a television works but there
is
no picture.  Furthermore, the only cause of there being no picture that
the agent is aware of
is the picture tube being faulty.  However, the agent is also
aware that there are times when there is no picture even though the
picture tube works perfectly well---intuitively, there is no picture
``for inexplicable 
reasons''.  This is captured by the causal network described in Figure~\ref{fig-z}, where
$T$ describes whether or not the picture tube is working (1 if it is
and 0 if it is not) and $P$
describes whether or not there is a picture (1 if there is and 0 if
there is not).
\begin{figure}[htb]
\input{psfig}
\centerline{\psfig{figure=fig-z.eps}}
\caption{The television with no picture.}
\label{fig-z}
\end{figure}
The exogenous variable $U_0$ determines the status of the picture tube:
$T = U_0$.
The exogenous variable
$U_1$ is meant to represent the mysterious ``other possible causes''.
If $U_1=0$, then whether or not there is a picture depends solely on the
status of the picture tube---that is, $P = T$.
On the other hand, if
$U_1 = 1$, then there is no picture ($P=0$) no matter what the status of
the
picture tube.  Thus, in contexts where $U_1=1$, $T=0$ is {\em not\/} a
cause of $P=0$.  Now suppose that $\K$ includes a context
$\vec{u}_{00}$ where $U_0=U_1 =0$
%joe24*: rewrote rest of paragraph
and $\vec{u}_{10}$ where $U_0=1$ and $U_1 =0$.
The only cause of $P=0$ in both $\vec{u}_{00}$ and $\vec{u}_{10}$ is $P=0$
itself. 
($T=0$ is not a cause of $P=0$ in $\vec{u}_{10}$, since $P=0$ even if $T$ is
set to 1.)
As a result, there is no explanation of $P=0$ relative to an
epistemic $\K$ that includes $\vec{u}_{00}$ and $\vec{u}_{10}$.
(EX4 excludes the vacuous explanation $P=0$.)
%joe24
On the other hand, $T=0$ is a cause of $P=0$ in all other contexts in
$\K$ satisfying $T=0$ other than $\vec{u}_{00}$.   If the probability of
$\vec{u}_{00}$  
(capturing the intuition that it is unlikely that more than one thing
goes wrong with a television at once), 
then we are entitled to view
$T=0$ as a quite good partial explanation of $P=0$ with respect to $\K$.

%joe24*: added
Note that if we modify the causal model here by adding an
endogenous variable, say $I$, corresponding to the ``inexplicable'' cause
$U_1$ (with equation $I = U_1$), then $I=0$ is a cause of
$P=0$ in the context $u_{10}$ (and both $I=0$ and $T=0$ are causes of
$P=0$ in $u_{00}$).  In this model, $I = 0$ is an explanation of $P=0$.
\exam

%joe24*: added 
Example~\ref{xam8} and the discussion after Example~\ref{xam7}
illustrate an important point.  Adding an endogenous variable
corresponding to an exogenous variable can result in there being an
explanation when there was none before.  This phenomenon of adding
``names'' to create explanations is quite common.  For example, ``gods''
are introduced to explain otherwise inexplicable phenomena; clusters of
symptoms are given names in medicine so as to serve as explanations.
%joe24*: Judea, can you think of another good example?

%jp8xyz resume text
In any case, these examples motivate the following definition of partial
explanation. 
%Let $\cause{\vec{X} = \vec{x}, \phi)$ consist of the contexts $\vec{u}$
%such that $\vec{X} = \vec{x}$ is a cause of $\phi$ in $\vec{u}$.
%joe21*: rewrote definition slightly
%\dfn $\vec{X} = \vec{x}$ is an {\em $\alpha$-partial
%explanation\/} of $\phi$ relative to $(\K,\Pr)$ (where $\Pr$ is a
%probability on $\K$) if there exists a subset $\K'$ of $\K$ such that
%$\vec{X} = \vec{x}$ is an explanation of $\phi$ relative to $\K'$ and
%$\Pr(\K'|\vec{X}=\vec{x}) \ge \alpha$.%
\dfn\label{def:partial} 
Let $\K_{\vec{X} = \vec{x},\phi}$ be the largest subset $\K'$ of $\K$
such 
that $\vec{X} = \vec{x}$ is an explanation of $\phi$ relative to
$\K_{\vec{X} = \vec{x},\phi}$.
(It is easy to see that there is a largest such set; 
%joe22: added
it consists of all the contexts in $\K$ except the ones where
$\vec{X}=\vec{x}$ is true but is not a sufficient cause of $\phi$.)
Then $\vec{X} = \vec{x}$ is a {\em partial explanation of $\phi$ with
goodness $\Pr(\K_{\vec{X}= \vec{x},\phi}|\vec{X} = \vec{x})$}.
Thus, the goodness of a partial explanation measures the extent to which
it provides an explanation of $\phi$.%
\footnote{Here and elsewhere, a formula such as $\vec{X} = \vec{x}$ is
being identified with the set of contexts where the formula is true.
%jp8 I would also condition $\Pr(\K'|\vec{X}=\vec{x}) on phi.
% but, fearing that Joe would object, I  will add here:
%joe8: you know me too well ... I'm comfortable with what you wrote
%though.
Recall that, since all contexts in $\K$ are presumed
%joe21
%compatible with $\phi$, there is no need to condition
to satisfy $\phi$, there is no need to condition
%joe21
%$\Pr(\K_{\vec{X} = \vec{x},\phi}|\vec{X}=\vec{x})$ 
on $\phi$; this probability is
already updated with the truth of the explanandum $\phi$.
Finally, note that our usage of partial explanation is related to,
but different from, that of Chajewska and Halpern \citeyear{CH97}.}
%joe20*: for want of a better term
%The {\em explanatory power\/} of a partial explanation
%The {\em goodness\/} of a partial explanation
%$\vec{X}=\vec{x}$ of $\phi$ is the sup over all $\alpha$ such that
%$\vec{X}=\vec{x}$ is an $\alpha$-partial explanation.
\edfn

In Example~\ref{xam7}, if the agent believes that it is sunny in the
%Canary Islands 90\% of the time (so that the probability of Victoria
%jp8 this sounds like prior probability. It should read:
%joe20: 
%Canary Islands with probability .9.
Canary Islands with probability .9
(that is, the probability that it was sunny given that Victoria is
suntanned and that she went to
the Canaries is .9),
%See: jp7 remark below, why this probability is really ONE,
%given that each member of K' is consistent with phi.
%joe7: I think what I wrote is OK; see above.
then Victoria going to the Canaries is a
%joe20*
%good partial explanation of her being tanned (at the .9 level).  The set
partial explanation of her being tanned with goodness .9.  The 
%joe21
%set $\K'$ 
relevant set $\K'$
consists of those contexts where it is sunny in the Canaries.
%jp8 suggest removing the sequel
%joe8: reinstated for now, pending decision on this example
Similarly, in Example~\ref{xam8}, if the agent believes that the
probability of both the picture tube being faulty and the other
mysterious causes being operative is .1, then $T=0$ is a partial
%joe20*
%explanation of $P=0$ at the .9 level (with $\K'$ consisting of all the
explanation of $P=0$ with goodness .9 (with $\K'$ consisting of all the
contexts where $U_1=1$).

%joe21
%A full explanation is clearly a 1-partial explanation, but we are quite
A full explanation is clearly a partial explanation with goodness 1, but
we are 
%joe21
%quite 
often satisfied with partial 
%joe10
%levels of lower explanatory power, especially if they have high probability.  
%joe20*
%explanations $\vec{X}=\vec{x}$ of lower explanatory power,
explanations $\vec{X}=\vec{x}$ that are not as good,
especially if they have high probability 
%joe10
(\ie if $\Pr(\vec{X} = \vec{x})$ is high).
Note that,
in general, there 
%joe21
%may be a
is a
tension
%between the explanatory power of an explanation and its probability.
between the goodness of an explanation and its probability.

%joe20*: new material
%joe21
%Yet another factor that causes tension is the ``explanatory power'' of
%an explanation.
%joe24: italicized
These ideas also lead to a definition of {\em explanatory power}.
Consider Example~\ref{xam:arson} yet again, and suppose that there is an
endogenous random variable $O$ corresponding to the presence of oxygen.
Now if $O=1$ holds in all the contexts that the agent considers
possible, then $O=1$ is excluded as an explanation by EX4.  
%joe20: added
If the agent
knows that there is oxygen, then the presence of oxygen cannot be part
of an explanation. 
But suppose that $O=0$ holds in one context that the agent considers
possible, albeit a very unlikely one (for example, there may be another
combustible gas).  In that case, $O=1$ becomes a very good partial
explanation of the 
fire.  Nevertheless, it is an explanation with, intuitively, very little
explanatory power.  How can we make this precise?

Suppose that there is a probability distribution $\Pr^-$ on a set $\K^-$
of contexts that includes $\K$.  $\Pr^-$ intuitively represents the
agent's ``pre-observation'' probability, that is, the agent's
prior probability before the explanandum $\phi$ is observed or discovered.
Thus, $\Pr$ 
is the result of conditioning $\Pr^-$ on $\phi$
%joe21
%joe24
%and $\K$ consists of the subset of $\K^-$ that satisfies $\phi$.  
and $\K$ consists of the contexts in $\K^-$ that satisfy $\phi$.  
%joe21
 G\"ardenfors identifies the explanatory
power of the (partial) explanation $\vec{X} = \vec{x}$ of $\phi$ 
with $\Pr^-(\phi|\vec{X} = \vec{x})$  (see \cite{CH97,Gardenfors1}).
If this probability is higher than $\Pr^-(\phi)$,
then the explanation makes $\phi$ more likely.%
%joe22: added footnote and following sentence
\footnote{Actually, for G\"ardenfors, the explanatory power of $\vec{X}
= \vec{x}$ is $\Pr^-(\phi|\vec{X} = \vec{x}) - \Pr^-(\phi)$.  But as far
as comparing the explanatory power of two explanations, it suffices to
consider just $\Pr^-(\phi|\vec{X} = \vec{x})$, since the $\Pr^-(\phi)$
terms will appear in both expressions.  We remark that Chajewska and
Halpern \citeyear{CH97} argued that the quotient
$\Pr^-(\phi|\vec{X})/\Pr^-(\phi)$ gives a better measure of explanatory
power than the difference, but the issues raised by Chajewska and
Halpern are irrelevant to our concerns here.}
Note that since $\K$ consists of all the contexts in $\K^-$ where $\phi$
is true, G\"ardenfors' notion of explanatory power is equivalent to
$\Pr^-(\K| \vec{X} = \vec{x})$.

G\"ardenfors' definition clearly captures some important features of our
intuition.  For example, under reasonable assumptions about
$\Pr^-$, $O=1$ has much lower explanatory power than, say, $\ML_1=1$.
Learning that there is oxygen in the air certainly has almost no
effect on an agent's prior probability that the forest burns down, while
learning that an arsonist dropped a match almost certainly increases it.
However, G\"ardenfors' definition still has a problem.  It basically
confounds correlation with causation.  
For example, according to this definition, the barometer
falling is an explanation of it raining with high explanatory power.

We would argue that a better measure of the explanatory power of
$\vec{X} = \vec{x}$ is $\Pr^-(\K_{\vec{X} = \vec{x},\phi}|\vec{X} =
\vec{x})$.   Note that the two definitions agree in the case that
$\vec{X} = \vec{x}$ 
is a full explanation (since then $\K_{\vec{X} = \vec{x},\phi}$ is just
$\K$, the set of contexts in $\K^-$ where $\phi$ is true).
In particular, they agree that $O=1$ has very low explanatory power,
while $\ML_1 = 1$ has high explanatory power.  
The difference between the two definitions arises if there are contexts
where $\phi$ and $\vec{X} = \vec{x}$ both happen to be true, but
$\vec{X} = \vec{x}$ is not a cause of $\phi$.
%joe20: added
In Example~\ref{xam7}, the context $\vec{u}^*$ is one such context,
since in $\vec{u}^*$, Victoria went to the 
Canary Islands, but this was not an explanation of
her getting tanned, since it was not sunny.  
Because of this difference, for us, the falling barometer has 0
explanatory power as far as explaining the rain.  Even though
the barometer falls in almost all contexts where it rains
(assume that there are contexts where it rains and the barometer does
not fall, perhaps because it is defective, so that the barometer falling
at least satisfies EX4), the barometer falling is not a {\em cause\/} of
the rain in any context.  Making the barometer rise would not result in
the rain stopping!


Again, (partial) explanations with higher explanatory power typically
are 
%jp8 adding a line
more refined and, hence, less
likely, than explanations with less explanatory power.
There is no obvious way to resolve this tension.
%joe18: added
%joe20: cut for IJCAI
%\footnote{One reviewer of this paper suggested using the
%expected utility of the explanation, relative to the person receiving
%it.  However, just because an explanation is very useful (or desirable)
%does not make it more appropriate.}
(See \cite{CH97} for more discussion of this issue.)

%jp. Joe, this is our third repitition of the same
%noninformative relationship to Gardenfors. But, now, after
%we explained twice why his probabilistic approach is faulty,
%the paragraph sounds tired, irrelevant and diversionary. 
%I suggest that we drop this paragraph altogether.
As this discussion suggests,
our definition shares some features with that of G\"ardenfors'
\citeyear{Gardenfors1}.  Like him, we consider explanation relative to
an agent's epistemic state.  
%G\"{a}rdenfors also starts by assuming the agent's epistemic state is
%described by a probability distribution $\Pr$.  For ease of exposition,
%assume that $\Pr$ is a probability on contexts, although G\"{a}rdenfors
%actually considers probabilities on what we would call context-model pairs.
%G\"{a}rdenfors assumes that $\Pr(\phi) = 1$---the agent currently
%believes the explanandum $\phi$.  This is a
%probabilistic analogue of EX1.  
G\"{a}rdenfors also considers a 
``contracted'' epistemic state characterized by the distribution 
$\Pr^-$.  Intuitively, $\Pr^-$ describes the agent's beliefs before
discovering $\phi$.  (More accurately, it describes an epistemic state
as close as possible to $\Pr$ where the agent does not ascribe
probability 1 to $\phi$.)  
%joe24: we didn't do this above; rewrote sentence
%If the agent's current belief in $\phi$ came
%about as the result of an observation $\psi$, then we can take $\Pr$ to
%be the result of conditioning $\Pr^-$ on $\psi$, as we have done above.
If the agent's current epistemic state came about as a result of
observing $\phi$, then we can take $\Pr$ to be the result of
conditioning $\Pr^-$ on $\phi$.
However, G\"{a}rdenfors does necessarily assume such a
connection between $\Pr$ and $\Pr^-$.  In any case, for G\"{a}rdenfors,
$\vec{X} = \vec{x}$ is an explanation of $\phi$ relative
to $\Pr$ if (1) $\Pr(\phi) = 1$, (2) $0 < \Pr(\vec{X} = \vec{x}) < 1$,
and (3) $\Pr^-(\phi|\vec{X} = \vec{x}) > \Pr^-(\phi)$.  
(1) is the probabilistic analogue of EX1.
Clearly, (2) is the probabilistic analogue of EX4.  Finally, (3) says
%joe21
that learning the explanation increases the likelihood of $\phi$.
%$\phi$ in the state before the agent knew $\phi$.  Under this intuition,
%$\vec{X} = \vec{x}$ is a better explanation of $\phi$ than $\vec{X}' =
%\vec{x}'$ if $\Pr^-(\phi|\vec{X} = \vec{x}) > \Pr^-(\phi|\vec{X}' =
%\vec{x'})$.  Very roughly speaking then, G\"{a}rdenfors focuses on
%$\Pr^-(\phi|\vec{X} = \vec{x})$,  
G\"{a}rdenfors focuses on 
the explanatory power of an
explanation, but does not take into account its prior probability.
As pointed out by Chajewska and Halpern \citeyear{CH97}, G\"ardenfors'
definition suffers from 
another defect: 
%joe1
%Since there is no minimality
%requirement like EX3, if $\vec{X} = \vec{x}$ is an explanation of 
%$\phi$, so too is $\vec{X} = \vec{x} \land \vec{Y} = \vec{y}$.  
If there is an explanation of $\vec{Y} = \vec{y}$ at all, then
for all events $\vec{X} = \vec{x}$ 
such that $0 < \Pr(\vec{X}=\vec{x} \land \vec{Y}=\vec{y}) < 1$, $\vec{X} =
\vec{x} \land \vec{Y} = \vec{y}$ is an explanation  of $\vec{Y} = \vec{y}$.
Moreover, it has the highest possible explanatory power.
(Note that, in our definition, EX3 blocks $\vec{X} =
\vec{x} \land \vec{Y} = \vec{y}$ from being a cause of $\vec{Y} = \vec{y}$.)


In contrast to G\"ardenfors' definition, the dominant approach to
explanation in the AI literature, the {\em maximum a posteriori (MAP)\/}
approach (see, for example, \cite{DH90,Pearl,Shim91a}),
focuses on  the 
%joe20*: We need to be a little careful, since we're using the posterior.
%I fudged the point by taking out the word prior altogether
%prior
probability of the explanation,  
%joe22
that is, what we have denoted $\Pr(\vec{X} = \vec{x})$.%
%jpf, I think you meant to write "posterior" or
%"conditional" probability, not "prior".%
\footnote{The MAP literature typically considers $\Pr^-(\vec{X} = \vec{x} |
\phi)$, but this is equivalent to $\Pr(\vec{X} = \vec{x})$.}
The MAP approach is based on the intuition that
the best explanation for an observation is the state of the world (in
our setting, the context) that is most probable 
%joe20
%(given the evidence).  
given the evidence.  
%To convert this to our setting, assume that we are given a probability
%$\Pr$ on the set of contexts.  (If the agent knows that the actual
%context is one in a set $\K$, then all the contexts not in $\K$ are
%given probability 0.)  
%joe22: cut this; I agree with you that it's irrelevant
%The most probable explanation for $\phi$ is then
%the context $\vec{u}^*$ such that 
%%joe20*: don't need to condition on $\phi$ here; \Pr is the posterior
%%$\Pr(\vec{u}^*|\phi) = \max_{\vec{u}} \Pr(\vec{u}|\phi)$.   
%$\Pr(\vec{u}^*) = \max_{\vec{u}} \Pr(\vec{u})$.   
%Thus, an explanation is a (complete) context.  This
%means that part of the explanation will include totally irrelevant facts
%(the agent sneezed).  Moreover, it is quite sensitive to the description of
%the context (see \cite{CH97} for details) and does not directly take
%causality into account.  
There are various problems with this approach (see \cite{CH97} for a
critique).  Most of them can be dealt with, except for the main one:
it simply ignores the issue of explanatory power.
%
%
%To some extent, these problems can be dealt with by
%limiting the set of candidate explanations to ancestors (of the
%explanandum) in the causal network; this also avoids many of the problems
%associated with non-causal approaches (although it requires there to be
%a causal network in the background).  However, the MAP approach does
%not go far enough.  One problem is that propositions with extremely high
%prior probabilities (e.g., that oxygen is present in the room)
%will also receive high posterior probabilities,
An explanation like $O=1$ has a very high probability, even though it is
intuitively irrelevant to the forest burning down.
%joe20*: I didn't find this very clear.  Part of the problem is that the
%notation is inconsistent with the notation above.  The P should
%probably be Pr^-, since it's the prior.  I don't know what the c' is
%below.  
%To remedy this problem, more intricate combinations of the probabilistic
%parameters $[P(e|c), P(e|c'), P(c|e), P(c)]$ have been
%suggested to quantify the causal relevance of the cause $c$ to
%the  effect $e$. 
%joe19: Judea, is there a reference to someone who tried using more
%complicated combinations of parameters
%jpf: Yes, Good (1993) continues to press for his log
%likelihood measures, Michie (2000) continues his tradition,
%and I believe Salmon also filled volumes with this acrobatics
%when he was young.
%joe20*: shrunk this a bit
%Unfortunately, no such combination can
%succeed. Any proposition $c$ that is earlier than $e$
%can, with a small stretch of imagination, be thought of as having
%some influence on $e$, however feeble. This would then
%qualify $c$ as an ancestor of $e$ in the causal network and
%would permit $c$ to compete and win against genuine explanations
%by virtue of $c$ having strong spurious association with $e$  
To remedy this problem, more intricate combinations of the 
quantities $\Pr(\vec{X} = \vec{x})$, $\Pr^-(\phi|\vec{X}=\vec{x})$, and 
$\Pr^-(\phi)$ have been suggested 
to quantify the causal relevance of $\vec{X} = \vec{x}$ on $\phi$ but,
as argued 
%jpf adding:
%joe24
%in \cite[p.~221]{pearl:2k}, without taking causality into 
by Pearl \citeyear[p.~221]{pearl:2k}, without taking causality into
account, no such 
combination of parameters can work.

\section{The General Definition}\label{sec:general}
%joe8
%As we observed earlier,
%an explanation might include information about
In general, an agent may be uncertain about the causal model, so
an explanation will have to include information about it.
(G\"ardenfors \citeyear{Gardenfors1} and Hempel
\citeyear{Hempel65}
make similar observations, although they focus not on causal
%information, but on statistical information; we return to this
%jp9. Hemple went beyond statistics; he talked about
%the laws of physics I would say:
information, but on statistical and nomological information;
we return to this
point below.)  It is relatively straightforward to extend our definition
%jp8 rephrasing
%of explanation to handle this.
of explanation to accommodate this provision.
Now an epistemic state $\K$ consists not
only of contexts, but of pairs $(M,\vec{u})$ consisting of a causal
model $M$ and a context $\vec{u}$.  
%joe24
%(Call such a pair a {\em
(Recall that such a pair is a {\em
situation}.)  Intuitively, now an explanation should consist of some
causal information (such as
%jp8 for variety sake
``prayers do not cause fires'')
%the only causes of fires are arsonists and lightning'')
and the facts that are true.
%joe7: rewrote, per our earlier email discussion
%Unfortunately, our language
%is too weak to allow us to express facts such as ``the {\em only\/}
%cause of $A$ is $B$''.  The question of what is an appropriate language
%for expressing such information is an interesting one, but one that is
%beyond the scope of this paper.  Thus, to simplify matters, we assume
%that an explanation has the form $(\M',\vec{X}=\vec{x})$, where $\M'$ is
%a set of causal models (over some fixed signature).
%A statement like ``the only causes of fire
%are arsonists and lightning'' corresponds to a set $\M'$ of causal
%models where this is indeed the case.
Thus, a {\em (general) explanation\/} has the form $(\psi,
\vec{X}=\vec{x})$, where
$\psi$ is an arbitrary formula in our causal language and, as before,
$\vec{X}=\vec{x}$ is a conjunction of primitive events.
We think of the $\psi$ component as consisting of some causal information
%joe8: for consistency with your earlier change
%(such as ``the only possible causes of fire are arsonists and
%lightning'', which corresonds to a rather conjunction of
%statements of the form $(F=i) \rimp [Y=y](F=i)$, where $Y$ is any
%variable other than arsonist and lightning).
%joe7: added paragraph
(such as ``prayers do not cause fires'', which corresponds to a
conjunction of statements of the form 
%joe10
%$F=i \rimp [P=x](F=i)$, where $P$
%joe16: made the wrong fix
%$F \gets i \rimp [P=x](F=i)$, where $P$
$(F = i) \rimp [P \gets x](F=i)$, where $P$
is a random variable describing whether or not prayer takes place).
The first component in a general explanation
is viewed as restricting the set of causal models. To make this precise,
given a causal model $M$, we say $\psi$ is {\em valid in $M$\/}, and
write $M \sat \psi$, if $(M,\vec{u}) \sat \psi$ for all contexts
$\vec{u}$
%joe10
consistent with $M$.
With this background, it is easy to state the general definition.

%joe7:
%\dfn\label{def:explanation2} {\em $(\M,\vec{X} = \vec{x})$ is an
\dfn\label{def:explanation2} {\em $(\psi,\vec{X} = \vec{x})$ is an
explanation of $\phi$ relative to a set $\K$ of situations\/} if the
following conditions hold:
\begin{description}
\item[{\rm EX1.}] $(M,\vec{u}) \sat \phi$ for each situation $(M,\vec{u})
\in \K$.
%joe24
%\item[{\rm EX2.}]  For all $(M,\vec{u}) \in \K$ such that
%$(M,\vec{u}) \sat \vec{X} = \vec{x}$ and
%$M \sat \psi$,
%joe+
%\item[{\rm EX2.}]  $\vec{X} = \vec{x}$ is a sufficient case of $\phi$ in
\item[{\rm EX2.}]  $\vec{X} = \vec{x}$ is a sufficient cause of $\phi$ in
$(M,\vec{u})$ for all $(M,\vec{u}) \in \K$ such that
$(M,\vec{u}) \sat \vec{X} = \vec{x}$ and
$M \sat \psi$.
%joe8: again
%joe24
%$\vec{X} = \vec{x}$ is a weak cause of $\phi$ in $(M,\vec{u})$.
$\vec{X} = \vec{x}$ is a sufficient cause of $\phi$ in $(M,\vec{u})$.
%joe8: cut
%there exists a partition $(\vec{Z},\vec{W})$ of $\V$ with $\vec{X}
%\subseteq \vec{Z}$ and some
%setting $(\vec{x}',\vec{w}')$ of the variables in $(\vec{X},\vec{W})$
%such that if $(M,u) \sat \vec{Z} = \vec{z}^*$, then
%\begin{description}
%\item[{\rm (a)}]
%$(M,\vec{u}) \sat [\vec{X} \gets \vec{x}',
%%joe7: for consistency
%%\vec{W} \gets \vec{w}'](\neg \phi \land
%%(\land_{Z \in \vec{Z}} (Z \ne z^*)))$.
%\vec{W} \gets \vec{w}']\neg \phi$.
%\item[{\rm (b)}]
%$(M,\vec{u}) \sat [\vec{X} \gets \vec{x}, \vec{W} \gets \vec{w}'](\phi
%\land (\vec{Z} = \vec{z}^*))$.
%\end{description}
\item[{\rm EX3.}]
%joe7:
%$\M$ and $\vec{X}$ are minimal; there is no pair
%$(\M',\vec{X}' = \vec{x}') \ne (\M,\vec{X} = \vec{X})$ satisfying EX2
%such that $\M' \inter \M(\K) \supseteq \M \inter \M(\K)$,
$(\psi,\vec{X}=\vec{x})$ is minimal; there is no pair
%joe18
%$(\psi',\vec{X}' = \vec{x}') \ne (\psi,\vec{X} = \vec{X})$ satisfying %EX2
$(\psi',\vec{X}' = \vec{x}') \ne (\psi,\vec{X} = \vec{x})$ satisfying EX2
such that $\{M'' \in M(\K): M'' \sat \psi'\} \supseteq
\{M'' \in M(\K): M'' \sat \psi\}$,
 where $\M(\K) = \{M: (M,\vec{u}) \in \K \mbox{ for some } \vec{u}\}$,
$\vec{X}' \subseteq \vec{X}$, and $\vec{x}'$ is the restriction of
$\vec{x}$ to the variables in $\vec{X}'$.
%joe18: added
Roughly speaking, this says that no subset of $X$ provides a 
%joe24
%weak
sufficient
cause of $\phi$ in more contexts than those where $\psi$ is valid.
\item[{\rm EX4.}]
$(M,\vec{u}) \sat \neg (\vec{X}=\vec{x})$ for some $(M,\vec{u}) \in \K$
and $(M',\vec{u}') \sat \vec{X}=\vec{x}$ for some $(M',\vec{u}') \in
\K$. \eprf
\end{description}
\end{definition}
%jp elaborating
%Note that, in EX2, we now restrict to situations $(M,\vec{u}) \in \K$
Note that, in EX2, we now restrict the requirment of
sufficiency to situations $(M,\vec{u}) \in \K$
that satisfy both parts of the explanation $(\psi,\vec{X} = \vec{x})$, in
%joe7
%that $M \in \M$ and $(M,\vec{u}) \sat \vec{X} = \vec{x}$.  Abusing
that $M \sat \psi$ and $(M,\vec{u}) \sat \vec{X} = \vec{x}$.
%joe7:
%Abusing
%notation somewhat, this means that $(M,\vec{u} \sat \M \land \vec{X} =
%\vec{x}$.  In EX3, the requirement that $\M' \inter \M(\K) \supseteq
%\M \inter \M(\K)$ is the analogue of the requirement that $\vec{X}'
%\subseteq \vec{X}$, since if $\vec{X}' \subseteq \vec{X}$ and $\vec{x}'$
%is the restriction of $\vec{x}$ to $\vec{X}'$, then the set of causal
%models $M$ satisfying $\vec{X} = \vec{x}$ is a subset of that satisfying
%$\vec{X}' = \vec{x}'$.
%joe7
Furthermore, although both components of an explanation are
formulas in our causal language, they play very different roles.
The first component serves to restrict the set of causal models
considered (to those with the appropriate structure); the second
describes a cause of $\phi$ in the resulting set of situations.

Clearly Definition~\ref{def:explanation1} is the special case of
Definition~\ref{def:explanation2}
where there is no uncertainty about the causal structure
(i.e., there is some $M$ such that if $(M', \vec{u}) \in \K$, then $M =
M'$).  In this case, it is clear that we can take
%joe7
%$\M$ in the explanation to be $\{M\}$ (or any superset of $\{M\}$.
$\psi$ in the explanation to be $\true$.


\xam
%jp8 I suggest  shortening next paragraph, assuming that
% we eliminate example 5.3. and discussion of Gardenfors.
%joe8: I don't feel strongly about this.  It's just that it's apparently
%a classic example, so it would be nice to say we can handle it easily.
Using this general definition of causality, let us consider
%our approach handles
Scriven's \citeyear{Scriven59} famous paresis example, 
%joe16
which has caused problems for many other formalisms.
%in much the same way that G\"{a}rdenfors does.
Paresis develops only in patients who
have been syphilitic for a long time, but only a small number of
patients who are syphilitic in fact develop paresis.  Furthermore, 
%joe18
according to Scriven,
no other factor is known to be relevant in the development of paresis.%
\footnote{Apparently there are now other known factors, but this does
not change the import of the example.}
This description is captured by a simple causal model $M_P$.
%with a structure similar to that of Example~\ref{xam8},
%but with some critical differences.
There are two endogenous variables,
$S$ (for syphilis) and $P$ (for paresis), and two exogenous
variables, $U_1$, the background factors that determine $S$, and
$U_2$, which intuitively represents ``disposition to paresis'',
%joe_
%i.e., the factors that determine, in conjunction with
%syphilis, whether or not paresis actually develops.
that is, the factors that determine, in conjunction with
syphilis, whether paresis actually develops.
%If $U_2 = 0$, then paresis does not develop, even if
%the patient has syphilis; if $U_2 = 1$, it does.
An agent who knows this causal model and that a patient
has paresis does not need an explanation of why: he knows without
being told that the patient must have syphilis and that $U_2=1$.
On the other hand, for an agent who does not know the
causal model (i.e., considers a number of causal
models of paresis possible), 
%joe24*: should we say more about how \phi_P characterizes M_P
%$(\{M_P\},S=1)$ is an explanation of
%jp0 I believe next sentence should read \psi, not \phi
%$(\phi_P,S=1)$ is an explanation of paresis, where $\phi_P$ is a formula
$(\psi_P,S=1)$ is an explanation of paresis, where $\psi_P$ is a formula
that characterizes $M_P$.  
\exam

%joe24*: this material used to be before the example; I've moved it here
%and done some major rewriting, with more detail.  Should we say more?
Definition~\ref{def:explanation2} can also be extended to deal naturally
with probability.  Actually, probability plays a role in two places.
First, there is  a probability on the situations in $\K$, analogous to
the probability on contexts discussed in Section~\ref{s:partialexp}.
Using this probability, it is possible to talk about the goodness of a
partial explanation and  to talk about explanatory power, just as
%joe+
%before.   In addition, probability ca also be added to causal models to
before.   In addition, probability can also be added to causal models to
get {\em probabilistic causal models}.  A probabilistic 
causal model is a tuple $M = (\S,\F,\Pr)$, 
where $M =(\S,\F)$ is a causal model and $\Pr$ is a probability measure
%joe7: since I use $\S$ below, I think it's worth using above
on the contexts defined by signature $\S$ of $M$.  In a probabilistic
causal model, it is possible to talk about the probability that
$X=3$; this is just the probability of the set of context in $M$ where
$X=3$.  More importantly for our purposes, it is also possible to say
``with probability .9, $X=3$ causes $Y=1$''.  Again, this is 
just the probability of the set of contexts where $X=3$ is the cause of
$Y=1$.  
%Thus, probabilistic causal models can capture 
%statistical information of the kind considered by G\"{a}rdenfors and
%Hempel.  

Once we allow probabilistic causal models, explanations can include
statements like ``with probability .9, working with asbestos causes lung
cancer''.  Thus, probabilistic causal models can capture 
statistical information of the kind considered by G\"{a}rdenfors and
Hempel.   To fit such statements into the framework discussed above, we
must extend the language to allow statements about probability.  For example,
$\Pr([X\gets 3](Y=1)) = .9$, ``the probability that setting $X$ to 3
results in $Y$ being 1'', would be a formula in the language.  Such
formulas could then become part of the first component $\psi$ in a
general explanation.%
\footnote{We remark that G\"{a}rdenfors also consider two types of
probability measures, one on his analogue of situations, and one on the
worlds in a model.  Like here, the probability measure on worlds in a
%joe+
%model allows to have explanations with statistics information, while the
model allows explanations with statistical information, while the
probability on situations allows him to define his notion of explanatory
power.}

\section{Discussion}\label{sec:discussion}
%joe20*
We have given a formal definition of explanation in terms of
causality.  As we mentioned earlier, there are not too many formal
definitions of explanation in terms of causality in the literature.
One of the few exceptions
%joe+
%is Lewis~\citeyear{Lewis86b}, who
is given by Lewis~\citeyear{Lewis86b}, who
defends the thesis that ``to explain an event is to provide some
information about its causal history''.  While this view is compatible
with our definition, there is no formal definition given to allow for a
careful comparison between the approaches.  
%jpf This is the appropriate way to insert what I wrote
%relative to Lewis standard account. 
In any case, if we were to define causal history in terms of Lewis's
%joe**
%\citeyear{Lewis86a} definition of causality, we would
\citeyear{Lewis73} definition of causality, we would
inherit all the problems of that definition.
%joe20*: my concern is that all these will be meaningless to the reader
%(e.g., overdetermination, commitment to transitivity, sensitivity to
%quiescient factors)  
%that have been identified with Lewis' account (e.g., see
%joe20
%Pearl, 2000; chapter 10). 
%\cite[Chapter 10]{pearl:2k}).
%Our approach avoids these problems
%by (1) defining explanation as the removal of 
%uncertainty about actual causation.
%(2) basing actual causation on a special kind of (non-transitive) 
%conterfactual dependencies, as formulated in Definition~\ref{actcaus}.
Our definition avoids these problems.

We have mentioned one significant problem of the definition
already: dealing with disjunctive explanations.  Disjunctions cause
problems in the definition of causality, which is why we do not deal
with them in the context of explanation.  As we pointed out
earlier, it may be possible to modify the definition of causality so as
to be able to deal with 
%joe24
%conjunctions 
disjunctions
without changing the structure of
our definition of explanation.  
%joe24; this isn't true ...
%We are currently exploring this.
In addition, our definition gives no tools for dealing with the
inherent tension between explanatory power,
%joe20*
%and prior beliefs.  Clearly
goodness of partial beliefs, and the probability of the explanation.
Clearly this is an area that requires further work.

%joe24*: should we have a rousing final paragraph?

%joe7: cut for now
\commentout{
\subsection{A comparison to G\"ardenfors' definition}
G\"ardenfors' definition of explanation is one of the more formal ones
given in the literature.  This makes it easier to compare ours to his.
Many of the points we make, though, apply to other attempts to define
explanation.

The following summary and critique of G\"ardenfors' definition is
largely taken from \cite{CH97}.
For the purposes of this discussion, we
restrict to simple explanations, where the causal structure is assumed
to be known, although G\"{a}rdenfors explicitly allows statistical
information in his explanations.  Roughly speaking, for G\"{a}rdenfors,
$\vec{X} = \vec{x}$ is
an explanation of $\phi$ if $\Pr(\phi|\vec{X} = \vec{x}) > \Pr(\phi)$.
That is,
$\vec{X} = \vec{x}$ is an explanation of $\phi$ if learning
$\vec{X} = \vec{x}$ raises the probability of $\phi$.
%jp7: replacing next sentence with one that would put
%his proposal in historical context.
%In order to flesh out this intuition, we need to make
%precise what probability measure we are using.
%joe7: I actually think Gardenfors' usage is consistent with everyone
%else's
%However, whereas most philosophers (e.g., Good (1951))
Most philosophers (e.g., Good \citeyear{Good51}) used $\Pr(\phi)$ to mean
the agent's prior probability just before discovering $\phi$.
%joe7: I don't think this is quite right
%G\"{a}rdenfors uses another probability, one
%that embodies some, but not all, of the information
%provided by $\phi$.
G\"{a}rdenfors tries to capture this intuition, without necessarily
assuming that there was a sequence of events, the last of which
was the discovery of $\phi$.

As we mentioned earlier, G\"{a}rdenfors also asks for explanations
only for facts that are already known; for him, this means that they
have probability 1.
Clearly, nothing we can learn can raise the probability of a known fact
beyond 1.  G\"{a}rdenfors' intuition is that we ask for an explanation
of $\phi$ only if $\phi$ is unexpected.  That is, if
$\Pr_{\phi}^-$ describes the agent's probability distribution in the
{\em contracted\/} belief state, before $\phi$ was discovered, then we
expect
$\Pr_\phi^-(\phi)$ not to be too high.
%jp7 Joe, Sorry, I cant call this acrobatics "intuition"
%unless we can explain to the reader why "the belief state
%before $\phi$ was discovered" should not equal the
%traditional prior probability of phi (just
%before  its  discovery), and consequently, why the belief state after
%the discovery should not  equal  the posterior Pr(*|\phi).
%What happened? we/Gardenfors suddenly cease to use
%conditionalization in representing the process of
%discovering new facts?
%I find the contraction operator to be a poor  coverup
%of someone's lack of intuition. But since you are so
%fascinated with Gardenfors, how  about compromising on
% "construction", instead of "intuition" ??
%joe7: If there is a state just before the current one where \phi
%was discovered, then I think Gardenfors would be happy to do just what
%you said.  He certainly has no problem with condiitoning.
An explanation $\vec{X} =
\vec{x}$ would raise the probability
of $\phi$ in the contracted belief state, that is, we have
$${\Pr}_\phi^-(\phi|\vec{X} = \vec{x}) > {\Pr}_\phi^-(\phi).$$

To formalize these intuitions,
%jp7:  again?, I can't!. Even "construction" wont do here.
% how about  saying:
%To formalize these vague steps, ???
%Or, more drastically, how about dropping the whole
%Gardenfors story? or at least let me write a footnote:
%"Some researchers, the second author among them,
%consider the contraction operator
%to be ill defined, ill conceived and lacking any
%parallel in human thought."  ??
%I must protect the dignity of our paper!
G\"{a}rdenfors characterizes a
(probabilistic) epistemic state using the possible worlds model.
His worlds correspond to our contexts (or situations, in the more
general case).
At any given time, an agent is assumed to consider a set of
worlds possible and to have a probability measure on this set.
A {\em belief state\/} for G\"{a}rdenfors is a pair
$\B = \< W, \PrB \>$, where
$W$ is a set of possible worlds (or possible states of the world) and
$\PrB$ is a probability measure on $W$.   (Thus, a belief state can
be viewed as a probabilistic causal model without the structural
equations.)  A formula $A$ is said to be
{\em accepted\/} in belief state $\B$ if
$\PrB(A) = 1$.
We sometimes abuse notation and write $A \in \B$ if $A$ is accepted in
belief state $\B$.

Given belief state $\B\! =\! \<W,\PrB\>$ of an agent, let $\B^-_\phi\!
=\!
\<W^-_\phi, \PrB^-_\phi\>$
denote the {\em contraction\/} of $\B$ with respect to $\phi$, i.e.,
the belief state characterizing the agent's beliefs
that is as close to $\B$ as possible such that $\phi \notin \B^-_\phi$.
G\"{a}rdenfors describes a number of postulates that $\B^-_\phi$ should
satisfy, such as $\B^-_\phi\; =\; \B$ if $\phi\! \notin\! \B$.  It is
beyond the scope of this paper to discuss these postulates
(see \cite{AGM85}).
However, these postulates do not serve to specify $\B^-_\phi$ uniquely;
that is, given $\B$ and $\phi$, there may be several belief states
$\B'$ that satisfy the postulates.

We can now present G\"{a}rdenfors' definition of explanation.

\dfn
{\rm (from \cite{Gardenfors1})}
$\vec{X} = \vec{x}$ is an explanation of $\phi$ relative
to $\B = \<W,\PrB\>$ if the following conditions hold:
\begin{enumerate}
\item[{\rm EX1$'$.}] $\phi \in \B$.
\item[{\rm EX2$'$.}] $\PrB_\phi^-(\phi|\vec{X} = \vec{x}) >
\PrB_\phi^-(\phi)$.
\item[{\rm EX3$'$.}] $\PrB(\vec{X} = \vec{x}) < 1$ (that is, $\vec{X} =
\vec{x} \notin \B$).
\end{enumerate}
The {\em explanatory power\/} of $\vec{X} = \vec{x}$ is
$\PrB_\phi^-(\phi|\vec{X} = \vec{x}) - \PrB_\phi^-(\phi)$.%
\footnote{In \cite{CH97} it is suggested that explanatory power be defined
as a quotient rather than a difference; this issue is not relevant to
our discussion.}
\edfn

EX1$'$ corresponds to our EX1, while EX3$'$ corresponds to the first
half of EX4 (\ie there exists a context $\vec{u}$ such that
$(M,\vec{u}) \sat \neg(\vec{X} = \vec{x})$.  There are no other obvious
analogies between the definitions.

While G\"{a}rdenfors' definition has some compelling features (see
\cite{Gardenfors1} for further discussion), as pointed out in
\cite{CH97}, it also has some serious problems,
both practical and philosophical.  We briefly review these problems
here.
\begin{itemize}
\item EX3$'$ is intended to block $\phi$ from being an
explanation of itself (if $\phi$ is of the form $\vec{X} = \vec{x}$); it
clearly succeeds because $\PrB(\phi) = 1$ according to EX1.
However, there are many other explanations that it does not block.
For example, consider the original arsonist example and suppose that it
included a variable for sneezing (which we think of as being independent
of whether there is a fire).  Although $F=1$ is not an explanation of
itself, if $S=1$ stands for the arsonist sneezing and we assume, quite
reasonably, that $\PrB(S=1) < 1$ and $\PrB^-_{F=1}(F=1 \land S=1) > 0$,
then $F=1 \land S=1$ is an explanation of $F=1$.   Moreover, it will
have optimal explanatory power,
since $\PrB^-_{F=1}(F=1|F=1 \land S=1) = 1$.  This is clearly
unreasonable; there being a fire and someone sneezing certainly
shouldn't be considered an explanation of there being a fire!
More generally, note that we can add such irrelevant conjuncts to any
explanation to get an explanation with equivalent explanatory power.

Our minimality condition EX3 blocks the addition of such irrelevant
conjuncts. We could add a similar minimality condition to
G\"{a}rdenfors'
definition, but we must be careful, since sometimes adding a
conjunct to an explanation significantly raises its explanatory power.
The requirement would have to say something like ``there is no `smaller'
explanation with the same explanatory power''.

\item According to G\"{a}rdenfors' definition, testing whether
$\vec{X}=\vec{x}$ is an explanation of $\phi$ requires consideration not
only of an agent's belief state but of her contracted belief state.
In general, it is not clear where the contraction is coming
from (although a concrete proposal is provided in \cite{CH97},
using Bayesian networks).
%jp7: Joe, if you really insist on spending so many words
%beating a dead horse, let me add my own 2 cents here.
In particular, it is not clear why an agent having
probability $\Pr(\phi)$ prior to observing $\phi$
would not revert back to \PrB_\phi^-(\phi)$= $\Pr(\phi)$
after observing, then retracting $\phi$. The reason
Gardenforse does not commit to this straightforward retraction
operator is to avoid the myrid of problems associated with the
usual "probability  raising" criterion
$\Pr(\phi|\vec{X} = \vec{x}) > \Pr(\phi)$.
(see  Pearl, 2000 p.253-256).
For instance, aiming a gun at and shooting a person from 1,000 meters
away will only qualify as a weak explanation for
that person's death, owing to the very low
tendency of shots fired from such long distances to
hit their marks. Commonsense tells us that the shot
counts as a strong for explanation the death, because
the fact that the  shot did hit its mark implies that
conditions for accurate shooting (or accidental
wind conditions) were particulary favorable
on that singular day. Thus, the information provided by
$phi$ should not be retracted altogether.
Our account captures this information
by restricting $K$ to contexts consistent with $\phi$
(which amounts to conditioning on $\phi$)
prior to computing the explanatory power of X=x.
How Gardenforse's contraction
captures this information remains a mystery,
(though he gets the right answer, through hand waving,
in Victoria's example)
%jp7: Joe, looking back at examples 5.2, and 5.3,
%I do not see that we condition
%on phi -- perhaps we should emphasize that point.
%This is important: on page 27 we talk  about a parobabilistic model
%being a pair <M Pr>, also in Def 5.4 (page 25) we talk about Pr on
%K, but we do not state if this Pr is before or after
%observing phi. If it is before, then what happens to Pr
%when we obwerve phi? Do we adhere to conditionalization? or
%go through some sort of contraction acrobatics (like G)?
%joe7: this is the Pr after observing phi, since it is a probability on
%K, which is a set of contexts in all of which phi is true.  The
%notion of "observing phi" simply doesn't arise for us.  We don't have
%to worry about the state of the world before observing phi.  I think
%this is a real feature in the definition (which perhaps should be
%stressed).
%If it is after, then
%the definition of a probabilistic causal model should contain
%another component: phi. and would not be applicable in
%testing explanations of other propositions, say phi'.
%we need to clarify this point.
% Thinking more in this connection, it seems to me that the probability
%of sunshine given Victoria's vacation is ONE, because we also
%know she is suntanned.
%joe7: the above is not true, since she may have gone to a tanning salon
%Thinking more in this connection, I dont see why you define
%explanatory power in terms of P(K'|x), given that we wish
%to "consider the probability of the set of contexts where
%the explanation X=x is true" (page 23). The Victoria
%example shows the problem associated with such reversal.
%joe7: let's discuss this more
\item  Perhaps most significant of all, G\"{a}rdenfors' definition is
not causal.   The fact that learning $\vec{X}=\vec{x}$ raises the
probability of $\phi$ does not
by itself qualify $\vec{X}=\vec{x}$ to be an explanation of $\phi$.  For
example, suppose
$s$ is a symptom of disease $d$ and Bob knows this.  If Bob learns from
a doctor that
David has disease $d$ and asks the doctor for an explanation, he
certainly would not accept as an explanation that David has
symptom $s$, even though $\PrB^-_{D=d}(D=d|S=s) > \PrB^-_{D=d}(D=d)$.
G\"ardenfors is aware of this issue, and
discusses it in some detail \cite[p.~205]{Gardenfors1}.  He would call
$S=s$ an explanation of $D=d$, but not a {\em causal\/} explanation.
For $\vec{X} = \vec{x}$ to be a causal explanation of $\phi$, it must
not only be an explanation of $\phi$ (in the sense of EX1$'$-3$'$ above)
but also a cause of $\phi$.  This is certainly closer in
spirit to our definitions (although G\"{a}rdenfors allows the
possibility of non-causal explanations, while we do not).
Unfortunately, G\"{a}rdenfors' notion of causal belief, expressed in
terms of probabilities in certain contracted belief sets, does adequately
deal not with many examples of causality (for example, it does
not deal well with overdetermination, as in Example~\ref{xam2}).
%jp7 adding
Moreover, it cannot deal with even simple preemption, since
reagrdless of how one interprets contracted probabilities,
EX2' is not sensitive to the causal structure leading from X
to phi (see Pearl 2000, page 311, for the role of structural
information)
\end{itemize}
}%\end{commentout}

\appendix
\section{Appendix: The Formal Definition of Causality}
%joe**
To keep this part of the paper self-contained,
we reproduce here the formal definition of actual causality from
%joe*
%\cite{HP01b}.  
Part I.

\dfn\label{actcaus}
(Actual cause)
$\vec{X} = \vec{x}$ is an {\em actual cause of $\phi$ in
$(M, \vec{u})$ \/} if the following
three conditions hold:
\newcounter{enumerate}
\begin{description}
\item[{\rm AC1.}]\label{ac1} $(M,\vec{u}) \sat (\vec{X} = \vec{x}) \land
\phi$.
(That is, both $\vec{X} = \vec{x}$ and $\phi$ are true in the actual
world.)
\item[{\rm AC2.}]\label{ac2}
There exists a partition $(\vec{Z},\vec{W})$ of $\V$ with $\vec{X}
\subseteq \vec{Z}$ and some
setting $(\vec{x}',\vec{w}')$ of the variables in $(\vec{X},\vec{W})$
%joe20: added parens
%such that if $(M,\vec{u}) \sat Z = z^*$ for $Z \in \vec{Z}$, then
such that if $(M,\vec{u}) \sat (Z = z^*)$ for 
%joe**
all
$Z \in \vec{Z}$, then
\begin{description}
\item[{\rm (a)}]
$(M,\vec{u}) \sat [\vec{X} \gets \vec{x}',
\vec{W} \gets \vec{w}']\neg \phi$.
In words, changing $(\vec{X},\vec{W})$ from $(\vec{x},\vec{w})$ to
$(\vec{x}',\vec{w}')$ changes
%joe20
%$\phi$ from true to false,
$\phi$ from true to false;
\item[{\rm (b)}]
$(M,\vec{u}) \sat [\vec{X} \gets
%joe**: as in part I
\vec{x}, \vec{W'} \gets \vec{w}', \vec{Z}' \gets \vec{z}^*]\phi$ for 
all subsets $\vec{W'}$ of $\vec{W}$ and all subsets $\vec{Z'}$ of $\vec{Z}$. 
In words, setting any subset of variables in $\vec{W}$ to their values\
in $\vec{w'}$ should have no 
effect on $\phi$ 
%or on any variable in $\vec{Z}$
as long as $\vec{X}$ is kept at its current value $\vec{x}$,
even if all the variables in an arbitrary subset of $\vec{Z}$ are set to
their original values in the context $\vec{u}$.
%joe11: footnote is now unnecessary
%\footnote{In all of our examples, $\phi$ is a Boolean combination of
%$Z = z^*$ for variables $Z \in \vec{Z}$, so the fact that setting
%$\vec{W}$ to $\vec{w}'$ has no effect on $\phi$ follows from the fact
%that it has no effect on any variable in $\vec{Z}$.}
%     \end{itemize}
\end{description}
\item[{\rm AC3.}] \label{ac3}
$\vec{X}$ is minimal; no subset of $\vec{X}$ satisfies
conditions AC1 and AC2.
Minimality ensures that only those elements of
the conjunction $\vec{X}=\vec{x}$ that are essential for
changing $\phi$ in AC2(a) are
considered part of a cause; inessential elements
are pruned. \bbox
\label{def3.1}  %%changed from {def2.2}
%joe4: moving end defintion marker
\end{description}
%\edfn
\end{definition}
%joe8:

$\vec{X} = \vec{x}$ is a {\em sufficient cause\/} of $\phi$ in
$(M,\vec{u})$ if AC1 and AC2 hold, but not necessarily AC3.

%joe**
%We remark that in \cite{HP01b}, a slight generalization of this
We remark that in Part I, a slight generalization of this
definition is considered.  Rather than allowing {\em all\/} settings of
$\vec{X}$ and $\vec{W}$ in AC2, the more general definition presupposes
a set of allowable settings.  All the settings used in AC2 must come
from this allowable set.  It is shown that by generalizing in this way,
it is possible to avoid a number of problematic examples.

\subsection*{Acknowledgments:} Thanks to Riccardo Pucella and Vicky
Weissman for useful comments.

\bibliographystyle{chicago}
\bibliography{z,joe,refs,expl} %%,book}
\end{document}




actcaus1.bbl
\begin{thebibliography}{}

\bibitem[\protect\citeauthoryear{Chajewska and Halpern}{Chajewska and
  Halpern}{1997}]{CH97}
Chajewska, U. and J.~Y. Halpern [1997]:
\newblock Defining explanation in probabilistic systems.
\newblock In {\em Proc.~Thirteenth Conference on Uncertainty in Artificial
  Intelligence (UAI '97)}, pp.\  62--71.

\bibitem[\protect\citeauthoryear{Eiter and Lukasiewicz}{Eiter and
  Lukasiewicz}{2002}]{EL01}
Eiter, T. and T.~Lukasiewicz [2002]:
\newblock Complexity results for structure-based causality.
\newblock {\em Artificial Intelligence\/}~{\bf 142}:1, pp.\ 53--89.

\bibitem[\protect\citeauthoryear{G{\"{a}}rdenfors}{G{\"{a}}rdenfors}{1988}]{Ga%
rdenfors1}
G{\"{a}}rdenfors, P. [1988]:
\newblock {\em Knowledge in Flux}.
\newblock Cambridge, Mass.: MIT Press.

\bibitem[\protect\citeauthoryear{Goldberger}{Goldberger}{1972}]{Goldberger72}
Goldberger, A.~S. [1972]:
\newblock Structural equation methods in the social sciences.
\newblock {\em Econometrica\/}~{\bf 40}:6, pp.\ 979--1001.

\bibitem[\protect\citeauthoryear{Halpern and Pearl}{Halpern and
  Pearl}{2004}]{HP01b}
Halpern, J.~Y. and J.~Pearl [2004]:
\newblock Causes and explanations: A structural-model approach. {P}art {I}:
  {C}auses.
\newblock {\em British Journal for Philosophy of Science\/}.

\bibitem[\protect\citeauthoryear{Hempel}{Hempel}{1965}]{Hempel65}
Hempel, C.~G. [1965]:
\newblock {\em Aspects of Scientific Explanation}.
\newblock Free Press.

\bibitem[\protect\citeauthoryear{Henrion and Druzdzel}{Henrion and
  Druzdzel}{1990}]{DH90}
Henrion, M. and M.~J. Druzdzel [1990]:
\newblock Qualitative propagation and scenario-based approaches to explanation
  of probabilistic reasoning.
\newblock In {\em Uncertainty in Artificial Intelligence~6}, pp.\  17--32.

\bibitem[\protect\citeauthoryear{Hopkins}{Hopkins}{2001}]{Hopkins01}
Hopkins, M. [2001]:
\newblock A proof of the conjunctive cause conjecture.
\newblock Unpublished manuscript.

\bibitem[\protect\citeauthoryear{Lewis}{Lewis}{1986}]{Lewis86b}
Lewis, D. [1986]:
\newblock Causal explanation.
\newblock In {\em Philosophical Papers}, Volume~{II}, pp.\  214--240. New York:
  Oxford University Press.

\bibitem[\protect\citeauthoryear{Lewis}{Lewis}{1973}]{Lewis73}
Lewis, D.~K. [1973]:
\newblock {\em Counterfactuals}.
\newblock Cambridge, Mass.: Harvard University Press.

\bibitem[\protect\citeauthoryear{Pearl}{Pearl}{1988}]{Pearl}
Pearl, J. [1988]:
\newblock {\em Probabilistic Reasoning in Intelligent Systems}.
\newblock San Francisco: Morgan Kaufmann.

\bibitem[\protect\citeauthoryear{Pearl}{Pearl}{1995}]{Pearl.Biometrika}
Pearl, J. [1995]:
\newblock Causal diagrams for empirical research.
\newblock {\em Biometrika\/}~{\bf 82}:4, pp.\ 669--710.

\bibitem[\protect\citeauthoryear{Pearl}{Pearl}{2000}]{pearl:2k}
Pearl, J. [2000]:
\newblock {\em Causality: Models, Reasoning, and Inference}.
\newblock New York: Cambridge University Press.

\bibitem[\protect\citeauthoryear{Salmon}{Salmon}{1989}]{Salmon89}
Salmon, W.~C. [1989]:
\newblock {\em Four Decades of Scientific Explanation}.
\newblock Minneapolis: University of Minnesota Press.

\bibitem[\protect\citeauthoryear{Scriven}{Scriven}{1959}]{Scriven59}
Scriven, M.~J. [1959]:
\newblock Explanation and prediction in evolutionary theory.
\newblock {\em Science\/}~{\bf 130}, pp.\ 477--482.

\bibitem[\protect\citeauthoryear{Shimony}{Shimony}{1991}]{Shim91a}
Shimony, S.~E. [1991]:
\newblock Explanation, irrelevance and statistical independence.
\newblock In {\em Proceedings, Ninth National Conference on Artificial
  Intelligence (AAAI '91)}, pp.\  482--487.

\bibitem[\protect\citeauthoryear{Sosa and Tooley}{Sosa and
  Tooley}{1993}]{sosa:too93}
Sosa, E. and M.~Tooley (Eds.) [1993]:
\newblock {\em Causation}.
\newblock Oxford readings in Philosophy. Oxford: Oxford University Press.

\bibitem[\protect\citeauthoryear{Woodward}{Woodward}{2001}]{Woodward01}
Woodward, J. [2001]: 
\newblock Explanation.
\newblock In {\em The Blackwell Guide to the Philosophy of Science}.
\newblock To appear.

\end{thebibliography}
