\documentstyle[jair,twoside,11pt,theapa]{article}
\input epsf %% at top of file

\jairheading{4}{1996}{37--59}{9/95}{2/96}
\ShortHeadings{Queries \& Updates in Probabilistic Networks}
{Delcher, Grove, Kasif \& Pearl}
\firstpageno{37}

\def\PROB{\mbox{\sl Pr\hskip 0.1em}}
\def\WIN{\mbox{\sc win}}
\def\LOSS{\mbox{\sc loss}}
\def\MAX{\mbox{\sc max}}
\def\MIN{\mbox{\sc min}}
\def\SUM{\mbox{\sc sum}}
\def\EVAL{\mbox{\sl Eval}}
\def\LEFT{\mbox{\sl Left}}
\def\RIGHT{\mbox{\sl Right}}
\def\BEL{\mbox{\sl Bel\,}}
\def\BELOW#1{{\mbox{\scriptsize\it below\hspace{0.1em}}#1}}
\def\PU{p_{u_1}}
\def\PV{p_{u_2}}
\def\PE{p_e}
\newcounter{propctr}
\def\citeauthoryear#1#2{#1, #2}
\def\Dyad{\ast}
\def\Transpose{^{\mbox{\tiny T}}}
\def\Rake{{\sc Rake}}
\def\Raketree{{\sc Contract}}
\def\Calc#1{\mbox{{\sc Calc}$\pi\lambda \, (#1)$}}
\def\A#1#2{A_{#2} ({#1})}
\def\B#1#2{B_{#2} ({#1})}
\def\C#1#2{C_{#2} ({#1})}
\def\D#1#2{D_{#2} ({#1})}
\def\Diag#1{\mbox{Diag}_{#1}}
\def\Index#1{\mbox{\sl ind}\,(#1)}
\def\LambdaForm#1#2#3#4{\A{#1}{#4} \cdot \lambda ({#2})
       \Dyad \B{#1}{#4} \cdot \lambda ({#3})}
\def\LambdaEq#1#2#3#4{\lambda ({#1}) & = & \LambdaForm{#1}{#2}{#3}{#4}}
\def\PiForm#1#2#3#4{\D{#1}{#4} \cdot \left( \pi ({#2})
       \Dyad \C{#1}{#4} \cdot \lambda ({#3}) \right)}
\def\PiEq#1#2#3#4{\pi ({#1}) & = & \PiForm{#1}{#2}{#3}{#4}}
\def\LambdaQuery#1{\mbox{$\lambda$-{\sc Query}~($#1$)}}
\def\LambdaUpdate#1#2#3{\mbox{$\lambda$-{\sc Update}~($#1 = #2, #3$)}}
\newcounter{theoremctr}
\def\Afact#1#2#3{A_{#3}^{#1} ({#2})}
\def\Bfact#1#2#3{B_{#3}^{#1} ({#2})}

\def\NIL{\mbox{\rule{0in}{0in}}}
\def\x{\hspace{0.3em}}
\def\Em#1{{\em #1\/}}
\def\ie{\Em{i.e.}}
\def\Ie{\Em{I.e.}}
\def\eg{\Em{e.g.}}
\def\etal{\Em{et~al}}
\def\etc{\Em{etc}}
\def\bigO{{\cal O}}
\def\bchar#1{{\hspace{0.2em}\bf #1\hspace{0.2em}}}
\def\th{\mbox{\raisebox{1.0ex}{\scriptsize th}}}
\def\half{\mbox{$1 \over 2$}}
\def\emph#1{{\hspace{0.2em}\sf #1\hspace{0.2em}}}
\def\N#1{\mbox{\sl #1\thinspace}}
\def\P{\mbox{$\cal P$}}
\def\NP{\mbox{$\cal N\!P$}}
\def\NC{\mbox{$\cal N\!C$}}
\def\YPE{\mbox{$\Upsilon\Pi$E}}
\def\vstrut#1{\rule{0in}{#1}}
\def\RaggedRight{\rightskip=0pt plus2.0em
  \spaceskip=0.3em plus0.03em minus0.03em
  \xspaceskip=0.5em plus0.05em minus0.05em}
\def\SV{\small\spaceskip=0.472em}
\def\BSV{\begin{trivlist}\item[]\small\spaceskip=0.472em
  \advance\baselineskip by -1pt}
\def\ESV{\advance\baselineskip by 1pt\end{trivlist}}


\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\bn{\begin{enumerate}}
\def\en{\end{enumerate}}
\def\bd{\begin{description}}
\def\ed{\end{description}}
\def\bl#1{\begin{list}{}{#1}}
\def\el{\end{list}}
\def\bq{\begin{quote}}
\def\eq{\end{quote}}
\def\bc{\begin{center}}
\def\ec{\end{center}}
\def\exdent{\item[]\hspace*{-\leftmargin}}
\def\bpf{\begin{list}{}
  {\setlength{\leftmargin}{1em}}
  \item \hspace{-1em}{\bf Proof: \x}}
\def\epf{\hfill $\Box$ \end{list}}
\def\bdf{\begin{list}{}
  {\setlength{\leftmargin}{1em}}
  \item \hspace{-1em}{\bf Definition: \x}}
\def\edf{\end{list}}
\def\bcl{\begin{list}{}
  {\setlength{\leftmargin}{1em}}
  \item \hspace{-1em}{\bf Claim: \x}}
\def\ecl{\end{list}}
\newcounter{stepctr}
\def\bsteps{\begin{list}{\sl Step \arabic{stepctr}}
  {\usecounter{stepctr}}}
\def\esteps{\end{list}}
\def\babs{\begin{list}{}{\setlength{\leftmargin}{2.0em}
  \setlength{\rightmargin}{\leftmargin}} \item
  \hspace*{\fill} {\bf Abstract} \hspace*{\fill} \bigskip \\}
\def\eabs{\end{list}}
\def\bthm#1#2{\begin{list}{}
  {\leftmargin=1em \refstepcounter{#2}}
  \item \hspace{-1em}{\bf #1 \arabic{#2}:}}
\def\ethm{\end{list}}
\def\bclm#1{\begin{list}{}
  {\leftmargin=1em}
  \item \hspace{-1em}{\bf #1:}}
\def\eclm{\end{list}}

\newtheorem{proposition}{Proposition}
\newtheorem{theorem}[proposition]{Theorem}
\newtheorem{lemma}[proposition]{Lemma}
\newtheorem{corollary}[proposition]{Corollary}
\newtheorem{claim}[proposition]{Claim}

\setcounter{topnumber}{1}


%union
\newcommand{\union}{\cup}
%intersection
\newcommand{\inter}{\cap}
%set
\newcommand{\set}[1]{\left\{ #1 \right\}}
%set
\newcommand{\parents}[1]{{{\mbox{\it parents\,}}(#1)}}

%black box
\newcommand{\bbox}{\vrule height7pt width4pt depth1pt}
%proposition
\newcommand{\pro}{\begin{proposition}}
%definition
\newcommand{\dfn}{\begin{definition}}
%remark
\newcommand{\epro}{\end{proposition}}
%end definition
\newcommand{\edfn}{\bbox\end{definition}}
%end remark
%proof
\newcommand{\prf}{\noindent{\bf Proof:} }
%end proof
\newcommand{\eprf}{\bbox\vspace{0.1in}}

\def\today{}

\def\citeasnoun#1{\citeauthor{#1}~\citeyear{#1}}


\begin{document} 

\title{Logarithmic-Time Updates and Queries \\ in Probabilistic Networks}

\author{\name Arthur L. Delcher  \email delcher@cs.loyola.edu \\
  \addr Computer Science Department, Loyola College in Maryland \\
  \addr Baltimore, MD \, 21210 \\
  \AND
  \name Adam J. Grove  \email grove@research.nj.nec.com \\
  \addr NEC Research Institute \\
  \addr Princeton, NJ \, 08540 \\
  \AND
  \name Simon Kasif  \email kasif@cs.jhu.edu \\
  \addr Department of Computer Science, Johns Hopkins University \\
  \addr Baltimore, MD \, 21218 \\
  \AND
  {\name Judea Pearl  \email pearl@lanai.cs.ucla.edu \\[-1pt]
  \addr Department of Computer Science, University of California \\[-2pt]
  \addr Los Angeles, CA \, 90095}}

\maketitle 


\begin{abstract}
%{\small

Traditional databases commonly support efficient
query and update procedures that operate in time which is
sublinear in the size of the database. 
Our goal in this paper is to take a first step toward
dynamic reasoning in probabilistic databases with comparable efficiency.
  We propose a dynamic data structure that supports efficient
  algorithms for updating and querying singly connected Bayesian networks.
  In the conventional algorithm, new
  evidence is absorbed in time $O(1)$ and queries are processed in time
  $O(N)$, where $N$ is the size of the network.  We propose an
  algorithm which, after a preprocessing phase, allows us to answer queries
  in time $O(\log N)$ at the expense of $O(\log N)$ time per evidence
  absorption.  The usefulness of sub-linear processing time manifests
  itself in applications requiring (near) real-time response over large
  probabilistic databases. We briefly discuss a potential
  application of dynamic probabilistic reasoning in computational
  biology.
  %for example, dynamic
  %systems involving thousands of temporally ordered states.
%}%end \small
\end{abstract}


\section{Introduction}

Probabilistic (Bayesian) networks are an increasingly popular
modeling technique that has been used successfully in numerous
applications of intelligent systems such as real-time planning
and navigation, model-based diagnosis, information retrieval,
classification, Bayesian forecasting, natural language
processing, computer vision, medical informatics and
computational biology.  Probabilistic networks allow the user to
describe the environment using a ``probabilistic database'' that
consists of a large number of random variables, each
corresponding to an important parameter in the environment.
Some random variables could in fact be hidden and may correspond
to some unknown parameters (causes) that influence the
observable variables.  Probabilistic networks are quite general
and can store information such as the probability of failure of
a particular component in a computer system, the probability of
page $i$ in a computer cache being requested in the near future,
the probability of a document being relevant to a particular
query, or the probability of an amino-acid subsequence in a
protein chain folding into an alpha-helix conformation.

The applications we have in mind include networks that are
dynamically maintained to keep track of a {\em probabilistic\/}
model of a changing system.  For instance, consider the task of
automated detection of power-plant failures.  We might repeat a
cycle that consists of the following sequence of operations:
First we perform sensing operations.  These operations cause
updates to be performed to specific variables in the
probabilistic database.  Based on this evidence we estimate
(query) the probability of failure in certain sites.  More
precisely, we query the probability distribution of the random
variables that measure the probability of failure in these sites
based on the evidence.  Since the plant requires constant
monitoring, we must repeat the cycle of sense/evaluate on a
frequent basis.

A conventional (non-probabilistic) database tracking the plant's
state would not be appropriate here, because it is not possible
to directly observe whether a failure is about to occur.  On the
other hand, a probabilistic ``database'' based on a Bayesian
network will only be useful if the operations---update and
query---can be performed very quickly.  Because real-time or
near real-time is so often necessary, the question of doing {\em
extremely\/} fast reasoning in probabilistic networks is
important.

Traditional (non-probabilistic) databases support efficient
query and update procedures that often operate in time which is
sublinear in the size of the database (\eg, using binary
search).  Our goal in this paper is to take a step toward
systems that can perform dynamic probabilistic reasoning (such
as what is the probability of an event given a set of
observations) in time which is sublinear in the size of the
probabilistic network.  Typically, sublinear performance in
complex networks is attained by using parallelism.  This paper
relies on preprocessing.


%Queries allow the agent to probe the probability distribution
%of a small constant number
%of variables.  Updates allow the agent to modify the value
%of a single variable and the new evidence must be absorbed
%into the network.
%In an intelligent real-time system, evidence absorption could
%be done periodically, (\eg, every second), reactively (\eg, in
%response to another sensor), or proactively (by the system
%initiating some plan and therefore deciding to perform a test
%and update of the evidence at some sensor).  In a real-time
%system, it is particularly important to incorporate an update as
%efficiently as possible in order to minimize delay in
%responding to queries.  Naturally, responses to queries in a
%real-time system must take the current evidence values at all
%sensors into account.  Speed is particularly important in applications
%of probabilistic networks to intelligent decision making
%in operating systems such as intelligent prefetching and caching.

%Given a probabilistic database and query-update mechanisms,
%an AI system now can perform intelligent decision making
%using an internal program. 
%An internal program using an automaton for example, 
%would repeat the following cycle:
%in every state it queries a small number of
%random variables in the database,
%performs an action based on the results, and moves
%to the next state. 
%The action may cause a small number of variables in the database to be 
%updated, and the cycle continues.

%To illustrate probabilistic reasoning in a real-time intelligent system,
%consider the task of automated detection of power-plant failures.
%We typically repeat a cycle that consists of the following sequence of 
%operations:
%First we perform sensing operations.  These operations cause updates
%to be performed to specific variables in the probabilistic database.
%Based on this evidence we estimate (query) the 
%probability of failure in certain sites.  More precisely, we query 
%the probability distribution of the random variables that measure the 
%probability of failure in these sites based on the evidence. 
%Based on these predictions, we perform additional sensing
%operations, and again re-estimate the probability of failure in some
%other sub-system.
%What is illustrated in this example is a process
%of dynamically updating and querying a joint probability 
%distribution of a subset of random variables. 

%%%Simon:  I think this example can be omitted.
%Consider the example of an automated ambulance vehicle
%travelling in a snow storm.  It has to minimize the time it
%takes to the hospital while maintaining safe speed.  While
%driving, the system has to check and periodically update a large
%number of important parameters (\eg, the probability of
%skidding on the road) that could influence its future
%decisions.  The driver may tap the brakes to get a feel
%for the response (probability of slipping when stopping), assess
%the number of cars on the side of the road
%(the prior probability of slipping),
%check the distance to the nearest vehicle, etc.  For
%example, during an attempt to pass on the right it will check
%the distance to the nearest vehicle on the right lane, the
%distance to vehicle in front of it, etc.  If the probability of
%performing passing safely is higher than some predefined safety
%threshold, the vehicle would perform the action.

%The key to the success of this convenient framework to describe
%agents is our ability to implement efficiently query and 
%update operations on probabilistic databases.

%adam: redundant
%In this paper we rely on techniques from complexity theory and 
%make a first step toward developing very efficient algorithms for 
%querying and updating probabilistic databases.
%adam: changed; several new algorithms overstates things
%Specifically, we describe several new algorithms for performing

Specifically, we describe new algorithms for performing queries
and updates in belief networks in the form of trees (causal
trees, polytrees and join trees).  We define two natural
database operations on probabilistic networks.
\begin{enumerate}
\item
  {\sc Update-Node}:  Perform sensory input, modify the evidence
  at a leaf node (single variable) in the network 
  and {\bf absorb} this evidence into the network. 

\item
  %adam: reworded slightly
  %{\sc Query-Node}:  Obtain the probability distribution
  %(belief vector) of an arbitrary node (single variable) in the network.
  {\sc Query-Node}:  Obtain the marginal probability distribution
  over the values of an arbitrary node (single variable) in the network.
  
\end{enumerate}
The standard algorithms introduced by \citeasnoun{pearl/net}
%adam: added can. and changed whereas to although
can 
perform the {\sc Query-Node} operation in $O (1)$ time although
evidence absorption, \ie,
the {\sc Update-Node} operation, takes $O (N)$ time where $N$ is
the size of the network.
%adam: this is false; the *joint* distribution isn't re-estimated, is it?
%Evidence absorption is typically done by re-estimating the 
%joint probability distribution given the new evidence.
Alternatively, one can assume that the
%adam: asserting --> recording
{\sc Update-Node} operation takes O(1) time (by simply recording
the change) and the {\sc Query-Node} operation takes $O (N)$
time (evaluating the entire network).

%art: broke paragraph and added 2 sentences at end
In this paper we describe an approach to perform both queries
and updates in $O (\log N)$ time.  This can be very significant
in some systems since we improve the ability of a system to
respond after a change has been encountered from $O(N)$ time to
$O (\log N)$.  Our approach is based on preprocessing the
network using a form of node absorption in a carefully
structured way to create a hierarchy of abstractions of the
network.  Previous uses of node absorption techniques were
reported by \citeasnoun{peot/shachter/91}.

We note that measuring complexity only in terms of the size of
the network, $N$, can overlook some important factors. Suppose
that each variable in the network has domain size $k$ or less.
For many purposes, $k$ can be considered constant. Nevertheless,
some of the algorithms we consider have a slowdown which is some
power of $k$, which can be become significant in practice unless
$N$ is very large. Thus we will be careful to state this
slowdown where it exists.

Section~\ref{causal} considers the case of causal trees, \ie,
singly connected networks in which each node has at most one
parent.  The standard algorithm (see \citeauthor{pearl/net},
1988) must use $O(k^2 N)$ time for either updates or for
retrieval, although one of these operations can be done in
$O(1)$ time.  As we discuss briefly in
Section~\ref{simplepreprocessing}, there is also a
straightforward variant on this algorithm that takes $O(k^2 D)$
time for both queries and updates, where $D$ is the height of
the tree.

We then present an algorithm that takes $O(k^3 \log N)$ time for
updates and $O(k^2 \log N)$ time for queries in any causal tree.
This can of course represent a tremendous speedup, especially
for large networks.  Our algorithm begins with a polynomial-time
preprocessing step (linear in the size of the network),
constructing another data structure (which is not itself a
probabilistic tree) that supports fast queries and updates. The
techniques we use are motivated by earlier algorithms for
dynamic arithmetic trees, and involve ``caching'' sufficient
intermediate computations during the update phase so that
querying is also relatively easy.  We note, however, that there
are substantial and interesting differences between the
algorithm for probabilistic networks and those for arithmetic
trees.  In particular, as will be apparent later, computation in
probabilistic trees requires both bottom-up and top-down
processing, whereas arithmetic trees need only the former.
Perhaps even more interesting is that the relevant probabilistic
operations have a different algebraic structure than arithmetic
operations (for instance, they lack distributivity).

%adam: deleted first few lines.
%Finally, we briefly mention several specific applications that are 
%relevant to queries and updates in probabilistic trees
%(or general Bayes networks that have a relatively efficient
%transformation into a join tree).
Bayesian trees have many applications in the literature
including classification.  For instance, one of the most popular
methods for classification is the Bayes classifier that makes
independence assumption on the features that are used to perform
classification \cite{duda/hart/73,rachlin/etal/94}.
Probabilistic trees have been used in computer vision
\cite{werman1,chelberg}, signal processing \cite{wilsky/etal},
game playing \cite{kasif/delcher/92}, and statistical mechanics
\cite{berger/ye}.  Nevertheless, causal trees are fairly limited
for modeling purposes.  However similar structures, called {\em
join trees}, arise in the course of one of the standard
algorithms for computing with arbitrary Bayesian networks (see
\citeauthor{lauritzen/spiegelharter}, 1988).
%adam2 extended this sentence. 
Thus our algorithm for join trees has potential relevance to
many networks that are not trees.  Because join trees have some
special structure, they allow some optimization of the basic
causal-tree algorithm.  We elaborate on this in
Section~\ref{jointree}.

In Section~\ref{polytree} we consider the case of arbitrary
polytrees.
%adam3: changed as recommended by reviewer 
%Although we suspect that it is possible to directly
%state an $O(\log N)$ algorithm for updates and queries in
%polytrees, in a similar fashion to the causal-tree algorithm of
%Section~\ref{causal}, we propose a different technique in this
%paper.
We give an $O(\log N)$ algorithm for updates and queries, which
involves transforming the polytree to a join tree,
and then using the results of
Sections~\ref{causal}~and~\ref{jointree}.  The join tree of a
polytree has a particularly simple form, giving an algorithm in
which updates take $O(k^{p+3} \log N)$ time and queries
$O(k^{p+2} \log N)$, where $p$ is the maximum number of parents
of any node.  Although the constant appears large, it must be
noted that the original polytree takes $O(k^{p+1} N)$ space
merely to represent, if conditional probability tables are given
as explicit matrices.
%adam2: c is always 1; this was a silly thing to say. 
%We also show that
%$O(k^{p+1} k^{2c} \log N)$ is achievable for many common polytrees, where
%$c$ is a small constant.

%adam: added finally,
Finally, we discuss a specific modelling application in
computational biology where probabilistic models are used to
describe, analyze and predict the functional behavior of
biological sequences such as protein chains or DNA sequences
(see \citeauthor{delcher/kasif/protein}, 1993 for references).
Much of the information in computational biology databases is
noisy.  However, a number of successful attempts to build
probabilistic models have been made.  In this case, we use a
probabilistic tree of depth 300 that consists of 600 nodes and
all the matrices of conditional probabilities are $2 \times 2$.
The tree is used to model the dependence of a protein's
secondary structure on its chemical structure.  The detailed
description of the problem and experimental results are given by
\citeasnoun{delcher/kasif/protein}.  For this problem we obtain
an effective speed-up of about a factor of 10 to perform an
update as compared to the standard algorithm.  Clearly, getting
an order of magnitude improvement in the response time of a
probabilistic real-time system could be of tremendous importance
in future use of such systems.


\section{Causal Trees}\label{causal}

%Following \cite{pearl/net} we assume that a probabilistic
%causal tree is a directed tree in which each node represents a
%discrete random variable $X$, and each directed edge
%represents a matrix of conditional probabilities $M_{Y | X}$
%(associated with edge $X \rightarrow Y$).
%Without loss of
%generality, we can assume all trees are binary trees, and are complete
%(\ie, each node has $0$ or $2$ children.)%
%\footnote{Converting any tree into one of this form involves at most
%  doubling the number of nodes.}
%In a causal tree, each node
%(with the exception of the root) has only one incoming
%directed edge.  The leaf nodes in the tree 
%are called {\bf evidence nodes}.
%Each leaf node is instantiated
%to a boolean vector with a single $1$ corresponding to the observed
%evidence.
%%adam:this is silly; we have *defined* things this way!
%Without loss of generality we assume evidence nodes are always
%leaves in the causal tree.  The probability distribution of
%any non-evidence node in the tree is a probability vector
%$\BEL(X)$ defined by
%\[
%  \BEL(X) = \PROB( X | \mbox{\,all evidence values})
%\]
%and describes the discrete probability distribution of $X$
%conditioned by the current instantiation of evidence nodes.
%The belief vector of an evidence node $X$ is fully known and
%does not depend on other nodes in the tree.
%In this paper we assume that the size of each vector 
%$\BEL(X)$ is a constant $k$; that is, the variable $X$ takes exactly
%$k$ values.
%A common case is that of binary random variables ($k = 2$)
%that take the value TRUE with probability $p$ and FALSE with probability  
%$1-p$.

{\sloppy
A probabilistic causal tree is a directed tree in which each
node represents a discrete random variable $X$, and each
directed edge is annotated by a matrix of conditional
probabilities $M_{Y | X}$ (associated with edge $X \rightarrow
Y$). That is, if $x$ is a possible value of $X,$ and $y$ of $Y,$
then the $(x,y)$th component of $M_{Y | X}$ is
$\PROB(Y=y|X=x)$.  Such a tree represents a joint probability
distribution over the product space of all variables; for
detailed definitions and discussion see \citeasnoun{pearl/net}.
Briefly, the idea is that we consider the product, over all
nodes, of the conditional probability of the node given its
parents. For example, in Figure~\ref{causal/segment/fig} the
implied
\begin{figure}
  \bc
  \unitlength=0.01in
  \begin{picture}(305,220)(-115,-5)
    \put(25,25){\circle{30}}
      \put(25,25){\makebox(0,0){$Y$}}
      \put(89,89){\vector(-1,-1){53}}
      \put(60,65){\makebox(0,0)[br]{$M_{Y|X}$}}
    \put(175,25){\circle{30}}
      \put(175,25){\makebox(0,0){$Z$}}
      \put(111,89){\vector(1,-1){53}}
      \put(140,65){\makebox(0,0)[bl]{$M_{Z|X}$}}
    \put(-100,100){\circle{30}}
      \put(-100,100){\makebox(0,0){$V$}}
      \put(-11,189){\vector(-1,-1){78}}
      \put(-53,153){\makebox(0,0)[br]{$M_{V|U}$}}
    \put(100,100){\circle{30}}
      \put(100,100){\makebox(0,0){$X$}}
      \put(11,189){\vector(1,-1){78}}
      \put(53,153){\makebox(0,0)[bl]{$M_{X|U}$}}
    \put(0,200){\circle{30}}
      \put(0,200){\makebox(0,0){$U$}}
  \end{picture}
  \ec

  \caption{A segment of a causal tree.}
  \label{causal/segment/fig}
\end{figure}
distribution is:
\[
  \begin{array}{@{}l@{}}
  \PROB(U=u,V=v,X=x,Y=y,Z=z) \, = \\
  \makebox[1.7em]{} \PROB(U=u)\, \PROB(V=v|U=u)\, \PROB(X=x|U=u)\,
                       \PROB(Y=y|X=x)\, \PROB(Z=z|X=x).
  \end{array}
\]
Given particular values of $u,v,x,y,z,$ the conditional
probabilities can be read from the appropriate matrices $M$.
One advantage of such a product representation is that it is
very concise. In this example, we need four matrices and the
unconditional probability over $U$, but the size of each is at
most the square of the largest variable's domain size.  In
contrast, a general distribution over $N$ variables requires an
exponential (in $N$) representation.
\par}

Of course, not every distribution can be represented as a causal
tree. But it turns out that the product decomposition implied by
the tree corresponds to a particular pattern of conditional
%adam3: added (if..); reviewer 2.
independencies which often hold (if perhaps only approximately)
in real applications.
Intuitively speaking, in Figure~\ref{causal/segment/fig} some of
these implied independencies are that the conditional
probability of $U$ given $V$, $X$, $Y$ and $Z$ depends only on
values of $V$ and $X$; and the probability of $Y$ given $U$,
$V$, $X$, and $Z$ depends only on $X$.  Independencies of this
sort can arise for many reasons, for instance from a causal
modeling of the interactions between the variables.  We refer
the reader to \citeasnoun{pearl/net} for details related to the
modeling of independence assumptions using graphs.

In the following, we make several assumptions that significantly
simplify the presentation, but do not sacrifice generality.
%adam3: added
First, we assume that each variable ranges over the same,
constant, number of values $k$.%
\footnote{This assumption is nonrestrictive because we can
add ``dummy'' values to each variable's range, which should be
given conditional probability $0$. Nevertheless, there may some computational
advantage in allowing different variable domain sizes. The changes
required to permit this are not difficult, but since they
complicate the presentation somewhat we omit them.}
It follows that the marginal
probability distribution for each variable can be viewed as a
$k$-dimensional vector, and each conditional probability matrix
such as $M_{Y | X}$ is a square $k \times k$ matrix.
%adam: do we need the following?
A common case is that of binary random variables ($k = 2$); the
distribution over the values (TRUE, FALSE) is then $(p,1-p)$ for
some probability $p$.

The next assumption is that the tree is binary, and complete, so
that each node has 0 or 2 children. Any tree can be converted
into this form, by at most doubling the number of nodes. For
instance, suppose node $p$ has children $c_1, c_2, c_3$ in the
original tree.  We can create another ``copy'' of $p$, $p'$, and
rearrange the tree such that the two children of $p$ are $c_1$ and
$p'$, and the two children of $p'$ are $c_2$ and $c_3$.  We can
constrain $p'$ always to have the same value as $p$ simply by
choosing the identity matrix for the conditional probability
table between $p$ and $p'$. Then the distribution represented by
the new tree is effectively the same as the original.
Similarly, we can always add ``dummy'' leaf nodes if necessary
to ensure a node has two children.  As explained in the
introduction, we are interested in processes in which certain
variables' values are observed, upon which we wish to condition.
Our final assumption is that these observed {\bf evidence\/}
%adam3: got rid of precisely, don't think we need it
%nodes are precisely the leaves of the tree.  Again, because it
nodes are all leaves of the tree.  Again, because it
is possible to ``copy'' nodes and to add dummy nodes, this is
not restrictive.


%adam: minor rewriting
The product distribution alluded to above corresponds to the
distribution over variables prior to any observations.  In
practice, we are more interested in the conditional
distribution, which is simply the result of conditioning on all
the observed evidence (which, by the earlier assumption,
corresponds to seeing values for all the leaf nodes). Thus, for
each non-leaf node $X$ we are interested in the conditional
marginal probability over $X$, \ie, the $k$-dimensional vector:
\[
  \BEL(X) = \PROB( X | \mbox{\,all evidence values}).
\]

%%adam3. Since lambda is *not* a probability distribution, this is
%%potentially confusing. Also, I think it is possible to deal
%%with unobserved leaf nodes perfectly well; see next note. I think
%%we can just delete this sentence.
%The probability distribution of a leaf node is assumed to be
%known: it is $0$ for all values except the value most recently
%observed, which has probability 1.
The main algorithmic problem
is to compute $\BEL(X)$ for each (non-evidence) node $X$ in the
tree given the current evidence.
%adam: moved this up earlier
%
%
%As in Figure~\ref{causal/segment/fig}, 
%let $X$ be a node in a tree, with $U$ a parent of $X$, and $Y$
%and $Z$ children of $X$.  Intuitively speaking, the independence
%assumption in a causal tree states that the conditional
%probability of a node $U$ given the probability of $X$, $Y$ and
%$Z$ depends only on the probability of $X$; and the probability
%of $Y$ given $X$, $Z$ and $U$ depends only on $X$.  We refer the
%reader to \cite{pearl/net} for details related to the modeling
%of independence assumptions using graphs.
%adam: As a result --> It is know than 
%As a result, the probability vector $\BEL(X)$ can
It is well known that the probability vector $\BEL(X)$ can be
computed in linear time (in the size of the tree) by a popular
algorithm based on the following equation:
\[
  \BEL(X) = \PROB(X | \mbox{\,all evidence}) = \alpha \Dyad \lambda (X) \Dyad \pi(X) 
\]
Here $\alpha$ is a normalizing constant, $\lambda(X)$ is the
probability of all the evidence in the subtree below node $X$
given $X$, and $\pi(X)$ is the probability of $X$ given all
evidence
%adam: minor rewriting
in the rest of the tree.  To interpret this equation, note that
if $X = (x_1, x_2, \ldots, x_k)$ and $(Y = y_1, y_2, \ldots,
y_k)$ are two vectors we define $\Dyad$ to be the operation of
component-wise product (pairwise or dyadic product of vectors):
\[
  X \Dyad Y = (x_1 y_1, x_2 y_2, \ldots, x_k y_k).
\]
%adam: No these aren't definitions; pi and lambda are defined above. .
%We define $\lambda(X)$  and $\pi(X)$ recursively as follows:
The usefulness of $\lambda(X)$ and $\pi(X)$ derives from the
fact that they can be computed recursively, as follows:
\begin{enumerate}
\item
  If $X$ is the root node, $\pi (X)$ is the prior probability of $X$.

\item
  %adam3: changed this text. Lambda is not a probability vector,
  %so I think this rewrite is clearer.
  If $X$ is a leaf node, $\lambda(X)$ is a vector with $1$ in
  the $i$th position (where the $i$th value has been observed)
  and $0$ elsewhere.
  %adam3. Added, reviewer asked for. This is right, isn;t it? (Please confirm)
  If no value for $X$ has been observed, then $\lambda(X)$  is
  a vector consisting of all $1$'s.%
  %adam3: added, but it might be overkill. Delete if you want.
  \footnote{Or we can set to $1$ all components corresponding to
    {\em possible\/} values---this is especially useful when the
    observed variable is part of a joint-tree clique
    (Section~\ref{jointree}). In general, 
    $\lambda(X)$ should be thought of as the {\em likelihood\/} vector
    over $X$ given our observations about $X$.}
\item
  Otherwise, if, as shown in Figure~\ref{causal/segment/fig},
  the children of node $X$ are $Y$ and $Z$, its
  sibling is $V$ and its parent is $U$, we have:
  \begin{eqnarray*}
    \lambda(X) & = & (M_{Y|X} \cdot \lambda (Y))
                       \Dyad (M_{Z|X} \cdot \lambda (Z)) \\
    \pi(X) & = & M_{X|U}\Transpose \cdot \left( \pi (U) \Dyad
                       (M_{V|U} \cdot \lambda(V)) \right)
  \end{eqnarray*}
\end{enumerate}

%adam: changed
%Our derivation of belief vectors in causal trees is borrowed
Our presentation of this technique follows that of
\citeasnoun{pearl/net}.  However, we use a somewhat different
notation in that we don't describe messages sent to parents or
successors, but rather discuss the direct relations among the
$\pi$ and $\lambda$ vectors in terms of simple algebraic
equations.  We will take advantage of algebraic properties of
these equations in our development.

%adam: this has already been said; no need to repeat. 
%We assume that the size of the causal tree is $N$, and that each
%variable has a constant domain size $k$. It follows that the matrices
%of conditional probabilities have size $k^2$.

%Given the notation above
It is very easy to see that the equations above
can be evaluated in time proportional to the size of the
network.  The formal proof is given by \citeasnoun{pearl/net}.
\bthm{Theorem}{theoremctr}
  The belief distribution of every variable (that is, the marginal
  probability distribution for each variable, given the evidence)
  in a causal tree can be evaluated
  in $O(k^2 N)$ time where $N$ is the size of the tree.
  (The factor $k^2$ is due to the multiplication of a matrix by a vector that must
  be performed at each node.)
\ethm
%In our model we are not interested in evaluating the joint
%probability distribution.  Instead, we want to support two
%operations on a probabilistic database, namely update of a
%variable and query of a variable.
%From the theorem above it is
%clear that given an update to some node, (\ie, instantiation of
%a variable to a constant vector) we can perform evidence
%absorption by computing the joint probability distribution.  We
%can then perform queries (\ie, retrieving the probability
%distribution of a single variable) in constant time by a look-up
%table.
This theorem shows that it is possible to perform evidence absorption
in $O(N)$ time, and queries in constant time (\ie, by retrieving the
previously computed values from a lookup table). 
In the next sections we will show how to perform both queries and updates
in worst-case $O(\log N)$ time.
Intuitively, we will not recompute all the marginal
distributions after an update, but rather make only 
a small number of changes, sufficient, however, to compute the value
of any variable with only a logarithmic delay.


%adam: changed title
\subsection{A Simple Preprocessing Approach}\label{simplepreprocessing}

To obtain intuition about the new approach we begin with a
very simple observation.  Consider a causal tree $T$ of depth
$D$.  For each node $X$ in the tree we initially compute its
$\lambda (X)$ vector.  $\pi$ vectors are left uncomputed.
Given an update to a node $Y$, we calculate the revised
$\lambda (X)$ vectors for all nodes $X$ that are ancestors of
$Y$ in the tree.  This clearly can be done in time
proportional to the depth of the tree, \ie, $O (D)$.  The rest of
the information in the tree remains unchanged.  Now consider
a {\sc Query-Node} operation for some node $V$ in the tree.
We obviously already have the accurate $ \lambda(V)$ vector
for every node in the tree including $V$.  However, in order
to compute its $\pi(V)$ vector we need to compute only the
$\pi(Y)$ vectors for all the nodes above $V$ in the tree and
multiply these by the appropriate $\lambda$ vectors that are
kept current.  This means that to compute the accurate
$\pi(V)$ vector we need to perform $O (D)$ work as well.
Thus, in this approach we don't perform the complete update to
every $\lambda (X)$ and $\pi (X)$ vector in the tree.  
\bthm{Lemma}{theoremctr}
  {\sc Update-Node} and {\sc Query-Node} operations in a causal
  tree $T$ can be performed in $O (k^2 D)$ time where $D$ is the depth
  of the tree.
\ethm

This implies that if the tree is balanced, both operations can
be done in $O (\log N)$ time.  However, in some important
applications the trees are not balanced (\eg, models of
temporal sequences, \citeauthor{delcher/kasif/protein}, 1993).
The obvious question therefore is: Given a causal tree $T$ can
we produce an equivalent balanced tree $T'$?  While the answer
to this question appears to be difficult, it is possible to use
a more sophisticated approach to produce a data structure (which
is {\em not} a causal tree) to process queries and updates in $O
(\log N)$ time.  This approach is described in the subsequent
sections.

\subsection{A Dynamic Data Structure For Causal Trees}

%adam: next few paragraphs significantly changed
The data structure that will allow efficient incremental processing of a
probabilistic tree $T = T_0$ will be a sequence
of trees, $T_0, T_1, T_2, \ldots, T_i, \ldots, T_{\log N}$.
%adam: added {\em to contracted
Each $T_{i+1}$ will be a {\em contracted\/} version of $T_i$, whose
nodes are a subset of those in $T_i$. In particular, $T_{i+1}$ will
contain about half as many leaves as its predecessor.

We defer the details of this contraction process until the next
section. However, one key idea is that we maintain consistency, 
in the sense that $\BEL(X),$ $\lambda(X),$ and $\pi(X)$ are given the
same values by all the trees in which $X$ appears.
We choose the conditional probability matrices in the contracted
trees (\ie, all trees other than $T_0$) to ensure this.

Recall that the $\lambda$ and $\pi$ equations have the form
\begin{eqnarray*}
    \lambda(X) & = & (M_{Y|X} \cdot \lambda (Y))
                       \Dyad (M_{Z|X} \cdot \lambda (Z)) \\
    \pi(X) & = & M_{X|U}\Transpose \cdot \left( \pi (U) \Dyad
                       (M_{V|U} \cdot \lambda(V)) \right)
\end{eqnarray*}
if $Y$ and $Z$ are children of $X$, $X$ is a right child of $U$,
and $V$ is $X$'s sibling (Figure~\ref{causal/segment/fig}).
However, these equations are not in the most convenient form and
the following notational conventions will be very helpful.
First, let $\A{x}{i}$ (resp., $\B{x}{i}$) denote the conditional
probability matrix between $X$ and $X$'s left (resp., right)
child in the tree $T_i$.  Note that the identity of these
children can differ from tree to tree, because some of $X$'s
original children might be removed by the contraction process.
One advantage of the new notation is that the explicit
dependence on the identity of the children is suppressed.  Next,
suppose $X$'s parent in $T_i$ is $u$. Then we let $\C{x}{i}$
denote either $\A{u}{i}$ or $\B{u}{i}$, and $\D{x}{i}$ denote
either $\B{u}{i}\Transpose$ or $\A{u}{i}\Transpose$, depending
on whether $X$ is the right or left child, respectively, of $U$.
It will not be necessary to keep careful track of these
correspondences, but simply to note that the above equations
become:\footnote{Throughout, we assume that $\Dyad$ has lower
precedence than matrix multiplication (indicated by $\cdot$).}
\begin{eqnarray*}
  \LambdaEq{x}{y}{z}{i} \\
  \PiEq{x}{u}{v}{i}
\end{eqnarray*}

%In each $T_i$ there will be a set of equations for the $\pi$
%and $\lambda$ values of nodes in $T_i$.
%In general, for each
%\footnote{Throughout, we assume
%that $\Dyad$ has lower precedence than conventional matrix
%multiplication (indicated by $\cdot$).}
%node $x$ in $T_i$ we will have equations of the form:%
%\begin{eqnarray*}
%  \LambdaEq{x}{y}{z}{i} \\
%  \PiEq{x}{u}{v}{i}
%\end{eqnarray*}
%where $y$ and $z$ are the children of $x$, $v$ its sibling, and
%$u$ its parent in $T_i$.  $\A{x}{i}$, $\B{x}{i}$, $\C{x}{i}$ and
%%$\D{x}{i}$ are constant matrices, and $\C{x}{i}$ is equal to
%either $\A{u}{i}$ or $\B{u}{i}$ depending on whether $x$ is the
%right or left child, respectively, of $u$.
%$\D{x}{i}$ are constant matrices. $\C{x}{i}$ is equal to
%either $\A{u}{i}$ or $\B{u}{i}$, and $\D{x}{i}$
%$is $\B{u}{i}\Transpose$ or $\A{u}{i}\Transpose$,
%depending on whether $x$ is the
%right or left child, respectively, of $u$.
%%adam: added; emphasize that this these are exactly the normal polytree
%%equations over the contracted tree.
%Note that it follows that we can identify
%$\A{x}{i}, \B{x}{i}, \C{x}{i}, \D{x}{i}\Transpose$ as the
%appropriate conditional probability matrices in the contracted tree,
%although we do not use this property in the following. 
In the next section we describe the preprocessing step
that creates the dynamic data structure. 

\subsection{\Rake\ Operation}

The basic operation used to contract the tree is \Rake\ which removes
both a leaf and its parent from the tree.  The effect of this operation
on the tree is shown in Figure~\ref{rake/fig}.
\begin{figure*}
  \bc
  \unitlength=0.005in
  \begin{picture}(305,225)(-115,-5)
    \put(80,225){\makebox(0,0){In $T_i$}}
    \put(10,10){\framebox(30,30){$e$}}
      \put(40,40){\line(1,1){49}}
    \put(175,25){\circle{30}}
      \put(175,25){\makebox(0,0){$z$}}
      \put(164,36){\line(-1,1){53}}
      \multiput(155,5)(-5,-5){3}{\circle*{1}}
      \multiput(195,5)(5,-5){3}{\circle*{1}}
    \put(-100,100){\circle{30}}
      \put(-100,100){\makebox(0,0){$v$}}
      \put(-89,111){\line(1,1){78}}
    \put(100,100){\circle{30}}
      \put(100,100){\makebox(0,0){$x$}}
      \put(89,111){\line(-1,1){78}}
    \put(0,200){\circle{30}}
      \put(0,200){\makebox(0,0){$u$}}
  \end{picture}
  \begin{picture}(200,220)
    \put(100,110){\makebox(0,0){$\Rightarrow$}}
    \put(100,140){\makebox(0,0){\Rake\,$(e,x)$}}
  \end{picture}
  \begin{picture}(305,220)(-115,10)
    \put(80,240){\makebox(0,0){In $T_{i+1}$}}
    \put(-100,100){\circle{30}}
      \put(-100,100){\makebox(0,0){$v$}}
      \put(-89,111){\line(1,1){78}}
    \put(100,100){\circle{30}}
      \put(100,100){\makebox(0,0){$z$}}
      \put(89,111){\line(-1,1){78}}
      \multiput(80,80)(-5,-5){3}{\circle*{1}}
      \multiput(120,80)(5,-5){3}{\circle*{1}}
    \put(0,200){\circle{30}}
      \put(0,200){\makebox(0,0){$u$}}
  \end{picture}
  \ec

  \caption{The effect of the operation \Rake\,$(e,x)$.  $e$ must be a leaf, but
    $z$ may or may not be a leaf.}
  \label{rake/fig}
\end{figure*}
%adam: some rewriting
We now define the algebraic effect of this operation on the
equations associated with this tree.  Recall that we want to
define the conditional probability matrices in the raked tree so
that the distribution over the remaining variables is unchanged.
We achieve this by substituting the equations for $\lambda (x)$
and $\pi (x)$ into the equations for $\lambda (u)$, $\pi (z)$,
and $\pi (v)$.  In the following, it is important to note that
$\pi (u)$, $\lambda (z)$ and $\lambda(v)$ are unaffected by the
rake operation.
%After having done this, nodes $x$ and $e$ and their associated equations
%can be removed from the tree. 
%$A$, $B$, $C$ and $D$ are
%matrices and $e$ is an evidence node (so that $\lambda(e)$ is constant).
%Since nodes $x$ and $e$ have been removed from the tree, they
%will have no equations at level~$(i+1)$ or higher.

%adam: restored it to full page formatting
In the following, let
$\Diag{\alpha}$ denote the diagonal matrix whose diagonal
entries are the components of the vector $\alpha$.
We derive the algebraic effect of the rake operation as follows:
%Using the properties given in the Lemma above, for $\lambda (u)$ we obtain:
\begin{eqnarray*}
%  \LambdaEq{u}{v}{x}{i} \\
%    & = & \A{u}{i} \cdot \lambda (v) \Dyad \B{u}{i} %\\
%       && \qquad \cdot \left( \LambdaForm{x}{e}{z}{i} \right) \\
%    & = & \A{u}{i} \cdot \lambda (v) \Dyad \B{u}{i} %\\
%       && \qquad \cdot \left( \Diag{\A{x}{i} \cdot \lambda (e)} \cdot \B{x}{i}
%            \cdot \lambda (z) \right) \\
%    & = & \A{u}{i} \cdot \lambda (v) \Dyad \\
%       && \qquad \left( \B{u}{i} \cdot \Diag{\A{x}{i} \cdot \lambda (e)}
%            \cdot \B{x}{i} \right)
%            \cdot \lambda (z) \\
%    & = & \LambdaForm{u}{v}{z}{i+1} \smallskip\\
  \LambdaEq{u}{v}{x}{i} \\
    & = & \A{u}{i} \cdot \lambda (v) \Dyad \B{u}{i}
        \cdot \left( \LambdaForm{x}{e}{z}{i} \right) \\
    & = & \A{u}{i} \cdot \lambda (v) \Dyad \B{u}{i} 
        \cdot \left( \Diag{\A{x}{i} \cdot \lambda (e)} \cdot \B{x}{i}
            \cdot \lambda (z) \right) \\
    & = & \A{u}{i} \cdot \lambda (v) \Dyad 
        \left( \B{u}{i} \cdot \Diag{\A{x}{i} \cdot \lambda (e)}
            \cdot \B{x}{i} \right)
            \cdot \lambda (z) \\
    & = & \LambdaForm{u}{v}{z}{i+1} \smallskip
\end{eqnarray*}
where $\A{u}{i+1} = \A{u}{i}$ and
$\B{u}{i+1} = \B{u}{i} \cdot \Diag{\A{x}{i} \cdot \lambda (e)} \cdot
\B{x}{i}$.
(Of course, the case where the leaf being raked is a right child
generates analogous equations.)
Thus, by defining $\A{u}{i+1}$ and 
$\B{u}{i+1}$ in this way, we ensure that all $\lambda$ values in
the raked tree are identical to
the corresponding values in the original tree.
This is not yet enough, because we must check that $\pi$ values
are similarly preserved. The only two values that could possibly
change are $\pi(z)$ and $\pi(v)$, so we check them both.
For the former, we must have
\begin{eqnarray*}
  \PiEq{z}{x}{e}{i} \\
    & = & \PiForm{z}{u}{v}{i+1}.
\end{eqnarray*}
After substituting for $\pi(x)$ and some algebraic manipulation,
we see that this is assured if 
$\C{z}{i+1} = \C{x}{i}$ and 
$\D{z}{i+1}= \D{z}{i} \cdot \Diag{\C{z}{i} \cdot \lambda (e)} \cdot
\D{x}{i}$.
However recall that, by definition, $\C{z}{i+1} = \A{u}{i+1}$
and $\C{x}{i} = \A{u}{i}$, and so $\C{z}{i+1} = \C{x}{i}$ follows.
Furthermore,
\begin{eqnarray*}
 \D{z}{i+1} & = &\B{u}{i+1}\Transpose \\
            & = &(\B{u}{i} \cdot \Diag{\A{x}{i}
                            \cdot \lambda (e)} \cdot \B{x}{i})\Transpose\\
            & = & \B{x}{i}\Transpose \cdot
                  \Diag{\A{x}{i} \cdot \lambda (e)} \cdot
                  \B{u}{i}\Transpose \\
            & = & \D{z}{i} \cdot
                  \Diag{\C{z}{i} \cdot \lambda (e)} \cdot
                  \D{x}{i}
\end{eqnarray*}
as required.

\noindent
For $\pi (v)$ it is necessary to verify that
\begin{eqnarray*}
  \PiEq{v}{u}{x}{i} \\
    & = & \PiForm{v}{u}{z}{i+1}.
\end{eqnarray*}
By substituting for $\lambda(x)$, this can be shown to be true if 
$\D{v}{i+1} = \D{v}{i} = \A{u}{i}\Transpose = \A{u}{i+1}\Transpose $
and
$\C{v}{i+1} = \C{v}{i} \cdot \Diag{\A{x}{i} \cdot \lambda (e)} \cdot \B{x}{i}
                = \B{u}{i+1}$.
But these identities follow by definition, so we are done.

\smallskip
%adam: not sure what this added, so deleted it
%Note that since node $e$ is a leaf, the value of $\lambda (e)$
%is known.  The situation is entirely symmetric if the leaf being
%raked is a right child.
%If node $v$ is also raked in
%contracting $T_i$ to $T_{i+1}$, then it is replaced in the
%$\pi (z)$-equation by the node that took its place.

Beginning with the given tree $T = T_0$, each successive
tree is constructed by performing a sequence of rakes, so as to rake
away about half of the remaining evidence nodes.
More specifically, let \Raketree\ be the
operation in which we apply the \Rake\ operation
to every other leaf of a causal tree, in left-to-right order,
excluding the leftmost and the rightmost leaf.
%adam: The following seems obvious. It isn't a property of Raketree as such,
%but merely a property of rake itself. (Ie, after any one rake you
%still have a probabilistic tree, so things remain ok).
%I've omitted it because it seems more confusing than helpful
%After each
%application of \Raketree, we can apply \Raketree\ again
%since all equations are in the correct form.
Let $\{ T_i \}$
be the set of causal trees constructed so that $T_{i+1}$ is the causal tree
generated from $T_i$ by a single application of \Raketree.
The following result is proved using an easy inductive argument:

\bthm{Theorem}{theoremctr}
  Let $T_0$ be a causal tree of size $N$.    Then
  the number of leaves in $T_{i+1}$ is equal to half the leaves in
  $T_i$ (not counting the two extreme leaves) so that starting with
  $T_0$, after $O (\log N)$ applications of \Raketree, we produce
  a three-node tree: the root, the leftmost leaf and the rightmost
  leaf.
\ethm

%The proof can be obtained by using induction
%and the previous lemma.
%%Which lemma?

%Below we make a few observations.
Below are a few observations about this process:
\begin{enumerate}
\item
  The complexity of \Raketree\ is linear in the size of the tree.
  Additionally, $\log N$ applications of \Raketree\ reduce the set of
  tree equations to a single equation involving the root in
  $O (N)$ total time.

\item
  The total space to store all the sets of equations associated
  with $\{ T_i \}_{0 \le i \le \log N}$ is %at most%
  about
  twice the space
  required to store the equations for $T_0$.

\item
  With each equation in $T_{i+1}$ we also store equations that
  describe the relationship between the conditional probability
  matrices in $T_{i+1}$ to the matrices in $T_i$.
  %adam: added this sentence.
  Notice that, even though $T_{i+1}$ is produced from $T_i$
  by a series of rake operations, each matrix in $T_{i+1}$
  depends directly on matrices present in $T_i$. This would not
  be the case if we attempted to simultaneously rake adjacent children.

  We regard
  these equations as part of $T_{i+1}$.  So, formally speaking
  $\{T_{i} \}$ are causal trees augmented
  with some auxiliary equations. Each of the contracted trees
  describes a probability distribution on a subset of the 
  first set of variables that is consistent with the original 
  distribution.
\end{enumerate}

We note that the ideas behind the
\Rake\ operation were
originally developed
by \citeasnoun{miller/reif}
in the context of parallel computation of 
bottom-up arithmetic expression trees
\cite{kosaraju/delcher/88,karp/ramachandran/90}. In contrast, we are using
it in the context of incremental update and query operations in
sequential computing.  A similar data structure to ours was
independently proposed by \citeasnoun{Fr93} in the context of 
dynamic arithmetic expression trees, and a 
different approach for incremental computing on 
arithmetic trees was developed by \citeasnoun{tamasia/cohen}.
There are important and interesting differences between the arithmetic
expression-tree case and our own.
For arithmetic expressions all
computation is done bottom-up.  However, in probabilistic networks
$\pi$-messages must be passed top-down.   
Furthermore, in arithmetic expressions when two 
algebraic operations are allowed,
we typically require the distributivity of one operation over the other,
but the analogous property does not hold for us. 
%Since the
%computation of $\pi$ vectors involves top-down computations in
%the tree, we substantially generalize the approach.  
%As shown above the operations do not distribute.
In these respects our approach is a substantial generalization of
the previous work, while remaining conceptually simple and practical.
%Our approach is also conceptually simple and practical.


%adam: shorter title; looks too ugly in 2column format otherwise
%\section{PERFORMING QUERIES AND UPDATE ON A CHAIN; AN EXAMPLE}
\section{Example: A Chain}
  \label{chainex}

%N is the number of nodes. We can't change this now!
To obtain an intuition about the algorithms, 
we sketch how to generate and utilize the 
$T_i,~ 0 \le i \le \log N$ and their equations
to perform $\lambda$-value queries and updates in $O (\log N)$ time on an
$N = 2L + 1$ node chain of length $L$.
%The general techniques are described in the previous sections.
Consider the chain of length 4 in 
Figure~\ref{chain/fig},  and the trees that are generated by
repeated application of \Raketree\ to the chain.
\begin{figure}
%           X1---->X2---->X3---->X4---->E5
%            |     |      |      |      
%            |     |      |      |    
%            |     |      |      |    
%            V     V      V      V    
% 
%            E1    E2    E3     E4    
%
%          Figure 4a.
%
%            X1---->X3---->E5
%            |     |    
%            |     |    
%            |     |     
%            V     V     
%            E1    E3    
%
%          Figure 4b.
%
%            X1--->E5
%            |
%            V     
%            E1   
%
%          Figure 4c.
  \bc
    \unitlength=0.010in
    \newcounter{nodectr}
    \begin{picture}(350,125)
      \put(60,100){\makebox(0,0)[r]{$T_0$:}}
      \multiput(100,100)(50,0){5}{\circle{20}}
        \setcounter{nodectr}{0}
        \multiput(100,100)(50,0){4}{\makebox(0,0){\addtocounter
              {nodectr}{1}$x_\arabic{nodectr}$}}
        \put(300,100){\makebox(0,0){$e_5$}}
        \multiput(110,100)(50,0){4}{\vector(1,0){30}}
        \multiput(100,90)(50,0){4}{\vector(0,-1){30}}
      \multiput(100,50)(50,0){4}{\circle{20}}
      \setcounter{nodectr}{0}
      \multiput(100,50)(50,0){4}{\makebox(0,0){\addtocounter
              {nodectr}{1}$e_\arabic{nodectr}$}}
    \end{picture} \\[-24pt]
    \begin{picture}(350,150)
      \put(60,100){\makebox(0,0)[r]{$T_1$:}}
      \multiput(100,100)(50,0){3}{\circle{20}}
        \setcounter{nodectr}{-1}
        \multiput(100,100)(50,0){2}{\makebox(0,0){\addtocounter
              {nodectr}{2}$x_\arabic{nodectr}$}}
        \put(200,100){\makebox(0,0){$e_5$}}
        \multiput(110,100)(50,0){2}{\vector(1,0){30}}
        \multiput(100,90)(50,0){2}{\vector(0,-1){30}}
      \multiput(100,50)(50,0){2}{\circle{20}}
      \setcounter{nodectr}{-1}
      \multiput(100,50)(50,0){2}{\makebox(0,0){\addtocounter
              {nodectr}{2}$e_\arabic{nodectr}$}}
    \end{picture} \\[-24pt]
    \begin{picture}(350,115)(0,35)
      \put(60,100){\makebox(0,0)[r]{$T_2$:}}
      \multiput(100,100)(50,0){2}{\circle{20}}
        \put(100,100){\makebox(0,0){$x_1$}}
        \put(150,100){\makebox(0,0){$e_5$}}
        \put(110,100){\vector(1,0){30}}
        \put(100,90){\vector(0,-1){30}}
      \put(100,50){\circle{20}}
      \put(100,50){\makebox(0,0){$e_1$}}
    \end{picture} \\[-24pt]
  \ec

  \caption{A simple chain example.}
    \label{chain/fig}
\end{figure}

The equations that correspond to the contracted trees in the
figure are as follows (ignoring trivial equations).
Recall that $A_i(x_j) $ is the matrix associated with the left edge of
random
%adam: changed
%variable $x_j$ at level $i$ of the data structure.
variable $x_j$ in $T_i$.
\[
  \left.
  \begin{array}{rcl}
    \hspace*{6pt} \LambdaEq{x_1}{e_1}{x_2}{0} \\
    \LambdaEq{x_2}{e_2}{x_3}{0} \\
    \LambdaEq{x_3}{e_3}{x_4}{0} \\
    \LambdaEq{x_4}{e_4}{e_5}{0}
  \end{array}
  \right\} \enskip \mbox{for $T_0$}
\]
\[
  \left.
  \begin{array}{rcl}
    %adam: changed x_2 --> x_3 in next line; surely x_2 was wrong!?
    \LambdaEq{x_1}{e_1}{x_3}{1} \\
    \LambdaEq{x_3}{e_3}{e_5}{1} \\[3pt]
    \multicolumn{2}{c}{\mbox{where}} \\[3pt]
    \B{x_1}{1} & = & \B{x_1}{0} \cdot \Diag{\A{x_2}{0} \cdot \lambda (e_2)} \cdot \B{x_2}{0} \\
    \B{x_3}{1} & = & \B{x_3}{0} \cdot \Diag{\A{x_4}{0} \cdot \lambda (e_4)}
    \cdot \B{x_4}{0}
  \end{array}
  \right\} \enskip \mbox{for $T_1$}
\]
\[
  \left.
  \begin{array}{rcl}
    \LambdaEq{x_1}{e_1}{e_5}{2} \\[3pt]
    \multicolumn{2}{c}{\mbox{where}} \\[3pt]
    \B{x_1}{2} & = & \B{x_1}{1} \cdot \Diag{\A{x_3}{1} \cdot \lambda (e_3)} \cdot \B{x_3}{1}
  \end{array}
  \right\} \enskip \mbox{for $T_2$}
\]

%adam: added following line.
We have not listed the $A$ matrices because, in this example,
they are constant.
Now consider a query operation on $x_2$.  Rather than performing
the standard computation we will find the level where $x_2$ was
``raked''.
%adam: Added ``Since this occurred on level 0
Since this occurred on level 0, we obtain the equation
%This gives us the equation
\begin{eqnarray*}
  \LambdaEq{x_2}{e_2}{x_3}{0}
\end{eqnarray*}
%adam: added next sentence
Thus we must compute $\lambda(x_3)$, and to do this we 
find where $x_3$ is ``raked''.  That happened on level 1.
However, on that level the equation associated with $x_3$ is:
\begin{eqnarray*}
  \LambdaEq{x_3}{e_3}{e_5}{1}
\end{eqnarray*}
That means that we need not follow down the chain.  In general
for a chain of $N$ nodes we can answer any query to a node on
the chain by evaluating $\log N$ equations instead of $N$
equations.

Now consider an update for $e_4$.  Since $e_4$ was raked
immediately, we first modify the equation
\[
\B{x_3}{1} = \B{x_3}{0} \cdot \Diag{\A{x_4}{0} \cdot \lambda (e_4)} \cdot \B{x_4}{0}
\]
on the first level where $e_4$ occurs on the right-hand side.
Since $\B{x_3}{1}$ is affected by the change to $e_4$, we
subsequently modify the equation
\[
\B{x_1}{2} = \B{x_1}{1} \cdot \Diag{\A{x_3}{1} \cdot \lambda (e_3)} \cdot \B{x_3}{1}
\]
on the second level.
%adam: added next sentence
In general, we clearly need to update at most $\log N$ equations; \ie, one
per level. 
We now generalize this example and describe
general algorithms for queries and updates in causal trees.

\subsection{Performing Queries And Updates Efficiently}

In this section we shall show how to utilize the contracted trees
$T_i,~ 0 \le i \le \log N$
%and their equations that were
%obtained by a repeated application of \Raketree\
to perform
queries and updates in $O (\log N)$ time in general causal trees.  We
shall show that a logarithmic amount of work will be necessary
and sufficient to compute enough information in our
data structure to update and query any $\lambda$ or $\pi$
value. 

\subsection{$\lambda$ Queries}

To compute $\lambda (x)$ for some node $x$ we can do the
following.  We first locate $\Index{x}$, which is defined to be the highest
level $i$
%adam: changed
%for which $x$ has equations.
such that $x$ appears in $T_i$.
The equation for
$\lambda (x)$ is of the form:
\begin{eqnarray*}
  \LambdaEq{x}{y}{z}{i}
\end{eqnarray*}
where $y$ and $z$ are the left and right children, respectively,
of $x$ in $T_i$.

Since $x$ does not appear in $T_{i+1}$, it was raked at
this level of equations, which implies that one child (we
assume $z$) is a leaf.  We therefore  only need to compute $\lambda (y)$,
which can be done recursively.
%adam: what? this multiply doesn't make sense 
%and multiply the result by
%$\A{x}{i} \cdot \lambda (e) \Dyad \B{x}{i}$.
If instead $y$ was the raked leaf, we would compute $\lambda (z)$
recursively.

In either case $O(1)$ operations are done in addition to one
recursive call, which is to a value at a higher level of
equations.  Since there are $O (\log N)$ levels, and the only operations
are matrix by vector multiplications, the procedure
takes $O (k^2 \log N)$ time.  The function \LambdaQuery{x} is
given in Figure~\ref{lambda/query/fig}.
\newlength{\ProcWidth}
\setlength{\ProcWidth}{\hsize}
\addtolength{\ProcWidth}{-2em}
\begin{figure}
  \bc
  \fbox{\,\begin{minipage}{\ProcWidth}
  \parindent=0pt
  \advance \parskip by 3pt
  \vstrut{3ex}{\sl FUNCTION} \LambdaQuery{x}

  \smallskip

  We look up the equation associated with $\lambda(x)$ in
  $T_{\mbox{\footnotesize\sl ind}\, (x)}$.
  \bl{\leftmargin=1.2em}
  \exdent\hskip 0.5em  Case 1:  $x$ is a leaf.  Then the equation is of the form:
    $\lambda (x) = e$ where $e$ is known.  In this
    case we return $e$.

  \exdent\hskip 0.5em  Case 2:  The equation associated with $\lambda (x)$ is
    of the form
    \begin{eqnarray*}
      \LambdaEq{x}{y}{z}{i}
    \end{eqnarray*}
    where $z$ is a leaf and therefore $\lambda(z)$ is known.
    In this case we return
    \[
      \A{X}{i} \cdot \LambdaQuery{y} \Dyad \B{X}{i} \cdot \lambda(z)
    \]
  \el
  The case where $y$ is the leaf is analogous. \smallskip
  \end{minipage}\,}
  \ec
  \caption{Function to compute the $\lambda$ value of a node.}
    \label{lambda/query/fig}
\end{figure}


\subsection{Updates}

We now describe how the update operations can modify enough
information in the data structure to allow us to query the
$\lambda$ vectors and $\pi$ vectors efficiently.  Most
importantly the reader should note that the update operation
does not try to maintain the correct $\pi$ and $\lambda$ values.
It is sufficient to ensure that, for all $i$ and $x$, the matrices
$\A{x}{i}$ and $\B{x}{i}$ (and thus also $\C{x}{i}$ and $\D{x}{i}$)
are always up to date. 
 
When we update the value of an evidence node, we are simply
changing the $\lambda$ value of some leaf $e$.  At each level of
equations, the value of $\lambda (e)$ can appear at most twice:
once in the $\lambda$-equation of $e$'s parent and once in the
$\pi$-equation of $e$'s sibling in $T_i$.  When $e$ disappears,
say at level $i$, its value is incorporated into one of the
constant matrices $\A{u}{i+1}$ or $\B{u}{i+1}$ where $u$ is the
grandparent of $e$ in $T_i$.  This constant matrix in turn
affects exactly one constant matrix in the next higher level,
and so on.  Since the effect at each level can be computed in
$O (k^3)$ time (due to matrix multiplication) and there are $O(\log N)$
levels of equations, the update can be accomplished in $O (k^3 \log N)$ time.
The constant $k^3$ is actually pessimistic, because faster 
matrix multiplication algorithms exist. 

The update procedure is given in Figure~\ref{update/fig}.
\begin{figure}[t]
%We look up the equation associated with $Node$ in 
%$\mbox{\sl EQUATIONS}_{\Index{Node}}$. \\
%Recall, this is the level of equations where $Node$ appeared last on the 
%right-hand side of some equation and was "raked" in this level. \\
  \bc
  \fbox{\,\begin{minipage}{\ProcWidth}
  \parindent=0pt
  \advance \parskip by 3pt
  \vstrut{3ex}{\sl FUNCTION} \LambdaUpdate{\mbox{\sl Term}}{\mbox{\sl Value}}{i}

  \bn
  \item
    Find the (at most one) equation in $T_i$, defining some $A_i$ or $B_i$,
    in which $\mbox{\sl Term}$ appears on the right-hand side;
    let $\mbox{\sl Term}'$ be the matrix defined by this equation (\ie,
    its left-hand side).
  
  \item
    Update $\mbox{\sl Term}'$; let \mbox{\sl Value} be the new value.

  \item
    Call \LambdaUpdate{\mbox{\sl Term}'}{\mbox{\sl Value}}{i + 1}
    recursively. \smallskip
  \en
  \end{minipage}\,}
  \ec
%  \smallskip
%  More specifically, let the following
%  \begin{eqnarray*}
%    \lambda(u) & = & \A{u}{i+1} \cdot \lambda (y) \Dyad \B{u}{i+1}
%         \cdot \lambda (v) \\
%    \A{u}{i+1} & = & \A{u}{i} \cdot \Diag{\alpha} \cdot \A{x}{i} 
%  \end{eqnarray*}
%  be the relevant equations where $\Diag{\alpha}$ is some diagonal
%  matrix.  Since $\mbox{\sl Term} = \A{u}{i}$ or
%  $\mbox{\sl Term} = \A{x}{i}$, we update $\A{u}{i+1}$ and
%  $\lambda (u)$ equations appropriately and call
%  \LambdaUpdate{\A{u}{i+1}}{\mbox{\sl Value}}{i + 1}
%
  \caption{The update procedure.}
    \label{update/fig}
\end{figure}
$\mbox{\sc Update}$ is initially called as
\mbox{\sc Update}$(\lambda (E) = e,i)$ where $E$ is a leaf, 
$i$ the level at which it was raked, and $e$ is the new evidence. 
This operation will start
a sequence of $O(\log N)$ calls to function
\LambdaUpdate{X}{\mbox{\sl Term}}{i} as the
change will propagate to $\log N$ equations.
%$\lambda$-equations.
%The
%first call is therefore of the form
%\LambdaUpdate{\lambda (E)}{e}{0}
%where $E$ is a leaf (evidence node) and $e$
%is a vector of constant probabilities.


\subsection{$\pi$ Queries}

It is relatively easy to use a similar recursive procedure to
perform $\pi (x)$ queries.  Unfortunately, this approach
yields an $O ({\log}^2 N)$-time algorithm if we simply
use recursion to calculate $\pi$ terms and calculate $\lambda$
terms using our earlier procedure.  This
is because there will be $O (\log N)$ recursive calls
to calculate $\pi$ values, but each is defined by an equation
that also involves a $\lambda$ term taking $O (\log N)$ time to
compute.

To achieve $O (\log N)$ time, we shall instead
implement $\pi (x)$
queries by defining a procedure \Calc{x, i} which returns a
triple of vectors $\langle P, L, R \rangle$ such that
$P = \pi (x)$, $L = \lambda (y)$ and $R = \lambda (z)$ where
$y$ and $z$ are the left and right children, respectively, of
$x$ in $T_i$.

To compute $\pi (x)$ for some node $x$ we can do the following.
%adam: rewrote, to use the \Index notation. Might as well use it
Let $i = \Index{x}$.
The equation for $\pi (x)$ in $T_i$ is of the form:
\begin{eqnarray*}
  \PiEq{x}{u}{v}{i}
\end{eqnarray*}
where $u$ is the parent of $x$ in $T_i$ and $v$ its sibling.  We
then call procedure \Calc{u, i+1} which will return the
triple $\langle \pi (u), \lambda (v), \lambda (x) \rangle$, from
which we immediately can compute $\pi (x)$ using the above
equation.

Procedure \Calc{x, i} can be implemented in the following
fashion.
\bl{\leftmargin=1.2em}
\exdent\hskip 0.5em  Case 1:  If $T_i$ is a 3-node tree with $x$ as its root,
  then both children of $x$ are leaves, hence their $\lambda$
  values are known, and $\pi (x)$ is a given sequence of prior
  probabilities for $x$.

\exdent\hskip 0.5em  Case 2:  If $x$ does not appear in $T_{i+1}$,
  then one of $x$'s children is a leaf, say $e$ which is raked at
  level $i$.  Let $z$ be the other child.  We call
  \Calc{u, i+1}, where $u$ is the parent of $x$ in $T_i$, and receive
  back $\langle \pi (u), \lambda (z), \lambda (v) \rangle$
  %adam: added next 3 lines although maybe this is a bit overcautious
  or $\langle \pi (u), \lambda (v), \lambda (z) \rangle$ according
  to whether $x$ was a left or right child of $u$ in $T_i$ (and $v$ is
  $u$'s other child). 
  We can
  now compute $\pi (x)$ from $\pi (u)$ and $\lambda (v)$, and
  we have $\lambda (e)$ and $\lambda (z)$, so we can return the
  necessary triple.

  Specifically,
  \[
    \pi (x) = \left\{ \begin{array}{l}
                \D{x}{i} \cdot \left( \pi (u) \Dyad \A{u}{i+1}
                   \cdot \lambda (v) \right) \\[5pt]
                \D{x}{i} \cdot \left( \pi (u) \Dyad \B{u}{i+1}
                   \cdot \lambda (v) \right)
              \end{array} \right.
  \]
  where the choice depends on whether $x$ is the right or left
  child, respectively, of $u$ in $T_i$.

\exdent\hskip 0.5em  Case 3:  If $x$ does appear in $T_{i+1}$,
  then we call \Calc{x, i+1}.  This returns the correct value of
  $\pi (x)$.  For any child $z$ of $x$ in $T_i$ that remains a
  child of $x$ in $T_{i+1}$, it also returns the correct value of
  $\lambda (z)$.  If $z$ is a child of $x$ that does not occur in
  $T_{i+1}$, then it must be the case that $z$ was raked at level $i$
  so that one of $z$'s children, say $e$, is a leaf and let the other
  child be $q$.  In this situation \Calc{x, i+1} has returned the
  value of $\lambda (q)$ and we can compute
  \[
    \lambda (z) = \LambdaForm{z}{e}{q}{i}
  \]
  and return this value.
\el

In all three cases, there is a constant amount of work done in addition
to a single recursive call that uses equations at a higher level.  Since
there are $O (\log N)$ levels of equations, each requiring only
matrix by vector multiplication, 
the total work done
is $O(k^2 \log N)$. 

\section{Extended Example}
  \label{example/sec}

In this section we illustrate the application of our algorithms
to a specific example.
Consider the sequence of contracted trees shown in
Figure~\ref{example/fig}.
\def\EE#1#2{\put(#1){\framebox(20,20){\small $e_{#2}$}}}
\def\XX#1#2{\put(#1){\circle{20}}\put(#1){\makebox(0,0){\small $x_{#2}$}}}
\begin{figure}
  \unitlength=0.009in
  \begin{picture}(420,340)(30,30)
    \put(150,360){\makebox(0,0){$T_0$:}}
    \EE{80,50}{2}
      \put(95,70){\line(1,2){20.5}}
    \EE{140,50}{3}
      \put(145,70){\line(-1,2){20.5}}
    \EE{50,110}{1}
      \put(65,130){\line(1,2){20.5}}
    \XX{120,120}{8}
      \put(115.5,129){\line(-1,2){21}}
    \EE{170,110}{4}
      \put(185,130){\line(1,2){20.5}}
    \EE{230,110}{5}
      \put(235,130){\line(-1,2){20.5}}
    \XX{90,180}{6}
      \put(97,187){\line(1,1){46}}
    \XX{210,180}{7}
      \put(203,187){\line(-1,1){46}}
    \EE{260,170}{6}
      \put(275,190){\line(1,2){20.5}}
    \EE{320,170}{7}
      \put(325,190){\line(-1,2){20.5}}
    \XX{150,240}{4}
      \put(158,246){\line(5,4){59}}
    \XX{300,240}{5}
      \put(292,246){\line(-5,4){59}}
    \EE{350,230}{8}
      \put(365,250){\line(1,2){20.5}}
    \EE{410,230}{9}
      \put(415,250){\line(-1,2){20.5}}
    \XX{225,300}{2}
      \put(233,306){\line(4,3){66}}
    \XX{390,300}{3}
      \put(382,306){\line(-4,3){66}}
    \XX{307,360}{1}
  \end{picture}
  \hfill
  \begin{picture}(210,280)(30,-30)
    \put(105,300){\makebox(0,0){$T_1$:}}
    \EE{50,50}{1}
      \put(65,70){\line(1,2){20.5}}
    \EE{110,50}{3}
      \put(115,70){\line(-1,2){20.5}}
    \XX{90,120}{6}
      \put(94.5,129){\line(1,2){21}}
    \EE{140,110}{5}
      \put(145,130){\line(-1,2){20.5}}
    \XX{120,180}{4}
      \put(124.5,189){\line(1,2){21}}
    \EE{170,170}{7}
      \put(175,190){\line(-1,2){20.5}}
    \XX{150,240}{2}
      \put(154.5,249){\line(1,2){21}}
    \EE{200,230}{9}
      \put(205,250){\line(-1,2){20.5}}
    \XX{180,300}{1}
  \end{picture} \\
  \hspace*{\fill}
  \begin{picture}(150,160)(30,30)
    \put(70,180){\makebox(0,0){$T_2$:}}
    \EE{50,50}{1}
      \put(65,70){\line(1,2){20.5}}
    \EE{110,50}{5}
      \put(115,70){\line(-1,2){20.5}}
    \XX{90,120}{4}
      \put(94.5,129){\line(1,2){21}}
    \EE{140,110}{9}
      \put(145,130){\line(-1,2){20.5}}
    \XX{120,180}{1}
  \end{picture}
  \hskip 60pt
  \begin{picture}(120,100)(30,-30)
    \put(50,120){\makebox(0,0){$T_3$:}}
    \EE{50,50}{1}
      \put(65,70){\line(1,2){20.5}}
    \EE{110,50}{9}
      \put(115,70){\line(-1,2){20.5}}
    \XX{90,120}{1}
  \end{picture}
  \hspace*{48pt}

  \caption{Example of tree contraction.}
    \label{example/fig}
\end{figure}
%adam: changed
%Corresponding to these trees we have the following equations:
Corresponding to these trees we have such equations as the following:
{\small\[
  \begin{array}{rcl@{\qquad}rcl}
    \multicolumn{3}{l}{\mbox{\hskip -0.5em \normalsize For $T_0$:}} \\
    \LambdaEq{x_1}{x_2}{x_3}{0} & \PiEq{x_2}{x_1}{x_3}{0} \\
      & \vdots &                &   & \vdots \\[10pt]
    \multicolumn{3}{l}{\mbox{\hskip -0.5em \normalsize For $T_1$:}} \\
    \LambdaEq{x_1}{x_2}{e_9}{1} & \PiEq{x_2}{x_1}{e_9}{1} \\
      & \vdots &                &   & \vdots \\[10pt]
    \multicolumn{3}{l}{\mbox{\hskip -0.5em \normalsize For $T_2$:}} \\
    \LambdaEq{x_1}{x_4}{e_9}{2} & \PiEq{x_4}{x_1}{e_9}{2} \\
      & \vdots &                &   & \vdots \\[10pt]
    \multicolumn{3}{l}{\mbox{\hskip -0.5em \normalsize For $T_3$:}} \\
    \LambdaEq{x_1}{e_1}{e_9}{3}
  \end{array}
\]}

%adam: changed; thinking about effects on the lambda equations is confusing
%We first consider the effect on the $\lambda$-equations of an
%update for $e_2$.  Since $e_2$ is raked immediately,
%its value is incorporated in the level-1 equations as:
Now consider, for instance, the effect of an update for $e_2$.
Since it is raked immediately, the new value of $\lambda(e_2)$ is
incorporated in:
{\small\[
  \begin{array}{rcl@{\qquad}rcl}
    \B{x_6}{1} & = & \B{x_6}{0} \cdot \Diag{\A{x_8}{0} \cdot \lambda (e_2)}
          \cdot \B{x_8}{0}
  \end{array}
\]}
%adam: changed:
%\noindent From subsequent \Rake\ operations we get:
\noindent From subsequent \Rake\ operations we know that $\A{x_4}{2}$
depends on $\B{x_6}{1}$, and $\A{x_1}{3}$ depends on $\A{x_4}{2}$,
so we must also update these values as follows:
{\small\[
  \begin{array}{rcl@{\qquad}rcl}
   \A{x_4}{2} & = & \A{x_4}{1} \cdot \Diag{\B{x_6}{1} \cdot \lambda (e_3)}
          \cdot \A{x_6}{1} \\
  \A{x_1}{3} & = & \A{x_1}{2} \cdot \Diag{\B{x_4}{2} \cdot \lambda (e_5)}
          \cdot \A{x_4}{2}
  \end{array}
\]}

%adam: deleted. There isn't a difference
%between the ``effect on the lambda equations'' and ``effect on the pi
%equations'' anymore, so this example isn't really showing anything new.
%In fact, because it seems to be implying something different is
%happening (which it isn't) I suspect it is more confusing than helpful

%We next consider the effect on the $\pi$ equations of an
%update for $e_8$.  Even though the value of $e_8$ affects
%adam: added ``almost''. It doesn't affect pi(x1) or pi(x3_
%almost all $\pi$ vectors in the tree, our approach modifies
%only the following values:
%{\small\[
%  \begin{array}{rcl@{\qquad}rcl}
%    \PiEq{x_2}{x_1}{e_9}{1}
%     & \C{x_2}{1} & = & \C{x_2}{0} \cdot \Diag{\A{x_3}{0} \cdot \lambda (e_8)}
%            \cdot \B{x_3}{0} \\
%    \PiEq{x_4}{x_1}{e_9}{2}
%    & \D{x_4}{2} & = & \D{x_4}{1} \cdot \Diag{\C{x_4}{1} \cdot \lambda (e_7)}
%          \cdot \D{x_2}{1}
%  \end{array}
%\]}

Finally, consider a query for $x_7$.  Since $x_7$ is raked together with
$e_5$ in $T_0$, we follow the steps outlined above and generate the
following calls: $\Calc{x_7, 0}$, $\Calc{x_4, 1}$, $\Calc{x_4, 2}$, and
$\Calc{x_1, 3}$.
%adam: added
This provides us with $\pi(x_7)$. In this case, $\lambda(x_7)$ is
particularly easy to compute since both $x_7$'s children are leaf nodes.
Then we simply compute $\pi(x_7) \Dyad \lambda(x_7)$ and then
normalize, giving us the 
conditional marginal distribution $\BEL(x_7)$ as required. 

\section{Join Trees}
  \label{jointree}

\begin{sloppypar}
Perhaps the best-known technique for computing with arbitrary
(\ie, {\em not\/} singly-connected) Bayesian networks uses the
idea of {\em join trees} (junction trees) \cite{lauritzen/spiegelharter}.
In many ways a join tree can be thought of as a causal tree, albeit one
with somewhat special structure. Thus the algorithm in the previous
section can be applied. However, the structure of a join tree
permits some optimization, which we describe in this section.
This becomes especially relevant in the next section, where we
use the join-tree technique to show how $O(\log N)$ updates and queries
can be done for arbitrary polytrees.
Our review of join-trees and their utility is extremely brief
and quite incomplete; for clear expositions see, for instance,
Spiegelhalter et~al.~\citeyear{LS:survey} and \citeasnoun{pearl/net}.
\end{sloppypar}

Given any Bayesian network, the first step towards constructing
a join-tree is to {\em moralize\/} the network: insert edges
between every pair of parents of a common node, and then treat all
edges in the graph as being undirected \cite{LS:survey}.
The resulting undirected graph is called the {\em moral\/} graph. 
We are interested in undirected graphs that are {\em chordal\/}:
every cycle of length 4 or more should contain a chord (\ie, an edge
between two nodes that are non-adjacent in the cycle).
If the moral graph is not chordal, it is necessary to add edges to
make it so; various techniques for this {\em triangulation\/}
stage are known (for instance, see \citeauthor{LS:survey}, 1993).

If $p$ is a probability distribution represented in a
Bayesian network $G=(V,E)$, and  $M = (V,F)$ is the result
of moralizing and then triangulating $G$, then:
\begin{itemize}
\item[1.] $M$ has at most $|V|$ cliques,\footnote{A {\em clique\/}
is a maximal completely-connected subgraph.}
  say $C_1, \ldots{}, C_{|V|}$.
\item[2.] The cliques can be ordered so that for each $i > 1$
there is some $j(i) < i$ such that
$$C_i \inter C_{j(i)} = C_i \inter (C_1 \union C_2 \union \ldots{} \union
C_{i-1}.)$$
The tree $T$ formed by treating the cliques as nodes, and connecting
each node $C_i$ to its ``parent'' $C_{j(i)}$, is called a {\em join tree}.
\item[3.] $  p = {\displaystyle \prod_{i}}\: p(C_i|C_{j(i)}) $
\item[4.] $p(C_i|C_{j(i)})  = p(C_i|C_{j(i)} \inter C_i)$
\end{itemize}
{From} 2 and 3, we see that if we direct the edges in $T$ away from the
``parent'' cliques, the resulting
directed tree is in fact a Bayesian causal tree that can represent 
the original distribution $p$. 
This is true no matter what the form of the original
graph. Of course, the price is that the cliques may be large, and
so the domain size (the number of possible values of a clique node) can
be of exponential size. This is why this technique is not guaranteed to
be efficient.

We can use the \Rake\ technique of Section~\ref{causal}
on the directed join tree without any modification. 
However, property 4 above shows that the conditional probability matrices
in the join tree have a special structure.
We can use this to gain some efficiency.
In the following, let $k$ be the domain size of the variables in $G$ as usual.
Let $n$ be the maximum size of cliques in the join tree; without
loss of generality we can assume that all cliques are of the same size
(because we can add ``dummy'' variables).
Thus the domain size
of each clique is $K= k^n$. Finally, let 
$c$ be the maximum intersection size of a clique and its
parent (\ie, $|C_{j(i)} \inter C_i|$) and $L = k^c$.

In the standard algorithm, we would represent $p(C_i|C_{j(i)})$
as a $K \times K$ matrix, $M_{C_i | C_{j(i)}}$.
However, $p(C_i|C_{j(i)} \inter C_i)$ can be represented as a smaller
$L \times K$ matrix,  $M_{C_i | C_{j(i)} \inter C_i}$.
By property 4 above, $M_{C_i | C_{j(i)}}$ is
identical to $M_{C_i | C_{j(i)} \inter C_i}$, except that many rows
are repeated. 
Thus there is a $K \times L$ matrix $J$ such that 
$$M_{C_i | C_{j(i)}} = J \cdot M_{C_i | C_{j(i)} \inter C_i}.$$
($J$ is actually a simple matrix whose entries are $0$ and $1$, with
exactly one $1$ per row; however we do not use this fact.)

Our claim is that, in the case of join trees, the following is true.
%adam: got rid of C_i and D_i; not needed. 
First, the matrices $A_i$ and $B_i$ used in the \Rake\ algorithm
can be stored in factored form, as the product of two matrices
of dimension $K \times L$ and $L \times K$ respectively. So, for instance,
we factor $A_i$ as $A^{l}_i \cdot A_i^r$. We never need to
explicitly compute, or store, the full matrices.
As we have just seen, this claim is true when $i = 0$ because the
$M$ matrices factor this way. The proof for $i > 1$ uses an inductive
argument, which we illustrate below.
The second claim is that, when the matrices are stored in factored form,
all the matrix multiplications used in the \Rake\ algorithm
are of one of the following types: 1) an $L \times K$ matrix times
a $K \times L$ matrix, 2) an $L \times K$ matrix times a $K \times K$
diagonal matrix, 3) an $L \times L$ matrix times an $L \times K$ matrix,
or 4) an $L \times K$ matrix times a vector.

To prove these claims consider, for instance, the equation defining
$B_{i+1}$ in terms of lower-level matrices. From Section~\ref{causal}, 
$ \B{u}{i+1} = \B{u}{i}
\cdot \Diag{\A{x}{i} \cdot \lambda (e)} \cdot \B{x}{i}.$ But, by
assumption, this is:
$$
(\Bfact{l}{u}{i} \cdot \Bfact{r}{u}{i}) \cdot 
   \Diag{(\Afact{l}{x}{i} \cdot \Afact{r}{x}{i}) \cdot \lambda (e)}\cdot
    (\Bfact{l}{x}{i} \cdot \Bfact{l}{x}{i}),
$$     
which, using associativity, is clearly equivalent to
$$
\Bfact{l}{u}{i} \cdot 
  \left[((\Bfact{r}{u}{i} \cdot 
  \Diag{\Afact{l}{x}{i} \cdot (\Afact{r}{x}{i} \cdot \lambda (e))})
  \cdot \Bfact{l}{x}{i}) \cdot \Bfact{l}{x}{i}\right].
$$
However, every multiplication in this expression is one of the forms stated
earlier. Identifying $\Bfact{l}{u}{i+1}$ as $\Bfact{l}{u}{i}$ and
$\Bfact{r}{u}{i+1}$ as the bracketed part of the expression
proves this case, and
of course the case where we rake a left child (so that $\A{u}{i+1}$
is updated) is analogous. 
%adam: removed; don't need to mention C_i and D_i.
%The equations for the matrices $A_i, C_i, D_i$ are similar.
Thus, even using the most straightforward technique for matrix
multiplication, the cost of updating $B_{i+1}$ is $O(K L^2) =
O(k^{n+2c})$. 
This contrasts with $O(K^3)$ if we do not factor the matrices, and
may represent a worthwhile speedup if $c$ is small.
Note that the overall time for an update using this scheme is 
$O(k^{n+2c} \log N)$. Queries, which only involve matrix by vector
multiplication, require $O(k^{n+c} \log N)$ time.

For many join trees the difference between $N$ and $\log N$
is unimportant, because the clique domain size $K$ is often
enormous and dominates the complexity.
%adam3: added (for reviewer)
Indeed, $K$ and $L$ may
be so large that we cannot represent the required matrices explicitly.
Of course, in such cases
our technique has little to offer. But there will be other cases in 
which the benefits
will be worthwhile. The most important general class in which this is so,
and our immediate reason for presenting the technique for join trees, is
the case of polytrees. 

\section{Polytrees}
  \label{polytree}

A polytree is a singly connected Bayesian network; we drop
the assumption of Section~\ref{causal} that each node has at most
one parent. Polytrees offer much more flexibility than causal trees,
and yet there is a well-known process that can update and query in 
$O(N)$ time, just as for causal trees.  For this reason polytrees are
an extremely popular class of networks.

We suspect that it is possible to present an $O(\log N)$ algorithm
for updates and queries in polytrees,  as a direct extension of the
ideas in Section~\ref{causal}. 
Instead we propose a different
technique, which involves converting a polytree to its join tree
and then using the ideas of the preceding section. 
The basis for this is the simple observation that the join tree
of a polytree is already chordal. Thus (as we show in detail below)
little is lost by considering the join tree instead of the original
polytree.
The specific property of polytrees that we require is the following.
We omit the proof of this well-known proposition.
\bthm{Proposition}{theoremctr}
  \label{polyprop}
  If $T$  is the moral graph of a polytree $P=(V,E)$ then 
  $T$ is chordal, and the set of maximal cliques in $T$ is
  $\set{\set{v} \union \parents{v} : v \in V}$.
\ethm
%\prf
%
%Consider any edge $(x, y) \in F$. By definition of the moral graph, 
%either $(x,y)$ (or $(y,x)$) is an edge in $E$ or else $x$ and $y$ have
%a common child in $P$. In the latter case, there is some $z \in V$ such
%that $(x,z)$ and $(y,z)$ are edges in both $E$ and $F$.
%Now suppose the moral graph is not chordal, and consider a
%cycle of length $\geq 4$ not containing a chord,
%say $C = x_1, \ldots{}, x_k = x_0$ where
%$k \geq 4$ and $(x_i,x_{i+1}) \in F$ for all $i < k$. 
%But then, for a contradiction, we can construct an undirected
%cycle in $P$. As we have seen, for all $i$ we have
%$(x_i,x_{i+1})$ (or the converse) in $E$ or else we can find a common child
%$z_i$ of both $x_i$ and $x_{i+1}$. Whenever the latter case holds, we can 
%insert $z_i$ between $x_i$ and $x_{i+1}$; the result is clearly 
%a closed path in $P$.
%To show that this closed path is in fact a cycle, we must show
%that all of the $z_i$ we have added are distinct. But this must be the
%case, because otherwise there must be $x_i$, $x_j$ which are nonadjacent
%in $C$ yet which have a common child. By the construction of the moral
%graph, there is in fact a chord between such nodes. 
%
%To prove the second part of the result, we must first show that
%$\set{v} \union \parents{v}$ is a maximal clique in the moral graph
%for each $v$. For if not, there is another node $w$ adjacent to
%$v$ and all its parents. Since $w$ is not a parent of $v$, $w$ must have
%a common child with $v$, say $z$.
%Consider any parent $x$ of $v$. If $x$ is a parent of $w$
%(or vice versa) then $v, x, w, z, v$ is a cycle in $E$, for a
%contradiction. Thus the reason that $x$ and $w$ are adjacent in $F$ must
%be because they share a common child, say $u$. It is impossible
%that $u = x$ for then $w$ is parent of $x$ after all. But
%then $v, x, u, w, z, v$ is a cycle in $E$, again for a contradiction.
%To complete the proof it is enough to recall that a chordal graph
%can only have at most $|V|$ maximal cliques (see Section~\ref{jointree}), and
%since the cliques $\set{v} \union \parents{v}$ are distinct we are done. 
%\eprf

Let  $p$ be the maximum number of parents
of any node. From the proposition, every maximal clique in the
join tree has at most $p+1$ variables, and so the domain size of a node
in the join tree is
$K = k^{p+1}$. This may be large, but recall that 
the conditional probability matrix in the original polytree,
for a variable with $p$ parents, has $K$ entries anyway
since we must give the conditional distribution for every combination
of the node's parents. 
Thus $K$ is really a measure of the size of the polytree itself.

It now follows from the proposition above that
we can perform query and update in polytrees in time $O( K^3 \log N)$, 
simply by using the algorithm of Section~\ref{causal} on
the directed join tree.
But, as noted in Section~\ref{jointree}, we can do better.
Recall that the savings depend on $c$, the maximum size of the 
intersection between any node and its parent in the join tree.
However, when the join tree is formed from a polytree, no two cliques
can share more than a single node. This follows immediately from
Proposition~\ref{polyprop}, 
for if two cliques have more than one node in common then
there must be either two nodes that share more than one parent,
or else a node and one of its parents that both share yet another parent. 
Neither of these is consistent with the network being a polytree. 
Thus in the complexity bounds of Section~\ref{jointree}, we can put $c = 1$.
It follows that we can 
process updates in $O( K k^{2c} \log N) = O(k^{p+3} \log N)$
time and queries in $O( k^{p+2} \log N)$. 


%\section{Conclusion}\label{conclusion}
%
%In this concluding section we provide several additional perspectives
%on this development. 
%
%While the message-based framework for probabilistic belief
%propagation is important and suggests a great degree of concurrency
%in this type of computation, it is not readily amenable for
%implementation on all classes of parallel machines
%(\eg, non-shared memory, fixed interconnection network 
%SIMD computers).
%It has been observed in many practical applications that 
%load balancing, management of queues and locality of reference
%play a significant role in practical implementations.
%In addition, it is clear that long chains require $O(N)$
%propagation time using standard sequential methods. 
%On the other hand, one class of computations that 
%has been mapped successfully onto many parallel machines,
%such as the CM2 and N-cube, is matrix-multiplication based computation
%(e.g., inner products, outer products, tensor products).
%Thus, for instance, the most efficient current parallel implementations
%of feed-forward neural networks on these machines actually use
%matrix multiplications rather than relying on the 
%message based frameworks.
%Since matrix multiplications are common in many signal processing 
%applications we are likely to see inexpensive 
%array and vector processors in the back of every workstation.
%Our approach suggests the possibility of parallelizing matrix
%multiplication during computation using specialized
%co-processors, while keeping the remainder of the computation
%sequential.
%Our approach requires only $O(\log N)$ matrix by matrix 
%multiplications for updates and $O(\log N)$ matrix by vector
%multiplications for queries. 
%
%Finally we comment on 
%an intriguing potential application of our approach
%in the domain of probabilistic modeling and simulation 
%of biological sequences.
%Recently, relatively robust probabilistic models have been built 
%for the recognition of double-stranded coils (special
%class of alpha helices) in protein sequences
%(see \cite{delcher/kasif/protein} for references).
%Once a stable probabilistic model is built a biologist can
%experiment with the model and perform a process called
%automated muta-genesis which is used in drug design. 
%During this process we perform an artificial simulation of evolution
%by repeatedly modifying one small component 
%(a single amino-acid replacement) of the protein sequence 
%and test if the structure at a particular 
%binding site is preserved.
%This technique is an important technique used in drug design,
%however it is slow and costly in a laboratory environment. 
%The techniques reported in the current paper suggest 
%the possibility of performing this process
%efficiently by a computer simulation (if the probabilistic models are robust).
%
%In \cite{delcher/kasif/protein} we report a modeling experiment 
%with a probabilistic causal tree of depth 300 that consists
%of 600 nodes and where all the matrices of conditional probabilities
%are $2 \times 2$.  The tree is used to model the dependence of
%a protein's secondary structure on its chemical structure.
%The detailed description of the problem
%and experimental results are given in \cite{delcher/kasif/protein}.
%For this problem we can obtain an effective
%speed-up of about a factor of 10 to perform a query/update cycle as
%compared to the standard algorithm.  
%Clearly, getting an order of magnitude improvement in the response time of a
%probabilistic real-time system could be of tremendous
%importance in future use of such systems. 


\def\SL#1{\mbox{\sl #1\/}}

{\sloppy
\section{Application: Towards Automated Site-Specific Muta-Genesis}
  \label{applic/sec}
}

\noindent
An experiment which is commonly performed in biology
laboratories is a procedure where a particular site in a protein
is changed (\ie, a single amino-acid is mutated) and then tested
to see whether the protein settles into a different conformation.  In
many cases, with overwhelming probability the protein does not
change its secondary structure outside the mutated region.  This
process is often called muta-genesis.
\citeasnoun{delcher/kasif/protein} developed a probabilistic model of a protein
structure which is basically a long chain.  The
length of the chain varies between 300--500 nodes.  The nodes in
the network are either protein-structure nodes (\SL{PS}-nodes) or
evidence nodes (\SL{E}-nodes).  Each \SL{PS}-node in the network is a
discrete random variable $X_i$ that assumes values corresponding
to descriptors of secondary sequence structure: helix, sheet or
coil.  With each \SL{PS}-node the model associates an evidence node
that corresponds to an occurrence of a particular subsequence of
amino acids at a particular location in the protein.

In our model, protein-structure nodes are finite strings over the alphabet
$\{ \SL{h}, \SL{e}, \SL{c} \}$.  For example the
string \SL{hhhhhh} is a string of six
residues in an $\alpha$-helical conformation, while \SL{eecc} is a
string of two residues in a $\beta$-sheet conformation followed
by two residues folded as a coil.  Evidence nodes are nodes that
contain information about a particular region of the protein.
Thus, the main idea is to represent physical and statistical
rules in the form of a probabilistic network.

In our first set of experiments we converged on the following
model that, while clearly biologically naive,
seems to match in prediction accuracy many existing
approaches such as neural networks. 
The network looks like a set of \SL{PS}-nodes
connected as a chain.  To each such node we connect a single
evidence node.  In our experiments the \SL{PS}-nodes are strings of
length two or three over the alphabet $\{ \SL{h}, \SL{e}, \SL{c} \}$ and the
evidence nodes are strings of the same length over the set of
amino acids.  The following example clarifies our
representation.  Assume we have a string of amino
acids \SL{GSAT}.  We model the string as a network comprised of
three evidence nodes \SL{GS}, \SL{SA}, \SL{AT} and three \SL{PS}-nodes.  The
network is shown in Figure~\ref{chain/pair/fig}.
\begin{figure}
  \bc \unitlength=1.4pt
    \begin{picture}(200,60)(15,0)
      \multiput(50,50)(50,0){3}{\oval(30,20)}
        \put(50,50){\makebox(0,0){\SL{cc}}}
        \put(100,50){\makebox(0,0){\SL{ch}}}
        \put(150,50){\makebox(0,0){\SL{hh}}}
      \multiput(65,50)(50,0){2}{\vector(1,0){20}}
      \multiput(50,40)(50,0){3}{\vector(0,-1){20}}
      \multiput(50,10)(50,0){3}{\oval(30,20)}
        \put(50,10){\makebox(0,0){\SL{GS}}}
        \put(100,10){\makebox(0,0){\SL{SA}}}
        \put(150,10){\makebox(0,0){\SL{AT}}}
    \end{picture}
  \ec
  \medskip

  \caption{Example of causal tree model using pairs, showing protein
      segment \SL{GSAT} with corresponding secondary
      structure \SL{cchh}.}
    \label{chain/pair/fig}
\end{figure}
A correct prediction will assign the values \SL{cc}, \SL{ch}, and \SL{hh}
to the \SL{PS}-nodes as shown in the figure.

Now that we have a probabilistic model, we can test the robustness of
the protein or whether small changes in the protein affect the structure
of certain critical sites in the protein.
In our experiments, 
the probabilistic network performs a ``simulated evolution'' 
of the protein, namely the simulator repeatedly mutates
a region in the chain and then tests whether some designated sites
in the protein that are coiled into a helix are predicted to
remain in this conformation.  The main goal of the experiment was
to test if stable bonds far away from the mutated
location were affected.  Our previous results
\cite{delcher/kasif/protein}
support the current thesis in the biology community, namely
that local distant changes rarely affect structure.

The algorithms we presented in the previous sections of the
paper are perfectly suited for this type of application and are
predicted to generate a factor of 10 improvement in efficiency
over the current brute-force implementation presented by
\citeasnoun{delcher/kasif/protein} where each change is propagated
throughout the network.

\section{Summary}

This paper has proposed several new algorithms that yield a
substantial improvement in the performance of probabilistic
networks in the form of causal trees.  
Our updating procedures 
absorb sufficient information in the tree such that our 
query procedure can compute the correct probability distribution of 
any node given the current evidence.  
In addition, all procedures execute in time $O(\log N)$, where $N$ is the
size of the network.
Our algorithms are
expected to generate orders-of-magnitude speed-ups for causal
trees that contain long paths (not necessarily chains) and for
which the matrices of conditional probabilities are relatively
small.  We are currently experimenting with our approach with singly
connected networks (polytrees).  It is likely to be more difficult to
generalize the techniques to general networks.  Since it is
known that the general problem of inference in probabilistic
networks is \NP-hard~\cite{cooper/90}, it obviously is not
possible to obtain polynomial-time incremental solutions of the
type discussed in this paper for general probabilistic networks.
The other natural open question
is extending the approach developed in this paper to 
other dynamic operations on probabilistic networks such as addition and 
deletion of nodes and modifying the matrices of conditional probabilities
(as a result of learning).

It would also be interesting to investigate the practical
logarithmic-time parallel algorithms for probabilistic networks
on realistic parallel models of computation.  One of the main
goals of massively parallel AI research is to produce networks
that perform real-time inference over large knowledge-bases very
efficiently (\ie, in time proportional to the depth of the
network rather than the size of the network) by exploiting
massive parallelism.  Jerry Feldman pioneered this philosophy in
the context of neural architectures (see
\citeauthor{stanfill/waltz/86},~1986, \citeauthor{shastri},~1993, and
\citeauthor{feldman/ballard}, 1982).  To achieve this type of
performance in the neural network framework, we typically
postulate a parallel hardware that associates a processor with
each node in a network and typically ignores communication
requirements.  With careful mapping to parallel architectures
one can indeed achieve efficient parallel execution of specific
classes of inference operations (see \citeauthor{mani/shastri},~1994,
\citeauthor{kasif/90},~1990, and \citeauthor{kasif/aij2}, 1992).  The
techniques outlined in this paper presented an alternative
architecture that supports very fast (sub-linear time) response
capability on sequential machines based on preprocessing.
However, our approach is obviously limited to applications where
the number of updates and queries at any time is constant.  One
would naturally hope to develop parallel computers that support
real-time probabilistic reasoning for general networks.

\acks{Simon Kasif's research at Johns Hopkins University was sponsored in 
part by National Science foundation under Grants No.\ IRI-9116843, IRI-9223591
and IRI-9220960.
}

\vskip 0.2in
\bibliographystyle{theapa}
%\bibliography{journal}

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Berger \BBA\ Ye}{Berger \BBA\ Ye}{1990}]{berger/ye}
Berger, T.\BBACOMMA\  \BBA\ Ye, Z. \BBOP1990\BBCP.
\newblock \BBOQ Entropic aspects of random fields on trees\BBCQ\
\newblock {\Bem IEEE Trans.~on Information Theory}, {\Bem 36\/}(5), 1006--1018.

\bibitem[\protect\BCAY{Chelberg}{Chelberg}{1990}]{chelberg}
Chelberg, D.~M. \BBOP1990\BBCP.
\newblock \BBOQ Uncertainty in interpretation of range imagery\BBCQ\
\newblock In {\Bem Proc. Intern. Conference on Computer Vision}, \BPGS\
  654--657.

\bibitem[\protect\BCAY{Cohen \BBA\ Tamassia}{Cohen \BBA\
  Tamassia}{1991}]{tamasia/cohen}
Cohen, R.~F.\BBACOMMA\  \BBA\ Tamassia, R. \BBOP1991\BBCP.
\newblock \BBOQ Dynamic trees and their applications\BBCQ\
\newblock In {\Bem Proceedings of the 2nd ACM-SIAM Symposium on Discrete
  Algorithms}, \BPGS\ 52--61.

\bibitem[\protect\BCAY{Cooper}{Cooper}{1990}]{cooper/90}
Cooper, G. \BBOP1990\BBCP.
\newblock \BBOQ The computational complexity of probabilistic inference using
  bayes belief networks\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 42}, 393--405.

\bibitem[\protect\BCAY{Delcher \BBA\ Kasif}{Delcher \BBA\
  Kasif}{1992}]{kasif/delcher/92}
Delcher, A.\BBACOMMA\  \BBA\ Kasif, S. \BBOP1992\BBCP.
\newblock \BBOQ Improved decision making in game trees: Recovering from
  pathology\BBCQ\
\newblock In {\Bem Proceedings of the 1992 National Conference on Artificial
  Intelligence}.

\bibitem[\protect\BCAY{Delcher, Kasif, Goldberg, \BBA\ Hsu}{Delcher
  et~al.}{1993}]{delcher/kasif/protein}
Delcher, A.~L., Kasif, S., Goldberg, H.~R., \BBA\ Hsu, B. \BBOP1993\BBCP.
\newblock \BBOQ Probabilistic prediction of protein secondary structure using
  causal networks\BBCQ\
\newblock In {\Bem Proceedings of 1993 International Conference on Intelligent
  Systems for Computational Biology}, \BPGS\ 316--321.

\bibitem[\protect\BCAY{Duda \BBA\ Hart}{Duda \BBA\ Hart}{1973}]{duda/hart/73}
Duda, R.\BBACOMMA\  \BBA\ Hart, P. \BBOP1973\BBCP.
\newblock {\Bem Pattern Classification and Scene Analysis}.
\newblock Wiley, New York.

\bibitem[\protect\BCAY{Feldman \BBA\ Ballard}{Feldman \BBA\
  Ballard}{1982}]{feldman/ballard}
Feldman, J.~A.\BBACOMMA\  \BBA\ Ballard, D. \BBOP1982\BBCP.
\newblock \BBOQ Connectionist models and their properties\BBCQ\
\newblock {\Bem Cognitive Science}, {\Bem 6}, 205--254.

\bibitem[\protect\BCAY{Frederickson}{Frederickson}{1993}]{Fr93}
Frederickson, G.~N. \BBOP1993\BBCP.
\newblock \BBOQ A data structure for dynamically maintaining rooted trees\BBCQ\
\newblock In {\Bem Proc. 4th Annual Symposium on Discrete Algorithms}, \BPGS\
  175--184.

\bibitem[\protect\BCAY{Hel-Or \BBA\ Werman}{Hel-Or \BBA\
  Werman}{1992}]{werman1}
Hel-Or, Y.\BBACOMMA\  \BBA\ Werman, M. \BBOP1992\BBCP.
\newblock \BBOQ Absolute orientation from uncertain data: A unified
  approach\BBCQ\
\newblock In {\Bem Proc. Intern. Conference on Computer Vision and Pattern
  Recognition}, \BPGS\ 77--82.

\bibitem[\protect\BCAY{Karp \BBA\ Ramachandran}{Karp \BBA\
  Ramachandran}{1990}]{karp/ramachandran/90}
Karp, R.~M.\BBACOMMA\  \BBA\ Ramachandran, V. \BBOP1990\BBCP.
\newblock \BBOQ Parallel algorithms for shared-memory machines\BBCQ\
\newblock In Van~Leeuwen, J.\BED, {\Bem Handbook of Theoretical Computer
  Science}, \BPGS\ 869--941. North-Holland.

\bibitem[\protect\BCAY{Kasif}{Kasif}{1990}]{kasif/90}
Kasif, S. \BBOP1990\BBCP.
\newblock \BBOQ On the parallel complexity of discrete relaxation in constraint
  networks\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 45}, 275--286.

\bibitem[\protect\BCAY{Kasif \BBA\ Delcher}{Kasif \BBA\
  Delcher}{1994}]{kasif/aij2}
Kasif, S.\BBACOMMA\  \BBA\ Delcher, A. \BBOP1994\BBCP.
\newblock \BBOQ Analysis of local consistency in parallel constraint
  networks\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 69}.

\bibitem[\protect\BCAY{Kosaraju \BBA\ Delcher}{Kosaraju \BBA\
  Delcher}{1988}]{kosaraju/delcher/88}
Kosaraju, S.~R.\BBACOMMA\  \BBA\ Delcher, A.~L. \BBOP1988\BBCP.
\newblock \BBOQ Optimal parallel evaluation of tree-structured computations by
  raking\BBCQ\
\newblock In Reif, J.~H.\BED, {\Bem VLSI Algorithms and Architectures:
  Proceedings of 1988 Aegean Workshop on Computing}, \BPGS\ 101--110. Springer
  Verlag.
\newblock LNCS 319.

\bibitem[\protect\BCAY{Lauritzen \BBA\ Spiegelhalter}{Lauritzen \BBA\
  Spiegelhalter}{1988}]{lauritzen/spiegelharter}
Lauritzen, S.\BBACOMMA\  \BBA\ Spiegelhalter, D. \BBOP1988\BBCP.
\newblock \BBOQ Local computations with probabilities on graphical structures
  and their applications to expert systems\BBCQ\
\newblock {\Bem J. Royal Statistical Soc. Ser. B}, {\Bem 50}, 157--224.

\bibitem[\protect\BCAY{Mani \BBA\ Shastri}{Mani \BBA\
  Shastri}{1994}]{mani/shastri}
Mani, D.\BBACOMMA\  \BBA\ Shastri, L. \BBOP1994\BBCP.
\newblock \BBOQ Massively parallel reasoning with very large knowledge
  bases\BBCQ\
\newblock \BTR, Intern. Computer Science Institute.

\bibitem[\protect\BCAY{Miller \BBA\ Reif}{Miller \BBA\
  Reif}{1985}]{miller/reif}
Miller, G.~L.\BBACOMMA\  \BBA\ Reif, J. \BBOP1985\BBCP.
\newblock \BBOQ Parallel tree contraction and its application\BBCQ\
\newblock In {\Bem Proceedings of the 26th IEEE Symposium on Foundations of
  Computer Science}, \BPGS\ 478--489.

\bibitem[\protect\BCAY{Pearl}{Pearl}{1988}]{pearl/net}
Pearl, J. \BBOP1988\BBCP.
\newblock {\Bem Probabilistic Reasoning in Intelligent Systems}.
\newblock Morgan Kaufmann.

\bibitem[\protect\BCAY{Peot \BBA\ Shachter}{Peot \BBA\
  Shachter}{1991}]{peot/shachter/91}
Peot, M.~A.\BBACOMMA\  \BBA\ Shachter, R.~D. \BBOP1991\BBCP.
\newblock \BBOQ Fusion and propagation with multiple observations in belief
  networks\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 48}, 299--318.

\bibitem[\protect\BCAY{Rachlin, Kasif, Salzberg, \BBA\ Aha}{Rachlin
  et~al.}{1994}]{rachlin/etal/94}
Rachlin, J., Kasif, S., Salzberg, S., \BBA\ Aha, D. \BBOP1994\BBCP.
\newblock \BBOQ Towards a better understanding of memory-based and bayesian
  classifiers\BBCQ\
\newblock In {\Bem Proceedings of the Eleventh International Conference on
  Machine Learning}, \BPGS\ 242--250\ New Brunswick, NJ.

\bibitem[\protect\BCAY{Shastri}{Shastri}{1993}]{shastri}
Shastri, L. \BBOP1993\BBCP.
\newblock \BBOQ A computational model of tractable reasoning: Taking
  inspiration from cognition\BBCQ\
\newblock In {\Bem Proceeding of the 1993 Intern. Joint Conference on
  Artificial Intelligence}. AAAI.

\bibitem[\protect\BCAY{Spiegelhalter, Dawid, Lauritzen, \BBA\
  Cowell}{Spiegelhalter et~al.}{1993}]{LS:survey}
Spiegelhalter, D., Dawid, A., Lauritzen, S., \BBA\ Cowell, R. \BBOP1993\BBCP.
\newblock \BBOQ Bayesian analysis in expert systems\BBCQ\
\newblock {\Bem Statistical Science}, {\Bem 8\/}(3), 219--283.

\bibitem[\protect\BCAY{Stanfill \BBA\ Waltz}{Stanfill \BBA\
  Waltz}{1986}]{stanfill/waltz/86}
Stanfill, C.\BBACOMMA\  \BBA\ Waltz, D. \BBOP1986\BBCP.
\newblock \BBOQ Toward memory-based reasoning\BBCQ\
\newblock {\Bem Communications of the ACM}, {\Bem 29\/}(12), 1213--1228.

\bibitem[\protect\BCAY{Wilsky}{Wilsky}{1993}]{wilsky/etal}
Wilsky, A. \BBOP1993\BBCP.
\newblock \BBOQ Multiscale representation of markov random fields\BBCQ\
\newblock {\Bem IEEE Trans. Signal Processing}, {\Bem 41}, 3377--3395.

\end{thebibliography}


\end{document}


