NLP基础:语言模型

什么是语言模型

语言模型旨在为语句的联合概率函数建模,是用来计算一个句子概率的模型,对有意义的句子赋予大概率,对没有意义的句子赋予小概率,也就是用来判断一句话是否是人话的概念。这样的模型可以用于NLP中的很多任务,如机器翻译、语音识别、信息检索、词性标注以及手写识别等。语言模型考虑两个方面的子任务(以“How long is a football game?”为例):

  • 句子中的词序:“How long game is a football?”
  • 句子中的词义:“How long is a football bame?”

语音识别举例:

“厨房里的食油用完了”和“厨房里的石油用完了”

文本翻译举例:

“you go first”:“你走先”和“你先走”

给定一个句子的词语序列:

图片

  • 如果假设句子中的每个词都相互独立,则整体的句子概率为:

图片

  • 然而,句子中的每一个词的含义均与前面的词紧密相关,所以实际的语言模型概率可以通过条件概率计算为:
    图片
    求解上式中的条件概率:
    图片
    这样就存在两个问题
  • 参数空间太大:条件概率

    P

    (

    W

    k

    W

    1

    ,

    W

    2

    ,

    .

    .

    .

    ,

    W

    k

    1

    )

    P(W_{k}|W_{1},W_{2},…,W_{k-1})

    P(WkW1,W2,...,Wk1)的可能性太多,计算开销巨大,甚至到无法估算;

  • 数据稀疏严重:非常多的词语组合在语料库中并未出现,依据最大似然估计获得的概率将为0;

参数空间太大:Markov假设

针对参数空间过大的问题,Markov假设是解决该问题的有效方法,即随意一个词出现的概率只与它前面出现的一个或者几个词有关。

  • Probability is usually conditioned on window of n previous words.
  • An incorrect but necessary Markov assumption.
    图片

N元模型

假设当前词的出现概率只与它前面的N-1个词相关,而这些概率参数是可以通过大规模语料库计算获得的。

unigram模型

如果一个词的出现与它周围的词是独立的,那么就称之为unigram模型,也就是一元语言模型
图片
上式成立的基础就是条件无关假设,即每个词的出现都是条件无关的。
缺陷:忽视了词间的语义信息,如:
两句话:“He eats Pizza”和“He drinks Pizza”,在unigram模型下的概率相同,但是显然前者的概率要大于后者。

bigram模型

根据N元语言模型的定义,bigram模型是考虑当前词前面的一个词的条件概率,即二元语言模型,如:
图片图片

trigram 模型图片图片

那么,我们在面临实际问题时,如何选择依赖词的个数,即n。

  • 更大的n:对下一个词出现的约束信息更多,具有更大的辨别力
  • 更小的n:在训练语料库中出现的次数更多,具有更可靠的统计信息,具有更高的可靠性。

理论上,n越大越好,经验上trigram用的最多,尽管如此,原则上能用bigram解决,绝不使用trigram。

一般采用最大似然估计(Maximum Likelihood Estimate,MLE)来构建语言模型

N元语言模型的评价

目前有两种评价方法:

  • 实用方法:通过查看语言模型在实际应用(如拼写检查、机器翻译)中的表现来评价,优点是直观、实用,缺点是缺乏针对性、不够客观;
  • 理论方法:迷惑度/困惑度/混乱度(preplexity),其基本思想是给测试集赋予较高概率值的语言模型较好,公式如下:
    图片
    Chain rule:
    图片
    For bigrams:
    图片
    因此,迷惑度越小,句子概率越大,语言模型越好

数据稀疏:平滑技术Smoothing

大规模数据统计方法与有限的训练语料之间必然产生数据稀疏,导致出现零概率问题。

数据稀疏问题定义:“The problem of data sparseness, also known as the zero-frequency problem arises when analyses contain configurations that never occurred in the training corpus. Then it is not possible to estimate probabilities from observed frequencies, and some other estimation scheme that can generalize (that configurations) from the training data has to be used. —— Dagan”。

对于如下的概率模型,也就是 p(e)在 event space E 下的概率分布,模型很可能会用最大似然估计(MLE),如下:

P

M

L

E

=

c

(

x

)

Σ

e

c

(

e

)

P_{MLE}=\frac{c(x)}{\Sigma_{e}c(e)}

PMLE=Σec(e)c(x)
然而,由于并没有足够的数据,很多事件

x

x

x并没有在训练数据中出现,也就是

c

(

x

)

=

0

,

P

M

L

E

=

0

c(x)=0,P_{MLE}=0

c(x)=0,PMLE=0。这是有问题的,没有在训练数据中出现的数据,并不代表不会在测试数据中出现,如果没有考虑到数据稀疏性,那么模型就太简单了!

