隐马尔可夫模型

马尔可夫模型

马尔可夫模型（The Markov chain, sometimes called the observed Markov model）本质上是一个加权的有限状态机（weighted finite automaton），它描述了不同状态之间的转换关系以及转换概率（这里的权重就是状态转移概率）。

我们常说的Markov Model其实是一阶马尔科夫模型（first-order Markov Model），它有个最基本的假设：当前状态出现的概率，只取决于上一个状态（In a first-order Markov chain, the probability of a particular state depends only on the previous state），数学表达式如下：

马尔可夫模型有什么用？

我们知道两个状态之间的转移概率是很容易计算出来的，但是一连串的状态出现的概率却没那么容易计算。于是，我们可以先通过计算两两状态之间的转移概率构造出一个马尔可夫链，然后再通过马尔可夫链去计算一连串状态出现的概率（A Markov chain is useful when we need to compute a probability for a sequence of events that we can observe in the world.）这句话的重点是如何计算一连串状态出现的概率。

隐马尔可夫模型

隐马尔科夫模型（Hideen Markov Model, HMM）是统计模型，用来描述一个含有隐含状态变量/未知参数的（未观测到的） 马尔可夫过程/系统，其难点是如何从可观察到的 状态变量/参数 中确定该 过程/系统 的隐含状态变量/参数（未观测到的）。

HMM在控制系统中的一个很好的例子就是设计卡尔曼滤波器对系统状态进行估计，这里系统的状态被建模为隐含状态。

注：马尔可夫过程用于建模一个随机系统的动态过程，这里的参数等同于系统的状态。

一个简单的例子

假设我手里有三个不同的骰子。第一个骰子D6，6个面，每个面（1，2，3，4，5，6）出现的概率是1/6。第二个骰子D4，每个面（1，2，3，4）出现的概率是1/4。第三个骰子D8，每个面（1，2，3，4，5，6，7，8）出现的概率是1/8。

骰子类型

假设我们有如下马尔科夫过程：
第一步，我们先从三个骰子里选一个，挑到每个骰子的概率都为1/3；第二步，掷骰子，得到数字1,2,3,4,5,6,7,8中的一个。不听的重复以上两个过程，我们会得到一串数字。例如我们会得到这么一串数字（掷了10次）：1,6,3,5,2,7,3,5,2,4。

这串数字叫做可见状态连，但在HMM中我们不仅有一串（时间序列）可见状态连，还有一串隐含状态链。在这个例子中隐含状态链就是你用骰子的序列，例如：D6,D8,D8,D6,D4,D8,D6,D6,D4,D8

HMM中说到的马尔可夫链，一般指的都是隐含状态链。隐含状态（骰子）之间存在转移概率（transition probability）。在这个例子中就是D6转移到下一个状态D4,D6,D8的概率都是1/3。D4或D8转移到下一个状态D4,D6,D8的转移概率也分别都是1/3。这样的设定是为了最开始容易说清楚问题，当然我们也可以随意设定转移概率，这样就是一个新的HMM。

同样的，尽管可见状态链之间没有转移概率，但是隐含状态到可见状态之间有一个概率叫做输出概率（emission probability）。就是说D6下产生1-6的概率分别都是1/6。同样我们也可以对输出概率进行其他的定义。

HMM示意图
隐含状态转移过程示意图

对于HMM来说，如果提前知道所有隐含状态之间的转移概率和输出概率，做模拟（simulation）是相当容易的。但是应用HMM模型的时候，往往是缺失一部分信息的，有时候你知道骰子有几种（我们这里是3种），每种骰子是什么，但是你不知道掷出来的骰子序列（可见状态链）；有时候你只是看到了很多次掷骰子的结果（只知道可见状态链），剩下的什么都不知道。我们需要做的就是设计算法去估计出这些缺失的信息。

HMM的三类问题

1.（Decoding） 知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），求每次掷出来的都是哪种骰子（隐含状态链）。

求解方法：1.最大似然路径法，穷举算法。2.The Viterbi Algorithm，一种动态规划算法

2.（Likelihood） 知道骰子有几种（隐含状态数量），每种骰子是什么（转移概率），根据掷骰子掷出的结果（可见状态链），求掷出这个结果的概率。

求解方法： The Forward Algorithm，一种动态规划算法

3.（Learning） 知道骰子有几种（隐含状态数量），不知道每种骰子是什么（转移概率），观测到很多次掷骰子的结果（可见状态链），推出每种骰子的转移概率。

求解方法：Expectation-Maximization,EM 算法，一种Forward-Backward Algorithm

求解方法

0. 一个简单的问题 Forward Pass

知道骰子有几种，每种骰子是什么，每次掷的都是什么骰子，根据掷骰子掷出的结果，求产生这个结果的概率。

转移过程
概率相乘：

1.Decodeing

以一种解法，最大似然路径法：
举例来说，我知道我有三个骰子，六面骰，四面骰，八面骰。我也知道我掷了十次的结果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那种骰子，我想知道最有可能的骰子序列（隐含状态序列）。

最简单而暴力的方法就是穷举所有可能的骰子序列，然后依次按第零个问题的解法把每个序列对应的概率算出来。最后，我们从里面把对应最大似然概率的序列挑出来就行了。如果马尔可夫链不长，当然可行。如果长的话，穷举的数量太大，就很难完成了。

解法二，Viterbi algorithm：

2.Likelihood

1.Learning

---

参考文献

http://www.cnblogs.com/skyme/p/4651331.html
https://www.cnblogs.com/jacklu/p/6225073.html
https://en.wikipedia.org/wiki/Hidden_Markov_model