Graphics Reference
In-Depth Information
Cross-validation
The traditional approach of cross-validation consists in dividing the data to classify into training
and testing partitions a number of times. In our studies, we applied
K
-fold cross-validation
procedure (with
k
10), where the data was first partitioned into
k
equally (or nearly equally)
sized segments or folds. Subsequently
k
iterations of training and validation were performed
such that within each iteration a different fold of the data was held out for validation, while
the remaining
k
=
1 folds were used for learning. Following this procedure we measured the
classification accuracy of the considered classifier.
−
Hidden Markov Model
HMM consists of
<
S
,
s
0
,
O
,
A
,
B
>
:
S
: the set of states;
•
s
0
: the initial state where everything begins;
•
O
: the sequence of observations, each of which is drawn from a vocabulary,
o
1
,
o
2
,...,
o
T
;
•
A
: the transitional probability matrix;
•
B
: the emission probabilities, where
b
i
(
o
t
) is the probability of observation
o
t
generated
from state
i
.
•
Forward-Backward Probability
Forward probability: At time
t
, the probability that
-
we are in state
i
-
the observation thus far has been
o
1
...
•
o
t
-
α
t
(
i
)
=
P
(
s
t
=
i
,
o
1
,...,
o
t
|
λ
).
Backward probability: At time
t
and we are in state
i
, the probability that
-
the observation that follows will be
o
t
+
1
...
•
o
T
-
β
t
(
i
)
=
P
(
o
t
+
a
...
o
T
|
s
t
=
i
,λ
).
Baum-Welch Algorithm
The Baum-Welch algorithm is used to estimate the parameters of a Hidden Markov model. It
can compute maximum likelihood estimates and posterior mode estimates for the parameters
(transition and emission probabilities) of an HMM, when given only emissions as training data.
Algorithm 11
Baum-Welch algorithm
1. Initialize the parameters to some values;
2. Calculate “forward-backward” probabilities based on the current parameters;
3. Use the forward-backward probabilities to estimate the expected frequencies;
•
Expected number of transitions from state
i
(to state
j
);
•
Expected number of being in state
j
(and observing
o
t
);
•
Expected number of starting in state
j
;
4. Use the expected frequencies to estimate the parameters;
5. Repeat 2 to 4 until the parameters converge.
