浅谈隐马尔可夫模型(HMM)
前置芝士
- 最最最基本的古典概率
0x00 简介
隐马尔可夫模型(Hidden Markov Model;缩写:HMM)或称作隐性马尔可夫模型,是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。
From wikipedia
是不是一脸懵逼QAQ
0x01 真·介绍
举个栗子:这里有三个骰子,分别是:
有四个面的
有六个面的
有八个面的
接下来,我们开始掷骰子。每一次先从三个骰子里拿一个,拿到每个骰子的概率是
但是在隐马尔可夫模型中,我们不仅仅有这么一串可见状态链，还有一串隐含状态链。
在这个例子里,这串隐含状态链就是你用的骰子的序列。比如,隐含状态链有可能是:
比如说,在
同样的,尽管可见状态间没有转换概率,但隐含状态和可见状态间有一种叫输出概率的东西。比如说
比如,假设我有一个被赌场动过手脚的四面骰子，掷出来是
0x02 隐马尔可夫模型的相关问题
- . 知道骰子有几种(隐含状态数量),每种骰子是什么(转换概率),根据掷骰子掷出的结果(可见状态链),我想知道每次掷出来的都是哪种骰子(隐含状态链)。
这个问题大多用在语音识别领域,叫解码问题。这个问题有两个解法,是两个不同的答案,只不过意义不一样。第一种解法求最大似然状态路径,说通俗点呢,就是我求一串骰子序列,这串骰子序列产生观测结果的概率最大。第二种解法呢,就不是求一组骰子序列了,而是求每次掷出的骰子分别是某种骰子的概率。
- . 还是知道骰子有几种(隐含状态数量),每种骰子是什么(转换概率),根据掷骰子掷出的结果(可见状态链),我想知道掷出这个结果的概率。
看似这个问题意义不大,因为你掷出来的结果很多时候都对应了一个比较大的概率。问这个问题的目的呢，,其实是检测观察到的结果和已知的模型是否吻合。如果很多次结果都对应了比较小的概率,那么就说明我们已知的模型很有可能是错的,有人偷偷把我们的骰子给换了。
- . 知道骰子有几种(隐含状态数量)，不知道每种骰子是什么(转换概率)，观测到很多次掷骰子的结果(可见状态链),我想反推出每种骰子是什么(转换概率)。
这个问题很重要,因为这是最常见的情况。很多时候我们只有可见结果,不知道
0x03 如何解决上述问题
-
. 这只是一个简
(hua)单(ji)的前提栗子:知道骰子有几种,每种骰子是什么,每次掷的都是什么骰子,根据掷骰子掷出的结果,求产生这个结果的概率。
解法就是将概率相乘:P=P(S8) \times P(S8 \rightarrow 7) \times P(S8 \rightarrow S4) \times P(S4 \rightarrow 1) \times P(S4 \rightarrow S4) \times P(S4 \rightarrow 3) \space \space=\frac 1 3 \times \frac 1 8 \times \frac 1 3 \times \frac 1 4 \times \frac 1 3 \times \frac 1 4 \space \space =\frac {1} {3456} - 问题1 看见不可见的，破解骰子序列
这里讲的是第一种解法。
For example:我知道我有S4 ,S6 ,S8 三个骰子，我也知道我掷了十次骰子的结果(7 1 3 5 8 2 3 5 2 4 ),我不知道每次用了哪种骰子，我想知道最有可能的骰子序列。
其实最简单而暴力的方法就是穷举所有可能的骰子序列，然后依照样例问题的解法把每个序列对应的概率算出来。然后我们从里面把对应最大概率的序列挑出来就行了。如果马尔可夫链不长，当然可行。如果长的话，穷举的数量太大，就很难完成了。
另外有一种很有名的算法叫做Viterbi algorithm . 要理解这个算法，我们先看几个简单的例子。
首先,如果我们只掷一次骰子:
看到结果为1.对应的最大概率骰子序列就是S4 ，因为S4 产生1 的概率是\frac 1 4 ，高于\frac 1 6 和\frac 1 8 .
拓展这个情况，如果我们掷两次骰子:
结果为1 和3 ,这个问题稍微复杂了一点。为了使概率最高，第一个骰子必须是S4 ,同理,第二个骰子必须也是S4 。则概率为:P=P(S4) \times P(S4 \rightarrow 1) \times P(S4 \rightarrow S4) \times P(S4 \rightarrow 3) \space = \frac 1 3 \times \frac 1 4 \times \frac 1 3 \times \frac 1 4 \space = \frac {1} {144} 写到这里，大家应该看出点规律了。我们发现，我们要求最大概率骰子序列时要做这么几件事情。首先，不管序列多长，要从序列长度为1算起，算序列长度为1时取到每个骰子的最大概率。然后，逐渐增加长度，每增加一次长度，重新算一遍在这个长度下最后一个位置取到每个骰子的最大概率。因为上一个长度下的取到每个骰子的最大概率都算过了，重新计算的话其实不难。当我们算到最后一位时，就知道最后一位是哪个骰子的概率最大了。然后，我们要把对应这个最大概率的序列从后往前推出来。
- 问题1 看见不可见的，破解骰子序列