隐马尔可夫模型（HMM)
隐马尔可夫模型（Hidden Markov ， 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中的一个。不停的重复上述过程，我们会得到一串数字，每个数字都是1，2，3，4，5，6，7，8中的一个。例如我们可能得到这么一串数字（掷骰子10次）：1 6 3 5 2 7 3 5 2 4
这串数字叫做可见状态链。但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。在这个例子里，这串隐含状态链就是你用的骰子的序列。比如，隐含状态链有可能是：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。这样设定是为了最开始容易说清楚，但是我们其实是可以随意设定转换概率的。比如，我们可以这样定义，D6后面不能接D4，D6后面是D6的概率是0.9，是D8的概率是0.1。这样就是一个新的HMM。
同样的，尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emission probability）。就我们的例子来说，六面骰（D6）产生1的输出概率是1/6。产生2，3，4，5，6的概率也都是1/6。我们同样可以对输出概率进行其他定义。比如，我有一个被赌场动过手脚的六面骰子，掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。
其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。但是应用HMM模型时候呢，往往是缺失了一部分信息的，有时候你知道骰子有几种，每种骰子是什么，但是不知道掷出来的骰子序列；有时候你只是看到了很多次掷骰子的结果，剩下的什么都不知道。如果应用算法去估计这些缺失的信息，就成了一个很重要的问题。这些算法我会在下面详细讲。
隐马尔可夫(HMM)模型相关算法
在马尔可夫模型中，上一个状态到下一个状态是得到已知的概率矩阵的，就像在前一篇马尔可夫模型1文章中得到的非确定模式中的昨天天气->今天天气的转换矩阵，在这个例子中也同样道理，现在有D6,D4,D8三种类型的色子，假设他们之间的转换都是均匀的，那么应该得到如下转换矩阵：
$$
\begin{bmatrix}
& D4 & D6 & D8\\
D4 & 1/3 & 1/3 & 1/3 \\
D6 & 1/3 & 1/3 & 1/3\\
D8 & 1/3 & 1/3 & 1/3
\end{bmatrix}
$$
1.最简单的解决方法
实用性不大，但作为入门
那么我们需要知道产生上方隐式链的计算概率方式就应该是
$$
P(D6,D8,D8) = P(D6) ∗ P(D6 \rightarrow 1) ∗ P(D6 \rightarrow D8) \\
∗ P(D8 \rightarrow 6) ∗ P(D8 \rightarrow D8) ∗ P(D8 \rightarrow 3) \\
=1/3 ∗ 1/6 ∗ 1/3 ∗ 1/8 ∗ 1/3 ∗ 1/8
$$
上述的式子就代表了得到这条隐式链的概率以及从隐式链的每一项对应到显式链每一项的概率。
2.看见不可见的，破解色子序列(viterbi算法)
viterbi算法只是解决隐马第三个问题（求观察序列的最可能的标注序列）的一种实现方式。这个问题可以用于viterbi算法实现，也可以用其他方式实现（如穷举法）；而viterbi算法可以用于解决隐马第三问题，也可以用于解决其他问题。
viterbi算法其实就是多步骤每步多选择模型的最优选择问题，其在每一步的所有选择都保存了前续所有步骤到当前步骤当前选择的最小总代价（或者最大价值）以及当前代价的情况下前继步骤的选择。依次计算完所有步骤后，通过回溯的方法找到最优选择路径。符合这个模型的都可以用viterbi算法解决，隐马模型的第三问题刚好符合这个模型，所以才采用了viterbi算法。
|
|
Step 1: 首先只掷一次骰子
看到结果为1，初始概率也同样认为每个骰子都是1/3。
P1(D4->1) = P(D4) ∗ P(D4->1) = 1/3 ∗ 1/4
P1(D6->1) = P(D6) ∗ P(D6->1) = 1/3 ∗ 1/6
P1(D8->1) = P(D8) ∗ P(D8->1) = 1/3 ∗ 1/8
所以第一次就认为选择的是D4
Step 2: 判断第二个骰子
看到结果为6。因为在马尔可夫模型中，当前状态只跟前一次状态存在转移关系。所以之前状态有3个->当前的3个状态，我们需要把9种状态都计算一遍，然后对于每个骰子的选择出选中它最大的一个，最后进行比较。
但是对于当前步的隐藏状态->观察状态的概率在比较过程中先不乘进去，最后再乘上
（1）前一个状态为D4，后一个状态为D6:
$$
P2(D6) = P1(D4 \rightarrow1) ∗ P(D4 \rightarrow D6) = 1/12 ∗ 1/3
$$
（2）前一个状态为D6，后一个状态为D6:
$$
P2(D6) = P1(D6 \rightarrow 1) ∗ P(D4 \rightarrow D6) = 1/18 ∗ 1/3
$$
（3）前一个状态为D8，后一个状态为D6:
$$
P2(D6) = P1(D8 \rightarrow 1) ∗ P(D4 \rightarrow D6) = 1/24 ∗ 1/3
$$
所以P2(D6)最后会选择最大的1/12 ∗ 1/3
同理可以求出P2(D4) , P2(D8)
通过比较之后P2(D6->6)大于它们两个，所以第二个色子选择D6
然后就可以计算：
$$
P2(D6 \rightarrow 6) = P2(D6) P(D6 \rightarrow 6) = 1/36 1/6
$$
同理可以算出P2(D4->6),P2(D8->6)
Step 3: 后面的色子选择同理于第二个色子，每次只要判断前一次的状态即可。
但是我们需要注意的是，到达当前最优的隐藏状态是从上一次的什么什么隐藏状态来的，最后根据最优结果进行回溯。
3.谁动了我的骰子–前向算法(解决一类得到已知结果的状态链，想要求出得到这个状态链的概率)
|
|
现在已知投掷结果是{1,6,3}
对于未被换过色子的情况来说：
Step 1: 第一个骰子的投掷结果
看到结果为1，产生这个结果的总概率就是计算每种色子到达1的概率的总和
| P1 | P2 | P3 | |
|---|---|---|---|
| D6 | 1/3 ∗ 1/6 | ||
| D4 | 1/3 ∗ 1/4 | ||
| D8 | 1/3 ∗ 1/8 | ||
| Total | 0.18 |
Step 2: 第二个骰子的投掷结果
看到结果为6，从上一次状态转移到这一次的6选择的所有可能概率的总和
| P1 | P2 | P3 | |
|---|---|---|---|
| D6 | 1/3 ∗ 1/6 | P1(D6) ∗ 1/3 ∗ 1/6 + P1(D4) ∗ 1/3 ∗ 1/6 + P1(D8) ∗ 1/3 ∗ 1/6 | |
| D4 | 1/3 ∗ 1/4 | P1(D6) ∗ 1/3 ∗ 0 + P1(D4) ∗ 1/3 ∗ 0 + P1(D8) ∗ 1/3 ∗ 0 | |
| D8 | 1/3 ∗ 1/8 | P1(D6) ∗ 1/3 ∗ 1/8 + P1(D4) ∗ 1/3 ∗ 1/8 + P1(D8) ∗ 1/3 ∗ 1/8 | |
| Total | 0.18 | 0.05 |
Step 3: 第三个骰子的投掷结果
| P1 | P2 | P3 | |
|---|---|---|---|
| D6 | 1/3 ∗ 1/6 | P1(D6) ∗ 1/3 ∗ 1/6 + P1(D4) ∗ 1/3 ∗ 1/6 + P1(D8) ∗ 1/3 ∗ 1/6 | P2(D6) ∗ 1/3 ∗ 1/6 + P2(D4) ∗ 1/3 ∗ 1/6 + P2(D8) ∗ 1/3 ∗ 1/6 |
| D4 | 1/3 ∗ 1/4 | P1(D6) ∗ 1/3 ∗ 0 + P1(D4) ∗ 1/3 ∗ 0 + P1(D8) ∗ 1/3 ∗ 0 | P2(D6) ∗ 1/3 ∗ 1/4 + P2(D4) ∗ 1/3 ∗ 1/4 + P2(D8) ∗ 1/3 ∗ 1/4 |
| D8 | 1/3 ∗ 1/8 | P1(D6) ∗ 1/3 ∗ 1/8 + P1(D4) ∗ 1/3 ∗ 1/8 + P1(D8) ∗ 1/3 ∗ 1/8 | P2(D6) ∗ 1/3 ∗ 1/8 + P2(D4) ∗ 1/3 ∗ 1/8 + P2(D8) ∗ 1/3 ∗ 1/8 |
| Total | 0.18 | 0.05 | 0.03 |
同样地可以计算出被换过的骰子所得到的概率，根据大小比较来判断是不是被换了
