Article Outline
TOC
Collection 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 示例
上图中是一个简单的股市例子，包含三种状态${牛市、熊市、横盘}$，右边是状态转移矩阵，表示不同状态之间的转移概率，比如从牛市到熊市的转移概率为0.075，牛市->牛市为0.9，牛市->横盘为0.025。那么知道了昨天的状态，就可以计算今天故事可能的状态。
1.3 马尔科夫链的性质
- 不可约性
- 重现性
- 周期性
- 遍历性
- 细致平衡性
2. 隐马尔科夫模型
2.1 定义
隐马尔科夫模型(Hidden Markov Model,HMM)：马尔科夫链+一般随机过程
还是以股市为例，此时存在观测状态和不可观测的隐状态，观测状态$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) $$ 有了初始状态概率分布和状态转移概率分布，就可以知道不同时刻的状态分布概率。再结合观测状态生成矩阵，就可以知道观测值的概率。
三个基本问题
观测状态序列概率
即给定模型参数和观测状态序列，求该序列的概率。
模型参数学习
即给定观测状态序列集合，求模型参数。通常使用EM算法，求模型参数，使得在该参数下，观测序列集合出现的概率最大，使用极大似然估计求解。
预测(解码)问题
即给定模型参数和观测序列，求该观测序列对应的状态序列。也就是知道了股票的涨跌，通过模型参数来预测股市是牛市、熊市还是横盘。
总结
hmm包括2个假设、5个要素、3个问题
2个假设
齐次马尔可夫假设： HMM 的任一时刻 t 的某一状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻 t 无关。
观测独立假设：任一时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关
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^} $$