Data sparsity 是 smoothing 的最大原因。Chen & Goodman 在1998 年提到过,几乎所有数据稀疏的场景下,smoothing 都可以帮助提高 performance,而数据稀疏性几乎是所有统计模型(statistical modeling)都会遇到的问题。而如果你有足够多的训练数据,所有的 parameters 都可以在没有 smoothing 的情况下被准确的估计,那么你总是可以扩展模型,如原来是 bigram,没有数据稀疏,完全可以扩展到 trigram 来提高 performance,如果还没有出现稀疏,就再往高层推,当 parameters 越来越多的时候,数据稀疏再次成为了问题,这时候,用合适的平滑方法可以得到更准确的模型。实际上,无论有多少的数据,平滑几乎总是可以以很小的代价来提高 performance。

平滑技术的基本思想:降低已出现n-gram条件概率分布,以使未出现的n-gram条件概率非零,且经数据平滑后一定保证概率和为1。

平滑方法的两种思想:回退差值

回退:直观的理解,就是说如果没有 3gram,就用 bigram,如果没有 bigram,就用 unigram。

差值:就是把不同阶的模型结合起来。

二者区别:

  • 插值(Jelinek-Mercer)和回退(Katz)都涉及到来自较高和较低阶模型的信息
  • 主要区别:在决定非零计数的 n-gram 的概率时,差值模型使用低阶模型的信息,而回退模型则不使用
  • 相同点:在决定没有出现过的(零计数) n-gram 时,两者都用了低阶模型的信息
  • 事实证明,做差值模型的回退版本和做回退模型的差值版本都不难~(Kneser-Ney最开始是回退模型,而 Chen&Goodman 也做了差值版本)

另外还有一点,与差值平滑算法相比,回退算法所需参数较少,而且可以直接确定,无需通过某种迭代重估算法反复训练,因此实现更加方便。

Add-one(Laplace) Smoothing

加一平滑法,又称拉普拉斯定律,其保证每个n-gram在训练语料中至少出现1次,以bigram为例,公式如下:

  • MLE estimate:
    图片
  • Add-1 estimate:
    图片
    其中,

    V

    V

    V是所有n-gram的数量,

    V

    =

    {

    w

    :

    c

    (

    w

    )

    >

    0

    }

    {

    U

    N

    K

    }

    V={\{w:c(w)>0\}}\cup\{UNK\}

    V={w:c(w)>0}{UNK}

举例: 假设语料库为下面三个句子
图片
那么 JOHN READ A BOOK这句话的概率就是:
图片
而CHER READ A BOOK这个句子出现的概率是:
图片
使用Laplace平滑,那么概率就会变成:
图片
加 1 平滑通常情况下是一种很糟糕的算法,与其他平滑方法相比显得非常差;

然而,可以把加 1 平滑用在其他任务中,如文本分类,或者非零计数没那么多的情况下。

Additive smoothing

对加 1 平滑的改进就是把 1 改成 δ,且 0<δ≤1,也就是 pretend we’ve seen each n-gram δ times more than we have,当然,Gale & Church(1994) 吐槽了这种方法,说表现很差。
图片

Good-Turing smoothing

Good-Turing算法的基本思想是,用观察计数较高的N元组重新估计概率量的大小,并把它指派给那些具有零计数或者较低计数的N元组。

Idea: reallocate the probability mass of n-grams that occur r+1 times in the training data to the n-grams that occur r times.

一般情况下,我们选出现过一次的概率,也就是 Things seen once 这一概念:

Things seen once: 使用刚才已经看过一次的事物的数量来帮助估计从来没有见过的事物的数量。举个例子,假设你在钓鱼,然后抓到了18条鱼,种类如下:10 carp, 3 perch, 2 whitefish, 1 trout, 1 salmon, 1 eel,那么

下一条鱼是 trout 的概率是多少?

很简单,我们认为是 1/18

那么,下一条鱼是新品种的概率是多少?

不考虑其他,那么概率是 0,然而根据 Things seen once 来估计新事物,概率是 3/18(1 trout, 1 salmon, 1 eel)

在此基础上,下一条鱼是 trout 的概率是多少?

肯定就小于 1/18,那么怎么估计呢?

在Good-Turing下,对每一个计数

r

r

r 调整为

r

r^{*}

r,公式如下:

r

=

(

r

+

1

)

N

r

+

1

N

r

r^{*}=(r+1)\frac{N_{r+1}}{N_{r}}

r=(r+1)NrNr+1
其中,

r

r

r为某个n-gram出现的次数,

N

r

N_{r}

Nr 为出现次数为

r

r

r的n-gram的词组数量,

N

r

+

1

N_{r+1}

Nr+1为出现次数为

r

+

1

r+1

r+1的n-gram的词组数量,一般来说,发生次数为

r

r

r的n-gram词组数量多于发生次数为

r

+

1

r+1

r+1的n-gram词组数量。
然后,就有:

P

G

T

(

x

:

c

(

x

)

=

r

)

=

r

N

r

P_{GT}(x:c(x)=r)=\frac{r^{*}}{N_{r}}

PGT(x:c(x)=r)=Nrr
所以,当

c

=

1

c=1

c=1时:

c

(

t

r

o

u

t

)

=

2

1

3

=

2

3

c^{*}(trout)=2*\frac{1}{3}=\frac{2}{3}

c(trout)=231=32

P

(

t

r

o

u

t

)

=

2

3

1

18

=

1

27

P^{*}(trout)=\frac{2}{3}*\frac{1}{18}=\frac{1}{27}

P(trout)=32181=271
问题
如果

N

r

+

1

=

0

N_{r+1}=0

Nr+1=0怎么办?这在

r

r

r很高的情况下很常见,因为在对计数进行计数时(counts of counts),会出现“holes”。即使没有这个hole,对很高的

r

r

r来说,

N

r

N_{r}

Nr也是有噪音的(noisy)。所以,

r

r^{*}

r应该被定义为:
图片
问题是怎么估计这种期望呢?这需要更多的解释。

Jelinek-Mercer smoothing(Interpolation, 差值)

同样,以语言模型为例,我们看这样一种情况,如果 c(BURNISH THE) 和 c(BURNISH THOU) 都是 0,那么在前面的平滑方法 additive smoothing 和 Good-Turing 里,p(THE|BURNISH)=p(THOU|BURNISH),而这个概率我们直观上来看是错误的,因为 THE 要比 THOU 常见的多,p(THE|BURNISH)>p(THOU|BURNISH)应该是大概率事件。要实现这个,就希望把 bigram 和 unigram 结合起来,interpolate 就是这样一种方法。

用线性差值把不同阶的 N-gram 结合起来,这里结合了 trigram,bigram 和 unigram。用 lambda 进行加权:

图片

Σ

i

λ

i

=

1

\Sigma_{i}\lambda_{i}=1

Σiλi=1

怎样设置 lambdas?

把语料库分为 training data, held-out data, test data 三部分,然后

  • Fix the N-gram probabilities(on the training data)
  • Search for lambdas that give the largest probabilities to held-out set:
    图片

这种差值其实是一个递归的形式,我们可以把每个 lambda 看成上下文的函数,如果对于一个特定的 bigram 有特定的计数,假定 trigram 的计数是基于 bigram 的,那么这样的办法将更可靠,因此,可以使 trigram 的 lambda 值更高,给 trigram 更高权重。

图片

λ

(

w

n

2

n

1

)

\lambda(w_{n-2}^{n-1})

λ(wn2n1)通常用EM算法,在held-out data上训练得到(held-out interpolation),或者在 cross-validation 下训练得到(deleted interpolation)。

λ

(

w

n

2

n

1

)

\lambda(w_{n-2}^{n-1})

λ(wn2n1)的值依赖于上下文,高频的上下文通常会有更高的lambdas。

Katz smoothing

回退式算法。和 Good-Turing 一样,对计数进行调整,以 bigram 为例,非 0 计数的 bigram 都根据打折比率

d

r

d_{r}

dr进行打折,比率约为

r

r

\frac{r^{*}}{r}

rr。这个比率是由 Good-Turing 计算得到的,然后根据下一个低阶分布(如 unigram),对没有出现过的 bigram 重新分配从非零计数中减去的值。
以 bigram 为例看看它是怎么做的:
图片
对于

d

r

d_{r}

dr的一些探讨,当一个 n-gram 出现次数足够大时,MLE 其实是一个可靠的概率估计,而当计数不是足够大时,就可以采用 Good-Turing 对其进行平滑,让计数为 0 时,退回低阶模型。
图片

Witten-Bell smoothing

一个 JM smoothing 的实例,当 n-gram

w

i

n

+

1

i

w_{i-n+1}^{i}

win+1i在训练数据中出现的时候,我们应该用高阶模型,否则,用低阶模型。所以

1

w

i

n

+

1

i

1-w_{i-n+1}^{i}

1win+1i应该是一个单词在训练数据中没有出现在

w

i

n

+

1

i

w_{i-n+1}^{i}

win+1i后面的概率,可以用跟在

w

i

n

+

1

i

w_{i-n+1}^{i}

win+1i后的 unique words 的数量来估计,公式为:
图片
举个例子来理解一下,考虑 spite 和 constant 的 bigram,在 Europarl corpus 中,两个 bigram 都出现了 993 次,以 spite 开始的 bigram 只有 9 种,大多数情况下 spite 后面跟着 of(979次),因为 in spite of 是常见的表达,而跟在 constant 后的单词有 415 种,所以,我们更有可能见到一个跟在 constant 后面的 bigram,Witten-Bell 平滑就考虑了这种单词预测的多样性,所以:
图片

Absolute discounting

