NLP-NGram-LM
基于 N-gram 的语言模型
语言模型
什么是语言模型?
回想一下,在形式语言理论中,语言 $\mathcal L$ 只是某个字母表 $\Sigma$ 的子集 $\Sigma^*$。
相反,统计语言模型切换到语言生成的概率视图,并为来自词汇 $V$ 的任意序列 $\langle w_1,\dots, w_n\rangle \in V^*$ 分配一个概率
$$P(\langle w_1,\dots, w_n\rangle)$$
使得
$$\sum_{\mathbf{w}\in V^*} P(\mathbf{w}) = 1$$
词汇表
传统上,语言模型的词汇表由完整的单词组成,例如,
$V$ = {the, be, to, of, $\dots$}
但最近基于子词和字符的语言模型也被广泛使用,词汇表如
{ _don’, t, _un, related, $\dots$} 或 {a, b, c, d, e, f, $\dots$}
本章讨论基于单词的语言建模技术 — 字符和子词级别建模技术将是第 9 和第 11 讲的主题。
为什么语言模型有用?
概率语言模型对于大量的自然语言处理应用非常重要,其目标是生成合理的词序列作为输出,其中包括
拼写和语法检查
预测输入
语音转文字
聊天机器人
机器翻译
摘要生成
使用连续概率建模
使用链式法则,令token序列 $\mathbf{w} = \langle w_1,\dots, w_n\rangle$ 的概率可以重写为
$$P(\mathbf w)= P(w_1)\cdot P(w_2 \vert w_1 )\dots \cdot P(w_n\vert w_1,\dots, w_{n-1})$$
也就是说,对于一个完整的语言模型,只需指定
- 对于任何 $w\in V$ 单词,概率 $P(w)$ 表示它将是序列中的第一个单词,以及
- 对于任何 $w\in V$ 和 $\langle w_1,\dots,w_n\rangle$ 部分序列,单词 $w$ 的连续概率,即
$$P(w ~\vert ~ w_1,\dots,w_n)$$
起始和结束符号
基于链式法则的序列概率公式
需要一个单独的、无条件的子句来表示起始概率,并且
没有解决在某个点结束序列的概率。
这两个问题都可以通过在词汇表中添加显式的 $\langle start \rangle$ 和 $\langle end \rangle$ 符号来解决,并假设语言的所有序列都以这些符号 开始/结束。通过这个技巧,起始/结束 概率可以重写为条件形式 $P(w \vert \langle start \rangle)$ 和 $P(\langle end \rangle \vert \mathbf{w})$
语言模型树结构
使用 起始/结束 符号,语言模型分配的词序列及其连续概率可以排列成树结构:
文本生成
使用语言模型,可以基于模型的生成概率分布生成新的文本。
在前一张幻灯片所示的树结构中,我们寻找权重(对数概率)之和较大的分支。穷举搜索是不可行的,众所周知的策略包括
贪婪搜索
集束(beam)搜索
随机集束搜索
一个简单的集束搜索示例,$K=5$:
评估
语言模型的评估可以是
外在的: extrinsic,模型在拼写检查、语音转文字系统等组件中的表现如何,或者
内在的: intrinsic,分配的概率与测试语料库中的文本对应得有多好?
最广泛使用的内在评估指标是语料库的 困惑度。
语言模型 $\mathcal M$ 在序列 $\mathbf w = \langle w_1,\dots, w_n\rangle$ 上的困惑度为
使用链式法则,困惑度可以重写为
$${\sqrt[n]{\frac{1}{P_{\mathcal M}(w_1)}\cdot \frac{1}{P_{\mathcal M}(w_2 \vert w_1 )}\dots\cdot \frac{1}{P_{\mathcal M}(w_n\vert w_1,\dots, w_{n-1})}}}$$
这正是语料库中所有单词条件概率倒数的几何平均值。
换句话说,困惑度衡量的是,对于语言模型来说,语料库中的单词(续词)平均而言有多“出乎意料”。
取困惑度的对数,通过一些简单的代数运算可以得到结果
$$-\frac{1}{n} \left(\log P_{\mathcal M}(w_1) + \sum_{i=2}^n\log P_{\mathcal M}(w_i \vert w_1,\dots, w_{i-1})\right)$$
这就是每个单词的平均交叉熵和负对数似然。
一个简单的推论是:通过最小化平均交叉熵(cross-entropy)或最大化平均对数似然(log-likelihood),也可以最小化模型在训练数据上的困惑度(perplexity)。
基于 N-gram 的建模
概率估计
我们如何从文本语料库中估计所需的 $P(\mathbf{w})$ 概率?我们可以尝试使用出现次数来获得最大似然估计:
$$P(\mathbf{w}) \approx \frac{C(\mathbf{w})}{C(\mathrm{all \space texts \space in \space corpus})}$$
但在任何现实的语料库中,大多数文本只出现一次,许多可能的文本根本没有出现。一个选项是切换到连续概率:
$$P(w_{i} \vert w_1,\dots,w_{i-1})$$
使用基于计数的估计,我们可以得到
$$P(w_{i} \vert w_1,\dots,w_{i-1}) \approx \frac{C(\langle w_1,\dots,w_{i} \rangle)}{C(\langle w_1,\dots,w_{i-1} \rangle)}$$
但同样会遇到数据稀疏性问题。缓解这一问题的一种方法是使用
$$P(w_{i} \vert w_1,\dots,w_{i-1}) \approx P(w_{i} \vert w_{i-k},\dots,w_{i-1})$$
的近似,对于某个 $k$,假设续词概率(近似)由序列中前 $k$ 个 token 决定。
N-gram 语言模型
使用这种近似,$\langle w_1,\dots,w_n \rangle$ 序列的概率可以计算为
$$P(w_1) \prod_{i=2}^k P(w_{i} \vert w_{1},\dots,w_{i-1}) \prod_{i=k+1}^n P(w_{i} \vert w_{i-k},\dots,w_{i-1})$$
其主要优点是
$$P(w_{i} \vert w_{i-k},\dots,w_{i-1}) \approx
\frac{C(\langle w_{i-k},\dots,w_{i}\rangle)}{C(\langle w_{i-k},\dots,w_{i-1} \rangle)}$$
的估计可以仅基于语料库中最长为 $k+1$ 的子序列计数,即所谓的 N-gram $(N=1, 2, 3,\dots)$
一元模型
最简单的 $N$-gram 语言模型是一元(Unigram)模型,它为序列 $\langle w_1,\dots,w_n \rangle$ 分配概率
$$P(w_1)\cdot P(w_2)\cdot \dots \cdot P(w_{n-1})\cdot P(w_n)$$
其中单词概率可以简单地估计为
$$P(w) \approx \frac{C(w)}{\sum_{w’ \in V}C(w’)}$$
一元模型忽略了单词的顺序,最可能的序列只是完全由最频繁的单词组成的序列。
二元模型
自然地,基于更长子序列的 $N$-gram 模型更加细致,甚至所谓的二元(Bigram)模型($N=2$)计算序列概率简单为
$$P(\langle w_1,\dots,w_n \rangle) = P(w_1)\prod_{i=2}^n P(w_i \vert w_{i-1})$$
其中
$$P(w_2 \vert w_1) \approx \frac{C(\langle w_1,w_2\rangle)}{C(w_1)}$$
马尔可夫语言模型
$N$-gram 模型实际上是用概率有限状态机(Markov)来建模语言,其中状态对应于 $N-1$-gram。
例如,在 $\mathcal M$ 二元模型的情况下,状态对应于词汇表加上一个开始和结束状态,状态 $w_1$ 和 $w_2$ 之间的转移概率只是 $P(w_2 \vert w_1)$ 的续词概率。
很容易看出,token 序列 $\mathbf{w}=\langle w_1,\dots,w_n \rangle$ 的 $P_\mathcal{M}(\mathbf{w})$ 概率正是马尔可夫模型经过状态 $\langle start \rangle,w_1,\dots,w_n,\langle end \rangle$ 的概率。
一个简单的马尔可夫语言模型:
增加 N 值
由于实际上人类语言过于复杂,无法满足低阶马尔可夫假设,因此具有更高 N 值(如 N=3,4 甚至 5)的 N-gram 模型通常具有更好的内在和外在性能。不幸的是,随着 N 的增加,语言学上可能的 N-gram 数量急剧增加。例如,在谷歌的 1,024,908,267,229 token 的 N-gram 语料库 中,N-gram 计数为:
- 一元模型:13,588,391
- 二元模型:314,843,401
- 三元模型:977,069,902
- 四元模型:1,313,818,354
- 五元模型:1,176,470,663
对于较高 $N$ 值,语言学上可能的 $N$-gram 数量极高,这带来了两个重要问题:
数据稀疏性: 即使在大型文本语料库中,许多可能的组合也不会出现,或者只会很少出现,因此很难估计它们的概率;
模型大小: 即使估计是正确的,模型的大小也会非常庞大。
平滑
加法平滑
Additive smoothing。我们如何解决在语料库中从未或很少出现的 $N$-gram 的问题?一个简单的解决方案是通过某个数值过度计数每个 $N$-gram,并使用
$$P(w_{i} \vert w_{i-k},\dots,w_{i-1}) \approx \frac{C(\langle w_{i-k},\dots,w_{i}\rangle)+\delta}{C(\langle w_{i-k},\dots,w_{i-1} \rangle) + \delta|V|}$$
$|V|$ 乘数来自于这样一个事实:对于每个 $N-1$-gram,恰好有 $|V|$ 个 $N$-gram 是它的延续。
$\delta$ 的一个广泛选择是 1。
一个重要的问题是:
如果 $C(\langle w_1,w_2\rangle)=0$ 和 $C(\langle w_1,w_3\rangle)=0$,那么在加法平滑下我们有
$$p(w_1,w_2)=p(w_1,w_3)$$
假设现在 $w_2$ 比 $w_3$ 常见得多。那么,直观上,我们应该有
$$p(w_1,w_2)>p(w_1,w_3)$$
而不是上述的相等关系,因此加法平滑的结果似乎是错误的—我们应该以某种方式在一元和二元计数之间进行插值。
插值
Interpolation,在二元模型的情况下,我们通过一定的权重添加来自一元模型频率的概率:
$$P(w_2 \vert w_1) \approx \lambda_1\frac{C(\langle w_1, w_2 \rangle)}{C(w_1)} + (1 - \lambda_1)\frac{C(w_2)}{\sum_{w\in V}C(w)}$$
对于任意 $k$ 的递归解决方案:
$$P(w_{k+1} \vert w_1.. w_k) \approx \lambda_k\frac{c(\langle w_1 .. w_{k+1} \rangle)}{c(\langle w_1 .. w_k\rangle)} + (1-\lambda_k)P(w_{k+1} \vert w_2 .. w_{k})$$
$\lambda_k$ 是基于语料库经验设置的,通常使用期望最大化(Expectation Maximization)方法。
NLP-NGram-LM