Approximating Bayesian Belief Networks by Arc Removal.
AbstractI propose a general framework for approximating Bayesian belief networks through model simplification by arc removal. Given an upper bound on the absolute error allowed on the prior and posterior probability distributions of the approximated network, a subset of arcs is removed, thereby speeding up probabilistic inference.
Introduction
Today, more and more applications based on the Bayesian belief network 1 formalism are
emerging for reasoning and decision making in problem domains with inherent uncertainty.
Current applications range from medical diagnosis and prognosis [1], computer vision [10], to
information retrieval [2]. As applications grow larger, the belief networks involved increase
in size. And as the topology of the network becomes more dense, the run-time complexity of
probabilistic inference increases dramatically, reaching a state where real-time decision making
eventually becomes prohibitive; exact inference in general with Bayesian belief networks has
been proven to be NP-hard [3].
For many applications, computing exact probabilities from a belief network is liable to be
unrealistic due to inaccuracies in the probabilistic assessments for the network. Therefore, in
general, approximate methods suffice. Furthermore, the employment of approximate methods
alleviates probabilistic inference on a network at least to some extend. Approximate methods
provide probability estimates either by employing simulation methods for approximate
first introduced by Henrion [7], or through methods based on model simplification,
examples are annihilating small probabilities [8] and removal of weak dependencies [13].
With the former approach, stochastic simulation methods [4] provide for approximate
inference based on generating multisets of configurations of all the variables from a belief
network. From this multiset, (conditional) probabilities of interest are estimated from the
occurrence frequencies. These probability estimates tend to approximate the true probabilities
Part of this work has been done at Utrecht University, Dept. of Computer Science, The Netherlands.
1 In this paper we adopt the term Bayesian belief network or belief network for short. Belief networks are
also known as probabilistic networks, causal networks, and recursive models.
if the generated multiset is sufficiently large. Unfortunately, the computational complexity of
approximate methods is still known to be NP-hard [5] if a certain accuracy of the probability
estimates is demanded for. Hence, just like exact methods, simulation methods have an
exponential worst-case computational complexity.
As has been demonstrated by Kjaerulff [13], forcing additional conditional independence
assumptions portrayed by a belief network provides a promising direction towards belief net-work
approximation in view of model simplification. However, Kjaerulff's method is specifically
tailored to the Bayesian belief universe approach to probabilistic inference [9] and model
simplification is not applied to a network directly but to the belief universes obtained from
a belief network. The method identifies weak dependencies in a belief universe of a network
and removes these by removing specific links from the network thereby enforcing additional
conditional independencies portrayed by the network. As a result, a speedup in probabilistic
inference is obtained at a cost of a bounded error in inference.
In this paper we propose a general framework for belief network approximation by arc
removal. The proposed approximation method adopts a similar approach as Kjaerulff's
method [13] with respect to the means for quantifying the strength of arcs in a network
in terms of the Kullback-Leibler information divergence statistic. In general, the Kullback-Leibler
information divergence statistic [14] provides a means for measuring the divergence
between a probability distribution and an approximation of the distribution, see e.g. [22].
However, there are important differences to be noted between the approaches. Firstly, the
type of independence statements enforced in our approach renders the direct dependence relationship
portrayed by an arc superfluous, in contrast to Kjaerulff's method where other links
may be rendered superfluous as well. As a consequence, we apply more localized the changes
to the network which allows a large set of arcs to be removed simultaneously. Secondly, as
has been mentioned above, Kjaerulff's method operates only with the Bayesian belief universe
approach to probabilistic inference using the clique-tree propagation algorithm of Lauritzen
and Spiegelhalter [16]. In contrast, the framework we propose operates on a network directly
and therefore applies to any type of method for probabilistic inference. Finally, given an
upper bound on the posterior error in probabilistic inference allowed, a (possibly large) set of
arcs is removed simultaneously from a belief network requiring only one pre-evaluation of the
network in contrast to Kjaerulff's method in which conditional independence assumptions are
added to the network one at a time.
The rest of this paper is organized as follows. Section 2 provides some preliminaries from
the Bayesian belief network formalism and introduces some notions from information theory.
In Section 3, we present a method for removing arcs from a belief network and analyze the
consequences of the removals on the represented joint probability distribution. In Section 4,
some practical approximation schemes are discussed, aimed at reducing the computational
complexity of inference on a belief network. To conclude, in Section 5 the advantages and
disadvantages of the presented method are compared to other existing methods for approximating
networks.
Preliminaries
In this section we briefly review the basic concepts of the Bayesian belief network formalism
and some notions from information theory. In the sequel, we assume that the reader is well
acquainted with probability theory and with the basic notions from graph theory.
2.1 Bayesian Belief Networks
Bayesian belief networks allow for the explicit representation of dependencies as well as independencies
using a graphical representation of a joint probability distribution. In general,
undirected and directed graphs are powerful means for representing independency models,
see e.g. [21, 22]. Associated with belief networks are algorithms for probabilistic inference
on a network by propagating evidence, providing a means for reasoning with the uncertain
knowledge represented by the network.
A belief network consists of a qualitative and a quantitative representation of a joint
probability distribution. The qualitative part takes the form of an acyclic digraph G in which
each vertex represents a discrete statistical variable for stating the truth of a
proposition within a problem domain. In the sequel, the notions of vertex and variable are used
interchangeably. Each arc in the digraph, which we denote as
called the tail of the arc, and vertex called the head of the arc, represents a direct causal
influence between the vertices discerned. Then, vertex V i is called an immediate predecessor
of vertex V j and vertex V j is called an immediate descendant of vertex V i . Furthermore,
associated with the digraph of a belief network is a numerical assessment of the strengths of
the causal influences, constituting the quantitative part of the network.
In the sequel, for ease of exposition, we assume binary statistical variables taking values
in the domain ftrue; falseg. However, the generalization to variables taking values in any
finite domain is straightforward. Each variable V i represents a proposition where
is denoted as v i and false is denoted as :v i . For a set of variables V , the conjunction
is called the configuration scheme of V ; a configuration
c V of V is a conjunction of value assignments to the variables in V . In the sequel, we use
the concept of configuration scheme to denote that a specific property holds for all possible
configurations of a set of variables.
Definition 2.1 A Bayesian belief network is a tuple
is an acyclic digraph with
(G)g is a set of real-valued functions
\Theta fC G
called assessment functions, such that for each configuration
of the set G (V i ) of immediate predecessors of vertex V i we have that
A probabilistic meaning is assigned to the topology of the digraph of a belief network by
means of the d-separation criterion [18]. The criterion allows for the detection of dependency
relationships between the vertices of the network's digraph by traversing undirected paths,
called chains, comprised by the directed links in the digraph. Chains can be blocked by a set
of vertices as is stated more formally in the following definition.
Definition 2.2 Let be an acyclic digraph. Let  be a chain in G. Then
is blocked by a set of vertices contains three consecutive vertices
which one of the following three conditions is fulfilled:
are on the chain  and
are on the chain  and
are on the chain  and oe
the set of vertices composed of X 2 and all its descendants.
Note that a chain  is blocked by ; if and only if  contains . In this
case, vertex X 2 is called a head-to-head vertex with respect to  [6].
Definition 2.3 Let be an acyclic digraph and let X, Y , Z ' V (G) be
disjoint subsets of vertices from G. The set Y is said to d-separate the sets X and Z in G,
denoted
G , if for each every chain from V i to V j in G is blocked
by Y .
The d-separation criterion provides for the detection of probabilistic independence relations
from the digraph of a belief network, as is stated more formally in the following definition.
Definition 2.4 Let be an acyclic digraph. Let Pr be a joint probability
distribution on V (G). Digraph G is an I-map for Pr if hX j Z j Y i d
G implies X?? Pr Y j Z for
all disjoint subsets X, Y , Z ' V (G), i.e. X is conditionally independent of Z given Y in Pr.
By the chain-rule representation of a joint probability distribution from probability theory,
the initial probability assessment functions of a belief network provide all the information
necessary for uniquely defining a joint probability distribution on the set of variables discerned
that respects the independence relations portrayed by the digraph [11, 18].
Theorem 2.5 Let (G; \Gamma) be a belief network as defined in Definition 2.1. Then,
Y
defines a joint probability distribution Pr on V (G) such that G is an I-map for Pr.
A belief network therefore uniquely represents a joint probability distribution. For computing
(conditional) probabilities from a network, several efficient algorithms have been developed
from which Pearl's polytree algorithm with cutset conditioning [18, 19] and the method of
clique-tree propagation by Lauritzen and Spiegelhalter [16] (and combinations [20]) are the
most widely used algorithms for exact probabilistic inference. Simulation methods provide
for approximate probabilistic inference, see [4] for an overview.
2.2 Information Theory
The Kullback-Leibler information divergence [14] has several important applications in sta-
tistics. One of which is for measuring how well one joint probability distribution can be
approximated by another with a simpler dependence structure, see e.g. [22]. In the sequel,
we will make extensive use of the Kullback-Leibler information divergence. Before defining
the Kullback-Leibler information divergence more formally, the concept of continuity is
introduced [14].
Definition 2.6 Let V be a set of statistical variables and let Pr and Pr 0 be joint probability
distributions on V . Then Pr is absolutely continuous with respect to Pr 0 over a subset of
variables denoted as Pr  Pr 0 k X, if Pr(c X
configurations c X of X.
We will write Pr  Pr 0 for Pr  Pr 0 k V for short. Note that the continuity relation is
a reflexive and transitive relation on probability distributions. Furthermore, the continuity
relation satisfies
ffl if Pr  Pr 0 k X, then Pr  Pr 0 k Y for all subsets of variables X, Y ' V with Y ' X;
subsets of variables X, Y ' V
and each configuration c Y of Y with
That is, if a joint probability distribution Pr is absolutely continuous with respect to a distribution
Pr 0 over some set of variables X, then Pr is also absolutely continuous with respect to
Pr 0 over any subset of X. In addition, any posterior distribution
configuration c Y of Y is also absolutely continuous with respect to the posterior distribution
Definition 2.7 Let V be a set of statistical variables and let X ' V . Let Pr and Pr 0 be joint
probability distributions on V . The Kullback-Leibler information divergence or cross entropy
of Pr with respect to Pr 0 over X, denoted as I(Pr; Pr 0 ; X), is defined as
In the sequel, we will write short. Note that the information
divergence is not symmetric in Pr and Pr 0 and is finite if and only if Pr is absolutely continuous
with respect to Pr 0 . Furthermore, the information divergence I satisfies
subsets of variables X ' V , especially
only if Pr(CX
subsets of variables
subsets of variables X, Y ' V if
and Y are independent in both Pr and Pr 0 .
In principle, the base of the logarithm for the Kullback-Leibler information divergence is
immaterial, providing only a unit of measure; in the sequel, we use the natural logarithm.
With this assumption the following property holds.
Proposition 2.8 Let V be a set of statistical variables and let Pr and Pr 0 be joint probability
distributions on V . Furthermore, let I be the Kullback-Leibler information divergence as
defined in Definition 2.7. Then,
for all X ' V .
Hence, the Kullback-Leibler information divergence provides for an upper bound on the
absolute divergence jPr(c X configurations c X of X, a property of the
Kullback-Leibler information divergence known as the information inequality [15].
r
s
CC appoximation CTP appoximation

Figure

1: Reducing the complexity of cutset conditioning (CC) and clique-tree propagation (CTP)
by removing arc
3 Approximating a Belief Network by Removing Arcs
In this section we propose a method for removing arcs from a belief network and we investigate
the consequences of the removal on the computational resources and the error introduced. For
ease of exposition, a method for removing a single arc from a belief network is introduced first.
Then, based on this method and the observations made, a method for multiple simultaneous
arc removals is presented.
3.1 Reducing the Complexity of a Belief Network by Removing Arcs
The computational complexity of exact probabilistic inference on a belief network depends to
a large extend on the connectivity of the digraph of the network. Removing an arc from the
digraph of the network may substantially reduce the complexity of probabilistic inference on
the network. For Pearl's polytree algorithm with the method of cutset conditioning [18, 19],
undirected cycles, called loops [18], can be broken resulting in smaller loop cutsets to be
used. The size of the cutset determines the computational complexity of inference on the
network to a large extend. For the method of clique-tree propagation [16], a belief network is
first transformed into a decomposable graph. Here, the computational complexity of inference
depends to a large extend on the size of the largest clique in the decomposable graph. Removal
of an appropriate arc or edge results in splitting cliques into several smaller cliques, see e.g.
the method of Kjaerulff [13], yielding a reduction in computational complexity of inference
on the decomposable graph.
In

Figure

1 we have depicted the effect of removing an arc from the digraph of a belief
network for the method of cutset conditioning and for the method of clique-tree propagation.
For cutset conditioning, a vertex in the cutset (e.g. the vertex drawn in shading) is required
to break the loop. Since removal of arc breaks the loop, a smaller cutset may be
necessary. For clique-tree propagation, the decomposable graph obtained from the example
belief network has three cliques, each with 4 vertices. Removal of arc results in a
decomposable graph with four smaller cliques, one with 2 and three with 3 vertices.
For approximate methods, the computational complexity of for example forward simulation
[4] depends to some extend on the distance from a root vertex to a leaf vertex. Therefore,
the removal of arcs may also yield a reduction in the complexity of approximate inference.
However, it is more difficult to analyze and measure the amount of reduction in complexity
in general in comparison to exact methods and in the sequel we will discuss arc removal in
view of exact methods for probabilistic inference.
3.2 Removing an Arc from a Belief Network
Although several methods for removing an arc from a belief network can be devised, the
method for removal of an arc as defined in the following definition is the most natural choice.
This will be made clear when we analyze the effects of the removal.
Definition 3.1 (G; \Gamma) be a belief network and let Pr be the joint probability distribution
defined by B. Let V r be an arc in G. We define the tuple B
is the acyclic digraph with V (G Vr6!Vs
(G)g is the set of functions
with
Note that network B resulting after removal of an arc V r
from the digraph G of a belief network B, again constitutes a belief network. In this network
the assessment functions for the head vertex of the arc are changed only. In the sequel, we
will refer to B Vr6!Vs as the approximated belief network after removal of arc and the
operation of computing B Vr6!Vs will be referred to as approximating the network.
Removal of an arc from a belief network may result in a change of the represented joint
probability distribution. However, the represented dependency structure of the distribution
portrayed by the graphical part of the network may be retained by introducing a virtual arc
between the two vertices for which a physical arc is removed. A virtual arc may serve for the
detection of dependencies and independencies in the original probability distribution using
the d-separation criterion. A virtual arc, however, is not used in probabilistic inference, still
allowing for a faster, approximate computation of prior and posterior probabilities from the
simplified network.
3.3 The Error Introduced by Removing an Arc
Removing an arc from a belief network yields a (slightly) simplified network that is faster
in inference but exhibits errors in the marginal and conditional probability distributions. In
this section we will analyze the errors introduced in the prior and posterior distributions
upon belief network approximation by removal of an arc. These effects can be summarized as
introducing both a change in the qualitative (ignoring any virtual arcs) as well as a change
in the quantitative representation of a joint probability distribution.
The Qualitative Error in Prior and Posterior Distributions
The change in the qualitative belief network representation of the probabilistic dependency
structure by removing an arc from a belief network is described by the following lemma.
Lemma 3.2 Let G be an acyclic digraph and let V r be an arc in G. Let
be the digraph G with arc removed, that is,
g. Then, we have that hfV r g j
G Vr 6!Vs
Proof. To prove that hfV r
G Vr 6!Vs
holds, we show that every chain
from vertex V r to vertex V s in G Vr6!Vs is blocked by the set G Vr 6!Vs (V s ). For such a chain
from V r to V s two cases can be distinguished:
ffl  comprises an arc
chain  is blocked by G Vr 6!Vs (V s );
ffl  comprises an arc
is acyclic,  must contain a head-to-head vertex V k , i.e. a vertex with two converging
arcs on . Since oe
G Vr 6!Vs
blocked by G Vr 6!Vs (V s ).The property states that after removing arc digraph G of a belief network, the
simplified graphical representation now yields that variable V r is conditionally independent
of variable V s given G Vr 6!Vs (V s ) being the set of immediate predecessors of V s in the digraph
G with arc
The Quantitative Error in the Prior Distribution
The change in the qualitative dependency structure portrayed by the network has its quantitative
counterpart as the two are inherently linked together in the belief network formalism.
To analyze the error of the approximated prior probability distribution, similar to [13, 22]
we use the Kullback-Leibler information divergence for a quantitative comparison in terms of
the divergence between the joint probability distribution defined by a belief network and the
approximated joint probability distribution obtained after removing an arc from the network.
To facilitate the investigation, we will give an expression for the approximated joint probability
distribution in terms of the original distribution. First, we will introduce some additional
notions related to arcs in a digraph that are useful for describing the properties that
These notions are build on the observation that the set of immediate predecessors
G Vr 6!Vs (V s ) d-separates tail vertex V r from head vertex V s in the digraph G with arc
removed.
Definition 3.3 Let be an acyclic digraph and let V r be an
arc in G. We define the arc block of V r denoted as fi G as the set of
vertices g. Furthermore, we define the arc environment of V r
in G, denoted as j G as the set of vertices
The joint probability distribution defined by the approximated belief network can be factorized
in terms of the joint probability distribution defined by the original network.
Lemma 3.4 Let (G; \Gamma) be a belief network and let Pr be the joint probability distribution
defined by B. Let V r be an arc in G and let B be the
approximated belief network after removal of V r defined in Definition 3.1. Then the
joint probability distribution Pr Vr6!Vs defined by B Vr6!Vs satisfies
Pr Vr6!Vs (C V (G)
where is the arc environment of V r
as defined in Definition 3.3.
Proof. From Theorem 2.5, the joint probability distribution Pr Vr6!Vs defined by network
Pr Vr6!Vs (C V (G)
Y
where
Exploiting Definition 3.1 leads to
Y
Now, since fl Vs (V s j C G (Vs )
)Clearly, this property links the graphical implications of removing an arc from a belief net-work
with the numerical probabilistic consequences of the removal; variable V r is rendered
conditionally independent of variable V s given G Vr 6!Vs (V s ) after removal of an arc V r
Now, one of the most important consequences to be investigated is the amount of absolute
divergence between the prior probability distribution and the approximated distribu-
tion. From the information inequality we have
for all subsets X ' V , where Pr and Pr Vr6!Vs are joint probability distributions on the
set of variables V defined by a belief network and the network with arc removed
respectively. However, we recall that this bound is finite only if Pr is absolutely continuous
with respect to Pr Vr6!Vs . We prove this property in the following lemma.
Lemma (G; \Gamma) be a belief network. Let V r be an arc in G and let
be the approximated belief network after removal of V r
defined in Definition 3.1. Then the joint probability distribution Pr defined by B is absolutely
continuous with respect to the joint probability distribution Pr Vr6!Vs defined by B Vr6!Vs over
Proof. To prove that Pr is absolutely continuous with respect to Pr Vr6!Vs over V (G), we
prove that Pr(c V (G) implies that Pr Vr6!Vs configurations c V (G) of
(G). First observe that from the chain rule of probability theory we have that
where is the arc environment of arc
s in G as defined by Definition 3.3. Now consider a configuration c V (G) of V (G) with
configuration we have that Pr(c j G (Vr !Vs
. Furthermore, Pr(c Vr " c Vs j c G (Vs )nfVr implies that
These observations lead to
Hence, if Pr(c we conclude that Pr  Pr Vr6!Vs . 2
From this property of absolute continuity, the Kullback-Leibler information divergence provides
a proper upper bound on the error introduced in the joint probability distribution by
removal of an arc from the network. However, the bound can be rather coarse as it can be
expected that removing an arc may not always affect the prior probabilities of some specific
marginal distributions defined by the network. This observation is formalized by the following
lemma which states that the divergence in the prior marginal distributions is always zero for
sets of vertices that are not descendants of the head vertex of an arc that is removed. In
fact, this property is a direct result from the chain-rule representation of the joint probability
distribution by a belief network.
Lemma 3.6 Let (G; \Gamma) be a belief network and let Pr be the joint probability distribution
defined by B. Let V r be an arc in G and let B be the
approximated belief network after removal of V r defined in Definition 3.1. Then the
joint probability distribution Pr Vr6!Vs defined by B Vr6!Vs satisfies
Pr Vr6!Vs (C Y
for all Y ' V (G) n oe
denotes the set comprised by V s and all its descendants

Proof. First, we will prove that
Y
G (V s ). By applying Theorem 2.5 and by marginalizing Pr we obtain
Y
Y
Y
for all configurations c X of X with the assumption that the configurations that occur within
the sum adhere to c V
. Now since G (V k
we find by rearranging terms
Y
Y
Y
for all configurations c X of X. Hence, we have
Y
By a similar exposition for network B Vr6!Vs , we have
Pr Vr6!Vs (CX
Y
where
Now observe that from Definition 3.1
and we obtain Pr Vr6!Vs (CX by principle of marginalization we
conclude that Pr Vr6!Vs (C Y
This property provides the key observation for the applicability of multiple arc removals as
will be described in Section 3.4.
The Quantitative Error in Posterior Distributions
Belief networks are generally used for reasoning with uncertainty by processing evidence. That
is, the probability of some hypothesis is computed from the network given some evidence. In
the belief network framework, this amounts to computing the revised probabilities from the
posterior probability distribution given the evidence. We will investigate the implications on
posterior distributions after removal of an arc. We begin our investigation by exploring some
general properties of the Kullback-Leibler information divergence.
Lemma 3.7 Let V be a set of statistical variables and let X, Y ' V be subsets of V . Let
Pr and Pr 0 be joint probability distributions on V . Then the Kullback-Leibler information
divergence I satisfies
Proof. We distinguish two cases: the case that Pr  Pr and the case that
ffl Assume that Pr  Pr 0 k X[Y . This assumption implies that the information divergence
2.7 we therefore have that
c X[Y
Here, we used the fact that if for some configuration c 0
Y of the set of variables Y
the probability distribution
Y ) is undefined, that is, if Pr(c 0
any configuration c 0
of X the probability Pr(c 0
log(Pr(c 0
definition. Therefore, we let the first sum in the
last equality above range over all configurations c Y of Y for which Pr(c Y ) ? 0. Now by
rearranging terms we find
log
Note that I(Pr; Pr
ffl Assume that Pr 6 Pr This implies that I(Pr; Pr
show that I(Pr; Pr
observe that from the assumption there exists a configuration c 0
Y of X [ Y such
that Pr(c 0
two cases are distinguished: the case
that Pr 0 (c 0
and the case that Pr 0 (c 0
- Assume that Pr 0 (c 0
implies that Pr(c 0
yields that Pr 6 Pr 0 k Y . By Definition 2.7 I(Pr; Pr using the fact
that the divergence I is non-negative
to
- Assume that Pr 0 (c 0
for the configurations c 0
X and
Y . Hence,
and by Definition 2.7 this implies that
non-negative, we
conclude that I(Pr; Pr
property of the Kullback-Leibler information divergence leads to the following lemma
stating an upper bound on the absolute divergence of the posterior probability distribution
defined by a belief network given some evidence and the (approximated) posterior probability
distribution defined by another (approximated) network.
Lemma 3.8 Let V be a set of statistical variables and let Pr and Pr 0 be joint probability
distributions on V such that Pr  Pr 0 . Let I be the Kullback-Leibler information divergence.
Then,
for all subsets of variables X, Y ' V and all configurations c Y of Y with
Furthermore, this upper bound on the absolute divergence is finite.
Proof. Consider two subsets X, Y ' V and a configuration c Y of Y with
this configuration, Pr  Pr 0 implies that Pr 0 hence, the posterior distributions
are well-defined. Furthermore, since Pr  Pr 0 also implies that
it follows from Proposition 2.8 that we have the finite upper bound
Furthermore, Lemma 3.7 yields that
Y )?0
When we consider the divergence isolation, we have
since for any configuration c 0
Y of Y with Pr(c 0
divergence
Y
is finite and non-negative. From these observations we finally find the finite upper bound
Y )Now, from this property of the information divergence, the absolute divergence between the
posterior distribution given evidence c Y for a subset of variables Y of a belief network B and
the approximated network B Vr6!Vs after removal of an arc V r ! V s is bounded by
where Pr is the joint probability distribution defined by B and Pr Vr6!Vs is the joint probability
distribution defined by B Vr6!Vs . This bound is finite since Pr is absolutely continuous
with respect to Pr Vr6!Vs . Furthermore, from this bound we find that in the worst case, i.e.
the error in probabilistic inference on an approximated belief net-work
is inversely proportional to the square root of the probability of the evidence; the more
unlikely the evidence, the larger the error may be.
3.4 Multiple Arc Removals
In this section we generalize the method of single arc removal from belief networks to a method
of multiple simultaneous arc removals, thereby still guaranteeing a finite upper bound on the
error introduced in the prior and posterior distributions.
We recall from Definition 3.1 that removing an arc yields an appropriate change of the
assessment functions only for the head vertex of the arc to be removed. Therefore, this
operation can be applied in parallel for all arcs not sharing the same head vertex. To formalize
this requirement, we introduce the notion of a linear subset of arcs of a digraph.
be an acyclic digraph with the set of vertices
indexed in ascending topological order. The relation OE G ' A(G) \Theta
A(G) on the set of arcs of G is defined as V r
pairs of arcs G. Furthermore, let A ' A(G) be a subset of arcs
in G. Then we say that A is linear with respect to G if the order OE G is a total order on A,
that is, either for each pair of distinct arcs
Note that a linear subset of arcs from a digraph contains no pair of arcs that have a head
vertex in common. Now, we formally define the simultaneous removal of a linear set of arcs
from a belief network.
(G; \Gamma) be a belief network. Let A ' A(G) be a linear subset of arcs
in G. We define the multiply approximated belief network, denoted as
the network resulting after the simultaneous removal of all arcs A from B by Definition 3.1.
That is, we obtain network
the digraph with V (GA
(G)g the set of functions
To analyze the error introduced in the prior as well as in the posterior distribution after
removal of a linear set of arcs from a belief network, we once more exploit the information
inequality. For obtaining a proper upper bound, the essential requirement is that the joint
probability distribution defined by the original network is absolutely continuous with respect
to the distribution defined by the multiply approximated network. To prove this, we will
exploit the ordering relation on the arcs of a digraph as defined above. This ordering relation
induces a total order on the arcs of a linear subset of arcs in a digraph and we show that
a consecutive removal of arcs from a belief network in arc linear order yields a multiply
approximated network. Then, by transitivity of the continuity relation, this directly implies
that the joint probability distribution defined by the original network is absolutely continuous
with respect to the distribution defined by the multiply approximated network.
Lemma 3.11 Let (G; \Gamma) be a belief network and let Pr be the joint probability distribution
defined by B. Let
1, be a linear
subset of arcs in G ordered with respect to OE G as defined in Definition 3.9, i.e. for all pairs
of arcs V r we have that i ! j. Now,
be the multiply approximated belief network after removal of all arcs A as
defined in Definition 3.10. Then,
Vrn 6!Vsn
where each (approximated) network on the right-hand side is approximated by removal of an
defined in Definition 3.1.
Proof. The proof is by induction on the cardinality of A.
Base case
For
holds as the
hypothesis for induction. Now, consider arc A. Then, by principle of in-
duction, to prove that
now have to prove that
. Obviously, the digraphs obtained after removal of this arc are
identical, i.e we have This leaves us with a proof for the probability
assessment functions. First, observe that the simultaneous removal of all arcs A from
network B yields network BA with probability assessment functions
where we have that fl 0
observe that the
removal of arc V rn!Vsn from network B AnfVrn !Vsn g yields probability assessment functions
which we find that fl 00
it remains to prove that fl 0
Vsn , or equivalently, that Pr(V sn j C G (Vsn )nfVrn
observe that from the ordering relation OE G we find that
all arcs A n fV rn ! V sn g that are removed from B are 'below' arc V rn ! V sn in the digraph G
of B, i.e. by assuming an ascending topological order of the vertices this implies that s i ? s n
g. Hence, ( G (V sn )[fV sn g)" oe
and by the induction hypothesis, we can apply Lemma 3.6 for each arc in
to find that Pr(V sn "C G (Vsn )nfVrn
thermore, this yields that Pr(V sn j C G (Vsn )nfVrn
Vsn and we conclude that
As a result of this property of multiple arc removals, the Kullback-Leibler information divergence
of the joint probability distribution defined by a belief network with respect to the
distribution defined by the multiply approximated network is finite. Furthermore, arc linearity
implies the following additive property of the Kullback-Leibler information divergence.
Lemma 3.12 Let (G; \Gamma) be a belief network and let Pr be the joint probability distribution
defined by B. Let A ' A(G) be a linear subset of arcs in G and let be the
multiply approximated belief network after removal of all arcs A as defined in Definition 3.10.
Let PrA be the joint probability distribution defined by BA . Then the Kullback-Leibler information
divergence I satisfies
Proof. First, we prove that Pr  PrA . Assume that the arcs in the linear set A are ordered
according to the relation OE G as defined in Definition 3.9, i.e. for all pairs of arcs V r i
we have that i ! j. From Lemma 3.5 we find that
Pr  Pr Vr 1
(Pr Vr 1
, . ,
is transitive, we conclude that Pr  PrA by application
of Lemma 3.11. Now, with this observation we find
is linear, we have for each arc
new probability assessment function fl 0
for each
This leads to
log
Vs
that linearity of a set of arcs to be removed is a sufficient condition for the property
stated above, yet not a necessary one.
From these observations, we have that the information inequality provides a finite upper
bound on the error introduced in the prior and posterior distributions of an approximated
belief network after simultaneous removal of a linear set of arcs. This bound is obtained by
summing the information divergences between the joint probability distribution defined by
the network and the approximated distribution after removal of each arc individually from
the set of arcs.
Example 1 Consider the belief network (G; \Gamma) where G is the digraph depicted in

Figure

2.
Figure

2: Information divergence for each arc in the digraph of an example belief network.
A

Table

1: Information inequality and absolute divergence of an approximated example belief network.
The set \Gamma consists of the probability assessment functions fl
For each arc V r digraph G, the information divergence I(Pr; Pr Vr6!Vs ) between the
joint probability distribution Pr defined by B and the joint probability distribution Pr Vr6!Vs
defined by the approximated network B Vr6!Vs after removal of V r computed and
depicted next to each arc in Figure 2.
Note that despite the presence of arc are conditionally
independent given variable V 7 from the fact that fl V9 (V 9
this graphically portrayed dependence can be rendered redundant and arc can be
removed without introducing an error in the probability distribution since I(Pr; Pr V86!V9
as shown in Figure 2.

Table

1 gives the upper bound provided by the information inequality and the absolute
divergence of the approximated joint probability distributions after removal of various linear
subsets of arcs A from the network's digraph. The table is compressed by leaving out all
linear sets containing arc for the set fV 8 because the second and
third column are both unchanged after leaving out this arc. Note that any subset of arcs
containing both arcs 7 is not linear.
From this example, it can be concluded that the upper bound provided by the information
inequality exceeds the absolute divergence by a factor of 2 to 3. Furthermore, note that some
arcs have more weight in the value of the absolute divergence. For example, the absolute
divergence for all sets containing arc
Approximation Schemes
In this section we will present static and dynamic approximation schemes for belief networks.
These schemes are based on the observations made in the previous section.
4.1 A Static Approximation Scheme
Clearly, arcs that significantly reduce the computational complexity of inference on a belief
network upon removal are most desirable to remove. However, the error introduced upon
removal may not be too large. For each arc, the error introduced upon removal of the arc is
expressed in terms of the Kullback-Leibler information divergence.
Efficiently Computating the Information Divergence for each Arc
Unfortunately, straightforward computation of the Kullback-Leibler information divergence is
computationally far too expensive as it requires summing over all configurations of the entire
set of variables, an operation in the order of O(2 jV (G)j ). However, the following property
of the Kullback-Leibler information divergence can be exploited to compute the information
divergence locally.
Lemma 4.1 Let V be a set of statistical variables and let X, Y , Z ' V be mutually disjoint
subsets of V . Let Pr and Pr 0 be joint probability distributions on V such that Pr 0 (C
the Kullback-Leibler
information divergence I satisfies
Proof. By exploiting the factorization of Pr 0 in terms of Pr we find that Pr  Pr 0 . Using
Definition 2.7 we derive
log Pr(c X[Y [Z )
Now, since
yields that
c X[Y[Z
c X[Y[Z
efficiently computing the Kullback-Leibler information divergence I(Pr; Pr Vr6!Vs ) for each
of a linear subset of arcs A of the digraph of a belief network, it suffices to
sum over all configurations of the arc block fi G only, which amounts
to computing the quantity
c  G (Vs )[fVsg
log
which is derived by application of the chain rule from probability theory. Hence, the computation
of the information divergence I(Pr; Pr Vr6!Vs ) only requires the probabilities Pr(C G (Vs ) ),
to be computed from the original belief net-
work. In fact, the latter two sets of probabilities can simply be computed from the former set
of probabilities using marginalization:
and these conditional probabilities are further used to compute
Furthermore, once the probabilities Pr(C G (Vs )
are known, the divergence I(Pr; Pr Vr6!Vs ) for
that share the same head vertex V s can be computed simultaneously since
these computations only require the probabilities Pr(C G (Vs ) ).
Selecting a Set of Arcs for Removal
For selecting an optimal set of linear arcs for removal one should carefully weight the advantage
of the reduction in computational complexity in inference on a belief network and the
disadvantage of the error introduced in the represented joint probability distribution after
removal of the arcs.
Given a linear subset of arcs A from the digraph of a belief network B, we define the
function expressing the exact reduction in computational complexity of inference on network
B as
where K is a cost function expressing the computational complexity of inference on a net-
work. Furthermore, we define the exact divergence function d given arcs A on the probability
distribution Pr defined by network B as the absolute divergence
Note that function K depends on the algorithms used for probabilistic inference. For example,
if the clique-tree propagation algorithm of Lauritzen and Spiegelhalter is employed, K(B)
expresses the sum of the number of configurations of the sets of variables of the cliques of the
decomposable graph rendered upon moralization and subsequent triangulation of the digraph.
Then, K(BA ) expresses this complexity in terms of the approximated network B after removal
of arcs A. Here, we assume an optimal triangulation of the moral graphs of B and BA , since
a bad triangulation of the moral graph of BA may even yield a negative value for c(B; A).
If Pearl's polytree algorithm with cutset conditioning is employed, K(B) equals the number
of configurations of the set of variables of the loop cutset of the digraph. Now, an optimal
selection method weights the advantage expressed by c(B; disadvantage expressed by
removal of a set of arcs A from network B.
Unfortunately, an optimal selection scheme will first of all depend heavily on the algorithms
used for probabilistic inference and, secondly, will depend on the purpose of the
network within a specific application. Furthermore, it is rather expensive from a computational
point of view to evaluate the exact measures c and d for all possible linear subsets of
arcs. In general, the employment of heuristic measures for the selection of a near optimal set
of arcs for removal will suffice. To avoid costly evaluations for all possible subsets of arcs,
the heuristic measures should be based on combining the local advantages (or disadvantages)
of removing each arc individually. Such heuristic functions ~
c and "
d for respectively c and d,
expressing the impact on the computational complexity and error introduced by removing an
arc may be defined with various degrees of sophistication. In fact, the Kullback-Leibler information
divergence measures how well one joint probability distribution can be approximated
by another exhibiting a simpler dependence structure [22, 13]. Hence, instead of computing
the absolute divergence, the information inequality can be used:
where is the information divergence associated with each arc
as described in the previous section. Note that "
d now combines the divergence
of removing each arc separately and independently.
For defining a heuristic function ~
c valuing the reduction in computational complexity of
inference with exact methods for probabilistic inference upon removal of a set of arcs from a
belief network, the following scheme can be employed. The complexity of methods for exacts
inference depends to a large extend on the connectivity of the digraph of a belief network.
With each arc in the digraph G, a set of loops (undirected cycles), denoted
as loopset loopset of an arc consists of all loops in the digraph
containing the arc; a loopset of an arc provides local information on the role of the arc in the
connectivity of the digraph. This set can be found by a depth-first search for all chains from
in the graph, backtracking for all possibilities and storing the set of vertices found
along each chain in the form of bit-vector. Now, we define the heuristic function ~ c as
~ c(B;
loopset
i.e. ~ c expresses the number of distinct loops that are broken by removal of a set of arcs from
the digraph plus a fraction ff 2 (0; 1] of the the total number of arcs rendered superfluous.
The optimal value for ff depends on the algorithm used for exact probabilistic inference.
Now, a combined measure reflecting the trade-off between the advantage ~ c and disadvantage
d of arc removal may have the form
as suggested by Kjaerulff [13] where  is chosen such that ~ c(B; A) is comparable to "
Function w expresses the desirability of removing a set of arcs from a belief network.
Now suppose that a maximum absolute error " ? 0 is allowed in probabilistic inference on a
multiply approximated belief network and further suppose that the probability of the evidence
to be processed is never smaller than some constant . Observe that from Lemma 3.8 a set
of arcs A can be safely removed from the network if   1I(Pr; PrA )=" 2 . Hence, an optimal
set of arcs can be found for removal if we solve the following optimization problem: maximize
w(B;A) for A ' A(G) subject to "
and A is linear. Note that the constraint
ensures that the error in the prior and posterior probability distribution never
exceeds ". This optimization problem can be solved by employing a simulated annealing
technique [12], or by using an evolutionary algorithm [17], to find a linear set of arcs for
removal that is nearly optimal. A 'real' optimal solution is not appropriate to search for,
since only heuristic functions are involved in the search process.
Example 2 Consider once more the belief network from Example 1. Suppose that the probability
of evidence to be processed by the approximated belief network does not exceed
and further suppose that the maximum absolute error allowed for the (conditional) probabilities
to be inferred from the approximated network is
First, three loops in G can be identified: loop 1 constitutes vertices
g.
Thus, the loopset of arc and the loopset of arc
c. The following table is obtained for "
A ~ c(B;
The linear set is the most desirable set of arcs for removal (w(B;
4:9547). Note that after removal, the graph GA is singly connected and, therefore, the network
is at least twice as fast for probabilistic inference compared to the original network using either
Pearl's polytree algorithm with cutset conditioning or the method of clique-tree propagation.
in
probability
Probability of evidence
Observed
Upper bound

Figure

3: Posterior error in probabilities inferred from an approximated example belief network.
Actually, the probability of evidence that can be processed with the approximated net-work
such that the error in inferred probabilities is bounded by " requires that Pr(c Y
In Figure 3 we show the observed
maximum absolute error and upper bound
obtained for all evidence c Y , Y ' V (G), with Pr(c Y )  0:205. 3
Efficiently Computing an Approximation of a Belief Network
Removal of a linear set of arcs from a belief network requires the computation of new set
of probability assessment functions that reflect the introduced qualitative conditional independence
with a quantitative conditional independence. We recall from Definition 3.1
that we have that the new probability assessment functions
removal of an arc V r
selected for removal only if the Kullback-Leibler information divergence I(Pr; Pr Vr6!Vs ) is sufficiently
small in order that the error introduced by approximating the network after removal
of bounded. The probabilities Pr(V
are in fact already computed
by the computation of the information divergence I(Pr; Pr Vr6!Vs ) for all arcs in the
digraph of a belief network. When these probabilities are stored temporarily, it suffices to
assign these probabilities to the new probability assessment functions of the head vertex of
each arc that is selected for removal.
4.2 A Dynamic Approximation Scheme
In this section we will consider belief networks with singly connected digraphs as a special case
for approximation. A singly connected digraph exhibits no loops, that is, at most one chain
exists between any two vertices in the digraph. For these networks, arcs can be removed
dynamically while evidence is being processed in contrast to a static removal of arcs as a
preprocessing phase before inference as described in the previous section. Therefore, the
computational complexity of processing evidence can be reduced depending on the evidence
itself and no estimate for a lower bound for the probability of the evidence has to be provided
in advance. A detailed description and analysis of the method is beyond the scope of this
paper. However, a practical outline of the scheme will be presented which is based on Pearl's
polytree algorithm.
First, we will show that all variables in the network retain their prior probabilities upon
removal of an arc.
Lemma 4.2 Let (G; \Gamma) be a belief network with a singly connected digraph G. Let Pr
be the joint probability distribution defined by B. Furthermore, let be an arc
in G and let B be the approximated belief network after removal of
defined in Definition 3.1. Let Pr Vr6!Vs be the joint probability distribution defined
by B Vr6!Vs . Then, Pr Vr6!Vs
Proof. Assume that the vertices of the singly connected digraph are indexed in ascending
topological order, i.e. for each pair of vertices directed path from V i to
in G we have that i ! j. The proof is by induction on the index i of variable V i .
Base case s: from Lemma 3.6 we have that Pr Vr6!Vs
For i  s, we apply the chain rule and the principle of marginalization to obtain
Pr Vr6!Vs
c  G Vr 6!Vs
c  G Vr 6!Vs
where
singly connected, all variables are mutually
independent by the d-separation criterion. Hence, we have that Pr Vr6!Vs (c G Vr 6!Vs
). By the assumption that the vertices in G are ordered in ascending
topological order, for each by the induction
hypothesis assume that for each
by applying the principle of induction, we find
Pr Vr6!Vs
c  G Vr 6!Vs
Y
c  G Vr 6!Vs
Y
consider an in a singly connected digraph. In a singly connected digraph no
other chain exists from V r to V s except for the chain constituting the arc V r Therefore,
G Vr 6!Vs
holds on the singly connected digraph G Vr6!Vs for any
subset of variables Y ' V (G). From this observation, we have that the independence relationship
between the variables V r and V s given G Vr 6!Vs (V s ) remain unchanged after evidence
is given for any subset of variables. Informally speaking, this means that after evidence is
processed in a belief network, we can compute the Kullback-Leibler information divergence
between the posterior probability distribution defined by a belief network and the posterior
distribution of the approximated network after removal of an arc locally. Then, by a similar
exposition for the properties of the Kullback-Leibler information divergence applied on general
belief networks for multiple arc removals as presented in the previous sections, it can be
shown that
for belief network consisting of a singly connected digraph, where Pr is the joint probability
distribution defined by the network and PrA is the joint probability distribution defined by
the multiple approximated network after removal of all arcs A. We note that the computation
of the divergence is as expensive
on the computational resources as the computation of the causal and diagnostic messages
for vertex V s in Pearl's polytree algorithm assuming that logarithms require one time unit.
Furthermore, in fact, by using Pearl's polytree algorithm, arcs do not have to be physically
removed, the blocking of causal and diagnostic messages for updating the probability distribution
will suffice. With this observation, we envisage an approximate wave-front version
of the polytree algorithm where the sending of messages is blocked between two connected
vertices in the graph if the probabilistic dependency relationship between the vertices is very
weak. That is, we block all messages for which the information divergence per blocked arc is
small such that the total sum of the information divergences over all blocked arcs does not
exceed some predetermined constant for the maximum absolute error allowed in probabilistic
5 Discussion and Related Work
We have presented a scheme for approximating Bayesian belief networks based on model
simplification through arc removal. In this section we will compare the proposed method
with other methods for belief network approximation.
Existing belief network approximation methods are annihilating small probabilities from
belief universes [8], and removal of weak dependencies from belief universes [13]. Both methods
have proven to be very successful in reducing the complexity of inference on a belief network
on real-life applications using the Bayesian belief universe approach [9].
The method of annihilating small probabilities by Jensen and Andersen reduces the computational
effort of probabilistic inference when the method of clique-tree propagation is used
for probabilistic inference. The basic idea of the method is to eliminate configurations with
small probabilities from belief universes, accepting a small error in the probabilities inferred
from the network. To this end, the k smallest probability configurations are selected for
each belief universe where k is chosen such that the sum of the probabilities of the selected
configurations in the universe is less than some predetermined constant ". The constant "
determines the maximum error of the approximated prior probabilities. The belief universes
are then compressed to take advantage of the zeros introduced. Jensen and Andersen further
point out that if the range of probabilities of evidence is known in advance, the method can
be applied to approximate a belief network such that the error of the approximated posterior
probabilities computed from the network are bounded by some predetermined constant.
Similar to the method of annihilating small probabilities, the method of removal of weak
dependencies by Kjaerulff reduces the computational effort of probabilistic inference when
the method of clique-tree propagation is used. Kjaerulff's approximation method and the
method of annihilation are complementary techniques [13]. The basic idea of the method is
to remove edges from the chordal graph constructed from the digraph of a belief network that
model weak dependencies. The weaker the dependencies, the smaller the error introduced in
the represented joint probability distribution approximated upon removal of an edge. The
method operates on the junction tree of a belief network only. Given a constant ", a set of
edges can be removed sequentially such that the error introduced in the prior distribution is
smaller than ". Removal of an edge results in the decomposition of the clique containing the
edge into two or more smaller cliques which results in a simplification of the junction tree
thereby reducing the computational complexity of inference on the network.
In comparing the methods for approximating belief networks, we first of all find that
the method of annihilating small probabilities from belief universes introduces an error that
is inversely proportional to the probability of the evidence [8] while the methods based on
removing arcs introduces an error that is inversely proportional to the square root of the
probability of the evidence. Furthermore, since the original joint probability distribution is
absolutely continuous with respect to the approximated probability distribution, the processing
of evidence in an approximated belief network by our method is safe in the sense that no
undefined conditional probabilities will arise for evidence with a nonzero probability in the
original distribution; the evidence that can be processed in an approximated belief network is
a superset of the evidence that can be processed in the original network. Once more, this is in
contrast to the method of annihilating small probabilities from belief universes. On the other
hand, however, the advantage of annihilating small probabilities is that the method operates
on the quantitative part of a belief network only whereas arc removal methods change the
qualitative representation as well. This can be remedied by introducing virtual arcs to replace
removed arcs. Virtual arcs are not used in probabilistic inference.
The method presented in this paper has some similarities to Kjaerulff's method of removal
of weak dependencies from belief universes [13]. Both methods aim at reducing inference on a
belief network by removing arcs or edges. However, the independency statements we enforce
are of the in contrast to V r ??V s j C n fV r by Kjaerulff's
method where C ' V (G) denotes the clique containing the edge removed by Kjaerulff's
method. Furthermore, Kjaerulff's method of removal is based on the clique-tree propagation
algorithm only and restricts the removal to one edge from a clique at a time in order that the
error introduced is bounded by some predetermined constant. In contrast, our method allows a
larger set of arcs (edges) to be removed in parallel, still guaranteeing that the introduced error
to be bounded by some predetermined constant regardless of the algorithms for probabilistic
inference used.
To summarize the conclusions, the scheme we propose for approximating belief networks
operates directly on the digraph of a belief network, has a relatively low computational com-
plexity, provides a bound on the posterior error in the presence of evidence, and is independent
of the algorithms used for probabilistic inference.

Acknowledgements

The author would like to acknowledge valuable discussions with Linda van der Gaag of Utrecht
University, The Netherlands.



--R


Index Expression Belief Networks for Information Disclosure
The Computational Complexity of Probabilistic Inference using Bayesian Belief Networks
A Tutorial to Stochastic Simulation Algorithms for Belief Networks
Approximating Probabilistic Inference in Bayesian Belief Networks is NP-hard

Propagating uncertainty in Bayesian networks by probabilistic logic sam- pling
Approximations in Bayesian Belief Universes for Knowledge-based Systems
Bayesian updating in causal probabilistic networks by local computations
Use of Causal Probabilistic Networks as High LEvel Models in Computer Vision
Journal of the Australian Mathematical Society A

Reduction of Computational Complexity in Bayesian Networks through Removal of Weak Dependencies
Information Theory and Statistics
A lower bound for discriminating information in terms of variation
Local computations with probabilities on graphical structures and their application to expert systems
Genetic Algorithms
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
Probabilistic inference in multiply connected belief networks using loop cutsets
A Combination of Exact Algorithms for Inference on Bayesian Belief Networks
On Substantive Research Hypothesis
Graphical Models in Applied Multivariate Statistics
--TR

--CTR
Helge Langseth , Olav Bangs, Parameter Learning in Object-Oriented Bayesian Networks, Annals of Mathematics and Artificial Intelligence, v.32 n.1-4, p.221-243, August 2001
Marek J. Druzdzel , Linda C. van der Gaag, Building Probabilistic Networks: 'Where Do the Numbers Come From?' Guest Editors' Introduction, IEEE Transactions on Knowledge and Data Engineering, v.12 n.4, p.481-486, July 2000
Helge Langseth , Thomas D. Nielsen, Fusion of domain knowledge with data for structural learning in object oriented domains, The Journal of Machine Learning Research, 4, 12/1/2003
Magnus Ekdahl , Timo Koski, Bounds for the Loss in Probability of Correct Classification Under Model Based Approximation, The Journal of Machine Learning Research, 7, p.2449-2480, 12/1/2006
Rina Dechter , Irina Rish, Mini-buckets: A general scheme for bounded inference, Journal of the ACM (JACM), v.50 n.2, p.107-153, March
Russell Greiner , Christian Darken , N. Iwan Santoso, Efficient reasoning, ACM Computing Surveys (CSUR), v.33 n.1, p.1-30, March 2001
belief network approximation;approximate probabilistic inference;information theory;model simplification;bayesian belief networks