隐含马尔科夫模型(HMM)

机器学习 算法

---

马尔科夫模型

任何一次观测都和前面的所有观测有关，则有

$$p(x_1,..x_N)=p(x_1)*\prod_{n=2}^Np(x_n|x_1,..x_{n-1})$$

简化

对其进行简化，假设其每次观测只与前面一次或者两次有关，则有
一阶马尔科夫模型

$$p(x_1,..x_N)=p(x_1)*\prod_{n=2}^Np(x_n|x_{n-1})$$
二阶马尔科夫模型 $$p(x_1,..x_N)=p(x_1)*p(x_2|x_1)\prod_{n=3}^Np(x_n|x_{n-2},x_{n-1})$$
使用一阶简化模型后有 $$p(x_n|x_1,...x_{n-1})={p(x_1)*\prod_{i=2}^np(x_i|x_{i-1}) \over p(x_1)*\prod_{i=2}^{n-1}p(x_i|x_{i-1})}=p(x_n|x_{n-1})$$

参数个数

接受观测具有K个状态，则有 $p(x_n|x_{n-1})$ 有 K-1 个参数，$x_{n-1}$ 可为K个值，则有 K(K-1) 个参数。M 阶参数有 $K^M(K-1)$ 个。

隐马尔科夫模型

是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。

状态序列

隐藏的马尔科夫链随机生成的状态的序列

观测序列

每个状态生成一个观测，而由此产生的观测的随机序列

形式定义

Q是所有的状态集合，V是所有观测集合 $$Q={q_1,..q_N};V={v_1,..v_M}$$ I是长度为T的状态序列，O是对应的观测序列 $$I={i_1,..i_T};O={o_1,..o_T}$$ A是状态转移矩阵 $$A=[a_{ij}]_{N×N}；a_{ij}=p(i_{t+1}=q_j|i_t=q_i),ij\in (1-N)$$ B是观测概率矩阵 $$B=[b_j(k)]_{N×M};b_j(k)=p(o_t=v_k|i_t=q_j);k\in(1-M),j\in (1-N)$$ $\pi$是初始状态概率向量 $$\pi=(\pi_i);\pi_i=p(i_1=1_i),i\in(1-N)$$ 其模型$\lambda$可以用三元符号表示 $$\lambda = (A,B,\pi)$$

基本假设：

• 齐次马尔科夫性假设，即假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态以及观测无关，也与时刻t无关 $p(i_t|i_{t-1},o_{t-1},...i_1,o_1)=p(i_t|i_{t-1}),t\in(1-T)$
• 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关。 $p(o_t|i_T,o_T,...i_1,o_1)=p(o_t|i_t)$

概率计算问题

给定模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,..o_T)$，计算在模型$\lambda$下观测序列O出现的概率$p(O|\lambda)$

直接计算法

$$p(O|\lambda)=\sum_Ip(O|I,\lambda)p(I|\lambda)$$ $$=\sum_{i_1,..i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1,i_2}b_{i_2}(o_2)...a_{i_{T-1}i_T}b_{i_T}(o_T)$$

scala代码如下

  def calcProbDirect(output: Array[Int]): Double = {
    val len = output.length
    val stateLen = stateChange.length
    def rescCalc(outputIndex: Int, lastState: Int, currProb:Double):scala.collection.immutable.IndexedSeq[Double] ={
      if (outputIndex == 0){
        for (state <- 0 until stateLen;
          i <- rescCalc(outputIndex+1,state, pi(state)*ouputPorbs(state)(output(outputIndex))*currProb))
          yield i
      }
      else if (outputIndex == len-1) {
        for (state <- 0 until stateLen) yield currProb*stateChange(lastState)(state)*ouputPorbs(state)(output(outputIndex))
      }
      else {
        for (state <- 0 until stateLen;
          i <- rescCalc(outputIndex+1,state, currProb*stateChange(lastState)(state)*ouputPorbs(state)(output(outputIndex))))
          yield i
      }
    }
    rescCalc(0, 0, 1).sum
  }

前向算法

前向概率

给定模型$\lambda$，定义到时刻t部分观测序列为$o_1,...o_t$且状态为$q_i$的概率为前向概率，记为 $$\alpha_t(i)=p(o_1,..o_t,i_t=q_i|\lambda)$$

前向算法

