从此文起,我将重心转移到对机器音乐的探索。Github项目jazzml能基于机器学习算法自动生成音乐,作者最初使用的生成模型即为N-Grams。本文是我关于Speech and Language Processing第4章N-Grams 的阅读笔记。

1.问题引入

        我们首先从一个有趣的问题开始:下面句子中接下来的词会是什么?

                Please turn your homework ...

        我们直觉的判断可能会是over,但绝不可能是the或者run。接下来我们会把这种直观上的感觉转化成概率模型。这个模型将能使:

                all of a sudden I notice three guys standing on the sidewalk

        与

                on guys all I of notice sidewalk three a sudden standing the

        相比较而言,前者的整体概率更高。更直白一些的说法是:句子中语序正确程度与其整体概率成正比。

        我们能用这个模型做什么呢?首先,如果能准确预测接下来的词(word)是什么,现有的手机输入法提示性能将大大改善。对全文概率的预测,还可以辅助机器翻译(machine translation)中对语序进行调整,也能用于拼写纠错(spelling correction)和手写识别(handwriting recognition)。

2.N-Grams

        N-Grams是一个包含N个连续词的序列。特别地,我们将仅包含1个词的序列称为unigram,包含2个词的为bigram, 包含3个称为trigram。以语句Please turn your homework为例,其unigram、bigram、trigram分别为:

1
2
3
unigram:Please | turn | your | homework
bigram: Please turn | turn your | your homework
trigram:Please turn your | turn your homework

        我们回忆上文回答问题时用到的词——直觉。是的,直觉告诉我们turn your homework overturn your homework the可能性更大,这源于我们在日常会话和文字阅读过程中积累的经验。现在我们试图将这种经验使用概率模型表达:给定历史词序列$h$,计算下一个词是$w$的概率。例如: $$P(the | its water is  so  transparent  that)$$

        最简单的做法是收集一个巨大的数据集,统计词the出现在语句its water is so transparent that之后的次数: $P(the | its water is  so  transparent  that) = \frac{P(its water is  so  transparent  that the)}{P(its water is  so  transparent  that)}$

        但实际上,即使数据量大到包含整个万维网,也不够给出令我们满意的结果。究其原因,是语言本身富于创造性导致对任何一条句子的微小扩展,都可能在网页上找不到完全相同的句子。例如:Walden Pond's water is so transparent that the在网页上就找不到这一句。另外,每当我们想评估一条新的语句,例如$P(transparent |water is  so  transparent)$,就得重新统计,这无疑增加了工作量。

2.1 N-Grams模型

        我们首先给出计算词序列的联合概率公式:历史词序列$h$包含{$w_1, ..., w_n$}共$n$个词,用$w_i^j$表示第$i$到第$j$个词,则该词序列的联合概率: $$P(w_1^n)=P(w_1)P(w_2|w_1)P(w_3|w_1^2)...P(w_n|w_1^{n-1})$$

$$=\prod_{k=1}^nP(X_k|X_1^{k-1})$$

        上式的假设条件是:当前词$w_i$的概率仅与它之前的词{$w_1, ..., w_{n-1}$}有关。那么我们如何计算$P(w_k|w_1^{k-1})$呢?如上文所说,此项计算依赖海量数据,并需要进行大量统计。

        N-Grams模型的灵感源自:与其计算某个词$w_i$在给定$history$出现的概率,我们不妨仅以该词最邻近的N个词{$w_{i-N+1}, ... w_{i-1}$}近似代替整个$history$,让我们以最简单的bigram举例。

bigram

        在bigram中我们仅计算词$w_i$对其前1个词$w_{i-1}$的条件概率,因此对$P(w_k|w_1^{k-1})$的计算变为$P(w_k|w_{k-1})$。即与其计算: $$P(the | its water is  so  transparent  that)$$

现在我们只需要计算: $$P(the |that)$$

        因此当我们在使用bigram时,其实我们是在做如下近似: $$P(w_n|w_1^{n-1}) \approx P(w_n|w_{n-1})$$

        这种“假设当前词的概率仅取决于前1个词”的假设称之为马尔科夫假设。因此对bigram的联合概率计算公式化简为: $$P(w_1^n)=P(w_1)P(w_2|w_1)P(w_3|w_1^2)...P(w_n|w_1^{n-1})$$ $$=\prod_{k=1}^nP(w_k|w_1^{k-1})$$ $$\approx \prod_{k=1}^{n}P(w_k|w_{k-1})$$

        对于$P(w_n|w_{n-1})$的计算我们引入极大似然估计。假设我们给定前置词$w_{i-1}$,要预测接下来单词$w_i$的概率。可以首先统计整个文档中$w_{i-1}w_i$组成的"二元序列"共同出现的次数$C(w_{i-1}w_i)$,再统计以$w_{i-1}$开头的全部"二元序列"的个数。则有: $$P(w_n|w_{n-1})=\frac{C(w_{n-1}w_n)}{\sum_wC(w_{n-1}w)}$$

        事实上,分母中以$w_{i-1}$开头的全部"二元序列"的个数等价于$w_{i-1}$出现的次数。因此上式简化为: $$P(w_n|w_{n-1})=\frac{C(w_{n-1}w_n)}{C(w_{n-1})}$$

