%\documentstyle[theapa,jair,twoside,url,11pt]{article}
%6/26: 11:52

\documentstyle[theapa,jair,twoside,url,11pt]{article}


\input{defn}
\input{bghkmac}
\renewcommand{\IN}{I\!\!N}
\newcommand{\PlP}{\Pl_{\P}}
\newcommand{\sPlP}{\sPl_{\P}}
\newcommand{\DP}{D_{I}}
\newcommand{\Bel}{{\rm Bel}}
\newcommand{\Poss}{{\rm Poss}}
\newcommand{\Plaus}{{\rm Plaus}}
\newcommand{\Range}{\mbox{\it Range}}
\newcommand{\Pl}{\mbox{Pl}}
\newcommand{\IPl}{I_{\sPl}}
\newcommand{\IrvPl}{I_{\rm Pl}^{\it rv}}
\newcommand{\Par}{{\rm Par}}
\newcommand{\des}{{\rm Des}}
\newcommand{\nondes}{{\rm ND}}
%\newcommand{\Irv}{I^{\it rv}}
\newcommand{\sPl}{{\mbox{\rm\scriptsize Pl}}}
\newcommand{\PL}{{\cal PL}}
\newcommand{\NIPl}{\mbox{\it NI\/}_{\sPl}}
\newcommand{\Dom}{\mbox{\it Dom}}
\newcommand{\dsep}{\mbox{\it d-sep\/}}
\renewcommand{\IN}{I\!\!N}
%\setlength\textheight{9.4in}

\jairheading{14}{2001}{359--389}{10/00}{6/01}
\ShortHeadings{Conditional Plausibility Measures and Bayesian Networks}{Halpern}
\firstpageno{359}

\begin{document}

%joe:UAI
%\begin{titlepage}

\title{Conditional Plausibility Measures and Bayesian Networks}
\author{\name Joseph Y.\ Halpern \email halpern@cs.cornell.edu\\
\addr   Cornell University, Computer Science Department\\
   Ithaca, NY 14853\\
   http://www.cs.cornell.edu/home/halpern
}
\maketitle
%joe:UAI


\begin{abstract}
A general notion of algebraic conditional plausibility measures is
defined.  Probability
measures, ranking functions, possibility measures, and (under the
appropriate definitions) sets of probability measures can all be viewed
as defining algebraic conditional plausibility measures.
%It is shown that the technology of Bayesian networks can be
%applied to algebraic conditional plausibility measures.
It is shown that algebraic conditional plausibility measures
can be represented using Bayesian networks.
\end{abstract}

%\end{titlepage}


\section{Introduction}
Pearl \citeyear{Pearl} among others has long argued that Bayesian
networks (that is, the dags without the conditional probability tables)
represent important {\em qualitative\/} information about uncertainty
regarding conditional dependencies and independencies.  To the extent
that this is true, Bayesian networks should make perfect sense for
non-probabilistic representations of uncertainty.  And, indeed, Bayesian
networks have been used with $\kappa$ rankings \cite{spohn:88} by
Darwiche
and Goldszmidt \citeyear{DarwicheGoldszmidt94}.  It follows from results
of Wilson~\citeyear{Wilson94} that 
{\em possibility measures\/} \cite{DuboisPrade88} can be represented
using Bayesian networks.

The question I address in this paper is ``What properties of a
representation of uncertainty are required 
%joe2
%in order for the technology of Bayesian networks to work?''  
to be able to represent the uncertainty using a Bayesian network?''  
This question too has been addressed in
earlier work, see \cite{DarwicheThesis,DarwicheGinsberg1,FrH7,Wilson94},
although the characterization given here is somewhat different.
Shenoy and Shafer \citeyear{SS90} consider a related question---%
essentially, what is required of a representation of uncertainty so
that marginals can be computed using ``local computations''
of the type used in Bayesian networks---and provide axioms
sufficient to guarantee that this is possible.

Here I
represent uncertainty using {\em plausibility measures}, as in
\cite{FrH7}.  To answer the question, I must examine general properties
of conditional plausibility as well as defining a notion of
plausibilistic independence.
Unlike earlier papers, I enforce a symmetry condition in the definition
of conditional independence, so that, for example, $A$ is
independent of $B$ iff $B$ is independent of $A$.  While this property
holds for 
probability, under the asymmetric definition of independence used in
earlier work it does not necessarily hold for other
formalisms.  There are also subtle but important differences between
this paper and \cite{FrH7} in the notion of conditional plausibility.
The definitions here are simpler but more general; particular attention
is paid here to conditions on when the conditional plausibility must be
defined.

The major results here are a general condition, simpler than that given
in \cite{FrH7,Wilson94}, under which a conditional plausibility measure
satisfies the semi-graphoid properties (which means it can be
represented using a Bayesian network).   
Conditions are also
given that suffice for a Bayesian network to be able to quantitatively
represent a plausibility measure; more precisely, conditions are given
so that a plausibility measure can be uniquely reconstructed given
conditional plausibility tables for each node in the Bayesian network.
Conditions for quantitative representation by Bayesian networks do not
seem to have been 
presented in the literature for representations of uncertainty other
than probability (for which the conditions are trivial).   A minor
additional condition also suffices to guarantee  that {\em d-separation\/}
in the network characterizes conditional independence.  
All these conditions clearly apply to
$\kappa$ rankings and possibility measures.
Perhaps more interestingly, they also apply to sets
of probabilities under a novel representation of such sets as a
plausibility measure.  This novel representation (and the associated
notion of conditioning) is shown to have some natural properties not
shared by other representations.

The rest of the paper is organized as follows.  In
Section~\ref{sec:cpm}, I discuss conditional plausibility measures.
Section~\ref{sec:alg} introduces {\em algebraic\/} conditional
plausibility measures, which are ones where there is essentially an
analogue to $+$ and $\times$.  (Putting such an algebraic structure on
uncertainty is not new; it was also done in
\cite{DarwicheThesis,DarwicheGinsberg1,FrH7,Weydert94}.)
Section~\ref{sec:ind} discusses independence and conditional
independence in conditional plausibility spaces, and shows that algebraic
conditional plausibility measures satisfy the semi-graphoid properties.
Finally, in Section~\ref{sec:bn}, Bayesian networks based on (algebraic)
plausibility measures are considered.  Combining the fact that algebraic
plausibility measures satisfy the semi-graphoid properties with the results of
\cite{GVP90}, it follows that
d-separation in a Bayesian network $G$ implies conditional
independence for all algebraic plausibility measures compatible with
$G$; a weak
richness condition is shown to yield the converse.  
The paper concludes
in Section~\ref{sec:conc}.  Longer proofs are relegated to the appendix.


\section{Conditional Plausibility}
\label{sec:cpm}

\subsection{Unconditional Plausibility Measures}

Before getting to conditional plausibility measures, it is perhaps best
to consider unconditional plausibility measures.
The basic idea behind plausibility measures is straightforward.
A probability measure maps subsets of a set $W$ to $[0,1]$.  Its domain
may not consist of all subsets of $W$; however, it is required to be an
{\em algebra}.  (Recall that
an algebra $\F$ over $W$ is a set of subsets of $W$ containing $W$ and
closed under union and complementation, so that if
$U, V \in \F$, then so are $U \union V$ and $\overline{U}$.) A {\em
plausibility measure\/} is more general; it maps elements in an algebra
$\F$
to some arbitrary partially ordered set.  If $\Pl$ is a plausibility
measure, then we read $\Pl(U)$ as ``the
    plausibility of set $U$''.  If $\Pl(U) \le \Pl(V)$, then $V$ is at
    least as plausible as $U$.  Because the ordering is partial, it
could be that the plausibility of two different sets is incomparable.
An agent may not be prepared to say of two sets that one is more likely
than another or that they are equal in likelihood.

    Formally, a {\em plausibility space\/}
    is a tuple $S = (W,\F,\Pl)$, where $W$ is a set of worlds, $\F$
    is an algebra over $W$,
    and $\Pl$ maps sets in $\F$ to some set  $D$ of {\em
    plausibility values\/} partially ordered by a relation $\le_D$ (so
    that $\le_D$ is reflexive, transitive, and anti-symmetric)
that contains
two special elements $\top_D$ and $\bot_D$ such that
$\bot_D \le_D d     \le_D \top_D$ for all $d \in D$;
%$\bot_D \le \top_D$;
these are intended to be the analogues of 1 and 0 for probability.
%\footnote{In earlier papers on plausibility (\eg \cite{FrH7}) and the
%conference version of this paper, it was
%assumed that $\bot_D \le d \le \top_D$ for all $d \in D$.  This
%assumption is not required and, for technical reasons, as we shall see,
%it is sometimes useful to have elements larger than $\top_D$ in $D$.}
%In the case of probability
%measures, $\top_D$ and $\bot_D$ are 1 and 0, respectively.
As usual, the ordering is defined $<_D$ by taking $d_1 <_D d_2$ if $d_1
    \le_D d_2$ and $d_1 \neq d_2$.
I omit the subscript $D$ from $\le_D$, $<_D$, $\top_D$ and $\bot_D$
whenever it is clear from context.

There are three requirements on plausibility measures.  The first two
are obvious analogues of requirements that hold for other
notions of uncertainty: the whole space gets the maximum
plausibility and the empty set gets the minimum plausibility.  The third
requirement says that a set must be
    at least as plausible as any of its subsets.
\begin{description}
\item[{\rm Pl1.}] $\Pl(\emptyset) = \bot_D$.
\item[{\rm Pl2.}] $\Pl(W) = \top_D$.
\item[{\rm Pl3.}] If $U \subseteq U'$, then $\Pl(U) \le \Pl(U')$.
\end{description}
(In Pl3, I am implicitly assuming that $U, U' \in \F$.  Similar
assumptions are made throughout.)

All the standard representations of uncertainty in the literature
can be represented as plausibility measures.
I briefly describe some other representations of uncertainty that will
be of relevance to this paper.
%\begin{itemize}
\commentout{
\item A {\em belief function\/} $\Bel$ on $W$ is a function
    $\Bel: 2^{W} \rightarrow [0,1]$ satisfying certain axioms
    \cite{Shaf}.  Corresponding to each belief function $\Bel$ there is
a plausibility function $\Plaus$ defined via $\Plaus(U) = 1 -
\Bel(\overline{U})$.%
{The word ``plausibility'' is slightly overloaded,
appearing both in the context of ``plausibility function'' and
``plausibility measure''.  Plausibility functions will only play a minor
role in this paper, so there should not be much risk of confusion.}
It follows from the axioms for belief functions that $\Bel(U) \le
\Plaus(U)$ for all $U \subseteq W$.  The axioms for belief functions
imply properties Pl1--3 hold for belief and for plausibility.  It thus
follows that
belief functions and plausibility functions are plausibility measures.
But there is another way of associating a plausibility measure
$\Pl_{{\Bel}}$ with a belief function $\Bel$: Let $D_{{\Bel}} = \{(a,b):
0 \le a \le b \le 1\}$ and define $(a,b) \le (a',b')$ iff $b \le a'$.
This puts a partial order on $D_{{\Bel}}$;  clearly $\bot_{D_{{\Bel}}} =
(0,0)$ and $\top_{D_{{\Bel}}} = (1,1)$.  Define $\Pl_{{\Bel}}(U) =
(\Bel(U),\Plaus(U))$.  Thus, $\Pl_{{\Bel}}$ associates with a set $U$
two numbers which can be thought of as defining an interval in terms of
the belief and plausibility of $U$.  It is easy to  check that
$\Pl_{{\Bel}}$ satisfies Pl1--3, so it is indeed a plausibility
measure.
}%\end{commentout}
\paragraph{Sets of probabilities:} One common way of representing uncertainty is by a set of
probability measures.  This set is often assumed to be convex (see, for
example, \cite{CM95,CMW99,GilboaSchmeid93,Levi85,Walley91} for
discussion and further references),
however, convex sets do not seem
appropriate for representing independence assumptions, so I do not make
this restriction here.
For example, if a coin with an unknown probability of heads is tossed
twice, and the tosses are known to be independent, it seems that a
reasonable representation is given by the set $\P_0$ consisting of
all measures $\mu_\alpha$, where
$\mu_\alpha(hh) = \alpha^2,\  \mu_\alpha(ht) = \mu_\alpha(th) =
\alpha(1-\alpha), \mu_\alpha(tt) = (1-\alpha)^2$.
Unfortunately, $\P_0$ is not convex.  Moreover, its convex
hull includes many measures for which the coin tosses are not
independent.  It is argued in \cite{CMW99} that a set of probability
measures is behaviorally equivalent to its convex hull.  However, even
if we accept this argument, it does not follow that a set and its convex
hull are equivalent insofar as determination of independencies goes.

There are a number of ways of viewing a set $\P$
of probability measures as a plausibility measure.  One uses the
{\em lower probability\/} $\P_*$, defined as
$\P_*(U) = \inf\{\mu(U): \mu \in \P\}$.  Clearly $\P_*$ satisfies
Pl1--3.  The corresponding {\em upper
probability\/} $P^*$, defined as $\P^*(U) = \sup\{\mu: \mu \in \P\} = 1 -
\P_*(\overline{U})$, is also clearly a plausibility measure.

Both $\P_*$ and $\P^*$ give a way of comparing the likelihood of
two subsets $U$ and $V$ of $W$.  These two ways are incomparable; it is
easy to find a set $\P$ of probability measures on $W$ and subsets
$U$ and $V$ of $W$ such that $\P_*(U) < \P_*(V)$ and $\P^*(U)
> \P^*(V)$.  Rather than choosing between
$\P_*$ and $\P^*$, we can associate a different plausibility measure
with $\P$ that captures both.   Let $D_{\P_*,\P^*} = \{(a,b):
0 \le a \le b \le 1\}$ and define $(a,b) \le (a',b')$ iff $b \le a'$.
This puts a partial order on $D_{\P_*,\P^*}$; clearly $\bot_{D_{\P_*,\P^*}}
=
(0,0)$ and $\top_{D_{\P_*,\P^*}} = (1,1)$.  Define $\Pl_{\P_*,\P^*}(U) =
(\P_*(U),\P^*(U))$.  Thus, $\Pl_{\P_*,\P^*}$ associates with a set $U$
two numbers that can be thought of as defining an interval in terms of
the lower and upper probability of $U$.  It is easy to check that
$\Pl_{\P_*,\P^*}(U) \le \Pl_{\P_*,\P^*}(V)$ if the upper probability of
$U$ is less than or equal to the lower probability of $V$.
$\Pl_{\P_*,\P^*}$ satisfies Pl1--3, so it is indeed a plausibility
measure, but one which puts only a partial order on events.

The trouble with $\P_*$, $\P^*$, and even
$\Pl_{\P_*,\P^*}$ is that they lose information.  For example, it is
not hard to find a set $\P$ of probability measures and subsets $U, V$
of $W$ such that $\mu(U) \le \mu(V)$ for all $\mu \in \P$ and $\mu(U) <
\mu(V)$ for some $\mu \in \P$, but $\P_*(U) = \P_*(V)$ and $\P^*(U) =
\P^*(V)$.  Indeed, there exists an infinite set $\P$ of probability
measures such that $\mu(U) < \mu(V)$ for all $\mu \in \P$ but $\P_*(U) =
\P_*(V)$ and $\P^*(U) = \P^*(V)$.  If all the probability
measures in $\P$ agree that $U$ is less likely than $V$, it seems
reasonable to conclude that $U$ is less likely than $V$.  However,
none of $\P_*$, $\P^*$, or $\Pl_{\P_*,\P^*}$
will necessarily draw this conclusion.

Fortunately, it is not hard to
associate yet another plausibility measure with $\P$ that does not lose
this important information.  For technical convenience that will become
clear later, assume
that there is some index set $I$ such that $\P = \{\mu_i: i \in I\}$.
Thus, for example, if $\P = \{\mu_1, \ldots, \mu_n\}$, then $I = \{1,
\ldots, n\}$.  Let $\DP =
[0,1]^{I}$, that is, the functions from $I$ to $[0,1]$, with the pointwise ordering,
so that $f \le g$ iff $f(i) \le g(i)$ for all $i \in I$.%
\footnote{In the conference version of this paper \cite{Hal25}, $\DP$, the range of
the plausibility measure, was taken to be functions from $\P$ to $[0,1]$,
not from the index set $I$ to $[0,1]$.  The difference is mainly cosmetic,
but this representation makes the range
independent of $\P$, so that the same plausibility values can be used
for any set of probability measures indexed by $I$.}
It is easy to check that $\bot_{\DP}$ is the function $f: I \rightarrow
[0,1]$ such
that $f(i) = 0$ for all $i \in I$
and  $\top_{\DP}$ is the function $g$ such that $g(i) = 1$ for
all $i \in I$.
For $U \subseteq W$, let $f_{U}$ be the function such that $f_{U}(i) =
\mu_i(U)$ for all $i \in I$.  For example, for the set $\P_0$ of
measures representing the two coin tosses (which is indexed by $\IR$),
the set $W$ can be taken to be $\{hh, ht, tt, th\}$.  Then, for example,
$f_{\{hh\}}(\alpha)
= \mu_\alpha(hh) = \alpha^2$ and $f_{\{ht,tt\}}(\alpha) = 1-\alpha$.

It is easy to see that $f_{\emptyset} =
\bot_{\DP}$ and $f_W = \top_{\DP}$.
Now define $\PlP(U) = f_U$.  Thus, $\PlP(U) \le \PlP(V)$ iff $f_U(i)
\le f_V(i)$ for all $i \in I$ iff
$\mu(U) \le \mu(V)$ for all $\mu \in \P$.
Clearly $\PlP$ satisfies Pl1--3.  Pl1 and Pl2 follow since
$\PlP(\emptyset) = f_\emptyset = \bot_{\DP}$ and
$\PlP(W) = f_W = \top_{\DP}$, while  Pl3 follows since if $U \subseteq
V$ then $\mu(U) \le \mu(V)$ for all $\mu \in \P$.
$\PlP$ captures all the information in $\P$ (unlike, say, $\P_*$, which
washes much of it away by taking infs).

