隐马尔可夫模型的维特比算法

作者: 引线小白-本文永久链接:http://www.limoncc.com/机器学习/2018-01-09-隐马尔可夫模型的维特比算法/
知识共享许可协议: 本博客采用署名-非商业-禁止演绎4.0国际许可证

Knowledge is the antidote to fear.
摘要:本文意在理清维特比算法的基础问题。本文通过清晰的数学符号,说明问题,大大易于理解。若有错误,请大家指正。
关键词: 隐马尔可夫模型,维特比算法,动态规划

一、问题描述

定义隐变量数据集 $\displaystyle \mathcal{D}_T^z$,观测变量数据集 $\displaystyle \mathcal{D}_T^\bm{x}$,完全数据集 $\displaystyle \mathcal{D}^+_T$。维特比算法要解决的是求隐变量最可能状态序列。可以理解为:已知观测变量数据集,推断隐变量数据集:

$$\begin{align}
\hat{\mathcal{D}_T^\bm{z}}=\mathop{\mathrm{argmax}}_{\mathcal{D}_T^\bm{z}}\,p \big(\mathcal{D}_T^\bm{z}\mid\mathcal{D}_T^\bm{x}\big)
\end{align}$$注意到:
$$\begin{align}
p \big(\mathcal{D}_{t}^z\mid \mathcal{D}_t^\bm{x}\big)=p \big(\mathcal{D}_t^\bm{x},\mathcal{D}_{t}^z \big)\big/p \big(\mathcal{D}_t^\bm{x}\big)\propto p \big(\mathcal{D}_t^\bm{x},\mathcal{D}_{t}^z \big)
\end{align}$$相差一个常数 $ p \big(\mathcal{D}_t^\bm{x}\big)$,通过直接优化完全数据集会简化问题。我们选择最大化下式:
$$\begin{align}
\max_{\mathcal{D}_t^z} p\big(\mathcal{D}_t^\bm{x},\mathcal{D}_t^z\big)
=\max_{\mathcal{D}_t^z}\left[ p\big(z_1\big)p\big(\bm{x}_1\mid z_1\big)\bigg[\prod_{\tau=2}^tp\big(z_\tau\mid z_{\tau-1}\big)p\big(\bm{x}_\tau\mid z_\tau\big)\bigg]\right]\\
\end{align}$$其中完全数据集的概率 $\displaystyle \pi[i_1]\rho_1[i_1]\cdot\prod_{t=2}^T \bigg[A_t[i_{t-1},i_{t}]\cdot \rho_t[i_t]\bigg]$,写成对数形式有:
$$\begin{align}
\ln\pi[i_1]+\ln\rho_1[i_1]+\sum_{t=2}^T \bigg[\ln A_t[i_{t-1},i_{t}]+\ln \rho_t[i_t]\bigg]
\end{align}$$这个形式有利于我们着手分析。

二、前向计算

我们可以拆分隐变量数据集 $ \mathcal{D}_t^z=\mathcal{D}_{t-1}^z\cup \{z_t\}$,拆分的关键直觉是时刻 $ t$的最可能路径必须有是由时刻 $ t-1$的最可能路径组成。问题变为
$$\begin{align}
\max_{\mathcal{D}_t^z} p\big(\mathcal{D}_t^\bm{x},\mathcal{D}_t^z\big)
=\max_{z_t}\max_{\mathcal{D}_{t-1}^z} p \big(\mathcal{D}_{t-1}^z,z_t, \mathcal{D}_t^\bm{x}\big)
\end{align}$$追寻这一关键思想,下面来具体化:我们假设 $ t$时刻的状态为 $ i_t$,进而定义路径$ \mathcal{D}_t^z=\mathcal{D}_{t-1}^z\cup \{z_t=i_t\}$的最大概率(权重):

$$\begin{align}
\delta_t[i_t]=\max_{\mathcal{D}_{t-1}^z} p \big(\mathcal{D}_{t-1}^z,z_t=i_t, \mathcal{D}_t^\bm{x}\big)
\end{align}$$为了充分利用隐马尔可夫模型的条件独立性质和动态规划思想,假设 $ t-1$的状态为 $ i_{t-1}$。继续拆分数据集于是有:
$$\begin{align}
\delta_{t}[i_t]
&=\max_{\mathcal{D}_{t-1}^z} p \big(\mathcal{D}_{t-1}^z,z_t=i_t, \mathcal{D}_t^\bm{x}\big)\\
&=\max_{\mathcal{D}_{t-2}^z,z_{t-1}=i_{t-1}}\left[ p\big(z_1\big)p\big(\bm{x}_1\mid z_1\big)\bigg[\prod_{\tau=2}^tp\big(z_\tau\mid z_{\tau-1}\big)p\big(\bm{x}_\tau\mid z_\tau\big)\bigg]\right]\\
&=\max_{i_{t-1}}\bigg[p\big(z_t=i_t\mid z_{t-1}=i_{t-1}\big)p\big(\bm{x}_t\mid z_t=i_t\big)\max_{\mathcal{D}_{t-2}^z} p \big(\mathcal{D}_{t-2}^\bm{x},\mathcal{D}_{t-1}^z,z_{t-1}=i_{t-1}\big)\bigg]\\
&=\max_{i_{t-1}} \delta_{t-1}[i_{t-1}]A[i_{t-1},i_t]\rho_t[i_t]\\
\end{align}$$也就是说:时刻 $ t$行至状态 $ i_t$的最可能路径必须有是由时刻 $ t-1$ 行至其他状态 $ i_{t-1}$的最可能路径组成。
$$\begin{align}
\delta_{t}[i_t]=\max_{i_{t-1}}\delta_{t-1}[i_{t-1}]A[i_{t-1},i_t] \rho_t[i_t]
\end{align}$$定义初始状态 $ \delta_1[i_1]=\pi[i_1]\rho_1[i_1]$。利用这公式,已知观测变量数据集 $ \mathcal{D}_T^\bm{x}$,可以求时刻 $ t$状态为 $ i_t$的最大概率,有
$$\begin{align}
\bm{\delta}_1,\cdots,\bm{\delta}_t,\cdots,\bm{\delta}_T
\end{align}$$

