Language Model-(二)

Posted on | In | | Visitors: |
Words count in article:

Markov Models

在上一篇文章中对语言模型进行了感性认知和形式化地定义，并给出一个最简单的LMs,虽然它不强大。

现在基于我们之前的形式化定义，系统性地分析：如何estimate 一个句子的联合概率？

考虑一个随机变量序列，$X_1,X_2,…,X_n$ . 每个随机变量的取值都可能是 $\color{blue}{\mathbb{V}}$ 中的任意一个值。现在我们假设：序列的长度 n 是一个固定的值，比如：n=100. 我们的目标是：面对任意序列 $x_1,x_2,…,x_n$ ，其中-

  • $n\ge 1$,
  • $x_i \in \color{blue}{\mathbb{V}}$ for $i=1,2,…,n-1$

我们需要estimate 一个联合概率：
$$
P(X_1=x_1,X_2=x_2,…,X_n=x_n)
$$
根据概率论中的链式法则(Chain Rule):
$$
\begin{align}
&P(X_1=x_1,X_2=x_2,…,X_n=x_n)\\
&= P(X_1=x_1)P(X_2=x_2|X_1=x_1)…P(X_n=x_n|X_1=x_1,…,X_{n-1}=x_{n-1})\\
&=\prod_{i=1}^{n} P(x_i|x_{1}^{i-1})
\end{align}
$$

Markov Assumption

上面，我们已经将联合概率转化为一些列条件概率的乘积，但似乎亦然无法帮助我们计算一整个句子的联合概率。因为我们不知道什么方法能够计算$P(x_i|x_1^{i-1})$, 也即：我们无法计算给定一个特定词之前很长的词序列的情况下，该词出现的概率。正如前一篇文章提到的那样，我们无法数出 $C(x_1,x_2,…,x_{i-1},x_i)$, 因为句子是无穷的，任何一个特定的context都可能是从来没有出现过的。

因此，我们需要通过一些假设约束来使得这个计算可行。马尔可夫假设背后的朴素想法是这样的：

在一个随机变量序列,$X_1,X_2,…,X_n$ 中, 任何一个随机变量取某一个特定值的概率只与它之前的少数几个随机变量相关，而与离它更远的随机变量没有关系。

我们现在形式化地表示马尔可夫假设，

  • 一阶马尔可夫假设(First-Order markov assumption)：

    $P(x_i|x_1^{i-1})\approx P(x_i|x_{i-1})$，从而整个随机变量序列的联合概率为
    $$
    P(X_1=x_1,X_2=x_2,…,X_n=x_n)=\prod_{i=1}^{n} P(x_i|x_{i-1})
    $$

  • 二阶马尔可夫假设(Second-Order Markov assumption):

    $P(x_i|x_1^{i-1})\approx P(x_i|x_{i-2},x_{i-1})$, 此时整个随机变量序列的联合概率为
    $$
    P(X_1=x_1,X_2=x_2,…,X_n=x_n)=\prod_{i=1}^{n}P(x_i|x_{i-2},x_{i-1})
    $$

这样，我们计算联合概率就简单多了，将这个思想用来建模句子的联合概率，就是N-Grams Language Model。

N-Grams 语言模型

将上述概率理论应用于语言模型，即：estimate 一个句子的联合概率：$P(w_1,w_2,…,w_n)$

基于Markov 假设，很容易理解N-Grams语言模型。这里一用Dan Jurafsky一句很形象的话来描述：

The intuition of the N-gram model is that instead of computing the probability of a word given its entire history, we can approximate the history by just the last few words.

  • Bigram

    用来 $P(w_n|w_{n-1})$ 近似$P(w_n|w_1^{n-1})$. 换句话说，我们不是计算：
    $$
    P(\text{university}|\text{Clition’s book store near my})
    $$
    而是计算：
    $$
    P(\text{university}|\text{my})
    $$
    总之，我们做了以下近似：
    $$
    P(w_n|w_1^{n-1})\approx P(w_n|w_{n-1})
    $$

  • N-gram

    类似的思想，我们做以下近似：
    $$
    P(w_n|w_1^{n-1})\approx P(w_n|w_{n-N+1}^{n-1})
    $$

计算整个句子的联合概率

如果基于bigram模型，整个句子的联合概率可以按照下面公式计算：
$$
P(w_1^{n})\approx \prod_{i=1}^n P(w_i|w_{i-1})
$$
可见只要我们会计算$P(w_i|w_{i-1})$ , 句子的联合概率我们就可以计算了。那么现在的问题是，我们如何计算bgrams or N-gram 概率呢？一个直观的估计概率的方法叫做极大似然估计(Maximim likelihood estimation,MLE).

极大似然估计（MLE）

用MLE对N-Grams模型的参数进行估计：从语料库中计数，并把这个计数归一化(Normalize), 使得计数在0，1之间。

