Biomedical Engineering Reference
In-Depth Information
The Baum-Welch algorithm is an application of the EM algorithm for HMMs. In an HMM,
X
t
is a discrete hidden random variable with possible states [1, ... ,
N
]. We further assume that the pa-
rameters of the hidden Markov chain are time-independent, that is,
P
(
X
t
|X
t
- 1
) is time homogeneous.
Therefore,
P
(
X
t
|X
t
- 1
) can be represented by a stochastic matrix
A
[
a
ij
]
= p
(
X
t
=
j|X
t
- 1
=
i
) that does not
change over time. The special case
t
= 1 is specified by the initial distribution π
i
=
p
(
X
1
=
i
). A particular
observation sequence
O
is described by
O
= (
O
1
=
o
1
, ... ,
O
T
=
o
T
). The probability of a particular ob-
servation vector at time t for state j is described by
b
j
(
o
t
) =
p
(
O
t
=
o
t
| X
t
=
j
). The complete collection
of parameters is represented by
B
=[
b
j
(.)].
There are three basic problems in HMM design but here we will only focus on the following
two:
Find
p
(
O|
λ) for some
O
=(
o
1
, ... ,
o
T
). We will use the forward procedure because it is much
more efficient than direct evaluation.
Find
λ
*
using the Baum-Welch algorithm.
=
max
p O
arg
(
|
λ
)
λ
For the forward algorithm, let us define a forward variable α
t
(
i
):
α
t
(
i
)
= P
(
O
1
,O
2
, … , O
t
, q
t
= X
i
|
λ)
(5.38)
which refers to the probability of the partial observation sequence [
O
1
, ... ,
O
t
] while being in state
X
i
at time
t
, given the model λ [
39
]. The α
t
(
i
) variables can be computed inductively, and from them,
P
(
O
|λ) is easily evaluated as explained by Rabiner [
39
] and Baum et al. [
40
]. The forward algorithm
is defined below:
1.
Initialize:
(5.39)
α
( )
i
=
P O q
(
,
=
X
i
|
λ
)
1
1
1
α
( )
i
=
P O q
(
|
=
X
,
λ
)
P
(
q
=
X
|
λ
)
(5.40)
i
i
1
1
1
1
(5.41)
α
( )
i
=
π
b O i
(
),
=
{ , ...,
1
N
}
i
i
1
1
2.
Induction:
)
(5.42)
α
( )
j
=
P O
(
, ...,
O
,
q
=
X
|
λ
1
1
1
j
t
+
1
t
+
t
+
N
)
P O
P O
(
,...,
O
t
,
q
t
X
i
| )
P q
t
(
X
j
|
q
t
X
i
,
=
=
=
λ
=
λ
α
t
(
j
)
=
λ
(
|
q
X
,
)
∑
j
+
1
+
+
+
1
1
1
t
1
t
i
=
1
N
α
( )
j
=
α
( )
i a
ij
b O
(
),
t
∈
{ ,... ,
1
T j
},
∈
{ ,...,
1
T
)
∑
(5.43)
t
j
+
+
t
1
t
1
i
=
1
