Biology Reference
In-Depth Information
Algorithm 4.1
Junction Tree Clustering Algorithm
1.
Moralize:
create the moral graph of the Bayesian network
B
as illustrated in
Sect.
2.1.4
.
2.
Triangulate:
break every cycle spanning 4 or more nodes into subcycles of ex-
actly 3 nodes by adding arcs to the moral graph, thus obtaining a
triangulated
graph
.
3.
Cliques:
identify the
cliques
of the triangulated graph, i.e., maximal subsets of
nodes in which each element is adjacent to all the others.
4.
Junction Tree:
create a tree in which each clique is a node, and adjacent cliques
are linked by arcs.
5.
Reparameterize:
use the parameters of the local distributions of
B
to compute
the parameter sets of the compound nodes of the junction tree.
For instance, the marginalization in Eq.
4.4
can be rewritten as
P
P
(
Q
|
E
,
G
,
Θ
)=
(
X
|
E
,
G
,
Θ
)
d
(
X
\
Q
)=
p
i
=
1
P
(
X
i
|
E
,
Π
X
i
,
Θ
X
i
)
d
P
)=
∏
i
:
X
i
∈
=
(
X
\
Q
(
X
i
|
E
,
Π
X
i
,
Θ
X
i
)
dX
i
.
(4.8)
Q
The correspondence between d-separation and conditional independence can also
be used to further reduce the dimension of the problem. From Definition
2.2
,vari-
ables that are d-separated from
Q
by
E
cannot influence the outcome of the query.
Therefore, they may be completely disregarded in computing the posterior proba-
bilities.
Exact inference algorithms combine repeated applications of Bayes' theorem
with local computations to obtain exact values P
.
However, their feasibility is restricted to small or very simple networks such as
trees and polytrees.
The two best-known exact inference algorithms are
variable elimination
and be-
lief updates based on
junction trees
. Both were originally derived for discrete net-
works and have been later extended to the continuous and mixed networks. Variable
elimination uses the structure of the Bayesian network directly, specifying the opti-
mal sequence of operations on the local distributions and how to cache intermediate
results to avoid unnecessary computations. On the other hand, belief updates can
also be performed by transforming the Bayesian network into a junction tree first.
As illustrated in Algorithm
4.1
, a junction tree is a transformation of the moral
graph of
B
in which the original nodes are clustered to reduce any network structure
into a tree. Subsequently, belief updates can be performed efficiently using Kim and
Pearl's Message-Passing algorithm. The derivation and the details of the major steps
(
Q
|
E
,
G
,
Θ
)
or
f
(
Q
|
E
,
G
,
Θ
)
Search WWH ::
Custom Search