Biology Reference
In-Depth Information
ptr
t
(
r
means that the path with the highest probability ending in state
k
at time
t
came from
state
r
at time
t
k
)
=
r
, where
v
r
(
t
−
1
)
a
rk
=
max
j
∈
Q
{
v
j
(
t
−
1
)
a
jk
}
. The notation ptr
t
(
k
)
=
1.
Utilizing the agreement that the process always starts in the beginning state B,
Viterbi's algorithms can be summarized as follows. To find themost probable path
−
π
=
π
1
π
2
π
3
···
π
l
for the observed data
x
=
x
1
x
2
x
3
···
x
l
, perform the following steps:
Initialization
t
=
0:
v
B
(
0
)
=
1
,v
j
(
0
)
=
0
,
j
∈
Q
.
Recursion (repeat for
t
=
1
,
2
,...,
l
:
v
k
(
t
)
=
e
k
(
x
t
)
max
j
∈
Q
{
v
j
(
t
−
1
)
a
jk
};
ptr
t
(
k
)
=
r
where
r
=
argmax
j
{
v
j
(
t
−
1
)
a
jk
}
.
,π
∗
)
=
)
=
π
l
Termination:
P
(
x
max
P
(
x
,π)
=
max
j
∈
Q
{
v
j
(
l
)
};
ptr
l
(
k
.
π
π
∗
can now be found by backtracking through the
The maximal probability path
recorded pointers.
Our next example illustrates the method.
Example 9.5.
Consider the game from Example
9.3
with modified transition prob-
abilities between the hidden states
F
and
U
as in Table
9.6
. Assume we have observed
the sequence
x
=
x
1
x
2
x
3
=
LWW
. We will apply the Viterbi algorithm to compute
the most likely hidden path
π
=
π
1
π
2
π
3
for this observed sequence.
=
t
0:
v
B
(
)
=
,v
F
(
)
=
We begin with probability 1 at the beginning state and thus
0
1
0
,v
U
(
)
=
v
B
(
)
=
0
1 is used just for initialization. It
stands for the most probable path ending in
B
at time
t
0
0. As explained earlier,
0
=
0. Since all paths of the
process start from
B
,
v
B
(
0
)
=
1. Since no path can be in either
F
or
U
at time
t
=
0
,v
F
(
0
)
=
0
,v
U
(
0
)
=
0.
t
=
1
:
v
F
(
1
)
=
max
π
1
P
(π
1
=
F
,
x
1
=
L
)
=
max
{
v
B
(
0
)
a
0
F
e
F
(
L
)
}
=
(
0
.
5
)(
0
.
33
)
=
0
.
1667
.
The maximum is taken over all paths that start at the beginning state and end at
F
.
There is only one such path. Thus
is the probability that the process is at state
F
at time 1 (which occurs with probability 0.5) and that it emits the symbol
x
1
=
v
F
(
1
)
L
from
that state (which happens with probability 0.33). Similarly,
v
U
(
1
)
=
max
1
P
(π
1
=
π
U
,
x
1
=
L
)
=
max
{
v
B
(
0
)
a
0
U
e
U
(
L
)
}=
v
B
(
0
)
a
0
U
e
U
(
L
)
=
(
0
.
5
)(
0
.
6
)
=
0
.
30.
Table 9.6
HMM parameters for Example
9.5
.
Transitions
Emissions
Initial Distribution
F
U
W
L
F
0.7
0.3
0.67
0.33
0.5
U
0.4
0.6
0.40
0.60
0.5
Search WWH ::
Custom Search