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})$

语言模型树结构

使用 起始/结束 符号,语言模型分配的词序列及其连续概率可以排列成树结构:

lm_tree

文本生成

使用语言模型,可以基于模型的生成概率分布生成新的文本。

在前一张幻灯片所示的树结构中,我们寻找权重(对数概率)之和较大的分支。穷举搜索是不可行的,众所周知的策略包括

  • 贪婪搜索

  • 集束(beam)搜索

  • 随机集束搜索

一个简单的集束搜索示例,$K=5$:

beam_search

评估

语言模型的评估可以是

  • 外在的: extrinsic,模型在拼写检查、语音转文字系统等组件中的表现如何,或者

  • 内在的: intrinsic,分配的概率与测试语料库中的文本对应得有多好?

最广泛使用的内在评估指标是语料库的 困惑度
语言模型 $\mathcal M$ 在序列 $\mathbf w = \langle w_1,\dots, w_n\rangle$ 上的困惑度为

$$\mathbf{PP}_{\mathcal M}(\mathbf w) = \sqrt[n]{\frac{1}{P_{\mathcal M}(\mathbf w)}}$$

使用链式法则,困惑度可以重写为

$${\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$ 的概率。

一个简单的马尔可夫语言模型:

https://slideplayer.com/slide/4578484/

增加 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)方法。

Author

Aloento

Posted on

2024-10-04

Updated on

2024-11-14

Licensed under

CC BY-NC-SA 4.0

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×