机器学习 - 隐马尔可夫模型

作者: nlpming | 来源:发表于2020-06-26 12:27 被阅读0次

马尔科夫模型的几个子模型
HMM隐马尔可夫模型概述
统计学习方法——修炼学习笔记10：隐马尔可夫模型
贝叶斯公式和隐马尔可夫模型(完结篇)
隐马尔科夫模型（1）基本概念和概率计算
【机器学习实践】隐马尔可夫模型（一）
机器学习 - 隐马尔可夫模型
第七章数据预测与估算算法——基于隐马尔可夫模型预测
matlab中的隐马尔可夫模型(HMM)实现
马尔可夫链和隐马尔可夫模型

1 隐马尔可夫模型 - 定义

隐马尔可夫模型（hidden markov model, HMM）是可用于标注问题 [自动分词、词性标注、命名实体识别等] 的统计学习模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型；
隐马尔可夫模型定义如下：隐马尔可夫模型是一种有向概率图模型。描述由一个隐藏的马尔科夫链生成不可观测的状态随机序列（状态序列，state sequence），再由各个状态序列生成一个观测从而产生观测随机序列（观测序列，observation sequence）的过程。

2 隐马尔可夫模型 - 用于中文分词

2.1 中文分词例子

输入：我想去乌鲁木齐
输出：我/S 想/S 去/S 乌/B 鲁/M 木/M 齐/E

注意： B表示一个词的开始；M表示一个词的中间；E表示一个词的结尾；S表示单独成词；

2.2 中文分词 - 问题建模

$x$ 表示输入的将要分词的句子（观测序列）；
$y$ 表示输出的句子分词结果（状态序列）；
中文分词问题就是：给定 $x$ 的情况下，找到一个 $y$ 使得条件概率 $p(y|x)$ 最大化；

隐马尔可夫模型，使用贝叶斯公式将条件概率 $p(y|x)$ 的求解问题，转换成对联合概率 $p(x,y)$ 的求解：
$\begin{align} \hat{y} &= \mathop{\arg\max}_{y} p(y|x) \\ &= \mathop{\arg\max}_{y} \frac{p(x,y)}{ p(x)} \\ &= \mathop{\arg\max}_{y} p(x,y) \end{align}$
注意： $x$ 是给定的，因此对于任意的 $y$ 而言 $p(x)$ 都是一样的；

2.3 隐马尔可夫模型三要素

观测序列（待分词的句子）： $x_1, x_2, ..., x_L$ ；
状态序列（分词结果）： $y_1, y_2, ..., y_L$ ；
观测空间 $\mathcal{X}$ ，表示所有可能的观测集合；即中文中所有可能的词，大小为 $M$ ；
状态空间 $\mathcal{ Y}$ ，表示所有可能的状态集合；即分词标签 $B, M, E, S$ ，大小为 $N$ ；
初始概率分布 $\pi \in \mathbb{R}^{ 1 \times N }$ ： $p(y_1 | start)$ ；
发射概率分布 $B \in \mathbb{R}^{ N \times M }$ ： $p(x_l | y_l)$ ；
转移概率分布 $A \in \mathbb{ R}^{ (N+1) \times (N+1) }$ ： $p(y_{l+1} | y_l)$ ；包含一个结束符 $end$ ；
隐马尔可夫模型： $\lambda = (A, B, \pi)$

隐马尔可夫模型.png

3 隐马尔可夫模型 - 两个基本假设

齐次马尔科夫假设： 即假设隐藏的马尔可夫链在任意时刻 $t$ 的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关；
$p(y_t|y_{t-1}, x_{t-1}, ..., y_1, x_1) = p(y_t|y_{t-1})$

观测独立性假设： 即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关；
$p(x_t|y_T, x_T, y_{T-1}, x_{T-1}, ..., y_1, x_1) = p(x_t|y_t)$

4 隐马尔可夫模型 - 3个基本问题

概率计算问题： 给定模型 $\lambda = (A, B, \pi)$ 和观测序列 $x_1, x_2, ..., x_L$ ，计算在模型 $\lambda$ 下观测序列 $x$ 出现的概率 $p(x | \lambda)$ ；

学习问题： 已知观测序列 $x_1, x_2, ..., x_L$ ，估计模型 $\lambda = (A, B, \pi)$ 参数，使得在该模型下序列概率 $p(x | \lambda)$ 最大；

