HMM(隐马尔科夫模型）
隐马尔科夫模型是统计模型在机器学习中的典型应用，即使在目前神经网络飞速发展的当下，也被认为是NLP领域相当有效的方法。
转移概率，发射概率
现实生活中，我们可以观察到很可见状态，这些可见状态是已发生的，确定的。
这些可见状态会依赖于一些隐藏状态，隐藏状态之间会存在转移概率（transition probality), 而从隐藏状态到可见状态则存在发射概率（emission probality）
马尔科夫假设
实际情况中，某一时刻的状态其实是由已发生的多个状态决定的.
$$P(X_{n} | X_{n-1},X_{n-2}... )$$但这样对于计算太过于复杂，所以建立一种假设，当前状态只依赖于上一个状态。而与其他状态无关。$$P(X_{n} | X_{n-1})$$这个假设虽然不太符合实际，但在实际应用中发现，相当有效。隐马尔科夫模型解决的问题
- 已知一种模型(隐含状态数量，转移概率，发射概率），求一可见状态链的概率。(Forward算法)
- 已知一种模型(隐含状态数量，转移概率，发射概率），求最可能的隐藏状态链。(Veterbi 算法)
- 已知一组可见状态链，求模型（转移概率，发射概率）。（EM 算法）
Forward 算法
针对第一类问题，如果状态空间较小，可以通过穷举各种可能的组合，然后进行累加。
但这在样本空间较大后，变成不可能完成的任务。Forward则采取迭代计算的方式层层计算，直至得到最后结果。假设现在有:
隐含状态：$X \in (X_{1},X_{2})$
初始概率：假设均匀分布，都为1/2
转移概率：$ P(X_{1}->X_{2}) =1/3$ $ P(X_{1}->X_{1}) =2/3$ $ P(X_{2}->X_{1}) =7/8$ $P(X_{2}->X_{2})=1/8 $
发射概率：$ P(X_{1}->S_{1}) =1/2$ $P(X_{1}->S_{2})=1/2 $ $P(X_{2}->S_{1})=3/8 $ $P(X_{2}->S_{2})=5/8 $
观察状态链: $S_{1}->S_{2}->S_{2}->S_{1}$
计算过程：
| S(X) | $S_{1}$ | $S_{2}$ | $S_{2}$ | $S_{1}$ |
| $X_{1}$ | 1/2 * 1/8 | $S_{1}(X_{1})$ * 2/3 * 1/2 + $S_{1}(X_{2})$ * 7/8 * 5/8 | ... | ... |
| $X_{2}$ | 1/2 * 3/8 | $S_{1}(X_{2})$ * 1/8 * 1/4 + $S_{1}(X_{1})$ * 7/8 * 1/4 | ... | ... |
| Total | 0.25 | 0.14 | ... | ... |
Veberbi 算法
针对第二类问题，解决办法就是在Forward计算的基础，只是不是累加概率，而是挑选最大的概率。
其实有点动态规划的意思，算出$S_{n-2}$到$S_{n-1}$的各种情况下的概率，然后挑选出最大概率的串，用于$S_{n}$的迭代计算。计算过程：| S(X) | $S_{1}$ | $S_{2}$ | $S_{2}$ | $S_{1}$ |
| $X_{1}$ | 1/2 * 1/8 | Max($S_{1}(X_{1}) * 2/3 * 1/2$ , $S_{1}(X_{2}) * 7/8 * 5/8 $) | ... | ... |
| $X_{2}$ | 1/2 * 3/8 | Max($S_{2}(X_{2}) * 1/8 * 1/4$ , $S_{1}(X_{1}) * 7/8 * 1/4 $) | ... | ... |
在迭代计算的过程，保存最大概率的串。在最后一个隐藏状态计算中，最大概率的串就是结果。
EM 算法
无监督算法。 to be continued...