HOME/Articles/

1.马尔科夫链

Article Outline

1.马尔科夫链

1.1 定义

假设状态序列为$x_1,x_2,\ldots,x_{t-2},x_{t-1},x_{t},x_{t+1},x_{t+2},\ldots$ $$ P(x_{t+1}| \ldots,x_{t-2},x_{t-1},x_t)=P(x_{t+1}|x_t) $$ 某一个时刻状态转移的概率只依赖于它的前一个状态。

打个比方,一个十恶不赦的坏人一直在做坏事,昨天脑子抽筋、突发奇想做了件好事。那么安照上述规则,今天只依赖于昨天。昨天它做了件好事是个好人,那么今天也会继续做好事成为好人。但是实际上这看起来有问题,因为之前一直做坏事,两者冲突。那么该怎么理解呢?可以这么说,如果他之前一直干坏事,那么昨天突然做好事的概率是很小的,小概率事件可以忽略不计,不应该影响今天的判断。

上述的假设在实际中效果比较好,可以大大简化计算。

1.2 示例

image-20210109211340266

上图中是一个简单的股市例子,包含三种状态${牛市、熊市、横盘}$,右边是状态转移矩阵,表示不同状态之间的转移概率,比如从牛市到熊市的转移概率为0.075,牛市->牛市为0.9,牛市->横盘为0.025。那么知道了昨天的状态,就可以计算今天故事可能的状态。

1.3 马尔科夫链的性质

  • 不可约性
  • 重现性
  • 周期性
  • 遍历性
  • 细致平衡性

2. 隐马尔科夫模型

2.1 定义

隐马尔科夫模型(Hidden Markov Model,HMM):马尔科夫链+一般随机过程

image-20210109213352005

还是以股市为例,此时存在观测状态和不可观测的隐状态,观测状态$V$为{上涨0,下跌1,不变2},隐状态$Q$为{牛市0,熊市1,横盘2}。我们只能看到股票上涨、下跌或者不变,而不知道当前是牛市、熊市还是横盘。当前的股市状态决定了股票是上涨还是下跌,即隐状态决定观测状态。当然,股市是牛市时,股票也有可能下跌或者横盘,所以,在同一个隐状态下可以有不同的观测值。

上图中$B$表示观测状态生成矩阵,$b_0$表示隐状态为牛市时观测到上涨、下跌和不变三种观测状态的概率。因此,有了隐状态(股市状态),结合观测状态生成矩阵,就可以知道观测状态发生的概率。那么,股市的状态就需要一个初始值,即初始状态概率矩阵,表示初始时刻不同隐状态的概率。再结合状态转移矩阵,就可以知道任意时刻观测状态的概率。

上述中,对股市状态即隐状态的判断就是一个马尔科夫链,而股市状态产生观测状态的过程就是一般随机过程。

  • 定义

    隐状态集合 $ Q={q_1,q_2,\ldots,q_N} $,可观测状态集合$V={v_1,v_2,\ldots,v_M}$;

    隐状态序列 $I={i_1,i_2,\ldots,i_T}$,观测状态序列$O={o_1,o_2,\ldots,o_T}$

    状态转移概率矩阵 $$ A=[a_{ij}]{N\times N},a{ij}=P(i_{t+1}=q_j|i_t=q_i) $$ 其中$a_{ij}$表示$t$时刻隐状态为$q_i$,在这个条件下,$t+1$时刻隐状态的值为$q_j$的概率。即当前时刻隐状态为$q_i$,下一时刻为$q_j$的状态转移概率为$a_{ij}$。

    观测状态生成矩阵 $$ B=[b_j(k)]_N \times M ,b_j(k)=P(o_t=v_k|i_t=q_j) $$ 其中$b_j(k)$即$t$时刻隐状态为$q_j$,在这个状态条件下,观测到观测状态为$v_k$的概率。

    隐状态初始概率分布 $$ \Pi=[\pi(i)]_N ,\pi(i)=P(i_1=q_i) $$ 表示初始时刻不同隐状态的概率。

    有了上述概率矩阵,即可以定义HMM模型: $$ \lambda =(A,B,\Pi) $$ 有了初始状态概率分布和状态转移概率分布,就可以知道不同时刻的状态分布概率。再结合观测状态生成矩阵,就可以知道观测值的概率。

  • 三个基本问题

    • 观测状态序列概率

      image-20210109220224458

      即给定模型参数和观测状态序列,求该序列的概率。

    • 模型参数学习

      image-20210109220403267

      即给定观测状态序列集合,求模型参数。通常使用EM算法,求模型参数,使得在该参数下,观测序列集合出现的概率最大,使用极大似然估计求解。

    • 预测(解码)问题

      image-20210109220743868

      即给定模型参数和观测序列,求该观测序列对应的状态序列。也就是知道了股票的涨跌,通过模型参数来预测股市是牛市、熊市还是横盘。

  • 总结

    hmm包括2个假设、5个要素、3个问题

    • 2个假设

      • 齐次马尔可夫假设: HMM 的任一时刻 t 的某一状态只依赖于其前一时刻的状态,与其它时刻的状态及观测无关,也与时刻 t 无关。

        image-20210109221459430

      • 观测独立假设:任一时刻的观测只依赖于该时刻的马尔科夫链的状态,与其他观测及状态无关

        image-20210109221535344

        t+1 时刻的观测只依赖于 t+1 时刻的马尔科夫链的状态,与其他观测状态无关。

    • 5个要素 $$ \lambda =(Q,V,A,B,\Pi) $$

    • 三个问题