预测问题： 也称为解码问题。已知模型 $\lambda = (A, B, \pi)$ 和观测序列 $x_1, x_2, ..., x_L$ ，求对给定观测序列条件概率 $p(y | x)$ 最大的状态序列 $y_1, y_2, ..., y_L$ 。即给定观测序列，求最有可能对应的状态序列；

4.1 概率计算问题

可使用前向（forward）、后向（backward）算法计算 $p(x | \lambda)$ ；为后续学习问题做铺垫；

4.2 学习问题

隐马尔可夫模型的学习，根据训练数据是包括 观测序列 和对应的 状态序列 还是只有观测序列，可以分别由 监督学习 与 无监督学习 实现；

4.2.1 监督学习方法

使用极大似然估计法来估计隐马尔可夫模型的参数。

转移概率 $p(y_{l+1} | y_l)$ 的估计：
$p(y_{l+1} | y_l) = \frac{Count(y_l, y_{l+1}) }{ Count(y_l) }$

发射概率 $p(x_l | y_l)$ 的估计：
$p(x_l | y_l) = \frac{ Count(x_l, y_l) }{ Count(y_l) }$

初始概率 $p(y_1 | start)$ 的估计：Count(start)，训练语料总数；
$p(y_1 | start) = \frac{ Count(start, y_1) }{ Count(start) }$

4.2.2 无监督方法 [Baum-Welch 算法]

由于监督学习需要使用标注的训练数据，而人工标注训练数据往往代价很高，有时就会利用无监督学习方法；
隐马尔可夫模型实际上是一个含有隐变量的概率模型： $p(x|\lambda) = \sum_y {logp(x|y, \lambda) p(y|\lambda)}$ 它的参数学习可以由 EM算法 实现。

4.3 预测问题

HMM模型问题定义如下，找出 $\hat{y}$ 使得联合概率 $p(x,y)$ 最大化； 最直观的思路是穷举所有可能的 $y$ ，但是时间复杂度为 $O(N^L)$ ；一般使用viterbi算法求解，其时间复杂度为 $O(L \times N^2)$ ；
$\begin{align} \hat{y} &= \mathop{\arg\max}_{y} p(y|x) \\ &= \mathop{\arg\max}_{y} \frac{p(x,y)}{ p(x)} \\ &= \mathop{\arg\max}_{y} p(x,y) \end{align}$
隐马尔可夫的预测问题，一般使用维特比算法求解。维特比算法实际是动态规划（Dynamic Programming）解隐马尔可夫模型预测问题，即用动态规划求概率最大路径（最优路径）。这时一条路径对应着一个状态序列。
维特比算法解HMM预测问题：

输入：模型 $\lambda = (A, B, \pi)$ 和观测 $X=(x_1, x_2, ..., x_L)$ ；
输出：最优路径 $Y^* = (y_1^*, y_2^*, ..., y_L^*)$ ；
（1）初始化
$\begin{align} \delta_1(i) &= \pi_i b_i(x_1), \quad i=1,2,...,N \\ \Psi_1(i) &= 0, \quad i=1,2,...,N \end{align}$
（2）开始递推，对 $l = 2,3,...,L$ ；注意： $a_{ji}$ 表示转移概率， $b_i(x_l)$ 表示发射概率；
$\begin{align} \delta_l(i) &= \max_{1 \leq j \leq N} \left[ \delta_{l-1}(j) a_{ji} \right] b_i(x_l), \quad i=1,2,...,N \\ \Psi_l(i) &= \arg\max_{1 \leq j \leq N} \left[ \delta_{l-1}(j) a_{ji} \right], \quad i=1,2,...,N \end{align}$
（3）终止
$\begin{align} P^* &= \max_{1 \leq i \leq N} \delta_L(i) \\ y_L^* &= \arg\max_{1 \leq i \leq N}\delta_L(i) \end{align}$
（4）最优路径回溯，对 $l = L-1, L-2,..., 1$
$y_l^* = \Psi_{l+1}(y_{l+1}^*)$
求得最优路径： $Y^* = (y_1^*, y_2^*, ..., y_L^*)$

4.3.1 HMM预测过程例子

隐马尔可夫模型的三个概率矩阵如下：

HMM三个概率矩阵.png