举个例子，要计算一个具体的bigram：$\text{xy}$ 的概率，我们要数一下$C(\text{xy})$, 然后用所有第一个字是 $\text{x}$ 的bigram的个数进行归一化，即：
$$
P(w_n|w_{n-1})=\frac{C(w_{n-1}w_n)}{\sum_{w} C(w_{n-1}w)}
$$
其实，我们可以简化上述公式：因为$C(w_{n-1}w_n)=C(w_{n-1})$ . 即：以 $\text{x}$ 为首词的 bigram 的个数必然等于 $\text{x}$ 出现的次数。所以，
$$
P(w_n|w_{n-1})=\frac{C(w_{n-1}w_n)}{C(w_{n-1})}
$$

一个具体例子-bigram

终于到了具体例子了，我平时在看书的时候最怕全是逻辑描述、定义、公式而没有具体例子。实际上具体例子对于概念和问题的理解是非常重要的！

  • 考虑我们现在有一个微型语料库（Corpus），只包含三个句子。
  • 我们需要在语料库中每个句子的开头添加个一个特殊符号：[BOS] 标明这是句子的开始。
  • 在每个句子的结束也添加一个特殊符号：[EOS] ，标明这是句子的结束。

语料库为：

[BOS] I am Sam [EOS]

[BOS] Sam am I [EOS]

[BOS] I do not like green eggs and ham [EOS]

我们现在计算一些bigrams的概率：

$$
\begin{align}
&P(\text{I|[BOS]})=\frac{2}{3}, &&P(\text{Sam|[BOS]})=\frac{1}{3}, &&&P(\text{am|I})=\frac{1}{3}\\
&P(\text{[EOS]|Sam})=\frac{1}{2}, &&P(\text{Sam|am})=\frac{1}{2}, &&&P(\text{do|I})=\frac{1}{3}
\end{align}
$$

通用情况的MLE N-gram参数估计：

$$
P(w_n|w_{n-N+1}^{n-1})= \frac{C(w_{n-N+1}^{n-1}w_n)}{C(w_{n-N+1}^{n-1})}
$$

也就是就是我们上面讲过的：用一个特定的N-grams的个数除以其prefix的个数。这个比值我们称为相对频率（relative frequency）. 这种方法在MLE中是估计参数的一种常用手段（不是唯一手段）。在MLE中，在给定模型的情况下，最后的结果参数集(resulting parameter set)会最大化训练数据 T 的似然，i.e. $P(T|M)$。

现在我们基于bigram语法计算一下整个句子的联合概率：

$$
\begin{align}
P(\text{[BOS] I am Sam [EOS]})&= P(I|[BOS])P(am|I)P(Sam|am)P([EOS]|Sam)\\
&=\frac{2}{3} \cdot \frac{1}{3}\cdot \frac{1}{2}\cdot \frac{1}{2}\\
&=0.056
\end{align}
$$

以上的内容，就是所谓基于计数的N-gram语言模型（Count-based N-gram Language Model），此外还有Neural Language Model等其他模型，会在之后的文章中陆续介绍。

N-Gram 能捕获什么？

如果我们的语料库足够大的话，我们计算的 bi-gram 概率确实能够encode一些语言学现象，比如syntantic

  • 动词之后往往接名词、代词、介词(这类bigram的概率较高)
  • 形容词之后往往接名词

有些可能捕获不是syntantic现象，而是个人习惯：

  • I want…
  • I should….

有些可能捕获的是文化方面的现象：

  • Chinese food…
  • English book…

总之，N-gram 模型确实可以捕获到很多语言学、文化、社会、个人偏好等现象，所谓 Encode Some Facts。可想而知，随着N不断变大，Trigram, 4-gram, 5-gram 等将会encode 更多有意义的信息。

一些特殊问题

上面的例子为了计算简单，我们举了基于bigram的例子。实际上，当我们的语料库足够大的时候，Trigram，乃至4-gram，5-gram是更加合理的选择（更加强大！）。这里我们以 Trigram为例 进行说明。

  1. 在我们选择 Trigram 模型时，我们对语料中每个句子开始和结尾的context 都需要进行扩展。即：语料中的句子应该处理成这样：

    $$
    \text{[BOS] [BOS] I want to drink beer [EOS] [EOS]}
    $$

  2. Log format of probability.

    我们在计算和表示语言模型的概率的时候常常采用它的对数形式。因为概率值是一个[0,1]区间的数值，语言模型中概率值是连乘的形式，因此一个句子的联合概率可能会是一个非常小的数字，可能会导致下溢出。因此我们采用Log Probability 来避免下溢出的问题。

    在log space 中做加法与在linear space做乘法是等价的。我们所有对log probability 进行的计算和存储都可以转化回概率,

$$
p_1\times p_2 \times p_3…\times p_n = exp(\log p_1 +\log p_2 +…+\log p_n)
$$

如何评价语言模型

评价语言模型的方式主要分为两类。