和 Jelinek-Mercer 相似,Absolute discounting 包括了对高阶和低阶模型的差值,然而它并不是用高阶模型的

P

M

L

E

P_{MLE}

PMLE乘以一个 lambda,而是从每个非零计数里减掉一个固定的discount δ∈[0,1]。

先简单的来看下 bigram model,加上 Absolute discounting 就是:
图片
完整的公式:
图片
一般来说,δ直接取 0.75。

Kneser-Ney smoothing

是 Absolute discounting 的一个扩展,对回退部分做了一个修正。

Idea: 只有在高阶模型的计数很小或者为 0 时,低阶模型才显得重要,(换种说法,只有在 bigram 没有出现过时,unigram 才有用),因此应针对该目的进行优化。举例:
图片
reading 后面跟 Francisco 还是 glasses 呢?因为 “San Francisco” 是个很常见的地名,所以 Francisco 有一个很高的 unigram 概率,比 glasses 高,而 Francisco 偏偏只在 San 后面出现,这就非常不合理。而更合理的方式是,给 Francisco 一个较低的 unigram 概率,这样,bigram 模型表现会更好。

改进的方案是,我们不看 how likely is w,而去看 how likely is w to appear as a novel continuation,也就是,对每个单词,我们看它对应的 bigram type 的数量,然后,每个 bigram type 在第一次出现的时候都是 novel continuation。
图片
所以,最后的公式为:
图片

平滑技术总结

  • 影响最大的因素是使用 modified backoff distribution,如 Kneser-Ney smoothing
  • Jelinek-Mercer 平滑在小型训练数据集上表现更好,而 Katz 在大型训练集上表现更好
  • Katz 在计数大的 n-grams 上效果很好,而 Kneser-Ney 适合小的计数
  • Absolute discounting 要优于 linear discounting
  • 在非零计数较低的情况下,Interpolated models 优于 backoff
  • 添加 free parameters 到算法中,通过 held-out data 上优化这些参数可以提高性能

语言模型变种

Class-based N-gram Model

该方法基于词类建立语言模型,以缓解数据稀疏问题,且可以方便融合部分语法信息。

Topic-based N-gram Model

该方法将训练集按主题划分成多个子集,并对每个子集分别建立N-gram语言模型,以解决语言模型的主题自适应问题。架构如下:

图片

Cache-based N-gram Model

该方法利用cache缓存前一时刻的信息,以用于计算当前时刻概率,以解决语言模型动态自适应问题。

  • People tends to use words as few as possible in the article.
  • If a word has been used, it would possibly be used again in the future.

架构如下:

图片

猜测这是目前QQ、搜狗、谷歌等智能拼音输入法所采用策略,即针对用户个性化输入日志建立基于cache的语言模型,用于对通用语言模型输出结果的调权,实现输入法的个性化、智能化。由于动态自适应模块的引入,产品越用越智能,越用越好用,越用越上瘾。

Skipping N-gram Model&Trigger-based N-gram Model

二者核心思想都是刻画远距离约束关系。

指数语言模型:最大熵模型MaxEnt、最大熵马尔科夫模型MEMM、条件随机域模型CRF

传统的n-gram语言模型,只是考虑了词形方面的特征,而没有词性以及语义层面上的知识,并且数据稀疏问题严重,经典的平滑技术也都是从统计学角度解决,未考虑语法、语义等语言学作用。

MaxEnt、MEMM、CRF可以更好的融入多种知识源,刻画语言序列特点,较好的用于解决序列标注问题。

参考资料

  1. 深入浅出讲解语言模型 https://zhuanlan.zhihu.com/p/28080127
  2. 斯坦福大学自然语言处理第四课“语言模型(Language Modeling)” http://52opencourse.com/111/%E6%96%AF%E5%9D%A6%E7%A6%8F%E5%A4%A7%E5%AD%A6%E8%87%AA%E7%84%B6%E8%AF%AD%E8%A8%80%E5%A4%84%E7%90%86%E7%AC%AC%E5%9B%9B%E8%AF%BE-%E8%AF%AD%E8%A8%80%E6%A8%A1%E5%9E%8B%EF%BC%88language-modeling%EF%BC%89
  3. http://faculty.cs.byu.edu/~ringger/CS479/papers/Gale-SimpleGoodTuring.pdf
  4. NLP Lunch Tutorial: Smoothing https://nlp.stanford.edu/~wcmac/papers/20050421-smoothing-tutorial.pdf
  5. NLP 笔记 – 平滑方法(Smoothing)小结 http://www.shuang0420.com/2017/03/24/NLP%20%E7%AC%94%E8%AE%B0%20-%20%E5%B9%B3%E6%BB%91%E6%96%B9%E6%B3%95(Smoothing)%E5%B0%8F%E7%BB%93/

版权声明:本文为weikai_w原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。