Database Reference
In-Depth Information
C
1
C
1
C
1
v
1
v
1
v
1
v
v
v
v
v
v
3
2
3
2
3
2
C
2
C
2
C
2
v
4
v
4
v
4
v
5
v
v
5
v
v
5
v
6
6
6
v
7
v
7
v
7
C
3
C
3
C
3
(c) Step 3.
(a) Step 1.
(b) Step 2.
Fig. 7.4
Computing the probability for possible world
W
=
{
v
1
,
v
4
,
v
7
}
. Black and grey vertices
are assigned values 1 and 0, respectively. White vertices have not been assigned any value yet.
L
A
,
B
can be regarded as an assignment of
values 0 and 1 to the vertices in the PME-graph
G
L ,
A
,
B
, where a vertex
v
l
=
A possible world
W
of linkages
1
if the corresponding linkage
l
∈
W
, otherwise
v
l
=
0. For a clique
C
in
G
L ,
A
,
B
,
if
∑
v
∈
C
Pr
(
v
=
1
)
<
1, then at most one vertex in
C
can be assigned to 1; if
∑
v
∈
C
Pr
1, then there is exactly one vertex in
C
taking value 1. The prob-
ability of a possible world
W
is the joint distribution
(
v
=
1
)=
(
)=
((
∧
l
∈
W
v
l
=
)
∧
(
∧
l
∈
W
v
l
=
))
.
Pr
W
Pr
1
0
(7.4)
Since vertices in different connected components in
G
L ,
A
,
B
are independent
(Section 7.2.2), if
G
L ,
A
,
B
=(
V
,
E
)
contains
k
connected components
V
=
V
1
∪
V
2
∪
···
V
k
, Equation 7.4 can be rewritten as
i
=
1
Pr
((
k
Pr
(
W
)=
v
l
=
1
)
(
v
l
=
0
))
(7.5)
l
∈
l
∈
l
∈
W
∩
V
i
W
,
V
i
The remaining question is how to generate the possible worlds in one connected
component.
Example 7.2 (Factoring joint probability). Consider the set of linkages in Fig-
ure 7.2(a) and the corresponding PME-graph in Figure 7.2(b). Figure 7.4 shows
how we generate a possible world using the PME-graph.
We consider cliques C
1
,
C
3
in the PME-graph one by one. In the first step,
since no value has been assigned in clique C
1
, all three vertices in C
1
may have
a chance to be set to
1
. The probability of v
1
taking value
1
is Pr
C
2
,
(
v
1
=
1
)=
0
.
6
.
Suppose we set v
1
=
1
. Then, v
2
and v
3
can only take value
0
(Figure 7.4(a)).
After clique C
1
is set, we consider clique C
2
. Since v
3
=
0
, only v
4
and v
5
can take
value
1
. Moreover, given condition v
3
=
0
, the probabilities of v
4
=
1
and v
5
=
1
,
Pr
(
v
4
=
1
)
Pr
respectively, are Pr
(
v
4
=
1
|
v
3
=
0
)=
)
=
0
.
5
and Pr
(
v
5
=
1
|
v
3
=
0
)=
0
.
5
.
(
v
3
=
0
Suppose we set v
4
=
1
. Then, v
5
=
0
(Figure 7.4(b)).
