大纲

• Why HMM
• 传统学习 vs 深度学习
• HMM模型参数
• Two Major Tasks

Why HMM

隐马尔科夫模型（Hidden Markov Model，以下简称HMM）是比较经典的机器学习模型了，它在语言识别，自然语言处理(词性标注)，模式识别等领域得到广泛的应用。

当然，随着目前深度学习的崛起，尤其是RNN，LSTM等神经网络序列模型的火热，HMM的地位有所下降。

但是作为一个经典的模型，学习HMM的模型和对应算法，对我们解决问题建模的能力提高以及算法思路的拓展还是很好的。

首先我们来看看什么样的问题解决可以用HMM模型。

使用HMM模型时我们的问题一般有这两个特征：

１）我们的问题是基于序列的，比如时间序列，或者状态序列。

２）我们的问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。

有了这两个特征，那么这个问题一般可以用HMM模型来尝试解决。这样的问题在实际生活中是很多的。比如：一个你天天见到的朋友，他心情好的时候会和你说很多话，心情不好的时候可能爱答不理，你可以通过他的表现来推断出来他心情的变化甚至可以猜测他身边可能发生的一些事情。

传统学习 vs 深度学习

传统: 非分布式表示; 单词: 独热编码; 时序: HMM; space represtation;local generalization;

深度学习:分布式表示; 单词: 词向量；时序: RNN;dense represtation; gobal generalization;

HMM模型简介

theta = (A,B,pi)

z: 状态 ; x: 观测值

A(transition_matrix) : 状态迁移矩阵, 假设现在有 k 个状态, 它是个 k times k 的矩阵 , 横向之和为1。

B(emission_matrix): 发射矩阵，假设现在有 k 个状态， m 种观测情况，它是个 k times m 的矩阵

一阶

① Markov assumption 当前的状态只依赖于之前的状态

② 当前的observation 只依赖于当前的状态

Two Major Tasks

1. 给定模型的参数(观测值X已知)，找出最合适的Z(线上预测 ex.实体命名识别)
2. 估计模型参数 theta (训练阶段)

Z: latent ; variable

X:Observation

theta:Model ; Parameter

假设 Z 已知,可以用最大似然估计求出 theta

maxmize ; P(x,z|theta) Rightarrow theta

P(x) = sum_{z}^{}P(x,z)

X sim P(X|Z)

rightarrow X是离散型 rightarrow Multinomial

;;;; X sim multinomial (B_z)

rightarrow X是连续型的 rightarrow GMM

;;;; X sim Gaussian (mu_z, Sigma_z)

Finding Best Z

方法1: 遍历出所用的情况(Navie Solution)

方法2: P(z|x,theta) Rightarrow P(z_1 = k|x,theta)

Greedy Solution rightarrow global optimal solution

方法3：DP/Viterbi

Gaussian Distribution x:正/负

Gamma Distribution x:正

Multinomial Distribution x rightarrow y

Dirichelet Distribution x(正数) rightarrow y(0.1+0.2+0.7 = 1)

Laplace Distribution x rightarrow y(spase)

score = 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)…

delta_k(i): the score of the best path ending at state i at time t

delta_{k+1}(j): begin{bmatrix} delta_k(1) + logP(z_{k+1} = j | z_k = 1) + logP(x_{k+1} | z_{k+1} = j) / delta_k(2) + logP(z_{k+1} = j | z_k = 2) + logP(x_{k+1} | z_{k+1} = j) /…/ delta_k(m) + logP(z_{k+1} = j | z_k = m) + logP(x_{k+1} | z_{k+1} = j) end{bmatrix}

用log起到了防止乘法溢出的问题

上面的时间复杂度为 O(m times n) cdot O(m) = O(m^2 cdot n)

delta = np.zeros((n,m))

i=1时 初始化

for ; i = 2 ,….,n

::::for ; j= 1 ,….,m

;;;;;;;delta_{i}(j) = max(m个计算)

时间复杂度: O(m^2 cdot n)

空间复杂度: O(m cdot n)

viterbi代码: