Network Construction

***

I

I

Pruning Bayesian Networks for Efficient Computation

I Michelle Baker and Terrance E. Boult

Department of Computer Science

I Columbia University

New York, NY 10027

*****@**.********.***, ******@**.********.***

I

I 2 Introduction

1 Abstract

The computation of conditional probabilities

This paper analyzes the circumstances under

for arbitrary discrete probability distributions

which Bayesian networks can be pruned in or

I is very efficient in singly connected Bayesian

der to reduce computational complexity with

networks. However, in the general case the

out altering the computation for variables of

problem is NP-Complete [Cooper 89]. This

interest. Given a problem instance which con

I paper examines how the specific query one is

sists of a query .and evidence for a set of nones

interested in and the evidence available can be

in the network, it is possible to deiete portions

taken advantage of in order to reduce com

of the network which do not participate in the

I putational complexity. If one is interested in

computation for the query. Savings in com

determining values for a subset of the vari

putational complexity can be large when the

ables in a problem domain it is not necessary

original network is not singly connected.

I to propagate information along every path in

Results analogous to those described in this the network. Thus the network can be pruned

paper have been derived before [Geiger, prior to carrying out the computation. Very

I Verma, and Pearl 89, Shachter 88] but the im large savings in computational complexity are

plications for reducing complexity of the com possible when a multiply connected network

putations in Bayesian networks have not been can be reduced to a singly connected sub

I stated explicitly. We show how a preprocess graph.

ing step can be used to prune a Bayesian net

One of the implications of this paper is that it

work prior to using standard algorithms to

I is not necessary that evidence be available in

solve a given problem instance. We also

order for a Bayesian network to be pruned.

show how our results can be used in a parallel

Probably the simplest example in which enor

distributed implementation in order to achieve

I greater savings. We define a minimal com mous savings in computation are possible is

putationally equivalent subgraph of a the case in which you are only interested in

Bayesian network. The algorithm developed knowing the value of a root (i.e., parentless)

I in [Geiger, Verma, and Pearl 89] is modified node of a network and there is no evidence

to construct the subgraphs described in this available. In this case, the network can be

pruned until only the single node that you are

paper with O (e) complexity, where e is the

I number of edges in the Bayesian network. interested in remains. The example seems

Finally, we define a minimal computationally trivial because, when there is no evidence, we

equivalent subgraph and prove that the sub need to determine the prior probability of the

I graphs described are minimal. nodes we are interested in and root nodes have

their priors directly available. Nevertheless,

I

I

258

I

I

Shachter' s methods to Bayesian networks.

techniques for pruning Bayesian networks that

Indeed, this has not been done in an im

are based only on probabilistic independencies

plemented system. Alternatively, theoretical

among variables would return the entire net

I

work in [Geiger, Verma, and Pearl 89] that

work when given this example.

analyzes the distinction between "sensitivity

The runtime construction of subgraphs of to parameter values" and sensitivity to vari

Bayesian networks in order to reduce com

I

able instantiations" imply results described in

putational complexity has only recently be this paper. However, because that work did

come a focus of research. [Wellman not address the question of efficient computa

88] developed methods for constructing

I

tion and treated the two types of independence

qualitative Bayesian networks at various as separate issues with separate algorithms its

levels of abstraction. Another technique, full implications for the dynamic construction

more closely related to the work described in

I

of Bayesian networks were hidden.

this paper, has used evidence to guide

In the rest of this paper we will define for

dynamic network construction. In his work on

mally what is meant by a computationally

combining first order logic with probabilistic

I

inference, [Breese 89] designed an algorithm equivalent subgraph, prove that recursive

pruning of leaf nodes without evidence does

for dynamic network construction that is

not violate computational equivalence and

based on evidence induced probabilistic in

I

show how the algorithm developed by

dependence. Using the semantics of

[Geiger, Verma, and Pearl 89] can be used to

d-separation he proves the algorithm correct

construct subgraphs described in this paper.

I

in the sense that subgraphs generated do not

Finally, we define formally what is meant by a

introduce unwarranted assumptions of

probabilistic independence. minimal computationally equivalent subgraph

and prove that the subgraphs described here

I

The main contribution of this paper is to show are minimal. In the conclusion we discuss

that as part of the dynamic construction of a how our results apply additional savings in a

subgraph of a Bayesian network, leaf nodes parallel distributed implementation and dis

I

without evidence can be recursively removed cuss limitations of the method.

without altering the computation at nodes of

interest. Following [Shachter 88], we will call

I

3 Computational equivalence v.s.

these barren nodes. As was illustrated in the

d-separation

previous example, barren nodes need not be d

The specific problem addressed in this paper

separated from the nodes of interest in order to

I

be removed. Although similar results have is that of finding the smallest subgraph of a

Bayesian network that will correctly compute

