# A Novel Method for Decoding Any High-Order Hidden Markov Model

Authors: Fei Ye; Yifei Wang
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

This paper proposes a novel method for decoding any high-order hidden Markov model. First, the high-order hidden Markov model is transformed into an equivalent first-order hidden Markov model by Hadar’s transformation. Next, the optimal state sequence of the equivalent first-order hidden Markov model is recognized by the existing Viterbi algorithm of the first-order hidden Markov model. Finally, the optimal state sequence of the high-order hidden Markov model is inferred from the optimal state sequence of the equivalent first-order hidden Markov model. This method provides a unified algorithm framework for decoding hidden Markov models including the first-order hidden Markov model and any high-order hidden Markov model.


---

## Body

## 1. Introduction

Hidden Markov models are powerful tools for modeling and analyzing sequential data. For several decades, hidden Markov models have been used in many fields including handwriting recognition [1–3], speech recognition [4, 5], computational biology [6, 7], and longitudinal data analysis [8, 9]. Past and current developments on hidden Markov models are well documented in [10, 11]. A hidden Markov model comprises an underlying Markov chain and an observed process, where the observed process is a probabilistic function of the underlying Markov chain [12]. Given a hidden Markov model, an efficient procedure for finding the optimal state sequence is of great interest in the real-world applications. In the traditional first-order hidden Markov model, the Viterbi algorithm is utilized to recognize the optimal state sequence [13]. Like the Kalman filter, the Viterbi algorithm tracks the optimal state sequence with a recursive method.In recent years, the theory and applications of high-order hidden Markov models have been substantially advanced, and high-order hidden Markov models are known to be more powerful than the first-order hidden Markov model. There are two basic approaches to study the algorithms of high-order hidden Markov models. The first one is called the extended approach, which is to extend directly the existing algorithms of the first-order hidden Markov model to high-order hidden Markov models [14–16]. The second one is called the model reduction method, which is to transform a high-order hidden Markov model to an equivalent first-order hidden Markov model by some means and then to establish the algorithms of the high-order hidden Markov model by using standard techniques applicable to the first-order hidden Markov model [17–20].In this paper, we propose a novel method for decoding any high-order hidden Markov model. First, the high-order hidden Markov model is transformed into an equivalent first-order hidden Markov model by Hadar’s transformation. Next, the optimal state sequence of the equivalent first-order hidden Markov model is recognized by the existing Viterbi algorithm of the first-order hidden Markov model. Finally, the optimal state sequence of the high-order hidden Markov model is inferred from the optimal state sequence of the equivalent first-order hidden Markov model.


## 2. High-Order Hidden Markov Model and Hadar’s Transformation

