Database Reference
In-Depth Information
bilities are different. From the probability of each linkage and the mutual exclu-
sion rules, we can compute the marginal distributions f
(
l
1
,
l
2
)
,f
(
l
3
,
l
4
)
,f
(
l
1
,
l
3
)
and f
(
l
2
,
l
4
)
, respectively. The three marginal distributions f
(
l
1
,
l
2
)
,f
(
l
3
,
l
4
)
and
f
(
l
2
,
l
4
)
can uniquely determine a joint distribution f
(
l
1
,
l
2
,
l
3
,
l
4
)
. Due to the mu-
tual exclusion rule l
1
l
3
, the probability that l
1
and l
3
both appear should be
0
.
However, from this joint distribution, we can derive
⊕
1
15
.
Pr
(
l
1
,
l
3
)=
Pr
(
l
1
,¬
l
2
,
l
3
,¬
l
4
)=
Pr
(
l
1
,¬
l
2
)
Pr
(
¬
l
4
|¬
l
2
)
Pr
(
l
3
|¬
l
4
)=
Thus, the joint probability f
(
l
1
,
l
2
,
l
3
,
l
4
)
computed from the marginal distributions
f
(
l
1
,
l
2
)
,f
(
l
3
,
l
4
)
and f
(
l
1
,
l
3
)
is inconsistent with the marginal distribution f
(
l
1
,
l
3
)
.
Therefore, the linkages in Figure 7.1(c) are not compatible.
Definition 7.1 (Compatible linkages).
A set of linkages are
compatible
if there is
at least a joint distribution on the linkages that satisfies the marginal distributions
specified by the linkages.
Example 7.1 indicates that some linkages may lead to a situation where the pos-
sible worlds cannot be decided (i.e., the linkages are not compatible). In the rest of
this section, we will discuss three problems.
1. In what situations are the linkages compatible?
2. How to fix incompatible linkages to compatible ones with small information
loss?
3. How to compute the probabilities of possible worlds for compatible linkages?
7.2.2 Probabilistic Mutual Exclusion Graphs
Dependencies among linkages are important in deriving possible world probabili-
ties. We develop a probabilistic graphic model to capture such dependencies.
Definition 7.2 (PME-graph).
Given a set of probabilistic linkages
L
A
,
B
,a
prob-
abilistic mutual exclusion graph (PME-graph)
G
L ,
A
,
B
=(
V
,
E
)
is an undirected
graph such that (1) a vertex
v
l
∈
V
(
l
∈ L
A
,
B
)
is a binary random variable corre-
sponding to a probabilistic linkage,
Pr
(
v
l
=
1
)=
Pr
(
l
)
and
Pr
(
v
l
=
0
)=
1
−
Pr
(
l
)
;
V
) if linkages
l
and
l
share a common tuple,
i.e., they are involved in a mutual exclusion rule
R
t
(
t
(2) an edge
e
=(
v
l
,
v
l
)
∈
E
(
v
l
,
v
l
∈
∈
A
or
t
∈
B
).
A PME-graph may contain multiple connected components. The vertices in one
connected component are correlated. The vertices in a PME-graph
G
L ,
A
,
B
=(
V
,
E
)
have several basic properties.
Corollary 7.1 (Vertices in a PME-graph).
For a PME-graph G
=(
V
,
E
)
, two ver-
tices v
i
,
v
j
∈
V has the following properties:
1. v
i
,
v
j
∈
V are independent if v
i
and v
j
belong to different connected components.
