隐马尔科夫模型

隐马尔科夫模型是一种可用于标记的模型，属于生成模型。主要包括概率计算问题、学习问题以及预测问题，其算法广泛应用于语音识别、自然语言处理、生物信息等等。

基本概念

隐马尔可夫的定义

隐马尔科夫模型是关于时序的概率模型，描述又一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成对应的观测而产生观测随机序列的过程。其中，随机生成的状态构成状态序列，对应的随机观测构成观测序列。
设Q施所有可能状态的集合，V是所有可能的观测的集合：

$$Q=\{q_1, q_2, ..., q_N\}, V=\{v_1, v_2, ..., v_M\}$$

其中N和M代表各自集合的大小。
I是长度为T的状态序列，O是其对应的观测序列：

$$I=(i_1, i_2, ..., i_T), O=(o_1, o_2, ..., o_T)$$

A为状态转移概率矩阵：

$$A={[a_{ij}]}_{N\times{N}}$$

其中，$a{ij}=P(i{t+1}=q_j|i_t=q_i), i=1,2,…,N; j=1,2,…,N$是时刻t处于状态$q_i$的条件下在时刻$t+1$转移到状态$q_j$的概率
B为观测概率矩阵：

$$B={[b_j(k)]}_{N\times{M}}$$

其中，$b_j(k)=P(o_t=v_k|i_t=q_j), k=1,2,…,M; j=1,2,…,N$是在时刻t处于状态$q_j$的条件下生成观测$v_k$的概率。
$\pi$为初始状态概率向量：

$$\pi=(\pi_i)$$

其中，$\pi_i=P(i_1=q_i), i=1,2,…N$是时刻$t=1$处于状态$q_i$的概率。
通常A，B和$\pi$足以表示一个隐马尔科夫模型，我们用$\lambda$表示：

$$\lambda=(A, B, \pi)$$

在下文中，如无特殊说明，则相关变量如$\lambda$的定义将如上。

基本假设

1. 齐次马尔科夫假设
2. 观测独立性假设

观测序列的生成算法

输入：$\lambda$以及序列长度T
输出：观测序列$O=(o_1, o_2, …, o_T)$

1. 由$\pi$产生状态$i_1$
2. 令t=1
3. 按照状态$i_t$的观测概率分布$b_it(k)$生成$o_t$。
4. 按照状态$it$的状态转移概率分布 ${a{iti{t+1}}}$产生状态$i_{t+1}$。
5. 令t=t+1，如果t<T，回到第三步，否则终止。

隐马尔科夫模型的三个问题

隐马尔科夫模型通常有三类问题，接下来的章节也将介绍这几类问题的对应算法。

1. 概率计算问题
2. 学习问题
3. 预测问题

概率计算问题

给定$\lambda$和O，计算观测序列O出现的概率$P(O|\lambda)$。
通常有前向算法和后向算法，两者过程相反，但原理相同。

前向算法

前向概率的定义

给定$\lambda$，以及到t时刻为止的观测序列O以及t时刻的状态$q_i$，则前向概率为：

$$\alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda)$$

算法

输入：$\lambda$, 观测序列O
输出：$P(O|\lambda)$

1. 初值$\alpha_1(i) = \pi_i b_i(o_i), i=1,2,…,N$
2. 递推，对$t=1,2,…,T-1, \alpha{t+1}(i)=[\sum{j=1}^{N}{\alphat(j)a{ji}}]bi(o{t+1}), i=1,2,…,N$
3. 终止，$P(O|\lambda)=\sum_{i=1}^{N}{\alpha_T(i)}$

后向算法

后项概率的定义

给定$\lambda$，以及从t+1时刻到T的观测序列O以及t时刻的状态$q_i$，则后向概率为：

$$\beta_t(i)=P(o_{t+1},o_{t+2},...,o_T,i_t=q_i|\lambda)$$

算法

输入：$\lambda$, 观测序列O
输出：$P(O|\lambda)$

1. 初值$\beta_T(i) = 1, i=1,2,…,N$
2. 递推，对$t=T-1,T-2,…,1, \betat(i)=[\sum{j=1}^{N}{a{ij}b_j(o{t+1})\beta_{t+1}(j)}], i=1,2,…,N$
3. 终止，$P(O|\lambda)=\sum_{i=1}^{N}{\pi_ib_i(o_1)\beta_1(i)}$

一些概率与期望的计算

