Biology Reference
In-Depth Information
Since at time
t
=
0 the process is in the beginning state
B
with probability 1,
b
0
(
0
)
=
P
(
x
1
x
2
···
x
l
|
π
0
=
B
)
=
P
(
x
1
x
2
···
x
l
)
=
P
(
x
)
. This shows that the prob-
ability
P
(
x
)
can also be computed from the backward algorithm as
b
0
(
0
)
=
P
(
x
)
=
k
∈
Q
a
0
k
e
k
(
. If this probability is already computed from the forward algo-
rithm, the backward algorithm will terminate once
b
k
(
x
1
)
b
k
(
1
)
1
)
are computed for all
k
∈
Q
.
The complete algorithm is:
Initialization
(
t
=
l
)
:
b
k
(
l
)
=
1
,
k
∈
Q
.
)
=
k
∈
Q
a
jk
e
k
(
Recursion (repeat for
t
=
l
−
1
,
l
−
2
,...,
1
)
:
b
j
(
t
x
t
+
1
)
b
k
(
t
+
1
).
)
=
k
∈
Q
a
0
k
e
k
(
Termination:
P
(
x
x
1
)
b
k
(
1
)
.
Combining nowEqs. (
9.3
) and (
9.5
), we obtain the following equation for the posterior
probabilities
P
(
x
,π
t
=
k
)
f
k
(
t
)
b
k
(
t
)
P
(π
t
=
k
|
x
)
=
=
,
k
∈
Q
,
t
=
1
,
2
,...,
l
.
(9.6)
P
(
x
)
P
(
x
)
Since we use both the forward and the backward algorithms, we say that the posterior
probabilities are computed by the
forward-backward
algorithm.
Example 9.8.
Consider again the HMM from Example
9.5
.Usetheforward-
backward algorithm to compute the posterior probabilities of
the sequence
x
LWW
.
Solution:
P
=
(
x
)
and the probabilities
f
k
(
t
)
were computed in Example
9.7
.Wenow
compute
b
k
(
t
)
for
t
=
3
,
2
,
1.
t
=
3
:
b
F
(
3
)
=
1
;
b
U
(
3
)
=
1
.
t
=
2
:
b
F
(
2
)
=
a
FF
e
F
(
W
)
b
F
(
3
)
+
a
FU
e
U
(
W
)
b
U
(
3
)
=
(
0
.
7
)
∗
(
0
.
67
)
+
(
0
.
3
)
∗
(
0
.
4
)
=
0
.
589
,
b
U
(
2
)
=
a
UF
e
F
(
W
)
b
F
(
3
)
+
a
UU
e
U
(
W
)
b
U
(
3
)
=
(
0
.
4
)
∗
(
0
.
67
)
+
(
0
.
6
)
∗
(
0
.
4
)
=
0
.
508
.
t
=
1
:
b
F
(
1
)
=
a
FF
e
F
(
W
)
b
F
(
2
)
+
a
FU
e
U
(
W
)
b
U
(
2
)
=
0
.
3372
,
b
U
(
1
)
=
a
UF
e
F
(
W
)
b
F
(
2
)
+
a
UU
e
U
(
W
)
b
U
(
2
)
=
0
.
2798
.
The posterior probabilities are now:
f
F
(
1
)
b
F
(
1
)
=
(
0
.
165
)
∗
(
0
.
3372
)
P
(π
1
=
F
|
x
)
=
=
0
.
3986
,
P
(
x
)
0
.
1396
f
U
(
1
)
b
U
(
1
)
=
(
0
.
3
)
∗
(
0
.
2798
)
P
(π
1
=
U
|
x
)
=
=
0
.
6014
.
P
(
x
)
0
.
1396
The process continues similarly until all posterior probabilities are determined (see
Exercise
9.10
).
Exercise 9.10.
Complete the previous example to calculate
P
(π
2
=
F
|
x
),
P
(π
2
=
U
|
x
),
P
(π
3
=
F
|
x
)
, and
P
(π
3
=
U
|
x
)
.
Search WWH ::
Custom Search