NLP-隐马尔可夫模型

Posted on Edited on

隐马尔可夫模型

本讲内容：

基于隐马尔可夫模型分词(HMM)

一.隐马尔可夫模型（HMM）

HMM模型也是基于N元语法模型，本讲在N = 2的情况下，只计算历史 = 1的条件概率。

1. HMM特点：

隐马尔可夫模型中有两个序列，一个是状态序列，另一个是观测序列，其中状态序列是隐藏的。

2. 简单例子理解：

假设有N个盒子，每个盒子中分别有M种不同颜色的球（除颜色外均相同），一个人根据概率分布随机地选取一个初始的盒子，从中根据不同颜色的球的概率分布，随机选择出一个球，然后将这个球展示给观众看。观众看到的不同颜色的球的序列就是观测序列，而对应的不可见的盒子的序列是状态序列。

3. 中文分词上的解释：

我们有N = 4个状态：\(s_1\): 词首(B)，\(s_2\): 词中(M)，\(s_3\): 词尾(E)，\(s_4\): 单字成词(S)，相当于上面的盒子

  • 初始概率：这个概率是句首状态的概率分布情况

    \(\pi = \{ \pi_{i} \}\)，其中\(\pi_i = P(q_1 = s_i), 1 \leq i \leq N\)

    ​ \(\pi_ \geq 0\) \(\sum_{i=1}^N \pi_i = 1\)

  • 状态转移概率矩阵\(𝐴 = \{ 𝑎_{𝑖𝑗} \}\)， \(a_{ij} = P(q_t = s_j| q_{t-1} = s_i), 1 \leq i, j \leq N\)

    ​ \(a_{ij} \geq 0\)， \(\sum_{j = 1}^N a_{ij} = 1\)

    理解：如果上一个状态是S， 则下一个状态不可能是M 或是 E，所以我们在计算最终的标注概率时，加入这一部分概念是很合理的。

  • 发射概率：如果在确定了转移状态后，我们需要计算当前状态对应当前字符的概率，也即发射概率:

    从状态\(𝑠_𝑗\)观察到符号\(𝑣_𝑘\)的概率分布矩阵\(𝐵 = \{ 𝑏_𝑗(𝑘) \}\)（另一个理解就是：从第j个口袋去除第k个颜色的小球）

然后我们要根据四个状态对应的初始概率分布随机选择一个，作为文本串第一个字符(相当于小球)的标注并累计相应的发射概率。对于之后的每个字符的状态标注则有两方面影响：首先是由上一个状态作为条件，计算下一个状态的状态转移概率与对应状态到词的发射概率。由此，逐步累积计算一个划分的概率后，我们选择概率最大的那个划分作为最终的分词结果。故：观察序列

二. HMM分词算法描述

1. 问题描述：

已知输入文本串\(O = O_1O_2...O_T\)，状态集$S = { s_1 = B, s_2 = M, s_3 = E, s_4 = S } \(， 初始概率分布：\)= { i }\(， 状态转移矩阵：\)A = { a{ij} }\(， 发射概率：\)B = { b_j(k) }\(；求出一个概率最大的状态序列（最优观察序列）。解决方法：维特比算法（\)， A, B$需要通过对训练语料进行统计得出，所以算是已知的）。

2. 维特比算法（动态规划算法）：

1). 在给定模型 𝜇(A, B, \(\pi\)) 和文本串O的条件下，求出使得𝑃(𝑄|𝑂, 𝜇)最大的标注序列Q。数学描述：\({Q}' = \underset{Q}{argmax} P(Q|O, u)\)

2). 定义：维特比变量\(𝛿_𝑡(𝑖)\)：是在时间t时，HMM沿着某一条路径到达状态\(𝑠_𝑖\)，输出观察序列\(𝑂_1𝑂_2 … 𝑂_𝑡\)的最大概率。

3). \(𝛿_𝑡(i) = \max_{𝑞_1,𝑞_2,…,𝑞_{𝑡−1} } 𝑃(𝑞_1, 𝑞_2 … 𝑞_𝑡= 𝑠𝑖,𝑂_1𝑂_2…𝑂_𝑡|𝜇)\)

4). 动态转移方程：\(𝛿_{𝑡+1}(i) = \max_𝑗 [𝛿_𝑡(𝑗)∙𝑎_{𝑗𝑖}]∙𝑏_𝑖(𝑂_{𝑡+1})\)

5). 伪代码：

初始化： \(prob[1][i] = \pi_iB[i][o_1], 1 \leq i \leq N\)

​ \(path[1][i] = 0\) -------------------- 记忆回退路径

​ for t from 2 to T:

​ for j from 1 to N:

​ \(prob[t][j] = \underset{1 \leq i \leq N}{max}(prob[t-1][i]*A[i][j])*B[j][O_t]\)

​ \(path[t][j] = \underset{1 \leq i \leq N}{argmax}(prob[t-1][i]*A[i][j])*B[j][O_t]\)

​ \(maxProb = \underset{1 \leq i \leq N}{max}(prob[T][i])\)

​ \(finalPath[T] = \underset{1 \leq i \leq N}{argmax}(prob[T][i])\)

输出路径：\(finalPath[i] = path[i + 1](fianlPath[i+1]), 1 \leq i \leq T-1\)