Biology Reference
In-Depth Information
B
B
B
B
1
F
F
F
F
0.167
0.0804
0.038
U
U
U
U
0.3
0.072
0.0173
t
= 0
t
= 1
t
= 2
t
= 3
FIGURE 9.6
Trellis diagram for Example
9.5
.
B
is the beginning state (the ending state is not pictured).
The numbers under each node indicate the maximal probability for all paths ending in
this node and emitting sequences in agreement with the data. The dashed arrows indicate
possible transitions. For each node, the solid arrow into the node is the pointer indicating
where the maximal probability path comes from.
LWW
and the algorithm
terminates. The probability of the most likely path is therefore
We have reached the end of the sequence
x
=
x
1
x
2
x
3
=
,π
∗
)
=
P
(
x
max
π
P
(
x
,π)
=
max
j
Q
{
v
j
(
l
)
}=
max
{
v
F
(
3
), v
U
(
3
)
}
∈
=
max
{
0
.
038
,
0
.
017
}=
0
.
038
.
The maximum was achieved at
v
F
(
3
)
, thus the ending state for the most likely path is
π
3
=
F
. Since ptr
3
(
F
)
=
F
, the most likely path into
F
at time
t
=
3 came from
F
,
π
2
and thus
=
F
. Since ptr
2
(
F
)
=
U
, the most likely path into
F
at time
t
=
2 came
π
1
from
U
, and thus
=
U
. Therefore, the hidden sequence of maximal probability
π
∗
=
π
1
π
2
π
3
0.038 is
UFF
.
It is convenient to visualize the Viterbi algorithm by using a
trellis diagram
that
makes it easier to follow the process. In a trellis diagram, the columns are labeled
with the values of
t
and the rows correspond to the states of the Markov chain (see
Figure
9.6
). Starting from the stateBand following the arrows can generate all possible
paths
=
π
=
π
1
π
2
π
3
. The number under each node is the maximal probability for the
path ending in the node and agreeing with the observed data up to that time (these are
the
-values computed by the Viterbi algorithm). The solid arrow into each node is
the pointer that keeps track of the origin of the maximal probability path. Locating the
largest probability in the last column and backtracking using the solid lines, generates
the maximal probability path
v
π
∗
=
π
1
π
2
π
3
.
Search WWH ::
Custom Search