隐马尔科夫链模型(HMM)学习

2018/11/09 Machine Learning

隐马尔可夫模型(Hidden Markov Model, HMM)是一个广泛应用的统计分析模型。应用于语音识别,行为识别,文字识别及故障诊断等领域。平时在看论文时总能涉及到HMM的相关讨论,一直只了解个大概,这次在调研异常检测算法时发现有基于HMM的算法,趁此机会深入了解一下。

马尔可夫链

个人感觉翻译成“马尔可夫”比“马尔科夫”好听一些。

马尔科夫链是满足马尔可夫性质的随机过程。该过程中,每个状态的转移只依赖于之前的 n 个状态,这个过程被称为1个 n 阶的模型,其中 n 是影响转移状态的数目。最简单的马尔科夫过程就是一阶过程,每一个状态的转移只依赖于其之前的那一个状态。注意这和确定性系统不一样,因为这种转移是有概率的,而不是确定性的。 马尔可夫性质可以写作恒等式:

即某个状态的取值只依赖于前一个状态。

马尔可夫链的核心是一个状态转移矩阵P,其中$P_{ij}$是指从状态i转到状态j的概率。马尔可夫链有一个特别有意思的性质,即无论初始状态是什么,经过N次状态转移后,马尔可夫链状态变量的分布会收敛到一个平稳分布,称为马尔可夫收敛定理。马尔可夫链收敛的充要条件(细致平稳条件)是:

  1. 可能的状态是有限的
  2. 转移概率矩阵固定不变
  3. 能从任意状态转移到任意状态
  4. 不是简单循环,例如不会能全是从A到B再从B到A

证明过程略。用图片的例子,任意赋予状态变量一个分布,比如我们刚开始都没吃过三家店,所以分布是均匀分布,经过N次状态转移后,“晚上吃啥”这一变量则一定收敛到符合一个只和转移矩阵相关的分布。有点小神奇。马尔可夫收敛定理的一大应用就是MCMC,这个方法解决了贝叶斯估计中困扰多年的高维求解问题,有机会另外论述。

隐马尔可夫模型

隐马尔可夫模型,其实就是将马尔可夫链中的状态设置为不可观测的隐含状态,而我们可观测到的状态都是由某个隐含状态概率生成的。也就是说,如果我们观测到了一组符合隐马尔可夫模型的观测序列,那么每个观测值背后都有一个隐含状态,这些隐含状态则组成了一个马尔可夫链(观测状态集合隐含状态集的大小可以不同)。

还是举晚饭的例子,假设小李每天晚上只吃{好口福,新奇特,徽湘菜}这三个饭店,且小李每天吃完饭后会出现这几种状态{健康,不舒服,拉肚子,食物中毒},我们想构造出类似上图的一个隐马尔可夫模型,现在已经有了状态转移矩阵,那么还需要知道什么呢?就是观测状态的概率分布,每个隐藏状态对应的概率分布肯定是不同的,好口福比较干净,所以概率分布大概会是(0.7, 0.2, 0.09, 0.01);新奇特有色素饮料,所以概率分布大概为(0.5, 0.3, 0.15, 0.05), 随后我们把所有的隐含状态-观测状态概率分布组合成一个矩阵,我们成为混淆矩阵。现在还剩下一个问题,就是第一个隐含状态是怎么来的,所以我们还需要一个初始状态概率$\pi$,现在我们就可以用一个三元组来表示HMM了,即$\lambda={\pi,A,B}$,求HMM的模型时实际就是求着三个参数。

三个假设

对于HMM来说,有如下三个假设,其实这些假设都是不现实的,我们只是尽量的去近似真实情况。

假设1:马尔可夫假设(状态构成一阶马尔可夫链)

假设2:不动性假设(状态与具体时间无关)

假设3:输出独立性假设(输出仅与当前状态有关)

三个问题

在HMM中有三个典型问题:

评估问题(Evaluation):已知模型参数$\lambda$和给定观察状态序列$O$,求出现这一序列的概率

当给出多个HMM模型时,可通过这个问题根据观察序列找出最好的模型
解决方案:前向算法

解码问题(Decoding):已知模型参数$\lambda$和给定观察状态序列$O$,求一个最可能的隐含状态序列$X$

这个问题是我们大部分时间的需求,在晚饭的例子中就是知道连续8天小李吃完饭的状态,求这8天小李最可能吃了啥
解决方案:Viterbi算法

学习问题(Learning):已知观察状态序列$O$,求一个最可能的隐马尔可夫模型$\lambda$

这个问题相当于模型的训练,已知只有一组观察序列,正如其他学习问题一样,训练数据有限的情况下,没有任何一种方法可以精确的找到一组最优的参数$\lambda$使$P(O\,|\,\lambda)$最大,因此我们寻求一种近似的局部最优解决方法。
解决方案:Baum-Welch算法(前向后向算法)

评估问题

评估问题用前向算法解决。前向算法参考的是动态规划的思路,因为第i+1个观测值出现的概率是由第i个观测值的概率得到的,求序列$O_1,…,O_T$的概率可分解为子问题“求序列$O_1,…,O_{T-1}$的概率”。