Example

现有如下一段文字:

1
2
3
<s> I am Sam </s>
<s> Sam I am </s>
<s> I do </s>

        我们以<s>作为序列开始的标志,</s>则作为结尾标志,它们也被当做文本中的一部分,现统计bigram如下:

$$\small P(I|<s>)=\frac{2}{3} \approx 0.67 \qquad P(I|Sam)=\frac{1}{2} = 0.5 \qquad P(am|I)=\frac{2}{3} \approx 0.67$$ $$\small P(Sam|<s>)=\frac{1}{3} \approx 0.33 \qquad P(do|I)=\frac{1}{3} \approx 0.33 \qquad P(</s>|am)=\frac{1}{2} = 0.5$$         此外我们还需要统计各个word出现的概率,以Sam为例,上文中Sam共出现了2次,不去重后总词数为14,因此: $$\small P(Sam)=\frac{2}{14} \approx 0.14$$

由此我们可以计算出bigram下序列Sam I am的概率: $$\small P(Sam \quad I \quad am) = P(Sam)P(I|Sam)P(am|Sam \quad I)$$ $$\small = P(Sam)P(I|Sam)P(am|I) \qquad (bigram假设)$$ $$\small = 0.14 \ast 0.5 \ast 0.67$$ $$\small = 0.0469$$ 现在我们可以对任意一段序列计算其bigram下的概率了。

推广到N-grams

bigram同理,广义上的N-grams是假设$history$仅与待预测的word前N个词相关: $$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的任意序列的概率。到此我们解决了上文中如何衡量序列A比序列B出现的概率高的问题。接下来我们将讨论如何预测下一个word。

3 模型预测和评估

3.1 模型预测

        我们给出对已知序列下一个词的预测算法:

  • 1.基于文本$t$,我们事先为其生成N-grams和(N-1)-grams。
  • 2.给定值为{$w_1, w_2, ..., w_{n-1}$}的待预测序列$s$,目标是预测接下来的词$w_n$。我们仅取其近$N-1$个word,统计(N-1)-grams中序列$w_{n-N+1}^{n-1}$的频数$C_{w_{n-1}}$,并将N-grams中所有以$w_{n-N+1}^{n-1}$起始的序列中结尾词$w_n$加入候选集。
  • 3.根据N-grams公式分别计算候选集中每一个word的条件概率$P(w_n|w_{n-N+1}^{n-1})$,从概率靠前的$topN$中随机挑选一个作为新word。
  • 4.重复2-3步。

        N-Grams-novel是我关于此算法的粗糙实现,它能够根据特定的训练文本和待预测序列,构建基于N-grams的"自动小说生成器",效果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/** 英文 */
语料:Game of Thrones 01 , 使用trigrams:
待预测序列:
There was an edge to this
50词的生成结果:
There was an edge to this . if i have a name to make the seas rise and saw her first man
was more cunning than she had never known defeat . " i am a sworn sword , and a third of those creatures ,
whatever it takes . i have a name ? oh
/** 中文 */
语料:《斗破苍穹》 , 使用trigrams:
待预测序列:
不愧是家族中种子级别的人物
200词的生成结果:
不愧是家族中种子级别的人物,她似乎便是从未见过萧炎白白吃亏过,即便如今已经晋入五星斗皇,
那是一种凌驾这片天地之上的气息巨蟒逐渐消散,最后一卷被能量层所包裹的人影,萧炎也只得停下介绍,
对着身旁那身姿欣长,脸色淡漠地举步走出,平静的声音,缓缓传出,青色斗气急速凝聚成火球之状,
然后火球裂开一道缝隙,一颗足有半个拳头大小。
在萧炎等人,也是逐渐地出现一丝晨辉时,萧炎却是一笑,道:“我知道你的一些事,只不过令得他感到意外,
微微点了点头:“好了…”
在萧炎等人为逃出一劫而松气时,那紧闭的眼眸,猛然睁开!
在那众多惊骇目光中缓缓松开了手掌,切记,以你如今在加玛帝国,也顶多只能伤到二阶魔兽,想要击杀,
却是必须跟老夫老老实实的交代,也是逐渐地变得黯淡

