深度学习 （七）Hidden Markov Model

Summary

自 learner 开始学习算法以来就时常听说这一算法, 今天抽空我们进行了系统性探讨. 将 HMM 归类的话, 则属于概率图模型(PGM)范畴. 从字面意义上看, PGM结合了概率论与图论的知识体系, 可以把概率与图结合起来形成一种新的数据结构用于解决复杂的问题. 在处理复杂性和不确定性问题方面展现了显著的优势, 而今这一技术已在图像处理、视频分析等领域取得了广泛的应用. 而今天我们将要探讨的概率模型正是 HMM 的一种类型. 另外还有一种叫做贝叶斯网络的概率模型, 关于这部分内容我们稍后再进行介绍.

theory foundation

随机过程是依赖于参数的一族随机变量的全体，参数通常是时间维度，随机变量呢即某一现象的体现，如我们每天吃的食物的多少，今天吃了1kg明天如果饿可能吃1.5kg，我们把随时间变化的量抽象出来即随时间变化的一组随机变量，也成为随机过程，这个方向的研究产生于20世纪末，那么这一研究的价值在哪里呢？
在研究随机过程时人们透过表面的偶然性描述出必然的内在规律并以概率的形式来描述这些规律，从偶然中悟出必然正是这一学科的魅力所在。

Markov process

这次我们选择了大家都能参与的股票作为例子，在研究随机过程时通常会给每个可能的事件赋予相应的概率值。我们需要关注的是某一特定事件发生与否的概率分布情况，在大多数情况下我们可以将这些特殊的问题转化为普通的数学问题来处理。然而，在某些特殊情况下这些转化并不成立或者难以实现，则需要采用更为复杂的理论模型来解决这些问题。特别地，在俄国数学家马尔科夫提出的一种特殊假设下，在这种情况下他假设当前状态的概率分布仅受其前一状态的影响而不受其他历史状态的影响。他的这种假设后来被推广并发展成为一种重要的理论模型——马尔可夫链。

以后人们就称具有这种性质的过程为马尔科夫过程。

Hidden Markov Model

举网友常用来说明的例子。为了简化起见，在此我们假定天气状况仅有雨天（rainy）和晴朗（sunny）两种情况。将这些天气状况视为一个由不同状态构成的状态集合，在某个系统中通常会发生各种随机事件。我们可以将这种现象通常被归类为马尔可夫过程。这种现象仅受昨日天气的影响而不受历史天气的影响。为此我们可以用S₁和S₂来表示这两个具体的状态。这些数值所组成的集合即被称为状态空间。马尔可夫过程的一个关键特性即当前的状态St仅与其前一时刻的状态St-₁相关联而不受其先前的历史信息如St-₂等任何其他信息的影响：如上

基于马尔可夫原理的基础上展开讨论。具体阐述其定义内容包括两个主要部分: π代表的状态序列初始概率分布和转移矩阵A所描述的状态转换关系。其中, π不仅决定了系统的起始分布,还直接关联着整个系统的演化过程。而矩阵A则详细刻画了系统在任意两个连续时刻之间的转换规律,其中每一个元素a_ij都代表着从第i个当前状态转移到第j个下一时刻的状态的概率值。

在实际问题中我们通常无法直接观察到隐含状态但在某些情况下可以通过这些隐含状态推断出一些事件发生的概率例如在购买日常用品时居家男人经常需要外出购买一些基本生活物资如大米、蔬菜、食用油等一类商品。假设今天下雨的话这位居家男人可能会选择外出购买这些东西而不是前往工作单位继续工作下去。无论是雨天还是晴天的情况都有可能发生这三件事而这三件事及其对应的概率已经建立好了如下图所示：

观察上图可知存在两个状态序列：一个是隐藏的马尔科夫过程 S = {S(rainy), S(sunny)} ，另一个则是可观察的状态序列集合 O = {O(sport), O(shop), O(work)} 。两者之间存在概率关联性，并伴有相应的概率矩阵。通常我们称这类包含一个隐马尔科夫过程及其相关联的概率模型为隐马尔科夫模型（HMM）。其主要目标则是利用观测数据推断隐藏状态及其转移规律。

Two hypothesis

该假设主要关注于隐式状态序列，在其发生与否上仅受前一状态的影响，并不受更早的状态影响；这正是马尔科夫特性

• 观察状态独立假设*
  第二个假设指出观察序列彼此之间相互独立。具体而言，在每一个时间步长t中, 每个观测变量仅与其对应的潜在变量相关联, 而与其他潜在变量无关。

Definition

一个 HMM 模型可以用一个5元组 { N, M, π，A，B } 表示，其中：

• N 隐藏状态的数量
  表示隐藏状态的数量，可能知道也可能不知道

• M 观测状态的数量
  表示可观测状态的数量，可以通过训练集获得

• π={πi} 初始状态概率
  代表的是刚开始的时候各个隐藏状态的发生概率；

