HMM
一、HMM五元素
其中：
N：隐藏状态数 hidden states
M：观测状态数 observed states
A： 状态转移矩阵 transition matrix
B：发射矩阵 emission matrix
pi：初始隐状态向量 initial state vector
HMM全称隐马尔科夫链，常用与异常检测，在大量正常的模式中找出异常的模式。
隐马尔科夫链模型相关的问题主要分为三类：
1.已知隐含状态数量、隐含状态的转换矩阵、根据可见的状态链，求出隐藏的状态链
2.已知隐含状态数量、隐含状态的转换矩阵、根据可见的状态链，求得出这个可见状态链的概率
3.已知隐含状态数量、可以观察到多个可见状态链，求因此状态的转移矩阵和发射概率
1.求隐藏状态链问题
该问题是在：已知隐含状态数量、隐含状态的转换矩阵、根据可见的状态链，求出隐藏的状态链(也就是最大概率的转移序列)
应用场景：语音识别解码问题
方法：Viterbi algorithm
时间复杂度：O（m*n^2）
m为时间序列的长度，n为每个时间点可能对应的状态数
举例来说，我知道我有三个骰子，六面骰，四面骰，八面骰。我也知道我掷了十次的结果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那种骰子，我想知道最有可能的骰子序列。
首先，如果我们只掷一次骰子：看到结果为1.对应的最大概率骰子序列就是D4，因为D4产生1的概率是1/4，高于1/6和1/8.
把这个情况拓展，我们掷两次骰子：结果为1，6.这时问题变得复杂起来，我们要计算三个值，分别是第二个骰子是D6，D4，D8的最大概率。显然，要取到最大概率，第一个骰子必须为D4。这时，第二个骰子取到D6的最大概率是
同样的，我们可以计算第二个骰子是D4或D8时的最大概率。我们发现，第二个骰子取到D6的概率最大。而使这个概率最大时，第一个骰子为D4。所以最大概率骰子序列就是D4 D6。
继续拓展，我们掷三次骰子：同样，我们计算第三个骰子分别是D6，D4，D8的最大概率。我们再次发现，要取到最大概率，第二个骰子必须为D6。这时，第三个骰子取到D4的最大概率是
同上，我们可以计算第三个骰子是D6或D8时的最大概率。我们发现，第三个骰子取到D4的概率最大。而使这个概率最大时，第二个骰子为D6，第一个骰子为D4。所以最大概率骰子序列就是D4 D6 D4。
写到这里，大家应该看出点规律了。既然掷骰子一二三次可以算，掷多少次都可以以此类推。
我们发现，我们要求最大概率骰子序列时要做这么几件事情。首先，不管序列多长，要从序列长度为1算起，算序列长度为1时取到每个骰子的最大概率。然后，逐渐增加长度，每增加一次长度，重新算一遍在这个长度下最后一个位置取到每个骰子的最大概率。因为上一个长度下的取到每个骰子的最大概率都算过了，重新计算的话其实不难。当我们算到最后一位时，就知道最后一位是哪个骰子的概率最大了。然后，我们要把对应这个最大概率的序列从后往前推出来,这就是Viterbi算法。
2.求得出某个可见状态链的概率
该问题是在：已知隐含状态数量、隐含状态的转换矩阵、根据可见的状态链，求得出这个可见状态链的概率
应用场景：检测观察到的结果与我们已知的模型是否吻合，即异常检测
方法:前向算法（forward algorithm）
要算用正常的三个骰子掷出这个结果的概率，其实就是将所有可能情况的概率进行加和计算（即在当前的HMM下可能出啊先找个状态链的概率）。同样，简单而暴力的方法就是把穷举所有的骰子序列，还是计算每个骰子序列对应的概率，但是这回，我们不挑最大值了，而是把所有算出来的概率相加，得到的总概率就是我们要求的结果。这个方法依然不能应用于太长的骰子序列（马尔可夫链）。
我们会应用一个和前一个问题类似的解法，只不过前一个问题关心的是概率最大值，这个问题关心的是概率之和。解决这个问题的算法叫做前向算法（forward algorithm）。
首先，如果我们只掷一次骰子，看到结果为1.产生这个结果的总概率可以按照如下计算，总概率为0.18：
把这个情况拓展，我们掷两次骰子，看到结果为1，6，总概率为0.05：
继续拓展，我们掷三次骰子，看到结果为1，6，3，计算总概率为0.03：
同样的，我们一步一步的算，有多长算多长，再长的马尔可夫链总能算出来的。用同样的方法，也可以算出不正常的六面骰和另外两个正常骰子掷出这段序列的概率，然后我们比较一下这两个概率大小，就能知道你的骰子是不是被人换了。
3. 求状态转移矩阵和发射概率（训练过程）
该问题是在： 已知隐含状态数量、可以观察到多个可见状态链
应用场景：有大量该问题的已知观测序列，想训练一个HMM模型
方法：Baum-Welch算法
面试常见问题
1.HMM的两个不合理假设
1.当前时刻的状态只与上一时刻的状态有关
2.当前表现只与当前状态有关
2.MEMM（最大熵马尔科夫模型）对HMM做了哪些改进还存在哪些问题？
虽然MEMM解决了HMM输出独立性假设的问题，但是只解决了观察值独立的问题，状态之间的假设则是标注偏置问题产生的根源，CRF则解决了标注偏置问题，是HMM模型的进一步优化。
缺陷：标注偏置问题
HMM：
MEMM
2.CRF和HMM和MEMM的不同点
整体来说就是解决了MEMM的标注偏置的问题、去除了HMM中两个不合理的假设
1.HMM是生成式模型，CRF是一种判别式模型。HMM对状态矩阵和发射矩阵进行直接建模，统计共同出现的概率，因此是一种生成式模型；
2.HMM是有向图模型，CRF是无向图模型。
3.CRF是全局最优解，结局了MEMM的标注偏置问题。MEMM是对转移概率和表现概率建立联合概率，统计时统计的是条件概率，由于其只在局部做归一化，所以容易陷入局部最优。
CRF是在全局范围内统计归一化的概率，而不像是MEMM在局部统计归一化概率。是全局最优的解。解决了MEMM中标注偏置的问题。
4.但是CRF的训练代价大，是复杂度高
