复习， 状态序列（state sequence），观测序列（observation sequence）
问题一 概率计算问题
转载链接：https://zhuanlan.zhihu.com/p/27056207
给定模型的情况下，求某种观测序列出现的概率。
一般方法： 前向、后向算法
举例来说明一下，例子如下：（例子来源于*）
考虑一个村庄，所有村民都健康或发烧，只有村民医生才能确定每个人是否发烧。医生通过询问患者的感受来诊断发烧。村民只能回答说他们觉得正常，头晕或感冒。
医生认为，他的患者的健康状况作为离散的马可夫链。 “健康”和“发烧”有两个状态，但医生不能直接观察他们;健康与发烧的状态是隐藏的。每天都有机会根据患者的健康状况，病人会告诉医生他/她是“正常”，“感冒”还是“头昏眼花”。
比如，给定的HMM模型参数已知，求出三天观察是(Dizzy,Cold,Normal)的概率是多少？对应的HMM模型参数已知的意思，就是说A(trainsition_probability),B(emission_probability),pi 矩阵是已经知道的。
这里仅算两天
这个问题我们最容易想到的解法就是将路径全部遍历一遍，
假如第一天为 Healthy
第一天为Healthy的概率为：0.6
在第一天为Healthy的基础上，观察为Dizzy的概率为：
P（Dizzy|Healthy）=0.6P(Healthy->Dizzy)=0.6*0.1=0.06
然后求出在第一天为Healthy的基础上，并且第一天表现为Dizzy的前提下，第二天也为Healthy的概率为：
P(Healthy|Healthy,Dizzy)=0.06p(Healthy->Healthy) = P(Dizzy|healthy)07 = 0.06*0.7
可以看出，一条路径已经求解完了。之后按这个思路求解其他三条路径。之后相加就好了。
问题： 实际中的隐状态个数非常大， 那么我们的计算量是无法忍受的。从图中可以看出，它是随着观测序列长度的增加呈指数级变化。（一旦遇到指数级，就像坐火箭一样，多一个数量都是灾难）
暴力法并不实用。
前向算法
我们首先定义一下前向概率
已知：模型 λ、
求解概率（前向概率）： 时刻 t 之前的观测序列为 O1,O2,……，Ot 且此时状态为 qi 的概率。
下面，我们可以整理一下前向算法的流程：
输入：隐马尔可夫模型 λ，观测序列 O
输出：观测序列概率 p(o| α）
-
（1）初值
前向概率的定义中一共限定了两个条件，一是到当前为止的观测序列，另一个是当前的状态。所以初值的计算也有两项（观测和状态），一项是初始状态概率，另一项是发射到当前观测的概率。 -
（2）递推对t=1,2,3,…,T-1
每次递推同样由两部分构成，大括号中是当前状态为i且观测序列的前t个符合要求的概率，括号外的是状态i发射观测 t+1的概率。 -
（3）终止
慢慢分析： ——把大象装入冰箱，大声告诉我有几步？
步骤（1）初始化前向概率，是初始时刻的状态 i1 = qi 和观测 o1 的联合概率。 也就是我们给个序列的起点，然后再说怎么往后推。
步骤（2），这是关键点，就像我们写递归程序一样，写好递归步骤一样。
计算前向概率（到时刻 t +1 部分观测序列为 ~，且在时刻 t +1 处于状态 qi ）
其实就是一个映射的过程
即我们的思路是： 从 t 时刻开始 ， 先把 t+1 时刻的第一个状态 q1 的前向概率算出来， 然后再对 t + 1 时刻的所有状态， q1, q2…等等求和， 再把 t + 2 时刻第一个状态 q1 的前向概率算出来，如此循环往复。直到求出概率。
前向算法好在哪里？
与暴力算法对比，它把计算的值都给存起来了，而不是像暴力算法一样，很多值都是重复计算，没有存起来的机制。
利用前向概率计算 P(O | λ） 的计算量是 O(N2T) 阶的， 而不是直接计算的 O(TNT)。
为什么是这样的呢？ 因为我们可以看出，暴力算法其实是计算每一条路径，而路径是随着观测序列越长呈指数级增长，示意图：
所以是 NT 条路径，又因为每个状态对应 T 个观测值， 所以是 TNT 。
而前向算法其实也没什么高明之处，需要求和的步骤都没有少，只是利用了一些优化手段，如下图，让它变成一个块，一个块的计算，而不是一条路径的计算，这样就可以消去指数变化
再看下面这张图， 之前讲到过，先求 t+1 时刻的 q1 状态前向概率，然后求和 t+1 时刻的 q1、q2等，求出 t +2 时刻 q1前向概率，如下所示，其实就是先集中求 q1, 这里需要 N 次（状态数量之和），然后再集中求 q2 ，一直求完qN 的前向概率，这里就变成了 N x N 次， 然后把它们求乘以发射概率,得到下一个时刻的 q1。一共递推 T次。