% -*-latex-*-
\documentclass[fleqn,11pt,twoside]{article}
\usepackage{hyperlatex}
\usepackage{dpstandard,myjair}
\usepackage[round,dcucite]{harvard}
\usepackage{url}
\W\usepackage{frames}

\T\jairheading{18}{2003}{263-313}{08/02}{04/03}
\T\firstpageno{263}

%\T\ShortHeadings{Exploiting contextual independence in probabilistic
%\T inference}{D. Poole and N. L. Zhang}
\T\ShortHeadings{E{{\scriptsize XPLOITING} C{\scriptsize
\T ONTEXTUAL} I{\scriptsize NDEPENDENCE} I{\scriptsize N}
\T P{\scriptsize ROBABILISTIC} I{\scriptsize
\T NFERENCE}}}{P{\scriptsize OOLE \& } Z{\scriptsize HANG}} 

\htmltitle{Exploiting Contextual Independence In Probabilistic Inference}
\htmladdress{\xlink{David Poole}{http://www.cs.ubc.ca/spider/poole/}
  and \xlink{Nevin Lianwen
    Zhang}{http://www.cs.ust.hk/~lzhang/},Exploiting Contextual
  Independence In Probabilistic Inference, \xlink{Journal of
    Artificial Intelligence Research}{http://www.jair.org/}, 18, 2003, 263-313. }
\xmlattributes{table}{border}
\setcounter{htmlautomenu}{2}

\W\newcommand{\citeasnoun}{\cite}
\W\newcommand{\in}{ in }
\W\newcommand{\boldmath}{}
\W\newcommand{\tuple}[1]{<#1>}
\W\newcommand{\dots}{...}
\W\newcommand{\wedge}{\&}
\W\newcommand{\bigwedge}{\&}
\W\newcommand{\AND}{\&}
\W\newtheorem{definition}[theorem]{Definition}
\W\newcommand{\subseteq}{ subset }
\W\newenvironment{eqnarray}{\[\begin{array}{rcl}}{\end{array}\]}
\W\newenvironment{eqnarray*}{\[\begin{array}{rcl}}{\end{array}\]}
\W\newcommand{\nonumber}{}
\W\newcommand{\ensuremath}{}
\W\newcommand{\includegraphics}[2][{}]{\htmlimage{#2.gif}}
\W\newcommand{\hfill}{   }
\W\newcommand{\lefteqn}{}
\W\newenvironment{pcode}{\begin{tabbing}
\W xxxxx\=xxxxx\=xxxxx\=xxxxx\=
\W xxxxx\=xxxxx\=xxxxx\=xxxxx\=
\W xxxxx\=xxxxx\=\kill}{\end{tabbing}}
\W\newcommand{\otimes}{\xmlent{times}}
\W\newcommand{\oplus}{+}
\W\newcommand{\cap}{ intersect }
\W\newcommand{\cup}{ union }
\W\newcommand{\bigcup}{ union }
\W\newcommand{\head}{}
\W\newcommand{\left}[1]{}
\W\newcommand{\right}[1]{}
\W\newcommand{\propto}{\verb|~|}
\W\newcommand{\displaystyle}{}
\W\renewcommand{\harvarditem}[4][]{\bibitem{#4}}
\W\newcommand{\harvardand}{\&}
\W\newcommand{\harvardyearleft}{[}
\W\newcommand{\harvardyearright}{]}
\W\newcommand{\'}{}
\W\newcommand{\name}{\Large}
\W\newcommand{\email}{      \normalsize}
\W\newcommand{\addr}{}
\W\newcommand{\pcodecomm}[1]{\{{\em #1}\}}
\W\newcommand{\url}[1]{\xlink{#1}{#1}}

\newcommand{\prub}{,}
\newcommand{\rool}[1]{\langle #1\rangle}
\T\newcommand{\roolb}[1]{\left< #1\right>}
\W\newcommand{\roolb}[1]{<#1>}
\newcommand{\hrool}[1]{\head{\langle #1\rangle}}
\newcommand{\hroolb}[1]{\head{\left< #1\right>}}
\newcommand{\hfactor}[1]{\head{#1}}
\newcommand{\vset}[1]{\mbox{\boldmath$#1$}}
\newcommand{\ttimes}{\ensuremath{\otimes_t}}
\newcommand{\tplus}{\ensuremath{\oplus_t}}
\T\newcommand{\notsubseteq}{\not\subseteq}
\W\newcommand{\notsubseteq}{\mbox{ is not a subset of }}

\newcommand{\genrool}{confactor}%{generalised rule}
\newcommand{\Genrool}{Confactor}%{Generalised rule}

\newtheorem{theorem}{Theorem} 
\newtheorem{myexampleem}{Example}
\newenvironment{myexample}{\begin{myexampleem}\em}{\end{myexampleem}}
%\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Proposition}
\newtheorem{proposition}[theorem]{Proposition}
\W\newcommand{\stuple}[1]{<#1>}

%\newcommand{\captn}[1]{\hrulefill \caption{#1} \hrulefill}
\newcommand{\captn}[1]{\caption{#1}}
\W\renewcommand{\negn}{\verb|~|}
\T\renewcommand{\negn}{\overline}
\newcommand{\F}{\mbox{{\boldmath$F$}}}
\renewcommand{\P}{\mbox{{\boldmath$P$}}}
\newcommand{\ev}{\mbox{{\boldmath$E$}}}
\newenvironment{proof}{\par\noindent {\bf Proof:}}{Q.E.D.\par}
\title{Exploiting Contextual Independence In Probabilistic Inference}

\author{{\name David Poole \email poole@cs.ubc.ca\\
        \addr Department of Computer Science,\\
        University of British Columbia,\\
        2366 Main Mall,
        Vancouver, B.C., Canada V6T 1Z4\\
\T        {\tt http://www.cs.ubc.ca/spider/}
\W        \url{http://www.cs.ubc.ca/spider/poole/}\\
\T \ANDAUTHOR
%\W\\\\
\name  Nevin Lianwen Zhang \email lzhang@cs.ust.hk\\
\addr Department of Computer Science,\\
Hong Kong University of Science and Technology,
Hong Kong,\\
\T {\tt http://www.cs.ust.hk/\~{}lzhang/}
\W \url{http://www.cs.ust.hk/\~{}lzhang/}
}}


\begin{document}

\maketitle
\W\xlink{Journal of Artificial Intelligence
\W  Research}{http://www.jair.org/}, 18, 263-313, 2003.
\begin{abstract}

Bayesian belief networks have grown to prominence because they provide
compact representations for many problems for which probabilistic
inference is appropriate, and there are algorithms to exploit this
compactness. The next step is to allow compact representations of the
conditional probabilities of a variable given its parents. In this
paper we present such a representation that exploits contextual
independence in terms of \emph{parent contexts}; which variables act
as parents may depend on the value of other variables. The internal
representation is in terms of contextual factors (\emph{{\genrool}s})
that is simply a pair of a context and a table.  The algorithm,
\emph{contextual variable elimination}, is based on the standard variable
elimination algorithm that eliminates the non-query variables in turn,
but when eliminating a variable, the tables that need to be
multiplied can depend on the context. This algorithm reduces to
standard variable elimination when there is no contextual independence
structure to exploit. We show how this can be much more efficient than
variable elimination when there is structure to exploit. We explain
why this new method can exploit more structure than previous methods
for structured belief network inference and an analogous algorithm
that uses trees.
\end{abstract}
\section{Introduction}
Probabilistic inference is important for many applications in
diagnosis, perception, user modelling, and anywhere there is
uncertainty about the state of the world from
observations. Unfortunately general probabilistic inference is
difficult both computationally and in terms of the number of
probabilities that need to be specified.  Belief (Bayesian) networks
\cite{Pearl88a} are a representation of independence amongst random
variables. They are of interest because the independence is useful in
many domains, they allow for compact representations for many
practical problems, and there are algorithms to exploit the compact
representations. Note that even approximate inference is
computationally difficult in the worst case \cite{DagLub93a}.

Recently there has been work to extend belief networks by allowing
more structured representations of the conditional probability of a
variable given its parents \cite{D'Ambrosio95a}. This has been in
terms of either causal independencies \cite{HecBre94a,ZhaPoo96a},
parametric forms such as sigmoidal Bayesian networks
\cite{Neal92a,SauJaaJor96a}, or by exploiting contextual
independencies inherent in stating the conditional probabilities in
terms of rules \cite{Poole93g} or trees
\cite{SmiHolMat93a,BouFriGolKol96a}.  In this paper we show how an
algorithm that exploits conditional independence for efficient
inference in belief networks can be extended to also exploit
contextual independence. \citeasnoun{Poole97a} provides an earlier,
less efficient, version in terms of rules. \citeasnoun{ZhaPoo99a}
give an abstract mathematical analysis of how contextual independence
can be exploited in inference.

Section \ref{sec:background} introduces belief networks and an
algorithm, variable elimination (VE) \cite{ZhaPoo94a} or Bucket
Elimination for belief assessment \cite{Dechter96a}, for computing
posterior probabilities in belief that is based on nonlinear dynamic
programming \cite{BerBri72b}. Section \ref{ci-secn} presents a
representation for conditional probabilities that lets us state
contextual independence in terms of \emph{{\genrool}s}. Section
\ref{sec:rule-VE} shows how the VE algorithm can be extended to
exploit the contextual independence in {\genrool}s. Section
\ref{hybrid} shows how we can improve efficiency by reducing the
amount of splitting.  Section
\ref{emp-res} gives some empirical results on standard and random
networks. The details of the experiments are given in Appendix \ref{app:experiment}. Section \ref{sec:comparisons} gives comparisons
to other proposals for exploiting contextual independencies. Section
\ref{conclusion} presents conclusions and future work.

\section{Background}\label{sec:background}
In this section we present belief networks and an algorithm, variable elimination, to compute
the posterior probability of a set of query variables given some evidence.

\subsection{Belief Networks}
%\subsection{Random Variables}
We treat random variables as primitive. We use upper case letters to
denote random variables. The domain of a random variable $X$, written
$dom(X)$, is a set of values. If $X$ is a random variable and $v\in
dom(X)$, we write $X{=}v$ to mean the proposition that $X$ has value
$v$. The function $dom$ can be extended to tuples of variables. We
write tuples of variables in upper-case bold font. If $\vset{X}$ is a
tuple of variables, $\tuple{X_1,\dots,X_k}$, then $dom(\vset{X})$ is
the cross product of the domains of the variables. We write
$\tuple{X_1,\dots,X_k}=\tuple{v_1,\dots,v_k}$ as
$X_1=v_1\wedge\dots\wedge X_k=v_k$. This is called an instantiation of
$\vset{X}$.  For this paper we assume there is a finite number of
random variables, and that each domain is finite.

We start with a total ordering $X_1,\ldots,X_n$ of the
random variables. 
\begin{definition}
The {\bf parents} of random variable $X_i$, written $\pi_{X_i}$, are a
minimal\footnote{If there is more than one minimal set, any minimal set
can be chosen to be the parents. There is more than one minimal set
only when some of the predecessors  are deterministic functions of
others.} set of the predecessors of $X_i$ in the total ordering such
that the other predecessors of $X_i$ are independent of $X_i$ given
$\pi_{X_i}$. That is $\pi_{X_i} \subseteq \{X_1,\ldots,X_{i-1}\}$ such
that
%$X$ is independent of
%$\{X_1,\ldots,X_{i-1}\}-\pi_{X_i}$ given $\pi_{X_i}$. In particular,
$P(X_i|X_{i-1}\ldots X_1) = P(X_i|\pi_{X_i})$.
%\[P(X_i|X_{i-1}\ldots X_1) = P(X_i|\pi_{X_i})\]
\end{definition}

A {\bf belief network} \cite{Pearl88a} is an acyclic directed graph, where
the
nodes are random variables\footnote{Some people like to say the nodes
are \emph{labelled} with random variables. In the definition of a graph, the
set of nodes can be any set, in particular, they can be a set of random
variables. The set of arcs is a set of ordered
pairs of random variables.}. We use the terms node and random
variable interchangeably. There is an arc from each element of
$\pi_{X_i}$ into $X_i$.
Associated with the belief network is a set of probabilities
of the form $P(X|\pi_X)$, the conditional probability of each variable
given its parents (this includes the prior probabilities of those
variables with no parents).

By the chain rule for conjunctions and the independence assumption:
\begin{eqnarray}
P(X_1,\ldots,X_n) & = & \prod_{i = 1}^n P(X_i|X_{i-1}\ldots X_1) \nonumber\\
& = &  \prod_{i = 1}^n P(X_i|\pi_{X_i}) \label{joint-def}
\end{eqnarray}
This factorization of the joint probability distribution is often
given as the formal definition of a belief network.
\begin{figure}
\begin{center}
\includegraphics[]%[width=\columnwidth]
{str-bn}\hfill
 %\end{center}
%\begin{center}
\begin{tabular}[b]{|llll|l|}\hline
$A$ & $B$ & $C$ & $D$ & $P(e|ABCD)$\\\hline
$a$ & $b$ & $c$ & $d$ & $0.55 $\\
$a$ & $b$ & $c$ & $\negn d$ & $0.55 $\\
$a$ & $b$ & $\negn c$ & $d$ & $0.55 $\\
$a$ & $b$ & $\negn c$ & $\negn d$ & $0.55 $\\
$a$ & $\negn b$ & $c$ & $d$ & $0.3 $\\
$a$ & $\negn b$ & $c$ & $\negn d$ & $0.3 $\\
$a$ & $\negn b$ & $\negn c$ & $d$ & $0.3 $\\
$a$ & $\negn b$ & $\negn c$ & $\negn d$ & $0.3 $\\
$\negn a$ & $b$ & $c$ & $d$ & $0.08 $\\
$\negn a$ & $b$ & $c$ & $\negn d$ & $0.08 $\\
$\negn a$ & $b$ & $\negn c$ & $d$ & $0.025 $\\
$\negn a$ & $b$ & $\negn c$ & $\negn d$ & $0.5 $\\
$\negn a$ & $\negn b$ & $c$ & $d$ & $0.08 $\\
$\negn a$ & $\negn b$ & $c$ & $\negn d$ & $0.08 $\\
$\negn a$ & $\negn b$ & $\negn c$ & $d$ & $0.85 $\\
$\negn a$ & $\negn b$ & $\negn c$ & $\negn d$ & $0.5 $\\\hline
\end{tabular}
\end{center}
\captn{A simple belief network and a conditional
probability table for $E$.} \label{str-bn}
\end{figure}
\begin{myexample}\label{simple-factorization}
Consider the belief network of Figure \ref{str-bn}.
This represents a factorization of the joint probability distribution:
\begin{eqnarray*}
\lefteqn{P(A,B,C,D,E,Y,Z)}\\
& = &P(E|ABCD) P(A|YZ) P(B|YZ)% \\&&
P(C|YZ) P(D|YZ) P(Y) P(Z)
\end{eqnarray*}
If the variables are binary\footnote{In this and subsequent examples, we assume that variables
are Boolean (i.e., with domain $\{true,false\}$). If $X$ is a
variable, $X{=}true$ is written as $x$ and $X{=}false$ is written as
$\negn x$, and similarly for other variables. The theory and the
implementations are not restricted to binary variables.}, the first term, $P(E|ABCD)$, requires the
probability of $E$ for all 16 cases of assignments of values to
$A,B,C,D$. One such table is given in Figure \ref{str-bn}.
\end{myexample}

\subsection{Belief Network Inference}\label{VE-algo}
The task of probabilistic inference is to determine the posterior
probability of a variable or variables given some observations.  In
this section we outline a simple algorithm for belief net inference
called variable elimination (VE) \cite{ZhaPoo94a,ZhaPoo96a} or bucket elimination for belief
assessment (BEBA) \cite{Dechter96a}, that is based on the ideas of
nonlinear dynamic programming
\cite{BerBri72b}\footnote{\citeasnoun{BerBri72b} give essentially the
same algorithm, but for the optimization problem of finding a minimization
of sums. In VE, we use the algorithm for finding the sum of
products. VE is named because of the links to the algorithm of
\citeasnoun{BerBri72b}; they refer to their basic algorithm as
\emph{The elimination of variables one by one}, which is exactly what
we do. \citeasnoun{BerBri72b} also describe good elimination ordering
heuristics and refinements such as
eliminating variables in blocks and forms of conditioning which we
don't consider here.

The only difference between VE and BEBA is that BEBA requires an a
priori elimination ordering (and exploits the prior ordering for efficiency), whereas the VE allows for dynamic
selection of which variable to eliminate next.} and is
closely related to SPI \cite{ShaD'ADel90a}.
This is a query oriented algorithm that exploits the conditional
independence inherent in the network structure for
efficient inference, similar to how clique tree propagation exploits
the structure
\cite{LauSpi88a,JenLauOle90a}.

Suppose we observe variables $E_1,\dots,E_s$ have corresponding values
$o_1\dots o_s$. We want to determine the posterior probability of
variable $X$, the \emph{query variable}, given evidence $E_1{=}o_1
\AND\ldots\AND E_s{=}o_s$:
%\begin{eqnarray*}
%\lefteqn{
\[
P(X|E_1{=}o_1 \AND\ldots\AND E_s{=}o_s)%} \\
 = \frac{P(X \AND E_1{=}o_1 \AND\ldots\AND
E_s{=}o_s)}{P(E_1{=}o_1 \AND\ldots\AND E_s{=}o_s)}
\]
%\end{eqnarray*}
The denominator, $P(E_1{=}o_1 \AND\ldots\AND E_s{=}o_s)$, is a normalizing
factor:
\[ P(E_1{=}o_1 \AND\ldots\AND E_s{=}o_s) = \sum_{v \in dom(X)} P(X{=}v
\AND E_1{=}o_1 \AND\ldots\AND E_s{=}o_s)\]
The problem of probabilistic inference can thus be reduced to
the problem of computing the probability of conjunctions.  

Let
$\vset{Y} = \{Y_1,\ldots,Y_k\}$ be the non-query, non-observed variables (i.e.,
$\vset{Y} = \{X_1,\ldots,X_n\}-\{X\}-\{E_1,\ldots,E_s\}$).
To compute the marginal
distribution, we sum out the $Y_i$'s:
\begin{eqnarray*}
\lefteqn{P(X\AND E_1{=}o_1 \AND\ldots\AND E_s{=}o_s)}\\
& = & \sum_{Y_k}\cdots \sum_{Y_1} P(X_1,\ldots,X_n)_{\{E_1{=}o_1
\AND\ldots\AND E_s{=}o_s\}}\\ 
& = & \sum_{Y_k}\cdots \sum_{Y_1} \prod_{i = 1}^n
P(X_i|\pi_{X_i})_{\{E_1{=}o_1 \AND\ldots\AND E_s{=}o_s\}} 
\end{eqnarray*}
where the subscripted probabilities mean that the associated variables
are assigned the corresponding values.

Thus probabilistic inference reduces to the problem of summing out
variables from a product of functions. To solve this efficiently we
use the distribution law that we learned in high school: to compute a
sum of products such as
$xy+xz$ efficiently, we distribute out the common factors (which here
is $x$) which results in $x(y+z)$. This is the essence of the VE algorithm. We
call the elements multiplied together ``factors'' because of the use
of the term in mathematics. Initially the factors represent the
conditional probability tables, but the intermediate factors are just
functions on variables that are created by adding and multiplying factors.

A {\bf factor} on variables $V_1,\dots,V_d$ is a representation of a
function from $dom(V_1) \times \dots \times dom(V_d)$ into the real
numbers. 

Suppose that the $Y_i$'s are ordered according to some elimination
ordering.  We sum out the variables one at at time.

To sum out a variable $Y_i$
from a product, we distribute all of the factors that don't involve
$Y_i$ out of the sum.  Suppose $f_1,\ldots,f_k$ are some
functions of the variables that are multiplied together (initially
these are the conditional probabilities), then
\[\sum_{Y_i} f_1\ldots f_k = f_1\ldots f_m \sum_{Y_i} f_{m+1}\ldots f_k\]
where $f_1\ldots f_m$ are those functions that don't involve
$Y_i$, and $f_{m+1}\ldots f_k$ are those that do involve $Y_i$. We
explicitly construct a representation for the new function
$\sum_{Y_i} f_{m+1}\ldots f_k$, and continue summing out the remaining
variables. After all the $Y_i$'s have been summed out, the result is
a function on $X$ that is proportional to $X$'s posterior
distribution.

\begin{figure}
\begin{pcode}
\bf To compute \boldmath$P(X|E_1{=}o_1 \AND\ldots\AND E_s{=}o_s)$ \\
%\>\>\bf given elimination ordering \boldmath$ Y_1,\ldots,Y_k$:\\
\>Let {\F} be the factors obtained from the original conditional probabilities.\\
\>1.\>Replace each $f\in\F$ that involves some $E_i$ with $f_{\{E_1{=}o_1 ,\ldots, E_s{=}o_s\}}$.\\
%\>2.\>For $i = 1..k$ \\
%\>\>\>Set $\F = eliminate(Y_i,\F)$.\\
\>2.\>While there is a factor involving a non-query variable\\
\>\>\>Select non-query variable $Y$ to eliminate\\
\>\>\>Set $\F = eliminate(Y,\F)$.\\
\>3.\>Return $renormalize(\F)$
\end{pcode}

\begin{pcode}
{\bf Procedure} \boldmath$eliminate(Y,\F)$:\\
\>Partition {\F} into \\
\>\>\>$\{f_1,\ldots, f_m\}$ that don't contain $Y$ and\\
\>\>\>$\{f_{m+1},\ldots, f_r\}$ that do contain $Y$\\
\>Compute $f = \sum_Y f_{m+1}\ttimes \ldots\ttimes f_r$\\
\>Return $\{f_1,\ldots ,f_m,f\}$
\end{pcode}

\begin{pcode}
{\bf Procedure} \boldmath$renormalize(\{f_1,\dots,f_r\})$:\\
\>Compute $f = f_1\ttimes \ldots\ttimes f_r$\\
\>Compute $c = \sum_X f$\>\>\>\>\>\>\>\% $c$ is normalizing constant\\
\>Return $f/c$\>\>\>\>\>\>\>\% divide each element of $f$ by $c$
\end{pcode}

\captn{The tabular VE algorithm}
\label{trad-VE}
\end{figure}
In the tabular implementation of the VE algorithm (Figure
\ref{trad-VE}), a function of $d$ discrete variables $V_1,\dots,V_d$,
is represented as a $d$-dimensional table (which can be implemented,
for example, as a $d$-dimensional array, as a tree of depth $d$, or,
as in our implementation, as
a 1-dimensional array based on a lexicographic ordering on the variables). If
$f$ is such a table, let $variables(f) = \{V_1,\dots,V_d\}$. We
sometimes write $f$ as $f[V_1,\dots,V_d]$ to make the variables
explicit. $f$ is said to \emph{involve} $V_i$ if $V_i\in variables(f)$.

There are three primitive operations on tables: setting variables,
forming the product of tables, and summing a variable from a table.

\begin{definition}\label{setting-defn}
Suppose $\vset{C}$ is a set of variables, $c$ is an assignment
$\vset{C} = \vset{v}$, and $f$ is a factor on variables
$\vset{X}$. Let $\vset{Y} = \vset{X}-\vset{C}$, let $\vset{Z} =
\vset{X}\cap\vset{C}$, and let $\vset{Z} = \vset{v'}$ be the
assignment of values to $\vset{Z}$ that assigns the same values to
elements of $\vset{Z}$ as $c$ does. Define \boldmath{$set(f,c)$} be the factor on
$\vset{Y}$ given by:
\[set(f,c)(\vset{Y}) = f(\vset{Y},\vset{Z}{=}\vset{v'}).\]
That is, $set(f,c)$ is a function of $\vset{Y}$, the variables of $f$ that are not
in $c$, that is like $f$, but with some values already assigned. Note
that, as a special case of this, if $c$ doesn't involve any variable
in $f$ then $set(f,c)=f$.
\end{definition}

\begin{myexample}
Consider the factor $f(A,B,C,D,E)$ defined by the table of Figure
\ref{str-bn}. Some examples of the value of this function are
$f(a,b,c,d,e) = 0.55$, and $f(\negn
a,b,c,d,\negn e) = 1-0.08 = 0.92$.
$set(f,{\negn a\wedge b \wedge e})$ is a function of $C$ and
$D$ defined by the table:
\begin{center}
\begin{tabular}{|ll|l|}\hline
C & D & value \\\hline
$c$ & $d$ & $0.08 $\\
$c$ & $\negn d$ & $0.08 $\\
$\negn c$ & $d$ & $0.025 $\\
$\negn c$ & $\negn d$ & $0.5 $\\\hline
\end{tabular}
\end{center}

\end{myexample}

\begin{definition}\label{otimes1}
The {\bf product} of tables $f_1$ and $f_2$, written
$f_1\ttimes f_2$ is a table on the union of the variables in $f_1$ and
$f_2$ (i.e., $variables(f_1\ttimes f_2) = variables(f_1)\cup
variables(f_2)$) defined by:
\[(f_1\ttimes f_2)(\vset{X},\vset{Y},\vset{Z})  = 
f_1(\vset{X},\vset{Y})f_2(\vset{Y},\vset{Z})\]
where $\vset{Y}$ is $variables(f_1)\cap variables(f_2)$,
$\vset{X}$ is $variables(f_1)- variables(f_2)$, and 
$\vset{Z}$ is $variables(f_2)- variables(f_1)$.
\end{definition}
Note that $\ttimes$ is associative and commutative.

To construct the
product of tables, $f_{m+1}\ttimes\cdots\ttimes f_k$, we union all of the
variables in $f_{m+1}\ldots f_k$, say these are $X_1,\ldots,X_r$. Then
we construct an $r$-dimensional table so there is an entry in the
table for each combination $v_1,\ldots,v_r$ where $v_i\in dom(X_i)$. The value for the entry corresponding to
$v_1,\ldots,v_r$ is obtained by multiplying the values obtained from
each $f_i$ applied to the projection of $v_1,\ldots,v_r$ onto the
variables of $f_i$. 

\begin{definition}
The {\bf summing out} of variable $Y$ from table $f$, written $\sum_Y
f$ is the table with
variables $\vset{Z} = variables(f)-\{Y\}$ such that\footnote{This may look like a
circular definition, but the left side defines the summing 
tables, whereas on the right side we are summing numbers.}
\[(\sum_Y
f)(\vset{Z}) = \sum_{v_i\in dom(Y)} f(\vset{Z}\AND Y{=}v_i)\]
where $dom(Y) = \{v_1,\dots,v_s\}$.
\end{definition}
Thus, to sum out $Y$, we reduce the dimensionality of
the table by one (removing the $Y$ dimension), the values in the
resulting table are obtained by adding the values of the
table for each value of $Y$.

\begin{myexample}\label{ve-elim-b-ex}
Consider eliminating $B$ from the factors of Example
\ref{simple-factorization} (representing the belief network of Figure
\ref{str-bn}), where all of the variables are Boolean. The factors
that contain $B$, namely those factors that represent $P(E|ABCD)$ and
$P(B|YZ)$, are removed from the set of factors. We construct a factor
$f_1(A,B,C,D,E,Y,Z)=P(E|A,B,C,D) \ttimes P(B|Y,Z)$, thus, for example,
\begin{eqnarray*}
\head{f_1(a,b,c,d,e,y,z) = P(e|a\AND b\AND c\AND d) P(b|y\AND z)}\\
\head{f_1(\negn a,b,c,d,e,y,z) = P(e|\negn a\AND b\AND c\AND d) P(b|y\AND z)}\\
\head{f_1(\negn a,\negn b,c,d,e,y,z) = P(e|\negn a\AND \negn b\AND c\AND d) P(\negn b|y\AND z)}\\
\head{f_1(a,\negn b,c,d,e,y,z) = P(e|a\AND \negn b\AND c\AND d) P(\negn b|y\AND z)}
\end{eqnarray*}
and similarly for the other values of $A\ldots Z$. We then need
to sum out $B$ from $f_1$, producing $f_2(A,C,D,E,Y,Z)$ where, for
example, 
\[f_2(a,c,d,e,y,z) = f_1(a,b,c,d,e,y,z)+f_1(a,\negn b,c,d,e,y,z).\]
$f_2$ is then added to the set of factors.
Note that the construction of $f_1$ is for exposition only; we don't
necessarily have to construct a table for it explicitly.
\end{myexample}

%See \cite{ZhaPoo94a,ZhaPoo96a,Dechter96a} for more details.

\section{Contextual Independence}\label{ci-secn}
In this section we give a formalization of contextual
independence. This notion was first introduced into the influence
diagram literature \cite{SmiHolMat93a}. We base our definitions on the
work of \citeasnoun{BouFriGolKol96a}.
\begin{definition}
Given a set of variables $\vset{C}$, a {\bf context} on $\vset{C}$ is
an assignment of one value to each variable in $\vset{C}$. Usually
$\vset{C}$ is left implicit, and we simply talk about a context. We
would say that $\vset{C}$ are the variables of the context. Two
contexts are {\bf incompatible} if there exists a variable that is
assigned different values in the contexts; otherwise they are {\bf
compatible}.  We write the empty context as $true$.
\end{definition}

\begin{definition}\cite{BouFriGolKol96a}
Suppose $\vset{X}$, $\vset{Y}$, $\vset{Z}$ and $\vset{C}$ are sets of variables.
$\vset{X}$ and $\vset{Y}$ are {\bf contextually independent} given
$\vset{Z}$ and context $\vset{C}{=}c$, where $c \in dom(\vset{C})$, if
\[P(\vset{X}|\vset{Y}{=}y_1\AND \vset{Z}{=}z_1\AND \vset{C}{=}c) =
P(\vset{X}|\vset{Y}{=}y_2\AND \vset{Z}{=}z_1\AND  \vset{C}{=}c)\]
for all $y_1,y_2 \in dom(\vset{Y})$ for all $z_1 \in
dom(\vset{Z})$ such that $P(\vset{Y}{=}y_1\AND \vset{Z}{=}z_1 \AND
\vset{C}{=}c)>0$ and $P(\vset{Y}{=}y_2\AND  \vset{Z}{=}z_1 \AND \vset{C}{=}c)>0$.

We also say that $\vset{X}$ is {\bf contextually independent} of $\vset{Y}$ given
$\vset{Z}$ and context $\vset{C}{=}c$.
Often we will refer to the simpler case when the
set of variables $\vset{Z}$ is empty; in this case we say that $\vset{X}$ and $\vset{Y}$ are
{\bf contextually independent} given context $\vset{C}{=}c$.
\end{definition}
\begin{myexample}
Given the belief network and conditional probability table of Figure
\ref{str-bn},  
\begin{itemize}
\item $E$ is contextually independent of
$\{C,D,Y,Z\}$ given context $a\AND b$. 
\item $E$ is contextually independent of
$\{C,D,Y,Z\}$ given $\{B\}$ and context $a$.
\item $E$ is not contextually independent of
$\{C,D,Y,Z\}$ given $\{A,B\}$ and the empty context $true$.
\item
$E$ is contextually independent of
$\{B,D,Y,Z\}$ given context $\negn a\AND c$. 
\item $E$ is contextually independent of
$\{A,B,C,D,Y,Z\}$ given $B$ and context $\negn a\AND \negn c \AND d$.
\end{itemize}
\end{myexample}

\subsection{Where Does Contextual Independence Arise?}
Most of the examples in this paper are abstract as they are designed
to show off the various features of the algorithms or to show
pathological cases.  In this section we will give some examples to
show natural examples.  We are not claiming that contextual
independence is always present or able to be exploited. Exploiting contextual
independence should be seen as one of the tools to solve large
probabilistic reasoning tasks.

\begin{myexample}
When a child goes into an emergency ward the staff may want to
determine if they are a likely carrier of chicken pox (in order to
keep them away from other children). If they haven't been exposed to
chicken pox within the previous few weeks, they are unlikely to be a
carrier. Thus whether they are a carrier is independent of the other
background conditions given they haven't been exposed. If they have
been exposed, but have not had chicken pox before they are likely to
be a carrier. Thus whether they are a carrier is independent of the
other background conditions given they have been exposed and haven't
had chicken pox before. The other case can involve many other
variables (e.g., the severity and the age of the last time they had
chicken pox) to determine how likely the child is to be a carrier.
\end{myexample}

\begin{myexample} \label{heating-example}
Many engineered systems are designed to insulate something from other
conditions. The classic example is central air conditioning (heating
and/or cooling in a house). The temperature inside a house depends on
the outside temperature if the air conditioning is off. If the air
conditioning is on, the temperature depends on the setting of the
thermostat and not on the outside temperature.  Thus the inside
temperature is contextually independent of the outside temperature
given the air conditioning is on and is contextually independent of the
thermostat setting given the air conditioning is off.
\end{myexample}

\begin{myexample}
Consider a case where someone is to make a decision based on a
questionnaire and the questions asked depend on previous answers. In
this case the decision\footnote{To make this a probabilistic problem,
and not a decision problem, consider that the probability is for a
third party to determine the probability distribution over the
possible decisions. A similar analysis can be carried out to exploit
contextual independence for decisions
\cite{Poole95e}. The decision maker's decisions can't depend on
information she doesn't have. } is contextually independent of the
answers to the questions that are not asked given the context of the
questions asked. For example, consider a questionnaire to determine if
a bank customer should get a loan that starts asking the customer if
they rent or own their current home. If they own, they are asked a
number of questions about the value of the house which are not asked
if they rent. The probability that they get a loan is contextually
independent of the value of the home (and the other information
that was not available to the decision maker) given that the applicant
rents their home.
\end{myexample}

\begin{myexample}
When learning a decision network from data, it is often advantageous
to build a decision tree for each variable given its parents
\cite{FriGol96b,ChiHecMee97a}. These decision trees provide contextual
independence (a variable is independent of it's predecessors given the
context along a path to a leaf in the tree). The reason that this is a
good representation to learn is because there are fewer parameters and
more fine control over adding parameters; splitting a leaf adds many
fewer parameters than adding a new parent (adding a new variable to
every context).

\end{myexample}


\subsection{Parent Contexts and Contextual Belief Networks}
We use the notion of contextual independence for a representation that
looks like a belief network, but with finer-grain independence that
can be exploited for efficient inference in the contextual variable elimination algorithm.

As in the definition of a belief network, let's assume that we have a
total ordering of the variables, $X_1,\ldots,X_n$.
\begin{definition}
Given variable $X_i$, we say that $\vset{C}{=}c$, where
$\vset{C}\subseteq\{X_{i-1}\ldots X_1\}$ and $c\in dom(\vset{C})$, is a {\bf parent context} for
$X_i$ if $X_i$ is contextually independent of the predecessors of
$X_i$ (namely $\{X_{i-1}\ldots
X_1\})$ given $\vset{C}{=}c$.
\end{definition}
What is the relationship to a belief network? In a belief network, the
rows of a conditional probability table for a variables form a set of
parent contexts for the variable. However, there is often a much
smaller set of smaller parent contexts that covers all of the cases.

\begin{myexample}\label{parents-ex}
Consider the belief network and conditional probability table of Figure
\ref{str-bn}. The predecessors
of variable $E$ are $A,B,C,D,Y,Z$.  A set of minimal parent
contexts for $E$ is $\{ \{a,b\}$, $\{a,\negn b\}$, $\{\negn a,c\}$,
$\{\negn a,\negn c,d,b\}$, $\{\negn a,\negn c,d,\negn b\}$, $\{\negn
a,\negn c,\negn d\}\}$. This is a mutually exclusive and exhaustive set of parent contexts. The probability of $E$ given values for its
predecessors can be reduced to the probability of $E$ given a parent
context.  For example:
\begin{eqnarray*}
\head{P(e|a,b,c,\negn d,y,\negn z) = P(e|a,b)}\\
\head{P(e|\negn a,b,c,\negn d,y,\negn z) = P(e|\negn a,c)}\\
\head{P(e|\negn a,\negn b,c, d,\negn y,\negn z) = P(e|\negn a,c)}.
\end{eqnarray*}
In the belief network, the parents of $E$ are $A,B,C,D$.  To specify
the conditional probability of $E$ given its parents, the traditional
tabular representation (as in Figure \ref{str-bn}) require $2^4 = 16$
numbers instead of the 6 needed if we were to use the parent contexts
above. Adding an extra variable as a parent to $E$ doubles the size of
the tabular representation, but if it is only relevant in a single
context it may only increase the number of parent contexts
by one.

We can often (but not always) represent contextual independence in
terms of trees.
\begin{figure}
\begin{center}
\includegraphics[width=0.9\columnwidth]%
     {str-dt}
\end{center}

\captn{Tree-structured
representations of the conditional probabilities for $E$, $B$,
and $D$ given
their parents. Left branches correspond to true and right branches to
false. Thus, for example, $P(e|a \AND b) = 0.55$, $P(e|a \AND \negn
b) = 0.3$, $P(e|\negn a \AND \negn
c \AND d \AND b) = 0.025$ etc.} \label{str-dt}
\end{figure}
The left side of Figure \ref{str-dt} gives a tree-based
representation for the conditional probability of $E$ given its
parents. In this tree, internal nodes are labelled with parents of $E$
in the belief network. The left child of a node corresponds to
the variable labelling the node being true, and the right child
to the variable being false. The leaves are labelled with the
probability that $E$ is true. For example $P(e|a\AND \negn b) = 0.3$,
irrespectively of the value for $C$ or $D$. In the tree-based
representation the variable ($E$ in this case) is contextually
independent of its predecessors given the context defined by a path
through the tree. The paths through the tree correspond to parent
contexts. 
\end{myexample}


Before showing how the structure of parent contexts can be exploited in
inference, there are a few properties to note:
\begin{itemize}
\item
The elements of a mutually exclusive and exhaustive set of parent
contexts are not always the minimal parent contexts. For example,
suppose we have a variable $A$ with parents $B$ and $C$, all of which
are Boolean. Suppose probability of $a$ is $p_1$ when both $B$ and $C$
are true and probability $p_2$ otherwise. One mutually exclusive and
exhaustive set of parent contexts for $A$ is $\{b\AND c, b \AND \negn
c, \negn b\}$. $b \AND \negn c$ is not minimal as $\negn c$ is also a
parent context. Another mutually exclusive and exhaustive set of
parent contexts for this example is $\{b\AND c, \negn b \AND c, \negn
c\}$. The set of minimal parent contexts, $\{b\AND c, \negn b , \negn
c\}$, isn't a mutually exclusive and exhaustive set as the elements
are not pairwise incompatible.

One could imagine using arbitrary Boolean formulae in the
contexts. This was not done as it would entail using theorem proving
(or a more sophisticated subsumption algorithm) during inference. We
doubt that this would be worth the extra overhead for the limited 
savings.
\item A compact decision tree representation of conditional
probability tables \cite{BouFriGolKol96a} always corresponds to a
compact set of parent contexts (one context for each path through the
tree).  However, a mutually exclusive and exhaustive set of parent
contexts cannot always be directly represented as a decision tree (as
there isn't always a single variable to split on). For example, the
mutually exclusive and exhaustive set of contexts $\{\{a,b\}, \{\negn
a,c\}, \{\negn b,\negn c\}, \{a,\negn b,c\}, \{\negn a,b,\negn c\}\}$
doesn't directly translate into a decision tree. More importantly, the
operations we perform don't necessarily preserve the tree structure.
Section \ref{why-rules} shows how we can do much better than an
analogous tree-based formulation of our inference algorithm.
\end{itemize}

\begin{definition}
A {\bf contextual belief network} is an acyclic directed graph where
the nodes are
random variables. Associated with each node $X_i$
is a mutually exclusive
and exhaustive set of parent contexts, $\Pi_i$, and, for each
$\pi\in \Pi_i$, a probability
distribution $P(X_i|\pi)$ on $X_i$. Thus a contextual belief network
is like a belief network, but we only specify the probabilities for
the parent contexts.
\end{definition}


For each variable $X_i$ and for each
assignment $X_{i-1}{=}v_{i-1},\ldots , X_1{=}v_1$ of values to its
preceding variables, there is a compatible parent context
$\pi_{X_i}^{v_{i-1}\ldots v_1}$. The probability of a complete context
(an assignment of a value to each variable) is given by:
\begin{eqnarray}
\lefteqn{P(X_1{=}v_1,\ldots,X_n{=}v_n)} \nonumber\\
& = & \prod_{i = 1}^n P(X_i{=}v_n|X_{i-1}{=}v_{i-1},\ldots , X_1{=}v_1)\nonumber\\
& = &  \prod_{i = 1}^n P(X_i{=}v_i|\pi_{X_i}^{v_{i-1}\ldots v_1})\label{rule-joint-def}
\end{eqnarray}
This looks like the definition of a belief network (equation
(\ref{joint-def})), but which variables act as the parents depends on
the values.  The numbers required are the probability of each variable
for each element of the mutually exclusive and exhaustive set of
parent contexts. There can be many fewer of these than the number of
assignments to parents in a belief network. At one extreme, there are
the same number; at the other extreme there can be exponentially many
more assignments of values to parents than the number of elements of a
mutually exclusive and exhaustive set of parent contexts.


\subsection{Parent Skeletons}
Although the definition of a contextual belief network specifies the
contextual independence we want, it doesn't give us a way to organize
the parent contexts (in much the same way as a belief network doesn't
specify the representation of a conditional probability table). We use
the concept of a parent skeleton as a way to organize the parent
contexts; we want to use the indexing provided by tables while still
allowing for the ability to express context-specific independence.

The notion of a parent context is more fine-grained than that of a
parent (the set of parents corresponds to many parent contexts). When
there is no context-specific independence, we would like to not have
to consider the parent contexts explicitly, but consider just the
parents. We
will use a parent skeleton to cover both parents and parent contexts
as special cases, and to interpolate between them, when the
independence depends on some context as well as all values of some
other variables. 
\begin{definition}
A {\bf parent skeletal pair} for variable $X$ is a pair $\tuple{c,V}$ where $c$ is
a context on the predecessors of $X$ and $V$ is a set of predecessors
of $X$ such that $X$ is contextually independent of its predecessors
given $V$ and context $c$. Note that a parent context is $c\wedge
V=v$.
A {\bf parent skeleton} for variable $X$ is a set of parent skeletal
pairs, $\{\tuple{c_j,V_j}:0<j\leq k\}$, where the $c_j$ are mutually exclusive and
exhaustive (i.e., $c_i$ and $c_j$ are incompatible if $i\neq j$, and $\bigwedge_{j=1}^k
c_j \equiv true$).
\end{definition}

\begin{myexample} A parent skeleton for $E$ from Example \ref{parents-ex}
is $\{ \tuple{a,\{B\}}$, $\tuple{\negn a\AND c,\{\}}$,
$\tuple{\negn a\AND \negn c\AND d,\{B\}}$,  $\tuple{\negn
a\AND \negn c\AND \negn d,\{\}}$.
\end{myexample}

Parent skeletons form the basis of a representation for contextual
belief networks. For each variable, $X$, you select a parent skeleton
such that for each parent skeleton pair $\tuple{c_j,V_j}$ in the parent
context,  $c_j\AND V_j=v_j$ is a parent context for $X$.  For each
such parent context pair we specify a probability distribution $P(X|c_j\AND
V_j=v_j)$. 

\subsection{Contextual Factors}
Whereas the VE algorithm uses tables both as a representation for
conditional probabilities and for the intermediate representations,
the contextual variable elimination algorithm defined below uses a
hybrid of tables 
and rules \cite{Poole97a} that we call contextual factors or {\genrool}s. {\Genrool}s
cover both tables and rules as special cases.
\begin{definition}
A {\bf contextual factor} or {\bf {\genrool}} is a pair of the form:
\[\tuple{c,t}\]
where $c$ is a context, say $X_1{=}v_k\AND \ldots\AND X_k{=}v_k$, and $t$ is a
table that represents a function on variables $X_{k+1},\ldots,X_m$,
where $\{X_1,\dots,X_k\}$ and $\{X_{k+1},\ldots,X_m\}$ are disjoint
sets of variables. $c$ is called the {\bf body} of the {\genrool} and $t$ is
called the {\bf table} of the {\genrool}.
\end{definition}

A {\genrool} represents a partial function
\cite{ZhaPoo99a} from the union of the variables. The function only
has a value when the context is true, and the value of the function is
obtained by looking up the value in the table.

Just as tables can be used to represent conditional probabilities,
{\genrool}s can be used to represent conditional probabilities
when there is context-specific independence.
In particular, a set of parent contexts can be represented as a set of
{\genrool}s with mutually exclusive and exhaustive bodies. Given a
parent skeleton for variable $X$ we can construct a set of {\genrool}s
for $X$ as follows: for each $\tuple{c,V}$ in the parent skeleton for
$X$, we construct a {\genrool} $\tuple{c,t(\{X\}\cup V)}$ where
$t(\{X=x\}\wedge V=v)= P(X=x|V=v \AND c)$.


\begin{definition}
A {\genrool} is {\bf applicable} on a context if the
body of the {\genrool} is compatible with the context. 
\end{definition}

\begin{definition}
Given a {\genrool} $r=\tuple{X_1{=}v_k\AND \ldots\AND X_k{=}v_k, t[X_{k+1},\ldots,X_m]}$ and a context $c$ that assigns at least
the variables $X_1\dots X_m$, if $r$ is
applicable in $c$, the {\bf value} of the
context $c$ with respect to the
{\genrool} $r$ is the value of $t[X_{k+1}=v_{k+1},\ldots,X_m=v_m]$ where
$v_{k+1},\ldots,v_m$ are the values assigned to $X_{k+1},\ldots,X_m$ in $c$.
\end{definition}

\begin{definition}
A set $R$ of {\genrool}s {\bf represents a conditional
probability} $P(X_i|X_1\dots X_{i-1})$ if the bodies of the {\genrool}s are
mutually exclusive and exhaustive, and if $P(X_i=v_i|X_1=v_1\AND\dots\AND
X_{i-1}=v_{i-1})$ is equal to the value of the context $X_1=v_1\AND\dots\AND
X_{i-1}=v_{i-1}\AND X_i=v_i$ with respect to the (unique) {\genrool} in $R$
that is applicable in that context.
\end{definition}

Intuitively, the {\genrool}s that represent a contextual
belief network are a way to organize the parent contexts. The idea is
to represent the parent contexts in tables when there is no context-specific
independence, and when some variables are independent of their
predecessors in some context, then that context can be made a body of
the {\genrool}s.


\begin{myexample} \label{ex:genrooldemo}
Consider the conditional probabilities represented in Figure
\ref{str-dt}. 
$E$ is independent of its predecessors given $\{B\}$ and context
$a$. This leads to the {\genrool}:
\begin{eqnarray}
\head{\stuple{a,t_1[B,E]}}\label{gr-a-be}
\end{eqnarray}
$E$ is independent of its predecessors given context
$\negn a \AND c$. This leads to the {\genrool}:
\begin{eqnarray}
\head{\stuple{\negn a \AND c ,t_2[E]}}\label{gr-nac-e}
\end{eqnarray}
$E$ is independent of its predecessors given $\{B\}$ and context
$\negn a \AND \negn c \AND D$. This leads to the {\genrool}:
\begin{eqnarray}
\head{\stuple{\negn a \AND \negn c \AND d
    ,t_3[B,E]}}\label{gr-nancd-be}
\end{eqnarray}
$E$ is independent of its predecessors given context
$\negn a \AND \negn c \AND \negn d$. This leads to the {\genrool}:
\begin{eqnarray}
\head{\stuple{\negn a \AND \negn c \AND \negn d ,t_4[E]}}\label{gr-nancnd-e}
\end{eqnarray}
The full multiset of {\genrool}s corresponding to the trees of Figure
\ref{str-dt} are given in Figure \ref{gen-rules-str-dt}.
The fifth and sixth {\genrool}s give the
conditional probability for $B$, and the last two {\genrool}s
give the conditional probability for $D$.
\begin{figure}
\[
P(E|A,B,C,D)\left\{\begin{array}{cc}
\roolb{a,\begin{array}{|ll|l|}\hline
B & E & Value \\ \hline
true & true & 0.55\\
true & false & 0.45\\
false & true & 0.3\\
false & false & 0.7\\
\hline\end{array}
} \label{rule-init-hybrid1} &
\roolb{\negn{a}\wedge c,\begin{array}{|l|l|}\hline
E & Value \\ \hline
true & 0.08\\
false & 0.92\\
\hline\end{array}
} \label{rule-init-hybrid2}\\[1.5cm]
\roolb{\negn{a}\wedge \negn{c}\wedge d,\begin{array}{|ll|l|}\hline
B & E & Value \\ \hline
true & true & 0.025\\
true & false & 0.975\\
false & true & 0.85\\
false & false & 0.15\\
\hline\end{array}
} \label{rule-init-hybrid3} &
\roolb{\negn{a}\wedge \negn{c}\wedge \negn{d},\begin{array}{|l|l|}\hline
E & Value \\ \hline
true & 0.5\\
false & 0.5\\
\hline\end{array}
} \label{rule-init-hybrid4}
		     \end{array}\right.\]
\[
P(B|Y,Z)\left\{\begin{array}{cc}\roolb{y,\begin{array}{|ll|l|}\hline
B & Z & Value \\ \hline
true & true & 0.77\\
true & false & 0.17\\
false & true & 0.23\\
false & false & 0.83\\
\hline\end{array}
} \label{rule-init-hybrid5} &
\roolb{\negn{y},\begin{array}{|l|l|}\hline
B & Value \\ \hline
true & 0.27\\
false & 0.73\\
\hline\end{array}
} \label{rule-init-hybrid6}\end{array}\right.\]
\[P(D|Y,Z)\left\{\begin{array}{cc}
\roolb{z,\begin{array}{|l|l|}\hline
D & Value \\ \hline
true & 0.29\\
false & 0.71\\
\hline\end{array}
} \label{rule-init-hybrid7} &
\roolb{\negn{z},\begin{array}{|ll|l|}\hline
D & Y & Value \\ \hline
true & true & 0.79\\
true & false & 0.59\\
false & true & 0.21\\
false & false & 0.41\\
\hline\end{array}
} \label{rule-init-hybrid8}
  \end{array}\right.
\]
\captn{The {\genrool}s corresponding to the trees of Figure \ref{str-dt}}
\label{gen-rules-str-dt}
\end{figure}
\end{myexample}

We can now rewrite the definition of a contextual belief network in
terms of {\genrool}s:
\begin{quote}
If every conditional probability is represented by a set of
{\genrool}s,
the probability of a complete context, $c$ is the product of the
values of $c$ with respect to the {\genrool}s that are applicable in $c$.
For each complete context and for each variable there is one
{\genrool} containing that variable that is applicable in that
context.
\end{quote}


\section{Contextual Variable Elimination} \label{sec:rule-VE}
The general idea of contextual variable elimination (CVE) is to
represent conditional probabilities in terms of {\genrool}s, and
use the VE algorithm with the {\genrool} representation rather
than with tables.  The units of manipulation are thus finer grained
than the factors in VE or the members of the buckets of BEBA; what is
analogous to a factor or a member of a bucket consists of multisets of
{\genrool}s. Given a variable to eliminate, we can ignore (distribute out)
all of the \emph{{\genrool}s} that don't involve this
variable. Where there is some contextual independence that goes beyond
conditional independence of variables, the savings can be
substantial. If there is no contextual independence, all of the
{\genrool}s have empty contexts, and this algorithm reduces to
VE.

This section introduces an abstract nondeterministic version of CVE. Section
\ref{hybrid} presents a more concrete version where we explain how to
resolve much of the
nondeterminism.

The input to CVE is: 
\begin{itemize}
\item a multiset of {\genrool}s that consists of the union of the 
  {\genrool}s that represent the conditional probability distribution of each variable
  given its predecessors
\item a set of query
variables
\item an observation that is a conjunction of assignments of values to
some of the variables
\end{itemize}
We first consider the case with no observations. Observations
are considered in Section \ref{evidence}.

Initially and after the elimination of each variable, we maintain a multiset of {\genrool}s with the following {\bf
program invariant}:
\begin{quote}
The probability of a context $c$ on the non-eliminated variables can be
obtained by multiplying the values of context $c$ associated with {\genrool}s that
are applicable in context $c$. For each complete context on the
non-eliminated variables and for each variable there is at least one
{\genrool} containing that variable that is applicable in that
context\footnote{This second part of the invariant may not be so
intuitive, but is important. For example, in Example
\ref{ex:genrooldemo}, one may be tempted to reduce
{\genrool} (\ref{gr-nancnd-e}) to
$\rool{\negn{a}\wedge \negn{c}\wedge \negn{d},0.5}$ (i.e., where the
table is a function of no variables) as the
contribution of the {\genrool}s is the same independent of the value
of $E$ (the table $t_4[E]$ has value 0.5 for each value of $E$ in {\genrool} (\ref{gr-nancnd-e})).
The first part of the invariant isn't violated. However, if there were
no other {\genrool}s containing $E$ that are applicable when $\negn{a} \AND
\negn{c}\AND \negn{d}$ is true, after summing out $E$, we want the
{\genrool} $\rool{\negn{a}\wedge \negn{c}\wedge \negn{d},1}$, but before
summing out $E$ we want the {\genrool} $\rool{\negn{a}\wedge \negn{c}\wedge
\negn{d},0.5}$ in order to maintain the first part of the
invariant. We would like to maintain the property that we only
consider {\genrool}s containing $E$ when eliminating $E$. The second
part of the invariant allows us to do this without 
treating this as a special case in our algorithm. }.
\end{quote}
The algorithm will not sum out a variable in all contexts in one
step. Rather it will sum out a variable in different contexts
separately. Intermediate to being fully summed out, a variable will be
summed out in some contexts and not in others. The \emph{remaining
variables} should be interpreted relative to whether the variable
has been summed out in context $c$.

Like VE, the abstract algorithm is made up of the primitive operations
of summing out a variable and multiplying {\genrool}s, and also includes a
primitive operation
of {\genrool} splitting that enables the other two operations. All of these
operations locally preserve this program invariant. They are
described in the next subsections.
\subsection{Multiplying Contextual Factors} \label{multiplying-contexts}
If we have two {\genrool}s with the same context:
\begin{eqnarray*}
\hrool{b \prub t_1}\label{aifc2}\\
\hrool{b \prub t_2}\label{bifc}
\end{eqnarray*}
we can replace them with their product:
\begin{eqnarray*}
\head{\rool{b \prub t_1\ttimes t_2}.}\label{abifc}
\end{eqnarray*}
The program invariant is maintained, as any context
incompatible with $b$ isn't affected by this operation. Any context
that is compatible with $b$, the product of the values of $t_1$ and
$t_2$ on that context is the same as the value of $t_1\ttimes t_2$
on that context.  The completeness part of the invariant isn't
affected by multiplying.


\subsection{Summing Out A Variable That Appears In The Table}
Suppose we are eliminating $Y$, and have a {\genrool}:
\begin{eqnarray*}
\hrool{b \prub t}
\end{eqnarray*}
such that table $t$ involves $Y$, and no other {\genrool} that
is compatible with $b$ contains $Y$, we can replace this {\genrool} with
\begin{eqnarray*}
\hrool{b \prub \sum_Y t}
\end{eqnarray*}
Note that after this operation $Y$ is summed out in context $b$.

\paragraph{Correctness:}
To see why this is correct, consider a context $c$ on the remaining
variables ($c$ doesn't give a value for $Y$). If $c$ isn't compatible with $b$, it isn't affected by this
operation. If it is compatible with
$b$, by elementary probability theory:
\[P(c) = \sum_i P(c \AND Y{=}v_i)\] 
By the program invariant, and because there are no other {\genrool}s
containing $Y$ that are compatible with $c$, $P(c \AND Y{=}v_i) = p_i
p$, for some product $p$ of contributions of {\genrool}s that don't
involve $Y$.  Exactly the same {\genrool}s will be used for the
different values of $Y$.  Thus we have $P(c) = p (\sum_i p_i )$, and
so we have maintained the first part of the program invariant.
The second part of the program invariant is trivially maintained.

\subsection{Summing Out A Variable In The Body Of {\Genrool}s}  \label{tplus-defined}
Suppose we are eliminating $Y$, with domain $\{v_1,\dots,v_k\}$, and
have {\genrool}s: 
\begin{eqnarray*}
\hrool{b \AND Y{=}v_1\prub T_1}\label{aifbe2}\\
\head{\dots}\\
\hrool{b \AND Y{=}v_k\prub T_k}\label{aifbne}
\end{eqnarray*}
such that there are no other {\genrool}s that contain $Y$ whose
context is compatible with $b$. We can replace these {\genrool}s with
the {\genrool}:
\begin{eqnarray*}
\hrool{b \prub T_1\tplus \dots \tplus T_k}\label{aifbhi}
\end{eqnarray*}
Where $\tplus$ is the additive analogue of $\ttimes$. That is, it
follows definition \ref{otimes1}, but using addition of the values
instead of multiplication.

Note that after this operation $Y$ is summed out in context $b$.

\paragraph{Correctness:}
To see why this is correct, consider a context $c$ on the remaining
variables ($c$ doesn't give a value for $Y$). If $c$ isn't compatible with $b$, it isn't affected by this
operation. If it is compatible with
$b$, by elementary probability theory:
\[P(c) = \sum_i P(c \AND Y{=}v_i)\] 
we can distribute out all of the other {\genrool}s from the product
and thus the first part of the invariant is maintained. Note that the
$\tplus$ operation is equivalent to enlarging each table to include
the union of all of the variables in the tables, but not changing any
of the values, and then pointwise adding the values of the resulting
tables.  The second part is trivially maintained.


The second part of the program invariant implies that we cannot have
a {\genrool} of the form $\rool{b \AND Y{=}v_i\prub p_i}$ without a
corresponding {\genrool} for $Y{=}v_j$, where $i\neq j$.

\subsection{{\Genrool} Splitting} \label{rule-splitting}
In order to satisfy the prerequisites to be able to multiply
{\genrool}s and sum out variables, sometimes we need to split
{\genrool}s.

If we have a {\genrool}
\begin{eqnarray*}
\hrool{b \prub t}\label{aifbs}
\end{eqnarray*}
we can replace it by the result of splitting it on a non-eliminated variable $Y$, with domain
$\{v_1,\dots,v_k\}$. If $Y$ doesn't appear in $t$, splitting $t$ on
$T$ results in the
set of {\genrool}s:
\begin{eqnarray*}
\hrool{b \AND Y{=}v_1 \prub  t}\label{aifbcs}\\
\head{\dots}\nonumber\\
\hrool{b \AND Y{=}v_k \prub  t}\label{aifbncs}
\end{eqnarray*}
If $Y$ does appear in $t$, 
the result is the
set of {\genrool}s:
\begin{eqnarray*}
\hrool{b \AND Y{=}v_1 \prub  set(t,Y{=}v_1)}\label{aifbcset}\\
\head{\dots}\nonumber\\
\hrool{b \AND Y{=}v_k \prub  set(t,Y{=}v_k)}\label{aifbncset}
\end{eqnarray*}
where $set$ was defined in Definition \ref{setting-defn}.
\paragraph{Correctness:}
The program invariant is maintained as one of the new {\genrool}s is used
for any complete context instead of the original {\genrool}. They both
give the same contribution.

\begin{myexample}\label{split-on-y-ex}
Splitting the first {\genrool} for $P(E|A,B,C,D)$ in Figure
\ref{gen-rules-str-dt} on $Y$ gives two {\genrool}s:
\begin{eqnarray}
\hroolb{a \AND y,\begin{array}{|ll|l|}\hline
B & E & Value \\ \hline
true & true & 0.55\\
true & false & 0.45\\
false & true & 0.3\\
false & false & 0.7\\
\hline\end{array}
} \label{ay-be-ex}\\
\hroolb{a \AND \negn{y},\begin{array}{|ll|l|}\hline
B & E & Value \\ \hline
true & true & 0.55\\
true & false & 0.45\\
false & true & 0.3\\
false & false & 0.7\\
\hline\end{array}
}\label{any-be-ex}
\end{eqnarray}
\end{myexample}

\begin{myexample} \label{split-on-a-ex}
Splitting the first {\genrool} for $P(B|Y,Z)$ in Figure
\ref{gen-rules-str-dt} on $A$ gives two {\genrool}s:
\begin{eqnarray}
\hroolb{a \AND y,\begin{array}{|ll|l|}\hline
B & Z & Value \\ \hline
true & true & 0.77\\
true & false & 0.17\\
false & true & 0.23\\
false & false & 0.83\\
\hline\end{array}
}\label{ay-bz-ex}\\
\hroolb{\negn{a} \AND y,\begin{array}{|ll|l|}\hline
B & Z & Value \\ \hline
true & true & 0.77\\
true & false & 0.17\\
false & true & 0.23\\
false & false & 0.83\\
\hline\end{array}
}\label{nay-bz-ex}
\end{eqnarray}
The reason that we may want to do these two splits is that now we can
multiply {\genrool}s (\ref{ay-be-ex}) and (\ref{ay-bz-ex}).
\end{myexample}

\subsection{Examples of Eliminating Variables}
The four operations above are all that is needed to eliminate a
variable. A variable is eliminated when it is summed out of all
contexts.
\begin{myexample} \label{elimB-ex}
When we eliminate $B$ from the {\genrool}s of Figure
\ref{gen-rules-str-dt}, we only need to consider the four {\genrool}s
that contain $B$. The preconditions for summing out $B$ or for
multiplying are not satisfied, so we need to split. If we split the
first {\genrool} for $P(E|A,B,C,D)$ on $Y$ (as in Example
\ref{split-on-y-ex}) and split the first {\genrool} for $P(B|Y,Z)$ on
$A$ (as in Example \ref{split-on-a-ex}), we produce two {\genrool}s,
(\ref{ay-be-ex}) and (\ref{ay-bz-ex}), that can be multiplied
producing:
\begin{eqnarray}
\hroolb{a\wedge y,\begin{array}{|lll|l|}\hline
B & E & Z & Value \\ \hline
true & true & true & 0.4235\\
true & true & false & 0.0935\\
true & false & true & 0.3465\\
true & false & false & 0.0765\\
false & true & true & 0.069\\
false & true & false & 0.249\\
false & false & true & 0.161\\
false & false & false & 0.581\\
\hline\end{array}
} 
\end{eqnarray}
This is the only {\genrool} that contains $B$ and is applicable
in the context $a\wedge y$, so we can sum out $B$ from the table,
producing the {\genrool}:
\begin{eqnarray}
\hroolb{a\wedge y,\begin{array}{|ll|l|}\hline
E & Z & Value \\ \hline
true & true & 0.4925\\
true & false & 0.3425\\
false & true & 0.5075\\
false & false & 0.6575\\
\hline\end{array}
} \label{rule-elim-b-1}
\end{eqnarray}
The other nontrivial {\genrool}s produced when summing out $B$ are:
\begin{eqnarray}
\hroolb{a\wedge \negn{y},\begin{array}{|l|l|}\hline
E & Value \\ \hline
true & 0.3675\\
false & 0.6325\\
\hline\end{array}
} \label{rule-elim-b-2}\\
\hroolb{\negn{a}\wedge \negn{c}\wedge d\wedge y,\begin{array}{|ll|l|}\hline
E & Z & Value \\ \hline
true & true & 0.21475\\
true & false & 0.70975\\
false & true & 0.78525\\
false & false & 0.29025\\
\hline\end{array}
} \label{rule-elim-b-6}\\
\hroolb{\negn{a}\wedge \negn{c}\wedge d\wedge \negn{y},\begin{array}{|l|l|}\hline
E & Value \\ \hline
true & 0.62725\\
false & 0.37275\\
\hline\end{array}
} \label{rule-elim-b-7}
\end{eqnarray}
See Example \ref{ones-b-ex} below for some trivial {\genrool}s produced and
how to avoid them.

These {\genrool}s should be contrasted with the factor on $A,C,D,E,Y,Z$ (of
size 32) that is produced by eliminating $B$ in VE.
\end{myexample}

\begin{myexample}
Suppose that instead we were to eliminate $D$  from the 
{\genrool}s of Figure 
\ref{gen-rules-str-dt}. This example differs from the previous example as
$D$ appear in the bodies as well as in the tables.

The two {\genrool}s for $P(E|A,B,C,D)$ that contain $D$, namely
${\stuple{\negn a \AND \negn c \AND d ,t_3[B,E]}}$ ({\genrool}
(\ref{gr-nancd-be})), and $\stuple{\negn a \AND \negn c \AND \negn d
,t_4[E]}$ ({\genrool} (\ref{gr-nancnd-e})) are both compatible with both
{\genrool}s for $P(D|Y,Z)$. So we cannot sum out the variable or
multiply any {\genrool}s.  

In order to be able to multiply
{\genrool}s, we can split {\genrool}
(\ref{gr-nancd-be}) on $Z$ producing:
\begin{eqnarray}
\head{\stuple{\negn a \AND \negn c \AND d \AND z ,t_3[B,E]}} \label{nancdzBE}\\
\head{\stuple{\negn a \AND \negn c \AND d \AND \negn{z} ,t_3[B,E]}}\label{nancdnzBE}
\end{eqnarray}

The {\genrool}s for $P(D|Y,Z)$ are $\stuple{z,t_7[D]}$ and
$\stuple{z,t_8[D,Y]}$.  We can split the first of these on $A$
producing 
\begin{eqnarray}
\head{\stuple{a \AND z,t_7[D]}} \label{azD}\\
\head{\stuple{\negn{a} \AND z,t_7[D]}} \label{nazD}
\end{eqnarray}

There are no other {\genrool}s containing $D$ with context compatible with
{\genrool} (\ref{azD}). The prerequisite  required to sum
out $D$ in the context $a\wedge z$ is satisfied. This results in the 
{\genrool} $\stuple{a \AND z,1}$ where $1$ is the factor of no variables
that has value $1$. This can be removed as the product of $1$ doesn't
change anything.  Intuitively this can be justified because in the
context when $A$ is true $D$ has no children. We can detect this
case to improve efficiency (see Section \ref{ones-secn}).

The {\genrool} (\ref{nazD}) can be split on $C$, producing 
\begin{eqnarray}
\head{\stuple{\negn{a} \AND c \AND
z,t_7[D]}}\label{naczD}\\
\head{\stuple{\negn{a} \AND \negn{c} \AND
z,t_7[D]}}\label{nanczD}
\end{eqnarray}
We can sum out $D$ from {\genrool} (\ref{naczD}), producing $\stuple{\negn{a} \AND c \AND
z,1}$, as in the previous case.

We can split {\genrool} (\ref{nanczD}) on $D$ producing:
\begin{eqnarray}
\head{\stuple{\negn{a} \AND \negn{c} \AND d \AND
z,0.29}}\label{nanczd}\\
\head{\stuple{\negn{a} \AND \negn{c} \AND \negn{d} \AND
z,0.71}}\label{nancznd}
\end{eqnarray}
where $0.29$ and $0.71$ are the corresponding values from
$t_7[D]$. These are functions of no variables, and so are just numbers.

We can now multiply {\genrool} (\ref{nanczd}) and
(\ref{nancdzBE}), producing:
\begin{eqnarray}
\head{\stuple{\negn a \AND \negn c \AND d \AND z ,0.29 t_3[B,E]}}\label{nancdzBEres}
\end{eqnarray}
where $0.29 t_3[B,E]$ is the table obtained by multiplying each element
of $t_3[B,E]$ by $0.29$.

We can also split {\genrool} (\ref{gr-nancnd-e}) on $Z$,
producing:
\begin{eqnarray}
\head{\stuple{\negn a \AND \negn c \AND \negn d \AND z
    ,t_4[E]}}\label{gr-nancndzE}\\ 
\head{\stuple{\negn a \AND \negn c \AND \negn d \AND \negn z
    ,t_4[E]}}\label{gr-nancndnzE}
\end{eqnarray}
We can multiply {\genrool}s (\ref{nancznd}) and
(\ref{gr-nancndzE}), producing:
\begin{eqnarray}
\head{\stuple{\negn a \AND \negn c \AND \negn d \AND z
    ,0.71 t_4[E]}}\label{gr-nancndzEres}
\end{eqnarray}

We now have only complementary {\genrool}s for $D$ in the context $\negn a
\AND \negn c \AND z$, namely {\genrool}s (\ref{nancdzBEres}) and
(\ref{gr-nancndzEres}) so we can sum-out $D$ in this context resulting
in 
\begin{eqnarray}
\head{\stuple{\negn a \AND \negn c \AND z
    ,t_9[B,E]}}\label{gr-nancndzBEsum}
\end{eqnarray}
where $t_9[B,E]$ is $0.29 t_3[B,E]\tplus 0.71 t_4[E]$. In full form
this is:
\begin{eqnarray}
\hroolb{\negn{a}\wedge \negn{c}\wedge z,\begin{array}{|ll|l|}\hline
B & E & Value \\ \hline
true & true & 0.36225\\
true & false & 0.63775\\
false & true & 0.6015\\
false & false & 0.3985\\
\hline\end{array}
} \label{rule-hybrid-elim-d7}
\end{eqnarray}

The other {\genrool} produced when summing out $D$ is:
\begin{eqnarray}
\hroolb{\negn{a}\wedge \negn{c}\wedge \negn{z},\begin{array}{|lll|l|}\hline
B & E & Y & Value \\ \hline
true & true & true & 0.12475\\
true & true & false & 0.21975\\
true & false & true & 0.87525\\
true & false & false & 0.78025\\
false & true & true & 0.7765\\
false & true & false & 0.7065\\
false & false & true & 0.2235\\
false & false & false & 0.2935\\
\hline\end{array}
} \label{rule-hybrid-elim-d8}
\end{eqnarray}
\end{myexample}
\subsection{When to Split} 
{\Genrool} splitting makes the multiset of {\genrool}s more complicated, so we
have to be careful to apply this operation judiciously.
We need to carry out {\genrool} splitting in order to make identical or
complementary
contexts so we can carry out the operations of summing out a variable
or multiplying {\genrool}s. These are the only cases we need to split.

\begin{definition}\label{split-defn}
Given {\genrool} $r_1 = \rool{c_1,T_1}$ and context $c$, such that $c_1$ and
$c$ are compatible, to {\bf split \boldmath{$r_1$} on
\boldmath{$c$}} means to split $r_1$ sequentially on each of the variables
that are assigned in $c$ that aren't assigned in $c_1$.

When we split $r_1$ on $c$, we end up with a single {\genrool} with a
context that is compatible with $c$; the contexts of all of the other
{\genrool}s that are produced by the splitting are incompatible with
$c$. These {\genrool}s that are incompatible with $c$ are called {\bf
residual} {\genrool}s.

More formally, we can recursively define $residual(r_1,c)$, where $r_1
= \rool{c_1,t_1}$ and $c$ and $c_1$ are compatible, by:
\begin{itemize}
\item $residual(r_1,c)=\{\}$ if $c\subseteq c_1$
\item Else if $c\notsubseteq c_1$, select a variable $X$ that is
  assigned in $c$ but not in $c_1$.
\begin{eqnarray*}
residual(r_1,c)&=&\{\rool{c_1\AND X{=}v_i,set(t_1, X{=}v_i)}: v_i\in dom(X) \& v_i
\neq c^X\}\\
&& \cup residual(\rool{c_1\AND X{=}c^X,set(t_1,X{=}c^X)},c)
\end{eqnarray*}
where $c^X$ is
the value assigned to $X$ in context $c$. Recall (Definition \ref{setting-defn}) that $set(t,{X{=}v_i})$ is $t$ if $t$
doesn't involve $X$ and is the selection of the $X{=}v_i$ values from
the table, followed by the projection onto the remaining variables, if
$t$ does involve $X$.
\end{itemize}

The results of splitting a {\genrool} on a context is a set of
{\genrool}s:
\[split(\rool{c_1,t_1},c)=residual(\rool{c_1,t_1},c)
\cup \{\rool{c_1\cup c,t_1}\}.\]
\end{definition}


\begin{myexample} \label{split-exam}
Consider $residual(\rool{a\AND b,t_1[C,D]},c \AND e)$.
Suppose we split on $C$ first, then on $E$.
This results in two residual {\genrool}s:
$\rool{a\AND b\AND \negn c,t_2[D]}$ and
$\rool{a\AND b\AND c \AND \negn e,t_3[D]}$. Note that $t_2[D]$ is the
projection of $t_1[C,D]$ onto $C{=}false$ and $t_3[D]$  is the
projection of $t_1[C,D]$ onto $C{=}true$. The non-residual {\genrool} that
we want from the split is
$\rool{a\AND b\AND c \AND e,t_3[D]}$. 

If instead we split on $E$ then $C$, we
get the residual {\genrool}s:
$\rool{a\AND b\AND \negn e,t_1[C,D]}$ and $\rool{a\AND b\AND \negn c
\AND e,t_2[D]}$, with the same non-residual {\genrool}.
\end{myexample}


Note that the result can depend on the order in which variables are
selected (see below for some useful splitting heuristics). The algorithms that use the split will be correct no matter
which order the variables are selected, however some orderings may
result in more splitting in subsequent operations.

Example \ref{split-exam} highlights one heuristic that seems generally applicable. When we have
to split a {\genrool} on variables that appear in its body and on variables
in its table, it's better to split on variables in the table first, as
these simplify the {\genrool}s that need to be subsequently split.

We can use the notion of a residual to split two rules that are
compatible, and need to be multiplied. Suppose we have {\genrool}s
$r_1 = \rool{c_1,t_1}$ and
$r_2 = \rool{c_2,t_2}$, that both contain the variable being eliminated
and where $c_1$ and $c_2$ are compatible contexts.
If we split $r_1$ on $c_2$, and split $r_2$ on $c_1$, we end up with
two {\genrool}s whose contexts are identical. Thus we have the
prerequisite needed for multiplying.

\begin{myexample}
Suppose we have {\genrool}s $r_1 = \rool{a\AND b \AND \negn c,t_1}$ and
$r_2  = \rool{a \AND d,t_2}$ that both contain the variable being eliminated.
We can split $r_1$ on the body of $r_2$, namely $a \AND d$, producing the {\genrool}s
\begin{eqnarray}
\hrool{a\AND b \AND \negn c \AND d,t_1}\label{split_r1_ad}\\
\hrool{a\AND b \AND \negn c \AND \negn d,t_1} \nonumber
\end{eqnarray}
Only the first of these is compatible with $r_2$. The second {\genrool} is a
residual {\genrool}.

We can split $r_2$ on the body of $r_1$, namely $a\AND b \AND \negn c$, by first splitting $r_2$ on $B$, then on
$C$, producing the {\genrool}s: 
\begin{eqnarray}
\hrool{a \AND b \AND c \AND d,t_2}\nonumber\\
\hrool{a \AND b \AND \negn c \AND d,t_2}\label{split-r2bc}\\
\hrool{a \AND \negn b \AND d,t_2}\nonumber
\end{eqnarray}
Only the second {\genrool} ({\genrool} (\ref{split-r2bc}))is compatible with $r_1$ or any of the residual
{\genrool}s produced by splitting $r_1$. {\Genrool}s (\ref{split_r1_ad}) and
(\ref{split-r2bc}) have identical contexts and so can be multiplied.
\end{myexample}

Suppose we have {\genrool}s $r_1 = \rool{c_1\AND Y{=}v_i,t_1}$ and
$r_2 = \rool{c_2\AND Y{=}v_j,t_2}$,
where $c_1$ and $c_2$ are compatible contexts, and $v_i\neq v_j$.
If we split $r_1$ on $c_2$, and split $r_2$ on $c_1$, we end up with
two {\genrool}s whose contexts are identical except for the complementary
values for $Y$. This is exactly what we need for summing out $Y$.

If $Y$ is binary with domain $\{v_i,v_j\}$, and there are {\genrool}s
$r_1 = \rool{c_1\AND Y{=}v_i,t_1}$ and $r_2 = \rool{c_2\AND
Y{=}v_j,t_2}$, where $c_1$ and $c_2$ are compatible contexts, and
there is no other {\genrool} that contains $Y$ that is compatible
with $c_1$ and $c_2$, summing out $Y$ in the context $c_1\cup
c_2$ results in the
{\genrool}s:
\[residual(r_1,c_2) \cup residual(r_2,c_1) \cup \{\rool{c_1\cup
c_2,t_1 \tplus t_2}\}.\]
If there are more than two values in the domain, we may need to split
each pair of {\genrool}s, always using the results of previous splits for
subsequent splits.
\begin{proposition}\em\label{prop:number-rules}
Splitting {\genrool} $\rool{c_1,t_1}$ on $c$ creates
\[\sum_{X \in vars(c)-vars(c_1)} (\left|dom(X)\right|-1)\]
extra {\genrool}s, independently of the order in which the variables are
selected to be split, where $vars(c)$ is the set of variables assigned
in context $c$.
\end{proposition}

When we have to split, there is a choice as to which variable to split on
first. 
While this choice does not influence the number of {\genrool}s created for the
single split, it can
influence the number of {\genrool}s created in total because of subsequent
splitting. One heuristic was given above.
Another useful heuristic seems to be: given a {\genrool} with multiple possible
splits, look at all of the {\genrool}s that need to be combined with this
{\genrool} to enable multiplication or addition, and split on the variable
that appears most. For those cases where the conditional probability
forms a tree structure, this will tend to split on the root of the
tree first. 


\subsection{Evidence}\label{hybrid-evidence}\label{evidence}
As in VE, evidence simplifies the knowledge base.
Suppose $E_1{=}o_1 \AND\ldots\AND E_s{=}o_s$ is observed.
There are three steps in absorbing evidence:
\begin{itemize}
\item Remove any {\genrool} whose context contains $E_i{=}o_i'$, where $o_i
  \neq o_i'$. 
\item Remove any term $E_i{=}o_i$ in the context of a {\genrool}.
\item Replace each table $t$ with $set(t,{E_1{=}o_1 \AND\ldots\AND
E_s{=}o_s})$ (as in the tabular VE algorithm).
\end{itemize}
Again note that incorporating evidence only simplifies the {\genrool} base.


Once evidence has been incorporated into the {\genrool}-base, the
{\bf program invariant} becomes:
\begin{quote}
The probability of the evidence conjoined with a context $c$ on the
non-eliminated, non-observed variables is equal to the product
of the probabilities of the {\genrool}s that are applicable in context
$c$. For each context $c$ on the non-eliminated, non-observed
variables and for each variable $X$ there is at least one {\genrool} containing
$X$ that is applicable in context $c$.
\end{quote}
For probabilistic inference, where we will normalise at the end, we
can remove any {\genrool} that doesn't involve any variable (i.e., with an empty
context and single number as the table) as a result of the second
or third cases. That is, we remove any {\genrool} that only has
observed variables. We then need to replace ``equal'' with
``proportional'' in the program invariant.

\begin{myexample}
Suppose $\negn{d}\AND \negn{z}$ is observed given the {\genrool}s of
Figure \ref{gen-rules-str-dt}. The first two {\genrool}s for $P(E|A,B,C,D)$
don't involve $D$ or $Z$ and so are not affected by the
observation. The third {\genrool} is removed as its body is incompatible
with the observation. The fourth {\genrool} is replaced by:
\[\roolb{\negn{a}\wedge \negn{c},\begin{array}{|l|l|}\hline
E & Value \\ \hline
true & 0.5\\
false & 0.5\\
\hline\end{array}
}\]
The first {\genrool} for $P(B|Y,Z)$ is replaced by
\[\roolb{y,\begin{array}{|l|l|}\hline
B & Value \\ \hline
true & 0.17\\
false & 0.83\\
\hline\end{array}
}\]
The first {\genrool} for $P(D|Y,Z)$ is removed and the second is replaced by
\[\roolb{true,\begin{array}{|l|l|}\hline
Y & Value \\ \hline
true & 0.21\\
false & 0.41\\
\hline\end{array}
}\]
where $true$ represents the empty context.
\end{myexample}

\subsection{Extracting the Answer}\label{comp-post}
Suppose we had a single query variable $X$. After setting the evidence
variables, and eliminating the remaining variables, we end up
with {\genrool}s of the form:
\begin{eqnarray*}
\hrool{\{X{=}v_i\} \prub  p_i}
\end{eqnarray*}
and of the form
\begin{eqnarray*}
\hrool{\{\} \prub  t_i[X]}
\end{eqnarray*}

If $e$ is the evidence the probability of $X{=}v_i\AND e$ is proportional to
the product contributions of the {\genrool}s with context $X{=}v_i$ and the
selection for the $X{=}v_i$ value for the table.
Thus
\[P(X{=}v_i \AND e) \propto \prod_{\rool{X{=}v_i \prub  p_i}} p_i\prod_{\rool{\{\} \prub  t_i[X]}} t_i[v_i].\]

Then we have:
\[P(X{=}v_i|e) = \frac{P(X{=}v_i \AND e)}{\sum_{v_j}P(X{=}v_j \AND e)}.\]
Notice that constants of proportionality of the evidence or by
removing constants ({\genrool}s with no variables) cancel in the division.

If we had multiple query variables (i.e., we wanted the marginal of the
posterior), then we still multiply the remaining {\genrool}s and renormalise.

\subsection{The Abstract Contextual Variable Elimination Algorithm}
The contextual variable elimination algorithm, is  given in
Figure \ref{hybrid-CVE-algo-abs}.   A more refined version that does
less splitting is given in Section \ref{hybrid}.

\begin{figure}

\begin{pcode}
\bf To compute $P(\vset{X}|E_1{=}o_1 \AND\ldots\AND E_s{=}o_s)$ \\
\>{\bf Given} multiset $R$ of {\genrool}s\\
%\>\>\>elimination ordering $ Y_1,\ldots,Y_k$:\\
\>1.\>Incorporate evidence as in Section \ref{hybrid-evidence}.\\
\>2.\>{\bf while} there is a non-query variable to be eliminated\\
\>\>\>{\bf \{}\\
\>\>\>\>Select non-query variable $Y$ to eliminate;\\
\>\>\>\>Call $R := eliminate(Y,R)$;\\
\>\>\>{\bf \}}\\
%2.\>\>For $i = 1..k$ call $eliminate(Y_i)$.\\
\>3.\>Compute posterior probability for $\vset{X}$ as in Section \ref{comp-post}
\end{pcode}
\begin{pcode}
{\bf Procedure} \boldmath$eliminate(Y,R)$:\\
\>{\bf partition} $R$ into:\\
\>\>$R^- = \mbox{}$those {\genrool}s in $R$ that don't involve $Y$;\\
\>\>$R^* = \{r\in R : r \mbox{ involves } Y \}$;\\
\>{\bf while} there is  $\{\rool{b_1 \prub T_1},
\rool{b_2 \prub T_2}\}\subseteq R^*$ where $b_1$ and $b_2$ are
compatible,\\
\>\>{\bf \{}\\
\>\>\>remove $\rool{b_1 \prub T_1}$ and 
$\rool{b_2 \prub T_2}$ from $ R^*$;\\
\>\>\>split $\rool{b_1 \prub T_1}$ on $b_2$ putting residual {\genrool}s in $R^*$;\\
\>\>\>split
$\rool{b_2 \prub T_2}$ on $b_1$, putting residual {\genrool}s in
$R^*$;\\
\>\>\>add $\rool{b_1\AND b_2 \prub T_1\ttimes T_2}$ to $R^*$;\\
\>\>{\bf \}}\\
\>{\bf for every } $\rool{b,t} \in R^*$ such that $Y$ appears in $t$\\
\>\>{\bf \{}\\
\>\>\> remove $\rool{b,t}$ from $ R^*$;\\
\>\>\>  add $\rool{b,\sum_Y
  t}$ to $R^-$;\\
\>\>{\bf \}}\\
\>{\bf while} $R^*$ is not empty\\
\>\>{\bf \{}\\
\>\>\>{\bf if } $\{\rool{b \AND Y{=}v_1\prub T_1} ,\dots,
\rool{b \AND Y{=}v_k\prub T_k}\} \subseteq R^*$ \\
\>\>\>\>{\bf \{}\\

\>\>\>\>\>remove $\rool{b \AND Y{=}v_1\prub T_1} ,\dots,
\rool{b \AND Y{=}v_k\prub T_k}$ from $R^*$;\\
\>\>\>\>\>add $\rool{b \prub
    T_1\tplus \dots \tplus T_k}$ to $R^-$;\\
\>\>\>\>{\bf \}}\\
\>\>\>{\bf else if}  $\{\rool{b_1 \AND Y{=}v_i \prub T_1},
\rool{b_2 \AND Y{=}v_j \prub T_2}\}\subseteq R^*$ where $b_1$ and $b_2$ are
compatible and $b_1\neq b_2$\\
\>\>\>\>{\bf \{}\\
\>\>\>\>\>remove $\rool{b_1 \AND Y{=}v_i \prub T_1}$ and 
$\rool{b_2 \AND Y{=}v_j \prub T_2}$ from $R^*$;\\
\>\>\>\>\>split $\rool{b_1 \AND Y{=}v_i \prub T_1}$ on
$b_2$, putting all created  {\genrool}s in $R^*$;\\
\>\>\>\>\>split
$\rool{b_2 \AND Y{=}v_j \prub T_2}$ on $b_1$, putting all created  {\genrool}s in $R^*$;\\
\>\>\>\>{\bf \}}\\
\>\>{\bf \}}\\
\>{\bf Return} $R^-$.
\end{pcode}
\begin{pcode}
$\ttimes$ is defined in Section \ref{VE-algo}.\\
$\tplus$ is defined in Section \ref{tplus-defined}.\\
All set operations are assumed to be on multisets.
\end{pcode}

\captn{Contextual Variable Elimination}
\label{hybrid-CVE-algo-abs}
\end{figure}

The elimination procedure is called once for
each non-query, non-observed variable. The order in which the
variables are selected is called the {\bf elimination ordering}.
This algorithm does not imply that the elimination ordering
has to be given a priori. The
other choice points are the order in which to do multiplication, and
the splitting ordering.

Note that in the $eliminate$ algorithm, all set operations are assumed
to be on multisets. It is possible, and not uncommon, to get multiple
copies of the same {\genrool}. One example where this happens is when
there is a naive Bayes model with variable $C$ with no parents, and
variables $Y_1,\dots,Y_n$ each with only $C$ as a parent. Often the
conditional probabilities of some of the $Y_i$'s are the same as they
represent repeated identical sensors. If these identical sensors
observe the same value, then we will get identical {\genrool}s, none
of which can be removed without affecting the answer.

To see the correctness of the procedure, note that all of the local
operations preserve the program invariants; we still need to check
that the algorithm halts. After the first
while-loop of eliminate, the contexts of the  {\genrool}s in $R^*$ are mutually
exclusive and covering by the second part of the loop invariant. For
all complete contexts on the variables that remain after
$Y$ is eliminated, there is either a compatible {\genrool} with $Y$ in the
table, or there is a compatible {\genrool} with $Y=v_i$ for every
value $v_i$. The splitting of the second while loop of eliminate
preserves the mutual exclusiveness of the bodies of the {\genrool}s in
$R^*$ and when splitting a {\genrool}, the set of created {\genrool}s
covers the same context as the original {\genrool}.  If there are
{\genrool}s in $R^*$, and the if-condition does not hold, then there
must be a pair of {\genrool}s where the else-if condition holds. Thus,
each
time through the second while-loop, the
number of {\genrool}s in $R^-$ increases or the number of
{\genrool}s in $R^*$ increases and these are both bounded in size by
the size of the corresponding factor. Thus \emph{ eliminate} must stop, and
when it does $Y$ is eliminated in all contexts.

\subsection{Ones}\label{ones-secn}
In a Bayesian network we can remove a non-observed, non-query node
with no children without changing the conditional probability of the
query variable. This can be carried out recursively. In VE, if we
were to eliminate such variables, we create factors that are all ones (as
$\sum_X P(X|Y) = 1$).

In contextual VE, we can have a more subtle version when a variable
may have no children in some contexts, even if it has children in
another context.

\begin{myexample} \label{ones-b-ex}
Consider eliminating $B$ as in Example \ref{elimB-ex} where the belief network is
given in Figure \ref{str-bn} and the structured conditional
probabilities are given in Figure \ref{str-dt}). In the context $\negn
a\AND c$, the only {\genrool}s that are applicable are those that define
$P(B|YZ)$. As stated, the contextual VE algorithm, the following three
{\genrool}s are created:
\begin{eqnarray*}
\hrool{\negn{a}\wedge c\wedge y,1[Z]} \label{rule-test9}\\
\hrool{\negn{a}\wedge c\wedge \negn{y},1} \label{rule-test11}
\end{eqnarray*}
where $1[Z]$ is a function of $Z$ that has value $1$ everywhere and
$1$ is the function of no variables that has value $1$.
\end{myexample}

{\Genrool}s that have contribution 1 can be removed without affecting the
correctness of the algorithms (as long as these {\genrool}s aren't the only
{\genrool}s that contain a variable in some context). It is easy to show
that the first part of the program invariant is maintained as
multiplying by 1 doesn't affect any number. The second part of the
invariant is also maintained, as there are always the {\genrool}s for the
child ($E$ in this case) that don't depend on the variable being
eliminated, as well as the {\genrool}s for the parents of the variable being
eliminated.

It is however probably better to never construct such {\genrool}s rather
than to construct them and then throw them away. We show how this can
be done in Section \ref{avoid-split}.

\subsection{Multi-Valued Variables}\label{multi-valued-variables}
We have presented an algorithm that allows for multi-valued
variables, where the splitting operation creates the same number of
{\genrool}s as there are values in the domain of the variable being split. 

There is an alternate method for using multi-valued
variables. This is to extend the notion of a context to allow for
membership in a set of values. That is, a context could be a
conjunction of terms of the form $X\in S$ where $S$ is a set of
values. The original version of equality of the form $X{=}v$ is the same
as $X\in \{v\}$. Splitting can be done more efficiently as there is
only one residual {\genrool} for each split. Effectively we treat a multiset of
{\genrool}s as a unit.

There are examples where this representation can be much more
efficient, but it makes the algorithm much more complicated to
explain. There are also examples where the binary splitting is less
efficient as it needs more splits to get the same result.

\subsection{Why CVE Does More Than Representing Factors As Trees}\label{why-rules}
It may seem that CVE is a {\genrool} based representation for
factors, in much the same way as the trees in the structured policy
iteration \cite{BouDeaGol95a} for solving MDPs.  In this section we
present a detailed example that
explains why CVE can be much
more efficient than a tree-based representation of the VE factors.


\begin{myexample} \label{tree-factor-ex}
Figure \ref{mult-child-fig} shows a fragment of a belief network. 
\begin{figure}
\begin{center}
\includegraphics[width=0.8\columnwidth]{mult-child2}
\end{center}

\captn{A fragment of a belief network: $OT$ to eliminate.}
\label{mult-child-fig}
\end{figure}
This is an elaboration
of Example \ref{heating-example}, where what affects the inside temperature
depends on whether the air conditioning is broken or is working. All the variables
are Boolean. We use the following interpretation:
\begin{description}
\item[$FB$] Fred's air conditioning is broken
\item[$FT$] Fred's thermostat setting is high
\item[$OT$] Outside temperature is hot
\item[$FH$] Fred's house is hot
\item[$MB$] Mary's air conditioning is broken
\item[$MT$] Mary's thermostat setting is high
\item[$MH$] Mary's house is hot
\item[$S$] Season, that is true if it is Summer
\end{description}



The
ancestors of $FT$, $FB$, $S$, $MB$, and $MT$ are not shown. They can be
multiply connected. Similarly, the descendants of $FH$ and $MH$ are not
shown. They can be multiply connected.

The outside temperature ($OT$) is only relevant to Fred's house being
hot ($FH$) when Fred's air conditioner is broken ($FB$ is true) in
which case Fred's thermostat setting ($FT$) is not
relevant.
Fred's thermostat setting ($FT$) is only relevant to Fred's house being
hot ($FH$) when Fred's air conditioner is working ($FB$ is false),
in which case the outside ($OT$) is
not relevant. And similarly for Mary's house. See Figure
\ref{mult-child-trees}.  What is important to note is that $FH$ and
$MH$ are dependent, but only if both air conditioners are broken, in
which case the thermostat settings are irrelevant.

\begin{figure}
\begin{center}
\includegraphics[width=\columnwidth]{mult-ch-trees}
\end{center}

\captn{Tree-structured conditional probability tables for $A$
and for $B$. Left branches correspond to \emph{true} and right
branches to \emph{false}.
Thus $p_1 = P(a|d \AND e)$, $p_2 = P(a|d \AND \negn e)$, etc.
}
\label{mult-child-trees}
\end{figure}


Suppose we were to sum out $OT$ in VE. Once $OT$ is eliminated, $FH$ and $MH$
become dependent. In VE and bucket elimination we form a factor
$f(FH,MH,FT,FB,MB,MT,S)$ containing all the remaining variables. This factor
represents $P(FH,MH|FT,FB,MB,MT,S)$ (unless there is a pathological case
such as if $MT$ or $MB$ is a descendent of $FH$, or if $FT$ or $FB$ is a
descendent of $MH$). One could imagine a version of VE
that builds a tree-based representation for this factor. We show here
how the {\genrool}-based version is exploiting more structure than this.


If we are to take the contextual independence into account, we need to
consider the dependence between $FH$ and $MH$ when both $FB$ and $MB$ are
true (in which case $FT$ and $MT$ are irrelevant).  For all of the other
contexts, we can treat $FH$ and $MH$ as independent. The algorithm CVE
does this automatically.

%\begin{myexample}\label{gen_rules_elim_e}
The conditional probabilities of Figures \ref{mult-child-fig} and \ref{mult-child-trees} can be
represented as the following {\genrool}s:
\begin{eqnarray}
\hroolb{fb,\begin{array}{|ll|l|}\hline
FH & OT & Value \\ \hline
true & true & p_1\\
true & false & p_2\\
false & true & 1-p_1\\
false & false & 1-p_2\\
\hline\end{array}
} \label{rule-elim_e_init2}\\
\hroolb{\negn{fb},\begin{array}{|ll|l|}\hline
FH & FT & Value \\ \hline
true & true & p_3\\
true & false & p_4\\
false & true & 1-p_3\\
false & false & 1-p_4\\
\hline\end{array}
} \label{rule-elim_e_init3}\\
\hroolb{mb,\begin{array}{|ll|l|}\hline
MH & OT & Value \\ \hline
true & true & p_5\\
true & false & p_6\\
false & true & 1-p_5\\
false & false & 1-p_6\\
\hline\end{array}
} \label{rule-elim_e_init4}\\
\hroolb{\negn{mb},\begin{array}{|ll|l|}\hline
MH & MT & Value \\ \hline
true & true & p_7\\
true & false & p_8\\
false & true & 1-p_7\\
false & false & 1-p_8\\
\hline\end{array}
} \label{rule-elim_e_init5}\\
\hfactor{\begin{array}{|ll|l|}\hline
OT & S & Value \\ \hline
true & true & p_9\\
true & false & p_{10}\\
false & true & 1-p_9\\
false & false & 1-p_{10}\\
\hline\end{array}
} \label{rule-elim_e_init1}
\end{eqnarray}

Eliminating $OT$ from these {\genrool}s results in six {\genrool}s:
\begin{eqnarray*}
\hroolb{fb\wedge mb,\begin{array}{|lll|l|}\hline
FH & MH & S & Value \\ \hline
true & true & true & p_9*(p_5*p_1)+(1-p_9)*(p_6*p_2)\\
true & true & false & p_{10}*(p_5*p_1)+(1-p_{10})*(p_6*p_2)\\
true & mbalse & true & p_9*((1-p_5)*p_1)+(1-p_9)*((1-p_6)*p_2)\\
true & mbalse & false & p_{10}*((1-p_5)*p_1)+(1-p_{10})*((1-p_6)*p_2)\\
false & true & true & p_9*(p_5*(1-p_1))+(1-p_9)*(p_6*(1-p_2))\\
false & true & false & p_{10}*(p_5*(1-p_1))+(1-p_{10})*(p_6*(1-p_2))\\
false & false & true & p_9*((1-p_5)*(1-p_1))+(1-p_9)*((1-p_6)*(1-p_2))\\
false & false & false & p_{10}*((1-p_5)*(1-p_1))+(1-p_{10})*((1-p_6)*(1-p_2))\\
\hline\end{array}
} \label{rule-elim-e-1}\\
\hroolb{fb\wedge \negn{mb},\begin{array}{|ll|l|}\hline
FH & S & Value \\ \hline
true & true & p_9*p_1+(1-p_9)*p_2\\
true & false & p_{10}*p_1+(1-p_{10})*p_2\\
false & true & p_9*(1-p_1)+(1-p_9)*(1-p_2)\\
false & false & p_{10}*(1-p_1)+(1-p_{10})*(1-p_2)\\
\hline\end{array}
} \label{rule-elim-e-2}\\
\hroolb{\negn{fb},\begin{array}{|ll|l|}\hline
FH & FT & Value \\ \hline
true & true & p_3\\
true & false & p_4\\
false & true & 1-p_3\\
false & false & 1-p_4\\
\hline\end{array}
} \label{rule-elim-e-3}\\
\hroolb{\negn{fb}\wedge mb,\begin{array}{|ll|l|}\hline
MH & S & Value \\ \hline
true & true & p_9*p_5+(1-p_9)*p_6\\
true & false & p_{10}*p_5+(1-p_{10})*p_6\\
false & true & p_9*(1-p_5)+(1-p_9)*(1-p_6)\\
false & false & p_{10}*(1-p_5)+(1-p_{10})*(1-p_6)\\
\hline\end{array}
} \label{rule-elim-e-4}\\
\hroolb{\negn{fb}\wedge \negn{mb},\begin{array}{|l|l|}\hline
S & Value \\ \hline
true & p_9+(1-p_9)\\
false & p_{10}+(1-p_{10})\\
\hline\end{array}
} \label{rule-elim-e-5}\\
\hroolb{\negn{mb},\begin{array}{|ll|l|}\hline
MH & MT & Value \\ \hline
true & true & p_7\\
true & false & p_8\\
false & true & 1-p_7\\
false & false & 1-p_8\\
\hline\end{array}
} \label{rule-elim-e-6}
\end{eqnarray*}

Note that the third and the sixth {\genrool}s were there originally and were
not affected by eliminating $OT$. 
%The structure of these {\genrool}s
%corresponds to the structure of Figure \ref{res-nontrees}.

The resultant {\genrool}s encode the probabilities of $\{FH,MH\}$ in
the context $fb\AND mb$. For all other contexts, CVE considers $FH$
and $MH$ separately.
%There are {\genrool}s for $FH$ in the
%contexts $\negn d \AND c$ ({\genrool} (\ref{aifndc})), $\negn fb \AND \negn
%c$ ({\genrool} (\ref{aifndnc})), $fb \AND \negn mb \AND h$, and $fb \AND
%\negn mb \AND \negn h$, with the last two resulting from combining
%{\genrool} (\ref{aifdenf}), and an analogous {\genrool} created by splitting {\genrool}
%(\ref{aifdne}), with {\genrool}s (\ref{eifh}) and (\ref{eifnh}).
%Similarly there are {\genrool}s for $MH$ in the contexts $\negn mb \AND g$,
%$\negn mb \AND \negn g$, $\negn fb \AND mb \AND h$, and $\negn fb \AND mb
%\AND \negn h$. 
The total table size of the {\genrool}s after $OT$ is eliminated is
24. %The resulting {\genrool}s can be depicted as in Figure \ref{res-nontrees}.
%\begin{figure}
%\begin{center}
%\includegraphics[width=\columnwidth]{res-nontrees.eps}
%\end{center}
%When $D{=}true$ and $MB{=}true$, we
%have the probability of $FH$ and $MH$ together for the values of
%$S$ (i.e., rules of the form $\left<fb\AND mb\AND S{=}v_S\AND FH{=}v_FH \AND
%MH{=}v_MH,p\right>$).
%
%If $D{=}false$ or $MB{=}false$, we have separate rules for the
%probability of $FH$ and the probability of $MH$ (e.g, rules such as
%$\stuple{\negn fb\AND \negn c \AND a,p}$ and $\stuple{mb \AND \negn
%fb\AND h \AND b,p}$).
%
%\captn{Tree-like conditional probability tables for $FH$
%and $MH$ after $OT$ is eliminated.}
%\label{res-nontrees}
%\end{figure}


Unlike VE or BEBA, we need the combined effect on $FH$ and $MH$ only for
the contexts where $OT$ is relevant to both $FH$ and $MH$.  For all other
contexts, we don't need to combine the {\genrool}s for $FH$ and $MH$.  This is
important, as combining the {\genrool}s is the primary source of
combinatorial explosion. By avoiding combining {\genrool}s, we can have a
potentially huge saving when the variable to be summed out appears in
few contexts.
\end{myexample}

\subsection{CVE Compared To VE}
It is interesting to see the relationship between the {\genrool}s generated
and the factors of VE for the same belief network, with the same query
and observations and the same
elimination ordering. There are two aspects to the comparison, first
the exploitation of contexts, and second the idea of not multiplying
{\genrool}s unless you need to.  In this section, we introduce a
tree-based variable elimination algorithm (TVE) that uses {\genrool}s
but doesn't have the property of the example above where there are
{\genrool}s that are not multiplied when VE would multiply the
corresponding factors.


In order to understand the relationship between VE and CVE for the
same query and the same elimination order, we can consider the VE
derivation tree of the final answer. The tree contains all initial and
intermediate factors created in VE. The parents in the tree of any
factor are those factors that were multiplied or had a variable summed
out to produce this factor. Note that this is a tree (each factor has
only one child) as each factor is only used once in VE; once it is
multiplied or a variable is summed from it, it is removed.

For each node in this tree that is created by multiplying two other
factors, the number of multiplications in VE is equal to the table size of
the resulting factor. For each factor created by summing out a
variable, the number of additions is equal to the size of its parent
minus its size.


We can define tree-based variable elimination (TVE) to be a composite of
VE and CVE. It uses  {\genrool}s as in CVE. Associated with each
factor in the VE derivation tree is a set of {\genrool}s. When VE
multiplies two factors, TVE multiplies (and does the requisite
splitting) all of the compatible {\genrool}s associated with the
factors being multiplied.  TVE is essentially the
same as the tree-based merging of \citeasnoun{Boutilier97a} (but
Boutilier also does maximization at decisions).

Whenever VE multiplies two factors, TVE multiplies all of the
{\genrool}s associated with the factors. The TVE {\genrool}s associated
with the VE factors will always have a total table size that is less than
or equal to the VE factor size. TVE maintains a set of {\genrool}s
with mutually exclusive and covering contexts. The number of
multiplications is equal to the resulting table size for each pairwise
multiplication (as each entry is computed by multiplying two
numbers). It is easy to see that TVE always does fewer or an equal number
of multiplications than VE.

CVE is like TVE except that CVE doesn't multiply some of the
{\genrool}s when VE multiplies two factors. It delays the
multiplications until they need to be done. It relies on the hope
that the {\genrool}s can be separately simplified before they need to
be multiplied. This hope is not unjustified because if eliminating a
variable means that both of the factors need to be
multiplied by other {\genrool}s, then
they need to be multiplied by each other. 

\begin{myexample}
If we were to use TVE for Example \ref{tree-factor-ex}, once $OT$ is
eliminated, TVE builds a tree representing the probability on both
$FH$ and $MH$. This entails multiplying out the {\genrool}s that were
not combined in CVE, for example multiplying the third, fifth and
sixth factors of the result of Example \ref{tree-factor-ex}, which produces the
{\genrool} of the form $\tuple{\negn fb \AND\negn
  mb,t(FH,FT,MH,MT,S)}$. Eliminating $OT$ results in a set 
of {\genrool}s with total table size 72, compared to 24 for
VE. Without any contextual structure, VE builds a table with $2^7 = 128$
values.
\end{myexample}


It is possible that not multiplying compatible {\genrool}s earlier means
that we will eventually have to do more multiplications. The following example is the simplest example we could find where CVE  does more
multiplications than VE or TVE. Slight variations in the structure of
this example, however result in CVE doing fewer multiplications.
\begin{myexample}\label{counter-ex}
Consider the belief network shown in Figure
\ref{counter-fig}(a). 
\begin{figure}
\begin{center}
\includegraphics%[width=\columnwidth]
{counter-ex}
\end{center}
\captn{Belief network for Example \ref{counter-ex}.}
\label{counter-fig}
\end{figure}
First we will sum out a variable, $A$, to create
two {\genrool}s that are not multiplied in CVE but are multiplied in
TVE. We then multiply one of these {\genrool}s by another factor when
summing out the second variable, $B$. We then force the multiplication
when eliminating $C$.

Suppose that all of the variables are binary except for variable $W$
that has domain size 1000. (The counter example doesn't rely on
non-binary variables; you could just have $B$ having 10 binary
parents, but this makes the arithmetic less clear). In the analysis
below we only discuss the multiplications that involve $W$, as the
other multiplications sum up to less than a hundred, and are dominated
by the multiplications that involve $W$.

Suppose that we have the following {\genrool}s for $S$:
\begin{eqnarray}
\head{\tuple{x,t_1(A,B,C,S)}}\label{counter-t1}\\
\head{\tuple{\negn x,t_2(B,C,S)}\label{counter-t2}}
\end{eqnarray}
Suppose that we have the following {\genrool}s for $T$:
\begin{eqnarray}
\head{\tuple{x,t_3(A,B,C,T)}\label{counter-t3}}\\
\head{\tuple{\negn x,t_4(C,T)}\label{counter-t4}}
\end{eqnarray}
Suppose first that $T$ is observed. Then the {\genrool}s for $T$ are
replaced by:
\begin{eqnarray}
\head{\tuple{x,t_5(A,B,C)}\label{counter-t5}}\\
\head{\tuple{\negn x,t_6(C)}\label{counter-t6}}
\end{eqnarray}
Let's now eliminate $A$. In both CVE and TVE,  {\genrool}s
(\ref{counter-t1}) and (\ref{counter-t5}) and the prior on $A$ are
multiplied together, and $A$ is summed
out resulting in:
\begin{eqnarray}
\head{\tuple{x,t_7(B,C,S)}}\label{counter-t7}
\end{eqnarray}
In $TVE$, {\genrool}s (\ref{counter-t2}) and (\ref{counter-t6}) are also
multiplied together resulting in:
\begin{eqnarray}
\head{\tuple{\negn x,t_8(B,C,S)}\label{counter-t8}}
\end{eqnarray}
Next we eliminate $B$. In both CVE and TVE, {\genrool}
(\ref{counter-t7}) is multiplied by the factors representing $P(C|B)$ and
$P(B|W)$. We assume that the factor representing $P(B|W)$ is multiplied
last as this minimises the number of multiplications. This involves
8008 multiplications (as the product has a table size of 8000 and the
intermediate table is of size 8).
Then $B$ is summed out resulting in the factor:
\begin{eqnarray}
\head{\tuple{x,t_9(C,S,W)}}\label{counter-t9}
\end{eqnarray}
In CVE, {\genrool}
(\ref{counter-t2}) is multiplied by the factors representing $P(C|B)$
and $P(B|W)$. This also involves
8008 multiplications. Then $B$ is
summed out from the product resulting in:
\begin{eqnarray}
\head{\tuple{\negn x,t_{10}(C,S,W)}\label{counter-t10}}
\end{eqnarray}
In TVE, {\genrool} (\ref{counter-t8}) is multiplied by the factors
representing  $P(C|B)$ and $P(B|W)$. This also involves 8008
multiplications. Then $B$ is summed out from the product resulting in:
\begin{eqnarray}
\head{\tuple{\negn x,t_{11}(C,S,W)}\label{counter-t11}}
\end{eqnarray}
When $C$ is eliminated, TVE requires no more multiplications. It just
sums out $C$ from the table of {\genrool} (\ref{counter-t11}). However
in CVE, we need to multiply {\genrool}s (\ref{counter-t6}) and
(\ref{counter-t10}), which involves 4000 multiplications.  The
resulting {\genrool}s from CVE and TVE are identical.

Thus CVE requires about 20000 multiplications, TVE requires about 16000 multiplications.
VE, for the same elimination order, requires about 16000 multiplications.
\end{myexample}

This should not be surprising, particularly when you realise that VE is
not optimal. For a given elimination ordering, it is sometimes optimal
to multiply factors before VE actually multiplies them, as the following
example shows:
\begin{myexample}
Consider the belief network in Figure \ref{counter-fig}(b), with the
same domain sizes as in the previous example. The factors represent
$P(W)$, $P(B|W)$, $P(C)$, $P(S|BC)$. If we were to eliminate $B$ then
$C$, it is more efficient to preemptively multiply $P(C)$ by $P(S|BC)$
than to delay the multiplication till after summing out $B$ (as VE does).
\end{myexample}

It may seem negative to show that CVE doesn't always do fewer
multiplications than VE but has the overhead of maintaining
contexts. However, there seems no reason why the preemptive
multiplication of TVE is optimal either. One possibility is to treat
``when to multiply'' and ``when to sum out variables'' as a secondary
optimisation problem \cite{BerBri72b,ShaD'ADel90a,D'Ambrosio95a};
unfortunately this optimization is also computationally difficult
\cite{D'Ambrosio95a}. 
This, however is beyond the scope of this paper.
\section{Avoiding Splitting} \label{hybrid}

\subsection{Absorption}\label{avoid-split}
In this section we characterize a case when we don't
need to split during multiplication. Note that the result of eliminating a variable is
exactly the same as before; we are saving because we don't
create the residuals, but rather use the original {\genrool}.

\begin{definition}
A multiset of {\genrool}s $R$ is {\bf complete} if the contexts of the
{\genrool}s are mutually exclusive and covering.
\end{definition}


If we have a multiset $R$ of {\genrool}s that is complete, it means
that we don't have to split other {\genrool}s $r$ that may need to be
multiplied by all of the {\genrool}s in $R$. For each residual of $r$,
there will be another element of $R$ with which it will be
compatible. Instead of splitting $r$, we can just multiply it by each
element of $R$. This is the intuition behind absorption. Note that we
may need to split elements of $R$ during multiplication.

Suppose we have a complete multiset of {\genrool}s $R$ and
another {\genrool} $r_1=\rool{c_1,t_1}$. Define
\begin{eqnarray*}
\lefteqn{absorb(R,\rool{c_1,t_1})} \\
&= & \{\rool{c_i,p_i}\in R : incompatible(c_i,c_1)\} \\
&& \displaystyle\mbox{}\cup \bigcup_{\begin{array}{c}\rool{c_i,t_i}\in R \\ compatible(c_1,c_i)\end{array}}
\left(residual(\rool{c_i,t_i},c_1) \cup \{\rool{c_1\cup c_i,
set(t_1,c_i)\ttimes
set(t_i,c_1)}\}\right)
\end{eqnarray*}
where $\ttimes$ is table multiplication (Definition \ref{otimes1}).

\paragraph{Correctness:}
We can replace $R\cup \{r_1\}$ with $absorb(R,r_1)$ and the program
invariant is preserved. First note that the
{\genrool}s in $absorb(R,r_1)$ are complete (and so the second part of
the invariant holds). To see why the first part of the invariant is
preserved, consider a complete context $c$. If $c$ is compatible with $c_1$, then in the original
{\genrool}s, we use one {\genrool} from $R$ as well as $r_1$. In the
revised {\genrool} base we use the appropriate {\genrool} with the
product of the original probabilities. If $c$ is incompatible with
$c_1$ then it is compatible with one element $\rool{c_2,p_2}$ of
$R$. If $c_2$ is incompatible with $c_1$, the {\genrool} to be used is
the original {\genrool}, and if $c_2$ is compatible with $c_1$, then
we use the residual {\genrool}. In each case we get the same
contributions from $R\cup \{r_1\}$ and from $absorb(R,r_1)$.




\begin{myexample}
If we were to eliminate $B$ from the {\genrool}s of Figure
\ref{gen-rules-str-dt} (as in example \ref{elimB-ex}), we can treat
the two {\genrool}s for $P(B|Y,Z)$ as the complete multiset of {\genrool}s. This
means that we don't need to split the other {\genrool}s on $Y$.

Note that if we try to use the {\genrool}s for $E$ as the complete set of
{\genrool}s when eliminating $B$, we don't have to split the
{\genrool}s on $A$, $C$ or $D$, but we have to consider {\genrool}s that don't
involve $B$ when eliminating $B$, and we end up multiplying {\genrool}s that
don't need to be multiplied.


\end{myexample}

Note that if $R$ cannot be represented as a decision tree (e.g., if
$R$ has {\genrool}s corresponding to the contexts in $\{\{a,b\},
\{\negn a,c\}, \{\negn b,\negn c\}, \{a,\negn b,c\}, \{\negn a,b,\negn
c\}\}$), it's possible that there is no way to split $r_1$ that
results in as compact a representation as results from
$absorb(R,r_1)$.


It seems as though it is very useful to have a multiset of {\genrool}s that
is complete, but it is not of much use if we cannot easily find such a
set. First note that if we have a multiset $R$ of {\genrool}s that is
complete, then $absorb(R,r_1)$ is also a multiset of {\genrool}s that is
complete, which can, in turn, be used to combine with another {\genrool}.

Initially, for each variable $X$, the {\genrool}s that represent the
conditional probability table $P(X|\pi_X)$ are complete. Moreover they
will all contain $X$ and so need to be involved when eliminating
$X$. These can be used as the initial seed for absorbing other
{\genrool}s.
Unfortunately, after we have eliminated some variables, the
{\genrool}s that define the initial conditional probability tables for some
variable $X$ don't exist anymore; they have been split, multiplied by
other {\genrool}s and added to other {\genrool}s. However, for each
variable $X$, we can still extract a useful multiset of {\genrool}s that all
contain $X$ that are complete on the empty context (i.e., are mutually
exclusive and covering). These will be called the {\bf {\genrool}s for} $X$,
and correspond to the {\genrool}s with $X$ in the head in an earlier version
of contextual variable elimination \cite{Poole97a}.

\begin{definition}\label{rules-for-defn}
If $X$ is a variable, the {\bf {\genrool}s for \boldmath $X$} are a subset
of the {\genrool} base defined by:
\begin{itemize}
\item Initially the {\genrool}s for $X$ are the {\genrool}s that define the
conditional probability $P(X|\pi_X)$. 
\item When we split a {\genrool} for $X$, the {\genrool}s created are
also {\genrool}s for $X$. Note that this does not cover the case where
we are splitting a {\genrool} on a {\genrool} for $X$.
\item When we multiply a {\genrool} for $X$ with another {\genrool},
the {\genrool} created is a {\genrool} for $X$.
\item When we add a {\genrool} for $X$ with another {\genrool} (when
eliminating another variable $Y$, for example), the resulting
{\genrool} is also a {\genrool} for $X$.
\end{itemize}
\end{definition}

\begin{lemma}\em
The {\genrool}s for $X$ at any stage of contextual variable elimination
are complete.
\end{lemma}
To show this, we will show that the three basic operations preserve
this property.
\begin{itemize}
\item splitting preserves this property, as the resulting {\genrool}s are
exclusive and cover the context of the {\genrool} being split.
\item multiplication preserves this property as, for any variable $X$,
only one of the {\genrool}s involved in a multiplication can be a
{\genrool} for $X$ (as the {\genrool}s for $X$ are mutually exclusive)
and the set of contexts covered by the {\genrool}s isn't changed by
multiplication. This argument also holds for absorption. 
\item for addition, note that, for any variable $X$, either all of the
{\genrool}s or none of the {\genrool}s involved in an addition are
{\genrool}s for $X$ when summing out $Y$. To show this suppose we have
$r_1=\rool{c\AND Y=v_1,p_1}$ and $r_2=\rool{c\AND Y=v_2,p_2}$ where
{\genrool} $r_1$ is a {\genrool} for $X$ and {\genrool} $r_2$
isn't. Because the {\genrool}s for $X$ are mutually exclusive and
covering, there must be a {\genrool} that is covered by $X$ that is
applicable in a context when $c\AND Y=v_2$ is applicable. This
{\genrool} cannot mention $Y$, for otherwise addition isn't
applicable, and so it must also be applicable when $c\AND y=v_1$
is true, which contradicts the mutual exclusiveness of the {\genrool}s
for $X$. Now it is easy to see that addition preserves this property
as the {\genrool}s being summed cover the same contexts as the
resulting {\genrool}.
\end{itemize}

%\begin{myexample}
%Consider Example \ref{tree-factor-ex}. {\Genrool}s
%(\ref{aifde})--(\ref{naifndnc}) are the initial {\genrool}s for $A$, and
%{\genrool}s (\ref{biffe})--(\ref{nbifnfng}) are the initial {\genrool}s for
%$B$. After $E$ is eliminated, one of the {\genrool}s created is
%\begin{eqnarray*}
%\hrool{a \AND b \AND d \AND f \AND h, p_9*(p_5*p_1)+(1-p_9)*(p_6*p_2)}
%\end{eqnarray*}
%This is both a {\genrool} for $A$ and a {\genrool} for $B$. There are other {\genrool}s
%that are {\genrool}s for $A$, but not {\genrool}s for $B$, and vice versa. If $A$ had some
%children, the example would remain unchanged, but there would be
%some {\genrool}s what contain $A$ that are not {\genrool}s for $A$.
%\end{myexample}

We can also use the idea of the {\genrool}s for $X$ to recognise when
summing out a variable will create a table of 1's that can be removed
(see Section \ref{ones-secn}). First note that in the original
{\genrool}s for $X$, if, when eliminating $X$, we don't have to
multiply these by other {\genrool}s (i.e., they have no children in
this context), then we know that summing out $X$ will produce a table
of 1's.  We can do better than this for recognising when we will
produce ones. We will use one bit of information to encode whether a
{\genrool} for $X$ is \emph{pure} for $X$. Initially all of the
{\genrool}s for $X$ are pure for $X$. If a {\genrool} for $X$ is pure
for $X$, and, when eliminating $Y$ is absorbed into a {\genrool}s for
$Y$ that is pure for $Y$, then the resulting {\genrool} is pure for
$X$.  For every other case when a {\genrool} for $X$ is multiplied by
another {\genrool}, the result is not pure for $X$. If we are summing
out $X$, after absorption, we can remove all {\genrool}s for $X$ that
are pure for $X$. This is correct because we have maintained the
invariant that if we sum out $X$ from the table of a {\genrool} for
$X$ that is pure for $X$ we create a table with only ones.  Note that
this procedure generalises the idea that we can recursively remove
variables with no children that are neither observed nor queried.

The idea of absorption into the rules for the variable being
eliminated described in this section should only be seen
as a heuristic to avoid splitting. It does not necessarily reduce the
amount of work.
First note that in variable elimination there is a choice in the order
that we multiply factors. Multiplication of factors is associative and
commutative, however, the order in which the multiplication is carried
out affects efficiency, as the following example shows.

\begin{myexample}
Suppose variable $B$ has one parent, $A$ and two children $C$ and $D$,
who each only have $B$ as a parent. When eliminating $B$ we have to
multiply the factors representing $P(B|A)$, $P(C|B)$ and
$P(D|B)$. Suppose that $B$, $C$ and $D$ are binary, and that $A$ has
domain size of 1000. When multiplying two factors the number of
multiplications required is equal to the size of the resulting
factor. If we save intermediate results, and multiply these in the
order $(P(B|A)\ttimes P(C|B)) \ttimes P(D|B)$, we will do $12000$
multiplications. If we save intermediate results, and multiply these in
the order $P(B|A)\ttimes (P(C|B) \ttimes P(D|B))$, we will do $8008$
multiplications. If we don't save intermediate tables, but instead
recompute every product, we will do
$16000$ multiplications.
\end{myexample}
If you need to multiply $k>1$ factors, where $m$ is the size of the
resulting factor, the number of multiplications is
bounded below by $k-2+m$ 
(as the final product requires $m$ multiplications and each other
requires at least one multiplication) and bounded above by $(k-1)*m$
(as there are $k-1$ factor multiplications and each of these requires at most
$m$ multiplications).

The associative ordering imposed by absorption into the
rules for the variable being eliminated (which for
the example above implies absorbing $P(C|B)$ and $P(D|B)$ into
$P(B|A)$) may not be the optimal multiplication ordering. The
absorption ordering (that saves because it reduced splitting) should
be seen as a heuristic; it may be worthwhile to do a meta-level
analysis to determine what order to multiply
\cite{BerBri72b,ShaD'ADel90a,D'Ambrosio95a}, but this is beyond the
scope of this paper.


\subsection{Summing Out A Variable}\label{otimes-g}

Suppose we are eliminating $Y$, and we have absorbed all of the {\genrool}s
that contain $Y$ into the {\genrool}s for $Y$.  Then  any
two {\genrool}s in $R$ that contain $Y$
have incompatible contexts. The contexts for the {\genrool}s
that contain $Y$ in the table are disjoint from the contexts of the 
{\genrool}s that contain $Y$ in the body.

Summing out $Y$ from a {\genrool} that contains $Y$ in the table
proceeds as before. We can use a similar trick to absorption to
avoid any more splitting when adding {\genrool}s that contain $Y$ in the body.

Suppose $Y$ has domain $\{v_1,\dots,v_s\}$. The contexts of the
{\genrool}s with $Y{=}v_i$
in the body are exclusive and the disjunct is logically equivalent to
the disjunct of {\genrool}s with $Y{=}v_j$ in the body for any other value
$v_j$. 

For each
$1\leq i \leq s$, let $R_i = \{\rool{b,t}:  \rool{b\AND Y{=}v_i,t}\in
R^+ \}$. Thus $R_i$ is the {\genrool} for $Y=v_i$ in the context, but with $Y=v_i$ omitted from the context. We will combine the $R_i$'s
using a binary operation:
\begin{eqnarray*}
R_1 \oplus_g R_2=\{\rool{c_1\cup c_2,set(t_1,c_2)\tplus set(t_2,c_1)}:
\rool{c_1,t_1}\in R_1, \rool{c_2,t_2}\in R_2, compatible(c_1,c_2)\}
\end{eqnarray*}
where $\tplus$ is an addition operation defined on tables that is
identical to the product $\ttimes$ of Definition \ref{otimes1}
except that it adds the values instead of multiplying them.

Then $R_1 \oplus_g R_2 \oplus_g\dots\oplus_g R_s$ is the result from
summing out $Y$ from the {\genrool}s with $Y$ in the body.

\subsection{Contextual Variable Elimination with Absorption}
A version of  \emph{contextual variable elimination}
that uses absorption, is  given in
Figure \ref{hybrid-CVE-algo}. This is the algorithm used in the
experimental results of Section \ref{emp-res}.
\begin{figure}

\begin{pcode}
\bf To compute \boldmath$P(X|E_1{=}o_1 \AND\ldots\AND E_s{=}o_s)$ \\
\>{\bf Given} \>\>multiset of contextual contribution {\genrool}s\\
%\>\>\>elimination ordering $ Y_1,\ldots,Y_k$:\\
\>1.\>Incorporate evidence as in Section \ref{hybrid-evidence}.\\
\>2.\>While there is a factor involving a non-query variable\\
\>\>\>\>Select non-query variable $Y$ to eliminate;\\
\>\>\>\>Call $eliminate(Y)$.\\
%2.\>\>For $i = 1..k$ call $eliminate(Y_i)$.\\
\>3.\>Compute posterior probability for $X$ as in Section \ref{comp-post}
\end{pcode}
\begin{pcode}
{\bf Procedure} \boldmath$eliminate(Y)$:\\
\>{\bf partition} the {\genrool}base $R$ into:\\
\>\>$R^-$ those {\genrool}s that don't involve $Y$\\
\>\>$R^+ = \{r\in R : r$ is a {\genrool} for $Y\}$\\
\>\>$R^* = \{r\in R : r \mbox{ involves } Y$ and $r$ is not a {\genrool} for $Y\}$;\\
\>{\bf for each }$r\in R^*$\\
\>\>{\bf do } $R^+ \leftarrow absorb(R^+,r)$;\\
\>{\bf partition} $R^+$ into:\\
\>\>$R^t = \{r \in R^+ : Y \mbox{ in table of }r\}$\\
\>\>$R_i = \{\rool{b,t}:  \rool{b\AND Y{=}v_i,t}\in R^+ \}$ for each
$1\leq i \leq s$, where $dom(Y)=\{v_1,\ldots,v_s\}$.\\
\>{\bf Return} {\genrool}base $R^- \cup (R_1 \oplus_g \cdots \oplus_g R_s) \cup
\{\rool{b_i,\sum_Y t_i} : \rool{b_i,t_i} \in R^t\}$.
\end{pcode}
\begin{pcode}
$absorb(R,r)$ is defined in Section \ref{avoid-split}.\\
$R_1 \oplus_g R_2$ is defined in Section \ref{otimes-g}.
\end{pcode}

\captn{Contextual Variable Elimination with Absorption}
\label{hybrid-CVE-algo}
\end{figure}

The elimination procedure is called once for
each non-query, non-observed variable. The order in which the
variables are selected is called the {\bf elimination ordering}.
This algorithm does not imply that the elimination ordering
has to be given a priori.

One of the main issues in implementing this algorithm is efficient
indexing for the {\genrool}s. We want to be able to quickly find the
{\genrool}s for $Y$, the {\genrool}s that contain $Y$, and the
compatible {\genrool}s during addition and absorption. If we are given
a prior elimination ordering, we can use the idea of bucket
elimination \cite{Dechter96a}, namely that a {\genrool} can be placed
in the bucket of the earliest variable in the elimination
ordering. When we eliminate $Y$, all of the {\genrool}s that contain
$Y$ are in $Y$'s bucket. If we don't have a prior elimination
ordering, we can keep an inverted list of the {\genrool}s (for each
variable, we have a list of all of the {\genrool}s that are for that
variable and a list of the {\genrool}s that contain that variable). We
then have to maintain these lists as we create new {\genrool}s and
delete old ones. We also want to be able to index the {\genrool}s so that
we can quickly find other {\genrool}s that contain the variable to be
eliminated and have compatible contexts. In our implementation, we
compared all of the {\genrool}s that contain the variable to be
eliminated, and rejected those with incompatible contexts. Ideally, we
should be able to do better than this, but how to do it is an open
question. 

There are a number of choice points in this algorithm:
\begin{itemize}
\item the elimination
ordering.
\item the splitting ordering; when computing residuals, which order
should the variables be split on. This is discussed in Section
\ref{rule-splitting}.
\item  the order that the elements of $R^*$ are absorbed. This
has an impact similar to the choice of multiplication ordering for VE
(when we have to multiply a number of factors, which order should they
be done); sometimes we can have smaller intermediate factors if the
choice is done appropriately. 
\end{itemize}





\section{Empirical Results}\label{emp-res}

An interesting question is whether
there are real examples where the advantage of exploiting contextual
independence outweighs the overhead of maintaining {\genrool}s.

We can easily generate synthetic examples where VE is exponentially
worse than contextual variable elimination (for example, consider a
single variable with $n$, otherwise unconnected, parents, where the decision tree for the
variable only has one instance of each parent variable, and we
eliminate from the leaves). At another extreme, where all contexts are
empty, we get VE with very little overhead. However, if there is a
little bit of CSI, it is possible that we need to have the overhead of
reasoning about variables in the contexts, but get no additional
savings. The role of the empirical results is to investigate whether
it is ever worthwhile trying to exploit context-specific independence,
and what features of the problem lead to more efficient inference.

\subsection{A Pseudo-Natural Example}
While it may seem that we should be able to test whether CVE is
worthwhile for natural examples by comparing it to VE for standard
examples, it isn't obvious that this is meaningful. With the
table-based representations, there is a huge overhead for adding a new
parent to a variable, however there is no overhead for making a
complex function for how a variable depends on its existing
parents. Thus, without the availability of effective algorithms that
exploit contextual independence where there is a small overhead for
adding a variable to restricted contexts, it is arguable that builders
of models will tend to be reluctant to add variables, but will tend to
overfit the function for how a variable depends on its parents. As all
models are approximations it makes sense to consider approximations
to standard models. As we are not testing the approximations
\cite{DeaBou97a,Poole98b}, we will pretend these are the real models.

In this section we produce evidence that there exists networks for
which CVE is better than VE. The sole purpose of this experiment it to
demonstrate that there potentially are problems where it is
worthwhile using CVE. We use an instance of the \emph{water} network \cite{jensen:kjaerulff:olesen:etal:89}
from the Bayesian network repository\footnote{\tt
http://www.cs.huji.ac.il/labs/compbio/Repository/}
where we approximated the conditional probabilities to create
contextual independencies. Full details of how the examples were
constructed are in Appendix \ref{app:experiment}. We collapsed probabilities that were within 0.05 of each other to create
{\genrool}s. The \emph{water} network has 32 variables and the tabular
representation has a table size of $11018$ (after removing variables
from tables that made a difference of less that 0.05). The contextual
belief network representation we constructed had 41 {\genrool}s
and a total table size of $5834$.

\begin{figure}
\begin{center}
\includegraphics[width=\columnwidth]{plot/waterplotlog}
\end{center}
\caption{Scatterplot of runtimes (in msecs) of CVE (x-axis) and VE
(y-axis) for the \emph{water} network. Full details are in 
  Appendix \ref{app:experiment}. }
\label{scatterwater}
\end{figure}


Figure \ref{scatterwater} shows a scatter plot of 60 runs of random
queries\footnote{Note that all of these results are
  statistically significant to some degree. The least significant is
  with $10$ observations,
  that, using the matched-sample t-test (also known as the paired
  t-test), is significant to the 0.2 level for the logarithm of the
  runtimes. The others are significant way below the 0.001 level. The logarithm is appropriate as the difference in the logarithms
  corresponds to the multiplicative speedup.}. There were 20 runs each for 0, 5 and 10 observed
variables. The raw data is presented in Appendix \ref{app:experiment}. The
first thing to notice is that, as the number of observations
increases, inference becomes much faster. CVE was often significantly
faster than VE.  There are a few cases where CVE
was much worse than VE; essentially, given the elimination ordering,
the context-specific independence didn't save us anything in these example, but we had
to pay the overhead of having variables in the context.

\subsection{Randomised Networks}\label{secn:randomgraphs}
In order to see how the algorithm depends on the structure inherent in
the network, we constructed a number of parametrized classes of
networks. We explicitly constructed networks that display contextual
independence, as if there is not contextual independence this
algorithm degenerates to VE.

We have the following parameters for building random networks:
\begin{description}
\item[$n$] the number of variables
\item[$s$] the number of splits (so there will be $n+s$ 
{\genrool}s).
\item[$p$] the probability that a predecessor variable that isn't in
the context of a {\genrool} will be in the
table of the {\genrool}.
\end{description}
The exact algorithm for constructing the examples is given in
Appendix \ref{app:experiment}.

The variable $s$ controls the number of {\genrool}s, and $p$ controls
(probabilistically) the size of the tables. Figure
\ref{scatterall}\footnote{Note that all of these results are
  statistically significant. The least significant is the $s=10$ plot
  that, using the matched-sample t-test (also known as the paired
  t-test), is significant to the 0.05 level for the logarithm of the
  runtimes. The logarithm is appropriate as the difference in the logarithms
  corresponds to the multiplicative speedup.}
shows a scatter plot comparing the runtimes of CVE and VE for $n=30$
and $p=0.2$ and for three different values of $s$, $5$, $10$, and
$15$. 
\begin{figure}
\begin{center}
\includegraphics[width=\columnwidth]{plot/randomlog}
\end{center}
\caption{Scatterplot of runtimes (in seconds) of CVE (x-axis) and VE
(y-axis) for randomised networks}
\label{scatterall}
\end{figure}

%\begin{figure}
%\begin{center}
%\includegraphics[width=0.8\columnwidth]{plot/randomdet.eps}
%\end{center}
%\caption{Detail of Scatterplot of Figure \ref{scatterall} with $CVE < 50 secs$ and $VE < 120 secs$}
%\label{scatterdet}
%\end{figure}

While this may look reasonable, it should be noticed that the number
of splits and the number of different variables in the splits is
strongly correlated in these examples (see Appendix \ref{app:experiment}
for details). However, one of the properties of
CVE is that if a variable does not appear in the body  of any
{\genrool}, it is never added to the context of a constructed
{\genrool}. That is, a variable that only appears in tables,
always stays in tables. Thus it may be conjectured that having fewer
variables appearing in contexts may be good for efficiency.

We carried out another experiment to test this hypothesis. In this
experiment, the
networks were generated as before, however, when we went to split a
context we attempted to first split it using a variable that appears in a
different context before using a variable that didn't appear in a
context. The full details of the algorithms to generate examples and
some example data are given in Appendix \ref{app:experiment}. Figure
\ref{scatterfew} shows a scatter plot of comparing the run times for
CVE and VE for each of the generated examples. With this class of networks CVE is significantly
faster than VE.
\begin{figure}
\begin{center}
\includegraphics[width=\columnwidth]{plot/randomfewlog}
\end{center}
\caption{Scatterplot of runtimes (in seconds) of CVE (x-axis) and VE
(y-axis) for random networks biased towards fewer different variables
  in the contexts.}
\label{scatterfew}
\end{figure}

%\begin{figure}
%\begin{center}
%\includegraphics[width=0.9\columnwidth]{plot/randomfewdet2.eps}
%\end{center}
%\caption{Detail of Scatterplot of Figure \ref{scatterfew} with $CVE <
%30 secs$}% and $VE < 120 secs$} 
%\label{scatterfewdet1}
%\end{figure}

%\begin{figure}
%\begin{center}
%\includegraphics[width=0.9\columnwidth]{plot/randomfewdet1.eps}
%\end{center}
%\caption{Detail of Scatterplot of Figure \ref{scatterfew} with $CVE <
%10 secs$}% and $VE < 120 secs$} 
%\label{scatterfewdet2}
%\end{figure}


\section{Comparison With Other Proposals}\label{sec:comparisons}
In this section we compare CVE with other
proposals for exploiting context-specific information.

The belief network with the conditional probability table of Figure
\ref{str-bn} (i.e., with the contextual independence shown in Figure
\ref{gen-rules-str-dt}) is particularly illuminating because other
algorithms do very badly on it.  Under the elimination ordering $B$,
$D$, $C$, $A$, $Y$, $Z$, to find the marginal on $E$, the most
complicated {\genrool} multiset created is the {\genrool} multiset for
$E$ after eliminating $B$ (see Example \ref{elimB-ex}) with a total
table size of 16. Observations simplify the algorithm as they mean
fewer partial evaluations.

In contrast, VE requires a factor with table size 64 after $B$ is
eliminated.  Clique tree propagation constructs two cliques, one
containing $Y,Z,A,B,C,D$ of size $2^6 = 64$, and the other containing
$A,B,C,D,E$ of size 32. Neither takes the structure of the
conditional probabilities into account. 

Note however, that VE and clique tree propagation manipulate tables
which can be indexed much faster than we can manipulate {\genrool}s. There
are cases where the total size of the tables of the {\genrool}s is
exponentially smaller than the tables 
(where added variables are only relevant in narrow contexts).  There
are other cases where the table size for the {\genrool}s is
the same as the table size in VE, and where the overhead for
manipulating contexts will not make CVE competitive with the table-based
methods.

%Boutilier \emph{et al.}\ \citeyear{BouFriGolKol96a}
\citeasnoun{BouFriGolKol96a}
present two
algorithms to exploit structure.  For the network transformation and
clustering method, the example of Figure \ref{str-bn} is the worst case; no structure
can be exploited after triangulation of the resulting graph. (The tree
for $E$ in Figure \ref{str-dt} is structurally identical to the tree for
$X(1)$ in Figure 2 of \cite{BouFriGolKol96a}). The structured cutset
conditioning algorithm does well on this example. However, if the
example is changed so that there are multiple (disconnected) copies of
the same graph, the cutset conditioning algorithm is exponential in
the number of copies, whereas the probabilistic partial evaluation
algorithm is linear\footnote{This does not mean that all conditioning
algorithms need suffer from this. We conjecture that there is
a conditioning algorithm that can extend contextual VE but save
space, as in other bucket elimination algorithms \cite{Dechter96a} or
the relevant cutsets for probabilistic inference \cite{Darwiche95a,Diez96a}.}.

This algorithm is most closely related to the tree-based algorithms for
solving MDPs \cite{BouDeaGol95a}, but these work with much more
restricted networks and with stringent assumptions on what is
observable. CVE is simpler than the analogous algorithm by
\citeasnoun{Boutilier97a} for structured MDP with correlated action
effects that represents conditional probabilities as trees. Section
\ref{why-rules} shows why we can do better than the tree-based algorithms.

\citeasnoun{Poole97a} gave an earlier version of rule-based VE, but it
is
more complicated in that it distinguished between the head and the
body of rules as part of the inference (although the {\genrool}s
\emph{for} $X$ correspond to the rules with $X$ in the head). CVE is
much more efficient than the rule-based VE as it allows for faster
indexing of tables. The notion of $absorption$ was introduced by
\citeasnoun{Zhang98a}, which motivated the work in a very different
way.  \citeasnoun{ZhaPoo99a} give a mathematical analysis of how
context-specific independence can be exploited in terms of partial
functions. The union-product is a formalization of the operation we
are using between {\genrool}s. The current paper extends all of these
in giving a specific algorithm showing how to combine the {\genrool}s
and tables, gives a more general analysis of when we need to do
{\genrool} splitting and when we don't need to, gives a more
sophisticated method to initialize absorption (maintaining the
{\genrool}s for a variable) and gives a much more detailed empirical
evaluation (with a new implementation). The ability to handle ones is also improved.

Finally the representation should be contrasted with that of
\citeasnoun{GeiHec96a}. They use a similarity network that gives a
global decomposition of a belief network; for different contexts they
allow for different belief networks. We allow for a local
decomposition of conditional probabilities. The algorithms are not
very similar.

\section{Conclusion}\label{conclusion}
This paper has presented a method for computing posterior
probabilities in belief networks that exhibit context-specific
independence. This algorithm is an instance of variable elimination,
but when we sum out a variable the tables produced may depend on
different sets of variables in different contexts. 

The main open problem is in finding good heuristics for elimination
orderings \cite{BerBri72b}. Finding a good elimination ordering is
related to finding good triangulations in building compact junction
trees, for which there are good heuristics
\cite{Kjaerulff90a,BecGei96a}.  These are not directly applicable to
contextual variable elimination (although there are analogous
heuristics that are applicable), as an important criteria in this case
is the exact form of the {\genrool}s, and not just the graphical structure
of the belief network. This means that it is not feasible to compute
the elimination ordering a priori. We are also investigating anarchic
orderings where we eliminate a variable in some contexts, without
eliminating it in every context before we partially eliminate another
variable. We believe that this opportunistic elimination of variables
in contexts has much potential to improve efficiency without affecting
correctness.

One of the main potential benefits of this algorithm is in
approximation algorithms, where the {\genrool}s allow fine-grained
control over distinctions. Complementary {\genrool}s with similar
probabilities can be collapsed into a simpler {\genrool}. This can
potentially lead to
more compact {\genrool} bases, and reasonable posterior ranges
\cite{DeaBou97a,Poole98b}.  

The work reported in this paper has been followed up by a number of
researchers. \citeasnoun{Tung02a} has shown how to exploit
context-specific independence in clique
trees. \citeasnoun{GueVenKoll02a} extended the contextual variable
elimination to multi-agent coordination and planning.

\section*{Acknowledgements}
This work was supported by the Institute for Robotics and Intelligent
Systems, Natural Sciences and Engineering Research Council of
Canada Research Grant OGPOO44121 and Hong Kong Research Grants Council
    grant HKUST6093/99E. Thanks to Rita Sharma, Holger Hoos, Michael
Horsch and the anonymous reviewers for valuable comments, and to
Valerie McRae for careful proofreading. The code is available from the
first author.

\T\appendix
\section{Details of the experiments}\label{app:experiment}
\subsection{Water Network}
In order to construct a pseudo-natural example, we used the \emph{water}
network from the Bayesian network
repository\footnote{\url{http://www.cs.huji.ac.il/labs/compbio/Repository/}}
and modified it to let it exhibit context-specific independence. For
each table, a variable was declared redundant if the differences in
the probabilities for the values of this variable were less than a
threshold of 0.05
from each other (thus, if we chose the midpoint of a reduced table,
the original probabilities were all less than 0.025 from this
midpoint). In order to discover context-specific independence, we
carried out a greedy top-down algorithm to build a decision tree. If
we are building the conditional for variable $X_i$, we
chose the variable $Y$ to split on that results in the maximum number
of pairs of numbers where the values for $X_i$ are within the
threshold 0.05 of
each other. We then recursively remove redundant variables from each
side, and keep splitting. Once we have built a tree, for each node, we
can decide whether to use the tabular representation or a factored
representation. In these experiments, we only committed to the
context-based representation when the total size of the context-based
representation (obtained simply by summing the sizes of the tables)
was less than 51\% of the tabular representation. 

It should be noted that these thresholds were not chosen
arbitrarily. If we used 0.03 instead of 0.05, we didn't find any
context-specific independence. If we chose 0.07 instead of 0.05, then
the tabular representation collapses.  If we chose 80\% or 99\%
instead of 51\% as the threshold for accepting a change, we got
smaller tables, but much larger run times.

Figure \ref{fig:water0obs} shows some of the details of some of the
data with no observations. Figures \ref{fig:water5obs} and
\ref{fig:water10obs} shows some of the details of some of the data
with 5 and 10 observation respectively. These make up the data shown
in Figure %\ref{scatterwater}. 
10 of the main paper.
We show the
index of the variable given the ordering in the repository (we started
counting at 0).

All of the times are in milliseconds for a Java
implementation running on 700 MHz Pentium running Linux with 768
megabytes of memory. In order to allow for the variation in run times
due to garbage collection each evaluation was run three times and the
smallest time was returned.  The space is for the maximum table
created in VE or the maximum size of the sum of all of the {\genrool}s
created during the elimination of one variable.

\begin{figure}
\begin{center}
\begin{tabular}{|l|rr|rr|}\hline
& \multicolumn{2}{c|}{CVE} & \multicolumn{2}{c|}{VE} \\
Query Var & Time & Size & Time & Size \\\hline
 \#11(CKND\_12\_15)  &   15039 & 1327104 &   25368 & 5308416 \\
 \#13(CBODN\_12\_15)  &   620 & 16384 &   4552 & 442368 \\
 \#27(CKND\_12\_45)  &   3808 & 186624 &   53965 & 15925248 \\
 \#25(CKNI\_12\_45)  &   1708 & 36864 &   57414 & 7077888 \\
 \#22(CKNN\_12\_30)  &   367 & 16128 &   3821 & 442368 \\
 \#21(CBODN\_12\_30)  &   7953 & 193536 &   13997 & 1769472 \\
 \#17(CKNI\_12\_30)  &   742 & 48384 &   3677 & 442368 \\
 \#22(CKNN\_12\_30)  &   363 & 16128 &   3846 & 442368 \\
 \#19(CKND\_12\_30)  &   7939 & 774144 &   26654 & 2359296 \\
 \#15(CNON\_12\_15)  &   8177 & 193536 &   14599 & 1769472 \\
 \#12(CNOD\_12\_15)  &   618 & 37044 &   4264 & 442368 \\
 \#3(CKND\_12\_00)  &   419 & 29376 &   9414 & 1327104 \\
 \#16(C\_NI\_12\_30)  &   429 & 28224 &   3799 & 442368 \\
 \#30(CKNN\_12\_45)  &   2902 & 112896 &   52648 & 15925248 \\
 \#4(CNOD\_12\_00)  &   2496 & 110592 &   42270 & 5308416 \\
 \#21(CBODN\_12\_30)  &   8042 & 193536 &   13619 & 1769472 \\
 \#5(CBODN\_12\_00)  &   992 & 112320 &   3334 & 442368 \\
 \#19(CKND\_12\_30)  &   7936 & 774144 &   25637 & 2359296 \\
 \#11(CKND\_12\_15)  &   16290 & 1327104 &   24753 & 5308416 \\
 \#23(CNON\_12\_30)  &   604 & 37044 &   3535 & 442368 \\\hline
\end{tabular}
\end{center}
\caption{Data for random queries with no observed variables
for the \emph{water} network}
\label{fig:water0obs}
\end{figure}

\begin{figure}
\begin{center}
\begin{tabular}{|l|l|rr|rr|}\hline
 && \multicolumn{2}{c|}{CVE} & \multicolumn{2}{c|}{VE} \\
Observed & Query Var & Time & Size & Time &
Size\\\hline
  \#1=2 \#2=2 \#26=2 \#28=1 \#30=1 & \#8(C\_NI\_12\_15)  &   84 & 9216 &   579 & 36864 \\
  \#6=2 \#8=1 \#11=2 \#14=2 \#24=1 & \#22(CKNN\_12\_30)  &   15 & 816 &   156 & 9216 \\
  \#8=3 \#14=0 \#15=3 \#18=3 \#20=2 & \#6(CKNN\_12\_00)  &   9 & 336 &   26 & 2304 \\
  \#5=1 \#9=0 \#12=2 \#15=0 \#16=3 & \#10(CBODD\_12\_15)  &   54 & 576 &   71 & 6912 \\
  \#6=1 \#7=0 \#11=1 \#13=3 \#25=2 & \#27(CKND\_12\_45)  &   1184 & 28224 &   3210 & 147456 \\
  \#2=1 \#6=0 \#13=0 \#19=1 \#25=0 & \#18(CBODD\_12\_30)  &   123 & 9216 &   224 & 12288 \\
  \#0=3 \#2=1 \#18=2 \#20=1 \#23=1 & \#17(CKNI\_12\_30)  &   16 & 1728 &   87 & 5184 \\
  \#4=3 \#10=3 \#12=3 \#17=0 \#28=2 & \#6(CKNN\_12\_00)  &   284 & 6912 &   162 & 20736 \\
  \#3=1 \#11=1 \#19=1 \#25=1 \#31=3 & \#14(CKNN\_12\_15)  &   1450 & 36864 &   1041 & 147456 \\
  \#10=3 \#19=0 \#21=0 \#26=0 \#27=0 & \#16(C\_NI\_12\_30)  &   1076 & 49152 &   521 & 49152 \\
  \#11=1 \#13=0 \#21=1 \#25=2 \#29=2 & \#24(C\_NI\_12\_45)  &   353 & 28080 &   13928 & 1327104 \\
  \#3=0 \#23=1 \#26=1 \#27=0 \#28=3 & \#15(CNON\_12\_15)  &   14258 & 193536 &   2600 & 442368 \\
  \#9=2 \#10=1 \#13=1 \#25=2 \#26=1 & \#30(CKNN\_12\_45)  &   75 & 9216 &   2646 & 248832 \\
  \#9=1 \#11=0 \#14=2 \#15=1 \#27=0 & \#25(CKNI\_12\_45)  &   65 & 4096 &   120 & 4096 \\
  \#2=0 \#10=2 \#15=2 \#17=1 \#24=1 & \#8(C\_NI\_12\_15)  &   12 & 576 &   767 & 110592 \\
  \#2=0 \#7=3 \#15=1 \#21=2 \#27=2 & \#16(C\_NI\_12\_30)  &   29 & 1008 &   531 & 82944 \\
  \#0=3 \#2=0 \#6=0 \#7=2 \#16=2 & \#29(CBODN\_12\_45)  &   7 & 336 &   1304 & 147456 \\
  \#2=2 \#20=2 \#24=2 \#25=0 \#30=0 & \#21(CBODN\_12\_30)  &   453 & 49152 &   877 & 49152 \\
  \#8=2 \#11=2 \#19=2 \#25=1 \#29=3 & \#9(CKNI\_12\_15)  &   76 & 9216 &   216 & 9216 \\
  \#9=1 \#12=3 \#13=0 \#19=2 \#21=3 & \#26(CBODD\_12\_45)  &  
31 & 1024 &   440 & 49152 \\\hline
\end{tabular}
\end{center}
\caption{Data for random queries with 5 randomly observed variables
for the \emph{water} network}
\label{fig:water5obs}
\end{figure}

\begin{figure}
\begin{center}

\begin{tabular}{|l|l|rr|rr|}\hline
&&  \multicolumn{2}{c|}{CVE} & \multicolumn{2}{c|}{VE} \\
Observed & Query & Time & Size & Time & Size \\\hline
 \#2=3 \#3=0 \#7=2 \#12=1 \#13=2 &&&&&\\
\#19=1 \#21=2 \#22=2 \#26=1 \#30=1 & \#14  &   30 & 2304 &   40 & 2304 \\
  \#0=0 \#3=0 \#8=3 \#12=3 \#13=0 &&&&&\\
\#16=2 \#18=2 \#26=3 \#27=2 \#28=1 & \#7  &   14 & 256 &   17 & 768 \\
  \#1=2 \#6=0 \#8=0 \#11=2 \#17=0 &&&&&\\
\#20=3 \#22=1 \#23=1 \#24=2 \#26=2 & \#25  &   7 & 256 &   7 & 256 \\
  \#2=2 \#5=3 \#8=0 \#9=1 \#10=1 &&&&&\\
\#17=2 \#18=1 \#22=2 \#28=0 \#30=1 & \#23  &   4 & 192 &   4 & 192 \\
  \#4=2 \#7=1 \#8=2 \#12=1 \#13=2 &&&&&\\
\#15=3 \#17=0 \#19=0 \#22=2 \#31=2 & \#28  &   10 & 256 &   8 & 256 \\
  \#1=1 \#7=1 \#9=1 \#10=0 \#11=0 &&&&&\\
\#13=3 \#14=1 \#23=1 \#24=1 \#30=2 & \#22  &   9 & 336 &   10 & 768 \\
  \#2=1 \#4=0 \#6=0 \#15=0 \#18=0 &&&&&\\
\#22=2 \#23=3 \#24=2 \#29=2 \#30=1 & \#25  &   14 & 768 &   31 & 2304 \\
  \#3=0 \#10=0 \#14=1 \#16=3 \#19=0 &&&&&\\
\#24=1 \#25=2 \#28=3 \#30=1 \#31=1 & \#7  &   544 & 9216 &   121 & 9216 \\
  \#1=2 \#2=3 \#3=1 \#9=2 \#10=0 &&&&&\\
\#14=0 \#16=3 \#25=1 \#28=3 \#30=2 & \#8  &   10 & 1024 &   16 & 1024 \\
  \#2=3 \#5=1 \#6=0 \#11=2 \#12=0 &&&&&\\
\#17=1 \#22=0 \#24=3 \#27=0 \#28=1 & \#25  &   22 & 768 &   22 & 768 \\
  \#8=3 \#9=2 \#10=0 \#11=1 \#12=1 &&&&&\\
\#14=2 \#15=3 \#19=0 \#22=2 \#26=3 & \#5  &   3 & 84 &   4 & 192 \\
  \#1=0 \#7=2 \#8=2 \#13=0 \#15=3 &&&&&\\
\#17=2 \#20=3 \#26=1 \#27=0 \#31=3 & \#24  &   11 & 256 &   8 & 256 \\
  \#4=2 \#5=3 \#6=1 \#9=1 \#10=0 &&&&&\\
\#12=2 \#17=0 \#19=1 \#25=0 \#29=0 & \#23  &   6 & 256 &   23 & 1024 \\
  \#0=0 \#2=1 \#11=1 \#13=1 \#17=2 &&&&&\\
\#21=3 \#22=1 \#23=1 \#24=2 \#30=2 & \#27  &   10 & 576 &   18 & 768 \\
  \#4=1 \#9=0 \#10=0 \#11=1 \#12=2 &&&&&\\
\#23=1 \#25=2 \#29=1 \#30=0 \#31=2 & \#5  &   77 & 4096 &   141 & 12288 \\
  \#1=2 \#6=0 \#7=1 \#10=3 \#12=1 &&&&&\\
\#15=3 \#16=1 \#17=2 \#23=2 \#24=1 & \#27  &   3 & 64 &   4 & 144 \\
  \#1=2 \#2=2 \#3=2 \#5=2 \#9=2 &&&&&\\
\#13=1 \#15=0 \#22=1 \#25=2 \#30=0 & \#18  &   4 & 112 &   65 & 12288 \\
  \#0=3 \#1=1 \#5=1 \#6=0 \#7=1 &&&&&\\
\#8=2 \#15=3 \#17=0 \#24=3 \#25=0 & \#21  &   76 & 768 &   16 & 1024 \\
  \#0=2 \#6=1 \#8=0 \#9=2 \#10=2 &&&&&\\
\#16=0 \#18=0 \#19=0 \#21=0 \#26=0 & \#13  &   7 & 576 &   12 & 768 \\
  \#1=1 \#3=0 \#4=2 \#9=1 \#10=3 &&&&&\\
\#13=0 \#14=2 \#22=0 \#23=0 \#30=2 & \#6  &   37 & 768 &   17 & 768\\\hline
\end{tabular}
\end{center}
\caption{Data for random queries with 10 randomly observed variables
for the \emph{water} network}
\label{fig:water10obs}
\end{figure}

\subsection{Randomised Experiments}
The following procedure was used to generate the random networks.
Given the $n$ variables, we impose a total ordering. We build a
decision tree for each variable. The leaves of the decision trees
correspond to contexts and a variable that the tree is for. We start
with the empty decision tree for each variable. We randomly (with uniform
probability) choose a leaf and a variable. If the variable is a
possible split (i.e., it is a predecessor in the total ordering of the
variable the leaf is for and the context corresponding to the leaf
doesn't commit a value to that variable), we split that leaf on that
variable. This is repeated until we have $n+s$ leaves.  Then for each
leaf, we built a {\genrool} that has the same context and each
predecessor of the variable that the leaf is for is included in the
{\genrool} with probability $p$. The variable that the leaf is
for is also in the {\genrool}. We assign random numbers the
probabilities (these numbers won't affect anything in the results
assuming that the times for operations on floating point numbers isn't
affected by the actual values of the numbers).

The algorithm to construct the random examples used in Section
%\ref{secn:randomgraphs} 
6.2 is given in Figure \ref{algo:randex}. Note
that ``choose random'' means to choose randomly from a uniform distribution.

\begin{figure}
\begin{pcode}
$generate\_random\_CBN(n,s,p):$\\
\>create $n$ Boolean variables $X_1,\dots,X_n$\\
\>Let $S = \{\tuple{\{\},X_i}: i \leq i \leq n\}$\\
\>\>\pcodecomm{$S$ is a set of context-variable pairs}\\
\>{\bf repeat}\\
\>\>choose random $\tuple{c,X_i}\in S$\\
\>\>choose random $j$ such that $1\leq j < n$\\
\>\>{\bf if} $j<i$ and $X_j$ doesn't appear in $c$:\\
\>\>\>replace $\tuple{c,X_i}\in S$ with $\tuple{c\wedge X_j=true,X_i}$
and $\tuple{c\wedge X_j=false,X_i}$\\
\>{\bf until} there are $n+s$ elements of $S$\\
\>{\bf for each} $\tuple{c,X_i}\in S$\\
\>\>Let $V=\{X_i\}$\\
\>\>{\bf for each} $j<i$\\
\>\>\>{\bf if} $X_j$ doesn't appear in $c$\\
\>\>\>\>with probability $p$ add $X_j$ to $V$\\
\>\>create a random table $T$ on the variables in $V$\\
\>\>add {\genrool} $\tuple{c,T}$ to the contextual belief network
\end{pcode}

\caption{Algorithm for constructing the randomised examples}
\label{algo:randex}
\end{figure}

For the examples biased towards using fewer variables, we replaced the line:
\begin{pcode}
\>replace $\tuple{c,X_i}\in S$ with $\tuple{c\wedge X_j=true,X_i}$
and $\tuple{c\wedge X_j=false,X_i}$\\
\end{pcode}
with
\begin{pcode}
\>{\bf if} there is $k<i$ such that $X_k$ doesn't appear
in $c$ and $X_k$ is used in another context\\
\>\>{\bf then}\\
\>\>\>replace $\tuple{c,X_i}\in S$ with $\tuple{c\wedge X_k=true,X_i}$
and $\tuple{c\wedge X_k=false,X_i}$\\
\>\>{\bf else}\\
\>\>\>replace $\tuple{c,X_i}\in S$ with $\tuple{c\wedge X_j=true,X_i}$
and $\tuple{c\wedge X_j=false,X_i}$
\end{pcode}
where, if more than one such $k$ exists, the $k$ is chosen uniformly from all of the values that satisfy
the condition.

Figure \ref{randomdata} shows some of the details of some of the data shown in
Figure 11. %\ref{scatterdet}. 
All of the times are for a Java
implementation running on a 700 MHz Pentium
running Linux with 768 megabytes of memory. In order to allow for the
variation in run times due to garbage collection, each evaluation was
run three times and the smallest time was returned.
\begin{figure}
\begin{center}
\begin{tabular}{|rrr|rr|rr|rr|}\hline
$n$ & $s$ & $p$ & CBN & BN &\multicolumn{2}{c|}{CVE} & \multicolumn{2}{c|}{VE}\\
 &  &  & Size & Size & Time
& MTS& Time & MTS\\\hline
\begin{comment} 
30 & 5 (5) & 0.2 & 2014 & 263844 & 5739 & 131072 & 2183 & 131072 \\
30 & 5 (5) & 0.2 & 5772 & 37528 & 23057 & 524288 & 15236 & 1048576 \\
30 & 5 (5) & 0.2 & 836 & 3972 & 2985 & 122880 & 5205 & 262144 \\
30 & 5 (5) & 0.2 & 2138 & 38118 & 7381 & 131072 & 3362 & 131072 \\
30 & 5 (4) & 0.2 & 1620 & 5400 & 5215 & 262144 & 5027 & 262144 \\
30 & 5 (4) & 0.2 & 10612 & 69856 & 1722 & 131072 & 2197 & 131072 \\
30 & 5 (5) & 0.2 & 2122 & 7186 & 377 & 16384 & 489 & 32768 \\
30 & 5 (5) & 0.2 & 2588 & 17970 & 32803 & 262144 & 5284 & 262144 \\
30 & 5 (5) & 0.2 & 1262 & 4782 & 386 & 14336 & 343 & 16384 \\
30 & 5 (5) & 0.2 & 1298 & 15052 & 14114 & 524288 & 18491 & 1048576 \\
30 & 10 (8) & 0.2 & 1746 & 41982 & 6431 & 294912 & 10716 & 524288 \\
30 & 10 (8) & 0.2 & 3382 & 11636 & 6610 & 131072 & 6375 & 524288 \\
30 & 10 (9) & 0.2 & 3472 & 175636 & 53271 & 2162688 & 56210 & 8388608 \\
30 & 10 (8) & 0.2 & 3016 & 45028 & 7544 & 491520 & 7393 & 524288 \\
30 & 10 (8) & 0.2 & 1066 & 19616 & 7347 & 65536 & 1613 & 65536 \\
30 & 10 (8) & 0.2 & 1510 & 39826 & 2550 & 163840 & 6543 & 524288 \\
30 & 10 (8) & 0.2 & 5198 & 15722 & 9829 & 229376 & 7500 & 524288 \\
30 & 10 (9) & 0.2 & 3974 & 16877222 & 121749 & 5636096 & 361042 & 16777216 \\
30 & 10 (10) & 0.2 & 2140 & 26240 & 3580 & 117760 & 6342 & 524288 \\
30 & 10 (6) & 0.2 & 2946 & 38738 & 6258 & 458752 & 8567 & 524288 \\
30 & 15 (14) & 0.2 & 2272 & 235368 & 291405 & 5029888 & 368796 & 16777216 \\
30 & 15 (12) & 0.2 & 3004 & 660442 & 68797 & 1310720 & 63729 & 2097152 \\
30 & 15 (13) & 0.2 & 2430 & 8408726 & 123084 & 2325120 & 237570 & 8388608 \\
30 & 15 (11) & 0.2 & 2826 & 300208 & 168290 & 3670016 & 148848 & 4194304 \\
30 & 15 (9) & 0.2 & 5718 & 1610976 & 55607 & 1490944 & 157460 & 8388608 \\
30 & 15 (11) & 0.2 & 3014 & 4346738 & 41176 & 1736704 & 38819 & 2097152 \\
30 & 15 (12) & 0.2 & 2968 & 61382 & 49387 & 1032192 & 39255 & 1048576 \\
30 & 15 (11) & 0.2 & 2268 & 284702 & 22612 & 589824 & 27426 & 4194304 \\
30 & 15 (9) & 0.2 & 4626 & 299906 & 9894 & 262144 & 20247 & 1048576 \\
30 & 15 (12) & 0.2 & 2170 & 287724 & 52122 & 983040 & 32771 & 2097152 \\
30 & 20 (13) & 0.2 & 2452 & 191240 & 32298 & 573440 & 55211 & 2097152 \\
30 & 20 (14) & 0.2 & 3368 & 2703972 & 923518 & 8388608 & 499830 & 8388608 \\
30 & 20 (15) & 0.2 & 1756 & 109412 & 54366 & 674688 & 36669 & 4194304 \\
30 & 20 (14) & 0.2 & 4414 & 3416726 & 156197 & 2018304 & 79918 & 8388608 \\
30 & 20 (17) & 0.2 & 4638 & 17063998 & 111721 & 1048576 & 308817 & 8388608 \\
30 & 20 (15) & 0.2 & 2304 & 1623092 & 427310 & 1167360 & 86716 & 4194304 \\
30 & 20 (14) & 0.2 & 6866 & 33580222 & 286475 & 8388608 & 362249 & 16777216 \\
30 & 20 (13) & 0.2 & 2798 & 349650 & 71554 & 662016 & 115248 & 4194304 \\
30 & 20 (13) & 0.2 & 3036 & 220658 & 77251 & 819200 & 68048 & 2097152 \\
30 & 20 (14) & 0.2 & 2538 & 336562 & 45191 & 299584 & 55639 & 2097152 \\
\end{comment}
30 & 5 (5) & 0.2 & 10922 & 8398266 & 31388 & 2097152 & 84801 & 4194304 \\
30 & 5 (5) & 0.2 & 1846 & 132692 & 9653 & 393216 & 12418 & 524288 \\
30 & 5 (5) & 0.2 & 1964 & 13456 & 2022 & 131072 & 3748 & 131072 \\
30 & 5 (5) & 0.2 & 1600 & 4908 & 3922 & 196608 & 5572 & 524288 \\
30 & 5 (5) & 0.2 & 1668 & 8292 & 60304 & 614400 & 61612 & 2097152 \\
30 & 5 (5) & 0.2 & 904 & 1906 & 637 & 32768 & 1005 & 65536 \\
30 & 5 (5) & 0.2 & 1738 & 10786 & 720 & 42048 & 1340 & 131072 \\
30 & 5 (4) & 0.2 & 1744 & 18538 & 2223 & 131072 & 2546 & 262144 \\
30 & 5 (4) & 0.2 & 3060 & 87292 & 11681 & 524288 & 12298 & 1048576 \\
30 & 5 (3) & 0.2 & 2692 & 69602 & 5325 & 262144 & 9530 & 524288 \\
30 & 10 (9) & 0.2 & 3842 & 530622 & 22288 & 524288 & 31835 & 2097152 \\
30 & 10 (9) & 0.2 & 1262 & 36070 & 4063 & 147456 & 11038 & 524288 \\
30 & 10 (10) & 0.2 & 3908 & 80704 & 112537 & 1966080 & 31214 & 4194304 \\
30 & 10 (8) & 0.2 & 4904 & 33568176 & 81450 & 5111808 & 203284 & 16777216 \\
30 & 10 (7) & 0.2 & 10456 & 314126 & 31627 & 589824 & 44079 & 2097152 \\
30 & 10 (8) & 0.2 & 1790 & 28758 & 1590 & 98304 & 2974 & 262144 \\
30 & 10 (9) & 0.2 & 2054 & 24452 & 13642 & 262144 & 5253 & 262144 \\
30 & 10 (8) & 0.2 & 3608 & 58352 & 24948 & 819200 & 18574 & 1048576 \\
30 & 10 (9) & 0.2 & 6392 & 1188654 & 403347 & 5767168 & 359992 & 33554432 \\
30 & 10 (8) & 0.2 & 6180 & 42344 & 10078 & 253952 & 17501 & 1048576 \\
30 & 15 (10) & 0.2 & 2724 & 2104338 & 56636 & 1572864 & 49316 & 2097152 \\
30 & 15 (11) & 0.2 & 5896 & 8425520 & 185925 & 6389760 & 260645 & 16777216 \\
30 & 15 (11) & 0.2 & 2096 & 2239982 & 27065 & 825344 & 42180 & 2097152 \\
30 & 15 (12) & 0.2 & 3674 & 39928 & 6393 & 360448 & 9631 & 524288 \\
30 & 15 (11) & 0.2 & 2388 & 552768 & 8623 & 425984 & 13641 & 524288 \\
30 & 15 (11) & 0.2 & 1938 & 49388 & 11299 & 438272 & 27303 & 2097152 \\
30 & 15 (13) & 0.2 & 4188 & 351374 & 18602 & 432776 & 38843 & 2097152 \\
30 & 15 (12) & 0.2 & 2806 & 111632 & 3213 & 138240 & 5463 & 1048576 \\
30 & 15 (12) & 0.2 & 3512 & 126464 & 16118 & 258048 & 11479 & 1048576 \\
30 & 15 (10) & 0.2 & 1700 & 541498 & 5986 & 172032 & 8414 & 524288 \\

\hline
\end{tabular}
\end{center}
\caption{Comparisons of random networks that exhibit CSI.}
\label{randomdata}
\end{figure}

For each generated example, the table of Figure \ref{randomdata} shows
\begin{itemize}
\item $n$ the number of variables
\item $s$ the number of splits and, in parentheses, the number of different
variables on which the splits occur (different leaves can be split on
the same variable).
\item $p$ the probability of splitting on a variable it is possible to
split on.
\item CBN size: the total size (summing over the size of the tables)
of the contextual belief network representation.
\item BN size: the total size of the factors for the corresponding belief
network (i.e., assuming the probabilities are stored in tables).
\item CVE time is the runtime (in msecs) of contextual variable
elimination and CVE MTS is the maximum sum of the table sizes created for the
elimination of a single variable.
\item VE time: the runtime (in msecs) of variable
elimination and VE MTS is the maximum table size created for the
elimination of a single variable.
\end{itemize}


\begin{comment}
\begin{figure}
\begin{center}
\begin{tabular}{|rrr|rr|rr|rr|}\hline
$n$ & $s$ & $p$ & CBN & BN &  \multicolumn{2}{c|}{CVE} & \multicolumn{2}{c|}{VE}\\
 &  &  & Size & Size & Time
& MTS& Time & MTS\\\hline
30 & 5 (3) & 0.2 & 3244 & 28012 & 29001 & 1179648 & 44604 & 2097152 \\
30 & 5 (1) & 0.2 & 2490 & 35058 & 7421 & 262144 & 8382 & 262144 \\
30 & 5 (2) & 0.2 & 3412 & 22990 & 8292 & 786432 & 11686 & 1048576 \\
30 & 5 (2) & 0.2 & 3462 & 100646 & 1312 & 65536 & 2043 & 131072 \\
30 & 5 (2) & 0.2 & 1402 & 2312 & 270 & 16384 & 270 & 16384 \\
30 & 5 (2) & 0.2 & 2146 & 9146 & 1081 & 65536 & 1683 & 131072 \\
30 & 5 (2) & 0.2 & 4922 & 2101710 & 37093 & 2097152 & 41489 & 2097152 \\
30 & 5 (2) & 0.2 & 1604 & 50340 & 470 & 40960 & 902 & 65536 \\
30 & 5 (1) & 0.2 & 3606 & 5398 & 1693 & 67584 & 1693 & 131072 \\
30 & 5 (2) & 0.2 & 1324 & 7724 & 200 & 16384 & 240 & 16384 \\
30 & 10 (3) & 0.2 & 3396 & 106424 & 8833 & 360448 & 31846 & 4194304 \\
30 & 10 (1) & 0.2 & 4234 & 49824 & 6289 & 524288 & 30144 & 1048576 \\
30 & 10 (4) & 0.2 & 3490 & 170406 & 20459 & 655360 & 51574 & 2097152
\\
\hline
\end{tabular}
\end{center}
\caption{Comparisons of random networks that exhibit CSI and prefer
fewer variables is splits.}
\end{figure}
\end{comment}
\begin{figure}
\begin{center}
\begin{tabular}{|rrr|rr|rr|rr|}\hline
$n$ & $s$ & $p$ & CBN & BN & \multicolumn{2}{c|}{CVE} & \multicolumn{2}{c|}{VE}\\
 &  &  & Size & Size & Time
& MTS& Time & MTS\\\hline
30 & 5 (3) & 0.2 & 1602 & 3658 & 662 & 49152 & 604 & 65536 \\
30 & 5 (2) & 0.2 & 6108 & 7240 & 1583 & 131072 & 1945 & 131072 \\
30 & 5 (2) & 0.2 & 17526 & 19632 & 6754 & 393216 & 8833 & 1048576 \\
30 & 5 (2) & 0.2 & 892 & 4164 & 1604 & 81920 & 3119 & 131072 \\
30 & 5 (1) & 0.2 & 1540 & 2640 & 261 & 16512 & 457 & 32768 \\
30 & 5 (2) & 0.2 & 1156 & 5572 & 608 & 40960 & 816 & 65536 \\
30 & 5 (2) & 0.2 & 2344 & 68676 & 12462 & 1048576 & 9370 & 1048576 \\
30 & 5 (1) & 0.2 & 1406 & 7284 & 2197 & 81920 & 4021 & 262144 \\
30 & 5 (3) & 0.2 & 7740 & 209652 & 17736 & 851968 & 18279 & 2097152 \\
30 & 5 (2) & 0.2 & 4184 & 8838 & 8053 & 528384 & 16437 & 1048576 \\
30 & 10 (3) & 0.2 & 3038 & 1119562 & 30669 & 1048576 & 53732 & 2097152 \\
30 & 10 (3) & 0.2 & 888 & 5176 & 565 & 24576 & 2625 & 131072 \\
30 & 10 (2) & 0.2 & 3372 & 4222408 & 21834 & 917504 & 108732 & 4194304 \\
30 & 10 (3) & 0.2 & 2240 & 30968 & 20308 & 524800 & 129885 & 4194304 \\
30 & 10 (2) & 0.2 & 1106 & 11660 & 741 & 32768 & 433 & 65536 \\
30 & 10 (2) & 0.2 & 778 & 4582 & 274 & 18432 & 656 & 65536 \\
30 & 10 (3) & 0.2 & 1888 & 72260 & 6659 & 262144 & 11986 & 524288 \\
30 & 10 (2) & 0.2 & 9740 & 413892 & 11271 & 868352 & 179564 & 8388608 \\
30 & 10 (2) & 0.2 & 1102 & 7744 & 313 & 16384 & 1395 & 65536 \\
30 & 10 (3) & 0.2 & 4078 & 298438 & 61140 & 1048576 & 79858 & 4194304 \\
30 & 15 (2) & 0.2 & 2710 & 50698 & 8845 & 524288 & 39265 & 2097152 \\
30 & 15 (3) & 0.2 & 1246 & 84836 & 1935 & 90112 & 3652 & 262144 \\
30 & 15 (3) & 0.2 & 2046 & 75956 & 54571 & 1310720 & 141386 & 8388608 \\
30 & 15 (2) & 0.2 & 1588 & 138888 & 14280 & 458752 & 43059 & 2097152 \\
30 & 15 (3) & 0.2 & 2260 & 20230 & 522 & 28672 & 1815 & 131072 \\
30 & 15 (4) & 0.2 & 2842 & 67385366 & 322274 & 10485760 & 726989 & 33554432 \\
30 & 15 (3) & 0.2 & 3074 & 533738 & 85480 & 2752512 & 89431 & 8388608 \\
30 & 15 (3) & 0.2 & 1834 & 278426 & 18560 & 753664 & 43554 & 1048576 \\
30 & 15 (3) & 0.2 & 4362 & 209186 & 22872 & 1441792 & 131704 & 4194304 \\
30 & 15 (2) & 0.2 & 3142 & 151160 & 4476 & 164096 & 26426 & 1048576 \\
\hline
\end{tabular}
\end{center}
\caption{Some of the details of data from Figure 12 %\ref{scatterfew}
  (biased towards fewer different variables)} 
\end{figure}


\bibliographystyle{dcu}
%\bibliographystyle{plain}
%\bibliography{../../../bib/reason.string,../../../bib/poole_local_reason,../../../bib/reason}
\bibliography{../../book/bib/string,../../book/bib/poole,../../book/bib/reason}
\end{document}

