ред.
Прихована модель Маркова — це імовірнісна модель множини випадкових змінних
{
Y
1
,
…
,
Y
t
,
Q
1
,
…
,
Q
t
}
{\displaystyle \{Y_{1},\;\ldots ,\;Y_{t},\;Q_{1},\;\ldots ,\;Q_{t}\}}
Y
t
{\displaystyle Y_{t}}
Q
t
{\displaystyle Q_{t}}
t
{\displaystyle t}
(
t
−
1
)
{\displaystyle (t-1)}
(
t
−
1
)
{\displaystyle (t-1)}
P
(
Q
t
∣
Q
t
−
1
,
Y
t
−
1
,
…
,
Q
1
,
Y
1
)
=
P
(
Q
t
∣
Q
t
−
1
)
{\displaystyle P(Q_{t}\mid Q_{t-1},\;Y_{t-1},\;\ldots ,\;Q_{1},\;Y_{1})=P(Q_{t}\mid Q_{t-1})}
t
{\displaystyle t}
t
{\displaystyle t}
P
(
Y
t
∣
Q
t
,
Q
t
−
1
,
Y
t
−
1
,
…
,
Q
1
,
Y
1
)
=
P
(
Y
t
∣
Q
t
)
{\displaystyle P(Y_{t}\mid Q_{t},\;Q_{t-1},\;Y_{t-1},\;\ldots ,\;Q_{1},\;Y_{1})=P(Y_{t}\mid Q_{t})}
Далі буде запропоновано алгоритм «припущень і максимізації» для пошуку максимальної ймовірнісної оцінки параметрів прихованої моделі Маркова за заданого набору спостережень. Цей алгоритм також відомий як алгоритм Баума — Велша.
Q
t
{\displaystyle Q_{t}}
N
{\displaystyle N}
(
1
…
N
)
{\displaystyle (1\ldots N)}
P
(
Q
t
∣
Q
t
−
1
)
{\displaystyle P(Q_{t}\mid Q_{t-1})}
t
{\displaystyle t}
P
(
Q
t
∣
Q
t
−
1
)
{\displaystyle P(Q_{t}\mid Q_{t-1})}
стохастичну матрицю переміщень
A
=
{
a
i
j
}
=
p
(
Q
t
=
j
∣
Q
t
−
1
=
i
)
{\displaystyle A=\{a_{ij}\}=p(Q_{t}=j\mid Q_{t-1}=i)}
t
=
1
{\displaystyle t=1}
π
i
=
P
(
Q
1
=
i
)
{\displaystyle \pi _{i}=P(Q_{1}=i)}
Будемо вважати, що ми в стані
j
{\displaystyle j}
t
{\displaystyle t}
Q
t
=
j
{\displaystyle Q_{t}=j}
q
=
(
q
1
,
…
,
q
T
)
{\displaystyle q=(q_{1},\;\ldots ,\;q_{T})}
q
t
∈
{
1
…
N
}
{\displaystyle q_{t}\in \{1\ldots N\}}
t
{\displaystyle t}
Спостереження
Y
t
{\displaystyle Y_{t}}
t
{\displaystyle t}
L
{\displaystyle L}
y
t
∈
{
o
1
,
…
,
o
L
}
{\displaystyle y_{t}\in \{o_{1},\;\ldots ,\;o_{L}\}}
t
{\displaystyle t}
j
{\displaystyle j}
b
j
(
o
i
)
=
P
(
Y
t
=
o
i
∣
Q
t
=
j
)
{\displaystyle b_{j}(o_{i})=P(Y_{t}=o_{i}\mid Q_{t}=j)}
B
=
{
b
i
j
}
{\displaystyle B=\{b_{ij}\}}
L
{\displaystyle L}
N
{\displaystyle N}
y
{\displaystyle y}
y
=
(
y
1
,
…
,
y
T
)
{\displaystyle y=(y_{1},\;\ldots ,\;y_{T})}
Отже, ми можемо описати приховану модель Маркова за допомогою
λ
=
(
A
,
B
,
π
)
{\displaystyle \lambda =(A\;,B,\;\pi )}
y
{\displaystyle y}
λ
∗
=
a
r
g
max
λ
P
(
y
∣
λ
)
{\displaystyle \lambda ^{*}=arg\max _{\lambda }P(y\mid \lambda )}
λ
∗
{\displaystyle \lambda ^{*}}
y
{\displaystyle y}
Початкові дані:
λ
=
(
A
,
B
,
π
)
{\displaystyle \lambda =(A,\;B,\;\pi )}
Алгоритм ітеративно оновлює параметр
λ
{\displaystyle \lambda }
Позначимо через
α
i
(
t
)
=
p
(
Y
1
=
y
1
,
…
,
Y
t
=
y
t
,
Q
t
=
i
∣
λ
)
{\displaystyle \alpha _{i}(t)=p(Y_{1}=y_{1},\;\ldots ,\;Y_{t}=y_{t},\;Q_{t}=i\mid \lambda )}
y
1
,
…
,
y
t
{\displaystyle y_{1},\;\ldots ,\;y_{t}}
i
{\displaystyle i}
t
{\displaystyle t}
α
i
(
t
)
{\displaystyle \alpha _{i}(t)}
α
i
(
1
)
=
π
i
⋅
b
i
(
y
1
)
;
{\displaystyle \alpha _{i}(1)=\pi _{i}\cdot b_{i}(y_{1});}
α
j
(
t
+
1
)
=
b
j
(
y
t
+
1
)
∑
i
=
1
N
α
i
(
t
)
⋅
a
i
j
.
{\displaystyle \alpha _{j}(t+1)=b_{j}(y_{t+1})\sum _{i=1}^{N}{\alpha _{i}(t)\cdot a_{ij}}.}
Дана процедура дозволяє обчислити
β
i
(
t
)
=
p
(
Y
t
+
1
=
y
t
+
1
,
…
,
Y
T
=
y
T
∣
Q
t
=
i
,
λ
)
{\displaystyle \beta _{i}(t)=p(Y_{t+1}=y_{t+1},\ldots ,Y_{T}=y_{T}\mid Q_{t}=i,\lambda )}
y
t
+
1
,
…
,
y
T
{\displaystyle y_{t+1},\;\ldots ,\;y_{T}}
i
{\displaystyle i}
t
{\displaystyle t}
Можна обчислити
β
i
(
t
)
{\displaystyle \beta _{i}(t)}
β
i
(
T
)
=
p
(
Y
T
=
y
T
∣
Q
t
=
i
,
λ
)
=
1
;
{\displaystyle \beta _{i}(T)=p(Y_{T}=y_{T}\mid Q_{t}=i,\lambda )=1;}
β
i
(
t
)
=
∑
j
=
1
N
β
j
(
t
+
1
)
a
i
j
b
j
(
y
t
+
1
)
.
{\displaystyle \beta _{i}(t)=\sum _{j=1}^{N}{\beta _{j}(t+1)a_{ij}b_{j}(y_{t+1})}.}
Використовуючи
α
{\displaystyle \alpha }
β
{\displaystyle \beta }
γ
i
(
t
)
≡
p
(
Q
t
=
i
∣
y
,
λ
)
=
α
i
(
t
)
β
i
(
t
)
∑
j
=
1
N
α
j
(
t
)
β
j
(
t
)
,
{\displaystyle \gamma _{i}(t)\equiv p(Q_{t}=i\mid y,\;\lambda )={\frac {\alpha _{i}(t)\beta _{i}(t)}{\displaystyle \sum _{j=1}^{N}\alpha _{j}(t)\beta _{j}(t)}},}
ξ
i
j
(
t
)
≡
p
(
Q
t
=
i
,
Q
t
+
1
=
j
∣
y
,
λ
)
=
α
i
(
t
)
a
i
j
β
j
(
t
+
1
)
b
j
(
y
t
+
1
)
∑
i
=
1
N
∑
j
=
1
N
α
i
(
t
)
a
i
j
β
j
(
t
+
1
)
b
j
(
y
t
+
1
)
.
{\displaystyle \xi _{ij}(t)\equiv p(Q_{t}=i,\;Q_{t+1}=j\mid y,\;\lambda )={\frac {\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}{\displaystyle \sum _{i=1}^{N}\displaystyle \sum _{j=1}^{N}\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}}.}
Маючи
γ
{\displaystyle \gamma }
ξ
{\displaystyle \xi }
π
¯
i
=
γ
i
(
1
)
,
{\displaystyle {\bar {\pi }}_{i}=\gamma _{i}(1),}
a
¯
i
j
=
∑
t
=
1
T
−
1
ξ
i
j
(
t
)
∑
t
=
1
T
−
1
γ
i
(
t
)
,
{\displaystyle {\bar {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}\xi _{ij}(t)}{\displaystyle \sum _{t=1}^{T-1}\gamma _{i}(t)}},}
b
¯
i
(
o
k
)
=
∑
t
=
1
T
δ
y
t
,
o
k
γ
i
(
t
)
∑
t
=
1
T
γ
i
(
t
)
.
{\displaystyle {\bar {b}}_{i}(o_{k})={\frac {\displaystyle \sum _{t=1}^{T}\delta _{y_{t},\;o_{k}}\gamma _{i}(t)}{\displaystyle \sum _{t=1}^{T}\gamma _{i}(t)}}.}
де
δ
y
t
,
o
k
=
{
1
якщо
y
t
=
o
k
,
0
інакше
{\displaystyle \delta _{y_{t},\;o_{k}}={\begin{cases}1&{\text{якщо }}y_{t}=o_{k},\\0&{\text{інакше}}\end{cases}}}
індикативна функція, і
b
i
∗
(
o
k
)
{\displaystyle b_{i}^{*}(o_{k})}
o
k
{\displaystyle o_{k}}
i
{\displaystyle i}
i
{\displaystyle i}
Використовуючи нові значення
A
{\displaystyle A}
B
{\displaystyle B}
π
{\displaystyle \pi }
