Biology Reference
In-Depth Information
The average number of transitions from
j
to
k
in the training sequence
x
will then be
the sum of the probabilities of this transition occurring exactly at position
t
, over all
positions in the sequence
x
:
l
f
j
(
t
)
a
jk
e
k
(
x
t
+
1
)
b
k
(
t
+
1
)
A
jk
=
P
(
x
)
t
=
1
l
1
=
f
j
(
t
)
a
jk
e
k
(
x
t
+
1
)
b
k
(
t
+
1
).
(9.11)
P
(
x
)
t
=
1
In a similar way, since the posterior probabilities can be computed from the forward-
backward algorithm as
P
f
k
(
t
)
b
k
(
t
)
P
(π
t
=
k
|
x
,θ
0
)
=
(see Eq. (
9.6
)), the average
(
x
)
number of states emitting the symbol
b
∈
M
will be
f
k
(
t
)
b
k
(
t
)
1
E
k
(
b
)
=
=
f
k
(
t
)
b
k
(
t
).
(9.12)
P
(
x
)
P
(
x
)
{
t
=
1
,...,
l
|
x
t
=
b
}
{
t
=
1
,...,
l
|
x
t
=
b
}
Next, the expected counts from Eqs. (
9.11
) and (
9.12
) are substituted in the
Eqs. (
9.8
), generating improved estimates for the transition and emission proba-
bilities. This is the set of parameters that we have denoted by
θ
1
. Now, repeat-
ing the computations given by Eqs. (
9.11
) and (
9.12
) with the new values of the
parameters from the parameter set
θ
1
and substituting those values in Eqs. (
9.8
) will
generate the set of parameters
θ
2
and so on. The process is guaranteed to increase
the likelihood of the data, that is, for the sequence of parameter approximations
{
θ
i
}
,
=
,
,
,...,
(
|
θ
i
)
(
|
θ
i
+
1
)
[
33
]. The process terminates when two
successive values are either identical or sufficiently close.
Aswith the other algorithmswe have considered in this chapter, to avoid underflows
from multiplying small probabilities, the computations are usually carried out in
logarithm space. If several sequences
x
1
i
0
1
2
P
x
P
x
x
m
are used for training, Eqs. (
9.11
)
and (
9.12
) should be modified to include the sum of the expected counts from all
sequences:
x
2
,
,...,
m
l
1
f
j
(
x
t
+
1
)
b
k
(
A
jk
=
t
)
a
jk
e
k
(
t
+
1
),
x
i
P
(
)
i
=
1
t
=
1
m
1
f
k
(
b
k
(
E
k
(
b
)
=
t
)
t
),
(9.13)
x
i
P
(
)
i
=
1
{
t
=
1
,...,
l
|
x
t
=
b
}
where the superscripts
i
indicates that the respective probability is computed for the
sequence
x
i
.
Example 9.9.
Once again we will illustrate the method on simulated data from
the
Dishonest Casino
application in the
CpG Educate
suite with known parameters.
We used the algorithm three times for a simulated sequence of length 500, length
Search WWH ::
Custom Search