Database Reference
In-Depth Information
Edge
Weight: value(probability)
e
i
x
i
1
x
i
2
x
i
3
e
1
:AB 10
(
0
.
3
)
15
(
0
.
3
)
20
(
0
.
4
)
B
D
e
2
:AC
5
(
0
.
2
)
10
(
0
.
3
)
15
(
0
.
5
)
e
3
:BD 20
(
0
.
4
)
25
(
0
.
4
)
30
(
0
.
2
)
A
e
4
:BE
5
(
0
.
2
)
25
(
0
.
6
)
40
(
0
.
2
)
e
5
:CE 10
(
0
.
5
)
20
(
0
.
1
)
45
(
0
.
4
)
C
(a) A graph.
E
)
(b) Probabilistic weights of edges.
e
6
:DE 10
(
0
.
3
)
20
(
0
.
6
)
50
(
0
.
1
20
25
30
10
20
50
10
0
.
15
0
.
15
0
20
0
.
10
.
20
.
1
15
0
.
15
0
.
15
0
25
0
.
10
.
30
20
2
(c)
f
e
1
,
e
3
(
x
1
i
,
x
3
j
)
.
0
.
10
.
10
.
30
10
(d)
f
e
3
,
e
6
(
x
3
i
,
x
6
j
)
.
0
.
10
.
Fig. 2.6
A probabilistic graph.
n
−
1
1
f
e
i
,
e
i
+
1
(
x
i
,
x
i
+
1
)
x
∏
∑
x
1
+
...
+
i
=
f
P
(
x
)=
(2.6)
n
−
1
j
=
2
f
e
j
(
x
j
)
∏
x
n
=
Proof.
Since
P
is a simple path, each edge
e
i
∈
P
(1
≤
i
≤
) is only adjacent with
e
i
−
1
(if
i
>
1) and
e
i
+
1
(if
i
<
n
)in
P
. Therefore, given
w
e
i
, the weights
w
e
1
,...,
w
e
i
−
1
are
conditionally independent on
w
e
i
+
1
,...,
w
e
n
. Equation 2.6 follows with basic proba-
bility theory.
In sequel, the
cumulative distribution function
of
w
P
is
]=
∑
0
F
P
(
x
)=
Pr
[
w
P
≤
x
f
P
(
x
i
)
(2.7)
<
x
i
≤
x
We call
F
P
(
x
)
the
x
-weight probability
of path
P
.
Example 2.13 (Probabilistic graph and paths). A probabilistic graph is shown in
Figure 2.6, where the weight of each edge is represented by a set of samples and
their membership probabilities.
Path P
=
A
,
B
,
D
,
E
consists of edges AB, BD and DE. The joint probabilities
of
(
w
AB
,
w
BD
)
and
(
w
BD
,
w
DE
)
are shown in Figures 2.6(c) and 2.6(d), respectively.
The probability that w
P
=
45
is
[
=
]
Pr
w
P
45
=
Pr
[
w
e
1
=
15
,
w
e
3
=
20
,
w
e
6
=
10
]+
Pr
[
w
e
1
=
10
,
w
e
3
=
25
,
w
e
6
=
10
]
f
e
1
,
e
3
(
15
,
20
)
×
f
e
3
,
e
6
(
20
,
10
)
f
e
1
,
e
3
(
10
,
25
)
×
f
e
3
,
e
6
(
25
,
10
)
=
+
f
e
3
(
20
)
f
e
3
(
25
)
=
0
.
075
