机器学习——隐马尔科夫(HHM)原理

机器学习——隐马尔科夫(HHM)模型原理

1 从马尔科夫模型到隐马尔科夫模型

1.1 马尔科夫过程引入

首先，我们先给出一张图：

在上面的图里，给出的是一个链式的结构，结构中的每一个节点称之为一个状态。每一个状态$Q_i$的取值是一个范围$[S_0,S_n]$，我们称之为状态空间。并且，每一个状态$Q_i$的取值与之前状态的取值有关。也就是说$Q_i$在状态空间的和$Q_1,Q_2,..Q_{i-1}$的取值有关。我们将这种状态随着时间向前推进，状态的取值与之前状态的取值有关的过程称为马尔科夫随机过程。我们用概率来表示一下这个过程就是：
$P(Q_i=S_i)=P(Q_i=S_j|Q_1=S_i∈[S_0,S_n],Q_2=S_i∈[S_0,S_n],...,Q_{i-1}=S_i∈[S_0,S_n])$

其中$Q_{i-1}=S_i∈[S_0,S_n]$表示状态$Q_i$的取值$S_i$属于样本空间的某一个。现在我们做出一个强假设，假设当前状态的取值仅仅和前一个状态的取值有关。用公式表示就是：
$P(Q_i=S_i)=P(Q_i=S_j|Q_{i-1}=S_i∈[S_0,S_n])$
我们将其称为一阶马尔科夫过程。如果状态空间$S_i$是离散的值，我们就称其为离散的一阶马尔科夫过程。

或许上面的描述过于抽象化，下面我们举一个例子来解释这个过程,假设有如下三个状态和状态转移矩阵：
首先，我们假设状态空间为$[S_1,S_2,S_3]$

状态S₁：名词（N）
状态S₂：动词（V）
状态S₃：形容词（adj）

假设状态$Q_1$的取值为$S_1$,状态$Q_2$的取值为$S_2$,状态$Q_3$的取值为$S_3$,状态$Q_4$的取值为$S_3$,那么我们现在要确定$Q_5$为状态的$S_1$的概率就是：
$P(Q_5=S_1)=P(Q_5=S_j|Q_1=S_1,Q_2=S_2,Q_{3}=S_3,Q_4=S_3)$

下面，我们在具有给出一个状态转移的矩阵

$\left[ \begin{matrix} &S_1&S_2&S_3\\ S_1&0.3 & 0.5 & 0.2 \\ S_2&0.5 & 0.3 & 0.2\\ S_3&0.4 & 0.2 & 0.4 \\ \end{matrix} \right]$
转移矩阵的概念是，从某一个状态$S_i$转移到另外一个状态$S_j$的概率。在我们上面的式子中：
$P(Q_5=S_j)=P(Q_5=S_j|Q_1=S_1,Q_2=S_2,Q_{3}=S_3,Q_4=S_3)$
假设$Q_1$状态的是确定的$S_1$，那么从状态值$S_1$转移的到$Q_2$对应的状态值$S_2$的概率为0.5，同理从$S_2$转移到$Q_3$状态的状态值$S_3$的概率为0.2，从$S_3$转移到$Q_4$状态的状态值$S_3$的概率为0.4，则
$P(Q_5=S_1)=P(Q_5=S_j|Q_1=S_1,Q_2=S_2,Q_{3}=S_3,Q_4=S_3)\\ =0.5*0.2*0.4$

如果是一阶马尔科夫过程，并且已经确定了$Q_4=S_3$，则可以确定概率为：
$P(Q_5=S_j)=P(Q_5=S_j|Q_4=S_3)=0.4$

1.2、 隐马尔科夫模型

在上述马尔科夫模型中，每一个状态的代表的是一个可以直接观察的事件(比如，上面的每个状态对应的是一个的词性)。在隐马尔科夫模型中,我们不能知道模型所经过的状态序列，只知道状态转移的概率函数。同时，对于这个状态所产生的事件也是一个随机的函数。还是上面的例子。现在已知的是状态S₁，S₂，S₃转移的概率。但是对于每一个状态的S_i，其可以产生多个多种词性。即
状态S₁：名词（N）、动词（V）、形容词（A）
状态S₂：名词（N）、动词（V）、形容词（A）
状态S₃：名词（N）、动词（V）、形容词（A）
HMM的转移过程如图所示：