外部性方法（Extrinsic）

将语言模型嵌入到一个实际的应用中，然后测量这个应用的性能的提升有多少，这本质是一种End-to-End的评价方式，也是最好的评价方式。Extrinsic 的评测方式是唯一的一种可以评价一个组件中性能的提升是否真的帮助了你的任务的评测方式。其过程如下：

  1. 找一个实际Task（这个任务必须以LM作为其组件(components)之一）

  2. End-to-End的训练

    • Task with $LM_a$ , 计算性能, $P_a$.（比如：Acc，P，R，F）

    • Task with $LM_b$, 计算性能, $P_b$.

    • 比较 $P_a$ and $P_b$，得到比较的结果$C$. ( Compare with some certain metric.)
  3. 重复步骤2（N-次，N=0,…,1），计算加权平均的$C_{avg}$, 以此来衡量 $LM_a$ 与 $LM_b$ 哪个好，有多好。

然而，这种“最好”的评测方式有一个很大的缺点，那就是为了评测语言模型本身性能的好坏，你还需要找另外一个实际的任务，并以end-to-end的方式训练，比较若干次训练结果的（训练若干次）。这个整个过程非常昂贵的(时间、计算资源)。

内部性方法（Intrinsic）

鉴于Extrinsic的评测方法的缺点，我们希望有一种测量指标可以快速地评测语言模型其潜在性能。Intrinsic 的评价方法就是一种可以独立于具体应用来评测一个语言模型的性能的评价方法。

用Intrinsic的评价方法来评测语言模型，其过程如下：

  • 在training set（training corpus） 上训练我们的语言模型 $LM_a, LM_b$.
  • 用已经训练好的语言模型 $LM_a,LM_b$ （trained），来model test set （test corpus）。以此比较哪个语言模型更好。

然而，所谓的 “model test set“ 是什么意思？

答案很简单：哪个模型给 test set 赋予了更高的概率-即：更准确地在test set上做出了预测，那么它就是一个更好的模型。

其核心institution就是：在给定两个概率模型（probability model）的情况下，更好的那个模型更好地拟合了test data，或者说更好的预测了test data的细节，也就因此会对test data 赋予一个更高的概率。

此外还需要注意几个问题：

  1. test set 不能和 training set 有重合。

如果重合，那么在训练model 的时候就已经引入了一些偏见（bias），即：model更加侧重那些重合的部分（可以这样考虑，同样的句子多次被model拟合，模型就更加偏向给这些句子打更高的概率），这会使得在 test set 上的预测出奇的好，这很容易理解：因为模型已经见过一大部分这些数据了，模型对它们“不陌生”，自然就预测的好。但实际上，这对模型的泛化（generalization）能力有很大的影响。

  1. 有些时候，我们还需要一个dev set. 那corpus 如何划分为：training set， dev set，test set呢？
    • 我们需要尽可能多的training data，因为我们希望模型learning 的足够充分（不要欠拟合！）
    • test set 不能太小，因为太小的话它的代表性不够强。
    • 上述两条似乎有些冲突，此刻怎么办呢？我们希望选择：能够使我们有足够的统计信息来评测两个语言模型在统计上显著性差异的最小test set。

困惑度（Perplexity）

在具体的实践中，我们往往不采用raw probability 作为metric来评价语言模型，而是采用了一个变种-perplexity。

定义：

“The perplexity(sometimes called PP for short) of a language model on test set is the inverse probability of the test set, normalized by the number of words.”

给定一个test set, $W=w_1w_2…w_N$ :
$$
\begin{align}
PP(W) &= P(w_1w_2….w_N)^{-\frac{1}{N}}\\
&=\sqrt[N]{\frac{1}{P(w_1w_2…w_N)}}
\end{align}
$$
我们可以用Chain-Rule来扩展上述公式，
$$
PP(W)=\sqrt[N]{\prod_{i=1}^N\frac{1}{P(w_i|w_1…w_{i-1})}}
$$
因此，如果我们基于一个bigram 语言模型来计算perplexity，我们得到：
$$
PP(W)=\sqrt[N]{\prod_{i=1}^N \frac{1}{P(w_{i}|w_{i-1})}}
$$
根据上述公式可知：word sequence的条件概率越高，perplexity的值越小，反之亦然。因此，minimize perplexity等同于maximize test set上的probability。

有以下2个细节需要注意：

  • 上面公式中我们的计算是基于 test set中所有words 的序列，这就必然会跨越很多句子的边界。因此我们在计算概率的时候要记得加入[BOS] 和 [EOS]，也就是句子开始和结束的标志符。
  • 我们还需要在test set中token总数N中计入每个句子的[EOS]，切记：不包括[BOS]!!

一个例子-计算perplexity

TO-DO…

泛化和计数0的问题

平滑-Smoothing

Kneser-Ney Smoothing

困惑度与熵的关系

后记

坚持原创分享，您的支持是我继续创作的动力!