给定模型$\lambda$和观测O，在时刻t处于状态$q_i$的概率，记为：

$$\gamma_t(i)=P(i_t=q_i|O,\lambda)$$

则

$$\gamma_t(i)= = \frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^{N}{\alpha_t(j)\beta_t(j)}}$$

给定模型$\lambda$和观测O，在时刻t处于状态$q_i$且在时刻t+1处于状态$q_j$的概率。记为：

$$\xi(i,j)=P(i_t=q_i,i_{t+1}=q_i|O,\lambda)$$

则

$$\xi(i,j)=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum_{i=1}^{N}{\sum_{j=1}^{N}{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}}}$$

其他一些期望值：

• 在观测O下状态i出现的期望值：$\sum{t=1}^{T}{\gamma{t}(i)}$
• 在观测O下由状态i转移的期望值：$\sum{t=1}^{T-1}{\gamma{t}(i)}$
• 在观测O下由状态i转移到状态j的期望值：$\sum_{t=1}^{T-1}{\xi_t(i,j)}$

学习问题

给定观测序列O，估计模型$\lambda$的参数，使得$P(O|\lambda)$最大，即用极大似然估计的方法估计参数。

分为有监督学习和无监督学习

有监督学习

极大似然估计

1. 估计转移概率$a_{ij}$
2. 估计观测概率$b_j(k)$
3. 估计初始状态概率$\pi_i$

无监督学习 Baum-Welch算法

输入：观测数据O
输出：模型参数$\lambda$

1. 初始化。对n=0，选取$a_{ij}^{(0)}$，$b_j(k)^{(0)}$，$\pi_i^{(0)}$，得到模型$\lambda^{(0)}=(A^{(0)}, B^{(0)}, \pi^{(0)})$。
2. 递推。对n=1,2,…, $$a_{ij}^{(n+1)} = \frac{\sum_{t=1}^{T-1}{\xi_{t}(i,j)}}{\sum_{t=1}^{T-1}{\gamma_t(i)}}$$ $$b_j(k)^{(n+1)} = \frac{\sum_{t=1,o_t=v_k}^{T}{\gamma_t(j)}}{\sum_{t=1}^{T}{\gamma_t(j)}}$$ $$\pi_i^{(n+1)}=\gamma_1(i)$$ 右端各值按观测$O=(o_1,o_2,…,o_T)$和模型$\lambda^{(n)} = (A^{(n)}, B^{(n)}, \pi^{(n)})$计算。
3. 终止。得到模型参数$\lambda^{(N+1)}=(A^{(N+1)}, B^{(N+1)}, \pi^{(N+1)})$。

预测问题

给定$\lambda$和O，求最有可能的对应状态序列I。

近似算法

每个时刻t选择最有可能的状态$i_t^{*}$，由此构成状态序列。

维特比算法

首先定义两个变量：

• 定义在时刻t状态为i的所有单个路径$(i_1, i_2, …, i_t)$中概率最大值为 $$\delta_t(i) = \max_{i_1,i_2,...,i_{t-1}}{P(i_t=i,i_{t-1},...,i_1,o_t,...,o_1|\lambda)}, i=1,2,...N$$ 其中，其递推式为 $$\delta_{t+1}(i) = \max_{1\le{j}\le{N}}{[\delta_t(j)a_{ji}]}b_i(o_{t+1}), i=1,2,...,N; t=1,2,...,T-1$$
• 定义在时刻t状态为i的所有单个路径中概率最大的路径的第t-1个结点为 $$\phi_t(i)=arg\,\max_{1\le j\le N}{\delta_{t-1}(j)a_{ji}}$$

算法
输入：$\lambda$和观测O
输出：最优路径$I^*$

1. 初始化。 $$\delta_1(i)=\pi_i b_i(o_1), i=1,2,...,N$$ $$\phi_1(i)=0, i=1,2,...,N$$
2. 递推。对t=2,3,…,T，应用递推公式求解$\delta_t(i)$和$\phi_t(i)$。
3. 终止 $$P^*=\max_{1\le i\le N}{\delta_T(i)}$$ $$i_{T}^{*}=arg\,\max_{1\le i\le N}{\delta_T(i)}$$
4. 最优路径回溯。对t=T-1,T-2,…,1， $$i_t^*=\phi_{t+1}(i_{t+1}^{**})$$ 求得最优路径$I^*$。