在这里，我们把由各个状态产生的实际O称为可观测序列。

在HMM模型中，当计算到某一个事件序列产生的概率的时候，我们至少需要到三个部分，第一个部分是初始状态的概率，第二个是状态之间转移的概率，第三个是有状态产生事件的概率。对于以上三个部分，我们分别使用$π，A，B$三个矩阵来表示。那么也就是说，一个常规的隐马尔科夫练可以表示为：
$\{π，A，B\}$

2 HMM模型推导过程

对于HMM模型的求解过程，通常是从三个问题开始的，我们下面分别对这三个问题进行一一的推导和求解。

2.1 估计问题

2.1.1 问题描述

给定一个观察序列$O=\{O_1,O_2,...O_T\}$和HMM模型$μ=\{π，A，B\}$，如何计算观察序列O的概率？
对于这个问题，首先我们要明确的是对于每一个可以观测的数据而言，其可以用任何一个状态S_i来生成。

2.1.2 问题推导

对于第一个可以观测的数据$O_1$而言，整个模型生成$O_1$的概率是各个状态生成$O_1$的概率之和。也就是$∑_{Q_1=S_1}^{S_{p}}b_{Q_1}(j)$，同时由于模型是以一定的概率来生成初始状态$Q_1$的，那么也就是说，整个模型生成第一个可观测元素的概率为：
$P(O_1|μ)=∑_{Q_1=S_1}^{S_{p}}π(Q_1)*B_{Q_1}(O_1)$

对于可观测序列的第二个元素$O_2$而言，首先是由第一个状态$Q_1$转移到第二个状态$Q_2$，在有状态$Q_2$来生成的。由于状态$Q_2$的取值范围是$\{S_0,S_1,...S_{p-1}\}$，那么，有状态$Q_2$生成可以观测的元素$O_2$的概率就是各个状态生成$O_2$的概率和，用数学表达式表示就是：
$∑_{Q_2=S_1}^{S_{p}}b_{Q_2}(j)$。

同时，我们还需要考虑到的时，$Q_2$是由$Q_1$转移过来的。那么，我们就必须要考虑到状态转移的概率。对于$Q_2$状态的任意一个取值$S_i$而言，产生这个状态的概率是由$Q_1$的任意一个取值产生的，那么模型产生$S_i$的概率，就为：
$∑_{Q_1=S_1}^{S_{p}}π(Q_1)A_{Q_1S_i}$

则，由状态$Q_1$转移到状态$Q_2$的概率为：
$∑_{Q_1=S_1}^{S_{p}}π(Q_1)∑_{Q_2=S_1}^{S_{p}}A_{Q_1Q_2}$

则，由μ生成可观测元素$O_1,O_2$的概率为：
$∑_{Q_1=S_1}^{S_{p}}π(Q_1)B_{Q_1}(O_1)∑_{Q_2=S_1}^{S_{p}}A_{Q_1Q_2}B_{Q_2}(O_2)$

依次类推，可观测序列的第三个元素$O_3$产生的概率也是首先状态$Q_3$的所有的取值$S_i$生成$O_3$的概率和，同时考虑从状态$Q_1,Q_2$转移到$Q_3$的概率，就可以推导出产生$O_1,O_2,O_3$的概率为：
$∑_{Q_1=S_1}^{S_{p}}π(Q_1)B_{Q_1}(O_1)∑_{Q_2=S_1}^{S_{p}}A_{Q_1Q_2}B_{Q_2}(O_2)∑_{Q_3=S_1}^{S_{p}}A_{Q_2Q_3}B_{Q_3}(O_3)$

不断递推之后，我们可以知道生成整个序列的概率为：
$∑_{Q_1=S_1}^{S_{p}}π(Q_1)B_{Q_1}(O_1)∑_{Q_2=S_1}^{S_{p}}A_{Q_1Q_2}B_{Q_2}(O_2).....∑_{Q_T=S_1}^{S_{p}}A_{Q_{T-1}Q_T}B_{Q_T}(O_T)$

