隐马尔可夫链
看到这篇文章突然想到概率图模型，记得当时学习的时候留下一些问题，有时间回看一下，这篇blog主要是读完知乎一篇文的感悟
回到正题，我对马尔科夫链的认识是有一个最主要的特点，就是状态转移矩阵，意味着状态转移的概率是与时间无关的
隐马尔可夫链其实就是在马尔可夫链的基础上加了一条，每个状态分别由相应概率的观测值，我想这种问题一般发生在观测值与真实值不同，或者有两层的真实值，底层的真实值符合马尔可夫链的转移规律，顶层的真实值由底层的值具有的特性决定一个概率分布（暂时没想到别的应用场景）比如根据风力判断是否下雨
重点来力，同一时刻的状态才能影响对应观测值，也就是其他时间的状态（一般是之前时间）不会影响，挺符合逻辑的，事实上在后面的证明中有大用
这种模型一般有特定的应用场景（马尔可夫链的应用场景就挺固定的了，再加上预测值。。。），那就介绍俩典型问题，据说还有个关于EM的概率问题，以后的blog会补充
典型问题
| 评判问题：给定转移规律和初始状态，如何快速计算 P(指定T时间序列的观测值O1O2O3…Ot | 给定条件) |
看起来不是很难的题，不过他问的是如何快速计算
要是暴力就是每个时刻的可能状态用贝叶斯概率加起来？指数级复杂度。。。
这里介绍向前法（名字很土），公式在原文不贴了，构造一个迭代样式的序列
该序列特殊之处在于将t状态和t及其之前的所有观测值作为所求概率
且仅与此刻t有关，过程中不引入具体状态的值，最终结果也是按所有T时刻状态的概率相加
方法精髓在于利用条件独立以及同一事件的概率归一性
解码问题：给定转移规律和初始状态，再给定一段时间序列的观测值，如何选取使这个观测值概率最大的状态序列？
这个问题倒是挺有应用场景，原来误以为是后验概率，后来想想选择的状态序列也在概率的事件里，也就是就算有一种状态序列可能性最大，他产生的观测序列可能性也许反而小，最终他反而不会是最优解
维特比方法（有点类似动态规划），证明方法有效性可以通过反证法，就不多详述了
留个疑问
发现这两种问题都不会碰后验：给定观测值求最大可能的状态值，有一种模糊的想法，上述两种解法都是前向的，后验可能会引入反向的计算？
| 有点想法：给定转移规律后，要是给定观测求最大概率的状态，那么每个时刻分别利用状态到观测的概率分布就可以用后验求出来了，但是由于马尔科夫链的特性，状态可以前向影响状态，观测不能影响包括自己时刻内的所有状态，这个时刻可能是状态A最适合观测值A~，但是下个状态B不容易从A转来，而B恰是B~的最适合状态 P(Q | O)=P(O | Q)*P(Q) / P(O), P(O)可以用第一题求，P(Q)直接连乘求得，P(O | Q)根据状态只影响当前观测也可以求 |
| *所以P(Q | O)和P(Q,O)是两个问题！ 和求P(Q,O)最大值更是两个问题* |
| 误认为P(Ot+1 | qt）意味着qt会影响Ot+1，后来发现Q序列给定后qt+1也是给定，P(Ot+1 | qt) != P(Ot+1 | qt+1) = P(Qt+1 | qt+1，qt) |
| 解码问题求P(Q,O)最大值其实就是P(Q | O)*P(O)最大值，在O给定情况下也就是后验概率P(Q | O)最大值，所以疑问是不对的，解码问题隐藏的就是后验 |
而他采用的max我认为就是一种回溯的动作，选取适合观测值同时也大概率从前状态序列转移的此刻状态，不过没有考虑对状态序列在此时刻后的状态的影响，这一点可以这样理解，max保证每一阶段的各种状态都保持最大可能，虽然是从前一阶段的最大可能中选出的，但也无形中保持到下一阶段，让下一阶段不管从那个状态转移而来都是最大可能的情况，换句话说，就算每个单独的状态对应概率可能对后续产生影响，但是max没有因过程中某状态的概率大小而筛选，因此整体来看都是保持最优的，他们只关心如何从前一阶段继承并同时匹配现阶段的观测值，最后一阶段再做选择！
| 终于理清之前的困惑在哪了，准确来说，对于求P(Q | O)问题，我之前在中间求某一个状态时认为评判的标准是P(qt | qt-1) * P(Ot | qt) * P(Ot+1Ot+2…. | qt)，这种思路看起来合理，求解也能求，就是考虑从上一时刻转换的概率乘上适合观测的概率再乘上对今后观测值的影响，乍一看确实是求得了此时的最优，但是事实上每经过一次迭代计算就会在这个时刻固定一个qt，这就不考虑前一时刻状态转换来源了，其实很好推翻，第一时刻的状态下A可能是P(O1O2.. | q1)最优解，但A不一定是 max{P(O1O2….，q1qt2q3…)}中q1的解 |
| 再者，如果评判标准是P(qt | qt-1) * P(Ot | qt) * max{P(Ot+1Ot+2….，qtqt+1qt+2…)}那其实也可以推翻，在某一时刻选状态用的max中某一后续时刻的状态，到选该时刻的状态时不一定最优值就是那个状态了，就与前面矛盾 |
也就是说，上述方法就算保证此刻状态对后续预测合适，但不能保证该状态在最优值序列里面，但是维特比方法就可以保证始种都是最优值