Viterbi算法解码过程：维特比算法时间复杂度为： $O(L \times N^2)$
维特比算法.png

5. HMM算法总结

HMM算法总结如下：
（1）HMM对联合概率进行建模： $F(x,y) = P(x,y) = p(y)p(x|y)$ ；
（2）HMM inference目标为： $\hat{y} = \mathop{\arg\max}_{y} p(x,y)$ ；
（3）HMM参数估计 $p(y), p(x|y)$ ：可以采用简单的统计方法，或者采用无监督式的方式使用EM算法学习网络参数；
HMM的缺点：HMM算法并不一定能够保证 $p(x,\hat{y}) > p(x,y)$ ；
HMM算法缺点.png

参考资料

《统计学习方法》- 李航
结构化预测 - 序列标注，[李宏毅，机器学习2016] https://www.bilibili.com/video/BV1Ux411S7Yk?p=24
李宏毅，机器学习2016 - 课程主页 http://speech.ee.ntu.edu.tw/~tlkagk/courses_ML16.html
如何通俗地讲解 viterbi 算法？https://www.zhihu.com/question/20136144

马尔科夫模型的几个子模型
马尔可夫链（MC）：机器学习隐马尔可夫模型（HMM）：机器学习马尔科夫决策过程（MDP）：强化学习 MDP见：...
HMM隐马尔可夫模型概述
隐马尔可夫模型隐马尔可夫模型（hidden Markov model， HMM）适用于标注问题的统计学习模型，描...
统计学习方法——修炼学习笔记10：隐马尔可夫模型
一、隐马尔可夫模型的基本概念 1、隐马尔可夫模型定义隐马尔可夫模型是关于时序的模型，描述由一个隐藏的马尔可夫链随...
贝叶斯公式和隐马尔可夫模型(完结篇)
隐马尔可夫模型隐马尔可夫模型或称作隐性马尔可夫模型，是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其...
隐马尔科夫模型（1）基本概念和概率计算
隐马尔科夫模型 HMM 本文我们介绍一个机器学习中常用的模型————隐马尔科夫模型（Hidden Markov M...
【机器学习实践】隐马尔可夫模型（一）
隐马尔可夫模型隐马尔可夫链模型 Hidden Markov Model 首先应当了解马尔科夫链[https:/...
机器学习 - 隐马尔可夫模型
1 隐马尔可夫模型 - 定义隐马尔可夫模型（hidden markov model, HMM）是可用于标注问题 ...
第七章数据预测与估算算法——基于隐马尔可夫模型预测
7.5 基于隐马尔可夫模型预测基于隐马尔可夫模型是一种概率统计模型，实质是一种隐藏状态马尔可夫模型，在一般的马尔...
matlab中的隐马尔可夫模型(HMM)实现
原文链接：http://tecdat.cn/?p=7960 隐马尔可夫模型（HMM）简介隐马尔可夫模型（HMM）...
马尔可夫链和隐马尔可夫模型
马尔可夫模型可以分为四种：马尔可夫链、隐马尔可夫模型、马尔可夫决策过程和部分可观测马尔可夫过程 [1]。其中马尔可...

机器学习 - 隐马尔可夫模型

1 隐马尔可夫模型 - 定义

2 隐马尔可夫模型 - 用于中文分词

2.1 中文分词例子

2.2 中文分词 - 问题建模

2.3 隐马尔可夫模型三要素

3 隐马尔可夫模型 - 两个基本假设

4 隐马尔可夫模型 - 3个基本问题

4.1 概率计算问题

4.2 学习问题

4.2.1 监督学习方法

4.2.2 无监督方法 [Baum-Welch 算法]

4.3 预测问题

4.3.1 HMM预测过程例子

5. HMM算法总结

参考资料

相关文章

马尔科夫模型的几个子模型

HMM隐马尔可夫模型概述

统计学习方法——修炼学习笔记10：隐马尔可夫模型

贝叶斯公式和隐马尔可夫模型(完结篇)

隐马尔科夫模型（1）基本概念和概率计算

【机器学习实践】隐马尔可夫模型（一）

机器学习 - 隐马尔可夫模型

第七章数据预测与估算算法——基于隐马尔可夫模型预测

matlab中的隐马尔可夫模型(HMM)实现

马尔可夫链和隐马尔可夫模型

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读