HMM根底

隐马尔科夫模型（Hidden Markov model）,HMM是很风行的序列模型，广泛应用在语音辨认等畛域,也能够用在词性标注、实体辨认等文本问题中。

工夫序列数据

工夫序列数据（time series data）能够认为是沿着工夫的维度而变动的数据，列如股价、气温、语音、文本等。时序的数据它的长度是不确定的，比方两个人说同一句话，可能有的人说的比拟快，有的人比较慢。所以咱们在将逻辑回归或者SVM利用在这类数据上理论是会损失一些数据的。
非时序数据比方像图片，一个人的特色等，当咱们应用它们的时候，它的维度是固定的。
时序类的模型，从传统机器学习角度来说有HMM、CRF，从深度学习角度来说有RNN、LSTM。

HMM模型介绍

上图是一个HMM模型的经典构造，它由下层的隐变量和上层的观测值组成。隐变量之间的传递叫作状态转移，隐变量到观测值之间的传递叫作状态生成,所以它也是生成模型。
能够看到这个模型是有向的、生成的模型。
HMM是一个概率图模型，在$ t=1 $时刻：

$ z_1 $示意一个状态，然而它有多种状态，示意每种状态有着对应的概率
$ z_1 $ to $ z_2 $，示意状态的转移，由前一种状态转移到下一种状态也有着对应的概率
$ z_1 $ to $ x_1 $，示意在这种状态下生成了一个值，这个值也有不同的取值（通常可分为间断和离散值），在这种状态下生成了这种值也有着对应的概率。

由以上介绍不难晓得HMM模型存在三大次要问题：

一是在已知模型参数的条件下，对于任何一个观测值序列，去推出背地状态转移的序列，这种问题也叫inference 或者decoding。比如说如果这个序列是针对语音辨认，那么咱们能够依据听到的音乐或人的声音来反推出他到底说了哪些单词或者哪些句子。
二是给定观测值，咱们去预测出或者估算出整个模型的参数。
三是计算某一个观测值序列的边缘概率。

利用举例 Part of Speech Tagging(POS)

当咱们的问题变成词性标注时，咱们关怀的是：给定一句话，晓得观测值（单词）$ x_1 到 x_n $到底是什么词性。能够晓得在这个例子里$ z_i $是离散值。
接下来看咱们的三大问题：

给定咱们句子，咱们须要去反推出它每个单词的词性。这个问题也叫inference or decoding问题（怎么解决，维特比算法）
给定一句话之后，咱们怎么去预计模型的参数。
$ p(x_1x_2...x_n) $呈现的概率是多少

请看对下面第二个问题的详解：
参数$ \theta = (A,B,\pi) $，
A示意的是词性之间的转换的概率（transition probability）:

A是状态转移概率矩阵，也叫作transiton probability。咱们要晓得状态之间的转移不是随机产生的，而是更有可能转移到其它的状态里。
$ A_{m\times m} $,m示意词性(状态)的品种个数，每一行示意一个词性（状态），每一行加起来为1。
矩阵里每一个点示意从前一个词性（状态）转换到下一个词性（状态）的概率。

B是生成概率（emission probability）：

在$ z_1 $状态下咱们生成的单词$ w_1 $是某种词性的概率，它能够表白为一个概率矩阵
$ B_{m\times v} $,m示意词性的品种个数，v示意词库的大小，每一行示意每一种词性对应词库里每一个单词的概率，每一行加和为1。
矩阵里的每一个点示意在某个状态下（在这个例子中是单词词性）看到一个观测值（在这个例子中是单词）的概率是多少。
值得注意的是生成的值也能够是间断值，对于连续型的变量咱们是不能写成矩阵的模式的，这时该当借用高斯混合（GMM）模型来解决。

$ \pi $示意句子里第一个单词（观测值）呈现某个词性（状态）的概率：

能够了解为$ \pi $是一个初始化数组,即$ \pi = [\pi_1,\pi_2...\pi_i...\pi_m]$,加和为1

在这个模型中，$ x\to \theta $,这个过程叫预测，parameter estimate ；$ x\to z $，这个过程叫infer

基于为维特比算法的预测

解决inference/decoding 问题:给定$ \theta = (A,B,\pi) $,$ x $序列，反推出$ z $

tips:个别给定问题的时候，咱们都应该能想到一个最笨的办法，再基于这个办法去思考、一直去优化，这是个别的解题过程。

简略的办法：
假如咱们的 $ z_i\in \ { a,b,c} $, 所以咱们能够写出所有的状态转移序列，再基于以下公式（1）算出似然概率

$$p(z_1)p(z_2|z_1)p(z_3|z_2)...p(z_{n-1}|z_n)p(x_1|z_1)p(x_2|z_2)...p(x|z_n)\tag{1}$$

咱们能够用上式（1）计算出所以状态转移序列的似然概率，但毛病也是很显著的，就是计算的工夫复杂度是指数级的，计算量十分大，所以我得思考其余更高效的办法，如动静布局。

