HMM 模型
HMM（隐马尔科夫模型）有
两类变量：（变量序列）
1. Hidden States：xi
2. Events：ei
模型的三要素：
1. State priors
2. Transition matrix
3. Emission matrix
三种求解问题：
1. 已知 模型三要素 和 Events，求Hidden States：Viterbi算法
2. 已知 模型三要素 和 Events，求这一系列Events发生的概率：Forward/Backward 算法
3. 已知 Events，求 模型三要素： Baum-Welch算法 (也可以叫Forward-Backward 算法)
（注意：这里Baum-Welch算法也可以叫Forward-Backward 算法，是因为它本质上是从Forward和Backward两个方向进行的。而Forward/Backward 算法这里为“或”，是因为只要其中一个方向就能求解出来了）
（另：三种算法间有着紧密的联系）
以下为我个人对三种算法的理解：
Viterbi算法 和 Forward/Backward 算法都是 动态规划 的一种特例
Baum-Welch算法 是 EM算法 的一种特例（迭代的方法估计参数基本都是EM算法）
Viterbi 算法
简单了解Viterbi算法的思想可以看：https://www.zhihu.com/question/20136144/answer/763021768
在一个HMM模型的例子中来讲解可以看：https://www.zhihu.com/question/20136144/answer/239971177
用公式来表达Viterbi算法非常简洁：
其中M，C作为中间变量，其意义为：
M(i, j)：第 i 个状态时是第 j 个hidden state 的概率
C(i, j): 第 i 个状态时第 j 个hidden state 对应的上一个状态概率最大的 hidden state（因此 i 是取不到0的）
最后的x(i)即为events 对应的 hidden states 序列
时间复杂度分析：
该算法本质上来说是动态规划，其中取max相当于剪枝的效果，这样时间复杂度从暴力枚举的 N^T 缩小到 T * N^2
代码如下：
def Viterbi(prior, transProb, emisProb, events): ''' prior: [numHidden] transProb: [numHidden(last), numHidden(current)] emisProb: [numHidden, numEvents] events: [lengthEvents] # index of events should start from 0 ''' numHidden = emisProb.shape[0] numEvents = emisProb.shape[1] lengthEvents = events.shape[0] hiddenProb = np.zeros((lengthEvents, numHidden)) record = np.zeros((lengthEvents, numHidden), dtype=np.int) # record[0, :] is not been used assert prior.shape[0] == numHidden assert transProb.shape[0] == numHidden assert transProb.shape[1] == numHidden bestRoute = np.zeros(lengthEvents, dtype=np.int) # calculate the first state for i in range(numHidden): hiddenProb[0, i] = prior[i] * emisProb[i, events[0]] # calculate other states for i in range(1, lengthEvents): # event index for j in range(numHidden): # current state temp = np.zeros(numEvents) for k in range(numHidden): # last state temp[k] = hiddenProb[i-1, k] * transProb[k, j] hiddenProb[i, j] = np.max(temp) * emisProb[j, events[i]] record[i, j] = np.argmax(temp) # find the best route bestRoute[-1] = np.argmax(hiddenProb[-1, :]) for i in range(lengthEvents - 2, -1, -1): bestRoute[i] = record[i+1, bestRoute[i+1]] return bestRoute
（其实就是把上面公式翻译了一遍）
关于其他两个算法：
forward/backward比较简单
Baum–Welch算法可参考：
https://blog.csdn.net/u014688145/article/details/53046765?locationNum=7&fps=1
参考：
https://blog.csdn.net/sinat_36005594/article/details/69568538