文章目录
一、HMM简述
1.引入
民间传说告诉我们水藻的状态与天气状态有一定的概率关系——天气和水藻的状态是紧密相关的。在这个例子中我们有两组状态，观察的状态（水藻的状态）和隐藏的状态（天气的状态）。
现在我们定义一个一阶马尔科夫过程如下：
-
状态：三个状态——晴天，多云，雨天。
-
pi向量：定义系统初始化时每一个状态的概率。
-
状态转移矩阵：给定前一天天气情况下的当前天气概率。
任何一个可以用这种方式描述的系统都是一个马尔科夫过程。
除了定义了马尔科夫过程的概率关系，我们还有另一个矩阵，定义为混淆矩阵（confusion matrix），它包含了给定一个隐藏状态后得到的观察状态的概率。对于天气例子，混淆矩阵是：
注意矩阵的每一行之和是1。
我们使用一个隐马尔科夫模型（HMM）对这些例子建模。这个模型包含两组状态集合和三组概率集合：
- 隐藏状态：一个系统的（真实）状态，可以由一个马尔科夫过程进行描述（例如，天气）。
- 观察状态：在这个过程中‘可视’的状态（例如，海藻的湿度）。
- pi向量：包含了（隐）模型在时间t=1时一个特殊的隐藏状态的概率（初始概率）。
- 状态转移矩阵：包含了一个隐藏状态到另一个隐藏状态的概率
- 混淆矩阵：包含了给定隐马尔科夫模型的某一个特殊的隐藏状态，观察到的某个观察状态的概率。
因此一个隐马尔科夫模型是在一个标准的马尔科夫过程中引入一组观察状态，以及其与隐藏状态间的一些概率关系。
2.隐马尔科夫模型
（1）定义（Definition of a hidden Markov model）
一个隐马尔科夫模型是一个三元组（pi, A, B）。
：初始化概率向量；
：状态转移矩阵；
：混淆矩阵；
在状态转移矩阵及混淆矩阵中的每一个概率都是时间无关的——也就是说，当系统演化时这些矩阵并不随时间改变。实际上，这是马尔科夫模型关于真实世界最不现实的一个假设。
（2）应用
1. 对于一个观察序列匹配最可能的系统——评估，使用前向算法（forward algorithm）解决；
2. 对于已生成的一个观察序列，确定最可能的隐藏状态序列——解码，使用Viterbi 算法（Viterbi algorithm）解决；
3. 对于已生成的观察序列，决定最可能的模型参数——学习，使用前向-后向算法（forward-backward algorithm）解决。
3.前向算法（了解）
4. 维特比算法
寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states)
对于一个特殊的隐马尔科夫模型(HMM)及一个相应的观察序列，我们常常希望能找到生成此序列最可能的隐藏状态序列。
我们使用下面这张网格图片来形象化的说明隐藏状态和观察状态之间的关系：
我们可以通过列出所有可能的隐藏状态序列并且计算对于每个组合相应的观察序列的概率来找到最可能的隐藏状态序列。最可能的隐藏状态序列是使下面这个概率最大的组合：
给定一个观察序列和一个隐马尔科夫模型（HMM），我们将考虑递归地寻找最有可能的隐藏状态序列。我们首先定义局部概率,它是到达网格中的某个特殊的中间状态时的概率。然后，我们将介绍如何在t=1和t=n(>1)时计算这些局部概率。
这些局部概率与前向算法中所计算的局部概率是不同的，因为它们表示的是时刻t时到达某个状态最可能的路径的概率，而不是所有路径概率的总和。
考虑下面这个网格，它显示的是天气状态及对于观察序列干燥，湿润及湿透的一阶状态转移情况：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AvcaEJ7d-1633176787522)(https://www.52nlp.cn/images/trellis.1.gif)]
对于网格中的每一个中间及终止状态，都有一个到达该状态的最可能路径。举例来说，在t=3时刻的3个状态中的每一个都有一个到达此状态的最可能路径，或许是这样的：
我们称这些路径局部最佳路径(partial best paths)。其中每个局部最佳路径都有一个相关联的概率，即局部概率或。
因而是t时刻到达状态i的所有序列概率中最大的概率，而局部最佳路径是得到此最大概率的隐藏状态序列。对于每一个可能的i和t值来说，这一类概率（及局部路径）均存在。
特别地，在t=T时每一个状态都有一个局部概率和一个局部最佳路径。这样我们就可以通过选择此时刻包含最大局部概率的状态及其相应的局部最佳路径来确定全局最佳路径（最佳隐藏状态序列)。
2b.计算t=1时刻的局部概率’s
我们计算的局部概率是作为最可能到达我们当前位置的路径的概率（已知的特殊知识如观察概率及前一个状态的概率）。当t=1的时候，到达某状态的最可能路径明显是不存在的；但是，我们使用t=1时的所处状态的初始概率及相应的观察状态k1的观察概率计算局部概率
；即
——与前向算法类似，这个结果是通过初始概率和相应的观察概率相乘得出的。
2c.计算t>1时刻的局部概率’s
现在我们来展示如何利用t-1时刻的局部概率计算t时刻的局部概率
。
考虑如下的网格：
我们考虑计算t时刻到达状态X的最可能的路径；这条到达状态X的路径将通过t-1时刻的状态A，B或C中的某一个。
因此，最可能的到达状态X的路径将是下面这些路径的某一个
（状态序列），…，A，X
（状态序列），…，B，X
或 （状态序列），…，C，X
我们想找到路径末端是AX,BX或CX并且拥有最大概率的路径。
回顾一下马尔科夫假设：给定一个状态序列，一个状态发生的概率只依赖于前n个状态。特别地，在一阶马尔可夫假设下，状态X在一个状态序列后发生的概率只取决于之前的一个状态，即
Pr (到达状态A最可能的路径) .Pr (X | A) . Pr (观察状态 | X)
与此相同，路径末端是AX的最可能的路径将是到达A的最可能路径再紧跟X。相似地，这条路径的概率将是：
Pr (到达状态A最可能的路径) .Pr (X | A) . Pr (观察状态 | X)
因此，到达状态X的最可能路径概率是：
其中第一项是t-1时刻的局部概率，第二项是状态转移概率以及第三项是观察概率。
泛化上述公式，就是在t时刻，观察状态是kt，到达隐藏状态i的最佳局部路径的概率是：
这里，我们假设前一个状态的知识（局部概率）是已知的，同时利用了状态转移概率和相应的观察概率之积。然后，我们就可以在其中选择最大的概率了（局部概率)。
2d.反向指针，'s
考虑下面这个网格
在每一个中间及终止状态我们都知道了局部概率，(i,t)。然而我们的目标是在给定一个观察序列的情况下寻找网格中最可能的隐藏状态序列——因此，我们需要一些方法来记住网格中的局部最佳路径。
回顾一下我们是如何计算局部概率的，计算t时刻的’s我们仅仅需要知道t-1时刻的[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hCyrw9NR-1633176787535)(https://www.52nlp.cn/images/delta.gif)]'s。在这个局部概率计算之后，就有可能记录前一时刻哪个状态生成了
(i,t)——也就是说，在t-1时刻系统必须处于某个状态，该状态导致了系统在t时刻到达状态i是最优的。这种记录（记忆）是通过对每一个状态赋予一个反向指针
完成的，这个指针指向最优的引发当前状态的前一时刻的某个状态。
形式上，我们可以写成如下的公式
其中argmax运算符是用来计算使括号中表达式的值最大的索引j的。
请注意这个表达式是通过前一个时间步骤的局部概率’s和转移概率计算的，并不包括观察概率（与计算局部概率本身不同）这是因为我们希望其能回答这些问题：“如果我在这里，最可能通过哪条路径到达下一个状态？"——这个问题与隐藏状态有关，因此与观察概率有关的混淆（矩阵)因子是可以被忽略的。
2e.维特比算法的优点
通过使用递归减少计算复杂度——这一点和前向算法使用递归减少计算复杂度是完全类似的。
算法总结
1、维特比算法的形式化定义
5.前向-后向算法（了解）
根据观察序列生成隐马尔科夫模型(Generating a HMM from a sequence of obersvations)
与HMM模型相关的“有用”的问题是评估（前向算法）和解码（维特比算法）——它们一个被用来测量一个模型的相对适用性，另一个被用来推测模型隐藏的部分在做什么（“到底发生了”什么）。可以看出它们都依赖于隐马尔科夫模型（HMM）参数这一先验知识——状态转移矩阵，混淆（观察）矩阵，以及pi向量（初始化概率向量）。
然而，在许多实际问题的情况下这些参数都不能直接计算的，而要需要进行估计——这就是隐马尔科夫模型中的学习问题。前向-后向算法就可以以一个观察序列为基础来进行这样的估计，而这个观察序列来自于一个给定的集合，它所代表的是一个隐马尔科夫模型中的一个已知的隐藏集合。
前向-后向算法首先对于隐马尔科夫模型的参数进行一个初始的估计（这很可能是完全错误的），然后通过对于给定的数据评估这些参数的的价值并减少它们所引起的错误来重新修订这些HMM参数。从这个意义上讲，它是以一种梯度下降的形式寻找一种错误测度的最小值。
EM 算法
假定集合Z = (X,Y。)由观测数据 X 和未观测数据Y 组成，Z = (X,Y)和 X 分别称为完整数据和不完整数据。假设Z的联合概率密度被参数化地定义为P(X，Y|Θ)，其中Θ 表示要被估计的参数。Θ 的最大似然估计是求不完整数据的对数似然函数L(X;Θ)的最大值而得到的：
L(Θ; X )= log p(X |Θ) = ∫log p(X ,Y |Θ)dY ；(1)
EM算法包括两个步骤：由E步和M步组成，它是通过迭代地最大化完整数据的对数似然函数Lc( X;Θ )的期望来最大化不完整数据的对数似然函数，其中：
Lc(X;Θ) =log p(X，Y |Θ) ； (2)
假设在算法第t次迭代后Θ 获得的估计记为Θ(t ) ，则在（t+1）次迭代时，
E-步：计算完整数据的对数似然函数的期望，记为：
Q(Θ |Θ (t) ) = E{Lc(Θ;Z)|X;Θ(t) }； (3)
M-步：通过最大化Q(Θ |Θ(t) ) 来获得新的Θ 。
通过交替使用这两个步骤，EM算法逐步改进模型的参数，使参数和训练样本的似然概率逐渐增大，最后终止于一个极大点。
直观地理解EM算法，它也可被看作为一个逐次逼近算法：事先并不知道模型的参数，可以随机的选择一套参数或者事先粗略地给定某个初始参数λ0 ，确定出对应于这组参数的最可能的状态，计算每个训练样本的可能结果的概率，在当前的状态下再由样本对参数修正，重新估计参数λ ，并在新的参数下重新确定模型的状态，这样，通过多次的迭代，循环直至某个收敛条件满足为止，就可以使得模型的参数逐渐逼近真实参数。
EM算法的主要目的是提供一个简单的迭代算法计算后验密度函数，它的最大优点是简单和稳定，但容易陷入局部最优。
二、使用HMM进行文本分类
1.问题分析
将文本分类用HMM模型来描述
（1）模型中的隐藏状态
在中文分词中一般只有4个状态：STATES={‘B’,‘I’,‘E’,‘S’},
- B：代表一个词的开始
- I ：代表一个词的中间部分，若词为两个字则没有I
- E：代表一个词的结束
- S：代表一个单独的字作为一个词
例如：小明是中国人，对应的状态序列就是：B,E,S,B,I,E
（2）观察状态
在中文分词中就是对应每一个字符
（3）状态转移矩阵A
在中文分词中就是状态序列STATES={‘B’,‘I’,‘E’,‘S’}的转移概率，这个状态概率矩阵是在训练阶段参数估计中得到。在中文分词中状态转移矩阵是一个4*4的矩阵，
{'B': {'B': 0.0, 'I': 0.0, 'E': 0.0, 'S': 0.0},
'I': {'B': 0.0, 'I': 0.0, 'E': 0.0, 'S': 0.0},
'E': {'B': 0.0, 'I': 0.0, 'E': 0.0, 'S': 0.0},
'S': {'B': 0.0, 'I': 0.0, 'E': 0.0, 'S': 0.0}}
（4）混淆矩阵（发射概率矩阵）B
在中文分词中发射概率指的是每一个字符对应状态序列STATES={‘B’,‘M’,‘E’,‘S’}中每一个状态的概率，通过对训练集每个字符对应状态的频数统计得到。
2. 代码流程
首先定义类
class HMMModel:
初始化模型参数：
def __init__(self):
self.A = {} # 状态转移概率矩阵
self.B = {} # 发射概率矩阵
self.PI = {} # 初始状态矩阵
self.stateSet = [] # 存放状态
self.state_num = {} # ‘B,I,E,S’每个状态在训练集中出现的次数
self.Sentence_Num = 0 # 训练集语句数量
# 初始化所有概率矩阵
def initArray(self):
#初始化状态矩阵
self.stateSet = ['B', 'I', 'E', 'S']
# 初始化状态转移矩阵
for state0 in self.stateSet:
self.A[state0] = {}
for state1 in self.stateSet:
self.A[state0][state1] = 0.0
# 初始化PI,B，初始化状态计数
for state in self.stateSet:
self.PI[state] = 0.0 # PI['B'] = 0.0等
self.B[state] = {}
self.stateCount[state] = 0
初始化结果：
A:
{'B': {'B': 0.0, 'I': 0.0, 'E': 0.0, 'S': 0.0},
'I': {'B': 0.0, 'I': 0.0, 'E': 0.0, 'S': 0.0},
'E': {'B': 0.0, 'I': 0.0, 'E': 0.0, 'S': 0.0},
'S': {'B': 0.0, 'I': 0.0, 'E': 0.0, 'S': 0.0}}
B:
{'B': {}, 'I': {}, 'E': {}, 'S': {}}
PI:
{'B': 0.0, 'I': 0.0, 'E': 0.0, 'S': 0.0}
state_num:
{'B': 0, 'I': 0, 'E': 0, 'S': 0}
接着读取数据集，这里是将两个数据集合并作为一个大数据集
数据集：
训练集中将句子的每个字都标注了标志，读取训练集的函数
def getTrainSet(self):
trainSet = {} # 字典，句子对应状态
tmpSentence = ''
tmpSentenceState = ''
preNull = False
with open('../dataset/dataset2/train.utf8', encoding='utf-8') as trainFile:
while True:
s = trainFile.readline()
if s == "": # 文件读完
break
s = s.strip() # 去掉头尾空格
if s == "": # 读到换行符
if not preNull:
trainSet[tmpSentence] = tmpSentenceState
tmpSentence = ''
tmpSentenceState = ''
preNull = True
continue
preNull = False
s = s.replace(" ", "")
tmpSentence += s[0]
tmpSentenceState += s[1]
with open('../dataset/dataset1/train.utf8', encoding='utf-8') as trainFile:
while True:
s = trainFile.readline()
if s == "": # 文件读完
break
s = s.strip() # 去掉头尾空格
if s == "": # 读到换行符
if not preNull:
trainSet[tmpSentence] = tmpSentenceState
tmpSentence = ''
tmpSentenceState = ''
preNull = True
continue
preNull = False
s = s.replace(" ", "")
tmpSentence += s[0]
tmpSentenceState += s[1]
#print(len(trainSet))
#print(trainSet)
return trainSet
部分输出如下：
37365
'台北市长马英久星期二表示，他2月中旬将前往香港访问，同香港*官员就市政管理和台北、香港之间的文化交流等问题交换看法。': 'BEBEBIEBIEBESSBEBESBEBEBESSBEBEBESBEBESBESBEBESBEBESBEBEBES',
'马英久说，他在访问香港期间不会触及任何政治问题，并且期待台北与香港加强交流。': 'BIESSSSBEBEBESSBEBEBEBESBEBEBESBEBEBES',
'马英久还表示，台北市副市长白秀雄将与2月下旬前往上海参加城市论坛。': 'BIESBESBIEBIEBIESSBEBEBEBEBEBEBES'
使用HMM进行分词还应用到一个技巧，即取对数。在解码时，如果某个字符没有出现过，那么对应字典 位置为0，在后续的计算中，这是被禁止的，如果在不同概率相乘过程中，有一项为0，那么其他的就都是0，而且过多的0-1间概率相乘会导致结果很小，甚至溢出，因此，在概率上习惯取log对数形式，当x大时，log也大，x小时，log也小，而在学习和解码的过程中，仅需要比对大小，对数值没有要求，因此取log队最终结果没有影响。而又因0在log中无定义，故将0赋值为极小值-3.14e+100。另外，因为去了对数，乘法变成了加法。
为了实现上述功能，定义了如下数据处理的函数：
def Data_processing(self):
'''
对数据进行预处理
将‘0’变为极小值-3.14e+100
将统计结果取对数
:return:
'''
for key in self.PI:
# 如果该项为0，则手动赋予一个极小值
if self.PI[key] == 0.0:
self.PI[key] = -3.14e+100
# 如果不为0，则计算概率，再对概率求log
else:
self.PI[key] = np.log(self.PI[key] / self.Sentence_Num)
# 状态转移概率，与上方PI思路一样，求得A的概率对数
for key0 in self.A:
for key1 in self.A[key0]:
if self.A[key0][key1] == 0.0:
self.A[key0][key1] = -3.14e+100
else:
self.A[key0][key1] = np.log(
self.A[key0][key1] / self.state_num[key0])
# 发射概率，与上方PI思路一样，求得B的概率对数
for key in self.B:
for word in self.B[key]:
if self.B[key][word] == 0.0:
self.B[key][word] = -3.14e+100
else:
self.B[key][word] = np.log(self.B[key][word] / self.state_num[key])
下面进行训练，学习HMM的（PI,A,B），分别参考书中公式
PI依据式10.36
A依据式10.37
B依据式10.38
由于在文本分词中，采取统计的方法获取参数，并没有真的用到前向后向算法，而是借用其中公式来得到A，B，PI的统计值。
def train(self):
self.initArray() #初始化参数
trainSet = self.getTrainSet() # 字典，句子:状态
# print(trainSet)
for sent in trainSet:
self.Sentence_Num += 1
wordList = [] # 字符表
for i in range(len(sent)):
wordList.extend(sent[i]) #将句子中每个字符加入字符表
lineStateList = [] # 句子的状态序列，list类型
for i in range(len(trainSet[sent])):
lineStateList.extend(trainSet[sent][i]) #将句子每个字符对应标志加入标志表
首先将训练集中每句话的字符和其对应的词性提取出来，效果如下：
sent: 马英久还表示，台北市副市长白秀雄将与2月下旬前往上海参加城市论坛。
wordList ['马', '英', '久', '还', '表', '示', '，', '台', '北', '市', '副', '市', '长', '白', '秀', '雄', '将', '与', '2', '月', '下', '旬', '前', '往', '上', '海', '参', '加', '城', '市', '论', '坛', '。']
lineStateList ['B', 'I', 'E', 'S', 'B', 'E', 'S', 'B', 'I', 'E', 'B', 'I', 'E', 'B', 'I', 'E', 'S', 'S', 'B', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'S']
'''
def train(self):
self.initArray()
trainSet = self.getTrainSet() # 字典，句子:状态
# print(trainSet)
for sent in trainSet:
self.Sentence_Num += 1
wordList = [] # list类型，一个字一个entry
for i in range(len(sent)):
wordList.extend(sent[i])
lineStateList = [] # 句子的状态序列，list类型
for i in range(len(trainSet[sent])):
lineStateList.extend(trainSet[sent][i])
'''
#如果是开头第一个字，PI中对应标志位位置加1
self.PI[lineStateList[0]] += 1
# 因为A涉及到前一个状态，因此需要等整条状态链都生成了才能开始统计
# 统计t时刻状态和t+1时刻状态的所有状态组合的出现次数 如BE,BI,SB,IE等等
for j in range(len(lineStateList) - 1):
self.A[lineStateList[j]][lineStateList[j + 1]] += 1
# 统计每个状态的数量
for p in range(len(lineStateList)):
self.state_num[lineStateList[p]] += 1 # 记录每一个状态的出现次数
# 对于该单词中的每一个字，在生成的状态链中统计B
for state in self.stateSet:
#如果wordList[p]不在矩阵中，则将wordList[p]这个字加入发射概率矩阵
if wordList[p] not in self.B[state]:
self.B[state][wordList[p]] = 0.0
# 遍历状态链中每一个状态，并找到对应的中文汉字，在B中
# 对应位置加1
self.B[lineStateList[p]][wordList[p]] += 1
self.Data_processing()
torch.save(self, '../models/hmm.model')
输出结果：
A：
{'B': {'B': 0.0, 'I': 122157.0, 'E': 695633.0, 'S': 0.0},
'I': {'B': 0.0, 'I': 57989.0, 'E': 122157.0, 'S': 0.0},
'E': {'B': 400275.0, 'I': 0.0, 'E': 0.0, 'S': 413343.0},
'S': {'B': 392921.0, 'I': 0.0, 'E': 0.0, 'S': 297712.0}}
数据处理后
{'B': {'B': -3.14e+100, 'I': -1.9012984772751438, 'E': -0.16178335751427536, 'S': -3.14e+100},
'I': {'B': -3.14e+100, 'I': -1.1335142958412838, 'E': -0.3884605305764256, 'S': -3.14e+100},
'E': {'B': -0.7144537690390731, 'I': -3.14e+100, 'E': -3.14e+100, 'S': -0.6823278231729181},
'S': {'B': -0.6109424581589946, 'I': -3.14e+100, 'E': -3.14e+100, 'S': -0.8884244557644772}}
可以看到在A 矩阵种，词的开始状态B后一定接着I即词的中间部分或者词的结束E，I后接着下一个中间词I或者词结束E，而E后不能接结束词E和中间词I ，S后为新词B或者另一个单独词S 。
B：
'B': {'推': 1500.0, '行': 2293.0, '股': 779.0, '份': 44.0, '制': 1737.0, '要': 1076.0, '遵': 118.0, '循': 56.0, '经': 6499.0, '济': 111.0, '规': 1639.0, '律': 126.0, '，': 2.0, '尊': 231.0, '重': 3647.0, '群': 1017.0, '众': 203.0, '意': 1265.0, '愿': 221.0, '。': 1.0, '改': 2554.0, '革': 322.0, '的': 158.0, '最': 1721.0, '终': 329.0, '目': 2209.0, '是': 301.0, '让': 65.0, '得': 804.0, '实': 3374.0, '惠': 69.0, 。。。
数据处理后
{'B': {'推': -6.301140471819027, '行': -5.876744576051424, '股': -6.95634981303858, '份': -9.830171224991068, '制': -6.154446092668223, '要': -6.633355118187598, '遵': -8.843676234443663, '循': -9.58900916817418, '经': -4.83495726101498, '济': -8.904830657596994, '规': -6.212519280165498, '律': -8.77807895195785, '，': -12.921213678349384, '尊': -8.171943148387534, '重': -5.412700668100648, '群': -6.689748462860768, '众': -8.301154879867541, '意': -6.471533457747707, '愿': -8.216198157391576, '。': -13.614360858909329, '改': -5.768944822316843, '革': -7.8398093133649205, '的': -8.551765825882361,。。。
PI：
{'B': 24594.0, 'I': 0.0, 'E': 0.0, 'S': 12771.0}
数据处理后
{'B': -0.41823192663199793, 'I': -3.14e+100, 'E': -3.14e+100, 'S': -1.0735574618681285}
接着利用HMM的“解码”功能，给定观测序列，推出隐藏序列，这里使用维特比算法
def Viterbi(self, sentence, PI, A, B):
# 初始化分词后的文章列表
retsentence = []
delta = [{}] # 动态规划表
path = {} # 存路径
# 首先对在训练集中没有出现过的句首字进行处理
# 若第一个字没有出现在发射矩阵的'B'状态列表上，则默认他为S，所以初’S‘外其他状态的概率都为负无穷大
if sentence[0] not in B['B']:
for state in self.stateSet:
if state == 'S':
# 取0于无穷小1相区分，表示不计算发射概率为0对结果不造成影响。
B[state][sentence[0]] = 0
else:
B[state][sentence[0]] = -3.14e+100
# 依据算法10.5 第一步：初始化
for state in self.stateSet:
# delta[t][state]表示时刻t到达state状态的所有路径中，概率最大路径的概率值
# 初始化δ状态链中第一个状态的四种状态概率,因取log，所以乘法变加法
delta[0][state] = PI[state] + B[state][sentence[0]]
path[state] = [state]
接下来进行算法10.5的第二步
#算法10.5中的第二步：递推
#依次处理整条链
for i in range(1, len(sentence)):
delta.append({})
new_path = {}
# 开始计算
for state0 in self.stateSet:
# 初始化一个临时列表，用于存放四种概率
tmpbelta = []
for state1 in self. stateSet:
# 若这个字在当前状态的发射矩阵中不存在,则默认发射概率为0忽略该字
if sentence[i] not in B:
for state in self.stateSet:
B[state][sentence[0]] = 0
prob = delta[i - 1][state1] \
+ A[state1][state0] \
+ B[state0][sentence[i]]
tmpbelta.append((prob, state1))
#在state1-->state0四条路经中选择概率最大的路径，将概率和节点存入best
best = max(tmpbelta)
#更新i的δ
delta[i][state0] = best[0]
#将该节点加入路径
new_path[state0] = path[best[1]] + [state0]
print(new_path)
path = new_path
print(path)
print([(delta[len(sentence) - 1][state], state) for state in self.stateSet])
print(max([(delta[len(sentence) - 1][state], state) for state in self.stateSet]))
prob, state = max([(delta[len(sentence) - 1][state], state) for state in self.stateSet])
第二步算法实现如图，这里以i=1（i-1 =0）为例。
对于每个i值，i和i-1分别对应state0和state1，首先计算i = 0中每个状态state1到i=1中B的概率
prob = delta[i - 1][state1] \
+ A[state1][state0] \
+ B[state0][sentence[i]]
并将结果存入tmpbelta，当state1中四种状态全部计算完，选取概率最大的，这里假设是I，将I到B 的概率记为δ(B1)，并将节点记入new_path中为{‘B’: [ ‘I’ , ‘B’ ]}。接着同样的步骤处理state0中每个节点，得到δ(E1)、δ(S1)、δ(I1)和相对应的路径。这样i=1点就处理完了，接下来处理i=2、3、4、。。。直到最后一个点。期间得到的路径如下：
{'B': ['S', 'B']}
{'B': ['S', 'B'], 'I': ['B', 'I']}
{'B': ['S', 'B'], 'I': ['B', 'I'], 'E': ['B', 'E']}
{'B': ['S', 'B'], 'I': ['B', 'I'], 'E': ['B', 'E'], 'S': ['S', 'S']}
{'B': ['B', 'E', 'B']}
{'B': ['B', 'E', 'B'], 'I': ['S', 'B', 'I']}
{'B': ['B', 'E', 'B'], 'I': ['S', 'B', 'I'], 'E': ['S', 'B', 'E']}
{'B': ['B', 'E', 'B'], 'I': ['S', 'B', 'I'], 'E': ['S', 'B', 'E'], 'S': ['B', 'E', 'S']}
{'B': ['S', 'B', 'E', 'B']}
{'B': ['S', 'B', 'E', 'B'], 'I': ['S', 'B', 'I', 'I']}
{'B': ['S', 'B', 'E', 'B'], 'I': ['S', 'B', 'I', 'I'], 'E': ['S', 'B', 'I', 'E']}
{'B': ['S', 'B', 'E', 'B'], 'I': ['S', 'B', 'I', 'I'], 'E': ['S', 'B', 'I', 'E'], 'S': ['S', 'B', 'E', 'S']}
。。。
{'B': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'S', 'B']}
{'B': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'S', 'B'],
'I': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'B', 'I']}
{'B': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'S', 'B'],
'I': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'B', 'I'],
'E': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'B', 'E']}
{'B': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'S', 'B'],
'I': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'B', 'I'],
'E': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'B', 'E'],
'S': ['S', 'B', 'E', 'S', 'B', 'E', 'B', 'E', 'S', 'B', 'E', 'S', 'S', 'B', 'I', 'I', 'I', 'E', 'B', 'E', 'B', 'E', 'B', 'E', 'S', 'S']}
如此就可求到i等于最后一个点的对应路径。
求得所有的δ和路径后，计算最后一排的最大概率，并选取最大概率对应的路径最为最终结果。
prob, state = max([(delta[len(sentence) - 1][state], state) for state in self.stateSet])
[(-180.60538672684038, 'B'), (-180.16360323078624, 'I'), (-176.1302635679538, 'E'), (-180.02321523339765, 'S')]
(-176.1302635679538, 'E')
最后，处理最终结果，
if path[state][-1] == 'B' or path[state][-1] == 'I': # 最后一个字状态不是'S'或'E'则修改
if path[state][-2] == 'B' or path[state][-2] == 'I':
path[state][-1] = 'E'
else:
path[state][-1] = 'S'
首先修正最后一个点，如果最后一个词是 ’B‘ 或者 ’I‘ 则明显发生错误，这时需要判断，如果得到的倒数第二个词是 ’B‘ 或者 ‘I’，那么最后一个一定是 ‘E’，否则的话就是单独词’s’
# 开始对该行分词
curLine = ''
# 遍历该行每一个字
for i in range(len(sentence)):
# 在列表中放入该字
curLine += sentence[i]
# 如果该字是S->单个词 或 E->结尾词 ，则在该字后面加上分隔符 |
# 此外如果改行的最后一个字了，也就不需要加 |
if (path[state][i] == 'S' or path[state][i] == 'E') and i != (len(sentence) - 1):
curLine += '|'
# 在返回列表中添加分词后的该行
retsentence.append(curLine)
return retsentence
最后，按照BESI的规则，在‘E’和‘S’对应的词的后面加入’|’，方便观看分词效果。
def predict(self,sentence):
return self.Viterbi(sentence, self.PI, self.A, self.B)
if __name__ == '__main__':
model = HMMModel()
model.train()
print(model.predict("孙广博的机器学习大作业，用隐马尔科夫模型进行文本分词"))
输出结果：
中国银行是中国四大银行之一
['中国|银行|是|中国|四大|银行|之|一']
弘扬伟大建党精神，开创更加美好未来
['弘扬|伟大|建党|精神|，|开创|更加|美好|未来']
始终把人民放在心中最高位置，永远保持同人民群众的血肉联系，忠实履行宪法和法律赋予的职责，努力为实现人民对美好生活的向往而不懈奋斗。
['始终|把|人民放|在|心中|最高|位置|，|永远|保持|同|人民|群众|的|血肉|联系|，|忠实|履行|宪法|和|法律|赋予|的|职责|，|努力|为|实现|人民|对|美好|生活|的|向往|而|不懈|奋斗|。']
三、总结
1.模型
在HMM文本分词的过程中，输入即一条句子，而输出则是分词标志序列，要求的就是使其分词效果最好的HMM三个参数，A、B、PI，在本题中，HMM是在学习过程中，通过统计来获得
2.算法
维特比算法，部分baum-welch算法
def predict(self,sentence):
return self.Viterbi(sentence, self.PI, self.A, self.B)
if __name__ == '__main__':
model = HMMModel()
model.train()
print(model.predict("用隐马尔科夫模型进行文本分词"))
中国银行是中国四大银行之一
['中国|银行|是|中国|四大|银行|之|一']
弘扬伟大建党精神，开创更加美好未来
['弘扬|伟大|建党|精神|，|开创|更加|美好|未来']
始终把人民放在心中最高位置，永远保持同人民群众的血肉联系，忠实履行宪法和法律赋予的职责，努力为实现人民对美好生活的向往而不懈奋斗。
['始终|把|人民放|在|心中|最高|位置|，|永远|保持|同|人民|群众|的|血肉|联系|，|忠实|履行|宪法|和|法律|赋予|的|职责|，|努力|为|实现|人民|对|美好|生活|的|向往|而|不懈|奋斗|。']
三、总结
1.模型
在HMM文本分词的过程中，输入即一条句子，而输出则是分词标志序列，要求的就是使其分词效果最好的HMM三个参数，A、B、PI，在本题中，HMM是在学习过程中，通过统计来获得
2.算法
维特比算法，部分baum-welch算法
四、源码
源码正上传至本人博客