隐马尔可夫模型

马尔可夫性质：存在一个状态序列，未来的状态只与当前的状态相关，而不与历史状态相关

以每天的天气为例，明天的天气只与今天的天气相关，不与昨天、前天的天气相关。

马尔可夫过程：一个具备了马尔可夫性质的随机过程，与马尔可夫链的概念较像

隐马尔可夫模型：含有隐含参数的马尔可夫过程，包含两个等长的序列，观测序列和隐含序列。

两个假设

1、马尔可夫假设

隐含序列的每一个状态，只与上一个状态相关。

2、独立输出假设

每一时刻的观测状态，仅与当前时刻的隐含状态相关。

案例

构建一个案例（来自维基百科），假设你有一个住得很远的朋友，他每天跟你打电话告诉你他每天做了什么。他每天只可能做四种事中的一种：散步、打球、购物以及打扫房间。他选择做什么事情只凭天气，每天的天气只有三种，雨、晴、阴。但你不知道他所在地区的天气，只知道他每天做的事情。假如天气序列是一个马尔可夫链，那么天气的序列和他做的事情序列就构成了隐马尔可夫模型

模型参数

画图说明

(N) 表示隐含状态的种类数，每天天气的种类数 3，(M) 表示观测状态的种类数，即每天做的事情的种类数 4

(a_{ij}in R^{N*N}): 表示隐含状态之间的转移概率，天气 — 天气的转移概率

(b_{ij}in R^{N*M}): 表示每一个隐含状态到观测状态的输出概率，天气 — 做的事情的概率

(pi_i in R^N): 表示作为隐含序列第一个状态的概率，即第一天是某种天气的概率

下文以 ( heta=(a, b, pi)) 表示模型参数

三个问题

1、概率计算

已知模型参数和特定的观测序列，求各个时刻每个隐含状态的概率分布。即某个时刻是某种隐含状态的概率。

前向、后向算法

2、学习 / 训练

已知观测序列，求模型参数

有监督：统计概率

无监督：基于EM算法的思想，利用前向和后向算法迭代求解

3、预测

已知模型参数和观测序列，求最可能产生该观测序列的隐含序列

基于动态规划思想的维特比算法

概率计算

前向过程

定义 (alpha_{t}(i)=P(Y_1=y_1, Y_2 = y_2, ...Y_t=y_t, X_t=i| heta)) 是在已知参数 ( heta) 的条件下，观测序列是 (y_1,y_2,...y_t)，时刻 (t) 的隐含状态是 (i) 的概率。可以递归计算

(alpha_1(i)=pi_ib_{iy_1})
(alpha_{t+1}(i)=b_{iy_{t+1}}displaystyle sum_{j=1}^{N}{alpha_t(j)a_{ji}})

针对每一个时刻(t,tin[1, T])，每一个状态 (i, iin[1, N])，都可以计算出 (alpha_t(i))。( (N) 代表隐含状态的种类数)

后向过程

类似，定义 (eta_t(i)=P(Y_{t+1} = y_{t+1}, ..., Y_T = y_T|X_t=i, heta)) 是在已知参数 ( heta) ，时刻 (t) 的状态是 (i) 的条件下，余下观测部分是(y_{t+1}, ..., y_T) ，的概率

(eta_T(i)=1)
(eta_t(i)=displaystyle sum_{j=1}^{N}{eta_{t+1}(j)a_{ij}b_{jy_{t+1}}})

同样，针对每一个时刻 (t, tin[1, T]) ，每一个状态 (i, iin[1, N])，都可以计算出 (eta_t(i))

问题解答

在给定观测序列 (Y) 和参数 ( heta) 的情况下，在时间 (t) 状态是 (i) 的概率：

[gamma_t(i)=P(X_t=i|Y, heta)=frac{P(X_t=i,Y| heta)}{P(Y| heta)}=frac{alpha_t(i)eta_t(i)}{sum_{j=1}^{N}{alpha_t(j)eta_t(j)}} ]

中间参数

在给定观测序列 (Y) 和参数 ( heta) 的情况下，在时间 (t) 状态是 (i) , 在时间 (t+1) 状态是 (j) 的概率:

[xi_{t}(i,j)=P(X_t=i, X_{i+1}=j|Y, heta)=frac{P(X_t=i, X_{t+1}=j,Y| heta)}{P(T| heta)}=frac{alpha_t(i)a_{ij}eta_{t+1}(j)b_{jy_{t+1}}}{sum_{i=1}^{N}sum_{j=1}^{N}{alpha_t(i)a_{ij}eta_{t+1}(j)b_{jy_{t+1}}}} ]

训练

有监督

已知训练集的隐含状态，直接进行概率统计

1、转移概率 (a_{ij}) 的估计

假设样本中时刻 (t) 处于状态 (i) 且时刻 (t+1) 处于状态 (j) 的频次为 (A_{ij}) ，那么 (a_{ij}) 的定义为

[a_{ij}=frac{A_{ij}}{sum_{j=1}^{N}{A_{ij}}}, iin[1, n], jin[1, n] ]

2、观测概率 (b_{jk}) 的估计

假设样本中状态为 (j) 且观测为 (k) 的频次为 (B_{jk}) ，那么 (b_{jk}) 的估计为

[b_{jk}=frac{B_{jk}}{sum_{k=1}^{M}{B_{jk}}}, jin[1, N], kin[1, M] ]

3、发射概率的估计

假设隐含状态 (i) 作为隐含序列首状态的频次为 (C_i)，那么 (pi_i) 的估计为

[pi_i=frac{C_i}{sum_{i=1}^{N}{C_i}}, iin[1, N] ]

基于有监督的统计估计出模型参数，解决第二个问题

无监督

无监督的最大期望算法

对参数进行随机初始化，或者根据数据先验初始化，然后按照以下步骤迭代

[pi_i=gamma_1(i) ]

[a_{ij}=frac{sum_{t=1}^{T-1}{xi_{t}(i, j)}}{sum_{t=1}^{T-1}{gamma_t(i)}} ]

[b_i(v_k)=frac{sum_{t=1}^{T}{1_{y_t=v_k}gamma_t(i)}}{sum_{t=1}^{T}gamma_t(i))}, 1_{y_t=v_k}=1 if y_t=v_k else 0 ]

以上步骤根据EM算法进行推导，但直接理解的话也可

预测

维特比算法

分词问题

把文本当做观测序列，分词标注作为隐含序列，即可利用HMM进行分词任务