Initially suppose two processes{
q
~
t
} and {
o
t
} are defined on some probability space (
Ω
,
F
,
P
), where t is an integer index. q
~
t takes values in a finite set S
~
=
{
s
0
,
s
1
,
…
,
s
N
-
1
}, and o
t takes values in a finite set V
~
=
{
v
1
,
v
2
,
…
,
v
M
}. Without loss of generality, the elements of S
~ can be denoted by {
0,1
,
…
,
N
-
1
}. A high-order hidden Markov model is defined as follows.Definition 1 (see [18, 20]).
A high-order hidden Markov model is a doubly stochastic process with an underlying state process that is not directly observable but can be observed only through another stochastic process that is called the observation process. The observation process is governed by the hidden state process and produces the observation sequence. The state process and observation process, respectively, satisfy the following conditions.(a)
The hidden state process{
q
~
t
} is a homogeneous Markov chain of order n, that is, a stochastic process that satisfies
(1)
P
q
~
t
∣
q
~
l
l
<
t
=
P
q
~
t
∣
q
~
l
l
=
t
-
n
t
-
1
.
(b)
The observation process{
o
t
} is governed by the hidden state process according to a set of probability distributions that satisfy
(2)
P
o
t
∣
o
l
l
<
t
,
q
~
l
l
≤
t
=
P
o
t
∣
q
~
l
l
=
t
-
m
-
1
t
.To model the high-order hidden Markov model, the following parameters are needed.(1)
State transition probability distribution:(3)
a
~
i
n
⋯
i
1
i
0
=
P
q
~
t
=
i
0
∣
q
~
t
-
1
=
i
1
,
…
,
q
~
t
-
n
=
i
n
.
(2)
Symbol emission probability distribution:(4)
b
~
i
m
-
1
⋯
i
0
l
=
P
o
t
=
v
l
∣
q
~
t
=
i
0
,
…
,
q
~
t
-
m
-
1
=
i
m
-
1
.
(3)
Initial state probability distribution:(5)
π
~
i
r
⋯
i
1
=
P
q
~
1
=
i
1
,
…
,
q
~
2
-
r
=
i
r
,where r
=
max
⁡
{
n
,
m
},  i
0
,
i
1
,
…
,
i
r
∈
S
~, and v
l
∈
V
~. We call A
~
=
{
a
~
i
n
⋯
i
1
i
0
}, B
~
=
{
b
~
i
m
-
1
⋯
i
0
(
l
)
}, and π
~
=
{
π
~
i
r
⋯
i
1
}. For convenience, we use the compact notation λ
~
=
(
π
~
,
A
~
,
B
~
) to indicate the complete parameters of the high-order hidden Markov model.Definition 2 (see [18]).
Let(6)
f
:
S
^
=
0,1
,
…
,
N
-
1
r
⟶
S
=
0,1
,
…
,
N
r
-
1
be the mapping of any base N number to its decimal value; that is, if [
i
0
,
i
1
,
…
,
i
r
-
1
]
∈
S
^, then
(7)
f
i
0
,
i
1
,
…
,
i
r
-
1
=
∑
l
=
0
r
-
1
‍
i
l
N
r
-
1
-
l
.Definition 3 (see [17]).
Any two modelsλ
1 and λ
2 are defined as equivalent if
(8)
P
O
∣
λ
1
=
P
O
∣
λ
2
for any arbitrary observation sequence O. In other words, two models are only considered equivalent if they yield the same likelihood, regardless of the specific observation sequence.Based on Definition2, we set
(9)
q
t
=
f
q
~
t
,
q
~
t
-
1
,
…
,
q
~
t
-
r
-
1
=
∑
l
=
0
r
-
1
‍
q
~
t
-
l
N
r
-
1
-
l
.
Since q
~
t
,
q
~
t
-
1
,
…,  and q
~
t
-
(
r
-
1
) take values in the set S
~
=
{
0,1
,
…
,
N
-
1
}, q
t takes values in the set S
=
{
0,1
,
…
,
N
r
-
1
}. Moreover, it is easy to see that the inverse transformation can be implemented as follows:
(10)
kkkk
q
~
t
=
q
t
N
r
-
1
,
kik
q
~
t
-
1
=
q
t
-
q
~
t
N
r
-
1
N
r
-
2
,
kkkikkk
⋮
q
~
t
-
(
r
-
1
)
=
q
t
-
q
~
t
N
r
-
1
-
⋯
-
q
~
t
-
(
r
-
2
)
N
.Remark 4.
The functionf is a one to one correspondence between the set S
^
=
{
0,1
,
…
,
N
-
1
}
r and the set S
=
{
0,1
,
…
,
N
r
-
1
}.Proposition 5 (see [18]).
Leta
i
j
=
P
(
q
t
+
1
=
j
∣
q
t
=
i
) for any i
,
j
∈
S. If ⌊
i
/
N
⌋
≠
j
-
⌊
j
/
N
r
-
1
⌋
N
r
-
1, then a
i
j
=
0; that is, a transition from q
t
=
i to q
t
+
1
=
j is impossible.Lemma 6.
Letq
t
=
∑
l
=
0
r
-
1
‍
q
~
t
-
l
N
r
-
1
-
l; then the process {
q
t
} forms the first-order homogeneous Markov chain.Proof.
Without loss of generality, we may assume thatq
t
=
i and q
t
+
1
=
j, where i
,
j
∈
S.
First, we consider the case that⌊
i
/
N
⌋
≠
j
-
⌊
j
/
N
r
-
1
⌋
N
r
-
1. By Proposition 5, it is easy to see that
(11)
P
q
t
+
1
=
j
∣
q
t
=
i
,
q
t
-
1
=
⋯
=
P
q
t
+
1
=
j
∣
q
t
=
i
=
0
.
Next, we consider the case that⌊
i
/
N
⌋
=
j
-
⌊
j
/
N
r
-
1
⌋
N
r
-
1. Since q
t
=
i and q
t
+
1
=
j, it follows from (10) that
(12)
kkkk
q
~
t
+
1
=
i
0
,
kkkkik
q
~
t
=
i
1
,
kkkkkkkk
⋮
q
~
t
+
1
-
r
-
1
=
i
r
-
1
,
ik
q
~
t
-
(
r
-
1
)
=
i
r
,
where i
0
,
i
1
,
…
,
i
r
-
1
,
i
r
∈
S
~. Moreover, we have
(13)
P
q
t
+
1
=
j
∣
q
t
=
i
,
q
t
-
1
=
⋯
=
P
q
~
t
+
1
=
i
0
,
q
~
t
=
i
1
,
…
,
q
~
(
t
+
1
)
-
(
r
-
1
)
=
i
r
-
1
∣
q
~
t
=
i
1
,
…
,
q
~
t
-
(
r
-
2
)
=
i
r
-
1
,
q
~
t
-
(
r
-
1
)
=
i
r
,
q
~
t
-
r
=
⋯
=
P
q
~
t
+
1
=
i
0
∣
q
~
t
=
i
1
,
…
,
q
~
t
-
(
n
-
2
)
=
i
n
-
1
,
q
~
t
-
(
n
-
1
)
=
i
n
=
P
q
~
t
+
1
=
i
0
∣
q
~
t
=
i
1
,
…
,
q
~
t
-
(
r
-
2
)
=
i
r
-
1
,
q
~
t
-
(
r
-
1
)
=
i
r
=
P
q
~
t
+
1
=
i
0
,
q
~
t
=
i
1
,
…
,
q
~
t
-
(
r
-
2
)
=
i
r
-
1
∣
q
~
t
=
i
1
,
…
,
q
~
t
-
(
r
-
2
)
=
i
r
-
1
,
q
~
t
-
(
r
-
1
)
=
i
r
=
P
q
t
+
1
=
j
∣
q
t
=
i
.
Through the above analysis, we derive that(14)
P
q
t
+
1
∣
q
l
l
<
t
+
1
=
P
q
t
+
1
∣
q
t
.
Analogously, it is easy to see that(15)
P
q
t
+
1
=
j
∣
q
t
=
i
=
P
q
t
=
j
∣
q
t
-
1
=
i
.
Therefore, the process{
q
t
} forms the first-order homogeneous Markov chain.Lemma 7.
The two processes{
q
t
} and {
o
t
} form the first-order hidden Markov model.Proof.
Without loss of generality, we may assume thato
t
=
v
l and q
t
=
i, where v
l
∈
V
~ and i
∈
S. Since q
t
=
i, it follows from (10) that
(16)
kkkk
q
~
t
=
i
1
,
kik
q
~
t
-
1
=
i
2
,
kkkkkk
⋮
q
~
t
-
(
r
-
1
)
=
i
r
,
where i
1
,
i
2
,
…
,
i
r
∈
S
~. Moreover, we have
(17)
P
o
t
=
v
l
∣
o
l
l
<
t
,
q
l
l
<
t
,
q
t
=
i
=
P
o
t
=
v
l
∣
o
l
l
<
t
,
q
~
t
=
i
1
,
q
~
t
-
1
=
i
2
,
…
,
q
~
t
-
r
-
1
=
i
r
,
o
l
l
<
t
,
q
~
t
=
i
1
q
~
t
-
(
r
-
2
)
=
⋯
=
P
o
t
=
v
l
∣
q
~
t
=
i
1
,
q
~
t
-
1
=
i
2
,
…
,
q
~
t
-
(
m
-
1
)
=
i
m
q
~
t
-
1
=
i
2
,
…
,
q
~
t
-
(
m
-
1
)
=
i
m
=
P
o
t
=
v
l
∣
q
~
t
=
i
1
,
q
~
t
-
1
=
i
2
,
…
,
q
~
t
-
(
r
-
1
)
=
i
r
=
P
o
t
=
v
l
∣
q
t
=
i
.
Analogously, it is easy to see that(18)
P
o
t
=
v
l
∣
q
t
=
i
=
P
o
t
-
1
=
v
l
∣
q
t
-
1
=
i
.
Combining these with Lemma6, we prove that the two processes {
q
t
} and {
o
t
} form the first-order hidden Markov model.Remark 8.
Hadar and Messer [18] had also mentioned the fact that the two processes {
q
t
} and {
o
t
} form the first-order hidden Markov model, but they did not discuss and prove it in detail.To model the first-order hidden Markov model{
q
t
,
o
t
}, the following parameters are needed.(1)
State transition probability distribution:(19)
a
i
j
=
P
q
t
+
1
=
j
∣
q
t
=
i
.
(2)
Symbol emission probability distribution:(20)
b
i
l
=
P
o
t
=
v
l
∣
q
t
=
i
.
(3)
Initial state probability distribution:(21)
π
i
=
P
q
1
=
i
,where i
,
j
∈
S and v
l
∈
V
~. We call A
=
{
a
i
j
}, B
=
{
b
i
(
l
)
}, and π
=
{
π
i
}. For convenience, we use the compact notation λ
=
(
π
,
A
,
B
) to indicate the complete parameters of the first-order hidden Markov model.Proposition 9 (see [18]).
Leti
=
f
(
[
i
1
,
…
,
i
r
]
) and j
=
f
(
[
i
0
,
…
,
i
r
-
1
]
) for any i
0
,
i
1
,
…
,
i
r
∈
S
~; then
(22)
π
~
i
r
⋯
i
1
=
π
i
,
a
~
i
n
⋯
i
0
=
a
i
j
,
b
~
i
m
⋯
i
1
l
=
b
i
l
.Lemma 10.
LetO
=
o
1
⋯
o
T be any arbitrary observation sequence; then
(23)
P
O
∣
λ
~
=
P
O
∣
λ
.
That is, the high-order hidden Markov model {
q
~
t
,
o
t
} is equivalent to the first-order hidden Markov model {
q
t
,
o
t
}.Proof.
For anyi
2
-
r
,
…
,
i
1
,
…
,
i
T
-
(
r
-
1
)
,
…
,
i
T
∈
S
~, let
(24)
j
1
=
f
i
1
,
…
,
i
2
-
r
,
…
,
j
T
=
f
i
T
,
…
,
i
T
-
r
-
1
.
By Proposition9, we have
(25)
P
O
∣
λ
~
=
∑
i
2
-
r
=
0
N
-
1
‍
⋯
∑
i
T
=
0
N
-
1
P
o
1
⋯
o
T
,
q
~
2
-
r
=
i
2
-
r
,
…
,
q
~
T
=
i
T
∣
λ
~
‍
=
∑
i
2
-
r
=
0
N
-
1
‍
⋯
∑
i
T
=
0
N
-
1
‍
π
~
i
2
-
r
⋯
i
1
b
~
i
2
-
m
⋯
i
1
o
1
×
a
~
i
2
-
n
⋯
i
2
b
~
i
3
-
m
⋯
i
2
o
2
⋯
×
a
~
i
T
-
n
⋯
i
T
b
~
i
T
-
m
+
1
⋯
i
T
o
T
=
∑
i
2
-
r
=
0
N
-
1
‍
⋯
∑
i
T
=
0
N
-
1
‍
π
~
i
2
-
r
⋯
i
1
b
~
i
2
-
r
⋯
i
1
o
1
×
a
~
i
2
-
r
⋯
i
2
b
~
i
3
-
r
⋯
i
2
o
2
⋯
×
a
~
i
T
-
r
⋯
i
T
b
~
i
T
-
r
+
1
⋯
i
T
o
T
=
∑
j
1
=
0
N
r
-
1
‍
⋯
∑
j
T
=
0
N
r
-
1
‍
π
j
1
b
j
1
o
1
a
j
1
j
2
b
j
2
o
2
⋯
×
a
j
T
-
1
j
T
b
j
T
o
T
=
∑
j
1
=
0
N
r
-
1
‍
⋯
∑
j
T
=
0
N
r
-
1
‍
P
o
1
⋯
o
T
,
q
1
=
j
1
,
…
,
q
T
=
j
T
∣
λ
=
P
O
∣
λ
.Remark 11.
Hadar and Messer [18] had also mentioned the fact that the high-order hidden Markov model {
q
~
t
,
o
t
} is equivalent to the first-order hidden Markov model {
q
t
,
o
t
}, but they did not discuss and prove it in detail.


## 3. Methodology

Theorem 12.
LetO
=
o
1
⋯
o
T be any given observation sequence, and assume that q
t
=
f
(
[
q
~
t
,
q
~
t
-
1
,
…
,
q
~
t
-
(
r
-
1
)
]
)
=
∑
l
=
0
r
-
1
‍
q
~
t
-
l
N
r
-
1
-
l; then
(26)
P
q
~
2
-
r
⋯
q
~
T
∣
O
,
λ
~
=
P
q
1
⋯
q
T
∣
O
,
λ
.Proof.
Without loss of generality, letq
~
2
-
r
=
i
2
-
r
,
…
,
q
~
T
=
i
T, where i
2
-
r
,
…
,
i
T
∈
S
~. According to Proposition 9, we have
(27)
P
o
1
⋯
o
T
,
q
~
2
-
r
=
i
2
-
r
,
…
,
q
~
T
=
i
T
∣
λ
~
=
π
~
i
2
-
r
⋯
i
1
b
~
i
2
-
m
⋯
i
1
o
1
a
~
i
2
-
n
⋯
i
2
×
b
~
i
3
-
m
⋯
i
2
o
2
⋯
a
~
i
T
-
n
⋯
i
T
b
~
i
T
-
m
+
1
⋯
i
T
o
T
=
π
~
i
2
-
r
⋯
i
1
b
~
i
2
-
r
⋯
i
1
o
1
a
~
i
2
-
r
⋯
i
2
×
b
~
i
3
-
r
⋯
i
2
o
2
⋯
a
~
i
T
-
r
⋯
i
T
b
~
i
T
-
r
+
1
⋯
i
T
o
T
=
π
j
1
b
j
1
o
1
a
j
1
j
2
b
j
2
o
2
⋯
a
j
T
-
1
j
T
b
j
T
o
T
=
P
o
1
⋯
o
T
,
q
1
=
j
1
,
…
,
q
T
=
j
T
∣
λ
,
where j
t
=
f
(
[
i
t
,
…
,
i
t
-
(
r
-
1
)
]
) for 1
≤
t
≤
T.
On the other hand, it is easy to see that(28)
P
q
~
2
-
r
=
i
2
-
r
,
…
,
q
~
T
=
i
T
∣
O
,
λ
~
=
P
O
,
q
~
2
-
r
=
i
2
-
r
,
…
,
q
~
T
=
i
T
∣
λ
~
P
O
∣
λ
~
,
P
q
1
=
j
1
,
…
,
q
T
=
j
T
∣
O
,
λ
=
P
O
,
q
1
=
j
1
,
…
,
q
T
=
j
T
∣
λ
P
O
∣
λ
.
Hence, by Lemma10, we have
(29)
P
q
~
2
-
r
⋯
q
~
T
∣
O
,
λ
~
=
P
q
1
⋯
q
T
∣
O
,
λ
.Theorem 13.
LetO
=
o
1
⋯
o
T be any given observation sequence, and assume that the state sequence Q
~
*
=
q
~
2
-
r
*
⋯
q
~
T
* satisfies
(30)
Q
~
*
=
argmax
Q
~
P
Q
~
,
O
∣
λ
~
;
that is, the state sequence Q
~
*
=
q
~
2
-
r
*
⋯
q
~
T
* is some optimal state sequence of the high-order hidden Markov model {
q
~
t
,
o
t
}. Let q
t
*
=
f
[
q
~
t
*
,
…
,
q
~
t
-
(
r
-
1
)
*
]  (
1
≤
t
≤
T
); then the state sequence Q
*
=
q
1
*
⋯
q
T
* satisfies
(31)
P
Q
*
,
O
∣
λ
=
max
⁡
Q
P
Q
,
O
∣
λ
.
That is, the state sequence Q
*
=
q
1
*
⋯
q
T
* is some optimal state sequence of the first hidden Markov model {
q
t
,
o
t
}.Proof.
By Theorem12, it is easy to see that
(32)
P
Q
*
,
O
∣
λ
=
P
Q
~
*
,
O
∣
λ
~
,
max
⁡
Q
P
Q
,
O
∣
λ
=
max
⁡
Q
~
P
Q
~
,
O
∣
λ
~
.
Meanwhile, we have the equation
(33)
P
Q
~
*
,
O
∣
λ
~
=
max
⁡
Q
~
P
Q
~
,
O
∣
λ
~
.
Hence, we drive that
(34)
P
Q
*
,
O
∣
λ
=
max
⁡
Q
P
Q
,
O
∣
λ
.According to Theorem13, we can know that some optimal state sequence of the high-order hidden Markov model {
q
~
t
,
o
t
} is mapped to some optimal state sequence of the first-order hidden Markov model {
q
t
,
o
t
}. Similarly, we can draw the following conclusion.Theorem 14.
LetO
=
o
1
⋯
o
T be any given observation sequence, and assume that the state sequence Q
*
=
q
1
*
⋯
q
T
* satisfies
(35)
Q
*
=
argmax
Q
P
Q
,
O
∣
λ
;
that is, the state sequence Q
*
=
q
1
*
⋯
q
T
* is some optimal state sequence of the first-order hidden Markov model {
q
t
,
o
t
}. For 1
≤
t
≤
T, let
(36)
kkkk
q
~
t
*
=
q
t
*
N
r
-
1
,
kik
q
~
t
-
1
*
=
q
t
*
-
q
~
t
*
N
r
-
1
N
r
-
2
,
kkkikkk
⋮
q
~
t
-
r
-
1
*
=
q
t
*
-
q
~
t
*
N
r
-
1
-
⋯
-
q
~
t
-
r
-
2
*
N
;
then the state sequence Q
~
*
=
q
~
1
*
⋯
q
~
T
* satisfies
(37)
P
Q
~
*
,
O
∣
λ
~
=
max
⁡
Q
~
P
Q
~
,
O
∣
λ
~
.
That is, the state sequence Q
~
*
=
q
~
1
*
⋯
q
~
T
* is some optimal state sequence of the high-order hidden Markov model {
q
~
t
,
o
t
}.Remark 15.
Combining Theorem13 with Theorem 14, it is known that there exists a one to one correspondence between the optimal state sequence of the high-order hidden Markov model {
q
~
t
,
o
t
} and the optimal state sequence of the first-order hidden Markov model {
q
t
,
o
t
}.To decode any high-order hidden Markov model{
q
~
t
,
o
t
}, we transform it into an equivalent first-order hidden Markov model {
q
t
,
o
t
} by Hadar’s transformation. Then, do as follows.Step 1.
Determine some optimal state sequenceQ
*
=
q
1
*
q
2
*
⋯
q
T
* of the first-order hidden Markov model {
q
t
,
o
t
} by using the Viterbi algorithm. Without loss of generality, let
(38)
q
1
*
=
j
1
,
q
2
*
=
j
2
,
kkk
⋮
q
T
*
=
j
T
,
where j
1
,
j
2
,
…
,
j
T
∈
S.Step 2.
Forq
T
*
=
j
T, using the transformations
(39)
kkkk
q
~
t
=
q
t
N
r
-
1
,
kik
q
~
t
-
1
=
q
t
-
q
~
t
N
r
-
1
N
r
-
2
,
kikkkkk
⋮
q
~
t
-
(
r
-
1
)
=
q
t
-
q
~
t
N
r
-
1
-
⋯
-
q
~
t
-
(
r
-
2
)
N
,
we have
(40)
kkkk
q
~
T
*
=
j
T
N
r
-
1
,
ikk
q
~
T
-
1
*
=
j
T
-
q
~
T
*
N
r
-
1
N
r
-
2
,
kkkikkk
⋮
q
~
T
-
(
r
-
2
)
*
=
j
T
-
∑
l
=
0
r
-
3
‍
q
~
T
-
l
*
N
r
-
1
-
l
N
,
q
~
T
-
(
r
-
1
)
*
=
j
T
-
∑
l
=
0
r
-
2
‍
q
~
T
-
l
*
N
r
-
1
-
l
.Step 3.
Forq
1
*
=
j
1, q
2
*
=
j
2
,
…
,
q
T
-
1
*
=
j
T
-
1, using the transformation
(41)
q
t
=
∑
l
=
0
r
-
1
‍
q
~
t
-
l
N
r
-
1
-
l
,
we have
(42)
kik
q
~
T
-
r
*
=
j
T
-
1
-
∑
l
=
1
r
-
1
‍
q
~
T
-
l
*
N
r
-
l
,
q
~
T
-
(
r
+
1
)
*
=
j
T
-
2
-
∑
l
=
1
r
-
1
‍
q
~
T
-
1
-
l
*
N
r
-
l
,
kkkkkkk
⋮
kkk
q
~
2
-
r
*
=
j
1
-
∑
l
=
1
r
-
1
‍
q
~
2
-
l
*
N
r
-
l
.Combining Step2 with Step 3, we obtain the state sequence
(43)
Q
~
*
=
q
~
2
-
r
*
q
~
3
-
r
*
⋯
q
~
T
-
1
*
q
~
T
*
.According to Theorem14, the above state sequence Q
~
*
=
q
~
2
-
r
*
q
~
3
-
r
*
⋯
q
~
T
-
1
*
q
~
T
* is some optimal state sequence of the high-order hidden Markov model {
q
~
t
,
o
t
}.


## 4. Conclusions

In this paper, a novel method for decoding any high-order hidden Markov model is given. Based on this method, the optimal state sequence of any high-order hidden Markov model can be inferred by the existing Viterbi algorithm of the first-order hidden Markov model. This method has universal character for decoding hidden Markov models and provides a unified algorithm framework for decoding hidden Markov models including the first-order hidden Markov model and any high-order hidden Markov model. For instance, the Viterbi algorithm of the first-order hidden Markov model can be easily derived as a special case of our conclusion whenm
=
n
=
1.This method we analyzed is practical and valuable in its own right. Future research could use this method for applications in handwriting, speech recognition, speaker recognition, emotion recognition, and so forth.



---

*Source: 231704-2014-11-23.xml*