哈工大SCIR原创

2019/04/19 19:03

哈工大SCIR硕士生乐远作者

隐马尔可夫模型 | 赛尔笔记

隐马尔可夫模型(HMM)是可用于标注问题的统计学习模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。

说到隐马尔可夫模型(HMM)，我们先来了解下马尔可夫模型(Markov模型)，Markov模型是一种统计模型，广泛地应用在语音识别，词性自动标注，音字转换，概率文法等各个自然语言处理的应用领域。

一. 马尔可夫模型(Markov模型)

设是随机变量序列，其中每个随机变量的取值在有限集，称为状态空间。Markov特征是：

有限历史假设

时间不变性

如果具有这些特征，那么这个随机变量序列称为一个马尔可夫过程（链）。

Markov的形式化表示：一个马尔可夫模型是一个三元组，其中是状态的集合，是初始状态的概率，是状态间的转移概率。具体例子用图形表示如下，

相应的分别是，

最简单的情形：不同的状态只能有不同的输出，

增加一点灵活性：不同的状态，可以输出相同的输出，

再增加一点灵活性：输出在状态转移中进行，

最大的灵活性：在状态转移中以特定的概率分布输出，

二. 隐马尔可夫模型(HMM)

1.HMM的形式化定义

HMM是一个五元组，其中是状态的集合，是输出字符的集合，是初始状态的概率，是状态转移的概率, 是状态转移时输出字符的概率。

一个HMM的例子用图形表示如下，

2. 隐马尔可夫模型的三个基本问题

评估问题：给定一个模型，如何高效地计算某一输出字符序列的概率？
解码问题：给定一个输出字符序列，和一个模型，如何确定产生这一序列概率最大的状态序列？
学习问题：给定一个输出字符的序列，如何调整模型的参数使得产生这一序列的概率最大?

3. 评估问题的解法

已知，，计算？我们先来化简一下，

方案一：直接计算法

穷举所有可能的的情况，求和得到，但是时间复杂度太高，为。

方案二：前向算法(Forward algorithm)

方案三：向后算法(backward algorithm)

同样的道理，我们定义在时刻状态为的条件下，从到的部分观测序列为的概率为后向概率，记作，即

直接采用递推即可得到后向算法。

后向算法过程如下,

1. 初始化

2. 推导

3. 总和

4. 解码问题的解法

给定一个输出字符序列，和一个模型，如何确定产生这一序列概率最大的状态序列？

即

我们定义表示为在时刻到达状态，输出字符时，输出前面个字符的最可能路径的概率，

则有

这样我们就得到了维特比算法(Viterbi Algorithm)，算法过程如下：

5. 学习问题解法

隐马尔可夫模型的学习，根据训练数据是包括观测数据和对应的状态序列还是只有观测序列，可以分为有监督学习和无监督学习，其中无监督的学习即是利用EM算法思想的Baum-Welch算法。

方案一：有监督学习

假设训练数据包含个长度相同的观测序列和对应的状态序列，那么可以利用极大似然估计法来估计隐马尔可夫模型的参数，具体估计方法如下：

1. 转移概率的估计

设样本中时刻处于状态时刻处于状态的频数为，那么状态转移概率的估计是

2. 观测概率的估计

设样本中状态为并观测为的频数是，那么状态为观测为的概率的估计是

3. 初始状态概率的估计为个样本中初始状态为的概率

由于监督学习的方法需要使用训练数据，而人工标注的代价往往很高，有时会采用非监督学习的方法。

方案二：无监督学习——Baum-Welch算法

假设给定的训练数据只包含个长度为的观测序列而没有对应的状态序列，目标是学习隐马尔可夫模型的参数。我们将观测序列数据看做观测数据，状态序列数据看做不可观测数据，那么隐马尔可夫模型事实上是一个包含隐变量的概率模型

它的参数学习可以由EM算法实现。

（算法推导过程）

(1) 确定完全数据的对数似然函数所有观测数据写成，所有的隐数据写成，完全数据是。完全数据的对数似然函数是。
(2) EM算法的E步：求函数的。
其中是隐马尔可夫模型参数的当前估计值，是要极大化的隐马尔可夫模型参数。因为，
所以函数可以拆分写成
式中求和都是对所有训练数据的序列总长度进行的。
(3) EM算法的M步：极大化函数，求模型参数。
由于要极大化的参数在函数式子中单独的出现在三个项中，所以只需要对各项分别极大化。第一项可以写成，
注意到满足，利用拉格朗日乘子法，写出拉格朗日函数
对其求导数并令结果为0，
得到
对求和得到,
再代入上式子得到，
第二项可以写成
类似于第一项，利用具有约束条件的拉格朗日乘子法恶意求出
第三项可以写成，
同样利用拉格朗日乘子法，约束条件是，注意只有在时对的偏导数才不为0，以表示，得到，
-----
为了简便，我们使用一下式子简化，给定模型和观测，在时刻处于状态的概率记
有如下公式：
给定模型和观测，在时刻处于状态的概率记 :
有如下推倒：
我们结合上文以及EM算法可以推导如下公式

Baum-Welch算法过程：

输入：观测数据；

输出：隐马尔可夫模型参数。

1. 初始化。对，选取得到模型

2. 递推。对

3. 终止。得到模型参数

哈工大SCIR

哈尔滨工业大学社会计算与信息检索研究中心

理论马尔可夫链隐马尔可夫模型生成模型马尔可夫模型

相关数据

非监督学习技术

非监督式学习是一种机器学习的方式，并不需要人力来输入标签。它是监督式学习和强化学习等策略之外的一种选择。在监督式学习中，典型的任务是分类和回归分析，且需要使用到人工预先准备好的范例(base)。一个常见的非监督式学习是数据聚类。在人工神经网络中，自组织映射（SOM）和适应性共振理论（ART）则是最常用的非监督式学习。

