NLP学习笔记33-HMM

一序本文属于贪心NLP训练营学习笔记。本节课开始学习HMM。二时序类模型常见时序类模型的场景：（沿着时间的维度在变化的，而且数据之间有一定相关性，时间长度不固定）1股票价格、语音、文本，温度的变化。HMM / CRF <= traditional method 传统RNN / LSTM <= deep learning 深度学习三模型介绍z是状态值（隐式），x是观测值（已知），对

bohu83

659人浏览 · 2021-03-13 11:42:09

bohu83 · 2021-03-13 11:42:09 发布

一序

本文属于贪心NLP训练营学习笔记。本节课开始学习HMM。

二时序类模型

常见时序类模型的场景：（沿着时间的维度在变化的，而且数据之间有一定相关性，时间长度不固定）

1股票价格、语音、文本，温度的变化。

HMM / CRF <= traditional method 传统
RNN / LSTM <= deep learning 深度学习

三模型介绍

z是状态值（隐式），x是观测值（已知），对应不同时间t有不同的值。是有有方向的、生产模型。

既可以看做判别模型，也可以看做生成模型。

例子：扔不均匀硬币

现在有两个硬币A和B，它们出现正面的概率分别是 $\large \mu _1,\mu _2$ ,让叫小明的人丢硬币，而我只能看到丢的结果，不知道丢的是A还是B。

针对这个例子，我们现在有几个问题：

问题1（inference/decoding问题）：通过观测到的正反面，小明丢硬币的序列是什么？
问题2（parameter estimate问题）： $\large \mu _1,\mu _2$ 分别是什么？
问题3：如果计算某个观测序列出现的边界概率？例如：P(正反正正反)

Part of Speech Tagging(POS) 词性标注例子

观测到的是单词，不知道的是词性。

Q1：维特比解决

Q2：参数估计，再没有标注单词词性的情况下，使用EM算法。

Parameters of HMM : $\large \theta =(A,B,\pi )$

隐变量 $\large z_i$ 是离散型的(所有数据可以罗列出来)，类似于词性标注中的隐状态词性也是有限的。假设其隐状态有m个。

观测变量 $\large x_i$ 不限制，可以是离散型，连续型的。

看下具体的参数 $\large \theta =(A,B,\pi )$

A: transition probability 状态转移概率， $\large Z_{ij}$ 是状态 $\large Z_i$ 下一个时态转化为 $\large Z_j$ 的概率，矩阵大小是m×m

B是emission probability/matrix，就是生成概率矩阵。就在状态 $\large Z_i$ 下，生成观测变量 $\large x_i$ 的概率。矩阵大小是m×V ，V为观测变量的取值类型，举例的是单词的词典。

对于 $\large x_i$ 是连续型的（如语音的波形），是不能写成矩阵的，连续型用高斯混合模型(Gaussian Mixed Model)处理。

$\large \pi$ : 某一个状态, 在第一个位置的概率

Two Major Tasks

1. 给定模型参数theta, 找出最适合的Z (隐藏状态) Inference / Decoding

2. 估计模型的参数theta

1. complete case: 知道x,z => 最大似然估计(MLE)
2. Incomplete case: 知道x, 不知道z => EM算法

Case1 Finding best Z (维特比算法)

我们一开始先不看具体的维特比算法。遇到问题的时候，先想一个最笨的方法：

枚举所有可能的隐藏状态组合, 算出概率最高的组合

指数级的复杂度，假设z是3个可能性，序列长度是10，那么可能性就是 $\large 3^{10}$

维特比算法

对于这种指数级复杂度，使用动态规划算法，就是存储中间状态，避免重复计算。

使用维特比算法的一个前提是，某个隐式状态 $\large Z_i$ 只和它前后的状态有关，与其他状态无关。

我们是想通过已知条件 $\large \theta$ ，x来估计 $\large Z_i$ ，可以理解为下面截图的 $\large z_1$ 到 $\large z_n$ 有很多种选择。怎么求出最好的那条连线。

初始概率 $\large P(z_1=2)$ 是有 $\large \pi$ 决定的。另外还有一个因素要从 $\large z_1=2$ 状态生成观测变量 $\large x_1$ ,因此数学表达就是:

$\large P(z_1=2)\cdot p(x_1|z_1=2)$

以此类推，那么整根折线的概率就是把上面的概率连乘：

$P(z_1=2)\cdot p(x_1|z_1=2)\cdot P(z_2=1|z_1=2)P(x_2|z_2=1)...$

概率越高越好,接下来看如何用DP来简化,就是拆分成子问题来解决。

假设第k时刻，最好的概率 $\delta _k(i)$ .意思是第k时刻最好路径设置为i。