2.2观测状态序列概率计算

2.2.1 暴力穷举法

观测状态序列$O={o_1,o_2,\ldots,o_T}$,模型参数$\lambda =(A,B,\Pi)$

给定观测状态序列O和模型参数$\lambda$,求该序列出现的概率。 $$ P(O|\lambda)=\sum IP(O,I|\lambda) $$ 上式表示模型已知的情况下,给定隐藏状态,观测状态发生的概率。即对不同的隐状态给定模型参数$\lambda$时,观测状态处理的概率进行求和。举例说明:在时刻1,观测到状态为“上涨0”,此时根据初始概率矩阵和观测状态生成矩阵可以计算出"牛市0,上涨0的概率","熊市2,上涨0的概率"和"横盘2,上涨0的概率",将三个概率值相加即为时刻1观测状态为"上涨0"的概率。 $$ P(O,I|\lambda)=P(I|\lambda)P(O|I,\lambda) $$ 上式表示给定模型参数,求隐状态和观测状态发生的概率。$P(I|\lambda)$表示给定模型参数隐状态发生的概率(比如模型已知,当前是牛市的概率)。$P(O|I,\lambda)$表示模型参数和隐状态已知观测状态发生的概率(当前是牛市,观测到股票上涨的概率)。 $$ P(I|\lambda)=\pi{i_1}a_{i_1i_2}a_{i_2i_3}\ldots a_{i_{T-1}i_T} $$ 上式表示隐状态初始概率分布和状态转移概率矩阵相乘。同样: $$ P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2) \ldots b_{i_2}(o_T) $$ 上式表示观测状态生成矩阵,因此: $$ P(O,I|\lambda)=P(I|\lambda)P(O|I,\lambda)=\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)a_{i_2i_3} \ldots b_{i_T}(o_T) $$ 所以: $$ P(O|\lambda)=\sum IP(O,I|\lambda)=\sum _{i_1,i_2,\ldots,i_T}\pi{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)a_{i_2i_3} \ldots b_{i_T}(o_T) $$ 即对所有的隐状态下的$P(O,I|\lambda)$求和。

上述穷举方法直接有效,但当隐藏状态较多时,复杂度太大。

2.2.2 前向算法

定义前向概率 $\alpha _t(i)=P(o_1,o_2,\ldots o_t,i_t=q_i|\lambda)$,表示给定模型参数,在$t$时刻隐状态为$q_i$的情况下,观测序列($o_1,o_2,\ldots,o_t$)出现的概率。