上面的递推公式我们可以很容易的就确定。但是，这里存在的问题在于，如果我们想要获得观测序列的概率值，我们就必须穷尽所有的状态序列。也就是$(p)^T$。为了更好的解决这个问题，提出了前向算法，过程描述如下：
首先定义：
$α_t(i)=P(O_1,O_2,...O_t,Q_t=S_i|μ)$

该公式主要描述的是假设已经通过μ生成了{$O_1,O_2,...O_{t-1}$}的观测序列，同时在t时刻转移到$S_i$状态，并由$S_i$状态生成$O_t$的概率值。

当第一个时刻的时候有：

$α_1(i)=P(O_1,Q_1=S_i|μ)=π(S_i)B_i(O_1)$

同理我们可以定义出t+1时刻：
$α_{t+1}(j)=P(O_1,O_2,...O_t,O_t,Q_{t+1}=S_j|μ)$

进一步，我们可以推导出
$α_{t+1}(j)=P(O_1,O_2,...O_t,O_{t+1},Q_{t+1}=S_j|μ)=∑_{i=1}^pα_t(i)A_{ij}B_j(O_{t+1})$

根据递推公式，我们可以确定最后一个时刻T的时候，有：
$α_{T}(j)=P(O_1,O_2,...O_T,Q_{T}=S_j|μ)=∑_{i=1}^pα_{T-1}(i)A_{ij}B_j(O_{T})$

最后，对与整可观测序列的概率，就是对于各个$α_{T}(j)$求和，用公式表达就是：
$P(O|μ)=∑_{j=1}^pP(O_1,O_2,...O_T,Q_{T}=S_j|μ)=∑_{j=1}^Pα_{T}(j)$

我们用一个图来描述一下上面的过程：

前一列是t时刻所有可能的状态$S_i$，后一列是t+1时刻的$S_j$状态。也就是我们在计算t+1时刻的$S_j$状态的时候，已经考虑到了t时刻的所有状态。

2.1.3 算法过程

1. 初始化第一个时刻的α，也就是：
   $α_1(i)=P(O_1,Q_1=S_i|μ)=π(S_i)B_i(O_1)$
2. 归纳计算
   $α_{t+1}(j)=P(O_1,O_2,...O_t,O_{t+1},Q_{t+1}=S_j|μ)=∑_{i=1}^pα_t(i)A_{ij}B_j(O_{t+1})$
3. 最后求和
   $P(O|μ)=∑_{j=1}^pP(O_1,O_2,...O_T,Q_{T}=S_j|μ)=∑_{j=1}^Pα_{T}(j)$

2.2 最优序列

2.2.1 问题描述

我们知道，每一个可以观测的元素是由一个状态生成的，在已知观测序列和HMM模型的条件下，我们应该如何选择一个最优的状态序列，使得由该状态序列生成的可观测序列的概率最大？用数学的形式描述就是：

$max E(Q)=max(π(S_{Q1})B_{S_{Q1}}(O_1)A_{Q_1Q_2}B_{S_{Q2}}(O_2)A_{Q_2Q_3}).....A_{Q_{T-1}Q_T}B_{S_{Q_T}}(O_T))$

对于每一个$Q_i$可以取状态空间S中的某一个状态。

2.2.2 问题推导

对于求解这个问题，我们采用的是维特比算法，其数学推导过程如下：
首先，我们给出如下的递推公式：
$δ_t(i)=max(P(Q_1,Q_2,....Q_{t-1},Q_t=S_i,O_1,O_2,...O_t))$
我们来简单的解释以下这个公式，这个公式的意义在于在t时刻的时候，当该时刻取状态$S_i$的时候能够获取到的关于可观测的序列的最大概率。如下图所示：

如上图所示，前面的一列是t-1时刻的可能取的所有状态，后一列是t时刻的j状态，对于j状态而言，可以由前一个时刻的可以取的任意一个状态转移过来，上述的公式的作用就是用来寻找概率最大的状态。图中所示的就是$S_2$。

