[Next] [Up] [Previous]
Next: Generating Q-DAGs Up: Generating Query DAGs Previous: Generating Query DAGs

The Clustering Algorithm

We provide a sketch of the clustering algorithm in this section. Readers interested in more details are referred to [Shachter, Andersen, SzolovitsShachter et al.1994, Jensen, Lauritzen, OlesenJensen et al.1990, Shenoy ShaferShenoy \ Shafer1986].

According to the clustering method, we start by:

  1. constructing a join tree of the given belief network;[+]
  2. assigning the matrix of each variable in the belief network to some cluster that contains the variable's family.
The join tree is a secondary structure on which the inference algorithm operates. We need the following notation to state this algorithm:
-
tex2html_wrap1320 are the clusters, where each cluster corresponds to a set of variables in the original belief network.

-
tex2html_wrap1321 is the potential function over cluster tex2html_wrap1322, which is a mapping from instantiations of variables in tex2html_wrap1322 into real numbers.

-
tex2html_wrap1324 is the posterior probability distribution over cluster tex2html_wrap1322, which is a mapping from instantiations of variables in tex2html_wrap1322 into real numbers.

-
tex2html_wrap1327 is the message sent from cluster tex2html_wrap1322 to cluster tex2html_wrap1329, which is a mapping from instantiations of variables in tex2html_wrap1330 into real numbers.

-
tex2html_wrap1049 is the given evidence, that is, an instantiation of evidence variables tex2html_wrap1048.

We also assume the standard multiplication and marginalization operations on potentials.

Our goal now is to compute the potential tex2html_wrap1333 which maps each instantiation tex2html_wrap1334 of variable tex2html_wrap1335 in the belief network into the probability tex2html_wrap1336. Given this notation, we can state the algorithm as follows:

These equations are used as follows. To compute the probability of a variable, we must compute the posterior distribution of a cluster containing the variable. To compute the posterior distribution of a cluster, we collect messages from neighboring clusters. A message from cluster tex2html_wrap1322 to tex2html_wrap1329 is computed by collecting messages from all clusters adjacent to tex2html_wrap1322 except for tex2html_wrap1329.

This statement of the join tree algorithm is appropriate for situations where the evidence is not changing frequently since it involves computing initial potentials each time the evidence changes. This is not necessary in general and one can provide more optimized versions of the algorithm. This issue, however, is irrelevant in the context of generating Q-DAGs because updating probabilities in face of evidence changes will take place at the Q-DAG level, which includes its own optimization technique that we discuss later.


[Next] [Up] [Previous]
Next: Generating Q-DAGs Up: Generating Query DAGs Previous: Generating Query DAGs

Darwiche&Provan