%-*- Mode:TeX; Default-character-style: (:SWISS :ROMAN :NORMAL) -*-

\documentstyle[onecolumn]{aaai}
\newcommand{\mf}[2]{#1}
\newtheorem{proposition}{Proposition}
\special{legal}
\begin{document}

\title{Probabilistic Semantics for Qualitative Influences}
\author{Michael P. Wellman\footnotemark\\
MIT Laboratory for Computer Science\\
545 Technology Square\\
Cambridge, MA  02139}

\maketitle

\begin{abstract}

What's in an influence link?  To answer this foundational question, I propose a
semantics for qualitative influences: $a$ positively influences $b$ if and only
if the posterior distribution for $b$ given $a$ increases with $a$ in the sense
of first-order stochastic dominance.  By requiring that this condition hold in all
contexts, we gain the ability to perform inference across chains of qualitative
influences.  Under sets of basic desiderata, the proposed definition is
necessary as well as sufficient for this desirable computational property.

\end{abstract}

\footnotetext{Supported by National Institutes of Health Grant No.\
R01~LM04493 from the National Library of Medicine.}

\section{Introduction}

Innumerable AI programs incorporate constructs that are intended to capture
the notion that one variable ``causes'' or influences another in some particular
fashion, at precisions ranging from the mere direction of influence to exact
numerical relationships.  Although such terms as ``cause'' and ``influence'' are
often defined rather loosely in knowledge language specifications, any
inference procedure that manipulates models containing these terms imposes
constraints on their possible meaning.

In the sections below, I investigate the constraints imposed on a semantics for
qualitative probabilistic influences by the most basic properties of typical
inference algorithms.  {\it Qualitative} influences are those at the imprecise
end of the spectrum, asserting only a direction of association among
variables.  In looking for a {\it probabilistic} semantics we admit models
where the directions are not guaranteed, and the functional relationships are
not deterministically fixed.

\section{Example: The Digitalis Therapy Advisor}

Our discussion of qualitative influences is set in the context of a simple causal
model taken from Swartout's program for digitalis therapy~\cite{Swartout83}.
The model, shown in Figure~\ref{dig-model}, is a fragment of the knowledge
base that Swartout used to re-implement the Digitalis Therapy
Advisor~\cite{Gorry-Silverman-Pauker78} via an automatic programmer.

\begin{figure}[htbp]
\vspace{4.5cm}
\caption{Part of the causal model for digitalis therapy.  The direction on a link
from $a$ to $b$ indicates the effect of an increase in $a$ on $b$.}
\label{dig-model}
\end{figure}

In the figure the elliptical nodes represent random variables.  The rectangular
node is a decision variable, in this case the dosage of digitalis administered
to the patient.  The hexagonal node is called the value node and represents
the utility of the outcome to the patient.  This terminology and notation are
adapted from {\it influence diagrams}~\cite{Shachter86a}, a probabilistic
modeling formalism similar to Bayes networks~\cite{Pearl86b}. 

Influences among the variables are indicated by dependence links, annotated
with a sign denoting the direction of influence.  Thus digitalis negatively
influences conduction and positively influences automaticity.  The former is
the desired effect of the drug, because a decrease in conduction {\it
decreases} the heart rate, which is considered beneficial for patients with
tachycardia (tach), the population of interest here.  The desirability of lower
heart rates is represented by the negative influence on the value node (given
tach), asserting that lower rates increase expected utility.  The increase in
automaticity is an undesired side-effect of digitalis because this variable is
positively related to the probability of ventricular fibrillation (v.\ fib.), a
life-threatening cardiac state.  Calcium (Ca) and potassium (K) levels also
influence the level of automaticity.

One of the primary advantages of encoding the digitalis model qualitatively is
{\it modularity}, a knowledge representation issue of particular concern in the
case of uncertainty~\cite{Heckerman-Horvitz}.  While the exact probabilistic
relationships among these variables vary from patient to patient, the {\it
direction} of the relations are reliably taken as constant.  Conclusions drawn
from this model are therefore valid for a much broader class of patients.

The conclusions we would like our programs to derive from the digitalis model
are those taken for granted in the description above.  For example, we
unthinkingly assumed that the effects of digitalis on conduction and of
conduction on heart rate would combine to imply that digitalis reduces the
heart rate.  Further, because lower heart rates are desirable, digitalis is {\it
therapeutic} along the upper path.  Similarly, it is {\it toxic} along its lower
path to the value node.  The tradeoff between therapy and toxicity cannot be
resolved by the mere qualitative influences in the model.

The remainder of this paper develops a semantics for qualitative influences
that justifies the kinds of inferences we require while providing the maximum
possible degree of modularity.  A formalism for qualitative influences among
binary events was introduced in a previous paper~\cite{Wellman87d}.  In the
sections below I present the basic definitions, extending them to cover
multi-valued parameters.  The resulting definition is shown to be the weakest
that satisfies our inference desiderata.

\section{Qualitative Influences Defined}

Consider two random variables, $a$ and $b$.  Informally, when $a$ and $b$
are dichotomous events, a qualitative influence is a statement of the form
``$a$ makes $b$ more (or less) likely.''  This binary case is easy to capture in
a probabilistic assertion.  Let $A$ and $\bar{A}$ denote the assertions
$a={\bf true}$ and $a={\bf false}$, respectively, and similarly, $B$ and
$\bar{B}$.  Then we say ``$a$ positively influences $b$,'' written $S^+(a,b)$, if
and only if
\begin{equation}\label{binary}
\forall x\; \Pr(B|Ax) \geq \Pr(B|\bar{A}x).
\end{equation}
In the equation $x$ ranges over all assignments to the other event variables
consistent with both $A$ and $\bar{A}$.  The quantification is necessary to
assert that the influence holds in all contexts, not just marginally.  Because of
this context variable, $S^+$ holds in a particular influence network; programs
that alter the structure of the network may exhibit non-monotonicity in
$S^+$~\cite{Grosof87}.  Conditions analogous to~(\ref{binary}) and those
following serve to define negative and zero influences, omitted here for
brevity.

For the dichotomous case, Bayes's rule implies that~(\ref{binary}) is equivalent
to
\begin{equation}\label{likelihood-binary}
\forall x\; \Pr(A|B x) \geq \Pr(A|\bar{B}x).
\end{equation}
In the terminology of Bayesian revision (\ref{binary}) is a condition on {\it
posteriors}, while~(\ref{likelihood-binary}) is a condition on {\it likelihoods}.
Notice that $S^+(a,b)$ is simply an assertion that the {\it likelihood ratio} is
greater than or equal to unity.

Formalizing $S^+$ is not quite so straightforward when $a$ and $b$ take on
more than two values.  In such cases we want to capture the idea that ``higher
values of $a$ make higher values of $b$ more likely.''  An obvious
prerequisite for such statements is some interpretation of ``higher.''  Therefore,
we require that each random variable be associated with an order
$\geq$ on its values.  For numeric variables such as ``potassium
concentration,'' this relation has the usual interpretation; for variables like
``automaticity'' a measurement scale and ordering relation must be contrived.

The more troublesome part of defining positive influences is in specifying what
it means to ``make higher values of $b$ more likely.''  Intuitively, we want a
statement that the probability distribution for $b$ shifts toward higher values
as $a$ increases.  To make such a statement, we need an ordering that, given
any two cumulative probability density functions (CDFs) $G_1$ and $G_2$ over
$b$, determines whether $G_1$ is ``higher'' than $G_2$.

However, not all probability distributions can be easily ordered according to
the size of the random variable.  Different rankings are obtained through
comparing distributions by median, mean, or mean-log, for example.  We
require an ordering that is robust to changes of these measures because the
random variables need be described by merely {\it ordinal}
scales~\cite{Krantz}.  An assertion that calcium concentration positively
influences automaticity should hold whether calcium is measured on an
absolute or logarithmic scale, and regardless of how automaticity is
measured.

An ordering criterion with the robustness we desire is {\it first-order stochastic
dominance} (FSD)~\cite{Whitmore}.  FSD holds for $G_1$ over $G_2$ if and
only if the mean of $G_1$ is greater than the mean of $G_2$ for {\it any}
monotonic transform of $b$.  That is, for all monotonically increasing functions
$\phi$,
\begin{equation}\label{fsd}
\int \phi(b) dG_1(b) \geq \int \phi(b) dG_2(b).
\end{equation}
A necessary and sufficient condition for~(\ref{fsd}) is
\begin{equation}\label{fsd-condition}
\forall b \; G_1(b) \leq G_2(b).
\end{equation}
That is, for any given value of $b$ the probability of obtaining $b$ or less is
smaller for $G_1$ than for $G_2$.  For further discussion and a proof
that~(\ref{fsd-condition}) is equivalent to~(\ref{fsd}), see~\cite{Fishburn-Vickson}.

We are now ready to define qualitative influences.  Let $F(b|a_i x)$ be the CDF
for $b$ given $a=a_i$ and context $x$.\footnote{As above, $x$ is an
assignment to the remaining random variables consistent with the condition
$a=a_i$.  We need to include $x$ here and in the definitions below because
these conditions will be applied in situations where $x$ is partially or totally
known.  If we had stated the conditions in marginal terms (``on average, $a$
positively influences $b$''), it would not be valid to apply them in specific
contexts.} Then $S^+(a,b)$ if and only if
\begin{equation}\label{i-plus}
\forall a_1,a_2,x \;\;\; a_1 \geq a_2 \Rightarrow F(b|a_1x) \mbox{ FSD } F(b|a_2x).
\end{equation}
Adopting the convention for binary events that ${\bf true} > {\bf false}$,
we can verify that~(\ref{i-plus}) is a generalization of~(\ref{binary}).

Like~(\ref{binary}), (\ref{i-plus}) is a condition on posteriors.
Milgrom~\cite{Milgrom81} proves that the equivalent likelihood condition is
the Monotone Likelihood Ratio Property (MLRP) from statistics~\cite{Berger}.

Finally, we need a special definition for influences on the value node.  The
variable $a$ positively influences utility, $U^+(a)$, if and only if
\begin{equation}\label{utility}
\forall a_1,a_2,x \;\;\; a_1 \geq a_2 \Rightarrow u(a_1,x)\geq u(a_2,x),
\end{equation}
where $u$ is a utility function~\cite{Savage72} defined over the event space.

\section{Chains of Influence}

In an earlier paper on qualitative influences~\cite{Wellman87d}, I considered
networks of variables connected by influence links describing the direction of
probabilistic dependence.  There, I demonstrated for the binary case that, in
the absence of direct links from $a$ to $b$, $S^+(a,b)\wedge
S^+(b,c)\Rightarrow S^+(a,c)$.  From a computational perspective the ability
to perform inference across influence chains is an essential property of a
qualitative algebra.  From the digitalis model, for example, we would like to
deduce that increasing the dose of digitalis decreases the heart rate but
increases the likelihood of v.\ fib.  Indeed, most programs with models like
this would make such an inference.  Fortunately, the definition offered above
for $S^+$ implies transitivity for multi-valued as well as binary variables.

\begin{proposition}\label{chain-prop}
If $a$ and $c$ are not connected by any direct links, $S^+(a,b)$, and
$S^+(b,c)$, then $S^+(a,c)$ holds in the network obtained by removing $b$.
\end{proposition}
{\it Proof:} Choose $a_1$ and $a_2$ such that $a_1\geq a_2$, and an $x_0$
consistent with $a_1$, $a_2$, and all $b$.  Let $G$ denote the conditional CDF
for $c$ and $\underline{c}$ the minimal value of the variable.  By the
definition of cumulative probability we have
\begin{equation}
G(c_0|a_i x_0) = \int_{\underline{c}}^{c_0}\int f_{b c}(b c|a_i x_0) db dc.
\end{equation}
Changing the order of integration and decomposing the joint probability yields
\begin{equation}
G(c_0|a_i x_0) = \int\int_{\underline{c}}^{c_0} f_c(c|a_i b x_0) f_b(b|a_i x_0) dc
db.
\end{equation}
Because $a$ and $c$ are conditionally independent given $b$ and $x$, we can
remove $a_i$ from the $f_c$ expression.\footnote{The conditional
independence follows from separation in the influence network.  See
Pearl~\cite{Pearl86c} for a discussion of the independence properties of
graphical probability representations.}  Rewriting the density function as the
derivative of a cumulative, we get
\begin{equation}
G(c_0|a_i x_0) = \int\int_{\underline{c}}^{c_0} f_c(c|b x_0) dc dF(b|a_i x_0).
\end{equation}
The inner integral is simply the CDF for $c$ given $b$.
\begin{equation}\label{c|a-result}
G(c_0|a_i x_0) = \int G(c_0|b x_0) dF(b|a_i x_0).
\end{equation}
Because $b$ positively influences $c$, the pointwise FSD
condition~(\ref{fsd-condition}) implies that for any $c_0$, $G(c_0|b x_0)$ is a
{\it decreasing} function of $b$.  And $S^+(a,b)$ entails FSD of $F(b|a_1 x_0)$
over $F(b|a_2 x_0)$.  Therefore, (\ref{fsd}) applies with the inequality
reversed (negating $G(c_0|b x_0)$ yields an increasing function), leading to the
conclusion
\begin{equation}
\forall c_0\;\;\; G(c_0|a_1 x_0) \leq G(c_0|a_2 x_0),
\end{equation}
implying FSD.  Because $a_1$, $a_2$, and $x_0$ were chosen arbitrarily, we
have finally $S^+(a,c)$.  \rule{1ex}{9pt}

Similar arguments with the appropriate signs and directions switched would
reveal that chains of influences may be combined by sign multiplication.

In the remainder of this section I present some simple desiderata for a
qualitative influence definition that entail the {\it necessity} of FSD for
chaining influences.  We start by specifying the form such definitions must
take.  To capture the intent of ``higher values of $a$ make higher values of
$b$ more likely'' in a probabilistic semantics, it seems reasonable to restrict
our attention to conditions on the posterior distribution of $b$ for increasing
values of $a$.  Therefore, we postulate that a definition of $S^+(a,b)$ must be
of the form
\begin{equation}\label{R-posterior}
\forall a_1,a_2,x \;\;\; a_1 \geq a_2 \Rightarrow F(b|a_1x) \; R \; F(b|a_2x),
\end{equation}
where $R$ is some relation on CDFs.  This condition is
exactly~(\ref{i-plus}) with FSD replaced by the more abstract relation.

There are two basic desiderata that severely restrict the possible $R$s.  First,
the definition for $S^+$ induced by $R$ in~(\ref{R-posterior}) must satisfy
Proposition~\ref{chain-prop}.  Without the ability to chain inferences, the
qualitative influence formalism has little computational value.  Second, the
condition must be a generalization of the original definition of $S^+$ for
dichotomous events~(\ref{binary}).  With only two possible values there does
not appear to be a weaker monotonicity condition.  These criteria lead to a
sharp conclusion.

\begin{proposition}\label{necessity}
Let $S^+(a,b)$ be defined by~(\ref{R-posterior}).  Given the following conditions:
\begin{enumerate}
\item Proposition~\ref{chain-prop}
\item For binary $b$, $a_1\geq a_2$, and $x$,
\begin{equation}\label{binary-condition}
F(b|a_1x) \; R \; F(b|a_2x) \Leftrightarrow \Pr(B|a_1 x)\geq \Pr(B|a_2 x)
\end{equation}
\end{enumerate}
the weakest $R$ is FSD.
\end{proposition}
{\it Proof:} First, note that FSD satisfies these conditions.  Next, assume that
$R$ satisfies them but $R$ does not entail FSD.  We will start with an
instantiation of Proposition~\ref{chain-prop} and derive a contradiction.  Let
$a$, $b$, and $c$ be the only variables (so we can safely ignore $x$) with
$S^+(a,b)$, $S^+(b,c)$, and no other direct links.  For concreteness, let $b$
range over the unit interval $\left[0,1\right]$ and $c$ be binary with
$\Pr(C|b)=\phi(b)$, for some $\phi:\left[0,1\right]\rightarrow\left[0,1\right]$
monotonic.  The monotonicity of $\phi$ guarantees $S^+(b,c)$.  By assumption,
Proposition~\ref{chain-prop} applies, yielding the conclusion $S^+(a,c)$ and
therefore $F(c|a_1) \; R \; F(c|a_2)$.  Because $c$ is binary,
(\ref{binary-condition})~must hold.  Expanding the expression for the posterior
probability of $c$ given $a$, the RHS of~(\ref{binary-condition}) becomes
\begin{equation}\label{phi}
\int_0^1 \phi(b) dF(b|a_1) \geq \int_0^1 \phi(b) dF(b|a_2).
\end{equation}
Because $\phi$ may be any monotonic function, FSD is necessary
for~(\ref{phi}) and is therefore entailed by $R$.  \rule{1ex}{9pt}

The force of this result is weakened somewhat by the {\it a priori} restriction
of definitions to those having the form of~(\ref{R-posterior}).  Many statistical
concepts of directional relation (based on correlation or joint expectations, for
example) do not fit~(\ref{R-posterior}) yet appear to be plausible candidates
for a definition of qualitative influence.  {\it Quadrant
dependence}~\cite{Lehmann66} holds between $a$ and $b$ when\footnote{This
is actually the condition Lehmann proposes as a strengthening of quadrant
dependence.  The basic quadrant dependence fixes $a_1$ at $a$'s maximal
value.}
\begin{equation}\label{quadrant}
\forall a_1,a_2\;\;\; a_1 \geq a_2 \Rightarrow F(b|a\leq a_1) \mbox{ FSD }
F(b|a\leq a_2).
\end{equation}
Lehmann proves that quadrant dependence is necessary but not sufficient for
{\it regression dependence}, which is his terminology for~(\ref{i-plus})
without the quantification over contexts $x$.  As quadrant dependence is
weaker yet still exhibits transitivity,\footnote{For transitivity we need to
quantify over contexts in~(\ref{quadrant}).  The proof parallels that for
Proposition~\ref{chain-prop}.} it seems to be an attractive alternate to
regression dependence.  To justify our choice of the latter, we must appeal to
the decision-making implications of probabilistic models.

\section{Making Decisions}

The prime motivation for adopting a probabilistic semantics is so that the
behavior of our programs can be justified by Bayesian decision
theory~\cite{Savage72}.  A decision is valid with respect to an influence model
if expected utility is maximized.
For example, if $U^+(a)$ and there are no {\it indirect} paths from $a$ to the
value node, then a decision of $a_1$ over $a_2$ is valid if and only if
$a_1\geq a_2$, by the definition of $U^+$~(\ref{utility}).\footnote{The
existence of other paths from $a$ to utility would leave open the possibility
that the net influence of $a$ is negative.  For example, we could summarize
the therapeutic effect of digitalis through conduction and heart rate as a direct
positive influence.  But this might be outweighed by the indirect negative
influence of digitalis via automaticity.} Decision-making power is enhanced if
we can deduce new influences on utility from chains of influences in the
network.  Our definition of qualitative influence is necessary as well as
sufficient for such inferences.

\begin{proposition}\label{utility-chain}
Consider a network where $U^+(b)$ holds and $a$ and $u$ are not connected
by any direct links.  A necessary and sufficient condition for $U^+(a)$ on
removal of $b$ is $S^+(a,b)$ as defined by~(\ref{i-plus}).
\end{proposition}
{\it Proof:} The expected utility of $a_i$ with any $x$ is given by
\begin{equation}\label{utility-a}
u(a_i,x)=\int u(b,x) dF(b|a_i x).
\end{equation}
$U^+(a)$ is satisfied in the reduced network if and only if $u(a_i,x)$ is
increasing in $a_i$.  From~(\ref{utility}) we know that $u(b,x)$ is
monotonically increasing in $b$.  In fact, it can be {\it any} monotonic
function.  Therefore, (\ref{utility-a}) is increasing in $a_i$ under the same
conditions as~(\ref{fsd}), which is exactly $S^+$ as defined by~(\ref{i-plus}).
\rule{1ex}{9pt}

Proposition~\ref{utility-chain} demonstrates that while conditions like quadrant
dependence which are weaker than $S^+$ may be sufficient for propagating
influences across chains, they are not adequate to justify {\it decisions}
across chains.  For choosing among alternatives, the relevant parameter is the
utility function evaluated at a point; utilities conditioned on intervals of the
decision variable (as in quadrant dependence) do not have the same
decision-making import.

\section{Extensions}

The basic definitions above can be extended in a variety of ways.  Conditional
influences---defined for binary events in a previous
paper~\cite{Wellman87d}---simply delimit the range of $x$ in~(\ref{i-plus}).
For example, the negative influence of heart rate on utility in the digitalis
model is conditional on tachycardia.

Swartout's {\sc xplain} knowledge base included the ``domain principle'' that if
a state variable acts synergistically with the drug to induce toxicity, then
smaller doses should be given for higher observations of the
variable~\cite{Swartout83}.  This fact could be derived by a {\it
domain-independent} inference procedure given a suitable definition for
qualitative synergy.  We can say that two variables synergistically influence a
third if their joint influence is greater (in the sense of FSD) than separate
statistically independent influences.\footnote{This type of relationship was
exploited by NESTOR~\cite{Cooper}, a diagnostic program based on
probabilistic inequalities.} In the digitalis example, we need to assert that
digitalis acts at least independently with Ca and K deviations in increasing
automaticity.  In addition, we must specify that the decrease in utility for a
given increase in automaticity is larger when automaticity is already high.
Such a relationship can be captured by an assertion that automaticity is
synergistic with itself in its toxic effects.

\section{Related Work}

Philosophers have long attempted to develop mathematical definitions of
causality.  Motivated by computational rather than philosophical concerns, I
have ignored in this treatment temporal properties, mechanisms, spuriousness,
and other issues salient to causality.  These concerns aside,
Suppes~\cite{Supp} proposes a probabilistic condition equivalent
to~(\ref{binary}) without the context quantification for binary events.  For
multi-valued variables, Suppes suggests quadrant
dependence~(\ref{quadrant}).

As suggested previously, ordering of random variables has also attracted
considerable interest in statistics~\cite{Berger,Lehmann66,Ross83} and
decision theory~\cite{Whitmore}.  Milgrom~\cite{Milgrom81} demonstrates the
application of MLRP to theoretical problems in informational economics.

The key difference between the $S^+$ definition proposed here and previous
work is that we obtain transitivity by requiring the condition to hold in all
contexts.  Suppes shows that the causal algebra induced by his
condition---defined only at the margin---does not possess the transitive
property.  As argued above, this is a computationally essential characteristic
of qualitative influences.

\section{Conclusions}

Despite the ubiquity of qualitative influence assertions in knowledge
representation mechanisms, there has been little study of the semantics of
such constructs.  Previous work either denies the probabilistic nature of the
relationships among variables in the model or takes for granted the ability to
draw inferences by chaining influences in the network.  I have defined a
positive qualitative influence of $a$ on $b$ as an assertion that, in all
contexts, the posterior probability distribution for $b$ given $a$ is
stochastically increasing (FSD) in $a$.  A series of propositions provided
theoretical support for this $S^+$ definition:
\begin{itemize}
\item $S^+$ supports chaining of influences.
\item $S^+$ is the weakest posterior condition that supports chaining of
influences.
\item $S^+$ is necessary and sufficient for chaining {\it decisions} across
influences.
\end{itemize}

A semantics for qualitative influences should prove valuable for analyzing
knowledge bases like the digitalis model of Figure~\ref{dig-model}, as well
as knowledge representation theories that include similar constructs.  In
particular, the definition of $S^+$ can help to evaluate the potential of purely
qualitative methods like Cohen's endorsement approach~\cite{Cohen85} and to
characterize the techniques from AI work on qualitative reasoning that are
valid in probabilistic domains.

\section*{Acknowledgments}

Zak Kohane, Bill Long, Ramesh Patil, Elisha Sacks, Kate Unrath, and Alex Yeh
positively influenced this paper.  

\bibliographystyle{aaai}
\bibliography{/u/publish/bib/bib}

\end{document}
