Korb K.B., Nicholson A.E. Bayesian Artificial Intelligence

Подождите немного. Документ загружается.

PROPAGATION, EVIDENCE for node M

PROPAGATION, NO EVIDENCE

PHASE 1

PHASE 2

PHASE 2 PHASE 3

PHASE 1

FIGURE 3.4

Message passing algorithm propagation stages for without evidence (above) and with

evidence for node

(below).

marginals (i.e., when computing

). The normalization constants, ,arethe

same for all the marginals, being the inverse of the probability P(E), the computation

of which is often useful for other purposes.

3.4 Inference with uncertain evidence

Thus far we have assumed that any evidence is a direct observation of the value of

a variable that will result in the belief for a node being set to 1 for that value and

0 for all other values. This is the speciﬁc evidence described in

2.3.2, which is

entered in the message passing algorithm as a vector with a 1 in the position of the

evidence value and 0 in the other positions. Once speciﬁc evidence is entered for a

node, the belief for that node is “clamped” and doesn’t change no matter what further

information becomes available.

However, the inference algorithms should also be able to handle evidence that has

uncertainty associated with it. In our earthquake example, suppose that after you

get a call from your neighbor Mary saying she has heard your alarm going off, a

colleague who is in your ofﬁce at the time says he thinks he heard earlier on the

radio that there was a minor earthquake in your area, but he is only 80% sure.

We introduced this notion very brieﬂy in

2.3.2, where we mentioned that this sort

of evidence is called “virtual” evidence or “likelihood” evidence. We deferred further

explanation of these terms until here, as they relate to how inference is performed.

Some of the major BN software packages (e.g., Netica and Hugin) provide the

facility for adding likelihood evidence, as well as speciﬁc and negative evidence.

In fact, we describe how to enter likelihood evidence in both Netica and Hugin in

Figure 3.15. In our opinion, the explanations of this sort of evidence in both the

literature and available software documentation are confusing and incomplete. It is

important for people using this feature in the software to understand how likelihood

evidence affects the inference and also how to work out the numbers to enter.

First, there is the issue of how to interpret uncertainty about an observation. The

uncertain information could be represented by adopting it as the new distribution over

the variable in question. This would mean for the earthquake node somehow setting

. However, we certainly do not want to “clamp”

this belief, since this probabilistic judgement should be integrated with any further

independent information relevant to the presence of an earthquake (e.g., the evidence

about Mary calling).

3.4.1 Using a virtual node

Let’s look at incorporating an uncertain observation for the simplest case, a single

Boolean node X, with a uniform prior, that is P(X=T)=P(X=F)=0.5. We add a virtual

node

, which takes values , as a child of X, as shown in Figure 3.5. The

uncertainty in the observation of

is represented by the CPT; for an 80% sure

observation this gives

and .

Now speciﬁc evidence is entered that

. We can use Bayes’ Theorem to

perform the inference, as follows.

Since , this gives us = 2, and hence

and , as desired.

It is important to note here that due to the normalization, it is not the likelihoods

for and that determine the new belief, but

rather the ratio:

For example, we would get the same answers for or

Note that takes these values irrespective of the values of the observed node.

Note that the semantics of this CPT are not well speciﬁed. For example, what is the meaning of the CPT

entries for

CPT:

P(V=T|X=T) = 0.8

P(V=T|X=F) = 0.2

virtual node

0.5

P(X=T)

FIGURE 3.5

Virtual evidence handled through virtual node

for single node , with uncertainty

in CPT.

So far, we have seen that with the use of a “virtual” node we can represent uncer-

tainty in an observation by a likelihood ratio. For example, my colleague attributing

80% credibility to there having been an earthquake means that he is four times more

likely to think an earthquake occurred if that was in fact the case than he is of mis-

takenly thinking it occurred.

But we have considered only the situation of a node without parents, with uniform

priors. If the priors are not uniform, then simply mapping the uncertainty into a

likelihood ratio as described does not give a new belief that correctly represents

the speciﬁed observational uncertainty. For example, in our earthquake example, if

,then

which gives ,and and so the

posterior belief in Earthquake is only 7.5%. However, if

,then

which gives us and .

It is clear that directly mapping the observational uncertainty into a likelihood ratio

only results in the identical belief for the node in question (as intended in Jeffrey

conditionalization) when the priors are uniform. When the priors are non-uniform,

a likelihood ratio of 4:1 will increase the belief, but not necessarily to the intended

degree.

Some people feel this is an advantage of this representation, supposedly indicat-

ing that the observation is an external “opinion” from someone whose priors are

unknown. However, if we wish to represent unknown priors, we have no business

inferring a posterior at all!

If we really want the uncertain evidence to shift the beliefs

, then we can still use a virtual node and likelihood ratio ap-

proach, but we need to compute the ratio properly. Let’s return to our earthquake