三、后向回溯

回到我们的问题:已知观测变量数据集,推断隐变量数据集。最大化联合概率问题变为

$$\begin{align}
\max_{\mathcal{D}_T^z} p\big(\mathcal{D}_T^\bm{x},\mathcal{D}_T^z\big)
=\max_{i_T}\max_{i_{T-1}}A[i_{T-1},i_t] \rho_T[i_T]\cdots\max_{i_1}\delta_1[i_1]A[i_{1},i_2] \rho_2[i_2]
\end{align}$$这样一种转换称为 max-product操作。

为了解决这个问题,回顾动态规划思想:最优路径 $ \hat{\mathcal{D}}_{1:T}^z$的一部分 $ \hat{\mathcal{D}}_{t:T}^z$对于 $ t:T$的所有可能路径 $ \mathcal{D}_{t:T}^z$必然是最优。如果存在另外一条路径 $ \tilde{\mathcal{D}}_{t:T}^z$是最优的,那么会出现矛盾 $ \hat{\mathcal{D}}_{1:t}^z\cup \tilde{\mathcal{D}}_{t:T}^z\neq \hat{\mathcal{D}}_{1:T}^z $,所以 $ \hat{\mathcal{D}}_{t:T}^z$ 必须是最优的。根据这一思想,我们定义回溯操作 traceback: $ \omega_t[\cdot]$,来从后向前还原最优状态序列。
$$\begin{align}
\hat{z}_{t-1}=\omega_t[i_t]=\mathop{\mathrm{argmax}}_{i_{t-1}}\,\delta_{t-1}[i_{t-1}]A[i_{t-1},i_t] \rho_t[i_t]
\end{align}$$定义 $ T$时刻最优状态 $\displaystyle \hat{z}_{T}=\mathop{\mathrm{argmax}}_{i_T}\,\delta_T[i_T]$。应用回溯操作,得到最优路径:
$$\begin{align}
\hat{\mathcal{D}}_{T}^z=\{\hat{z}_{t-1}=\omega_t[\hat{z}_{t}]\}_{t=T}^1
\end{align}$$

为了解决数据下溢问题,我们可以取对数
$$\begin{align}
&\ln\delta_{t}[i_t]
=\max_{i_{t-1}}\big[\ln\delta_{t-1}[i_{t-1}]+\ln A[i_{t-1},i_t] +\ln\rho_t[i_t]\big]\\
&\hat{z}_{t-1}=\omega_t[i_t]=\mathop{\mathrm{argmax}}_{i_{t-1}}\,\big[\ln\delta_{t-1}[i_{t-1}]+\ln A[i_{t-1},i_t] +\ln\rho_t[i_t]\big]
\end{align}$$


算法:维特比算法


$1\displaystyle \bm{\delta}_1=\bm{\pi}^\text{T}\bm{A}$
$2\displaystyle \text{ for }\,t=2:T$
$\displaystyle
\quad\begin{array}{|lc}
\text{ for }\,i_{t}=1:K \\
\quad\begin{array}{|lc}
\displaystyle \big[\ln\delta_t[i_t],\omega_{t-1}[i_t]\big]=\max_{i_{t-1}}\ln \bm{\delta}_{t-1}\odot \ln\bm{A}+\bm{I}\ln B_{t}[i_{t},x_t]\big]
\end{array}\\
\text{ end}\\
\end{array}
$
3end
$\displaystyle [\ln\delta_T,\hat{z}_{T}]=\max_{i_T}\,\ln\bm{\delta}_T$
$4\displaystyle \text{ for }\,t=T:2$
$\displaystyle
\quad\begin{array}{|lc}
\hat{z}_{t-1}=\omega_{t}[\hat{z}_{t}]
\end{array}
$
5end
$6\displaystyle \hat{\bm{z}}$

四、评述

1、在切分数据集后,同过充分利用隐马尔可夫模型的条件独立假设,我们得到迭代方程和回溯方程。

$$\begin{align}
&\delta_{t}[i_t]
=\max_{i_{t-1}}\delta_{t-1}[i_{t-1}]A[i_{t-1},i_t] \rho_t[i_t]\\
&\hat{z}_{t-1}=\omega_t[i_t]=\mathop{\mathrm{argmax}}_{i_{t-1}}\,\delta_{t-1}[i_{t-1}]A[i_{t-1},i_t] \rho_t[i_t]
\end{align}$$
2、使用 max-product,我们认识到寻找最优隐状态序列问题是个动态规划问题。
3、然后很自然,使用动态规划,解决了问题。


版权声明
引线小白创作并维护的柠檬CC博客采用署名-非商业-禁止演绎4.0国际许可证。
本文首发于柠檬CC [ http://www.limoncc.com ] , 版权所有、侵权必究。
本文永久链接http://www.limoncc.com/机器学习/2018-01-09-隐马尔可夫模型的维特比算法/

予汝玫瑰,渡人沃土。