1 初始值 $\alpha_1(i)=\pi_ib_i(o_1),i\in(1...N)$
2 递推，对所有 $t\in (1...\ T-1)$ $$\alpha_{t+1}(i)=[\sum_{j=1}^N\alpha_t(j)a_{ji}]b_i(o_{t+1}),i\in(1...N)$$
3 终止 $p(O|\lambda) = \sum_{i=1}^N\alpha_T(i)$

  def calcProbForward(output: Array[Int]): Double = {
    val len = output.length
    val stateLen = stateChange.length
    def clacOutIndexProbForState(outputIndex:Int, state:Int) ={
      ouputPorbs(state)(output(outputIndex))
    }
    def forward(outputIndex: Int): Seq[(Int, Double)] ={
      if (outputIndex == 0) {
        (0 until stateLen zip pi).map{case (state, prob) => (state, prob*clacOutIndexProbForState(outputIndex, state))}
      }
      else {
        forward(outputIndex-1).flatMap {
          case (state, prob) => {
            ((0 until stateLen) zip stateChange(state)).map {
              case (nextState, changeRatio) => {
                (nextState, prob * changeRatio * clacOutIndexProbForState(outputIndex, nextState))
              }
            }
          }
        }.groupBy(_._1).map(line =>{(line._1, line._2.map(_._2).sum)}).toList
      }
    }
    forward(len-1).map(_._2).sum
  }

后向算法

后向概率

给定马尔科夫模型$\lambda$，定义在时刻t状态为$q_i$的条件下，从t+1到T的部分观测序列为$o_{t+1},o_{t+2}..,o_T$的概率为后向概率，记为 $$\beta_t(i)=p(o_{t+1},o_{t+2}..,o_T|i_t=q_i,\lambda)$$

后向算法

1 $\beta_T(i)=1,i\in(1..N)$
2 对$t\in(T-1...1)$ $$\beta_t(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j),j\in(1...N)$$ 3 $$p(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_i(i)$$

  def calcProbBackWord(output: Array[Int]): Double = {
    val len = output.length
    val stateLen = stateChange.length
    def clacOutIndexProbForState(outputIndex:Int, state:Int) ={
      ouputPorbs(state)(output(outputIndex))
    }
    def backward(outputIndex: Int): Seq[(Int, Double)] ={
      if (outputIndex == len-1) {
        0 until stateLen map ((_, 1.0))
      }
      else if (outputIndex == -1){
        backward(outputIndex+1).map{case(state, prob) => {(state, prob*pi(state)*clacOutIndexProbForState(outputIndex+1, state))}}
      }
      else {
        backward(outputIndex+1).flatMap {
          case (state, prob) => {
            val stateprobs = stateChange.map(line=> line(state))
            ((0 until stateLen) zip stateprobs).map {
              case (preState, changeRatio) => {
                //println(preState, state, prob, changeRatio, clacOutIndexProbForState(outputIndex+1, state), prob * changeRatio * clacOutIndexProbForState(outputIndex+1, state), outputIndex)
                (preState, prob * changeRatio * clacOutIndexProbForState(outputIndex+1, state))
              }
            }
          }
        }.groupBy(_._1).map(line =>{(line._1, line._2.map(_._2).sum)}).toList
      }
    }
    backward(-1).map(_._2).sum
  }

概率计算

利用前向算法与后向算法合并可得观测概率

$$p(O|\lambda)=\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j),t\in(1...T-1)$$

给定模型$\lambda$和观测$O$，在t时刻处于状态$q_i$的概率

$$r_t(i)={\alpha_t(i)\beta_t(i)\over p(O|\lambda)}={\alpha_t(i)\beta_t(i)\over \sum_{j=1}^N\alpha_t(j)\beta_t(j)}$$

给定模型，在时刻t处于$q_i$以及在t+1处于$q_j$的概率

$$={\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)\over\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}$$

学习问题

已知观测序列，估计模型参数，在该模型下观测序列概率$p(O|\lambda)$最大

监督学习方法

已知训练集中包含S个长度相同的观测序列和对应的状态序列$\{(O_1,I_1),...\}$，那么如下估计参数

转移概率 $a_{ij}$ 的估计

$$\hat a_{ij}={A_{ij}\over \sum_{j=1}^NA_{ij}},j\in(1..N),i\in(1..N)$$

观测概率 $b_j(k)$ 的估计

$$\hat b_j(k)={B_{jk}\over \sum_{k=1}^M B_{jk}},j\in(1..N),k\in(1..M)$$

初始状态概率 $\pi_i$

为S个样本中初始状态为$q_i$的频率

Baum-Welch算法

预测问题

利用

语音识别

在语音识别中用户实际的本意可以表达为 $(s_1,s_2.....)$ 而我们实际识别到的音轨可以表示为 $(o_1,o_2...)$ ,于是需要判断其实际的本意则可以通过如下的概率表示

$$s_1,s_2...=arg\max_{all s_1,s_2...}p(s_1,s_2...|o_1,o_2...)$$ $$=arg\max{p(o_1,o_2...|s_1,s_2...)*p(s_1,s_2...)\over p(o_1,o_2...)}$$

自动纠错

自动纠错与语音识别差不多，区别只在于