三胖导弹能否打偏，主要取决这个算法

在遥远的东方，渤海湾往东再走一点，有这样一个民族，他们有一个伟大的领袖，他的名字叫“河蟹”。“河蟹”有一个爱好就是扔导弹，今天我们就来讨论下这个导弹发射准确性的问题，主要取决一个算法—马尔科夫链。关于马尔科夫链的八卦大家可以自行上网搜索，比如冷战的时候苏联的导弹如何牛逼之类的，都是因为马尔科夫。

今天我们摘取一部分《机器学习实践应用》中的关于隐马尔科夫的片段，给大家介绍下这个算法，算法有点绕，可能得认真跟着走一遍就了解了，可以脑子里模仿导弹的行驶路径。

隐马尔科夫（HMM）主要可以用来解3种基本问题：评估问题（Forward-backward算法）、解码问题（Viterbi算法）、学习问题（Baum-Welch算法）。这3种问题的区分主要是依赖于算法的输入，我们可以把HMM算法模型输入分为五元组.

• InitStatus：初始状态集合。

• StatusSet：状态值集合。

• ObservedSet：观察值集合。

• TransProbMatrix：转移概率矩阵。

• EmitProbMatrix：发射概率矩阵。

解码问题的本质上是寻找最优的隐状态序列，通常是利用Viterbi算法来解，Viterbi算法是已知InitStatus、ObservedSet、TransProbMatrix、EmitProbMatrixsi，求解StatusSet的方法。Viterbi算法的理论是：下一步的状态会依赖前一步的状态和当前可观察的状态。下面看一下具体的Viterbi算法的推导过程。

为了更生动的表示算法的意义，我们采取一个生活中的场景进行具体的数值推导。假设有一个人B，他有3种状态分别是笑、无表情、哭，通过观察他的表情推测出他的隐含状态：高兴或者不高兴。这里假设我们的转移概率矩阵和发射概率矩阵等都是经过训练得到的最终结果（具体数值表示概率值），我们看下具体的推导过程是怎样实现的。

（1） 输入的5项式结果

• 首先看下初始状态，InitStatus的两种状态：InitStatus={高兴：0.6,不高兴：0.4}；

• 隐含的心情状态，StatusSet={高兴、不高兴}；

• 观察到的状态，ObservedSet={笑，无表情，哭}；

• 转移概率矩阵，TransProbMatrix=

  ，具体的含义是高兴-》不高兴的概率P(不高兴|高兴)=0.4，高兴-》高兴的概率是P(高兴|高兴)=0.6，不高兴-》高兴的概率P(高兴|不高兴)=0.7，不高兴-》不高兴的概率P(不高兴|不高兴)=0.3。

• 在相应心情状况下的表情概率，EmitProbMatrix=

这个矩阵的具体含义是高兴心情下的状态概率：

{高兴：P(笑)=0.6，P(无表情)=0.3，P(哭)=0.1}，

不高兴状态下的概率：

{不高兴：P(笑)=0.2，P(无表情)=0.2，P(哭)=0.6}

（2） 具体推导

假设我们观察到的B最近3天的表情分别是：笑、无表情、哭，我们来通过Viterbi算法推导下B这3天的心情是怎样的。

• 第1天的心情：由初始状态InitStatus得到，P(高兴)=0.6，P(不高兴)=0.4，这个是初始值。因为第一天的表情的观察状态是“笑”。所以第1天的心情：

P(高兴)=P(笑|高兴)*P(高兴|初始状态)=0.6*0.6=0.36

P(不高兴)=P(笑|不高兴)*P(不高兴|初始状态)=0.2*0.4=0.08

这里应用到了发射概率矩阵，第1天的P(高兴)> P(不高兴)，所以第1天的心情是高兴的可能性比较大。

• 现在来推算第2天的状况：第2天的表情是“无表情”，第2天的状态有4种可能：

P(前一天高兴，今天高兴)=P(前一天高兴)*P(高兴->高兴)*P(无表情|高兴)=0.36*0.6*0.3=0.0648

P(前一天高兴，今天不高兴)=P(前一天高兴)*P(高兴->不高兴)*P(无表情|不高兴)=0.36*0.4*0.2=0.0288

P(前一天不高兴，今天高兴)=P(前一天不高兴)*P(不高兴->高兴)*P(无表情|高兴)=0.08*0.7*0.3=0.0168

P(前一天不高兴，今天不高兴)=P(前一天高兴)*P(不高兴->不高兴)*P(无表情|不高兴)=0.08*0.3*0.2=0.0048

这里涉及到了TransProbMatrix和EmitProbMatrix，计算的结论是第2天B的心情是高兴的可能性最大，因为结果是“今天高兴”的两个概率值之和较大。

• 下面来看下第3天的情况，第3天我们观测到B的表情是“哭”，跟上一天的推导类似，第3天的公式如下：

P(前一天高兴，今天高兴)=P(前一天高兴)*P(高兴->高兴)*P(哭|高兴)= (0.0648+0.0168)*0.6*0.1=0.004896

P(前一天高兴，今天不高兴)=P(前一天高兴)*P(高兴->不高兴)*P(哭|不高兴)= (0.0648+0.0168) *0.4*0.6=0.019584

P(前一天不高兴，今天高兴)=P(前一天不高兴)*P(不高兴->高兴)*P(哭|高兴)=( 0.0288+0.0048)*0.7*0.1=0.002352

P(前一天不高兴，今天不高兴)=P(前一天高兴)*P(不高兴->不高兴)*P(哭|不高兴)= ( 0.0288+0.0048)*0.3*0.6=0.006048

所以通过计算可以推断出，第三天B的心情是不高兴，因为推导出今天不高兴的两个概率的和较大。

最终，通过3天的表情：笑-》无表情-》哭，可以推出他的心情是高兴-》高兴-》不高兴。以上是通过一个日常生活中的案例来描述如何利用InitStatus、StatusSet、ObservedSet、TransProbMatrix、EmitProbMatrix这5个输入，通过Viterbi算法进行推导，对隐藏的状态实现概率层面的推理。