来源：Wikipedia

动态规划技术

动态规划（也称为动态优化），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划将复杂的问题分解成一系列相对简单的子问题，只解决一次子问题并存储它的解决方案（solution），下一次遇到同样的子问题时无需重新计算它的解决方案，而是简单地查找先前计算的解决方案，从而节省计算时间。动态规划适用于有最优子结构（Optimal Substructure）和重叠子问题（Overlapping Subproblems）性质的问题。

来源：Wikipedia

维特比算法技术

维特比算法（英语：Viterbi algorithm）是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。术语“维特比路径”和“维特比算法”也被用于寻找观察结果最有可能解释相关的动态规划算法。例如在统计句法分析中动态规划算法可以被用于发现最可能的上下文无关的派生（解析）的字符串，有时被称为“维特比分析”。

来源：维基百科

参数技术

在数学和统计学裡，参数（英语：parameter）是使用通用变量来建立函数和变量之间关系（当这种关系很难用方程来阐述时）的一个数量。

来源：维基百科

时间复杂度技术

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。

来源：维基百科

概率分布技术

概率分布（probability distribution）或简称分布，是概率论的一个概念。广义地，它指称随机变量的概率性质－－当我们说概率空间中的两个随机变量具有同样的分布（或同分布）时，我们是无法用概率来区别它们的。

来源：维基百科

统计模型技术

统计模型[stochasticmodel；statisticmodel；probabilitymodel]指以概率论为基础，采用数学统计方法建立的模型。有些过程无法用理论分析方法导出其模型，但可通过试验测定数据，经过数理统计法求得各变量之间的函数关系，称为统计模型。常用的数理统计分析方法有最大事后概率估算法、最大似然率辨识法等。常用的统计模型有一般线性模型、广义线性模型和混合模型。统计模型的意义在对大量随机事件的规律性做推断时仍然具有统计性，因而称为统计推断。常用的统计模型软件有SPSS、SAS、Stata、SPLM、Epi-Info、Statistica等。

来源：百度百科

导数技术

导数（Derivative）是微积分中的重要基础概念。当函数y=f(x)的自变量x在一点x_0上产生一个增量Δx时，函数输出值的增量Δy与自变量增量Δx的比值在Δx趋于0时的极限a如果存在，a即为在x0处的导数，记作f'(x_0) 或 df(x_0)/dx。

来源：百度百科

监督学习技术

监督式学习（Supervised learning），是机器学习中的一个方法，可以由标记好的训练集中学到或建立一个模式（函数 / learning model），并依此模式推测新的实例。训练集是由一系列的训练范例组成，每个训练范例则由输入对象（通常是向量）和预期输出所组成。函数的输出可以是一个连续的值（称为回归分析），或是预测一个分类标签（称作分类）。

来源：Wikipedia

马尔可夫模型技术

「马尔可夫模型」是指基于马尔可夫性质的模型，其假设一个给定过程的未来状态仅取决于当前状态。根据系统状态是否完全可被观测以及系统是自动的还是受控的，可以将常见的马尔可夫模型分成四种：马尔可夫链、隐马尔可夫模型（HMM）、马尔可夫决策过程（MDP）和部分可观测马尔可夫决策过程（POMDP）。另外还有马尔可夫随机场（MRF）和马尔可夫链蒙特卡洛（MCMC）这两个模型也常常被用于近似和预测。

来源：机器之心

语音识别技术

自动语音识别是一种将口头语音转换为实时可读文本的技术。自动语音识别也称为语音识别(Speech Recognition)或计算机语音识别(Computer Speech Recognition)。自动语音识别是一个多学科交叉的领域，它与声学、语音学、语言学、数字信号处理理论、信息论、计算机科学等众多学科紧密相连。由于语音信号的多样性和复杂性，目前的语音识别系统只能在一定的限制条件下获得满意的性能，或者说只能应用于某些特定的场合。自动语音识别在人工智能领域占据着极其重要的位置。

来源：What is Automatic Speech Recognition?

隐马尔可夫模型技术

隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。

来源：维基百科

似然函数技术

在数理统计学中，似然函数是一种关于统计模型中的参数的函数，表示模型参数中的似然性。似然函数在统计推断中有重大作用，如在最大似然估计和费雪信息之中的应用等等。“ 似然性”与“或然性”或“概率”意思相近，都是指某种事件发生的可能性，但是在统计学中，“似然性”和“或然性”或“概率”又有明确的区分。

来源：维基百科

自然语言处理技术

自然语言处理（英语：natural language processing，缩写作 NLP）是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言；自然语言认知则是指让电脑“懂”人类的语言。自然语言生成系统把计算机数据转化为自然语言。自然语言理解系统把自然语言转化为计算机程序更易于处理的形式。

来源：维基百科

生成模型技术

在概率统计理论中, 生成模型是指能够随机生成观测数据的模型，尤其是在给定某些隐含参数的条件下。它给观测值和标注数据序列指定一个联合概率分布。在机器学习中，生成模型可以用来直接对数据建模（例如根据某个变量的概率密度函数进行数据采样），也可以用来建立变量间的条件概率分布。

来源：维基百科

隐变量技术

在统计学中，隐变量或潜变量指的是不可观测的随机变量。隐变量可以通过使用数学模型依据观测得的数据被推断出来。

来源：维基百科

马尔可夫链技术

马尔可夫链，又称离散时间马尔可夫链，因俄国数学家安德烈·马尔可夫得名，为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。

来源：维基百科