在了解了上述公式的意义之后，我们开始逐步的递推，在这里，我们新增加一个函数用来回溯：
首先是第一步：
$δ_1(i)=π(S_i)B_{S_i}(O_1)$
$Ψ_1(i)=0,i∈[1,p]$
然后是第二步：
$δ_2(j)=max(δ_1(i)A_{S_iS_j}B_{S_j}(O_2)),i∈[1,p]$
$Ψ_2(j)=max(δ_1(i)A_{S_iS_j}),i∈[1,p]$
依次类推到第t+1步为：
$δ_{t+1}(j)=max(δ_t(i)A_{S_iS_j}B_{S_j}(O_{t+1})),i∈[1,p]$
$Ψ_{t+1}(j)=max(δ_t(i)A_{S_iS_j}),i∈[1,p]$
到最后一步的时候：
$δ_{T}(j)=max(δ_{t-1}(i)A_{S_iS_j}B_{S_j}(O_{T})),i∈[1,p]$
$Ψ_{T}(j)=max(δ_{t-1}(i)A_{S_iS_j}),i∈[1,p]$
最后，我们找到概率最大的一条状态链为：
$max E(Q)=max(δ_{T}(j))，j∈[1,p]$

2.2.3 算法描述

1. 初始化：
   $δ_1(i)=π(S_i)B_{S_i}(O_1)$
   $Ψ_1(i)=0,i∈[1,p]$
2. 归纳计算：
   $δ_{t+1}(j)=max(δ_t(i)A_{S_iS_j}B_{S_j}(O_{t+1})),i∈[1,p]$
   $Ψ_{t+1}(j)=max(δ_t(i)A_{S_iS_j}),i∈[1,p]$
3. 获取最大路径：
   $δ_{T}(j)=max(δ_{t-1}(i)A_{S_iS_j}B_{S_j}(O_{T})),i∈[1,p]$
   $Ψ_{T}(j)=max(δ_{t-1}(i)A_{S_iS_j}),i∈[1,p]$
   $max E(Q)=max(δ_{T}(j))，j∈[1,p]$
4. 路径回溯
   $Q_t=Ψ_{t+1}(Q_{t+1})$

2.3 参数估计问题

2.3.1 问题描述

给定可观测序列$O_1,O_2,...O_T$，如何确定HMM模型中的参数π，A，B来使得产生可观测序列的概率最大？

2.3.2 问题推导

我们首先给出两个定义：

$θ_t(i)=P(O_1,O_2,...O_t,Q_t=S_i|μ)$
$β_t(i)=P(O_{t+1},O_{t+1},...O_T|Q_t=S_i,μ)$

根据上面的定义，我们可以确定的是：
$β_T(i)=1, i∈[1,p]$
$β_t(i)=∑_{j=1}^pA_{ij}β_{t+1}(j)B_j(O_{t+1}),t∈[1,T-1]$

1. 首先，我们随机化HMM的参数π，A
2. 然后我们计算：
   $ξ_t(i,j)=P(Q_t=S_i,Q_{t+1}=S_j|O,μ)=θ_t(i)A_{ij}β_{t+1}(j)B_j(O_{t+1})$
   进一步推导之后有：
   $ξ_t(i,j)=\frac{P(Q_t=S_i,Q_{t+1}=S_j,O|μ)}{P(O|μ)}=\frac{θ_t(i)A_{ij}β_{t+1}(j)B_j(O_{t+1})}{P(O|μ)}\\ =\frac{θ_t(i)A_{ij}β_{t+1}(j)B_j(O_{t+1})}{∑_{i=1}^p∑_{j=1}^pθ_t(i)A_{ij}B_j(O_{t+1})β_{t+1}(j)}$

则定义：
$γ_t(i)=P(Q_t=S_i,O|μ)=∑_{j=1}^pξ_t(i,j)$
3. 根据上面的计算，我们可以计算出：
$π(S_i)=γ_1(i)$
$A_{ij}=\frac{∑_{t=1}^{T-1}ξ_t(i,j)}{∑_{t=1}^{T-1}γ_t(i)}$
4. 对于B矩阵的计算可以采用的是
$B_j(O_k)=\frac{∑_{t=1}^Tγ_t(j)*δ_t(O_k)}{∑_{t=1}^Tγ_t(j)}$

3、总结

在明确了HMM模型的三个问题之后，我们就可以根训练数据来训练HMM的相关参数π，A，B。对于测试数据而言，根据维特比算法，可以确定最优的状态转移序列和整个序列的概率值。

3.1 参考文献

1. 浙江大学《机器学习》
2. 宗成庆 《统计自然语言处理》

转载：https://blog.csdn.net/hei653779919/article/details/104227688