数学聊妞之HMM的应用

我曾经以为,到了这样的年纪,自然就能结婚......

大家好，今天给大家带来一篇拿来就能用的算法讲解。现在咱们假定这么一个场景：小王是我的好同学，一直苦于没有妞。这两天不知从哪搞来一个心仪姑娘的手机号。据他表述，头两天聊的还行，发的信息姑娘没有不回也没感觉到敷衍，而且就着一个问题还可以深入的聊下去。但是今天不知怎的，突然就不回了。于是小王痛苦啊，满地打滚，虽然都还没恋上但依旧感觉自己已经失恋了。

这时我们肯定要帮他分析，安慰他，blabla说了半天，其实根本没用。因为小王同学曾经的坎坷感情经历告诉他，美好都是短暂虚幻的，失败却永远不会欺骗你的眼睛。既然小王已经精神崩溃，油盐不进。那么我们就需要用数学方法客观公正的帮他分析情况，做出判断。

根据情况，我们可以选用隐马尔可夫模型进行计算，简称HMM。下面先来了解一下这个模型。

什么是HMM？

  隐马尔可夫模型（Hidden Markov Model，HMM），是一种统计学模型，创立发展于二十世纪七八十年代，在信号处理领域有着非常重要的地位，这种模型在解决语音识别，机器翻译等问题上都有着很强的能力。这方面大家有兴趣的话可以给你们推荐一本书《数学之美》，谷歌吴军写的。里面有更详细有趣的介绍。

先来说说马尔可夫过程

简单来说，大家看到交通灯时，可以根据目前的颜色判断出下一个颜色将会是什么，假定现在看到红灯，那么可以判断出

红—绿—黄—红，这就构成了一个确定性系统，它的每个状态，和转移方向都是已知的。但是现实中还存在着许多不确定系统。

当然这只是举个很糟糕例子，假如咱们刚才看到的交通灯坏了，如上图。在这种情况下，我们很难根据目前的颜色推出下一个颜色，如果我们仍旧希望根据现有状态做出判断的话，我们需要假设，每一个状态的转移只依赖于上一个状态，这个假设成为马尔可夫假设。但是这种转移是有概率的，并非确定性。也就是说对于这种灯，如果现在观察到红色，那么下一个颜色有红，黄，绿三种可能性，每种可能性都有自己的概率。这样我们现在得到了一个马尔可夫过程。

隐马尔可夫模型隐藏了什么

隐马尔可夫模型描述的是一个含有隐含未知参数的马尔可夫过程，用上面那个坏的交通灯来说，假如我们所处的路口就有这么一个坏的交通灯，但我们观察不到灯的颜色，只能看到路面情况。如果想据此知道一段时间内交通灯变化的最可能情况，我们就要用到隐马尔可夫模型。



如果我们已经认为坏了的交通灯转移规律符合马尔可夫过程，那么在这个问题上，隐马尔可夫模型隐藏的就是灯的可观测状态。

Viterbi算法

对于给定的HMM模型，想解得结果我们当然可以使用穷举法，但是这种方法使用代价非常大，特别是对于较长的序列。可以利用这些概率的时间不变性来降低计算复杂度，所以我们引入一种动态规划算法viterbi算法。



对于每一种颜色，我们都能找到一个变化到该颜色的概率最大方式，或称为最短路径，每一个最短路径都有一个概率，即局部概率。我们便利用局部最优来确定最可能的路线。下面给出viterbi公式：



那么能帮小王做些什么？

上面我们定性的介绍了一下HMM，现在我们回归问题的开始，用HMM来帮小王同学解决难题。

我们先对情况进行分析，小王之所以郁闷，究其深层原因是害怕姑娘对他的印象不好，回不回信息只是表面现象。小王给提供了连续三天的情况，属于时间序列。人与人之间的印象，很大程度上取决于上一个时间节点。人做出决定很难做到全局最优，一般会追求局部最优，所以我们的目标是求得最有可能的转变路径。这三点请大家仔细体会。经过分析，此问题可以归于HMM模型，用Viterbi算法求解比较合理，可以取得较好结果。

下面我们对实际情况进行简化抽象。

假设小王在姑娘心中只有三种可能的印象：

S1：较好，S2：一般，S3：较差。

这三种情况其实就是对应上面红绿黄三种颜色，也就是说这是不可直接观测到的，只能根据对方短信回复判断。

根据小王所说，姑娘之前并不认识他，所以假定最初时刻小王在姑娘心中印象为S2：一般。

假设姑娘的回复只有三种可能的情况：

X1：不回，X2：敷衍，X3：有实质内容的沟通。

难点在于设置参数，这个参数设置不是固定的，如果有大数据支持可以进行模型训练，可惜在没有这个条件的情况下，只能根据自己多年聊妹经验粗略给出参数。

下面基于自设参数开始构建状态转移矩阵aij：



混淆矩阵bij：



根据Viterbi算法：



求得小王在姑娘心目种的最可能的情况是：



结果分析

  目前预设参数不变的情况下，小王在姑娘心目中印象为一般的可能性远胜较好与较差，基本可以确定为一般，但是根据转移矩阵（上图中也标出相应概率），未来的发展很难维持一般水平，基本上属于比较关键的时期，向较好发展的概率略胜一筹。结果基本符合常识，可以作为参考。

告诉小王

嗯，经过科学的分析与计算，你可以放心，起码可以负责任的告诉你，对方并没有对你有什么坏印象。现在的情况属于正常。往后的发展基本面向好，但是目前状态不稳定，在此阶段应保持稳定发挥，勿出奇招怪招。

写在最后

能读到最后的朋友，首先向你们表示感谢，祝你们依旧肠道畅通，挥洒自如。如果你们在文中发现那些技术性错误，请不吝赐教。

正处在纠结阶段的朋友们，也不妨试试用这个模型计算一下自己的处境，使用时注意参数的选取，如果哪个倒霉蛋有这方面的大量数据，欢迎提供以便训练模型。投稿地址：pojiziwowuyu@sina.com


或添加微信：

    关注 我与王特们