been stated before [Geiger, Verma, and Pearl

89, Shachter 8 8], their implications for the the conditional probability distributions for a

I

runtime construction of subgraphs of Bayesian subset of the variables in the network. Given

a Bayesian network and a problem instance

networks has not been clear. The results of

the analysis in [Shachter 88] of the infor which consists of evidence for a set of vari

I

mational requirements for solution of a ables and another set of variables whose

problem instance using an influence diagram values we wish to know, we would like to find

is equivalent to the results described here for the smallest subgraph (or set of subgraphs) of

I

Bayesian networks. However, because the the network such that the computation for

solution algorithm for influence diagrams is each of the variables of interest is unchanged.

bound up with the graph reduction it is not im

I

mediately obvious how one would apply

recursive pruning of leaf nodes

d-separation based pruning

I

Figure 1: Two computationally equivalent subgraphs for a problem instance

I A natural approach to take in solving this node, including the computation for

problem is to prune away nodes that cor- BEL(q), A.(q), and 1t(q) is identical in the

I respond to variables that are probabilistically subgraph to the computation at that node in

independent of the variables of interest. the original network.

Probabilistic independencies are represented

I Figure 1 illustrates two examples of computa

graphically in Bayesian networks according to

tionally equivalent subgraphs. Nodes labeled q

a semantics defined by d-separation [Pearl

are in Q, i.e., they represent the variables

88]. Evidence for variables that are known

I whose values we are interested in knowing.

with certainty define a set that d-separates

Nodes labeled k are evidence, i.e., they

other pairs of sets of variables. Using d

represent variables which have known values.

separation for pruning amounts to finding the

I The subgraph on the left is constructed by an

set of variables d-separated from the nodes of

algorithm based entirely on d-separation. The

interest by the evidence. An algorithm that is

one on the right is constructed by removing

linear in the number of edges in the under

I barren nodes as well by removing all the

as

lying network has been designed to solve this

nodes that are d-separated from the query

problem [Geiger, Verma, and Pearl 8 9].

nodes by the evidence.

However, whereas an algorithm based on d

I separation is sufficient to guarantee computa

The following theorem provides the basis for

tional equivalence, there are cases in which

the claim that barren nodes can be removed

nodes that are not d-separated from the nodes

I

from a Bayesian network without affecting the

of interest can be removed without jeopardiz

computation for a selected subset of nodes.

ing computational equivalence. In particular,

Furthermore, as one would expect, all nodes

barren nodes can be removed until either a

I that are d-separated by the evidence set from

node with evidence or a node of interest is en

the nodes of interest can be removed. The sub

countered.

graph that is constructed by this method may

I not be connected but there will be at most one

DEFINITION: Let Q be a subset of the nodes

graph for each node in Q.

in a Bayesian network. A subgraph of a

computationally

Bayesian network is

I

Theorem 2.1: Let Q denote the set of nodes

equivalent t o the network with respect to Q if,

whose values we are interested in and.K be

for each node q e Q, the computation at that

I

I

260

I

I

the set nodes with known values. A subgraph,

G, o f a Bayesian network, D, is computation

ally equivalent to D with respect to a problem

I

instance, (Q, K), if it is constructed by (1)

removing all nodes that are d-separated from

Q by K, (2) removing barren nodes until ei

I

ther a node in Q or a node inK is found, and

(3) removing all edges that are not incident on

two nodes in G.

I

Proof:

1. From the definition of d-separation we

I

know that if two sets of nodes, Q and Z are

d-separated from one another by a third set of

nodes, K, then P(qlz,k)=P(qlk). Thus if the

Figure 2: Propagation from the leaves

value of each node in K is known with cer

I

tainty, a node in Z cannot affect the computa

1tx

tion for any node in Q.l This fact can be Each is a vector with an entry for each

value of uk: The product, Ilk;ti 1tx(uk),

verified by an analysis of Pearl's equations for

I

computation in a singly connected network. generates a matrix with a term for each com

bination of values for the parents, uk:k i. To

2. The fact that a childless node for which no

see more easily what is going on, it is con

I

evidence is available does not affect the com

venient to order these terms from 1 to n and

putation at any other node can be seen by ex

create a vector in which the 1-th entry, 1tj, is a

amining Pearl's equations [Pearl 88] (pp

1t(ukp),

scalar equal to, 7t(u1m )7t(u2q )

177-181) and the flow of information in the

I

where m represents one of the values of u1, q

network. Figure 2 shows the information flow

represents one of the values of etc.

from a leaf, x. Information from x that will

eventually propagate to other nodes in the net Similarly, P (xl u, u; ) can be laid out in two

I

work, is sent to x's immediate parents via a A dimensions which correspond to x and the

parameter. Ax

J not blocked but which have no descendents in

1

either Q or K. 2 Either method preserves the

Thus, regardless of the information received

I from its parents, x, sends Ax

Contact this candidate