|
0 故事背景 有个男生只要晴天就高兴，他想和远在千里的女友玩个游戏，只告诉他的心情，让女友猜他当地的天气。 女友很了解他，想既然你今天高兴，那么今天是晴天。 第二天，男生说我今天不高兴，问女朋友天气如何？ 女友很了解他，想既然你今天不高兴，那么今天是雨天。 女友把这个男生卡的死死的，因为
因此可以完美根据他的心情来判断天气，这个规则就是：
如下图所示： 但人的心情不会这么简单，不可能根据天气而一成不变。让我们看看一个稍微复杂的情况：
如下图所示： 如果男生说这三天心情是“高兴-烦躁-高兴”，那么女友可能推断出（不是 100% 确定）天气是“晴天-雨天-晴天”。 如果男生这一周心情像过山车，隔一天高兴（Happy，H）隔一天烦躁（Grumpy，G），那么这一周他心情历程是“HGHGHG”。 他女友根据对男友的了解（即如果是晴天，男友 80% 的情况下高兴，20% 的情况下烦躁；如果是雨天，男友 60% 的情况下烦躁，40% 的情况下高兴），推断出这一周天气是“SRSRSR”，其中 S 代表 Sunny 晴天，R 代表 Rain 雨天。 Something is wrong！心情可以像过山车，但是天气一晴一雨的很少见，一般今天晴天明天大概率晴天，今天雨天明天还有可能是雨天。
如果今天是雨天，那么明天：
上图就是一个 HMM 的雏形。 1 HMM 是什么 HMM 的全称是 Hidden Markov Model，中文是隐马尔可夫模型。 HMM 有四个重要的概念：观测值（observation）、隐藏状态（hidden）、转换概率（transition probability）和输出概率（emission probability）。如下图所示，让我们来一一剖析。
以女友角度出发，
转换概率：隐含状态转换的概率，即
如下图所示。
输出概率：从隐含状态到观测值的概率，即
如下图所示。
总结 HMM 的示意图如下：
明晰 HMM 的概念后，让我们步入正题。 2 四个问题 为了把 HMM 讲透，接下来从易到难来分析以下四个问题。
3 解决问题一 如何估计转换概率和输出概率？ 转换概率 收集历史数据做统计，假设收集了 16 天的天气数据。
统计出“晴天-晴天”和“晴天-雨天”的个数，并标准化为概率，本例中结果为 0.8 和 0.2，两者加起来等于 1。
再统计出“雨天-晴天”和“雨天-雨天”的个数，并标准化为概率，本例中结果为 0.4 和 0.6，两者加起来等于 1。
这样就可以得到转换概率了。
输出概率 同样，收集 16 天“天气-心情”的数据。
统计出“晴天-高兴”和“晴天-烦躁”的个数，并标准化为概率，本例中结果为 0.8 和 0.2，两者加起来等于 1。
再统计出“雨天-高兴”和“雨天-烦躁”的个数，并标准化为概率，本例中结果为 0.4 和 0.6，两者加起来等于 1。
综上，我们已经计算出转换概率和输出概率，总结于下图。
第一个问题回答完毕！ 4 解决问题二 在没有任何男生情绪的信息情况下，那么晴天和雨天的概率是多少？ 假设今天是晴天，可能是因为昨天是晴天造成的，也可能是因为昨天是雨天造成的。如下图所示得到第一个方程 S = 0.8S + 0.4R 其中 0.8 是 “昨天 S - 今天 S” 的转换概率，0.4 是 “昨天 R - 今天 S” 的转换概率。
假设今天是雨天，可能是因为昨天是晴天造成的，也可能是因为昨天是雨天造成的。如下图所示得到第两个方程 R = 0.2S + 0.6R 其中 0.2 是 “昨天 S - 今天 R” 的转换概率，0.6 是 “昨天 R - 今天 R” 的转换概率。
仔细分析这两个方程是等价的，这样两个未知量一个方程解不出来，还需要一个，而 S + R = 1 就是我们所需的。
这样很容易求解出 S = 2/3，R = 1/3。
最终我们得到在不知道男生心情时，晴天和雨天的概率为 2/3 和 1/3。
当女友不知道男友心情时，她对天气的最优推断是 2/3 可能性是晴天，1/3 可能性是雨天。
第二个问题回答完毕！ 5 解决问题三 如果男生今天“高兴”，那么晴天和雨天的概率是多少？ 以上节最后结果为基准（ 2/3 可能性是晴天），先看两种情况。 情况一：当女友知道男友高兴时，，最优推断是大于 2/3 可能性（比如 4/5）是晴天。
情况二：当女友知道男友烦躁时，最优推断是小于 2/3 可能性（比如 2/5）是晴天。
那么这个具体概率值是多少呢？需要用贝叶斯定理（Bayes Theorem）来计算。这里只需要计算一天的概率，因此不需要转换概率，只需要输出概率。
因为晴天和雨天的概率为 2/3 和 1/3，不严谨地将其整数化用 2 个晴天和 1 天雨天代表概率。
根据“晴天-高兴”和“晴天-烦躁”的输出概率 0.8 和 0.2，再不严谨地将其整数化用 8 个高兴 (8/10) 和 2 天烦躁 (2/10) 代表输出概率。
根据“雨天-高兴”和“雨天-烦躁”的输出概率 0.4 和 0.6，再不严谨地将其整数化用 2 个高兴 (2/5) 和 3 天烦躁 (3/5) 代表输出概率。
回到该问题，如果男生高兴，那么晴天的概率是多少？简单，首先统计出所有男生高兴的次数，10 次。
10 次高兴中有 8 次发生在晴天，因此“当男生高兴时晴天”的条件概率为 8/10。
10 次高兴中有 2 次发生在雨天，因此“当男生高兴时雨天”的条件概率为 2/10。
同理，
第三个问题回答完毕！ 6 解决问题四 如果男生连续三天是“高兴-烦躁-高兴”，那么这连续三天的天气是什么？ 有可能是“晴天-雨天-晴天”，但怎么得到这个结果的呢？一个简单粗暴的方法就是穷举法，3 天每天 2 种天气一共 2^3 = 8 种组合，根据转换概率和输出概率计算下列 8 组概率，找一个最大值即可：
该方法简单粗暴，但是效率很低，本帖最终会介绍一个高效算法，维特比算法。首先还是看看简单粗暴法是怎么算的吧。 7 两天的情况 为了便于讲说，回顾两个观测值和两个隐含状态的缩写：
先从两天开始，男生的心情是 HG，让女友推断这两天的天气是什么。
女友穷举出以下四种情况，并计算每种情况发生的概率。
以上图第二种情况 SR 为例，之前已经得到
发生 SR 的总概率为 2/3 * 0.8 * 0.2 * 0.6 = 0.064
将穷举的四种组合发生概率全部计算出来，如下图所示，得到 SS 的概率最大，0.085。该方法也叫做最大似然法（maximum likelihood）。
因此当男生说两天心情为“高兴-烦躁”时，女友可推断出最有可能发生的天气是“晴天-晴天”。
8 三天的情况 再看三天，男生的心情是 HGH，让女友推断这三天的天气是什么。
女友穷举出以下八种情况，并计算每种情况发生的概率。
以上图第三种情况 SRS 为例，之前已经得到
发生 SRS 的总概率为 2/3 * 0.8 * 0.2 * 0.6 * 0.4 * 0.8 = 0.02048
将穷举的八种组合发生概率全部计算出来，如下图所示，得到 SSS 的概率最大。
虽然可以得到正确答案，但随着天数的增多，用穷举法的情况指数性增加。 9 四天的情况 最后看四天，男生的心情是 HGHH，让女友推断这四天的天气是什么。
女友穷举出以下十六种情况，并计算每种情况发生的概率。
当天数为 N 时，需要穷举的情况为 2^N，当 N 很大时，这种暴力穷举法根本行不通，我们需要更高效的方法，一种算法就是下节要讲的维特比（Viterbi）算法。 10 Viterbi 算法 根据男生的心情链 HHGGGH，女友推断最有可能发生的天气链。
解决此问题的核心思路是迭代法，就是把第 k 步的结果和第 k-1 步的结果连立起来。 先看最后一天，星期六的天气可能是 S 和 R。
注意力先聚焦到星期六天气为 S。从星期一到星期五有很多有路径可以到 S（如下图三条），那么总有一种是最有可能发生的。
假设我们找到中间一天是“星期一到星期五”最有可能发生的，那么连上星期六的 S，就是“星期一到星期六但最后一天是 S”最有可能发生的。
这样迭代关系就建立了，当星期六是 S， 5 天最有可能天气链 + S = 6 天最有可能天气链
当星期六是 R， 5 天最有可能天气链 + R = 6 天最有可能天气链
两者比较找到最大值，就锁定了“6 天最有可能发生的天气链”。 接下来我们过一遍 Viterbi 算法。 11 Viterbi 算法 1. 从起点星期一开始，天气为 S 的概率为 0.67，天气为 R 的概率是 0.33（答案由问题二解答）。
2. 接下来计算当天气为 S 和 R 而导致心情 H 的概率（用输出概率）：
因为 0.533 > 0.133，发现 S 比 R 导致心情 H 的可能性更大。
3. 到星期二了，有两种情况，S 和 R。 先看星期二的 S，可从星期一的 S 和 R 而来（用输出概率和转换概率）：
因为 0.341> 0.043，发现 SS 比 RS 导致心情 H 的可能性更大。
再看星期二的 R，可从星期一的 S 和 R 而来（用输出概率和转换概率）：
因为 0.043 > 0.032，发现 SR 比 RS 导致心情 H 的可能性更大。
4. 接着从星期三到星期六，一直可按照上述算法，得到截止到某一天是 S 或 R 而导致当天心情是 H 或 G 的最大概率值。具体过程如下面动图所示。
5. 下图展示最终结果，这些数字的含义是：
6. 沿着日期，找出每个日期下的最大值连成一条线，就是要找到的天气链，SSSRRS。
7. 如果男生说这一周他心情是“高兴-高兴-烦躁-烦躁-烦躁-高兴”，他女友用 Viterbi 算法得到的一周天气是“晴天-晴天-晴天-雨天-雨天-晴天”。
12 Python 实现 回顾 HMM 示意图。
设定初始晴天和雨天概率、转换概率和输出概率，并初始化男生一周心情链。 # Initial Probabilitiesp_s, p_r = 2/3, 1/3# Transition Probabilitiesp_ss, p_sr, p_rs, p_rr, = 0.8, 0.2, 0.4, 0.6# Emission Probabilitiesp_sh, p_sg, p_rh, p_rg = 0.8, 0.2, 0.4, 0.6mood = ['H', 'H', 'G', 'G', 'G', 'H']proba = []weather = []在起点星期一时，计算从“晴天 S 和雨天 R” 到“高兴 H 和烦躁 G” 的概率。
[(0.5333333333333333, 0.13333333333333333)]和上节手算结果比对没问题。
接下来用 Viterbi 算法来迭代计算从“前一天 S 和 R” 到“当天 S 和 R” 导致 H 和 G 的概率，取最大值并更新。
[(0.5333333333333333, 0.13333333333333333),和上节手算结果比对没问题。
变量 proba 是一个长度为 T 的列表，第 t 个元素代表第 t 天上天气在各个转态下的概率，假设有 N 个状态，那么 proba 里每个元素是一个长度为 N 的元组，第 n 个元素代表第 n 个天气状态。在本例中 T = 6，N = 2。 根据 proba 晴天概率 p[0] 和雨天概率 p[1] 的大小，得出当天是晴天还是雨天。
['S', 'S', 'S', 'R', 'R', 'S']和上节手算结果比对没问题。
13 Python 进一步实现 上节已经用 Python 代码实现出来本帖的例子了，但是不够通用。比如所有转换概率和输出概率都是用标量表示的，一旦状态和观测值多的话，代码会非常难看。本节用 numpy array 来实现 Viterbi 算法，专门用一个函数来实现它。
代码看起来很多，但其实就是不同矩阵或向量之间相乘，只要把形状匹配就没问题了。 将本帖例子用列表或者 numpy 数组来表示：
带入 viterbi() 函数中计算结果：
array([[0.53333333, 0.13333333],结果和上节的完全吻合！ 朋友们，你们弄懂了 HMM 了吗？
|
|
|