知道$t$时刻隐藏状态$i(i=1,2,\ldots,N)$的前向概率$\alpha t(i)$,即可求出$t+1$时刻隐藏状态为$i$的概率: $$ \alpha _{t+1}(i)=[\sum{j=1} ^N \alpha_t(j)a_{ji}]b_i(o_{t+1}) $$ 上式表示在$t$时刻的前向概率为$\alpha t(j)$乘以状态转移概率$a{ji}$,然后对$t$时刻所有的状态求和,再乘以$t+1$时刻状态$i$观测到$o_{t+1}$的概率值。因为在$t$时刻存在不同的状态中,都可以像$t+1$时刻的状态进行转化,所以需要求和。

由此可知,知道了$t$时刻隐藏状态为$q_i$的概率,即可求$t+1$时刻隐藏状态的概率。在已知初始状态概率分布、观测状态生成矩阵和状态转移概率矩阵的情况下,即可求给定观测状态序列的概率值。 $$ \alpha _1(i)=\pi _i b_i(o_1),i=1,2,\ldots,N $$ 上式表示初始时刻的前向概率,即初始时刻隐状态为$q_i$,观测状态为$o_1$的概率。知道了初始时刻的前向概率,即可迭代求$T$时刻的观测序列发生的概率: $$ P(O|\lambda)=\sum _{i=1}^N \alpha _T(i) $$ $\alpha _T(i)$表示$T$时刻隐藏状态为$q_i$观测序列为$O$的概率,对所有的隐状态概率求和即得观测序列$O$的发生概率。

上述即为前向算法求观测状态序列的概率。

2.4 解码问题

给定模型参数$\lambda =(A,B,\Pi)$和观测状态序列$O={o_1,o_2,\ldots,o_T}$,求观测状态序列对应的概率最大的隐藏状态序列。一般使用维特比(viterbi)算法求解。

定义局部状态: $$ \delta_t(i)=\max_{i_1,i_2,\ldots,i_{t-1}}P(i_t=i,i_1,i_2,\ldots,i_{t-1},o_t,o_{t-1},\ldots,o_1|\lambda),i=1,2,\ldots,N $$ 表示在是时刻$t$隐状态为$i$所有可能的状态转移路径中概率最大的路径概率。 $$ \Psi t(i)=\arg \max _{1 \leqslant j \leqslant N}[\delta _{t-1}(j)a{ji}] $$ 表示时刻$t$隐状态为$i$的所有状态转移矩阵中概率最大的转移路径中第$t-1$个节点的隐藏状态也就是在$t-1$时刻有$N$和节点可以转移到$t$时刻的状态$i$,选择其中概率最大的节点。

知道了$t$时刻隐状态为$i$的概率最大路径概率,也可以相应算出$t+1$时刻状态为$i$的所有可能状态转移概率路径中概率最大的路径概率。 $$ \delta_t(i+1)=\max_{i_1,i_2,\ldots,i_{t}}P(i_{t+1}=i,i_1,i_2,\ldots,i_{t-1},i_t,o_{t+1},o_t,o_{t-1},\ldots,o_1|\lambda) \ =\max {1 \leqslant j \leqslant N}[\delta _{t}(j)a{ji}]b_i(o_{t+1}) $$ 初始化: $$ \delta_1(i)=\pi_ib_i(o_1),i=1,2,\ldots,N \ \Psi_1(i)=0,i=1,2,\ldots,N $$ 计算局部状态: $$ \delta t(i)=\max _{1 \leqslant j \leqslant N}[\delta{t-1}(j)a_{ji}]b_i(o_t),i=1,2,\ldots,N \

\ \Psi_t(i)=arg \max {1 \leqslant j \leqslant N}[\delta _{t-1}(j)a{ji}],i=1,2,\ldots,N $$ 计算最可能隐藏状态序列出现的概率: $$ P^=\max_{1 \leqslant j \leqslant N} \delta_T(i) $$ 计算时刻T最可能的隐藏状态: $$ i_T^ =arg \max {1 \leqslant j \leqslant N}[\delta _T(i)] $$ 计算每一时刻的最可能状态: $$ i_t^=\Psi _{t+1}(i^{t+1}) $$ 从而可得最终的隐藏状态序列: $$ I^={i_1^,i_2^,\ldots,i_T^} $$

参考

[1] 隐马尔科夫模型详解_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili