Welcome to my Blog!

• 隐马尔可夫链

  2019-06-22

  algorithm

  algorithm,  ML
  • 前言
  • HMM模型的定义
  • HMM的3个经典问题
    • 评估描述
      • 前向算法
    • 预测描述
      • 近似算法
      • 维比特算法

  前言

  隐马尔可夫模型（Hidden Markov Model，简称HMM），是可以用来标注问题的统计学习模型，描述由马尔可夫链随机生成观测序列的过程，属于生成式模型。 在正常的马尔可夫模型中，状态对于观测者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中，状态并不是直接可见的，但是受状态影响的某些变量是可见的。每一个状态在可能输出的符号上都有一个概率分布，因此输出序列能否透露出状态序列的一些信息。

  HMM模型的定义

  隐马尔可夫模型由初始概率分布，状态转移概率分布以及观测概率分布确定。 我们假设Q是所有可能的隐藏状态的集合，V是所有可能的观测状态的集合，即：

  $$Q={q_1,q_2,...,q_N},V={v_1,v_2,...,v_M}$$

  其中，N是可能的状态数，M是可能的观测数。 I是长度为T的状态序列，O是对应的观测序列。

  $$I=(i_1,i_2,...,i_T), O=(o_1,o_2,...,o_T)$$

  A是状态转移概率矩阵：

  $$A=[a_{ij}]_{N*N}$$

  其中，

  $$a_{ij}=P(i_{t+1}|i_t=q_i), i=1,2,...,N; j=1,2,...,N$$

  表示在时刻t处于状态$q_i$的条件下在时刻t+1转移到状态$q_j$的概率。

  B是观测概率矩阵：

  $$B=[b_j(k)]_{N*M}$$

  其中，

  $$b_j(k)=P(o_t=v_k|i_t=q_j), k=1,2,...,M;j=1,2,...,N$$

  表示在时刻t处于状态$q_j$的条件下生成观测$v_k$的概率。

  $\pi$是初始状态概率向量：

  $$\pi=(\pi_i)$$

  其中：

  $$\pi_i=P(i_1=q_i),i=1,2,...,N$$

  表示时刻t=1处于状态$q_i$的概率。

  一个马尔可夫模型，可以有隐藏状态的初始概率分布$\pi$，状态转移矩阵A和观测状态转移矩阵B决定，$\pi$，A决定状态序列，B决定观测序列。因此，隐马尔可夫模型$\lambda$可以用三员符号表示，即：

  $$\lambda=(A,B,\pi)$$

  $\pi$,A,B称为隐马尔可夫模型的三要素。

  隐马尔可夫做了两个很重要的基本能假设：

  1、齐次马尔可夫假设，即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于前一时刻的状态，于其他时刻的状态及观察无关，也与时刻t无关，即：

  $$P(i_t|i_{t-1},o_{t-1},...,i_1,o_1)=P(i_t|i_{t-1})$$

  2、观察独立性假设，即假设任意时刻的观测值依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关，即：

  $$P(o_t|i_T,o_T,...,i_{t+1},o_{t+1},...,i_1,o_1)=P(o_t|i_t)$$

  HMM的3个经典问题

  HMM模型建立起来后，一般我们会讨论3个问题：

  1、评估问题：给定模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,…,o_T)$，计算在模型$\lambda$下观测序列O出现的概率 $P(O|\lambda)$ => （前向算法）

  2、预测问题：也称解码，给定观测序列O和模型参数$\lambda$，我们怎样选择一个状态序列，以便能够最好的解释观测序列，即求最有可能的状态序列（条件概率 $P(I|O)$最大）。=> (维比特算法)

  3、学习问题：给定观测序列O,找到一个能最好的解释观测序列的模型$\lambda=(A,B,\pi)$，即使得 $P(O|\lambda)$最大。=> (EM算法，前后向算法)

  评估描述

  给定观测序列$O=(o_1,o_2,…,o_T)$和模型$\lambda=(A,B,\lambda)$,求观测序列O出现的概率最大的概率$P(O|\lambda)$。解决该问题的最直观的想法是把所有可能的隐藏状态都遍历一遍，得到对应观测状态的概率有多大，这些可能全部加起来就是得到这个观测状态的可能性。 1、全概率公式求解观测序列在所有可能的隐藏状态序列下的概率之和。

  $$P(O|\lambda)=\sum_IP(O|I,\lambda)P(I|\lambda)$$

  2、任意隐藏状态序列$I=(i_1,i_2,…,i_T)$的概率是

  $$P(I|\lambda)=\pi_{i_1}a_{i_1}{i_2}...a_{i_{T-1}}{i_T}$$

  3、已知状态序列$\lambda$下，观测序列$O=(o_1,o_2,…,o_T)$的概率

  $$P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T)$$

  4、O和I同时出现的联合概率为:

  $$\begin{align} P(O,I|\lambda)&=P(O|I,\lambda)P(I|\lambda)\\ &=\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_T}(o_T) \end{align}$$

  5、对所有可能的隐藏状态序列I求和得:

  $$\begin{align} P(O|\lambda)&=\sum_IP(O|I,\lambda)P(I|\lambda)\\ &=\sum_{i_1i_2...i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_T}(o_T) \end{align}$$

  利用上式计算量很大，达到$O(TN^T)$阶，在状态集合和隐藏状态序列比较短时，还是有可能穷举所有可能的状态序列，如果长的话，穷举的数量太大，指数级的，就很难完成。

  前向算法

  给定HMM模型$\lambda$，定义到时刻t部分观测序列为$o_1,o_2,..o_t$且状态为$q_i$的概率为前向概率，记为：

  $$\alpha_t(i)=P(o_1,o_2,...,o_t,i=q_i|\lambda)$$

  通过递推求得前向概率$\alpha_t(i)$即观测序列概率 $P(O|\lambda)$

  算法

  输入：隐马尔可夫模型$\lambda$,观测序列O 输出：观测序列概率$P(O|\lambda)$ 1、初值

  $$\alpha_t(i)=\pi_ib_i(o_i)$$

  2、递推，对t=1,2,…,T-1

  $$\alpha_t(i)=[\sum_{j=1}^{N}\alpha_t(j)a_{ji}]b_i(o_{t+1})$$

  3、终止

  $$P(O|\lambda)=\sum_{i=1}^{N}\alpha_T(i)$$

  预测描述

  近似算法

  维比特算法

  维比特算法实际是用动态规划解马尔可夫模型的预测问题，即用动态规划求概率最大路径，这时一条路径对应着一个状态序列。

  算法

  输入：模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,...,o_T)$

  输出：最优路径$I^{*}=(i_1^*,i_2^*,...,i_T^*)$

  1、初始化：

  $$\delta_1(i)=\pi_ib_i(o_1),i=1,2,..,N$$ $$\Psi_1(i)=0,i=1,2,...,N$$

  2、递推，对$t=2,3,...,T$

  $$\delta_t(i)=\max_{1≤j≤N}[\delta_{t-1}(j)a_ji]b_i(o_t),i=1,2,...,N$$ $$\Psi_t(i)=arg\max_{1≤j≤N}[\delta_{t-1}(j)a_ji],i=1,2,...,N$$

  3、终止

  $$P^*=\max_{1≤i≤N}\delta_T(i)$$ $$i_T^*=arg\max_{1≤i≤N}\delta_T(i)$$

  4、最优路径回溯，对$t=T-1,T-2,…,1$

  $$i_t^*=\Psi_{t+1}(i_{t+1}^*)$$

  求得$I^{*}=(i_1^*,i_2^*,...,i_T^*)$

  Read All

  ---

• EM算法

  2019-06-20

  algorithm

  algorithm,  ML
  • 凸函数
  • Jensen不等式
  • EM算法
    • EM算法公式推导
    • EM算法的收敛性证明

  凸函数

  开始EM算法前，我们先讨论凸函数。连续函数的一阶导数就是相应的切线斜率。一阶导数大于0，则递增；一阶倒数小于0，则递减；一阶导数等于0，则不增不减。 而二阶导数可以反映图象的凹凸。二阶导数大于0，图象为凹；二阶导数小于0，图象为凸；二阶导数等于0，不凹不凸。

  现设一函数f(x)，在该函数定义域的凸区间内任取两点$x_1$,$x_2$, 其中$x_1<x_2$,设一点$x=q_1x_1+q_2x_2$,($q_1$,$q_2>0$且$q_1+q_2=1$),那么该点必包含于$x_1$,$x_2$之间。

  

  图中包含点$A_1(x_1,x_2)$、$A_2(x_2,x_2)$,$A(x,f(x))$,先构建线性函数两点式，代入$A_1(x_1,x_2)$、$A_2(x_2,x_2)$两点，再代入B点的横坐标，得到其纵坐标：

  $$y=\frac{x_2-x}{x_2-x_1}y_1+\frac{x-x_1}{x_2-x_1}y_2$$

  同时利用$x=q_1x_1+q_2x_2$可以得：

  $$q_1=\frac{x_2-x}{x_2-x_1}$$ $$q_2=\frac{x-x_1}{x_2-x_1}$$

  所以B的纵坐标是：

  $$y=q_1f(x_1)+q_2f(x_2)$$

  结合上图，显然：

  $$y_B≥y_A$$ $$=> q_1f(x_1)+q_2f(x_2)≥f(q_1x_1+q_2x_2)$$

  且当$x_1 -> x_2$时，可以等号成立。

  总结下：
  在区间X上，有定义而且连续的函数$f(x)$叫做凸函数（往下凸），如果对于区间x中的任何两点$x_1$和$x_2(x_2>=x_1)$有不等式：

  $$f(q_1x_1+q_2x_2) ≤q_1f(x_1)+q_2f(x_2)$$

  同理，当函数为凹函数是：

  $$f(q_1x_1+q_2x_2) ≥q_1f(x_1)+q_2f(x_2)$$

  Jensen不等式

  刚刚我们已经证明的凸函数的代数定义：

  $$q_1f(x_1)+q_2f(x_2)≥f(q_1x_1+q_2x_2)$$

  将其一般化，便容易推出：

  $$f(q_1x_1+q_2x_2+...+q_nx_n)≤q_1f(x_1)+q_2f(x_2)+...+q_nf(x_n)$$ $$(q_1,...,q_n>0,q_1+...+q_n=1)$$

  将形式更加简化得：

  $$f(\sum_{i=1}^np_ix_i)≤\sum_{i=1}^np_if(x_i)$$

  在概率论中，如果把$p_i$看成是取值为$x_i$的离散变量x的概率分布，那么上式可以写成：

  $$f(E(x))≤E(f(x))$$

  其中$E(.)$表示期望。

  EM算法

  EM算法是一种迭代算法，主要用来处理含有隐变量（hidden variable）的概率参数的极大似然估计，或者极大后验概率估计。EM算法的每次迭代分为两步：E步，求期望；M步，求极大。所以该算法称为期望极大算法（expectation maximization algorithm），简称EM算法。

  EM算法公式推导

  推导过程参照李航<统计学习方法>，加上个人理解。

  当我们面对一个含有隐变量的概率模型时，我们的最终目标是要极大化观测数据$Y$关于参数$\theta$的对数似然函数，即极大化：

  $$L(\theta)=logP(Y|\theta)$$

  将所有隐变量于观测数据$Y$的所有联合概率相加，即：

  $$P(Y|\theta)=\sum_ZP(Y,Z|\theta)$$ $$L(\theta)=\log\sum_ZP(Y,Z|\theta)=\log\left(\sum_ZP(Y|Z,\theta)P(Z|\theta)\right)$$

  注意到要极大化上式非常困难的，式中不仅有未观测数据$Z$,还包含了求和的对数，对未知变量求导后等于0的式子仍然十分复杂。 我们可以通过迭代的方式不断的逼近极大化的$L(\theta)$，假设在第i次的迭代后的$\theta$的估计值是$theta^{(i)}$,如果能够使新估计的$\theta$，让$L(\theta)$增加，即，使得$L(\theta)>L(\theta^{(i)})$,那么在一次次的迭代之后，最终会逼近$L(\theta)$的极大值。 即：

  $$L(\theta)-L(\theta^{(i)})=\log\left(\sum_ZP(Y|Z,\theta)P(Z|\theta)\right)-logP(Y|\theta^{(i)})$$

  利用上面的Jensen不等式，得到其下界：

  $$\begin{align} L(\theta)-L(\theta^{(i)})&=\log\left(\sum_ZP(Y|Z,\theta)P(Z|\theta)\right)-logP(Y|\theta^{(i)})\\ &=\log\left(\sum_ZP(Z|Y,\theta^{(i)})\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})}\right)-logP(Y|\theta^{(i)})\\ &≥\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})}-logP(Y|\theta^{(i)}) \end{align}$$

  因为$P(Z|Y,\theta^{(i)})$是Z关于Y的概率分布，所以: $\sum_ZP(Z|Y,\theta^{(i)})=1$ 即上式：

  $$≥\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})}-\sum_ZP(Z|Y,\theta^{(i)})logP(Y|\theta^{(i)})$$ $$=\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}$$

  令：

  $$B(\theta,\theta^{(i)})=L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}$$

  则：$L(\theta)≥B(\theta,\theta^{(i)})$,即函数$B(\theta,\theta^{(i)})$是$L(\theta)$的一个下界，由上面的式子可知：

  $$L(\theta^{(i)})=B(\theta^{(i)},\theta^{(i)})$$

  因此对于任何能使$B(\theta,\theta^{(i)})$增大的$\theta$，也同时可以使$L(\theta)$增大，为了使$L(\theta)$增大，选择$\theta^{(i)}$使得$B(\theta,\theta^{(i)})$达到极大，即：

  $$\theta^{(i+1)}=arg\max_{\theta}B(\theta,\theta^{(i)})$$

  去掉不相关的常数：

  $$\begin{align} \theta^{(i+1)}&=arg\max_{\theta}\left(L(\theta^{(i)})+\sum_ZP(Z|Y,\theta^{(i)})\log\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta^{(i)})P(Y|\theta^{(i)})}\right)\\ &=arg\max_{\theta}\left(\sum_ZP(Z|Y,\theta^{(i)})\log(P(Y|Z,\theta)P(Z|\theta))\right)\\ &=arg\max_{\theta}\left(\sum_ZP(Z|Y,\theta^{(i)})logP(Y,Z|\theta)\right)\\ &=arg\max_{\theta}Q(\theta,\theta^{(i)}) \end{align}$$

  EM算法的收敛性证明

  由于：

  $$P(Y|\theta)=\frac{P(Y,Z|\theta)}{P(Z|Y,\theta)}$$

  两边取对数有：

  $$logP(Y|\theta)=logP(Y,Z|\theta)-logP(Z|Y,\theta)$$

  等式两边同时对分布 $P(Z|Y,\theta^{(i)})$ 求期望得：

  $$\sum_ZlogP(Y|\theta)P(Z|Y,\theta^{(i)})=\sum_ZlogP(Y,Z|\theta)P(Z|Y,\theta^{(i)})-\sum_ZlogP(Z|Y,\theta)P(Z|Y,\theta^{(i)})$$

  等式左边与Z无关，分布求和等于1，于是：

  $$\begin{align} logP(Y|\theta)&=\sum_ZlogP(Y,Z|\theta)P(Z|Y,\theta^{(i)})-\sum_ZlogP(Z|Y,\theta)P(Z|Y,\theta^{(i)})\\ &=Q(\theta,\theta^{(i)})-H(\theta,\theta^{(i)}) \end{align}$$

  分别取$\theta$为$\theta^{(i)}$和$\theta^{(i+1)}$并相减，有：

  $$logP(Y|\theta^{(i+1)})-logP(Y|\theta^{(i)})=[Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})]-[H(\theta^{(i+1)},\theta^{(i)})-H(\theta^{(i)},\theta^{(i)})]$$

  要使收敛性成立，只需上式右端是非负即可，又由于$Q(\theta^{(i+1)})$是$Q(\theta,\theta^{(i)})$达到极大，所以有$Q(\theta^{(i+1)},\theta^{(i)})-Q(\theta^{(i)},\theta^{(i)})≥0$, 要使右端为非负，只需$H(\theta^{(i+1)},\theta^{(i)})-H(\theta^{(i)},\theta^{(i)})≤0$,于是：

  $$\begin{align} H(\theta^{(i+1)},\theta^{(i)})-H(\theta^{(i)},\theta^{(i)})&=\sum_ZlogP(Z|Y,\theta^{(i+1)})P(Z|Y,\theta^{(i)})-\sum_ZlogP(Z|Y,\theta^{(i)})P(Z|Y,\theta^{(i)})\\ &=\sum_Z\left(log\frac{P(Z|Y,\theta^{(i+1)})}{P(Z|Y,\theta^{(i)})}\right)P(Z|Y,\theta^{(i)})\\ &≤log\left(\sum_Z\frac{P(Z|Y,\theta^{(i+1)})}{P(Z|Y,\theta^{(i)})}P(Z|Y,\theta^{(i)})\right)\\ &=log\left(\sum_ZP(Z|Y,\theta^{(i+1)})\right)=0 \end{align}$$

  即收敛性得证。

  Read All

  ---