This way of associating a plausibility measure
with a set $\P$ of probability measures generalizes: it provides a way
of associating a single plausibility measure with any set of
plausibility measures; I leave the straightforward details to the
reader.

\paragraph{Possibility measures:} 
A {\em fuzzy measure\/} (or a {\em Sugeno measure\/}) $f$ on
    $W$ \cite{WangKlir} is a function $f:2^W \mapsto
    [0,1]$, that satisfies Pl1--3.  (That is, it is less general than a
    plausibility measure only in that it requires the range to be
    $[0,1]$ rather than an arbitrary partially ordered set.)
A {\em possibility measure\/} $\Poss$ on $W$ is a special case of a Sugeno
    measure; it is a function mapping
subsets of $W$ to $[0,1]$ such that $\Poss(W) = 1$, $\Poss(\emptyset) =
0$, and
$\Poss(U) = \sup_{w \in U}(\Poss(\{w\}))$, so that $\Poss(U \union V) =
\max(\Poss(U),\Poss(V))$ \cite{DuboisPrade88}.  Clearly a possibility
measure is a plausibility measure.


\paragraph{Ranking functions:} An {\em ordinal ranking\/} (or {\em $\kappa$-ranking\/} or {\em
ranking function\/}) $\kappa$ on
    $W$ (as defined by \cite{Goldszmidt92}, based on ideas that
    go back to \cite{spohn:88}) is a function
mapping subsets of $W$ to $\IN^* = \IN \union \{\infty\}$
    such
    that $\kappa(W) = 0$, $\kappa(\emptyset) = \infty$, and
    $\kappa(U) = \min_{w\in U}(\kappa(\{w\}))$, so that $\kappa(U \union
V) = \min(\kappa(U),\kappa(V))$.
    Intuitively, a
    ranking function assigns a degree of surprise to each subset of
    worlds in $W$, where $0$ means unsurprising and higher
    numbers denote greater surprise. It is easy to see that if
    $\kappa$ is a ranking function on $W$, then $(W, 2^W, \kappa)$
    is a plausibility space, where $x \le_{\IN^*} y$ if and only if $y
    \le x$ under the usual ordering on the natural numbers.
One standard view of a ranking function, going back to Spohn, is that a
ranking of $k$ can be associated with a probability of $\epsilon^k$, for
some fixed (possibly infinitesimal) $\epsilon$.  Note that this
viewpoint justifies taking $\kappa(W) = 0$, $\kappa(\emptyset) =
\infty$, and $\kappa(U \union V) = \min(\kappa(U),\kappa(V))$.