那么第k+1时刻，最好的路径是前一个状态乘上第k+1时刻的概率，加了log操作之后

$\delta_{k+1}(j) = max_i [\delta_k(i)+logP(Z{k+1}=j|Zk = i) + logP(x{k+1}|Z_{k+1}=j)]$

换句话当前时刻的best score = max(上一个时刻的best score + log当前时刻的转移概率 + log当前时刻的输出概率)

这是一个经典动态规划的场景，每次计算都可以确定出前一个时刻到当前时刻的最佳路径，这样从第一个时刻开始一次向后计算，并把路径结果保存下来就可以求出第k个时刻的最佳路径。

问题2：Forward/Backward Algorithm

这个算法是用来估计： $P(z_k|x)$ ,这个概率可以拆分为：

Forward Algorithm：计算联合概率： $P(z_k,x_{1:k})$

Backward Algorithm：计算条件概率： $P(x_{(k+1):n}|z_k)$

$P(z_k|x)=\frac{p(z_k,x) }{p(x)} \propto p(z_k,x)$ 前面用了贝叶斯定理，后面用正比于 $\propto$ 表示除以p(x) 做一个常数项

接下来看 $P(z_k,x)$ 我们用上面的前向x后向展开

$P(z_k,x)=P(x_{(k+1):n}|z_k,x_{1:k})P(z_k,x_{1:k})$ 前面哪里用了后向公式，因为x的范围1:n,前面只有 $x_{(k+1):n}$ ,所以还要补上 $x_{1:k}$ .

由于 $x_{1:k}$ 和 $x_{(k+1):n}$ 都是条件独立于 $z_k$ 的（意思是 $x_{1:k}$ 信息都包含在 $z_k$ ，可以去掉，原理是D-Seperation定理）

$P(z_k,x)=P(x_{(k+1):n}|z_k)P(z_k,x_{1:k})$

前面一项是Backward Algorithm，后面一项是Forward Algorithm

前面说过 $P(z_k|x)$ 是正比于关系，所以在计算的时候要用归一化处理一下

$p(z_{k=1}|x)= \frac{p(z_{k=1}|x)}{ \sum_{j}^{ } p(z_k=j,x)}$

F/B 算法最主要用来计算模型参数

前向算法

算法目标是求： $P(z_k,x_{1:k})$ 也是利用动态规划的思想来解决这个问题，公式：

$\large P(z_k,x_{1:k})=\sum_{z_{k-1}}^{ } P(z_{k-1},z_k,x_{1:k})$ 这里是把 $\large z_{k-1}$ 边缘化 marginalisation，这里缺乏背景知识不懂。

然后是拆开，目标是： $\large P(z_{k-1},x_{1:k-1})$

$\large P(z_k,x_{1:k})=\sum_{z_{k-1}}^{ } P(z_{k-1},z_k,x_{1:k})$

= $\large \sum_{z_{k-1}}^{ }P(z_{k-1},x_{1:k-1})P(z_k|z_{k-1},x_{1:k-1})P( x_k|z_k,z_{k-1},x_{1:k-1})$

观察式子跟图，找出条件独立的项，根据D-Seperation定理删除掉。

= $\large \sum_{z_{k-1}}^{ }P(z_{k-1},x_{1:k-1})P(z_k|z_{k-1})P( x_k|z_k)$

式子有3项，第一项是子问题，第二项是矩阵A可得，第三项是矩阵B可得。我们换个写法： $\large \alpha_k(z_k)$

$\large \alpha_k(z_k)=\sum_{ z_{k-1}}^{ } \alpha _{k-1}(z_{k-1})P(z_k|z_{k-1})P(x_k|z_k)$

然后初始条件：

$\large \alpha _1(z_1)=P(z_1,x)=P(z_1)P(x|z_1)$

前面有 $\large \pi$ 可得，后面有B可得。

后向算法

目标是求： $P(x_{(k+1):n}|z_k)$

拆分成子问题：X项 $\large P(x_{k+2:n}|z_{k+1})$ ，也是跟你前向算法一样，采用边缘化。

$P(x_{(k+1):n}|z_k)= \sum_{z_{k+1}}^{ }P(x_{(k+1):n},z_{k+1}|z_k ) \\= \sum_{z_{k+1}}P(x_{(k+2):n}|z_{k+1},z_k,x_{k+1}| )P(x_{k+1}|z_{k+1},z_k )P(z_{k+1}|z_k) \\= \sum_{z_{k+1}}P(x_{(k+2):n}|z_{k+1})P(x_{k+1}|z_{k+1})P(z_{k+1}|z_k)$