机器学习——隐马尔可夫模型HMM
目前的博客还是侧重于数学公式，方便自己复习，等忙过秋招就尽量做到雅俗共赏~~
1 HMM定义
隐马尔可夫模型是什么？有什么作用？数学公式是什么？
隐马尔可夫模型是一种时序（时间上的联系）的概率模型，用在词性标注，记住一个东西，例子+图。
例子就是，通过可看见的推测不可看见的，比如医生问诊，根据你身体状况（可以观察的到的，外在表现）来判断疾病。韩梅梅医生不仅要看你目前的身体状况，还会问你昨天的身体状况，也就是参考邻近的时间的观测信息。
HMM是一个时序模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态的序列，再由各个状态随机生成一个观测而产生观测的序列的过程。（很绕，但定义嘛，还是得根据书上来）绕没关系，断句理解。
1 什么是马尔可夫链？（马尔可夫链当前状态只和上一个状态有关，而和上个状态之前的状态无关）
2 各个状态 随机生成 一个观测（一对一） 而产生 观测的序列 的 过程？（这个的意思是，确定了当下，就能预测明天，然后到了明天，又能预测明天 这么个时间序列的过程）
所以要想描述清楚这个HMM，记住它的五个基本要素：（结合图）
HMM七个元素（O, I, X,Y,π，A, B），I是时间长度为T状态序列（下图{y1,y2,y3,y4），O是对应的观测值，下图的{x1,x2,x3,x4}。
Y是状态（输出）所有取值的集合，X是观察值（输入）所有取值的集合，π是初始状态的概率，A是状态转移概率矩阵，B是输出观察值概率矩阵。
看图解释！！！
情景：假设通过观测小明今天点菜是点辣的还是清淡的，来判断小明今天有没有上火：
现在还差个π了，π能是状态的初始概率值，比如，小明上火的概率是0.2，不上火的概率是0.8，那么π是（0.8,0.8,0.2,0.2）。
假设Y所有取值个数是N，X所有取值个数是M，时间序列长度是T，那么请记住：
A只和Y有关，根据定义，它是一个NXN的矩阵，枚举所有状态Y转换
B既和A有关又和M有关，根据B定义这是个NxM的矩阵，枚举所有状态Y转换到观测X
π的是状态初始概率分布，即在，没时间状态约束的情况下，Y的每个取值的概率，所以也只跟Y有关，长度为1xN
一般呢，我们把模型 λ（ A, B，π） 表示HMM模型。HMM有7个要素，根据已知哪些求哪些分为3个问题：
（1）给定模型λ（ A, B，π）和O，求P(O|λ)——这个是概率计算的问题
（2）给定O，求λ（ A, B，π）——这个是个学习的问题，一般是最大化P(O|λ)，然后使用最大似然估计法估计参数
（3）给定模型λ（ A, B，π）和O，求最优可能的I——这个就是预测问题了，准则就是P(I|O)最大
这三种场景对应的算法也不一样，（1）前向-后向算法求解（有点像神经网络的传播），根据前向-后向算法也是Baum-Welch算法中求概率和期望的方法；（2）学习问题的算法是Baum-Welch（EM+最大似然估计，生成模型）；（3）维特比算法（动态规划）
以下展开介绍。
2 概率计算算法
因为是时间序列，所以必须按时间先后的顺序。基本就是先确定t=0，由t=0确定t=1，t=1确定t=2。截个图吧，不想打了。建议理解的时候自动脑补类似于神经网络的图。
前向算法，t=0开始推导：
前向算法，t=T开始推导：
2.1 一些期望与概率的计算（学习算法和预测算法都需要）
3 学习算法
回忆一下EM算法，EM是求含有隐变量的条件概率问题，而这个HMM不就是包含隐变量吗？
（已知输出状态O，求参数λ(A,B,π)）
使用EM算法，估计参数，来最大化条件概率P(O|λ)=∑P(O|I,λ)P(I|λ)。
1 E步，确定期望E的下限：
初始化 ，确定P(O|λ)的期望的下限Q：
2 M步，极大化Q，来求得 模型参数A,B和π：
这三个参数，是学习而得的，可根据前向-后向算法求取。
4 预测算法（解码）
已知输出状态O和模型参数λ，求最可能的隐状态I。从例题入手去理解维特比算法。
假设3个箱子，每个箱子拿 红/白球的概率已知（混合矩阵B），3个箱子出现的概率也已知（π），当前状态是箱子j，下个状态是箱子i的概率也知道（状态转移矩阵A）。小明依次拿了3个球，分别是{红，白，红}，求这3个球对应的箱子应该是？
我觉得用高中的思想去看这道题会更好。
第一步，拿出红球的概率，它有3个取值：
P(i=1；o=红|λ) = 0.2*0.5 = 0.1
P(i=2；o=红|λ) = 0.4*0.4 = 0.16
P(i=2；o=红|λ) = 0.4*0.7 = 0.28
第二步，第一次是红球，第二次是白球的概率，则需要求：
P(i=1，1；o=白，红|λ) P(i=1，2；o=白，红|λ) P(i=1，3；o=白，红|λ)
P(i=2，1；o=白，红|λ) P(i=2，2；o=白，红|λ) P(i=2，3；o=白，红|λ)
P(i=3，1；o=白，红|λ) P(i=3，2；o=白，红|λ) P(i=3，3；o=白，红|λ)
但因为这是求最佳路径，这就用到了动态规划的思想。我们发现P(i=1，1；o=白，红|λ) 和P(i=1，2；o=白，红|λ) 和 P(i=1，3；o=白，红|λ)不管他之前的状态，在t=2时他们都在状态i=1上，那也就是说，接下来t=3,4，...，T他们面临的路是一样的，我是要选最优路径的，那肯定选择t=1——>t=2状态为i=1的最优路径了（比如每个学校要派个同学去参加竞赛，你是校长是不是会立马选择成绩最好的那个？）。即：
取max{P(i=1，1；o=白，红|λ) ， P(i=1，2；o=白，红|λ) ，P(i=1，3；o=白，红|λ) }
同样对t=2，状态为2、3依然选择最优的路径：
max{P(i=2，1；o=白，红|λ) ， P(i=2，2；o=白，红|λ) ，P(i=2，3；o=白，红|λ) }
max{P(i=3，1；o=白，红|λ) ， P(i=3，2；o=白，红|λ) ，P(i=3，3；o=白，红|λ) }
则：
max{ P(i=1；红|λ)*P(i=1-->i=1) P(i=2；红|λ)*P(i=2-->i=1) P(i=3；红|λ)*P(i=3-->i=1) }*P（i=1-->o=白），得到：
P(i=1，3；o=白，红|λ) = P(i=3；红|λ) *P(i=3-->i=1)*P（i=1-->o=白）=0.28*0.2*0.5=0.028
P(i=2，3；o=白，红|λ) = 0.0504
P(i=3，3；o=白，红|λ) = 0.042
同理算出t=3的时候：
max{P(i=1，1，3；o=红，白，红|λ) ， P(i,=1，2，3；o=红，白，红|λ) ，P(i=1，3，3；o=红，白，红|λ) }
max{P(i=2，1，3；o=红，白，红|λ) ， P(i,=2，2，3；o=红，白，红|λ) ，P(i=2，3，3；o=红，白，红|λ) }
max{P(i=3，1，3；o=红，白，红|λ) ， P(i,=3，2，3；o=红，白，红|λ) ，P(i=3，3，3；o=红，白，红|λ) }
则：
P(i=1，2，3；o=红，白，红|λ) = 0.00756
P(i=2，2，3；o=红，白，红|λ) = 0.01008
P(i=3，3，3；o=红，白，红|λ) = 0.0147
这个时候，我知道最大的概率是P(i=3，3，3；o=红，白，红|λ) = 0.0147
则，最优路径应该是 3-->3-->3，因为这条路径概率最大。
以下就是维特比算法：
就是我们上个例题的P(I=i,it-1,..,i1; O=o, ot-1,..,o1|λ)
而就看成是最优路径。