动静布局算法适宜那种刚开始是指数级复杂度。然而我通过存储两头的过程，来加重计算量，这是动静布局的外围。维特比算法就是这样的一种算法。
但其实在这里维特比算法为什么会无效还有另外的一些因素，就是像HMM这样的模型是有限度条件的，限度条件是咱们的隐式变量$ z_i $只会跟前一个隐式变量$z_{i-1}$有分割，只有这样咱们能力大大减少计算量。假如咱们的$ z_i $如果满足网状图或是齐全图，即每一个节点都和其余节点有分割，这时候即便咱们应用维特比算法也降不下来计算量。

维特比算法
上面是用维特比计算过程中的一个流程图：
$ 1-m $示意每个隐变量可取的状态，一共$ m $种,$ z_1-z_n $示意隐变量，同时也对应工夫$ t $

当初利用上图思考咱们的问题，给定一个序列$ x_i $,须要去确定最好的$ z_i $, 也就是须要确定上图中红色线标注的这样的一条最好门路。当咱们的门路确定了的时候，咱们的$ z_i $也就确定了。
咱们来看看这样的一条门路的其概率怎么计算：

$$\begin{equation}\begin{split} probability &= p(z_1=2)\cdot p(x_1|z_1=2)\cdot p(z_2=1|z_1=2)\cdot \\&p(x_2|z_2=1)\cdot... \cdot p(z_n=j|z_{n-1}=j+1)\cdot p(x_n|z_n=j)\end{split}\end{equation}\tag{2}$$

其中，

整个概率计算公式其实由这三局部组成，1其实就是参数$ \pi $，2是transition probability, 3是Observeation model,刚好对应参数$ \theta $。

接下来用递推公式：
定义 $ \delta_k(i) $ := the score of the best path ending at state i at time k
$ \delta_{k+1}(j) $只与其前一个状态无关，蓝色的虚线示意可能的转移门路，计算形式如下：

