HMM概念介绍
HMM是关于时序的概率模型，描述一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个可观测的随机序列的过程。
下面用一个例子来解释：
我在东京的女朋友每天根据天气{下雨，天晴}决定当天的活动{散步，购物，清理房间}中的一种，她不告诉我每天东京的天气状况，我只能从他的朋友圈看到他今天的活动。
这个例子其中{下雨，天晴}便是隐含状态链；{散步，购物，清理房间}是可见状态链；隐含状态（天气）之间的相互转换概率叫做状态转移概率；尽管可见状态（活动）之间没有转换概率，但是隐含状态和可见状态之间有一个概率（即不同的天气状况下进行不同的活动的概率）叫做发射概率；还有个初始概率即最开始是晴天还是雨天的概率。
任何一个HMM都可以通过下列五元组来描述：
:param obs:观测序列
:param states:隐状态
:param start_p:初始概率（隐状态）
:param trans_p:转移概率（隐状态）
:param emit_p: 发射概率 （隐状态表现为显状态的概率）
HMM的三个问题
HMM有三个基本问题：
预测问题（解码问题）
知道天气有几种状况（隐含状态数量），天气之间的转换概率（转移概率），根据每天的活动情况（可见状态链），我想知道每天的天气状况（隐含状态链）。概率计算问题
知道天气有几种状况（隐含状态数量），天气之间的转换概率（转移概率），根据每天的活动情况（可见状态链），我想知道今天做了这种活动的概率。学习问题
知道天气有几种状况（隐含状态数量），不知道天气之间的转换概率（转移概率），根据每天的活动情况（可见状态链），我想反推出天气之间的转换概率（转移概率）。
问题解决
本文重点介绍第一个问题的解决算法维特比算法。
维特比算法
假设我在朋友圈看到我女朋友最近三天的活动分别是{散步、购物、清理房间}，那我该如何估算这三天的天气状况。
预测问题可以用维特比算法来解决。维特比算法实际是用动态规划求解隐马尔科夫模型预测问题，即用动态规划求概率最大路径，即每天最可能的天气状况。
很明显，第一天天晴还是下雨可以算出来：
定义
V[时间][今天天气] = 概率，注意今天天气指的是，前几天的天气都确定下来了（概率最大）今天天气是X的概率，这里的概率就是一个累乘的概率了。因为第一天我的朋友去散步了，所以第一天下雨的概率
V[第一天][下雨] = 初始概率[下雨] * 发射概率[下雨][散步] = 0.6 * 0.1 = 0.06，同理可得V[第一天][天晴] = 0.24。从直觉上来看，因为第一天朋友出门了，她一般喜欢在天晴的时候散步，所以第一天天晴的概率比较大，数字与直觉统一了。从第二天开始，对于每种天气Y，都有
前一天天气是X的概率 * X转移到Y的概率 * Y天气下朋友进行这天这种活动的概率。因为前一天天气X有两种可能，所以Y的概率有两个，选取其中较大一个作为V[第二天][天气Y]的概率，同时将今天的天气加入到结果序列中。比较
V[最后一天][下雨]和[最后一天][天晴]的概率，找出较大的哪一个对应的序列，就是最终结果。
Python实现
# 打印路径概率表
def print_dptable(V):
print(" ", end=' ')
for i in range(len(V)):
print("%7d" % i, end=' ')
print('\n')
for y in V[0].keys():
print("%.5s: " % y, end=' ')
for t in range(len(V)):
print("%.7s" % ("%f" % V[t][y]), end=' ')
print('\n')
def viterbi(obs, states, start_p, trans_p, emit_p):
"""
:param obs:观测序列
:param states:隐状态
:param start_p:初始概率（隐状态）
:param trans_p:转移概率（隐状态）
:param emit_p: 发射概率（隐状态表现为显状态的概率）
:return:
"""
# 路径概率表 V[时间][隐状态] = 概率
V = [{}]
# 一个中间变量，代表当前状态是哪个隐状态
path = {}
# 初始化初始状态 (t == 0)
for y in states:
V[0][y] = start_p[y] * emit_p[y][obs[0]]
path[y] = [y]
# 对 t > 0 跑一遍维特比算法
for t in range(1, len(obs)):
V.append({})
newpath = {}
for y in states:
# 概率 隐状态 = 前状态是y0的概率 * y0转移到y的概率 * y表现为当前状态的概率
(prob, state) = max([(V[t - 1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states])
# 记录最大概率
V[t][y] = prob
# 记录路径
newpath[y] = path[state] + [y]
# 不需要保留旧路径
path = newpath
print_dptable(V)
(prob, state) = max([(V[len(obs) - 1][y], y) for y in states])
return (prob, path[state])
def main():
states = ('Rainy', 'Sunny')
observations = ('walk', 'shop', 'clean')
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
transition_probability = {
'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
}
emission_probability = {
'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}
result = viterbi(observations,
states,
start_probability,
transition_probability,
emission_probability)
return result
result = main()
print(result)
结果
0 1 2
Rainy: 0.06000 0.03840 0.01344
Sunny: 0.24000 0.04320 0.00259
(0.01344, ['Sunny', 'Rainy', 'Rainy'])
HMM和维特比算法在NLP上的应用
具体到分词系统，可以将天气当成“标签”，活动当成“字或词”。那么，几个NLP的问题就可以转化为：
词性标注
给定一个词的序列（也就是句子），找出最可能的词性序列（标签是词性）。如ansj分词和ICTCLAS分词等。分词
给定一个字的序列，找出最可能的标签序列（断句符号：[词尾]或[非词尾]构成的序列）。结巴分词目前就是利用BMES标签来分词的，B（开头）,M（中间),E(结尾),S(独立成词）命名实体识别
给定一个词的序列，找出最可能的标签序列（内外符号：[内]表示词属于命名实体，[外]表示不属于）。如ICTCLAS实现的人名识别、翻译人名识别、地名识别都是用同一个Tagger实现的。