example. Recalling Deﬁnition 1.6,

means .Since

(by odds-likelihood Bayes’ theorem 1.5)

and, as given in the example,

we get the likelihood ratio

This ratio is much higher than the one used with uniform priors, which is neces-

sary in order to shift the belief in Earthquake from its very low prior of 0.02 to 0.8.

3.4.2 Virtual nodes in the message passing algorithm

When implementing a message passing inference algorithm, we don’t actually need

to add the

node. Instead, the virtual node is connected by a virtual link as a child

to the node it is “observing.” In the message passing algorithm, these links only

carry information one way, from the virtual node to the observed variable. For our

earthquake example, the virtual node

represents the virtual evidence on .There

are no parameters

, but instead it sends a message to . The virtual

node and the message it sends to

is shown in Figure 3.6.

(J) = (1,1)l

(E)=(4,1)

(M) = (1,0)l

virtual node

FIGURE 3.6

Virtual evidence handled through virtual node

for earthquake node , with

message in message passing algorithm.

3.5 Exact inference in multiply-connected networks

In the most general case, the BN structure is a (directed acyclic) graph, rather than

simply a tree. This means that at least two nodes are connected by more than one

path in the underlying undirected graph. Such a network is multiply-connected

and occurs when some variable can inﬂuence another through more than one causal

mechanism.

The metastatic cancer network shown in Figure 3.7 is an example. The two causes

( and ) share a common parent, . For this BN, there is an undirected loop

around nodes

, , and . In such networks, the message passing algorithm for

polytrees presented in the previous section does not work. Intuitively, the reason is

that with more than one path between two nodes, the same piece of evidence about

one will reach the other through two paths and be counted twice. There are many

ways of dealing with this problem in an exact manner; we shall present the most

popular of these.

3.5.1 Clustering methods

Clustering inference algorithms transform the BN into a probabilistically equiva-

lent polytree by merging nodes, removing the multiple paths between the two nodes

along which evidence may travel. In the cancer example, this transformation can

be done by creating a new node, say

, that combines nodes and ,asshownin

Figure 3.8. The new node has four possible values,

TT,TF,FT,FF , corresponding

to all possible instantiations of

and . The CPTs for the transformed network are

also shown in Figure 3.8. They are computed from the CPTs of the original graph as

0.05

0.20

P(S=T|M)

0.20

0.80

P(B=T|M)

0.60

0.80

P(H=T|B)

0.80

0.05

P(M=T)

0.9

F F

T F

T T

S B P(C=T|S,B)

F T

FIGURE 3.7

Example of a multiply-connected network: metastatic cancer BN (

2.5.2).

follows.

by deﬁnition of Z

since S and B are independent given M

Similarly,

since H is independent of S given B

by deﬁnition of Z

It is always possible to transform a multiply-connected network into a polytree.

In the extreme case, all the non-leaf nodes can be merged into a single compound

node, as shown in Figure 3.9(a) where all the nodes

are merged into a single

super-node. The result is a simple tree. But other transformations are also possible,

as shown in Figure 3.9(b) and (c), where two different polytrees are produced by

different clusterings. It is better to have smaller clusters, since the CPT size for the

cluster grows exponentially in the number of nodes merged into it. However the

more highly connected the original network, the larger the clusters required.

Exact clustering algorithms perform inference in two stages.

1. Transform the network into a polytree

2. Perform belief updating on that polytree

The transformation in Step 1 may be slow, since a large number of new CPT values

may need to be computed. It may also require too much memory if the original

network is highly connected. However, the transformation only needs to be done

once, unless the structure or the parameters of the original network are changed.

0.16

0.64

0.16

P(Z|M)

P(C=T|Z)

0.8

0.6

0.05

P(H=T|Z)

0.8

0.6

Z=S,B

P(M=T)

0.9

FIGURE 3.8

Result of ad hoc clustering of the metastatic cancer BN.

The belief updating in the new polytree is usually quite fast, as an efﬁcient polytree

message passing algorithm may now be applied. The caveat does need to be added,

however, that since clustered nodes have increased complexity, this can slow down

updating as well.

3.5.2 Junction trees

The clustering we’ve seen thus far has been ad hoc. The junction tree algorithm

provides a methodical and efﬁcient method of clustering, versions of which are im-

plemented in the main BN software packages (see

B.4).

ALGORITHM 3.2

The Junction Tree Clustering Algorithm

1. Moralize: Connect all parents and remove arrows; this produces a so-called

moral graph.

2. Triangulate: Add arcs so that every cycle of length

3 has a chord (i.e., so

there is a subcycle composed of exactly three of its nodes); this produces a

triangulated graph.

3. Create new structure: Identify maximal cliques in the triangulated graph to

become new compound nodes, then connect to form the so-called junction

tree.

4. Create separators: Each arc on the junction tree has an attached separator,

which consists of the intersection of adjacent nodes.