• A={aij}表示隐藏状态的转换表
  该矩阵是N×N维的，并即其元素描述了从一个状态到另一个状态的概率；

B = {bij} 作为混淆矩阵使用
该混淆矩阵为 N \times M 大小的矩阵，在隐马尔可夫模型中表示处于某一特定隐状态条件下某观测事件发生的概率
其状态转移概率以及混淆度的概率值均为常数，在系统演化的过程中不随时间变化而改变。当隐马尔可夫模型中隐状态的数量N和观测空间的维度M固定时，则可以用参数集 \lambda = \{\pi, A, B\} 来描述该模型的基本结构参数

Three Question

evaluation（the probability of the observation）

该问题是基于已知的模型相关参数的问题。我们需要求取得到当前观测序列的概率是多少？通过解决这一问题的方法论框架，则可检验我们所观察到的概率结果是否准确。解决一般有三种方法。

iteration

此算法即用于计算产生观测序列的可能性数量，在该例子中观测序列为t=1、t=2、t=3三个时刻的状态，则每个时刻隐含的状态有两种可能性，则总共有2^3=8种可能的情况；当隐含的状态数量较多时会导致计算负担加重；由此可知，在工程实践中应用此算法将面临较大的计算压力

forward algorithm

该算法属于前向计算方法，在时间序列上从t=1依次进行运算直至最后一个观测序列，在此过程中避免重复运算以提高运算效率

根据图示，在运算t=3时, 可以通过将t=2时刻的结果带入来方便地得到结果. 该算法基于两个假设: 隐层的状态仅受前一状态的影响; 而当前的观测序列仅受当前隐含状态的影响.

recognition（corresponding state sequence）

此类问题是常见的一种方法，并非唯一的方式。很多问题都是基于可观察序列来识别隐含状态序列的模式和关系。例如，在语音识别、模式识别等领域中都可用这种猜测隐含状态的方式来实现对目标信息的解析和转换过程。通过查看图表持续进行文字解码过程以获取更多的信息和内容

Viterbi （dynamic programming）

动态规划是一种解决最优化问题的有效技术，
由美国数学家Bellman提出，
它特别适用于那些可以通过分解为子问题来求解全局最优的问题，
并且能够通过递推关系式来描述各个子问题的状态转移，
从而实现对整体最优解的求取。
Viterbi算法是动态规划的一个典型应用实例，
以天气状态为例说明：
已知的是观察序列以及各个概率参数，
我们需要分析随着时间t的变化趋势，
找出产生最大概率的隐含状态序列。
维特比算法的具体过程如下：
当时间步长为1时，
我们在计算两种可能性的概率时分别得到了如图所示的结果，
并从中提取出最大值并将其结果进行缓存以便后续步骤使用。

按上图可以一次计算出来t=2时 取哪个隐含状态概率最大，t=3 ,t=n等

用动态规划即要抽象出来公式，如下：

核查相关公式时，请将t值设为2进行计算。对于上图中的公式而言，则需要明确i和j各自所处的状态空间范围。

在上图所示的过程中存在大量重复计算的情况，通过缓存技术来减少冗余计算以提高效率；同时该方法在解决多种实际问题时展现出显著的有效性

training（adjust the model parameters）

这一问题最为复杂，在各种模型中进行参数训练的问题通过优化使我们的模型达到最优状态。而这种优化又分为两种情形。

通过观察一系列观测数据以及相应的状态信息, 我们能够推导出一系列参数表达式, 并按照最大似然准则进行求解

• 状态序列未知
  大致流程是假设另一个模型参数，在此算法中采用Baum-Welch辅助韦尔奇方法来计算两个模型参数的期望值，在每次迭代中逐步优化使期望最大化；而新估计的模型参数逐渐收敛；在训练过程中通常需要较多数量的数据样本；先不做详细说明。

应用

到目前为止, 它一直被视为解决各类自然语言处理问题最有效的方案, 并成功应对了语音识别、词性标注等难题, 其重要性无可置疑.
通信的本质是一个编码与解码以及信息传递的过程, 大家可以参考吴军老师《数学之美》第五章对隐马模型的具体阐述.

• 词性标注

• 语音识别

随笔

维特比算法
安德鲁维特比发明了维特比算法，并且创办了高通公司，它是通信领域应用最广泛的解码技术，将解码复杂度降低万倍，使得解码真正得到实施和应用，它是现在计算法传输上网等的基础，意义推动了互联网发展。
声波处理步骤一般分为三步
1.抽取特征 去燥
2.将特征转换为音节
3.音节解码为语句
维特比做的事情主要在第三步将音节字符转为语句，人们可以理解的自然语言文本或声音。
汉语二义性会有很多歧义，造成解码困难主要是计算量太大，指数爆炸，维特比是将音节看做隐含序列，将对应的语句看做是状态序列，并根据时间从t=1时逐渐解码知道句子长度，t=n,为止，大致和上述类似。