$$\delta_{k+1}(j) = max \left \{ \begin{array}{c} \delta_{k}(1)+log(p(z_{k+1}=j|z_k=1))+log(p(x_{k+1}=j|z_{k+1}=j))\\ \delta_{k}(2)+log(p(z_{k+1}=j|z_k=2))+log(p(x_{k+1}=j|z_{k+1}=j))\\ \ ......\\ \ \delta_{k}(m)+log(p(z_{k+1}=j|z_k=m))+log(p(x_{k+1}=j|z_{k+1}=j))\tag{3}\end{array}\right.$$

递推公式总结为：

$$\delta_{k+1}(j) = max_i[\delta_{i}(m)+log(p(z_{k+1}=j|z_k=i))+log(p(x_{k+1}=j|z_{k+1}=j))]\tag{4}$$

其中，$ j \in [1,m] ,i \in [1,m], k+1 \in [1,n] $，工夫复杂度为$ O(n\cdot m^2) $

整个过程是从上到下，从左到由计算（填表），其中最初一列是$ [\delta_{n}(1),\delta_{n}(2)...\delta_{n}(m)] $，选出其中最大的数就是咱们的最优门路起点，之后回溯便可确定最终的门路。
在计算的过程中，须要一个栈来记录门路上的节点。由此这个算法完结，但其实这样的过程咱们失去的是部分最优，并不是全局最优，失去全局最优还需其余算法(如贪婪，然而工夫开销十分大)。

HMM中的参数估计

Forward/Backward 算法

Forward/Backward算法在预计HMM参数中表演很重要的角色。换句话说，在预计HMM参数过程中，会用到Forward/Backward算法的后果。

Forward/Backward算法是为了计算$ p(z_k|x) $
Forward是为了计算$ p(z_k,x_{1:k}) $
Backward是为了计算$ p(x_{k+1:n } | z_k) $

通过贝叶斯咱们能够改写

$$p(z_k|x) = \frac {p(z_k,x)} {p(x)} \varpropto p(z_k,x) \tag{5}$$

在这里无论$ z_k $怎么取值，都有$ p(x) $这样的一个概率存在，或者说其实在这里$ p(x) $就相当于一个常数项。

$$\begin{equation}\begin{split} p(z_k,x) =& p(x_{k+1:n}|z_k,x_{1:k}) \cdot p(z_k,x_{1:k}) \\=& p(x_{k+1:n}|z_k) \cdot p(z_k,x_{1:k}) \tag{6}\end{split}\end{equation}$$

$ x_{1:k} $条件独立于$ x_{k+1:n} $

式（6）的后果正好是上Forward/Backward的后果

Forward algorithm

为了计算$ p(z_k,x_{1:k}) $，能够穷举，也能够用动静布局的的形式求出递推式，当然这种有前后关系的个别都采纳动静布局。
所以咱们想要求出这样一个递推式：

$$p(z_k,x_{1:k}) = something \cdot p(z_{k-1},x_{1:k-1}) \tag{7}$$

So,

$$\begin{equation}\begin{split} p(z_k,x_{1:k}) =& \sum_{z_{k-1}} p(z_{k-1},z_k,x_{1:k})\\=& \sum_{z_{k-1}} p(z_{k-1},x_{1:k-1}) \cdot p(z_k|z_{k-1},x_{1:k-1}) \cdot p(x_k|z_k,z_{k-1},x_{1:k-1})\\=& \sum_{z_k-1} p(z_{k-1},x_{1:k-1}) \cdot p(z_k|z_{k-1}) \cdot p(x_k|z_k)\tag{8}\end{split}\end{equation}$$

在式（8）中：

$ x_{1:k-1} $与$ z_k $条件独立，故能够删去
$ z_{k-1},x_{1:k-1} $与$ x_k $条件独立，故能够删去

到此，咱们曾经把递推关系写进去了，如果咱们把$ p(z_k,x_{1:k}) $示意为$ \alpha(z_k) $,那么递推公式能够从新示意为：

$$ \alpha_k(z_k) = \sum_{z_{k-1}} \alpha_{k-1}(z_{k-1}) \cdot p(z_k|z_{k-1}) \cdot p(x_k|z_k)\tag{9}$$

$$\alpha(z_1) = p(z_1,x) = p(z_1)\cdotp(x_1|z_1)=\pi \cdot B \tag{10}$$

Backward algorithm

Backward algorithm 是从前面向前计算的，与Forward algorithm相同。
同样咱们想要求出这样一个递推式：

$$p(x_{k+1:n}|z_k) = something \cdot p(x_{k+2:n}|z_{k+1}) \tag{11}$$

$$\begin{equation}\begin{split} p(x_{k+1:n}|z_k) =& \sum_{z_{k+1}} p(x_{k+1:n},z_{k+1}|z_k) \\=& \sum p(x_{k+2:n}|z_{k+1},x_{k+1},z_k) \cdot p(x_{k+1}|z_{k+1},z_k)\cdot p(z_{k+1}|z_k)\\=& \sum p(x_{k+2:n}|z_{k+1}) \cdot p(x_{k+1}|z_{k+1})\cdot p(z_{k+1}|z_k)\end{split}\end{equation}\tag{12}$$

在式（12）中，

$ x_{k+1},z_k $与$ x_{k+2:n} $条件独立，故能够删去
$ z_k $与 $ x_{k+1} $条件独立，故能够删去

到此，咱们曾经把递推关系写进去了，如果咱们把$p(x_{k+1:n}|z_k)$示意为$ \beta(z_k) $,那么递推公式能够从新示意为：

$$ \beta_k(z_k) = \sum_{z_{k+1}} \beta_k(z_{k+1}) \cdot p(x_{k+1}|z_{k+1})\cdot p(z_{k+1}|z_k)\tag{13}$$

Ok, 到此为止筹备工作已就绪，Forward算法，Backward算法行将在正式的参数估计中会用到

Incomplete and Complete Case

在正式进入HMM参数估计之前，首先来看一个更简略的状况，也就是在样本数据中咱们既能够观测到x，也能够观测到z的状况。这时候，参数估计变得分外简略，只须要从数据中统计一下就能够了。

Complete case: x, z 都晓得
Incomplete Case: 仅晓得x

Complete Case

Incomplete Case

在complete状况下，参数估计很简略，那么在incomplete状况下又如何预计呢?因为在incomplete状况下咱们并没有观测到变量z，所以不能简略地做统计。所以，怎么做? 答案是:求冀望(expectation)

在HMM中，有两类变量，一种是模型自身的参数，另外一种是隐变量z。而且很难同时对这两类参数求预计，所以采纳的一种办法是:把其中一组变量看作是常量(constant)，从而预计另外一组变量，以此类推。
具体来讲，把模型参数看作是常量，预计变量z; 把z看作是常量，预计模型参数; 把模型参数看作是常量，预计变量z; 把z看作是常量，预计模型参数, 始终循环到收敛为止。

这里咱们应用一种算法，EM算法，EM算法用于预计两个未知量，罕用于机器学习算法中，例如K近邻。
例如在这个例子中，$ \theta = { \pi,A,B} $,和参数$ z $。EM算法流程是预计$ z $，预计$ theta $,预计$ z $,预计$ \theta $...,直到converge。

EM algorithm

$$ \mathop {argmax}_{\theta}[E_{z|x,\theta}ln p(x,z | \theta)]\tag{14}$$

式（14）分为两步骤：

E-step: 求出$ Z $的冀望
M-step: 最大化$ ln p(x,z | \theta) $
一二步骤顺次循环，直到收敛

算法流程能够示意为：

while (not converged):    compute z(expectation)    update pi,A,B

HMM的参数求解

预计$ \pi $

预计B

预计A

条件概率与冀望

概率预计，标准化

小结

HMM的inference过程实际上是对于序列的预测过程，要用到维特比算法

维特比算法实际上是动静布局算法

HMM的参数估计实际上是模型训练过程，须要预计三类不同的参数

HMM的参数估计过程要用到EM算法，而且EM算法的后果依赖于初始化后果。不同的初始化很可能带来不一样的成果

未完待续....

此为集体学习笔记，不得侵权，不得用于其余路径！

关于nlp:隐马尔科夫模型