Biology Reference
In-Depth Information
The rationale is straightforward. For the process to be in state k at time t
+
1 with
emitted sequence x 1 x 2 ···
x t + 1 , it must be in one of the states j
∈
Q at time t with
emitted sequence x 1 x 2 ···
x t (with probability f j (
t
))
, then transition to state k at time
t
+
1 (with probability a jk )
and emit x t + 1 (with probability e k (
x t + 1 ))
. The probability
is then the sum of the product of those probabilities over all states j .
At time t = 0, the process is in the beginning state with probability 1 and has emitted
no output sequence yet. Thus, we initialize the algorithm by f B (
f k (
t
+
1
)
0
) =
1
,
f k (
0
) =
0
,
k
∈
Q .
The complete algorithm is:
￿
Initialization
(
t
=
0
)
: f B (
0
) =
1
,
f j (
0
) =
0
,
j
∈
Q .
x t ) j ∈ Q f j (
￿ Recursion (repeat for t
=
1
,
2
,...,
l ): f k (
t
) =
e k (
t
−
1
)
a jk ,
k
∈
Q .
) = k ∈ Q f k (
￿ Termination: P
(
x
l
)
.
Example 9.7. Consider again the HMM from Example 9.5 . Use the forward algo-
rithm to compute the probability of the sequence x
=
LWW .
Solution:
t
=
0
:
f B (
) =
,
We begin with probability 1 at the beginning state B and, thus,
0
1
f F (
0
) =
0
,
f U (
0
) =
0.
t
=
1
:
f F (
) =
(
x 1 =
,π 1 =
) =
f B (
)
a 0 F e F (
) = (
.
)(
.
) =
.
.
1
P
L
F
0
L
0
5
0
33
0
165
f U (
) =
(
x 1 =
,π 1 =
) =
f B (
)
a 0 U e U (
) = (
.
)(
.
) =
.
.
1
P
L
U
0
L
0
5
0
6
0
30
t
=
2
:
f F (
2
) =
P
(
x 1 =
L
,
x 2 =
W
,π 2 =
F
) =
e F (
W
)(
f F (
1
)
a FF +
f U (
1
)
a UF )
= (
0
.
67
)((
0
.
165
) ∗ (
0
.
7
) + (
0
.
3
) ∗ (
0
.
4
)) =
0
.
1578
.
f U (
2
) =
P
(
x 1 =
L
,
x 2 =
W
,π 2 =
U
) =
e U (
W
)(
f F (
1
)
a FU +
f U (
1
)
a UU )
= (
0
.
4
)((
0
.
1667
) ∗ (
0
.
3
) + (
0
.
3
) ∗ (
0
.
6
)) =
0
.
0918
.
t
=
3
:
f F (
3
) =
P
(
x 1 =
L
,
x 2 =
W
,
x 3 =
W
,π 3 =
F
)
=
e F (
W
)(
f F (
2
)
a FF +
f U (
2
)
a UF )
= (
0
.
67
)((
0
.
1578
) ∗ (
0
.
7
) + (
0
.
092
) ∗ (
0
.
4
)) =
0
.
0986
.
f U (
3
) =
P
(
x 1 =
L
,
x 2 =
W
,
x 3 =
W
,π 3 =
U
)
=
e U (
W
)(
f F (
2
)
a FU +
f U (
2
)
a UU )
= (
0
.
4
)((
0
.
1578
) ∗ (
0
.
3
) + (
0
.
0918
) ∗ (
0
.
6
)) =
0
.
041
.
Finally, we have P
(
x
) =
P
(
LWW
) =
0
.
0986
+
0
.
041
=
0
.
1396.
 
Previous Page
Next Page
Mathematical Concepts and Methods in Modern Biology
Search WWH ::




Custom Search
Home