自然语言处理学习笔记（2）——二元语法与中文分词
自然语言处理学习笔记（2）——二元语法与中文分词
一、 语言模型
1. 语言模型
-
模型指的是对事物的数学抽象；语言模型（Language Model，LM）则指的是对语言模型的数学抽象。
-
定义语言模型：把句子表示为单词列表 w = w1w2…wk，每个wt，t∈[1,k] 都是一个单词，则：
p ( w ) = p ( w 1 w 2 ⋯ w k ) p(w)=p(w_1w_2\cdots w_k) p(w)=p(w1w2⋯wk)= p ( w 1 ∣ w 0 ) × p ( w 2 ∣ w 0 w 1 ) × ⋯ × p ( w k + 1 ∣ w 0 w 1 w 2 ⋯ w k ) =p(w_1|w_0)\times p(w_2|w_0w_1)\times \cdots \times p(w_{k+1}|w_0w_1w_2\cdots w_k) =p(w1∣w0)×p(w2∣w0w1)×⋯×p(wk+1∣w0w1w2⋯wk)
= ∏ t = 1 k + 1 p ( w t ∣ w 0 w 1 ⋯ w t − 1 ) =\prod_{t=1}^{k+1} p(w_t|w_0w_1\cdots w_{t-1}) =t=1∏k+1p(wt∣w0w1⋯wt−1)
其中，w0 = BOS（Begin Of Sentence，< s >），wk+1 = EOS（End of Sentence，
< /s>），用来标记句子首尾的两个特殊“单词”。也就是说，对已经给定的词语序列，预测下一个词语的后验概率，一个单词一个单词地乘上后验概率，就能估计任意一句话地概率。
即使用极大似然估计（Maximum Likelihood Estimation，MLE）来计算每个后验概率：
p ( w t ∣ w 0 ⋯ w t − 1 ) = p M L ( w t ∣ w 0 ⋯ w t − 1 ) = c ( w 0 ⋯ w t ) c ( w 0 ⋯ w t − 1 ) p(w_t|w_0\cdots w_{t-1})=p_{ML}(w_t|w_0\cdots w_{t-1})=\frac{c(w_0\cdots w_t)}{c(w_0\cdots w_{t-1})} p(wt∣w0⋯wt−1)=pML(wt∣w0⋯wt−1)=c(w0⋯wt−1)c(w0⋯wt)
其中 c(w0···wt) 表示 w0···wt 的计数（count） -
产生的问题
-
数据稀疏，指的是长度越大的句子越难出现，语料库中极有可能统计不到长句子的频次，导致
p(wk|w1w2···wk-1) 为 0 。
-
计算代价大。
-
2. 马尔科夫链与二元语法
-
为解决上诉的两个问题，需要使用马尔科夫假设来简化语言模型：给定时间线上有一串事件顺序发生，假设每个事件发生的概率只取决于前一个事件，那么这串时间构成的因果链被称作马尔科夫链（Markov Chain）。
在语言模型中，第 t 个事件指的就是 wt 作为第 t 个单词出现，即每个单词的出现的概率只取决于前一个单词：
p ( w t ∣ w 0 ⋯ w t − 1 ) = p ( w t ∣ w t − 1 ) p(w_t|w_0\cdots w_{t-1})=p(w_t|w_{t-1}) p(wt∣w0⋯wt−1)=p(wt∣wt−1) -
基于此假设，由于每次计算只涉及连续两个单词的二元接续，此时的语言模型称为二元语法（bigram）模型：
p ( w ) = p ( w 1 w 2 ⋯ w k ) = p ( w 1 ∣ w 0 ) × p ( w 2 ∣ w 1 ) × ⋯ × p ( w k + 1 ∣ w k ) p(w)=p(w_1w_2\cdots w_k)=p(w_1|w_0)\times p(w_2|w_1)\times \cdots \times p(w_{k+1}|w_k) p(w)=p(w1w2⋯wk)=p(w1∣w0)×p(w2∣w1)×⋯×p(wk+1∣wk)= ∏ t = 1 k + 1 p ( w t ∣ w t − 1 ) =\prod_{t=1}^{k+1} p(w_t| w_{t-1}) =t=1∏k+1p(wt∣wt−1)
这样就缓解一部分数据稀疏问题。
3. n 元语法
-
n 元语法 (n-gram) 的定义：每个单词的概率仅取决于该单词之前的 n 个单词，即：
p ( w ) = ∏ t = 1 k + n − 1 p ( w t ∣ w t − n + 1 ⋯ w t − 1 ) p(w)=\prod_{t=1}^{k+n-1} p(w_t|w_{t-n+1}\cdots w_{t-1}) p(w)=t=1∏k+n−1p(wt∣wt−n+1⋯wt−1)- 当
n = 1时的 n 元语法称为一元语法（unigram）； - 当
n = 3时的 n 元语法称为三元语法（trigram）； -
n ≥ 4时，数据稀疏和计算代价又变得显著起来，在实际工程中几乎不使用； - 另外，深度学习带了一种递归神经网络语言模型（RNN Language Model），理论上可以记忆无限个单词，可以看作“无穷元语法”（∞-gram）。
- 当
4. 数据稀疏与平滑策略
-
平滑策略：使用低阶 n 元语法平滑高阶 n 元语法，所谓平滑，就是使 n 元语法频次的折线平滑为曲线。
-
其中最简单的一种是线性插值法（linear interpolation），它定义新的二元语法概率为
p ( w t ∣ w t − 1 ) = λ p M L ( w t ∣ w t − 1 ) + ( 1 − λ ) p ( w t ) p(w_t|w_{t-1})=\lambda p_{ML}(w_t|w_{t-1})+(1-\lambda)p(w_t) p(wt∣wt−1)=λpML(wt∣wt−1)+(1−λ)p(wt)
其中，λ∈(0,1)为平滑因子。类似地，一元语法也可以通过线性插值来平滑：
p ( w t ) = λ p M L ( w t ) + ( 1 − λ ) 1 N p(w_t)=\lambda p_{ML}(w_t)+(1-\lambda)\frac{1}{N} p(wt)=λpML(wt)+(1−λ)N1
二、 训练
-
词语种数：语料库中有多少个不重复的词语。
-
总词频：所有词语的词频之和。
-
训练（train）指的是，给定样本集（dataset，训练所用的样本集称为训练集）估计模型参数的过程。训练也叫编码（encoding）因为学习学习算法将知识以参数的形式编码（encode）到模型中。
三、 预测
1. 相关概念
- 在机器学习和自然语言处理的语境下，预测（predict）指的是利用模型对样本（句子）进行推断的过程，在中文分词中也就是利用模型推断分词序列。
- 词网：指的是句子中所有一元语法构成的网状结构，是 HanLP 工程上的概念。值得注意的是，词网必须保证从起点出发的所有路径都会连通到终点。
2. 节点间的距离计算
- 若赋予下述词图中每条边以二元语法的概率作为概率，则中文分词任务转换为有向无环图上的最长路径问题，如下图中的句子（商品和服务）：
二元语法概率可以利用 MLE 辅以平滑策略得到，在中文分词中常使用如下经验公式：
p
^
(
w
t
∣
w
t
−
1
)
=
λ
[
μ
c
(
w
t
−
1
w
t
)
c
(
w
t
)
+
1
−
μ
]
+
(
1
−
λ
)
c
(
w
t
)
+
1
N
\hat{p}(w_t|w_{t-1})=\lambda [\mu \frac{c(w_{t-1}w_t)}{c(w_t)}+1-\mu]+(1-\lambda)\frac{c(w_t)+1}{N}
p^(wt∣wt−1)=λ[μc(wt)c(wt−1wt)+1−μ]+(1−λ)Nc(wt)+1
其中，λ,u∈(0,1)为两个不同的平滑因子，也即上式额外做了一次平滑，称为加一平滑或拉普拉斯平滑。
- 考虑到多个 (0,1) 之间的浮点数连续相乘之后会发生下溢出（等于0），因此工程上经常对概率取负对数，将浮点数转化为负对数之间的加法：
∏ t = 1 k + 1 p ^ ( w t ∣ w t − 1 ) → − ∑ t = 1 k + 1 log p ^ ( W t ∣ w t − 1 ) \prod_{t=1}^{k+1}\hat{p}(w_t|w_{t-1})\rightarrow -\sum_{t=1}^{k+1}\log \hat{p}(W_t|w_{t-1}) t=1∏k+1p^(wt∣wt−1)→−t=1∑k+1logp^(Wt∣wt−1)
相应的，词图上的最长路径转化为负对数的最短路径。
3. 词图上的维特比算法
- 在自然语言处理领域，处理的图是一种特例：由马尔科夫链构成的网状图，该特例上的最短路径算法称为维特比算法（Viterbi Algorithm）。维特比算法为向前（forward）和向后（backward）两个步骤：
- 向前：由起点出发从前往后遍历节点，更新从起点到该节点的最小花费以及前驱指针。
- 向后：由终点出发从后往前回溯前驱指针，取得最短路径。
四、评测
-
标准化评测：分为训练、预测、计算准确率三步。
-
误差分析，将二元语法与词典分词的成绩汇总后如下表：
算法 P R F1 ROOV RIV 最长匹配 89.41 94.64 91.95 2.58 97.14 二元语法 92.38 96.70 94.49 2.58 99.26 -
模型调整：可以启用分词器的用户词典来解决词条无法识别和消歧失误的问题，甚至可以将无法识别的词条加入核心词典，并打开调试模式，追踪分词过程。
五、总结
- 在本章中为了学习语言模型的参数，亲自标注了一份微型的语料库，并用极大似然法估计了二元语法分词模型的参数。在统计方法中，为了解决数据稀疏的问题，使用了平滑策略。为了搜索最大概率的分词序列，将中文分词转化为有向无环图上的最短路径问题，学习并现实了维特比算法来高效求解词网上的最短路径问题。
- 相较于词典分词，二元语法分词器在 MSR 语料库上 F1 值提高了 2.5% ，通过误差分析，二元语法分词暴露了一些问题，可以通过模型调整来改善。