Original BN

(c)

(b)

Alternative Polytrees

(a) Extreme Cluster − all non−leaf nodes merged

M1 M2 M3 M4M1M1 M2 M3 M4M1M1 M2 M3 M4M1M1 M2 M3 M4M1

M3,M4

M1,M2,M3

D2,D3.D4

D1,D2

M1,M2

D2,D3

D1,D2,D3,D4

FIGURE 3.9

The original multiply-connected BN can be clustered into: (a) a tree; different poly-

trees (b) and (c).

5. Compute new parameters: Each node and separator in the junction tree has

an associated table over the conﬁgurations of its constituent variables. These

are all a table of ones to start with.

For each node

in the original network,

(a) Choose one node

in the junction tree that contains and all of ’s

parents,

(b) Multiply

on ’s table.

6. Belief updating: Evidence is added and propagated using a message passing

algorithm.

The moralizing step (Step 1) is so called because an arc is added if there is no

direct connection between two nodes with a common child; it is “marrying” the

parent nodes. For our metastatic cancer example,

and have as a common

child; however, there is no direct connection between them, so this must be added.

The resultant moral graph is shown in Figure 3.10(a).

As we have seen, the size of the CPT for a new compound node is the product

of the number of states of the combined nodes, so the size of the CPT increases

exponentially with the size of the compound node. Different triangulations (Step 2)

produce different clusters. Although the problem of ﬁnding an optimal triangulation

is NP complete, there are heuristics which give good results in practice. No arcs need

to be added to the moral graph for the metastatic cancer example, as it is already

triangulated.

(a) (b)

(a)

S1=S,B S2=B

Z1=M,S,B

Z2=S,B,C

Z3=B,H

FIGURE 3.10

Applying the junction tree algorithm to the metastatic cancer BN gives (a) the moral

graph and (b) the junction tree.

A clique of an undirected graph is deﬁned as a set of nodes that are all pairwise

linked; that is, for every pair of nodes in the set, there is an arc between them. A

maximal clique is such a subgraph that cannot be increased by adding any node.

In our example the maximal cliques can be read from the moral graph, giving three

new compound nodes,

, and (Step 3). The

junction tree, including the separators (Step 4), is shown in Figure 3.10(b).

Note that sometimes after the compound nodes have been constructed and con-

nected, a junction graph results, instead of a junction tree. However, because of the

triangulation step, it is always possible to remove links that aren’t required in order to

form a tree. These links aren’t required because the same information can be passed

along another path; see [129] for details.

The metastatic cancer network we’ve been using as an example is not sufﬁciently

complex to illustrate all the steps in the junction tree algorithm. Figure 3.11 shows

the transformation of a more complex network into a junction tree (from [129]).

Finally, Step 5 computes the new CPTs for the junction tree compound nodes.

The result of Step 5 is that the product of all the node CPTs in the cluster tree is

the product of all the CPTs in the original BN. Any cluster tree obtained using this

algorithm is a representation of the same joint distribution, which is the product of

all the cluster tables divided by the product of all the separator tables.

Adding evidence to the junction tree is simple. Suppose that there is evidence

about node . If it is speciﬁc evidence that , then we create an evidence

vector with a 1 in the

th position, zeros in all the others. If it is a negative ﬁnding

for state

,thereisazerointhe th position and ones in all the others. If it is virtual

evidence, the vector is constructed as in

3.4. In all cases, the evidence vector is

multiplied on the table of any node in the junction tree containing

Once the junction tree has been constructed (called “compilation”inmostBN

software, including Netica) and evidence entered, belief updating is performed using

a message passing approach. The details can be found in [128]. The basic idea is that

separators are used to receive and pass on messages, and the computations involve

computing products of CPTs.

The cost of belief updating using this junction tree approach is primarily deter-

(d) (e)

(a) (b) (c)

EFG

BCDF

ABCD

BCD

BEF DFG

EFH

FGI

BCD

ABCD

BCDF

BEF

DFG

EFH

FGI

DFBF

FIGURE 3.11

Example of junction tree algorithm application: (a) the original multiply-connected

BN; (b) the moral graph; (c) the triangulated graph; (d) the junction graph; and (e)

the junction tree. (From Jensen, F.V. An Introduction to Bayesian Networks.UCL

Press, London, 1996. With permission.)

mined by the sizes of the state space of the compound nodes in the junction tree. It

is possible to estimate the computational cost of performing belief updating through

the junction tree cost [139, 70]. Suppose the network has been transformed into a

junction tree with new compound nodes

, The junction tree cost

is deﬁned as:

(3.6)

where

is the number of separation sets involving clique , i.e., the total number of

parents and children of

in the junction tree. So the junction-tree cost is the product

of the size of all the constituent nodes in the cluster and the number of children and

parents, summed over all the compound nodes in the junction tree. The junction tree