\subsection{Conditional Plausibility Measures}
Since Bayesian networks make such heavy use of conditioning,
my interest here is not just plausibility measures, but {\em
conditional\/} plausibility measures ({\em cpm}'s).
Given a set $W$ of worlds, a cpm
maps pairs of subsets of $W$ to some partially ordered set $D$.
I write $\Pl(U|V)$ rather than $\Pl(U,V)$, in keeping with standard
notation for conditioning.  In the case of a probability measure $\mu$,
it is standard to take $\mu(U|V)$ to be undefined in $\mu(V) = 0$.
In general, we must make precise what the allowable second arguments are.
Thus, I take the domain of a cpm to have the form $\F \times \F'$ where,
intuitively, $\F'$ consists of those sets in $\F$ on which it makes
sense to condition.
For example, for a conditional probability measure defined in the usual
way from an unconditional probability measure $\mu$, 
$\F'$ consists of all sets $V$ such that $\mu(V)
> 0$.  (Note that $\F'$ is not an algebra---it is not
closed under complementation.)
A {\em Popper algebra\/} over $W$ is a set $\F \times \F'$ of subsets of $W
\times W$ satisfying the following properties:
\begin{description}
\item[{\rm Acc1.}] $\F$ is an algebra over $W$.
\item[{\rm Acc2.}] $\F'$ is a  nonempty subset of $\F$.
\item[{\rm Acc3.}] $\F'$ is closed under supersets in $\F$; that is, if
$V \in \F'$, $V \subseteq V'$, and $V' \in \F$, then $V' \in \F'$.
\end{description}
(Popper algebras are named after Karl Popper, who was the first to
consider formally conditional probability as the basic notion \cite{Popper68}.
De Finetti \citeyear{Finetti36} also did some early work, apparently
independently, taking conditional probabilities as primitive.  Indeed,
as R\'{e}nyi \citeyear{Renyi64} points out, the idea seems to go back as far
as Keynes \citeyear{Keynes}.)

A {\em conditional plausibility
space\/} ({\em cps\/}) is a tuple $(W,\F,\F',\Pl)$, where $\F
\times \F'$ is a Popper algebra over $W$,
$\Pl: \F \times \F' \rightarrow D$, $D$ is a partially ordered
set of plausibility values, and $\Pl$ is a
{\em conditional plausibility measure\/}
(cpm) that satisfies the following conditions:
\begin{description}
\item[{\rm CPl1.}] $\Pl(\emptyset|V) = \bot_D$.
\item[{\rm CPl2.}] $\Pl(W|V) = \top_D$.
\item[{\rm CPl3.}] If $U \subseteq U'$, then $\Pl(U|V) \le \Pl(U'|V)$.
\item[{\rm CPl4}] $\Pl(U|V) = \Pl(U \inter V|V)$.
\end{description}
CPl1--3 are the obvious analogues to Pl1--3.  CPl4 is a minimal property
that guarantees that when conditioning on $V$, everything is relativized
to $V$.  It follows easily from CPl1--4 that
$\Pl(\cdot|V)$ is a plausibility measure on $V$ for each fixed $V$.
A cps is {\em acceptable\/} if it satisfies
\begin{description}
\item[{\rm Acc4.}] If $V \in \F'$, $U \in \F$, and $\Pl(U|V) \ne \bot_D$, then
$U \inter V \in \F'$.
\end{description}
Acceptability is a generalization of the observation
that if $\Pr(V) \ne 0$, then conditioning on $V$ should be
defined.  It says that if $\Pl(U|V) \ne \bot_D$, then conditioning on $V
\inter U$ should be defined.


CPl1--4 are rather minimal requirements.  For example, they do not place
any constraints on the relationship between $\Pl(U|V)$ and
$\Pl(U|V')$ if $V \ne V'$.  One natural additional condition 
is the following.
\begin{description}
\item[{\rm CPl5.}] If $V \inter V' \in \F'$ and $U, U' \in \F$, then
$\Pl(U|V \inter V') \le \Pl(U'|V \inter V')$ iff $\Pl(U
\inter V|V') \le \Pl(U' \inter V|V')$.
\end{description}
It is not hard to show that CPl5 implies CPl4.

\lem\label{CPl5} CPl5 implies CPl4. \elem
\prf
Since clearly $\Pl(U\inter V|V) = \Pl(U\inter V \inter V|V)$, by CPl5 it
follows that $\Pl(U|V \inter V) = \Pl(U\inter V|V \inter V)$, and hence
$\Pl(U|V) = \Pl(U \inter V| V)$. \eprf


CPl5 does not follow from CPl1--4 (indeed, as shown below, the
standard notion of conditioning for lower probabilities satisfies CPl1--4
but not CPl5).  A cps that satisfies CPl5 is said to be {\em coherent}.
Although I do not assume CPl5 here, it in fact holds for all
plausibility measures to which one of the main results applies
(see Lemma~\ref{lem:cpl5}).

In any case, CPl5 is certainly not the only coherence that might be required.
For example, it may seem reasonable to require that if $V$ and $V'$ are
disjoint, then it is not the case that both $\Pl(U|V \union V')  > \Pl(U|V)$
and $\Pl(U|V \union V') > \Pl(U|V')$.  Similarly, we may want to require
that it not be the case that  $\Pl(U|V \union V') < \Pl(U|V)$
and $\Pl(U|V \union V') < \Pl(U|V')$.%
\footnote{I think an anonymous referee of this paper for suggesting this
condition.} 
Coming up with a reasonable set of coherence conditions remains a topic
for future work.  The only properties needed for the results of this
paper are CPl1--4. 

The notion of cps considered here is closely related to that defined in
\cite{FrH7}.  There, a cps is taken to be a family $\{W,D_V,\Pl_V): V
\subseteq W, V \ne \emptyset\}$ of plausibility spaces, where each
plausibility measure 
$\Pl_V$ satisfies Pl1--3 and has domain $2^W$ and an analogue of CPl5
holds: $\Pl_{V \inter V'}(U) \le \Pl_{V \inter V'}(U')$ iff $\Pl_{V'}(U
\inter V) \le \Pl_{V'}(U' \inter V)$.  
To distinguish the definition of cps given in this paper from that given
in \cite{FrH7}, I call the latter an FH-cps.
There is no analogue to Acc1--4 in \cite{FrH7};
$\F$ is implicitly taken to be $2^W$, while $\F'$ is implicitly taken to
be $2^W - \{\emptyset\}$.  This is an inessential difference
between the definitions.  More significantly, note that
in an FH-cps, $(W,D_V,\Pl_V)$ is
a plausibility space for each fixed $V$, and thus satisfies Pl1--3.
However, requiring CPl1--3 is {\em a priori\/} stronger
than requiring Pl1--3 for each separate plausibility space.  Pl1
requires that $\Pl(\emptyset|V) = \bot_{D_V}$, but the elements $\bot_{D_V}$
may be different for each $V$.  By way of contrast, CPl1 requires that
$\Pl(\bot|V)$ must be the same element, $\bot_D$, for all $V$.
Similar remarks hold for Pl2.  Nevertheless, as is shown below,
there is a construction that converts an FH-cps to a coherent cps.


I now consider some standard ways of getting a cps
starting with an unconditional representation of uncertainty.
\dfn
A cps $(W,\F,\F',\Pl)$ {\em extends\/} an unconditional plausibility
space $(W,\F,\Pl')$ if $\Pl(U|W) = \Pl'(U)$.   $(W,\F,\F',\Pl)$ is {\em
standard\/} if  $\F' = \{U: \Pl(U) \ne \bot\}$.  
\edfn
All the constructions below result in standard cps's.

%\begin{description}
%joe: full paper
\commentout{
\item There are two
notions of conditioning for belief functions (see \cite{FH5}), one using
Dempster's rule of combination and the other treating beliefs as lower
probabilities.  Given a belief function $\Bel'$, both constructions lead
to a coherent conditional belief function extending $\Bel$, although in
general they are different.  Since belief functions do not play a
significant role in this paper, I omit the definitions here.
}%\end{commentout}
%\item

\paragraph{Ranking functions:} Given an unconditional ranking function
$\kappa$, there is a
well-known way of extending it to a conditional ranking function:
$$
\kappa(U|V) =
\left\{\begin{array}{ll}
\kappa(U \inter V) - \kappa(V) &\mbox{if $\kappa(V) \ne \infty$,}\\
\mbox{undefined}      &\mbox{if $\kappa(V) = \infty$.}
\end{array}\right.
$$
This is consistent with the view that if $\kappa(V) = k$, then
$\mu(V) = \epsilon^k$, since then $\kappa(U|V) =
\epsilon^{\kappa(U \inter V) - \kappa(V)}$.
It is easy to check that this definition
results in a coherent cps.
%\item
\paragraph{Possibility measures:}
There are two standard ways of defining a conditional possibility
measure from an unconditional possibility measure $\Poss$.  To
distinguish them, I write $\Poss(U|V)$ for the first approach and
$\Poss(U||V)$ for the second approach.
According to the first approach,
$$
\Poss(U|V) = \left\{
\begin{array}{ll}
\Poss(V \inter U) &\mbox{if $\Poss(V \inter U) < \Poss(V)$,}\\
1 &\mbox{if $\Poss(V \inter U) = \Poss(V) > 0$,}\\
\mbox{undefined}  &\mbox{if $\Poss(V) = 0$.}
\end{array} \right.
$$

The second approach looks more like conditioning in probability:
$$\Poss(U||V) = \left\{
\begin{array}{ll}
\Poss(V \inter U)/\Poss(V) &\mbox{if $\Poss(V) > 0$,}\\
\mbox{undefined}  &\mbox{if $\Poss(V) = 0$.}
\end{array} \right.
$$
It is easy to show that both definitions
result in a coherent cps.
(Many other notions of conditioning for possibility measures can be
defined; see, for example \cite{Fonck94}.  I focus on
these two because they are the ones most-often considered in the
literature.)

%\item
\paragraph{Sets of probabilities:}
For a set $\P$ of probabilities, conditioning can be defined
for all the representations of $\P$ as a plausibility measure.
But in each case there are subtle choices involving when conditioning
is undefined.  For example, one definition of conditional lower
probability is that
$\P_*(U|V)$ is
$\inf\{\mu(U|V): \mu(V) \ne 0\}$ if $\mu(V) \ne 0$ for all $\mu
\in \P$, and is undefined otherwise (i.e.,
if $\mu(V) = 0$ for some $\mu \in \P$).
It is easy to check that $\P_*$ defined this way gives a coherent cpm,
as does the corresponding definition of $\P^*$.
The problem with this definition
is that it may result in a rather small set $\F'$ for which
conditioning is defined. For example, if for each set $V \ne W$, there
is some measure $\mu \in \P$ such that $\mu(V) = 0$ (which can certainly
happen in some nontrivial examples), then $\F' = \{W\}$.
As a consequence, the cps defined in this way is not acceptable (i.e.,
does not satisfy Acc4) in general.

The following definition gives a lower probability which is
defined on more arguments:
$$\P_*(U|V) = \left\{
\begin{array}{ll}
\inf\{\mu(U|V): \mu(V) \ne 0\}
%joe: full poaper
&\mbox{if $\mu(V) \ne 0$ for some $\mu \in
\P$,}\\
\mbox{undefined} &\mbox{if $\mu(V) = 0$ for all $\mu \in \P$.}
\end{array}\right.
$$
It is easy to see that this definition agrees with the first one
whenever the first is defined and results, in general, in a larger set
$\F'$.  Moreover, the resulting cps is acceptable.
However, the second definition does not
satisfy CPl5. For example, suppose that $W = \{a,b,c\}$ and $\P =
\{\mu,\mu'\}$, where $\mu(a) = \mu(b) = 0$, $\mu(c) = 1$, $\mu'(a) = 2/3$,
$\mu'(b) = 1/3$, and $\mu'(c) = 0$.  Taking $V = \{a,b\}$, $U = \{a\}$,
and $U' = \{b\}$, it is easy to see that according to the second
definition, $\P_*(U \inter V|W) = \P_*(U' \inter V|W) = 0$, but
$\P_*(U|V) > \P_*(U'|V)$.

For $\PlP$, there are two analogous definitions.  For the first,
$\PlP(U|V)$ is defined only if $\mu(V) > 0$ for all $\mu \in \P$, in
which case $\PlP(U|V)$ is $f_{U|V}$, where $f_{U|V}(i) =
\mu_i(U|V)$.  This definition gives a coherent cps, but again, in general,
not one that is acceptable.  In this paper, I focus on the following
definition, which does result in an acceptable cps.

First extend $\DP$ by allowing functions which have value
$*$ (intuitively, $*$ denotes undefined).  More precisely, let $\DP'$
consist
of all functions $f$ from $I$ to $[0,1] \union \{*\}$ such that
$f(i) \ne
*$ for at least one $i \in I$.  The idea is to define
$\PlP(U|V) = f_{U|V}$, where $f_{U|V}(i) = \mu_i(U|V)$ if $\mu_i(V) > 0$
and $*$ otherwise.  (Note that this agrees with the previous definition,
which  applies only to the situation where $\mu(V) > 0$ for all $\mu \in
\P$.)  There is a problem though, one to which I have already alluded.
CPl1 says that $f_{\emptyset|V}$ must be $\bot$ for
all $V$.  Thus, it must be the case that $f_{\emptyset|V_1} =
f_{\emptyset|V_2}$ for all $V_1, V_2 \subseteq W$.
But if $\mu_i \in
\P$ and $V_1, V_2 \subseteq W$ are such that $\mu_i(V_1)> 0$ and $\mu_i(V_2)
= 0$, then $f_{\emptyset|V_1}(i) = 0$ and $f_{\emptyset|V_2}(i) =
*$, so $f_{\emptyset|V_1} \ne f_{\emptyset|V_2}$.  A similar problem
arises with CPl2.

To deal with this problem $\DP'$ must be slightly
modified.  Say that $f \in \DP'$ is
{\em equivalent to $\bot_{\DP^*}$\/} if $f(i)$ is
either 0 or * for all $i \in I$; similarly, {\em $f$ is equivalent to
$\top_{\DP^*}$\/} if $f(i)$
is either 1 or * for all $i \in I$.  (Since, by definition, $f(i)
\ne *$
for at least one $i \in I$, an element cannot be equivalent to both
$\top_{\DP^*}$ and $\bot_{\DP^*}$.)
Let $\DP^*$ be the same as
$\DP'$ except that all elements equivalent to $\bot_{\DP}$ are identified
(and viewed as one element) and all elements equivalent to $\top_{\DP^*}$ are
identified.   More precisely, let $\DP^* = \{\bot_{\DP^*},
\top_{\DP^*}\}
\union \{f \in D': \mbox{$f$ is not equivalent to $\top_{\DP^*}$ or
$\bot_{\DP^*}$}\}$.
Define the ordering
$\le$ on $\DP^*$ by taking $f \le g$ if one of the following three
conditions holds:
\begin{itemize}
\item $f = \bot_{\DP^*}$,
\item $g = \top_{\DP^*}$,
\item neither $f$ nor $g$ is $\bot_{\DP^*}$ or $\top_{\DP^*}$ and
for all $i \in I$, either $f(i)
= g(i) = *$ or $f(i) \ne *$, $g(i) \ne *$, and $f(i) \le g(i)$.
\end{itemize}
%It is easy to see that $\bot_{\DP^*}$ is
%the set of elements equivalent to $\bot_{\DP}$ and

%$\top_{\DP^*}$ is
%the set of elements equivalent to $\bot_{\DP}$.
%With these in hand,
Now define
$$\PlP(U|V) = \left\{
\begin{array}{ll}
\bot_{\DP^*} &\mbox{if $\mu(V) \ne 0$ for some $\mu \in \P$ and}\\
&\mbox{$\mu(V)
\ne 0$ implies $\mu(U|V) = 0$ for all $\mu \in \P$,}\\
%\bot_{\DP^*} &\mbox{if $\exists \mu \in \P(\mu(V) \ne 0)$ and}\\
%&\forall \mu \in \P(\mu(V) \ne 0 \rimp \mu(U|V) = 0),\\
%&\mbox{and $\mu(V)
%\ne 0$ implies $\mu(U|V) = 1$ for all $\mu \in \P$,}\\
\top_{\DP^*} &\mbox{if $\exists \mu \in \P(\mu(V) \ne 0)$ and
$\forall \mu \in \P(\mu(V) \ne 0 \rimp \mu(U|V) = 1)$,}\\
%joe1: for UAI
\mbox{undefined} &\mbox{if $\mu(V) = 0$ for all $\mu \in \P$,}\\
f_{U|V}      &\mbox{otherwise.}
\end{array}\right.
$$
It is easy to check that this gives a coherent cps.
%I remark that a similar construction can be used to convert any FH-cps
%to a cps and contruct a conditional plausibility measure from an
%unconditional plausibility measure.  I leave details to the full paper.
%\end{itemize}

\paragraph{Plausibility measures:} The construction for $\PlP$ can be used to convert any FH-cps to a
cps.  I
demonstrate the idea by showing how to construct a conditional
plausibility measure from an unconditional plausibility measure.  Given
an unconditional plausibility space $(W,\F,\Pl)$ with range $D$,
an FH-cps is
constructed in \cite{FrH7} by defining $\Pl(U|V) = \Pl(U \inter V)$.
Thus, $D_V = \{d \in D: d \le \Pl(V)\}$ and $\top_{D_V} = \Pl(V)$.
This is not a cps because CPl2 is not satisfied, but it is an FH-cps,
since Pl1--3 is satisfied for each fixed $V$, and so is CPl5.
As observed in \cite{FrH7}, this is in fact the FH-cps extending
$\Pl$ that makes the minimal number of comparisons,
in the sense that if $\Pl'$ is an FH-cps extending $\Pl$ and
$\Pl(U|V) \le \Pl(U'|V)$, then $\Pl'(U|V) \le \Pl'(U'|V)$.

To get a cps, let $\D' = \{(d,V): V \subseteq W, \, d \le \Pl(V), \,
\Pl(V) > \bot_D\}$.  Say that $(d,V)$ is {\em equivalent to
$\bot_{D^*}$\/} if
$d = \bot_D$; say that $(d,V)$ is {\em equivalent to $\top_{D^*}$\/} if
$d =\Pl(V)$.  Now let
$D^* = \{\bot_{D^*}, \top_{D^*}\}
\union \{f \in D': \mbox{$f$ is not equivalent to $\top_{D^*}$ or
$\bot_{D^*}$}\}$. Then define $d
\le_{D^*} d'$ for $d, d' \in D^*$ iff $d = \bot_{D^*}$, $d' =
\top_{D^*}$,
or there is some $V \subseteq W$ such that $d = (d_1,V)$, $d' =
(d_2,V)$, and $d_1 \le_D d_2$.  Finally, for $U, V \in \F$, define
$$\Pl(U|V) = \left\{
\begin{array}{ll}
(\Pl(U \inter V),V) &\mbox{if $\bot_D < \Pl(U \inter V) < \Pl(V)$,}\\
\top_{D^*}          &\mbox{if $\Pl(U \inter V) = \Pl(V) > \bot_D$,}\\
\bot_{D^*}          &\mbox{if $\Pl(U \inter V) = \bot_D$, $\Pl(V) >
\bot_D$,}\\
\mbox{undefined}    &\mbox{if $\Pl(V) = \bot_D$.}
\end{array}\right.$$
I leave it to the reader to check that $\Pl$ is a coherent cpm. It is
important that $\Pl(U|V)$ is undefined if $\Pl(V) = \bot_D$;  if we
tried to extend the construction to $V$ such that $\Pl(V) = \bot_D$,
then we would have $\top_{D^*} = \bot_{D^*}$.  This issue did not
arise in \cite{FrH7}, since there were separate plausibility spaces for
each choice of $V$.

\bigskip

%Note that in all these constructions, $\F' = \{V: \Pl(V) \ne \bot\}$.
%Since this arises so frequently, I call a cps $(W,\F,\F',\Pl)$ such
%that $\F' = \{V: \Pl(V|W) \ne \bot\}$ {\em standard}.

%This follows from a more
%general observation.  $(W,\F,\F',\Pl)$ is
%{\em determined by unconditional plausibility (according to $g: D \times
%D \rightarrow D$)\/} if
%$\Pl(U|V) = g(\Pl(U \inter V|W),\Pl(V|W))$ for all $(U,V)
%\in \F \times \F'$.  It is almost
%immediate from the definitions that all the constructions above
%result in cps's that are determined by
%unconditional plausibility. If an acceptable cps is determined by unconditional
%plausibility, then it must be standard.
%
%\lem\label{lem:F'} If $(W,\F,\F',\Pl)$ is an acceptable cps
%determined by unconditional
%plausibility such that $\Pl(W) \ne \Pl(\emptyset)$, then
%$(W,\F,\F',\Pl)$ is a standard cps.
%\elem
%\prf By Acc2 and Acc3, $W \in
%\F'$, so by Acc4, $\{V \in \F: \Pl(V|W) \ne \bot\} \subseteq \F'$.
%If there exists some $V \in \F'$ such that $\Pl(V|W) = \bot_D$, then
%by CPl3, $\Pl(U\inter V|W) = \bot_D$, so
%$\Pl(U|V) = g(\Pl(U \inter V|W),\Pl(V|W)) = g(\bot_D,\bot_D)$
%for all $U \subseteq W$.  Thus, by CPl1 and CPl1, $\top_D = \Pl(W|V) =
%\Pl(\emptyset|V) = \bot_D$, a contradiction.  Thus, $\F' = \{V: \Pl(V|W)
%\ne \bot_D\}$, as desired. \eprf


\section{Algebraic  Conditional  Plausibility  Measures}\label{sec:alg}
To be able to carry out the type of reasoning used in Bayesian networks,
it does not suffice to just have conditional plausibility.  We need to
have analogues of addition and multiplication.  More precisely, there
needs to be some way of computing the plausibility of the union of two
disjoint sets in terms of the plausibility of the individual sets and
%what can be viewed as a strengthening of CPl5, which allows
a way
of computing $\Pl(U\inter V|V')$ given $\Pl(U| V \inter V')$ and
$\Pl(V|V')$.

\dfn A cps $(W,\F,\F',\Pl)$ where $\Pl$ has range $D$ is {\em
algebraic\/} if it is acceptable and
there are functions $\oplus: D \times D \rightarrow D$ and $\otimes :
D \times D \rightarrow D$  such that the following properties hold:
%and
%$\{\Pl(U|V \inter V'),\Pl(V|V'): U \in \F, \, V \inter V' \in F'\}
%\subseteq \Dom(\otimes) \subseteq D \times D$,
\begin{description}
\item[{\rm Alg1.}] If $U, U' \in \F$ are disjoint and $V \in \F'$ then
%$(\Pl(U|V),\Pl(U'|V)) \in \Dom(\oplus)$ and
$\Pl(U \union U'|V) = \Pl(U|V) \oplus \Pl(U'|V)$.
\item[{\rm Alg2.}]
If $U \in \F$, $V \inter V' \in \F'$, then
%$(\Pl(U|V \inter V'),\Pl(V|V')) \in \Dom(\otimes)$ and
$\Pl(U\inter V|V') = \Pl(U|V \inter V') \otimes \Pl(V|V')$.
%\end{description}
%
%Note that, given CPl4,  Alg2 can be simplified to
%\begin{itemize}
%\item[Alg2$'$.] $\Pl(U|V') = Pl(U|V ) \otimes Pl(V|V')$
%if $U \subseteq V \subseteq V'$, $U, V' \in \F$, $V \in \F'$.
%\end{itemize}
%Clearly Alg2$'$ is a special case of Alg2.  Moreover, by CPl4, Alg2 is
%equivalent to $\Pl(U \inter V \inter V'|V') = \Pl(U \inter V \inter V'|V
%\inter V') \otimes \Pl(V \inter V'| V')$, which is a special case of
%Alg2$'$.
%
\item[{\rm Alg3.}] $\otimes$ distributes over $\oplus$; more precisely,
%$a \otimes (b \oplus b') = (a \otimes b) \oplus (a \otimes b')$.
      $a \otimes (b_1 \oplus \cdots \oplus b_n) = (a \otimes b_1) \oplus
\cdots \oplus (a \otimes b_n)$
%and $(a_1 \oplus \cdots \oplus a_n)
%\otimes b = (a_1 \otimes b) \oplus \cdots \oplus (a_n \otimes b)$
if $(a,b_1), \ldots , (a,b_n), (a,b_1 \oplus \cdots \oplus  b_n)
%(a_1,b), \ldots,  (a_n,b), (a_1 \oplus \cdots \oplus a_n, b)
\in \Dom_{\sPl}(\otimes)$ and $(b_1, \ldots, b_n), (a \otimes b_1,
\ldots, a \otimes b_n) \in \Dom_{\sPl}(\oplus)$, where
$\Dom_{\sPl}(\oplus) = \{(\Pl(U_1|V),\ldots,
\Pl(U_n|V)): U_1, \ldots, U_n \in \F$ are pairwise disjoint and $V \in \F'\}$
and $\Dom_{\sPl}(\otimes) = \{(\Pl(U|V \inter V'),\Pl(V|V')): U \in \F, \, V
\inter V' \in F'\}$.%
\footnote{In the conference version of this paper, $\Dom(\oplus)$ was
taken to consist only of pairs, not tuples of arbitrary finite length,
and distributivity was considered only for terms of the form $a \otimes
(b \oplus b')$.  The more general version considered here is slightly
stronger.  The reason is that it is possible that $(a, b_1 \oplus
\cdots \oplus b_n) \in \Dom(\otimes)$ even though $(a, b_1 \oplus \cdots
\oplus b_k) \notin \Dom(\otimes)$ for $k \le n$.  Note also that only
left distributivity is required here.}
(See below for a discussion of $\Dom_{\sPl}(\oplus)$ and
$\Dom_{\sPl}(\otimes)$.  In the sequel, I omit the subscript $\Pl$ if it
is clear from context.)
\item[{\rm Alg4.}] If $(a,c), \, (b,c) \in \Dom(\otimes)$,
%\{(\Pl(U|V \inter V'),\Pl(V|V')): U \in \F, \, V
%\inter V' \in F'\}$,
$a \otimes c \le b \otimes c$, and $c \ne \bot$, then $a \le b$.
%(See below for more discussion of $\Dom(\otimes)$.)
%$a = \Pl(U_1|V_1)$, $b =
%\Pl(U_2|V_2)$, and $c = \Pl(V_1|V_1') = \Pl(V_2|V_2')$ for some $U_1
%\subseteq V_1 \subseteq V_1'$ and $U_2 \subseteq V_2 \subseteq V_2'$,
\end{description}
%A cps $(W,\F,\F',\Pl)$ is algebraic if it is acceptable and $\Pl$ is
%algebraic.
I sometimes refer to the cpm $\Pl$ as being algebraic as well. 
\edfn

It may seem more natural to consider a stronger version of Alg4 that
applies to all pairs in $D \times D$, such as
\begin{description}
\item[{\rm Alg4$'$.}] If $a \otimes
c \le b \otimes c$ and $c \ne \bot$, then $a \le b$.
\end{description}
However, as Proposition~\ref{algebraicpl} below shows, by requiring that
Alg3 and Alg4 hold only for tuples in $\Dom(\oplus)$ and $\Dom(\otimes)$
rather than on all tuples in $D \times D$, some cps's of interest become
algebraic that would otherwise  not be.
Intuitively, we care about $\otimes$ mainly to
the extent that Alg1 and Alg2 holds, and Alg1 and Alg2 apply only to tuples in
$\Dom(\oplus)$ and $\Dom(\otimes)$, respectively.  Thus, it does not
seem unreasonable that
Alg4 be required to hold only for these tuples.
%\footnote{In the conference version of this paper, Alg3 was required to
%hold only for tuples in $\Dom(\otimes)$ and the analogous $\Dom(\oplus)$
%for $\oplus$.  However, it turns out that by allowing elements greater
%that $\top_D$ in $D$, the simpler version of Alg3 used here holds for
%all domains of interest.}
%Note that although there are no requirements here that either
%$\oplus$ or $\otimes$ be commutative or associative,
%these properties follow for the values to which $\oplus$ and $\otimes$
%are applied.  For example, if $\Pl$ is algebraic and $U$, $V$, and $V'$
%are pairwise disjoint sets such that $a = \Pl(U)$, $b = \Pl(V)$, and $c
%= \Pl(V')$, then it is easy to see that $a \oplus b = b \oplus a$ and $a
%\oplus (b \oplus c) = (a \oplus b) \oplus c$ (since union is commutative
%and associative).  Similarly, it can be shown that $\otimes$ is
%associative for tuples of interest.  I omit parentheses in expressions
%involving $\oplus$ and $\otimes$ when associativity holds.
%(See \cite{FrH7} for further discussion of these
%properties in the context of FH-cps's.)

\pro\label{algebraicpl} The constructions for extending an unconditional
probability measure,
ranking function, possibility measure
(using either $\Poss(U|V)$ or $\Poss(U||V)$), and the plausibility
measure $\PlP$ defined by a set $\P$ of probability measures to a cps
result in algebraic cps's.%
\footnote{Essentially the same result is proved in \cite{FrH7} for all
cases but $\PlP$.}
%\commentout{
%Indeed, it is shown that
%the following stronger version of Alg4 holds:
%\begin{description}
%\item[{\rm Alg4$^+$.}] If $(a,c), \, (b,c') \in \Dom(\otimes)$,
%$a \otimes c \le b \otimes c'$, and $c \ge c'$,
%then $a \le b$.
%\end{description}}
\epro

\prf
It is easy to see that in each case the cps is acceptable.  It is
also easy to find appropriate notions of $\otimes$ and $\oplus$ in
the case of probability measures, ranking functions, and possibility
measures using $\Poss(U||V)$.  For probability, clearly
$\oplus$ and $\otimes$ are essentially $+$ and $\times$; however, since
the range of probability is $[0,1]$,
$a \oplus b$ must be defined as
$\max(1,a+b)$, and Alg3 holds only for
$\Dom(\oplus) = \{(a_1, \ldots, a_k) : a_1 + \cdots + a_k \le 1\}$;
there is no constraint on $\Dom(\times)$; it is $[0,1] \times [0,1]$.
For ranking,
$\oplus$ and $\otimes$ are $\min$ and $+$; there are no constraints on
$\Dom(\min)$ and $\Dom(+)$.
For $\Poss(U||V)$,
$\oplus$ is $\max$ and $\otimes$ is $\times$; again, there are no
constraints on $\Dom(\max)$ and $\Dom(\times)$.
I leave it to the reader to check that Alg1--4 hold in all these cases.

For $\Poss(U|V)$, $\oplus$ is again $\max$ and $\otimes$
is $\min$.  There are no constraints on $\Dom(\max)$;
however, note that $(a,b) \in \Dom(\min)$ iff
either $a < b$ or $a=1$.  For suppose that $(a,b) = (\Poss(U |V \inter
V'),\Poss(V|V')$, where $U \in \F$ and $V \inter V' \in \F'$.  If
$\Poss(U \inter V \inter V') = \Poss(V \inter V')$ then
$a = \Poss(U|V \inter V') = 1$; otherwise, $\Poss(U \inter V \inter V') <
\Poss(V \inter V')$, in which case $a = \Poss(U |V \inter V') = \Poss(U
\inter V
\inter V') < \Poss(V \inter V') \le \Poss(V|V') = b$.  It is easy to check
Alg1--3.   While $\min$ does
not satisfy Alg4$'$---certainly $\min(a,c) = \min(b,c)$ does not
in general imply that $a=b$---Alg4 does hold.
For if $\min(a,c) \le \min(b,c)$ and $a=1$, then clearly
$b=1$.  Alternatively, if $a < c$, then $\min(a,c) = a$ and the only
way that $a \le \min(b,c)$, given that $b < c$ or $b=1$, is if $a \le b$.

Finally, for $\PlP$, $\oplus$ and $\otimes$ are essentially pointwise
addition and multiplication.   But there are a few subtleties.  As in
the case of probability, $\Dom(\oplus)$ consists of sequences which
sum to at most 1 for each index $i$.  Care must also be taken in dealing
with $\bot_{\DP^*}$ and $\top_{\DP^*}$.  More precisely,
$\Dom(\oplus)$ consists of all tuples $(f_1, \ldots, f_n)$ such that
either
\begin{enumerate}
\item[1(a).] $f_j  \ne \top_{\DP^*}, j = 1, \ldots, n$,
\item[1(b).] if $f_j, f_k \ne \bot_{\DP^*}$ for $1 \le j, k \le n$, then
$f_j(i) = * \mbox{ iff } f_k(i) = *$, for all $i \in I$, and
\item[1(c).] $\sum_{\{j: f_j \ne \bot_{\DP^*}, f_j(i) \ne *\}} f_j(i) \le 1$
\end{enumerate}
or
\begin{enumerate}
\item[2.] there exists $j$ such that $f_j =
\top_{\DP^*}$ and  $f_k = \bot_{\DP^*}$ for $k \ne j$;
\end{enumerate}
$\Dom(\otimes)$
consists of pairs $(f,g)$ such that either one of $f$ or $g$ is in
$\{\bot_{\DP^*},\top_{\DP^*}\}$ or neither $f$ nor $g$ is in
$\{\bot_{\DP^*},\top_{\DP^*}\}$ and
$g(i) \in \{0, *\} \mbox{ iff } f(i) = *$.
%However, we must be a little careful in
%dealing with $\top_{\DP^*}$, $\bot_{\DP^*}$, and $*$.
The definition of $\oplus$ is relatively straightforward.
Define $f \oplus
\top_{\DP^*} = \top_{\DP^*} \oplus f = \top_{\DP^*}$ and
$f \oplus \bot_{\DP^*} = \bot_{\DP^*} \oplus f = f$.  If $f,g \inter
\{\bot_{\DP^*},\top_{\DP^*}\} = \emptyset$, then $f \oplus g = h$, where
$h(i) = \min(1,f(i) + g(i))$ 
(taking $a + * = * + a = *$ and
$\min(1,*) = *$).
In a similar spirit,
%$\Dom(\otimes) = \{(f,g):$ either $\{f,g\} \inter
%\{\bot_{\DP^*},\top_{\DP^*} \ne \emptyset$ or
%$(\{f,g\} \inter
%\{\bot_{\DP^*},\top_{\DP^*} =\emptyset$, $g(\mu) \in \{0,*\}$ iff
%$f(\mu) = *)\}$.  It is easy
%to check that $\{(\PlP(U|V \inter V'),\PlP(V|V')): U \in \F, \, V \inter
%V' \in \F'\} \subseteq \Dom(\otimes)$, since if $\mu(V') = 0$ or
%$\mu(V|V') = 0$ then
%$\mu(V \inter V') = 0$.
define $f \otimes
\top_{\DP^*} = \top_{\DP^*} \otimes f = f$ and
$f \otimes \bot_{\DP^*} = \bot_{\DP^*} \otimes f = \bot_{\DP^*}$;  if
$\{f,g\} \inter
\{\bot_{\DP^*},\top_{\DP^*}\} = \emptyset$, then $f \otimes g = h$, where
$h(i) =
f(i) \times g(i)$ (taking $ * \times a = a \times * = *$ if $a \ne
0$ and $* \times 0 = 0 \times * = 0$).   It is important that $* \times 0
= 0$ and $* 
\times * = *$,
since otherwise Alg3 may not hold.  For example,
according to Alg3,  
%$$\begin{array}{rcl}
$$((1/2,*,1/2) \otimes
(a,0,b)) \oplus ((1/2,*,1/2)) \otimes (a,0,b)) 
= ((1/2,*,1/2) \oplus (1/2,*,1/2)) \otimes (a,0,b)
= (a,0,b)$$
(since $(1/2,*,1/2) \oplus (1/2,*,1/2) = \top_{\DP^*}$) and, similarly,
$((1/2,*,1/2) \otimes (a,*,b)) \oplus ((1/2,*,1/2)) \otimes (a,*,b)) =
(a,*,b)$.  Since $* \times 0 = 0$ and $* \times * = *$, these equalities
hold.  I leave
it to the reader to check that, with these definitions, Alg1--4 hold
(although note that the restrictions to $\Dom(\oplus)$ and
$\Dom(\otimes)$ are required for both Alg3 and Alg4 to hold).  \eprf

Conditional lower probability is not algebraic.   For 
example, it is not hard to construct
pairwise disjoint sets $U_1$, $V_1$,
$U_2$, and $V_2$ and a set $\P$ of probability measures
such that $\P_*(U_i) = \P_*(V_i)$ (and $\P^*(U_i) = \P^*(V_i)$) for
$i=1,2$, but $\P_*(U_1 \union U_2) \ne \P_*(V_1 \union V_2)$.  That
means there cannot be a function $\oplus$ in the case of lower
probability.%
%joe2
\footnote{For readers familiar with Dempster-Shafer belief functions
\cite{Shaf}, they provide another example of a plausibility measure.
There are two well-known ways of defining conditioning for belief
functions (see \cite{FH5}), one using Dempster's rule of combination and
the other treating belief functions as lower probabilities.  Neither
leads to an algebraic cps, which is why I have not discussed belief
functions in this paper.}

For later convenience, I list some simple properties of algebraic
cpms that show that $\bot$ and $\top$ act like 0 and 1 with respect to
addition and multiplication.
Let $\Range(\Pl) = \{d: \Pl(U|V) = d \mbox{ for some } (U,V) \in \F
\times
\F'\}$.

\lem\label{lem0.5} If $(W,\F,\F',\Pl)$ is an algebraic cps, then $d \oplus \bot = \bot \oplus d = d$ for all $d \in
\Range(\Pl)$.
\elem
\prf Suppose that $d = \Pl(U|V)$.  By Alg1, it follows that
$$d = \Pl(U|V) = \Pl(U \union \emptyset|V) = \Pl(U|V) \oplus
\Pl(\emptyset|V) = d \oplus \bot.$$
A similar argument shows that $d = \bot \oplus d$.  \eprf


%joe5: pch4
\lem\label{lem0.7} If $(W,\F,\F',\Pl)$ is an algebraic cps then, for all
$d \in \Range(\Pl)$,
\begin{itemize}
\item[(a)] $d \otimes \top =  d$;
\item[(b)] if $d \ne \bot$, then $\top \otimes d = d$;
\item[(c)] if $d \ne \bot$, then $\bot \otimes d = \bot$;
\item[(d)] if $(d,\bot) \in \Dom(\otimes)$, then $\top \otimes \bot = d
\otimes \bot = \bot \otimes \bot = \bot$.
\end{itemize}
\elem

\prf Suppose that $d = \Pl(U|V)$.  By Alg2, CPl2, and CPl4,
it follows that
$$d = \Pl(U|V) = \Pl(U \inter V|V) = \Pl(U|V) \otimes \Pl(V|V) =  d
\otimes \top.$$
Similarly, if $d \ne \bot$, then $U \inter V \in \F'$ (by
Acc4), so
$$d = \Pl(U|V) = \Pl(U \inter V|V) = \Pl(U\inter V|U \inter V) \otimes
\Pl(U \inter V|V)
= \top \otimes d.$$
If $d \ne \bot$, then by Alg2, CPl1, and CPl4
$$\bot = \Pl(\bot|V) = \Pl(\bot|U \inter V) \otimes \Pl(U|V) = \bot
\otimes d.$$
Finally, if $(d,\bot) \in \Dom(\otimes)$, then there exist $U, V, V'$
such that $V \inter V' \in \F'$, $\Pl(U|V \inter V') = d$ and $\Pl(V|V')
= \bot$.  By Alg2,
$\Pl(U \inter V|V') = \Pl(U|V \inter V') \otimes \Pl(V|V') = d \otimes
\bot$.  By CPl3, $\Pl(U \inter V|V') \le \Pl(V|V') = \bot$, so $\Pl(U
\inter V|V') = \bot$.  Thus, $d \otimes \bot = \bot$.  Replacing $U$
with $V \inter V'$, the same argument shows that $\top \otimes \bot =
\bot$; replacing $U$ with $\emptyset$, we get that $\bot \otimes \bot =
\bot$.  \eprf



%joe: pch4



I conclude this section by showing that a standard algebraic cps that
satisfies one
other  minimal property must also satisfy CPl5.  Say that $\otimes$ is
{\em monotonic\/} if $d \le d'$ and $e \le e'$ then
%$d' \ne \bot$ implies that
$d \otimes e \le d' \otimes e'$.  A cpm (cps) is monotonic
if $\otimes$ is.

\lem\label{lem:cpl5} A standard algebraic monotonic cps
satisfies CPl5.
\elem
\prf  Suppose that $(W,\F,\F',\Pl)$ is a standard algebraic cps and
that $V \inter V' \in \F'$.  If $\Pl(U|V \inter V') \le
\Pl(U'|V \inter V')$, then it follows from Alg2 and monotonicity that
%if $\Pl(V|V') \ne \bot$, then
$$
\Pl(U \inter V|V')= \Pl(U|V \inter V') \otimes \Pl(V|V') \le \Pl(U'|V
\inter V') \otimes \Pl(V|V') = \Pl(U' \inter V|V').
$$
%On the other hand, if $\Pl(V|V') = \bot$, then by CPl3, $\Pl(U \inter
%V|V') \bot = \Pl(U' \inter V|V')$.
For the opposite implication,
suppose that $\Pl(U \inter V|V') \le  \Pl(U' \inter V|V')$.  Then, by
Alg2, 
\begin{equation}\label{eqcpl5}
\Pl(U|V \inter V') \otimes \Pl(V|V') \le \Pl(U'|V \inter V')
\otimes \Pl(V|V').\end{equation}
Since $V \inter V' \in \F'$ and the cps is standard, it must be the case
that $\Pl(V \inter V') \ne \bot$.  Hence (by CPl3), $\Pl(V') \ne \bot$;
moreover, $\Pl(V|V') \ne \bot$ (otherwise $\Pl(V \inter V') = \Pl(V|V')
\otimes \Pl(V') = \bot$). Thus,
by applying Alg4 to (\ref{eqcpl5}), it follows that $\Pl(U|V \inter
V') \le \Pl(U'|V \inter V')$.  \eprf



\section{Independence}\label{sec:ind}
How can we capture formally the notion that two events are
{\em independent}?  Intuitively, it means that they have nothing to do
with each other---they are totally unrelated; the occurrence of one has
no influence on the other.  None of the representations of
uncertainty that we have been
considering can express the notion of ``unrelatedness'' (whatever it
might mean) directly.  The best we can do is to capture the
``footprint'' of independence on the notion.
For example, in the case of probability, if $U$ and $V$ are unrelated,
it seems reasonable to expect that
learning $U$ should not affect the probability of $V$
and symmetrically, learning $V$ should not affect the probability of
$U$.  ``Unrelatedness'' is, after all, a symmetric notion.%
\footnote{Walley \citeyear{Walley91} calls the asymmetric notion {\em
irrelevance} and defines $U$ being independent of $V$ as $U$ is
irrelevant to $V$ and $V$ is irrelevant to $U$.  Although my focus here
is independence, irrelevance is an interesting notion in its own right;
see \cite{Cozman98,CozmanWalley}.}
The fact that $U$ and $V$ are probabilistically
independent (with respect to probability measure $\mu$) can thus be expressed
as $\mu(U|V) = \mu(U)$ and
$\mu(V|U) = \mu(V)$.  There is a technical problem with this definition:
What happens if $\mu(V) = 0$?  In that case $\mu(U|V)$ is undefined.
Similarly, if $\mu(U) = 0$ then $\mu(V|U)$ is undefined.
It is conventional to say that, in
this case, $U$ and $V$ are still independent.  This leads to
the following formal definition.

\dfn\label{dfn.indep}
$U$ and $V$ are {\em probabilistically independent (with respect to
probability measure $\mu$)\/} if $\mu(V) \ne 0$ implies $\mu(U|V) =
\mu(U)$ and $\mu(U) \ne 0$ implies $\mu(V|U) = \mu(V)$. \edfn

This does not look like the standard definition of independence in
texts, but an easy calculation shows that it is equivalent.
\pro\label{lem.indep} The following are equivalent:
\begin{itemize}
\item[(a)] $\mu(U) \ne 0$ implies $\mu(V|U) = \mu(V)$,
\item[(b)] $\mu(U \inter V) = \mu(U) \mu(V)$,
\item[(c)] $\mu(V) \ne 0$ implies $\mu(U|V) = \mu(U)$.
\end{itemize}
\epro

Thus, in the case of probability, it would be equivalent to say that $U$
and $V$ are independent with respect to $\mu$ if $\mu(U \inter V) =
\mu(U)\mu(V)$ or to require only that $\mu(U|V) = \mu(U)$ if $\mu(V) \ne
0$ without requiring that $\mu(V|U) = \mu(V)$ if $\mu(U) \ne 0$.
However, these equivalences do not necessarily hold for other
representations of uncertainty.  The definition of independence I have
given here seems to generalize more appropriately.%
\footnote{Another property of probabilistic independence is that if $U$
is independent of $V$ then $\overline{U}$ is independent of $V$.  This
too does not follow for the other representations of uncertainty, and
Walley~\citeyear{Walley91} actually makes this part of his definition.
Adding this requirement would not affect any of the results here, although it
would make the proofs somewhat lengthier, so I have not made it part of the
definition.}

The definition of probabilistic conditional independence is analogous.
\dfn\label{dfn.condindep}
$U$ and $V$ are {\em probabilistically independent given $V'$ (with
respect to
probability measure $\mu$)\/} if $\mu(V
\inter V') \ne 0$ implies $\mu(U|V \inter V') =
\mu(U|V')$ and $\mu(U \inter V') \ne 0$ implies $\mu(V|U \inter V') =
\mu(V|V')$.
\edfn
It is immediate that $U$ and $V$ are (probabilistically) independent
iff they are independent conditional on $W$.

The generalization to conditional plausibility measures (and hence to
all
other representations of uncertainty that we have been considering) is
straightforward.
\dfn\label{dfn.condindeppl}
Given a cps $(W,\F,\F',\Pl)$,
$U,V \in \F$ are {\em plausibilistically independent given $V' \in \F$
(with respect to the cpm $\Pl$)\/}, written $I_{\sPl}(U,V|V')$, if $V
\inter V' \in \F'$ implies $\Pl(U|V \inter V') =
\Pl(U|V')$ and $U \inter V'  \in \F'$ implies $\Pl(V|U \inter V') =
\Pl(V|V')$.
\edfn

%We get an analogue of Proposition~\ref{lem.indep} for cps's that are
%algebraic, right-invertible, and standard.
%
%\pro\label{lem.indep1} If $(W,\F,\F',\Pl)$ is algebraic,
%right-invertible, and standard, then the following are equivalent:
%\begin{itemize}
%\item[(a)] $U \in \F'$ implies $\Pl(V|U) = \Pl(V)$,
%\item[(b)] $\Pl(U \inter V) = \Pl(U) \otimes \Pl(V)$,
%\item[(c)] $V \in \F'$ implies $\Pl(U|V) = \Pl(U)$.
%\end{itemize}
%\epro


We are interested in conditional independence of random variables as
well as in conditional independence of events.
All the standard definitions extend to plausibility
in a straightforward way.  A {\em random variable\/} $X$ on
$W$ is a function from $W$ to the reals.  Let
$\R(X)$ be the set of possible values for $X$
(that is, the set of values over which $X$ {\em ranges}).  As usual,
$X=x$ is the event $\{w: X(w) = x\}$.
If ${\bf X} = \{X_1, \ldots, X_k\}$ is a set of random variables and
${\bf x} =
(x_1, \ldots, x_k)$, let ${\bf X = x}$ be an abbreviation for the event
$X_1 = x_1 \inter \ldots \inter X_k = x_k$.
A random
variable is {\em measurable} with respect to cps $(W,\F,\F',\Pl)$
if $X=x \in \F$ for all $x \in \R(X)$.  For the rest
of the paper, I assume that all random variables $X$ are measurable and
that $\R(X)$ is finite for all random variables $X$.  Random variables
$X$
and $Y$ are independent with respect to plausibility measure $\Pl$ if
the events $X=x$ and $Y=y$ are independent for all $x \in \R(X)$ and $y
\in \R(Y)$.  More generally, given sets {\bf X}, {\bf Y}, and {\bf Z} of
random variables, ${\bf X}$ and {\bf Y} are plausibilistically
independent given {\bf Z} (with respect to $\Pl$), denoted $\IrvPl({\bf
X},{\bf Y}|{\bf Z})$, if $\IPl({\bf X = x},{\bf Y = x}|{\bf Z = z})$ for
all {\bf x}, {\bf  y}, and {\bf z}.  (Note that I am using $\IPl$ for
conditional independence of events and $\IrvPl$ for conditional
independence of random variables.)  If ${\bf Z } = \emptyset$, then
$\IrvPl({\bf
X},{\bf Y}|{\bf Z})$ if ${\bf X}$ and ${\bf Y}$ are unconditionally
independent, that is, if $\IPl({\bf X = x},{\bf Y = x}|W)$
for all {\bf x}, {\bf  y};
if either ${\bf X} = \emptyset$ or ${\bf Y}
= \emptyset$, then $\IrvPl({\bf X}, {\bf Y}|{\bf Z})$ is taken to be
vacuously true.


Now consider the following four properties of random variables, called
the {\em semi-graphoid properties} \cite{Pearl}, where {\bf X}, {\bf
Y}, and {\bf Z} are pairwise disjoint sets of variables.

\begin{description}
\item[{\rm CIRV1.}] If $\IrvPl({\bf X},{\bf Y}|{\bf Z})$ then
$\IrvPl({\bf Y},{\bf X}|{\bf Z})$.
\item[{\rm CIRV2.}] If $\IrvPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf
Z})$ then $\IrvPl({\bf X},{\bf Y}|{\bf Z})$.
\item[{\rm CIRV3.}] If $\IrvPl({\bf X},{\bf Y} \union {\bf Y'}|{\bf
Z})$ then $\IrvPl({\bf X},{\bf Y}|{\bf Y}' \union {\bf Z})$.
\item[{\rm CIRV4.}] If $\IrvPl({\bf X},{\bf Y}|{\bf Z})$ and
$\IrvPl({\bf X}, {\bf Y}'| {\bf Y} \union {\bf Z})$ then
$\IrvPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf Z})$.
\end{description}

It is well known that CIRV1--4 hold for probability measures.  The
following result generalizes this.  The proof is not difficult, although
care must be taken to show that the result depends only on the
properties of algebraic cpms.

\thm\label{thm:alg} CIRV1--4 hold for all algebraic cps's.
\ethm
\prf See the appendix. \eprf


Theorem~\ref{thm:alg}, of course, is very dependent on the definition of
conditional independence given here.  Other notions of independence
have been studied in the literature for specific representations
of uncertainty. Perhaps the most common definition tries to generalize the
observation that if $U$ and $V$ are probabilistically independent, then
$\mu(U \inter V) = \mu(U) \times \mu(V)$.  Zadeh \citeyear{Zadeh1}
considered this approach in the context of possibility measures, calling
it {\em noninteraction}, but it clearly
makes sense for any algebraic cpm.

\dfn $U$ and $V$ {\em do
not interact given $V'$ (with respect to the algebraic cpm $\Pl$)\/}, denoted
$\NIPl(U,V|V')$, if $V' \in
\F'$ implies that $\Pl(U \inter V|V') = \Pl(U|V') \otimes \Pl(V|V')$.%
\footnote{Shenoy \citeyear{Shenoy94} defines a notion similar in spirit
to noninteraction for random variables.}
\edfn
Fonck \citeyear{Fonck94} shows that noninteraction
is strictly weaker than independence for a number of notions of
independence for possibility measures.  The following result shows that
independence implies noninteraction for all algebraic cpms.

\lem\label{NI1} If $(W,\F,\F',\Pl)$ is an algebraic cps, then
$I_{\sPl}(U,V|V')$ implies $\NIPl(U,V|V')$. \elem
\prf Suppose that $V' \in \F'$ and $I_{\sPl}(U,V|V')$ holds.  If $V
\inter V' \in \F'$ then, from Alg2, it follows that
$$\Pl(U \inter V|V') = \Pl(U|V \inter V') \otimes \Pl(V|V') = \Pl(U|V')
\otimes \Pl(V|V').$$
On the other hand, if $V \inter V' \notin \F'$, then by Acc4, $\Pl(V|V')
= \bot$.  By CPl3, $\Pl(U \inter V|V') = \bot$, and by
Lemma~\ref{lem0.5}, $\Pl(U|V') \otimes \Pl(V|V') = \bot$.  Thus,
$\Pl(U \inter V|V') = \Pl(U|V') \otimes \Pl(V|V')$.  \eprf


What about the converse to Lemma~\ref{NI1}?  The results of Fonck show
that it does not hold in general---indeed, it does not hold for
$\Poss(U|V)$.  So what is required for noninteraction to imply
independence?  The following lemma provides a sufficient condition.
%The following result gives some sense of why.
%Consider the two properties:
%\begin{description}
%\item[{\rm Alg4$''$.}] If $a \otimes c = b \otimes c$ and $c \ne \bot$, then
%$a=b$.
%\item[{\rm Acc5.}] If $U \in \F$, $V \in \F'$, and $\Pl(U|V) = \bot$, then $U
%\inter V \in \F'$.
%\end{description}
%Alg4$''$ holds for the $\otimes$ associated with conditional
%probability and
%conditional ranking, but not for the $\otimes$ associated with
%$\Poss(\cdot|\cdot)$ nor with the $\otimes$ associated with $\PlP$.
%Acc5 is essentially a converse to Acc4.
%As the following lemma shows, in the presence of Alg4$''$ and Acc5,
%noninteractivity implies independence.

\lem\label{NI2} If $(W,\F,\F',\Pl)$ is a standard algebraic cps that
satisfies Alg4$'$,
then $\NIPl(U,V|V')$ implies $I_{\sPl}(U,V|V')$. \elem
\prf Suppose that $V \inter V' \in \F'$ and $\NIPl(U,V|V')$.
Then by Alg2,
\begin{equation}\label{ni2eq1}
\Pl(U \inter V | V') = \Pl(U|V \inter V') \otimes \Pl(V|V').
\end{equation}
By Acc3, $V' \in \F'$, so $\NIPl(U,V|V')$ implies
\begin{equation}\label{ni2eq2}
\Pl(U \inter V | V') = \Pl(U| V') \otimes \Pl(V|V').
\end{equation}
Since $V \inter V' \in \F'$ and $(W,\F,\F',\Pl)$ is standard, $\Pl(V
\inter V') \ne \bot$.  Since $\Pl(V \inter V') = \Pl(V|V') \otimes
\Pl(V')$, it follows from Lemma~\ref{lem0.7} that $\Pl(V|V') \ne \bot$.
So, by Alg4$'$, (\ref{ni2eq1}), and (\ref{ni2eq2}), it follows that
$\Pl(U|V \inter V') =
\Pl(U|V')$.  An identical argument shows that $\Pl(V|U \inter V') =
\Pl(V|V')$ if $U \inter V' \in \F'$.  Thus, $\I_{\sPl}(U,V|V')$. \eprf

Lemmas~\ref{NI1} and~\ref{NI2} show why noninteraction and
independence coincide for conditional probability defined from
unconditional probability, ranking
functions, and possibility measures using $\Poss(U||V)$.  Moreover, they
suggest why they do not coincide in general.
Since neither $\Poss(U|V)$ nor $\PlP$ satisfy Alg4$'$, it is perhaps not
surprising that in neither case does noninteraction imply conditional
independence. (We shall shortly see an example in the case of $\PlP$;
Fonck \citeyear{Fonck94} gives examples in the case of $\Poss(U|V)$.)
Indeed, noninteraction may not even imply conditional independence for
an arbitrary conditional probability measure, as the following example shows.
\xam Suppose that $W = \{a,b\}$, $\F = 2^W$, $\F' = \F -
\{\emptyset\}$, $\mu(a) = 1$, $\mu(b) = 0$, but
$\mu(b|b) = 1$.  It is easy to see that $\{b\}$ is not independent of
itself, but $\{b\}$ does not interact with $\{b\}$, since $\mu(b) =
\mu(b) \times \mu(b)$.  Nevertheless, it is not hard to check that this
conditional probability measure $\mu$ is algebraic and, in fact,
satisfies Alg4$'$.  However, it is not standard, since $\{b\} \in \F'$
although $\mu(b) = 0$. 
\exam


It is easy to see that the assumption of standardness is necessary in
Lemma~\ref{NI2}.  For suppose that  $(W,\F,\F',\Pl)$ is an arbitrary
nonstandard
algebraic cps for which $\top \ne \bot$.  Since $(W,\F,\F',\Pl)$ is
nonstandard, there must exist some $U
\in \F'$ such that $\Pl(U|W) = \bot$.  But then $$\bot =
\Pl(\emptyset|W) = \Pl(\emptyset|U)
\otimes \Pl(U|W) = \bot \otimes \bot.$$  Thus
$$\Pl(U|W) = \bot = \bot \otimes \bot = \Pl(U|W) \otimes \Pl(U|W),$$
so $\NIPl(U,U|W)$.  But $\Pl(U|U) = \top \ne \bot = \Pl(U)$, so
$\IPl(U,U|W)$ does not hold.

In general, Theorem~\ref{thm:alg} does not hold if we use $\NIPl$
rather than $I_{\sPl}$.  That is, Alg1--4 do not suffice to ensure that
CIRV1--4 hold for $\NIPl$.  Besides noninteraction, a number of
different approaches to defining independence for possibility measures
\cite{CH99a,CH99b,DCFP94,Fonck94} and for sets of probability measures
\cite{CH93,CM95,CMW99} have been considered.  In general,
Theorem~\ref{thm:alg} does not hold for them either. 
It is beyond the scope of this paper to
discuss and compare these approaches to that considered here, but it is
instructive to consider independence for sets of
probability measures in a little more detail, especially for the
representation $\PlP$.

%$I_{\sPlP}$ is very close to a notion called {\em type-1}
%independence considered by de Campos and Moral \citeyear{CM95}.  $U$
De Campos and Moral \citeyear{CM95} define what the call
{\em type-1} independence.   $U$ and
$V$ are {\em type-1 independent conditional on $V'$ with respect to
$\P$\/} if $U$ and $V$ are independent conditional on
$V'$ with respect to every $\mu \in \P$.  It is easy to check that
type-1 independence is equivalent to noninteraction in the context of
sets of probability measures.   Thus, by Lemma~\ref{NI1}, 
$I_{\sPlP}(U,V|V')$ implies that $U$ and $V$ are type-1 independent
conditional on $V'$ (and similarly for random variables).
However, the converse does not necessarily hold, because the two
approaches treat conditioning on events that have probability 0
according to some (but not all) of the measures in $\P$ differently.
To see this, consider an example discussed by de Campos and Moral.
Suppose a coin is known to be either double-headed or double-tailed and
is tossed twice.  This can be represented by $\P = \{\mu_0,\mu_1\}$,
where $\mu_0(hh) = 1$ and $\mu_0(ht) = \mu_0(th) = \mu_0(tt) = 0$, while
$\mu_1(tt) = 1$ and $\mu_1(ht) = \mu_1(th) = \mu_1(hh) = 0$.  Let $X_1$
and $X_2$ be
the random variables representing the outcome of the first and
second coin tosses, respectively.  Clearly there is a functional
dependence between $X_1$ and $X_2$, but it is easy to check that $X_1$
and $X_2$ are type-1 independent with respect to $\P$.
Moreover, noninteraction holds: $\NIPl(X_1=i,X_2=j)$ holds for
$i,j \in \{h,t\}$.  On the other
hand, $I_{\sPlP}(X_1,X_2)$ does not hold.  For example,
$f_{X_1=h}(1)
= 0$ while $f_{X_1=h|X_2=h}(1) = *$.%
\footnote{As Peter Walley [private communication, 2000] points out, this
example is somewhat  misleading.  The definition of independence with
respect to $\PlP$ produces the same counterintuitive behavior as type-1
independence if 
the probabilities are modified slightly so as to make them positive, 
i.e., when there is ``almost functional dependence'' between the two
variables. For example, suppose that the coin in the example is known to
either land heads with probability $.99$ or $.01$ (rather than 1 and 0,
as in the example).  Let $\mu_0'$ and $\mu_1'$ be the obvious
modifications of $\mu_0$ and $\mu_1$ required to represent this
situation, and let $\P' = \{\mu_0', \mu_1'\}$.  It is easy to check that
$X_1$ and $X_2$ continue to be type-1 independent, 
and noninteraction continues to hold, but now
$I_{\sPl_{\P'}}(X_1, X_2)$ also holds.  The real problem is that this
representation of uncertainty does not enable learning.}

The difference between noninteraction (i.e., type-1
independence) and the definition of independence used in this paper in
the context of sets of probability measures can be summarized as
follows.  $U$ and $V$ do not  interact with respect to $\P$ if $U$ and
$V$ are independent with respect to all measures $\mu \in \P$.  On the
other hand, $U$ and
$V$ are independent with respect to $\P$ if (1) $U$ and $V$ are independent
for all measures $\mu \in \P$ such that $\mu(U) > 0$ and $\mu(V) > 0$
and (2) $\mu(U) = 0$ iff $\mu(V) = 0$ for all $\mu \in \P$.  The definition 
of independence used here is thus more restrictive; it does not 
ignore the measures that give $U$ or $V$ probability 0 when
determining independence.  The difference between the two approaches
is illustrated in the example in the previous paragraph. 

As the variant of the example considered in 
Footnote 9 shows though, neither definition can completely claim to
represent the intuition that if $U$ is independent of $V$, then learning
$U$ gives no information about $V$.  If the coin in the example is known
to land heads with probability either .99 or .01, then seeing the first
coin toss land heads certainly seems to give information about the second coin
toss, even though both definitions would declare the events independent.
However, the definition of independence used here does have the advantage
of leading to an algebraic cps, which means, as is shown in the next
section, that using it leads to a representation of sets of probability
measures that can  be represented as a Bayesian network. 




\section{Bayesian Networks}\label{sec:bn}
Throughout this section,  I assume that we start
with a
set $W$ of possible worlds characterized by a
set $\X = \{X_1, \ldots, X_n\}$ of $n$ binary random variables.
That is, a world in  $W$ is a tuple
$(x_1, \ldots, x_n)$ with $x_i \in \{0,1\}$, and $X_i(x_1, \ldots, x_n)
= x_i$; that is, the value of $X_i$ in world $w = (x_1, \ldots, x_n) = w_i$.%
%That means that there are $2^n$ worlds in $W$, say $w_1, \ldots,
%w_{2^n}$.%
\footnote{The assumption that the random variables are binary is just for
ease of exposition.  It is easy to generalize the results to the case
where $\R(X_i)$ is finite for each $X_i$;  there is no need to
assume that $\R(X_i)$ is a subset of the reals.}
The goal of
this section is to show that many of the tools of Bayesian network
technology can be applied in this setting.  The proofs of the main
results all proceed in essentially the same spirit as well-known results
for probabilistic Bayesian networks (see \cite{GP88,GVP90,Verma86}).

\subsection{Qualitative Bayesian Networks}
As usual, a (qualitative)
{\em Bayesian network\/} (over $\X$) is a {\em dag}
whose nodes are labeled by variables in $\X$.  The
standard notion of a
Bayesian network representing a probability measure \cite{Pearl} can be
generalized in the obvious way to plausibility.

\dfn\label{BNdef1} Given a qualitative Bayesian network $G$,
let $\Par_G(X)$ be the
{\em parents\/} of the random variable $X$ in $G$;  let $\des_G(X)$ be
all the {\em descendants\/} of $X$, that is, $X$ and all those nodes $Y$
such that $X$ is an ancestor of $Y$; let $\nondes_G(X)$, the
{\em nondescendants of $X$\/}, consist of $\X - \des_G(X)$.  Note that
all ancestors of $X$ are nondescendants of $X$.
The Bayesian network $G$  {\em is
compatible with\/} the cps $(W,\F,\F',\Pl)$ (or just {\em compatible with
$\Pl$}, if the other components of the cps are clear from
context) if $\IrvPl(X,\nondes_G(X)|\Par(X))$, that is, if $X$ is conditionally
independent of its nondescendants given its parents, for all $X \in \X$.
\edfn

There is a standard way of constructing a Bayesian network that represents a
probability measure \cite{Pearl}.  I briefly review the construction
here, since it works without change for an algebraic cpm.  Given
an algebraic cpm $\Pl$, 
let $Y_1, \ldots, Y_n$ be a
permutation of the random variables in $\X$.
Construct a qualitative Bayesian network $G_{\sPl, \<Y_1, \ldots, Y_n\>}$
as follows: For each $k$, find a minimal
subset of $\{Y_1, \ldots, Y_{k-1}\}$, call it ${\bf P}_k$, such that
$\IrvPl(\{Y_1, \ldots, Y_{k-1}\}, Y_k| {\bf P}_k)$.
Then add edges
from each of the nodes in ${\bf P}_k$ to $Y_k$.
Verma \citeyear{Verma86} shows that this construction gives
a Bayesian network that is compatible with $\Pl$ in the case that $\Pl$ is a
probability measure;
his proof depends only on CIRV1--4.  Thus, the
construction works for algebraic cpms.

\thm\label{bnthm1}
$G_{\sPl,\<Y_1, \ldots, Y_n\>}$ is compatible with $\Pl$.  \ethm
%joe4
\prf  For ease of notation in the proof, I write $G$ instead of
$G_{\sPl,\<Y_1, \ldots, Y_n\>}$.
Note that $Y_1, \ldots, Y_n$
represents a topological sort of $G$; edges
always go
from nodes in $\{Y_1, \ldots, Y_{k-1}\}$ to $Y_k$.
It follows that $G$ is acyclic; \ie it is a dag.
The construction guarantees that
${\bf P}_k = \Par_G(Y_k)$ and that
$\IrvPl(\{Y_1, \ldots, Y_{k-1}\},Y_k|\Par_G(Y_k))$.  It follows from
results of \cite{Verma86} (and is not hard to verify directly) that
$\IrvPl(\nondes_G(Y_k),Y_k|\Par_G(Y_k))$ can be proved using only
CIRV1--4.  The result now follows from Theorem~\ref{thm:alg}.
\eprf

\subsection{Quantitative Bayesian Networks}
A qualitative Bayesian network $G$ gives qualitative information about
dependence and independence, but does not actually give the values of
the conditional plausibilities.  To provide the more quantitative
information, we associate with each node $X$ in $G$
a {\em conditional plausibility table (cpt)}
that quantifies the effects of the parents of $X$ on $X$.  A
cpt for $X$ gives, for each setting
of $X$'s parents in $G$, the plausibility that $X=0$ and $X=1$ given that
setting.  For example, if $X$'s parents in $G$ are $Y$ and $Z$, then the cpt
for $X$ would have an entry denoted $d_{X=i|Y=j \inter Z= k}$
for all $(i,j,k) \in \{0,1\}^3$.  As the notation is meant to suggest,
$d_{X=i|Y=j \inter Z= k}
= \Pl(X=i|Y=j \inter Z=k)$ for the plausibility measure $\Pl$
represented by $G$.%
\footnote{Of course, if the random variables are not binary, $i, j, k$
have to range over all possible values for the random variables.}
For each fixed $j$ and $k$, we assume that $x_{0jk} \oplus x_{1jk} =
\top$.
A {\em quantitative Bayesian network\/} is a pair $(G,f)$ consisting of
a qualitative Bayesian network $G$ and a function $f$ that
associates
with each node $X$ in $G$ a cpt for $X$.


\dfn A quantitative Bayesian network $(G,f)$ {\em represents\/} $\Pl$
%\in \PL$ 
if  $G$ is compatible with $\Pl$
and the cpts agree with $\Pl$, in the sense that, for each random
variable $X$, the entry $d_{X=i| Y_1 =
j_1, \ldots, Y_k = j_k}$ in the cpt is
$\Pl(X=i|Y_1 = j_1 \inter \ldots \inter Y_k = j_k)$ if
$Y_1 = j_1 \inter \ldots \inter Y_k = j_k \in \F'$.  (It does not
matter what $d_{X=i| Y_1 = j_1, \ldots, Y_k = j_k}$ is if
$Y_1 = j_1 \inter \ldots \inter Y_k = j _k \notin \F'$.)
\edfn

Given a cpm  $\Pl$, it is easy to construct a quantitative
Bayesian network $(G,f)$ that represents $\Pl$: simply construct $G$
that is compatible with $\Pl$ as in Theorem~\ref{bnthm1} and define $f$
appropriately, using $\Pl$.  The more interesting question is whether
there is a unique algebraic cpm determined by a quantitative
Bayesian network.  As stated, this question is somewhat undetermined.
The numbers in a quantitative network do not say what $\oplus$ and
$\otimes$ ought to be for the algebraic cpm.  

A reasonable way to make the question more interesting is the following.
Recall that, for the purposes of this section, I have taken $W$ to
consist of the $2^n$ worlds characterized by the $n$ binary random
variables in $\X$.  Let $\PL_{D,\oplus,\otimes}$ consist of 
all standard cps's of the form $(W,\F,\F',\Pl)$, where 
%endowed with $\oplus$ and $\otimes$ 
$\F = 2^W$, so that all subsets of $W$ are measurable, the range of
$\Pl$ is $D$,  and $\Pl$ is algebraic with respect to $\oplus$ and
$\otimes$.  Thus, for example, $\PL_{\IN^*,\min,+}$  consists of all
conditional ranking functions on $W$ defined from unconditional ranking
functions by the construction in Section~\ref{sec:cpm}.
Since a cps $(W,\F,\F',\Pl) \in \PL_{D,\oplus,\otimes}$ is determined by
$\Pl$, I often abuse notation and write $\Pl \in \PL_{D,\oplus,\otimes}$.

With this notation, the question becomes whether a quantitative Bayesian
network $(G,f)$ such that the entries in the cpts are in $D$ determines
a unique element in $\PL_{D,\oplus,\otimes}$.  As I now show, the answer
is yes, provided $(D,\oplus,\otimes)$ satisfies some conditions.
Characterizing the conditions on $(D,\oplus,\otimes)$ required for
this result turns out to be a little
subtle.   Indeed, it is somewhat surprising how many assumptions are
required to reproduce the simple arguments that are required in
the case of probability. 


%What properties of $\PL$ are required for it to hold more
%generally?
%That is, given a Popper algebra $\F \times \F'$ over $WS
%and a quantitative Bayesian network $(G,f)$, is there a unique
%cpm $\Pl$ such that $(G,f)$ quantatively represents
%$(W,\F,\F', \Pl)$.  Clearly we cannot  recover the plausibility of sets
%not in the algebra generated by sets of the form $X_i = x_i$, so I
%assume for the remainder of this section that $\F$ is the smallest algebra
%generated by sets of this form.
%The argument that a probability measure can be recovered from a
%quantative Bayesian network makes heavy use of the algebraic properties
%of probability.  In order to have any hope of recovering a plausibility
%measure from a quantitative Bayesian network in general, we will have to
%restrict attention to algebraic cps's.  That means that the values
%in the cpt that $f$ associates with a random variable $X$ must come from
%some domain $D$ which can be the domain of values for an algebraic cpm.
%In particular, this means that $D$ must be endowed with operations
%$\otimes$ and $\oplus$ that satisfy Alg3 and Alg4.  However, Alg3 and
%Alg4 are defined in terms of a particular plausibility measure $\Pl$.
%We need to be able to state analogues of Alg3 and Alg4 without having a
%specific plausibility measure in mind.  This motivates the following
%definition.

\dfn $(D,\oplus,\otimes)$ is a {\em BN-compatible domain (with respect to
$\PL_{D,\oplus,\otimes}$)\/} if there are
sets $D(\otimes) \subseteq D \times D$ and $D(\oplus) \subseteq D \union
D^2 \union D^3 \union \ldots$ satisfying the following properties:
\begin{itemize}
\item[BN1.] $\oplus$ and $\otimes$ are commutative and associative.
\item[BN2.] For all $d \in D$, $(\top,d), (\bot,d) \in D(\otimes)$,
$(\bot,d) \in D(\oplus)$, $\top \otimes d = d$, $\bot \otimes d = \bot$,
and $\bot \oplus d = d$.
\item[BN3.] $\otimes$ distributes over $\oplus$; more precisely,
$a \otimes (b_1 \oplus \cdots \oplus b_n) = (a \otimes b_1) \oplus
\cdots \oplus (a \otimes b_n)$
if $(a,b_1), \ldots , (a,b_n), (a,b_1 \oplus \cdots \oplus  b_n)
\in D(\otimes)$ and $(b_1, \ldots, b_n), (a \otimes b_1, \ldots, a
\otimes b_n) \in D(\oplus)$; moreover, $(a_1 \oplus \cdots \oplus a_n) \otimes b = a_1 \otimes b \oplus \cdots
\oplus a_n \otimes b$ if $(a_1, \ldots, a_n), (a_1
\otimes b, \ldots, a_n \otimes b) \in
\D(\oplus)$ and $(a_1 \oplus \cdots \oplus a_n, b), (a_1, b), \ldots,
(a_n,b)  \in D(\otimes)$.
\item[BN4.] If $(a,c), (b,c) \in D(\otimes)$,  $a\otimes c \le b \otimes
c$, and $c \ne \bot$, then $a \le b$.
\item[BN5.] If
%$d_i \le d$ for $i = 1, \ldots, k$,
$(d_1, \ldots, d_k) \in D(\oplus)$ and $d_1 \oplus \cdots \oplus d_k \le
d$, then there exists $(d_1', \ldots, d_k') \in D(\oplus)$
such that $(d_1',d), \ldots, (d_k',d), (d_1' \oplus \cdots \oplus
d_k',d) \in D(\otimes)$, $d_i = d_i' \otimes d$, for $i
= 1, \ldots, k$, and $d_1 \oplus \cdots d_k = (d_1' \oplus \cdots \oplus
d_k')
\otimes d$.
\item[BN6.] $D(\oplus)$ is closed under permutations and prefixes, so
that if $(x_1, \ldots, x_k) \in D(\oplus)$ and $\pi$ is a permutation of
$(1, \ldots, k)$, then $(x_{\pi(1)}, \ldots, x_{\pi(k)}) \in D(\oplus)$
and if $k' \le k$, then $(x_1, \ldots, x_{k'}) \in D(\oplus)$; moreover
$D(\oplus) \supseteq D$.
\item[BN7.] If $(d_1, \ldots, d_k), (d'_1, \ldots, d'_m) \in D(\oplus)$,
$(d_i, d'_j) \in D(\otimes)$ for $i = 1, \ldots, k$, $j = 1, \ldots, m$,
then $(d_1 \otimes d'_1, \ldots, d_1 \otimes d'_m, \ldots, d_k \otimes
d'_1, \ldots, d_k \otimes d'_m) \in D(\oplus)$.
\item[BN8.] If $(d_1, \ldots, d_k) \in D(\oplus)$ and $k' \le k$,  then
$d_1 \oplus \cdots \oplus d_{k'} \le d_1
\oplus \cdots \oplus d_k$.
\end{itemize}
\end{definition}
Note that all the representations of uncertainty we have considered so
far have associated with them BN-compatible domains.  Indeed, the
definitions of $D(\oplus)$, $D(\otimes)$, $\oplus$, and $\otimes$ in
each case are given in the proof of Proposition~\ref{algebraicpl}.
For example, for $\PL_{[0,1],\max,\min}$, the set of conditional possibility
measures determined by unconditional possibility measures,
$D(\oplus) = [0,1] \times [0,1]$, while $D(\otimes)$ consists of all
pairs $(a,b) \in [0,1] \times [0,1]$ such that $a < b$ or $a=1$.
I leave it to the reader to check that, in all these cases,
BN1--8 hold.

Given a tuple ${\bf x} = (x_1, \ldots, x_n) \in [0,1]^n$, let $d_{X_i,G,
{\bf x}}$ denote the value $d_{X_i = x_i|\Par_G(X_i) = {\bf y}}$, where
${\bf y}$ is the restriction of ${\bf x}$ to the variables in $\Par_G(X_i)$.

\dfn If $(D,\oplus,\otimes)$ is BN-compatible, then a quantitative
Bayesian network $(G,f)$ is {\em $(D,\oplus,\otimes)$-representable\/}
if  the values of the cpts for $G$ lie in $D$
and the following properties hold:
\begin{itemize}
\item[R1.] For every node $X$ in $G$ and every setting {\bf y} of
$\Par_G(X)$, $(d_{X=0|\Par_G(X) = {\bf y}}, d_{X=1|\Par_G(X) = {\bf y}})
\in \Dom(\oplus)$ and
$$d_{X=0|\Par_G(X) = {\bf y}} \oplus d_{X=1|\Par_G(X) = {\bf
y}} = \top.$$
\item[R2.] Suppose $Y_1, \ldots, Y_n$ is a topological sort of the nodes
in $G$.  Then
for all ${\bf y} \in \{0,1\}^n$ and all $1 \le j < k \le n$,
$(d_{Y_j,G, {\bf y}}, d_{Y_{j+1},G,{\bf y}} \otimes \cdots \otimes
d_{Y_k,G,{\bf y}}) \in D(\otimes)$ and $(d_{Y_j,G, {\bf y}} \otimes
\cdots \otimes
d_{Y_{k-1},G,{\bf y}}, d_{Y_k,G,{\bf y}}) \in D(\otimes)$.
\end{itemize}
\end{definition}

R1 is the obvious analogue of the requirement in the probabilistic case
that the entries of the cpt for $X$, for a fixed setting of $X$'s
parents, add up to 1.  R2 essentially says that certain terms
%joenew: minor chagngs: ``essentially'' + )
(the ones required to compute the plausibility of ${\bf Y}
= {\bf y}$ for ${\bf Y} = \<Y_1, \ldots, Y_n\>$) are required to be in
$D(\otimes)$, so that it makes sense to take their product.  Since
$D(\otimes) = [0,1] \times [0,1]$ in the case of probability, there is
no need to make this requirement explicit.  However, it is necessary for
other representations of uncertainty.

%\dfn An quantitative Bayesian network $(G,f)$ {\em represents an
%algebraic cpm\/} if all the elements in the cpts $f(X)$, $X \in \X$,
%are in some algebraic domain and for each random variable $X \in \X$, we
%have $\sum_{x \in \R(X)}

The following result shows that, as the name suggests, there is a unique
cpm that represents a representable quantitative Bayesian network. 

\thm\label{thm:uniqrep}  If $(G,f)$ is $(D,\oplus,\otimes)$-representable,
then there is a unique cpm $\Pl \in \PL_{D,\oplus,\otimes}$ such that
$(G,f)$ represents  $\Pl$. \ethm

\subsection{D-Separation}
Just as in the case of probability, conditional independencies
can be read off the Bayesian network using the criterion of d-separation
\cite{Pearl}.  Recall that a set ${\bf X}$ of nodes in $G = (V,E)$,
is {\em d-separated\/} from a set
 ${\bf Y}$ of nodes by a set ${\bf Z}$ of nodes in $G$, written
$\dsep_G({\bf X},{\bf Y}|{\bf Z})$,  if, for every $X \in
 {\bf X}$, $Y \in {\bf Y}$, and a {\em trail\/}
from $X$ to $Y$ (that is, a sequence $(X_0,
\ldots, X_k)$ of nodes in $G$ such that $X_0 = X$, $X_k = Y$ and either
$(X_i,X_{i+1})$ or $(X_{i+1},X_i)$ is a directed edge in $G$) and
a node $X_i$ on the trail with $0 < i < k$ such that either:
\begin{itemize}
\item[(a)] $X_i \in {\bf Z}$ and there is an arrow leading into $X_i$ and
an arrow leading out (i.e., either $(X_{i-1},X_i), (X_i,X_{i+1}) \in E$
or $(X_i,X_{i-1}), (X_{i+1},X_i) \in E$
\item[(b)] $X_i \in {\bf Z}$ and $X_i$ is a tail-to-tail node (i.e.,
$(X_{i},X_{i-1}), (X_{i},X_{i+1}) \in E$)
\item[(c)] $X_i$ is a head to head node (i.e., $(X_{i-1},X_i),
(X_{i+1},X_i) \in E$), and neither $X_i$ nor any of its descendants are
in ${\bf Z}$. 
\end{itemize}
%{\bf X} is d-separated from {\bf Y} by {\bf Z} in $G$, written
%$\dsep_G({\bf X}, {\bf Y}| {\bf Z})$, if every node $X$ in
%${\bf X}$ is d-separated from every node $Y$ in {\bf Y} by {\bf Z}.

Let $\Sigma_{G,\sPl}$ consist of all statements of the form
$\IrvPl(X,\nondes_G(X)|\Par_G(X))$.  Let $\PL_{D,\oplus,\otimes}$ be an arbitrary
collection of cps's of the form $(W,\F,\F',\Pl)$ where all components
other than $\Pl$ are fixed, and the plausibility measures $\Pl$ all have
the same range $D$ of plausibility values.
Consider the following three statements:
\begin{enumerate}
\item $\dsep_G({\bf X}, {\bf Y}| {\bf Z})$.
\item $\IrvPl({\bf X}, {\bf Y}| {\bf Z})$ is provable from CIRV1--4 and
$\Sigma_{G,\sPl}$.
\item $\IrvPl({\bf X}, {\bf Y}| {\bf Z})$ holds for every plausibility
measure in $\PL_{D,\oplus,\otimes}$ compatible with $G$.
\end{enumerate}

The implication from 1 to 2 is proved in \cite{GVP90,Verma86}.

\thm\label{thm:PV} {\rm \cite{GVP90,Verma86}}
If $\dsep_G({\bf X}, {\bf Y}| {\bf Z})$, then
$\IrvPl({\bf X}, {\bf Y}| {\bf Z})$ is provable from CIRV1--4 and
$\Sigma_{G,\sPl}$.
\ethm

It is immediate from  Theorem~\ref{thm:alg} that the
implication from 2 to 3 holds for algebraic cpms.
\cor\label{thmbn2}
If $\IrvPl({\bf X}, {\bf Y}| {\bf Z})$ is provable from CIRV1--4 and
$\Sigma_{G,\sPl}$, then
$\IrvPl({\bf X}, {\bf Y}| {\bf Z})$ holds for every algebraic cpm
 $\Pl$ compatible with $G$.
\ecor

Finally,
the implication from 3 to 1 for probability measures is proved in
\cite{GP88,GVP90}.   Here I generalize the proof to algebraic
plausibility measures.  Notice
that to prove the implication from 3 to 1, it suffices to show that
if $X$ is not d-separated from $Y$ by {\bf Z} in $G$, then there is a
plausibility measure $\Pl \in \PL_{D,\oplus,\otimes}$ such that $\IrvPl(X,Y|{\bf Z})$ does
not hold.  To guarantee that such a plausibility measure exists in
$\PL_{D,\oplus,\otimes}$, we have to ensure that there are ``enough'' plausibility measures
in $\PL_{D,\oplus,\otimes}$ in the following technical sense.

\dfn
A BN-compatible domain $(D,\oplus,\otimes)$ is {\em rich\/} if there
exist $d, d' \in D$ such that (1) $(d,d') \in D(\oplus)$, (2) $d \oplus
d' = \top$ and (3) if $x =
x_1 \otimes \ldots \otimes x_k$, where each $x_i$ is either $d$ or $d'$
and $k < n$, then $(d,x)$, $(x,d)$, $(d',x)$, and $(x,d')$ are all in
$D(\otimes)$ (intuitively, $D(\otimes)$ contains all products involving $d$
and $d'$ of length at most $n$). \edfn
All the domains for the cps's we have considered are easily seen to be
rich.

\thm\label{thm:GP} Suppose that plausibility measures in
$\PL_{D,\oplus,\otimes}$ take values in a rich BN-compatible domain.
Then if 
$\IrvPl({\bf X}, {\bf Y}| {\bf Z})$ holds for every plausibility
measure in $\PL_{D,\oplus,\otimes}$ compatible with $G$, then
$\dsep_G({\bf X}, {\bf Y}| {\bf Z})$.  \ethm

I remark that independence and d-separation for  various approaches to
representing sets of probability measures using Bayesian networks are
discussed by Cozman \citeyear{Cozman00,Cozman00a}.
However, the technical details are quite different from the approach
taken here. 

\section{Conclusion}\label{sec:conc}
I have considered a general notion of conditional plausibility that
generalizes all other standard notions of conditioning in the
literature, and examined various requirements that could be imposed on
conditional plausibility.  One set of requirements, those that
lead to algebraic cps's, was shown to suffice
for the construction of Bayesian networks.  
Further assuming that the range $D$ of the plausibility measure is
a BN-compatible domain suffices for all the more quantitative properties
of Bayesian networks to hold and for d-separation to characterize
the independencies. 
It should also be clear that
standard constructions like belief propagation in Bayesian networks
\cite{Pearl} can also be applied to algebraic cps's with ranges that are
BN-compatible, since they typically use only basic properties of
conditioning, addition, and 
multiplication, all of which hold in BN-compatible domains (using $\oplus$ and
$\otimes$).  In particular, these results apply to sets to probability
measures, provided that they are appropriately represented as
plausibility measures.  The particular representation of sets of
probability measures advocated in this paper was also shown to have a
number of other attractive properties.

The results of this paper show that Alg1--4 are {\em sufficient\/}
conditions for representing a measure of uncertainty that is acceptable
as a Bayesian network.  They may not be necessary.  It would be
interesting to see if other natural conditions also suffice.  Similarly,
I have focused only on {\em acceptable\/} cps's, that is, ones that
satisfy Acc1--4.  Acc3 and Acc4 are nontrivial conditions; it would be
of interest to see to what extent they could be weakened while still
being able to prove results in the spirit of this paper.  I leave these
questions to future research.


\appendix

\section{Proofs}\label{proofs}
In this section I give the proofs of Theorems~\ref{thm:alg},
\ref{thm:uniqrep}, and~\ref{thm:GP}.
I repeat the statement of the results  for the convenience of the reader.

\lem\label{lem1}
Suppose that $(W,\F,\F',\Pl)$ is a cps,
$A_1, \ldots, A_n$ is a partition of $W$,
$X, A_1, \ldots,
A_n \in \F$, and $Y \in \F'$.  Then
%$(\Pl(X|A_i \inter Y),\Pl(A_i|Y)) \in \Dom(\otimes)$,
%$(\Pl(X \inter A_i |Y),\Pl(X \inter A_j |Y)) \in \Dom(\oplus)$, and
$$\Pl(X|Y) = \oplus_{\{i: A_i \inter Y \in \F'\}} \Pl(X|A_i \inter Y)
\otimes \Pl(A_i|Y).%
\footnote{Notice that if $A_i \inter Y \in \F'$, then $\Pl(X|A_i \inter Y)
\otimes \Pl(A_i|Y) = \Pl(X \inter A_i | Y)$ by Alg2.    Thus, the terms
arising on the right-hand side of the equation in Lemma~\ref{lem1} are
in $\Dom(\oplus)$.  This means that there is no
need to put in parentheses; $\oplus$ is associative on terms in
$\Dom(\oplus)$.}$$
\elem
\prf Using an easy induction argument, it follows from Alg1
that $$\Pl(X|Y) = \oplus_{i=1}^n \Pl(X \inter A_i|Y).$$
If $A_i \inter Y \notin \F'$, then it follows from Acc4
that $\Pl(A_i|Y) = \bot$.  Thus, by CPl3, $\Pl(X \inter A_i|Y) = \bot$.
Using Lemma~\ref{lem0.5}, it follows that
$$\Pl(X|Y) = \oplus_{\{i: A_i \inter Y \in \F'\}} \Pl(X \inter
A_i|Y).$$
If $A_i \inter Y \in \F'$, then it follows from Alg2
that $\Pl(X \inter A_i|Y) = \Pl(X|A_i \inter Y) \otimes
\Pl(A_i|Y)$.  Thus,
$$\Pl(X|Y) = \oplus_{\{i: A_i \inter Y \in \F'\}} \Pl(X|A_i \inter Y)
\otimes \Pl(A_i|Y),$$
as desired. \eprf

\bigskip

\othm{thm:alg} CIRV1--4 hold for all algebraic cps's.
\eothm

\medskip

\prf
CIRV1 is immediate from the fact that independence is symmetric.

For CIRV2, suppose that
$\IrvPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf Z})$.
We must show $\IrvPl({\bf X},{\bf Y}|{\bf Z})$.
That is, we must show that $\IPl({\bf X = x}, {\bf Y = y}|{\bf Z
=z})$, for all ${\bf x}$, ${\bf y}$,
and ${\bf z}$.   This requires showing two things.
\begin{enumerate}
\item[2(a).] If ${\bf X = x} \inter {\bf Z = z} \in \F'$, then
%\begin{equation}\label{eq3}
$$\Pl({\bf Y = y} | {\bf X = x} \inter {\bf Z = z}) =
\Pl({\bf Y = y} | {\bf Z = z}).
$$
\item[2(b).] If ${\bf Y = y} \inter {\bf Z = z} \in \F'$, then
%\begin{equation}\label{eq4}
$$\Pl({\bf X = x} | {\bf Y = y} \inter {\bf Z = z}) =
\Pl({\bf X = x} | {\bf Z = z}).$$
%\end{equation}
\end{enumerate}
For 2(a), suppose that $\Pl({\bf X = x} \inter {\bf Z = z}) \in \F'$.
From
$\IPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf Z})$, it follows that
$\IPl({\bf X = x}, {\bf Y = y} \inter {\bf Y' = y'}|{\bf Z = z})$ for
all ${\bf y}'$.  Hence
\begin{eqnarray}\label{eq1}
\Pl({\bf Y = y} \inter {\bf Y' = y'}| {\bf X = x}
\inter {\bf Z = z}) &=
&\Pl({\bf Y = y} \inter {\bf Y' = y'}| {\bf Z = z})
\end{eqnarray}
for all ${\bf y'} \in \R({\bf Y'})$.
From (\ref{eq1}) it follows that
$$\oplus_{{\bf y}'} \Pl({\bf Y = y} \inter {\bf Y' = y'}| {\bf X = x}
\inter {\bf Z = z}) =
\oplus_{{\bf y}'} \Pl({\bf Y = y} \inter {\bf Y' = y'}| {\bf Z = z}).$$
Thus,
$$\Pl(\union_{{\bf y}'} {\bf Y = y} \inter {\bf Y' = y'}| {\bf X = x}
\inter {\bf Z = z}) =
\Pl(\union_{{\bf y}'} {\bf Y = y} \inter {\bf Y' = y'}| {\bf Z = z}).$$
Since $\union_{{\bf y}'} ({\bf Y = y} \inter {\bf Y' = y'}) = {\bf Y =
y}$, 2(a) holds.

For 2(b),
%it follows from Lemma~\ref{lem1} that
%\begin{equation}\label{eq5}
%\begin{array}{l}
%\Pl({\bf X = x} | {\bf Y = y} \inter {\bf Z = z}) = \\
%\oplus_{\{{\bf
%y'}:
%{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}} \Pl({\bf
%X = x}|{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z}) \otimes
%\Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z = z}).
%\end{array}
%\end{equation}
from $\IrvPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf Z})$, it follows that if
${\bf Y = y} \inter {\bf Y' = y'}\inter {\bf Z = z} \in \F'$, then
\begin{eqnarray}\label{eq2}
\Pl({\bf X = x} | {\bf Y = y} \inter {\bf Y' = y'}\inter {\bf Z = z}) &=
&\Pl({\bf X = x}| {\bf Z = z}).
\end{eqnarray}

From (\ref{eq2}) and Lemma~\ref{lem1}, it follows that
\begin{equation}\label{eq6}
\begin{array}{ll}
&\Pl({\bf X = x} | {\bf Y = y} \inter {\bf Z = z}) \\
= &\oplus_{\{{\bf
y'}:
{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}} \Pl({\bf
X = x} | {\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z}) \otimes \Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z
= z})\\
= &\oplus_{\{{\bf
y'}:
{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}} \Pl({\bf
X = x}|{\bf Z = z}) \otimes \Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z
= z}).
%= &\Pl({\bf X = x}|{\bf Z = z}) \otimes (\oplus_{
%\{{\bf y'}:
%{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}}
%\Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z = z})).
\end{array}
\end{equation}

By Acc4, it follows that if $
{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \notin \F'$, then
$\Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z = z}) = \bot$.  Thus, by
Lemma~\ref{lem0.5}, Alg1, CPl2, and CPl4,
\begin{equation}\label{eq6.5}
\begin{array}{ll}
&\oplus_{ \{{\bf y'}:
{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}}
\Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z = z}) \\
= &
\oplus_{{\bf y'}} \Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z = z})\\
= &\Pl(W| {\bf Y = y} \inter {\bf Z = z}) \\
= &\top.
\end{array}
\end{equation}


The next step is to apply distributivity (Alg3) to the last line of
(\ref{eq6}).  To do this, we must show that certain tuples are
in $\Dom(\oplus)$ and $\Dom(\otimes)$, respectively.
Since $$(\Pl({\bf X = x} | {\bf Y = y} \inter {\bf Y' = y'}\inter {\bf Z
= z}), \Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z
= z}) \in \Dom(\otimes),$$ from (\ref{eq2}) it follows that $$(\Pl({\bf
X = x}|{\bf Z = z}), \Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z
= z})) \in \Dom(\otimes).$$  If $\{{\bf y}'_{i_1}, \ldots, {\bf
y}'_{i_k}\} = \{{\bf y}' \in \R({\bf Y'}):
{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}$, then
clearly $$(\Pl({\bf Y' = y}'_{i_1}|{\bf Y = y} \inter {\bf Z = z}),
\ldots,
\Pl({\bf Y' = y}'_{i_k}|{\bf Y = y} \inter {\bf Z = z}) \in
\Dom(\oplus).$$  Moreover, using (\ref{eq2}) again and Alg2, it follows
that
$$\Pl({\bf X=x}| {\bf Z = z}) \otimes \Pl({\bf Y' = y}'_{i_k}|{\bf Y =
y}
\inter {\bf Z = z}) = \Pl({\bf X = x} \inter {\bf Y' = y}'_{i_k}|{\bf Y =
y} \inter {\bf Z = z}).$$
 Thus, $(\Pl({\bf X = x}| {\bf Z = z})
\otimes \Pl({\bf Y' = y}'_{i_1}|{\bf Y
= y} \inter {\bf Z = z}), \ldots, \Pl({\bf X = x}| {\bf Z = z})
\otimes \Pl({\bf Y' = y}'_{i_k}|{\bf Y = y}
\inter {\bf Z = z}) \in \Dom(\oplus)$.  Finally, since (\ref{eq6.5})
shows that $\oplus_{ \{{\bf y'}:
{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}} = \top$
and, by the proof of Lemma~\ref{lem0.7}, $(d,\top) \in \Dom(\otimes)$ for
all $d \in \Range(\Pl)$, it follows that
$$(\Pl({\bf X}|{\bf Z = z}), \oplus_{\{{\bf y'}:
{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}}
\Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z = z}))  \in \Dom(\otimes).$$
It now follows, using Alg3, (\ref{eq6.5}), and Lemma~\ref{lem0.7}, that
$$\begin{array}{ll}
&\oplus_{\{{\bf
y'}:
{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}} \Pl({\bf
X = x}|{\bf Z = z}) \otimes \Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z
= z})\\
= &\Pl({\bf X = x}|{\bf Z = z}) \otimes (\oplus_{
\{{\bf y'}:
{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'\}}
\Pl({\bf Y' = y'}|{\bf Y = y} \inter {\bf Z = z}))\\
= &\Pl({\bf X = x}|{\bf Z = z}) \otimes \top\\
= &\Pl({\bf X = x}|{\bf Z = z}).
\end{array}$$
Thus, from (\ref{eq6}), it follows that $\Pl({\bf X = x}|{\bf Y = y}
\inter {\bf Z = z}) = \Pl({\bf X = x}|{\bf Z = z})$.
This completes the
proof of 2(b) and CIRV2.

For CIRV3, suppose that
$\IrvPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf Z})$.  We must show that
$\IrvPl({\bf X},{\bf Y}|{\bf Y}' \union {\bf Z})$.  This again requires
showing two things:
\begin{enumerate}
\item[3(a).] If ${\bf X = x} \inter {\bf Y' = y'} \inter {\bf Z =
z} \in \F'$, then
%\begin{equation}\label{eq7}
$$\Pl({\bf Y = y} | {\bf X = x} \inter {\bf Y' = y'} \inter {\bf Z = z}) =
\Pl({\bf Y = y} | {\bf Y' = y'} \inter {\bf Z = z}).$$
%\end{equation}
\item[3(b).] If ${\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z}
\in \F'$, then
%\begin{equation}\label{eq8}
$$\Pl({\bf X = x} | {\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z}) =
\Pl({\bf X = x} | {\bf Y' = y'} \inter {\bf Z = z}).$$
%\end{equation}
\end{enumerate}

For 3(a), suppose that ${\bf X = x} \inter {\bf Y' = y'} \inter {\bf Z
= z} \in \F'$.  Thus, by Acc3, ${\bf X = x} \inter {\bf Z = z} \in
\F'$.   Since
$\IrvPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf Z})$, it follows that
\begin{equation}\label{eq9}
\Pl({\bf Y = y''} \inter {\bf Y' = y'}| {\bf X = x} \inter {\bf Z = z})
=
\Pl({\bf Y = y''} \inter {\bf Y' = y'}| {\bf Z = z})
\end{equation}
for all ${\bf y}'' \in \R({\bf Y})$.
%Applying Lemma~\ref{lem0} to the special case of (\ref{eq9}) with ${\bf
%Y = y}$, get we that
Applying Alg2 to each side of (\ref{eq9}), it follows that
$$\begin{array}{ll}
&\Pl({\bf Y = y}| {\bf Y' = y'} \inter {\bf X = x} \inter {\bf Z = z})
\otimes \Pl({\bf Y' = y'}| {\bf X = x} \inter {\bf Z = z})\\
= &\Pl({\bf Y = y}| {\bf Y' = y'} \inter {\bf Z = z})
\otimes \Pl({\bf Y' = y'}| {\bf Z = z}).
\end{array}
$$
Thus, to prove 3(a), it follows from Alg4 that it suffices to show that
$$\Pl({\bf Y' = y'}| {\bf X = x} \inter {\bf Z = z}) =
\Pl({\bf Y' = y'}| {\bf Z = z}) \ne \bot.$$
%\end{equation}
But by (\ref{eq9}) and Alg1, it follows that
$$\begin{array}{ll}
&\Pl({\bf Y' = y'}| {\bf X = x} \inter {\bf Z = z}) \\
= &\oplus_{{\bf y''}\in \R({\bf Y})}
\Pl({\bf Y = y''} \inter {\bf Y' = y'}| {\bf X = x} \inter {\bf Z = z})\\
=
&\oplus_{{\bf y''}\in \R({\bf Y})}
\Pl({\bf Y = y''} \inter {\bf Y' = y'}| {\bf Z = z}) \\
= &\Pl({\bf Y' = y'}| {\bf Z = z}),
\end{array}$$
as desired.  Moreover, since ${\bf X = x} \inter {\bf Y' = y'} \inter
{\bf Z = z} \in \F'$, it follows from Acc4 that
$\Pl({\bf Y' = y'}| {\bf Z = z}) \ne \bot$.

For 3(b), suppose that
${\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'$.
Since $\IrvPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf Z})$, it follows that
$$
\Pl({\bf X = x} | {\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z}) =
\Pl({\bf X = x} | {\bf Z = z}).
$$
Thus, to prove 3(b), it suffices to show that
\begin{equation}\label{eq11}
\Pl({\bf X = x} | {\bf Y' = y'} \inter {\bf Z = z}) =
\Pl({\bf X = x} | {\bf Z = z}).
\end{equation}
Recall that we are assuming that
$\IrvPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf Z})$.
By CIRV2, it follows that
$\IrvPl({\bf X},{\bf Y}'|{\bf Z})$.  Thus, (\ref{eq11}) is immediate
from 2(b)
(since ${\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in
\F'$ implies that
${\bf Y' = y'} \inter {\bf Z = z} \in \F'$).

Finally, consider CIRV4.  Suppose that
$\IrvPl({\bf X},{\bf Y}|{\bf Z})$ and
$\IrvPl({\bf X}, {\bf Y}'| {\bf Y} \union {\bf Z})$.  We must show that
$\IrvPl({\bf X},{\bf Y} \union {\bf Y}'|{\bf Z})$.
As usual, this requires showing two things:
\begin{enumerate}
\item[4(a).] If ${\bf Y=y} \inter {\bf Y' = y'} \inter {\bf Z =
z} \in \F'$, then
%\begin{equation}\label{eq12}
$$\Pl({\bf X=x} | {\bf Y=y} \inter {\bf Y' = y'} \inter {\bf Z = z}) =
\Pl({\bf X=x} | {\bf Z = z}).$$
%\end{equation}
\item[4(b).] If ${\bf X = x} \inter {\bf Z = z} \in \F'$, then
%\begin{equation}\label{eq13}
$$\Pl({\bf Y = y} \inter {\bf Y' = y'}| {\bf X = x} \inter {\bf Z = z}) =
\Pl({\bf Y =y}\inter {\bf Y' = y'} | {\bf Z = z}).$$
%\end{equation}
\end{enumerate}

Both 4(a) and 4(b) are straightforward.  For 4(a), suppose that
${\bf Y=y} \inter {\bf Y' = y'} \inter {\bf Z = z} \in \F'$.  Since
$\IrvPl({\bf X},{\bf Y'}|{\bf Y} \union {\bf Z})$, it follows that
$$\Pl({\bf X = x}|{\bf Y = y} \inter {\bf Y' = y'} \inter {\bf Z = z}) =
\Pl({\bf X = x}|{\bf Y = y} \inter {\bf Z = z}).$$  And since $\IrvPl({\bf
X},{\bf Y}|{\bf Z})$, it follows that
$$\Pl({\bf X = x}|{\bf Y = y} \inter {\bf Z = z}) = \Pl({\bf X=x}|{\bf
Z=z}).$$  Thus we have 4(a).

For 4(b), suppose that ${\bf X = x} \inter {\bf Z = z} \in \F'$.
There are now two cases to consider.  If $\Pl({\bf Y = y}|{\bf X = x}
\inter {\bf Z = z}) \ne \bot$ then, by Acc4, ${\bf X = x} \inter {\bf Y
= y} \inter {\bf Z = z} \in \F'$.  Moreover, by Alg2,
\begin{equation}\label{eq14}
\Pl({\bf Y = y} \inter {\bf Y' = y'}| {\bf X = x} \inter {\bf Z = z})
=
\Pl({\bf Y' = y'}| {\bf X = x} \inter {\bf Y = y} \inter {\bf Z = z})
\otimes \Pl({\bf Y = y}|{\bf X = x} \inter {\bf Z = z}).
\end{equation}
Since $\IrvPl({\bf X}, {\bf Y}'| {\bf Y} \union {\bf Z})$, it follows
that
$$\Pl({\bf Y' = y'}| {\bf X = x} \inter {\bf Y = y} \inter {\bf Z = z}) =
\Pl({\bf Y' = y'}| {\bf Y = y} \inter {\bf Z = z}).$$  And since
$\IrvPl({\bf X}, {\bf Y}| {\bf Z})$, it follows that
$\Pl({\bf Y = y}|{\bf X = x} \inter {\bf Z = z}) = \Pl({\bf Y = y}|{\bf
Z = z})$.  Plugging this into (\ref{eq14}) and applying Alg2 again gives
$$\begin{array}{ll}
&\Pl({\bf Y = y} \inter {\bf Y' = y'}| {\bf X = x} \inter {\bf Z = z})\\
= &
\Pl({\bf Y' = y'}| {\bf Y = y} \inter {\bf Z = z})
\otimes \Pl({\bf Y = y}| {\bf Z = z})\\ 
= &\Pl({\bf Y = y} \inter {\bf Y' =
y'}|{\bf Z = z}),
\end{array}$$
as desired.

Now if $\Pl({\bf Y = y}|{\bf X = x} \inter {\bf Z = z}) = \bot$, then by
CPl3, it follows that
$\Pl({\bf Y = y} \inter {\bf Y' = y'}| {\bf X = x} \inter {\bf Z = z}) =
\bot$.  Moreover, since $\IrvPl({\bf X},{\bf Y}|{\bf Z})$, it follows that
$\Pl({\bf Y = y}| {\bf Z = z}) = \bot$.  Applying CPl3, we get that
$\Pl({\bf Y = y} \inter {\bf Y' = y'}| {\bf Z = z}) = \bot$.
Thus, again 4(b) holds.
\eprf

\bigskip

\othm{thm:uniqrep} If $(G,f)$ is $(D,\oplus,\otimes)$-representable 
then there is a unique cpm $\Pl \in \PL_{D,\oplus,\otimes}$ such that
$(G,f)$ represents  $\Pl$. \eothm

\medskip



\prf Given $(G,f)$, suppose without loss of generality that ${\bf X} = \<X_1,
\ldots, X_n\>$ is a topological sort of the nodes in $G$.
I now define the
plausibility measure $\Pl$ determined by $(G,f)$.  I start by defining
$\Pl_{(G,f)}$ on sets of the form ${\bf X} = {\bf x}$.

It easily follows from Alg2 that if $\Pl \in \PL_{D,\oplus,\otimes}$ and
$\Pl(X_1 = x_1 \inter  \ldots \inter X_{n-1} = x_{n-1}) \ne \bot$, then
\begin{equation}\label{bneq1}
\begin{array}{rcl}
\Pl({\bf X} = {\bf x}) &=
&\Pl(X_n = x_n | X_1 = x_1 \inter  \ldots \inter X_{n-1} = x_{n-1})
\otimes\\
&&\ \ \ \Pl(X_{n-1} = x_{n-1} | X_1 =
x_1 \inter  \ldots \inter X_{n-2} = x_{n-2}) \otimes\\
&&\mbox{ \ \ \ \ \ } \cdots \otimes \Pl(X_2= x_2|X_1=x_1) \otimes
\Pl(X_1=x_1).
\end{array}
\end{equation}
Thus, an algebraic plausibility measure satisfies an analogue of the
chain rule for probability.
(Since $\otimes$ in $D$ is assumed to be associative, no parentheses are
required here.  However, even without this assumption, it
follows easily from Alg2 that $\otimes$ is in fact associative on tuples
$(a,b,c)$ of the form  $(\Pl(U_1|U_2),\Pl(U_2|U_3),\Pl(U_3|U_4))$, where $U_1
\subseteq U_2 \subseteq U_3 \subseteq  U_4$, which
are the only types of tuples that arise in (\ref{bneq1}).  Associativity
will be more of an issue below.)

If $\Pl$ is compatible with $G$, then in fact
\begin{equation}\label{bneq2}
\begin{array}{rcl}
\Pl({\bf X} = {\bf x}) &=
&\Pl(X_n = x_n | \inter_{X_j \in \Par_G(X_n)} X_j = x_j) \otimes\\
&& \ \ \ \Pl(X_{n-1} = x_{n-1} | \inter_{X_j \in \Par_G(X_n-1)} X_j =
x_j)  \otimes\\
&&\mbox{ \ \ \ \ \ } \cdots \otimes (X_1=x_1).
\end{array}\end{equation}
(If $\Par_G(X_k) = \emptyset$, then $\Pl(X_k = x_k | \inter_{X_j \in
\Par_G(X_k)} X_j = x_j)$ is just taken to be $\Pl(X_k = x_k)$.)

It is clear from (\ref{bneq2})
that $\Pl_{(G,f)}({\bf X} = {\bf x})$ must be
$d_{X_n,G,{\bf x}} \otimes \cdots \otimes d_{X_1,G,{\bf x}}$.

Note that every subset of $W$ can be written as a disjoint
union of events of the form ${\bf X} = {\bf x}$.  Thus, if $U \in \F$,
define $$\Pl_{(G,f)}(U) = \oplus_{\{{\bf x}: {\bf X} = {\bf x} \subseteq U\}}
d_{X_n,G,{\bf x}} \otimes \cdots \otimes d_{X_1,G,{\bf x}}.$$

For conditional plausibilities, suppose that $\Pl_{(G,f)}(V) \ne \bot$,
so that $V \in \F'$.  Let $\{{\bf x}_1, \ldots, {\bf x}_k\} = \{{\bf x}:
{\bf X} = {\bf x} \subseteq V\}$.  It
follows easily from BN6, BN7, R1, and R2 that 
$(\Pl_{(G,f)}({\bf X} = {\bf x}_1), \ldots, \Pl_{(G,f)}({\bf X} = {\bf
x}_k)) \in D(\oplus)$.
Thus, by BN8, if ${\bf X} = {\bf x} \subseteq V$, then
$\Pl_{(G,f)}({\bf X} = {\bf x}) \le \Pl_{(G,f)}(V)$.  By BN5, for each
$j$, there exists 
$d_{{\bf X} = {\bf x}_j|V}$ such that $$(d_{{\bf X} = {\bf
x}_j|V},\Pl_{(G,f)}(V)) \in 
D(\otimes) \mbox{ and } d_{{\bf X} = {\bf x}_j|V} \otimes
\Pl_{(G,f)}(V) = \Pl_{(G,f)}({\bf X} = {\bf x});$$ it follows from BN4 that
$d_{{\bf X} = {\bf x}_j|V}$ is the unique element in $D$ with this property.
Moreover, by BN5, $(d_{{\bf X} = {\bf x}_1|V}, \ldots, d_{{\bf X} = {\bf
x}_k|V}) \in 
D(\oplus)$.   Define $\Pl_{(G,f)}(U|V) = \oplus_{\{{\bf x}: {\bf X} = {\bf x}
\subseteq U \inter V\}} d_{{\bf X} = {\bf x}|V}$ (where
$\Pl_{(G,f)}(\emptyset|V)$ is taken 
to be $\bot$).  Note for future reference that it follows from BN5
that $(\Pl_{(G,f)}(U|V),\Pl_{(G,f)}(V)) \in D(\otimes)$ and
\begin{equation}\label{bneq3}
\Pl_{(G,f)}(U|V) \otimes \Pl_{(G,f)}(V) = \Pl_{(G,f)}(U\inter V).
\end{equation}


%joenew: cut (U|V)
This completes the definition of $\Pl_{(G,f)}$.  It remains to
%joenew: algebraic cpm
check that it is an algebraic cpm that is represented by
$(G,f)$.  Thus, we must check that Alg1--4 and CPl1--4 hold.  Alg1 is
immediate from the definitions and BN1 and BN2 (BN2 is necessary for
the case that one of the disjoint sets is empty); Alg3 is immediate from
BN3 and Alg4 is immediate from BN4.  For Alg2, 
note that if $\Pl_{(G,f)}(V) \ne \bot$
and $\Pl_{(G,f)}(V') \ne \bot$ then, by (\ref{bneq3}),
$\Pl_{(G,f)}(U \inter V|V') \otimes \Pl_{(G,f)}(V') = \Pl_{(G,f)}(U
\inter V \inter V')$ and 
$$\begin{array}{ll}
&(\Pl_{(G,f})(U |V \inter V') \otimes \Pl_{(G,f)}(V|V')) \otimes
\Pl_{(G,f)}(V') \\
= &\Pl_{(G,f})(U|V \inter V') \otimes (\Pl_{(G,f)}(V|V') \otimes
\Pl_{(G,f)}(V')) \\
= &\Pl_{(G,f)}(U|V\inter V') \otimes \Pl_{(G,f)}(V
\inter V') \\
= &\Pl_{(G,f)}(U \inter V \inter V').
\end{array}$$
(Note that the associativity of $\otimes$ is being used here.)  Thus, by
BN4, $$\Pl_{(G,f)}(U \inter V|V') = \Pl_{(G,f})(U |V \inter V') \otimes
\Pl_{(G,f)}(V|V').$$

CPl1 is immediate by definition (the empty sum is taken to be
$\bot$).  For CPl2, note that by (\ref{bneq3}), $\Pl_{(G,f)}(W|V)
\otimes \Pl_{(G,f)}(V) = \Pl_{(G,f)}(V)$.  Since $\top \otimes
\Pl_{(G,f)}(V) = \Pl_{(G,f)}(V)$ by BN2, it follows from BN4 that
$\Pl_{(G,f)}(W|V) = \top$.   CPl3 follows readily from the definitions
together with BN1, BN6, and BN7.  CPl4 also follows by definition.

Next we must show that $(G,f)$ represents $\Pl_{(G,f)}$.
The first step is to show that $\Pl_{(G,f)}(X=x|\Par_G(X) = {\bf z}) =
d_{X=x|\Par_G(X) = {\bf z}}$.  Note that by (\ref{bneq3}),
$$\Pl_{(G,f)}(X=x|\Par_G(X) = {\bf z}) \otimes \Pl_{(G,f)}(\Par_G(X) =
{\bf z}) = \Pl_{(G,f)}(X=x \inter\Par_G(X) = {\bf z}).$$
By definition, $$\Pl_{(G,f)}(X = x \inter \Par_G(X)= {\bf z}) =
\oplus_{\{{\bf x}: {\bf X} = {\bf x}' \subseteq (X = x \inter \Par_G(X)=
\vec{y})\}} 
\Pl_{(G,f)}({\bf X} = {\bf x}').$$  
Each term in the ``sum'' on
the right is the ``product'' of terms; indeed, the sum is over all
possible products that include $d_{X=y|\Par_G(X) = {\bf z}}$ as one of
the terms and a 
term $d_{Y=y|\Par_G(Y) = {\bf z}'}$ for each $Y \in \Par_G(X)$, where
$y$ is the component of ${\bf z}$ corresponding to $Y$.
By using BN1, BN3, R1, and R2, 
it is not hard to show that
\begin{equation}\label{bneq4.5}
\begin{array}{ll}
&\Pl_{(G,f)}(X=y \inter\Par_G(X) = {\bf z})\\
= &\oplus_{\{{\bf }: {\bf X} = {\bf x}' \subseteq (X = x \inter
\Par_G(X)= \vec{y})} 
\Pl_{(G,f)}({\bf X} = {\bf x}')\\
= &d_{X=x|\Par_G = {\bf z}} \otimes \Pl_{(G,f)}(\Par_G(X) =
{\bf z}).\end{array} 
\end{equation}
It now follows from BN4 that $\Pl_{(G,f)}(X=x|\Par_G(X)= {\bf z}) =
d_{X=x|\Par_G(X) = {\bf z}}$.


To show that  $\Pl_{(G,f)}(X=x|\nondes_G(X) =
\vec{y} \inter \Par_G(X)= {\bf z}) = d_{X=x|\Par_G(X) = {\bf z}}$, it
suffices to 
show that
\begin{equation}\label{bneq4}
\begin{array}{ll}
&\Pl_{(G,f)}(X=x \inter \nondes_G(X) =
\vec{y} \inter \Par_G(X)= {\bf z}) \\
=  &d_{X=x|\Par_G(X) = {\bf z}}
\otimes \Pl_{(G,f)}(\nondes_G(X) = \vec{y} \inter \Par_G(X)= {\bf z}),
\end{array}
\end{equation}
for then the result
follows by BN5.  (\ref{bneq4}) can be shown much like (\ref{bneq4.5}),
but now the commutativity of $\otimes$ (BN1) is essential.  That is, the
expressions for $\Pl_{(G,f)}(X=x \inter \nondes_G(X) = \vec{y} \inter
\Par_G(X)= {\bf z})$ and $  d_{X=x|\Par_G(X) = {\bf z}} \otimes
\Pl_{(G,f)}(\nondes_G(X) = \vec{y} \inter \Par_G(X)= {\bf z}) $ involve the
same terms,
but not necessarily in the same order.  With commutativity, they can be
permuted so that they are in the same order.

Similar arguments, which I leave to the reader, show that
$\Pl_{(G,f)}(\nondes_G(X) = \vec{y}|X =x  \inter \Par_G(X)= {\bf z}) =
\Pl_{(G,f)}(\nondes_G(X) = \vec{y}|\Par_G(X)= {\bf z})$.  Thus, $(G,f)$
represents $\Pl_{(G,f)}$.
\eprf

\bigskip

\othm{thm:GP} Suppose that $(D,\oplus,\otimes)$ is a rich BN-compatible
domain.  Then if
$\IrvPl({\bf X}, {\bf Y}| {\bf Z})$ holds for every plausibility
measure in $\PL_{D,\oplus,\otimes}$ compatible with $G$, then
$\dsep_G({\bf X}, {\bf Y}| {\bf Z})$.  \eothm

\prf Suppose that {\bf X} is not d-separated from {\bf Y} by {\bf Z} in
$G$.  Then there is some $X \in {\bf X}$ and $Y\in {\bf Y}$ such that
$X$ is not d-separated from Y by {\bf Z} in $G$.  I construct a
cpm in $\Pl \in \PL_{D,\oplus,\otimes}$ such that $\IrvPl(X,Y|{\bf Z})$ does
not hold, using the techniques of \cite{GVP90}.

As shown in \cite[Lemma~9]{GVP90}, if $X$ is not d-separated from $Y$ in
$G$, there exists a subgraph $G'$ of $G$ such that
\begin{enumerate}
\item $G'$ includes all the nodes in $G$ but only a subset of the edges
in $G$,
\item $X$ is not d-separated from $Y$ by $Z$ in $G'$.
\item the edges $E'$ in $G'$ consist only of those specified below:
\begin{enumerate}
\item a {\em trail\/} $q$ from $X$ to $Y$,
\item for every head-to-head node $X_i$ on the trail $q$, there is a
directed path $p_i$ in $G'$ to a node in ${\bf Z}$; moreover, the paths $p_i$
do not share any nodes and the only node that $p_i$ shares with $q$ is $X_i$.
\end{enumerate}
\end{enumerate}

Note that every node in $G'$ has either 0, 1, or 2 parents in $G'$.
Let $(G',f)$ be a quantitative Bayesian network such that for each
node in $X$ in $G'$ with no parents in $G'$, the cpt $f(X)$ is such
that $d_{X=0} = d$ and $d_{X=1} = d'$.
If a node $X$ in $G'$ has one parent, say $X'$,
then the cpt $f(X)$ is such that 
$d_{X=i|X'=j}$  is $\top$ if $i = j$ and $\bot$ if $i \ne j$.
Finally, if $X$ has two parents, say $X'$ and $X''$,
the cpt $f(X)$ is such that $d_{X=k|X'=i \inter X''=k}$ is $\top$ if $k = i
\oplus j (\bmod 2)$ and is $\bot$ otherwise.  Since $d \oplus d' =
\top$ and BN2 guarantees that $\top \oplus \bot = \top$, the
construction satisfies R1.  The richness of $D$ guarantees that R2
holds.  By Theorem~\ref{thm:uniqrep}, there is a (unique) plausibility
measure in $\Pl \in \PL_{D,\oplus,\otimes}$ that is represented by  $(G',f)$.  It is easy to
check that $\Pl$ is compatible with $G$ as well.  There are three cases
to consider:
\begin{itemize}
\item Suppose that $X$ has no parents in $G'$. Then it is easy to see
that $\IrvPl(X,{\bf Y}|{\bf Z})$ for all {\bf Y} and {\bf Z} (and, in
particular, if ${\bf Y} = \nondes_G(X)$ and ${\bf Z} = \Par_G(X)$).
\item Suppose that $X$ has one parent in $G'$, say $X'$.  Then it is
easy to see that $\IrvPl(X,{\bf Y}|{\bf Z})$ holds for all {\bf Y} and
{\bf Z} such that $X' \in {\bf Z}$.  Since $X'$ is a parent of $X$ in
$G$, again $\IrvPl(X,\nondes_G(X)|\Par_G(X))$ must hold.
\item Finally, if $X$ has two parents in $G'$, say $X'$ and $X''$, then
it is easy to see that $\IrvPl(X,{\bf Y}|{\bf Z})$ holds for all {\bf Y} and
{\bf Z} such that $\{X',X''\} \subseteq {\bf Z}$.  Since $X'$ and $X''$ are
parents of $X$ in $G$, again $\IrvPl(X,\nondes_G(X)|\Par_G(X))$ must
hold.  \eprf
\end{itemize}


\acks{A preliminary version of this paper
appears in {\em Uncertainty in Artificial Intelligence, Proceedings of
the Sixteenth Conference}, 2000.
I thank Seraf{\' \i}n Moral, Fabio Cozman, Peter Walley, and the
anonymous referees of both the UAI and journal version of the paper
for very useful
comments.  This work was supported in part by the NSF, under grants
IRI-96-25901 and IIS-0090145.}

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