3.2 预测效果评估

        可以看到,N-grams的预测风格完全取决于语料数据,因此我们要使用与预期结果文风相近的训练集。例如生成法律文档,就应该以法律文件作为训练集。注意到使用trigrams的效果已经可以得到语言相对连贯的句子了,那bigrams4-grams效果会不会更好呢?我们需要一套指标衡量N取值为多少时预测效果更佳。

        对一个语言模型最好的评估方式是将其嵌入一款应用,然后看它提升了多少。这种端对端的评估称之为extrinsic evaluation,它是检验提升的唯一方法。基于此思想,我们的做法是:增加测试集。首先从训练集得到模型,然后评估它在测试集中的表现。评估准则是看哪一个模型对测试集词序列分配更高的概率——这表明它对预试集的预测更准确。例如测试集序列为:

                                                              go back home

按我们之前对序列的计算公式,词序列bigrams概率为: $$P_{bigram}(go back home)=P(go)P(back|go)P(home|back)$$ trigrams概率: $$P_{trigram}(go back home)=P(go)P(back|go)P(home|go back)$$

很显然$P_{bigram} \ge P_{trigram}$,因此原来的计算方法评估并不合理。我们引入一种新的评估指标——Perplexity(混乱度)。

        Perplexity:一个测试样例的混乱度即为该测试样例的概率倒数,再对词数N做归一化。 $$PP(W)=P(w_1w_2...w_n)^{\frac{-1}{N}}$$ $$=\sqrt[N] {\frac{1}{P(w_1w_2...w_n)}}$$ $$=\sqrt[N] {\frac{1}{\prod_{k=1}^nP(X_k|X_1^{k-1})}}$$

        注意到条件概率乘积越高的序列,其perplexity越低。因此最小化PP等价于最大化测试集的概率。 我们从另一个角度考虑混乱度:即将其视为语言的带权分歧因子(weighted average branching factor)分歧因子是指一个词后可能能跟的词的总个数。例如:在数字预测中,假设0-9这10个数字以概率1/10等可能地出现,那么 $$PP(W)=P(w_1w_2...w_n)^{\frac{-1}{N}}$$ $$={(\frac{1}{10})}^{N{(\frac{-1}{N})}}$$ $$={(\frac{1}{10})}^{-1}$$ $$=10$$         但假如0在本文中出现比较频繁,可以证明PP将会降低,在这一点上PP和熵的特性很相似。

4. 一些具体问题

        我们已经介绍了如何计算序列的概率、如何生成新序列,以及模型好坏的评估手段,但实际应用中往往存在诸多问题。主要问题如下:

  • 注意到计算中我们的概率是乘积形式,如果这条"链"存在值为0怎么办?例如在计算$\small P(Sam \quad I \quad am)$中,若$\small P(am|I)$为0则整个句子概率为0,此特性在N取更大值时愈发明显,例如5-grams概率计算$\small P(home|Sam \quad and \quad I \quad went)$
  • 如何处理测试集中的Unknown Words(生词)?

4.1 平滑处理

解决上述乘积出现0的问题,方法是对数据做平滑处理。例如原本对bigram的计算: $$P(w_n|w_{n-1})=\frac{C(w_{n-1}w_n)}{C(w_{n-1})}$$ 使用Laplace平滑: $$P_{Laplace}((w_n|w_{n-1})=\frac{C(w_{n-1}w_n)+1}{C(w_{n-1})+V}$$ 其中V是去重后的总单词数。此项操作能使乘积"链"中不出现0。

        还有一种方法:倒退(Backoff)。例如要计算trigram条件概率$P(w_n|w_{n-2}w_{n-1})$,但我们并无$w_{n-2}w_{n-1}w_{n}$的词序列,这时候可以倒退回bigram并使用$P(w_n|w_{n-1})$,同理如果要计算bigram,但没有$P(w_n|w_{n-1})$,可以考虑计算$P(w_n)$,换句话说——在概率为0时只不断"回退",直到概率不为0,但需要回退的概率计算结果做一定折扣。

        另一种是插值(Interpolation):假如我们现在使用trigram,则每次预测(无论是否存在该trigram序列)均使用插值: $$\hat{P}(w_n|w_{n-2}w_{n-1})=\lambda_1 P(w_n|w_{n-2}w_{n-1} )+ \lambda_2 P(w_n|w_{n-1}) + \lambda_3 P(w_n)$$ 其中$\small \lambda$由新增一个训练集学习得出,并需要满足: $$\sum_i \lambda_i = 1$$

4.2 处理Unknown Words

        最后我们简要谈谈Unknown Words,如果测试集中出现了训练集中没见过的词,我们就称之为的Unknown Words,这类词在训练集中概率为0,且前后N-gram词序列概率也为0。一个简单的处理办法是:对每个出现的Unknown Word替换为<UNK>,计算时以<UNK>的频率代替包含<UNK>序列的概率,更完善的解决方案可参考NLP Lunch Tutorial: Smoothing

5.文献及引用

林戈 | myfancoo@gmail.com