把隐马尔可夫模型彻底说清楚
1. 掌握HMM的必要性
有关于隐马尔可夫模型，我去年整理过一次，最后应该是直接把PPT截图到CSDN里了，似乎那篇文章也没有什么人看，或许是因为做成PPT索引不到，或许是大家对HMM没啥兴趣。但其实隐马的优势有点类似于朴素贝叶斯，我们比较好做人工干预。比如在HanLP的人名识别中就是利用的隐马模型，如果你对隐马基本原理没有一个清晰认识，那么直接上隐马的人名识别时，会有很多并非人名的词语被识别出来，这时候，就要利用HMM的3个概率表，即发射概率表，状态转移概率表，初始状态表，通过修改调整概率表，来提高系统识别准确率。
2. HMM的缺陷
按照何晗的《自然语言处理入门》第4章所述，HMM应用于分词的效果并不是特别理想，特别是很多在词典中的词没有被正确识别，也就是说HMM对于分词消岐并不理想，作者的结论是HMM的分词效果甚至不如词典分词。作者同时也利用HanLP做了二阶HMM的分词，作者的结论是增加HMM的阶数并不能提高分词器的准确率，单纯靠提高转移概率矩阵的复杂度并不能提高模型的拟合能力。
3. HMM解决序列标注问题的过程
训练过程：
（1）统计状态的概率分布，也就是初始概率矩阵pi
以分词为例，就是统计状态B、M、E、S的出现频率。其中B表示分词后词语的首字，M表示分词后词语的非首非尾自（如果词语字数>=3），E表示词语的尾字，S表示单字成词。比如“北京/ 信息/ 科技/ 大学”，对应的状态序列为“BEBEBEBE”。我想统计符号B、M、E、S在训练语料中的出现频率这件事的公式我就不用再在这里写出了吧？
（2）统计状态转移概率矩阵A
还以分词为例，我们应该用训练语料统计出下边的转移概率矩阵
转移概率矩阵顾名思义，就是说从一种转态到另一种状态的概率。比如训练语料中的一个词语“大学”，那么该词语对应的状态序列为“BE”，此时由B到E的转移次数就应该+1，按照这样的统计方法，就可以统计出状态转移概率矩阵A。（当然注意概率指的是出现次数除以总次数，这里认为频率就等于概率）
（3）统计发射概率矩阵B
依然以分词为例，发射概率就是一个状态可能对应的汉字的概率分布。就是下边的概率矩阵。
还是假设训练语料中出现了“大学”“BE”的对应关系，那么由“B”状态发射出“大”这个字的次数应该+1，由“E”状态发射出“学”这个字的次数应该+1，按照这样的统计方法，就可以统计出发射概率矩阵B。
至此，我们已经利用训练语料统计出了隐马模型的所有参数，也就是通常所说的三要素，接下来我们介绍预测。
预测过程：
（4）维特比算法
预测过程比较简单，就是利用维特比算法。我们先以分词为例说明维特比要做的事情。给定一个观测的序列如“北京信息科技大学”，利用维特比算法，系统可以求出一个最佳的状态序列比如是“BEBEBEBE”。好，就到这里，你应该已经知道维特比要做的事情了。那么，维特比是如何做到的呢，下边我们贴出李航《统计学习方法》中的计算过程。
首先给出两个定义：
接下来给出维特比算法
好了，读到这里你可能不想看了，没有关系，我们在下一小结求解李航《统计学习方法》书中第10章的10.3题，通过求解你就明白维特比的计算过程了。如果求解了这道习题，还是不明白，没有关系，文章最后一节给出一个Python实现的简单分词器，看了这段代码我想你应该了解了HMM分词的训练和预测过程了。
（5）根据状态序列执行分词
有了状态序列，就可以根据状态值进行分词了。比如“北京信息科技大学”HMM模型预测出的状态序列为“BEBEBEBE”，显然分词结果就是“北京/信息/科技/大学”。当然，我们这个例子刚好HMM预测正确了，实践过程中HMM很有可能会预测错误，比如预测出“SE”这样的序列，显然这两个状态不可能连续出现，因此，我们需要设计一定的规则将HMM输出的状态序列转换为合理的分词结果。HanLP的规则是只要遇到B或S这两个状态就切出1个词。
4. 一道例题理解HMM的训练和预测过程
（1）HMM的两个基本假设
前边我们都是以分词这个任务来叙述HMM的，这里，我们再回归到HMM的一些数学原理。
假设1:隐马的任一时刻状态只依赖于前一状态，而与其他时刻状态无关。
假设2:隐马的任意时刻观测值只依赖于对应该时刻的状态，而与其他时刻状态无关。
个人认为假设1在分词场景还是可以接受的，假设2忽略了两个以上汉字成词的概率这个特征。
（2）HMM中“隐”指什么？
实际上，前边我们都是说的状态，实际上对应于观测序列，可以将状态序列称为隐含状态，因为我们看到的只是汉字序列而没有看到对应于词的状态序列。
（3）例题：HMM的训练过程
这道例题是李航《统计学习方法》例10.1，通过这个例子，再次熟悉一下HMM的术语。
你能根据题目的3个叙述，写出3个概率矩阵和右侧的图吗？如果可以写出，那么你也就明白了HMM的训练过程。
（4）例题：HMM的预测过程
显然，最优状态序列为3 3 3,也就是3号盒子 3号盒子 3号盒子。
5. 基于HMM分词的Python示例
下边的代码是我用Python写的一个示例代码，代码长度在200行左右，希望通过该代码小伙伴们能彻底明白HMM的训练和预测过程。
#coding:utf-8
"""
基于隐马尔可夫模型的分词
"""
import codecs
import pickle
import numpy as np
idx_to_state = ['b', 'm', 'e', 's']
state_to_idx = {'b':0, 'm':1, 'e':2, 's':3}
# 极大似然估计法训练模型参数
def train():
# 构建字表
character_set = set()
with codecs.open('RenMinData.txt_utf8', 'rb', 'utf-8', 'ignore') as infile:
for line in infile:
line = line.strip()
if line:
word_li = line.split()
if word_li:
for word in word_li:
if word:
character_set.update(word)
# 输出字表
print('输出字表...')
with open('character_list.txt', 'wb') as outfile:
idx = 0
for character in character_set:
out_str = u'%d\t%s\n' % (idx, character)
outfile.write(out_str.encode('utf-8', 'ignore'))
idx += 1
# 加载字索引以及索引字
character_to_idx = dict()
idx_to_character = []
with codecs.open('character_list.txt', 'rb', 'utf-8', 'ignore') as infile:
for line in infile:
line = line.strip()
if line:
idx, character = line.split(u'\t')
character_to_idx[character] = int(idx)
idx_to_character.append(character)
print('加载字索引表 长度=%d' % len(character_to_idx))
print('加载索引字表 长度=%d' % len(idx_to_character))
global state_li
# 矩阵初始化
print('初始化模型矩阵')
A = np.zeros((len(idx_to_state), len(idx_to_state)))
print('A=\n', A)
B = np.zeros((len(idx_to_state), len(idx_to_character)))
print('B.shape', B.shape)
PI = np.zeros(len(idx_to_state))
print('PI=', PI)
# 训练
with codecs.open('RenMinData.txt_utf8', 'rb', 'utf-8', 'ignore') as infile:
for line_ser, line in enumerate(infile):
line = line.strip()
if line:
# 对句子中的每个字打状态标记
word_li = line.split()
character_li = []
if word_li:
for word in word_li:
if len(word) == 0:
continue
elif len(word) == 1:
character_li.append((word[0],'s'))
elif len(word) == 2:
character_li.append((word[0],'b'))
character_li.append((word[1], 'e'))
else:
character_li.append((word[0], 'b'))
character_li.extend([(w, 'm') for w in word[1:-1]])
character_li.append((word[-1], 'e'))
# 统计相关次数
# 更新PI列表
PI[state_to_idx[character_li[0][1]]] += 1
# 更新B字典
for character, state in character_li:
B[state_to_idx[state], character_to_idx[character]] += 1
# 更新A字典
if len(character_li) >= 2:
for ser_num, cur_state in enumerate([w[1] for w in character_li[:-1]]):
next_state = character_li[ser_num+1][1]
cur_state_idx = state_to_idx[cur_state]
next_state_idx = state_to_idx[next_state]
A[cur_state_idx][next_state_idx] += 1
# 计算PI
PI = PI/sum(PI)
# 计算A
for row_ser in range(A.shape[0]):
A[row_ser,::] /= sum(A[row_ser,::])
# 计算B
for row_ser in range(B.shape[0]):
B[row_ser,::] /= sum(B[row_ser, ::])
# 输出PI
print("输出PI矩阵...")
with open('model_PI', 'wb') as outfile:
pickle.dump(PI, outfile)
# 输出A
print("输出A矩阵...")
with open('model_A', 'wb') as outfile:
pickle.dump(A, outfile)
# 输出B
print("输出B矩阵...")
with open('model_B', 'wb') as outfile:
pickle.dump(B, outfile)
def viterbe(O, PI, A, B, str=u''):
"""
viterbi算法计算HMM问题2
:param O: 观测序列
:param PI: 初始状态分布
:param A: 状态转移矩阵
:param B: 发射矩阵
:return:
"""
# viterbi算法中初始化delta_1
delta_1 = PI * B[:, 0]
# viterbi算法中初始化kesi_1
kesi_1 = np.zeros(PI.size, dtype=np.int)
# 最优路径记录初始化
kesi = np.array(kesi_1.T)
# 递推
delta_tplusone = delta_1.copy()
for t in range(1, len(O)):
max_delta_tminus_aji = np.tile(delta_tplusone, PI.size).reshape(A.shape).T * A
delta_t = np.max(max_delta_tminus_aji, 0) * B[:, O[t]]
kesi_t = np.argmax(max_delta_tminus_aji, 0)
kesi = np.column_stack((kesi, kesi_t.T))
delta_tplusone = delta_t.copy()
# 终止
P_star = np.max(delta_t)
i_T_star = np.argmax(kesi_t)
# 最优路径回溯
I_star = [i_T_star]
i_tplus_star = i_T_star
for t in range(kesi.shape[1] - 1, 0, -1):
i_t_star = kesi[:, t][i_tplus_star]
I_star.append(i_t_star)
i_tplus_star = i_t_star
I_star = I_star[::-1]
# 输出分词结果
if str:
out_str = u""
state_li = [idx_to_state[w] for w in I_star]
i = 0
while i<len(state_li):
if state_li[i] == 'b':
j = i+1
while j<len(state_li):
if state_li[j] not in ['m', 'e']:
break
j += 1
out_str += str[i:j] + u'/'
i = j
else:
out_str += str[i] + u'/'
i+=1
print(out_str)
if __name__ == '__main__':
# 训练模型
train()
# 加载模型
PI = pickle.load(open('model_PI', 'rb'))
A = pickle.load(open('model_A', 'rb'))
B = pickle.load(open('model_B', 'rb'))
# 加载字索引以及索引字
character_to_idx = dict()
idx_to_character = []
with codecs.open('character_list.txt', 'rb', 'utf-8', 'ignore') as infile:
for line in infile:
line = line.strip()
if line:
idx, character = line.split(u'\t')
character_to_idx[character] = int(idx)
idx_to_character.append(character)
print('加载字索引表 长度=%d' % len(character_to_idx))
print('加载索引字表 长度=%d' % len(idx_to_character))
# 测试
# A = np.array([[0.5, 0.2, 0.3],
# [0.3, 0.5, 0.2],
# [0.2, 0.3, 0.5]])
# B = np.array([[0.5, 0.5],
# [0.4, 0.6],
# [0.7, 0.3]])
# PI = np.array([0.2, 0.4, 0.4])
# O = [0, 1, 0]
str = u'小明硕士毕业于北京信息科技大学'
try:
O = [character_to_idx[w] for w in str]
except:
print('有未登录字')
exit(1)
print(str)
viterbe(O, PI, A, B, str)
这里我们给出训练语料的格式,每行1个句子，词语之间以空格分隔即可。
这 是 我国 目前 最 大 的 朝鲜 民族 文化 设施 。
这 座 文化宫 建筑 面积 为 二千七百 平方米 ，
内部 设有 剧场 、 排 练 厅 、 舞 厅 ，
可 同时 容 纳 一千 多 人 参加 活动 。
（ 新华社 电 ） 文化 天地 空军 某地 空 导弹 旅 歌曲 创作 活跃 新华社 ０５ 旅 有 旅 歌 、
营 有 营 歌 、 连 有 连 歌 。
空军 某地 空 导弹 旅 开展 谱写 军 旅 歌曲 活动 ，
目前 所有 连 以上 单位 都 有 了 反映 自己 工作 特色 的 歌曲 。
这个 旅 是 一 支 屡 建 战功 的 部队 。
全 旅 从 １９８６年 ５月 起 开展 了 群众性 的 谱写 旅 、 营 、 连 歌 活动 。 下边给出实现代码的github链接，如有问题请大家留言。
至此，专栏中有关自然语言处理基本机器学习算法就全部介绍完毕了。我们介绍了HMM， baiziyu：最大熵模型 , baiziyu：条件随机场 。
文章被以下专栏收录