如果我们知道隐含状态序列X,则O的概率很好算,因为概率间不相关,顺着链连乘即可

暴力求解的想法是,枚举所有可能的隐含状态,相加即为所求

由于X序列有$N^T$种可能,所以这种方法的复杂度是O(N^T),N是隐含状态集合大小,显然太高了。

前向算法引入了前向变量$\alpha_t(i)$,即在t时刻,序列O中$O_t$对应的隐含状态是$S_i$的概率(S为隐含状态集)

假设有三个隐含状态,先算t=1时刻

当t=2时,先假设对应的隐含状态是1,可得

所以

以此类推可以得到整个序列O的概率$P(O_1,…,O_T)$,时间复杂度为$O(N^2T)$

解码问题

解码问题用Viterbi算法解决。Viterbi算法其实也是一种动态规划的思想,整体思路和前向算法基本相同,都是把问题规模逐层减小。其实所有寻找带权有向无环图中多步骤多选择的最优路径问题都可以通过Viterbi解决。用正向迭代的思路就是每步都甄选从开始到当前代价最(或最大)小的走法,计算完所有步骤后通过回溯找到最佳路径。

Viterbi算法引入了部分概率$\delta_t(i)$,即在t时刻到达状态i的所有可能路径中概率最大的那一条的概率。这个部分概率和前向算法中的前向变量时不一样的,这里的概率是一个最可能路径的概率,而前向变量表示的是所有路径的概率和。

依然假设有三个隐含状态,先算t=1时刻,此时到每个状态的最大可能路径就是$\pi$

当t=2时,再来计算每个状态的部分概率,对于每个状态来说,有三条路径可以到达,如果最终的路径包括了自己,那么它一定要选择三条中概率最大的一条来保证路过自己的路径是最大的。由于马尔可夫假设,当前状态只跟前一个状态有关,所以有

为了记录路径,我们还需要一个变量$\phi_t(i)$来记录取得最大概率时的前一个隐含状态。如此迭代,直到t=T,最后

然后根据路径变量回溯即可找到最终的最大可能路径X。算法的复杂度和前向算法类似,为$O(N^2T)$

学习问题

学习问题用Baum-Welch算法,又称前向后向算法。学习问题其实就是$\lambda={\pi, A, B}$的参数估计,而且是没有标注也就是HMM隐含状态序列未知的参数估计问题,所以得到的隐含状态有时候没有显性的解释,通常情况我们也不太关心隐含状态的意义。含有隐变量的参数估计的一个经典解决方案就是EM算法,其实,Baum-Welch算法就是EM算法的一种特例,他避免了EM算法的暴力计算,而采用动态规划思想减轻计算量。这里不讲从EM算法推算的思路,只讲Baum-Welch算法的思路。

回顾前向算法的前向变量$\alpha_t(i)$,我们同样定义后向变量$\beta_t(i)$

我们可以很容易发现

(后向变量同样可以迭代快速求出)因此有

再定义给定模型$\lambda$和观测序列$O$,在时刻t处于状态$S_i$的概率$\gamma$

很容易看出

在定义给定观察序列$O$及隐马尔科夫模型$\lambda$,定义t时刻位于隐藏状态$S_i$及t+1时刻位于隐藏状态$S_j$的概率变量为$\xi$

同样,该变量也可以用前向变量和后向变量表示

上述两个变量间的关系是

由此我们可以根据定义得到一些有用的期望:

在观测$O$下状态$S_i$出现次数的期望值

解释:$\gamma_t$是t时刻出现$S_i$的概率,那T次出现的期望即为求和

在观测$O$下由状态$S_i$转移次数的期望值

解释:因为T时刻的状态为当前状态,是由前一次的状态转移过来的,所以对前T-1次求期望即为前一次状态为$S_i$的期望

在观测$O$下由状态$S_i$转移到状态$S_j$次数的期望值

解释:同上,只有T-1次转移的机会


然后我们终于可以用这些来估计HMM的参数值了

$\pi$是t=1是状态$S_i$的期望次数

$A$是$S_i$到$S_j$的转移期望除以$S_i$的总转移期望

$B$是在状态$S_j$下观测到观察状态$K$的期望次数除以$S_j$的总期望次数

所以Baum-Welch算法的E步就是用模型参数$\lambda$计算新的$\gamma$和$\xi$,M步就是用新的$\gamma$和$\xi$根据上述式子重新估计$\lambda$,直到模型收敛。在第一次迭代时需要随意给定模型参数的初始值。

应用

HMM最成功的应用就是在语音识别领域,我们听到的声音模式可以作为观测状态,而背后的真实文本信息是隐含状态,文本词与词之间大致符合马尔科夫链模型,文本到观测语音也大致符合独立的概率分布,因此整体符合HMM模型。我们即可以先通过语音来建模,这是一个学习问题,再通过语音和模型来预测最可能的文本,这是一个解码问题。在其他领域,比如生物信息,图像识别,手势识别,用户行为分析,故障诊断,股票预测中都有应用,想想符合HMM模型的事物还真挺多的。

Search

    Table of Contents