统计语言模型

统计语言模型浅谈从属于笔者的程序猿的数据科学与机器学习实战手册,其他相关阅读Python 语法速览与机器学习开发环境搭建Scikit-Learn 备忘录基于 Gensim 的 Word2Vec 实践

统计语言模型

统计语言模型(Statistical Language Model)即是用来描述词、语句乃至于整个文档这些不同的语法单元的概率分布的模型,能够用于衡量某句话或者词序列是否符合所处语言环境下人们日常的行文说话方式。统计语言模型对于复杂的大规模自然语言处理应用有着非常重要的价值,它能够有助于提取出自然语言中的内在规律从而提高语音识别、机器翻译、文档分类、光学字符识别等自然语言应用的表现。好的统计语言模型需要依赖大量的训练数据,在上世纪七八十年代,基本上模型的表现优劣往往会取决于该领域数据的丰富程度。IBM 曾进行过一次信息检索评测,发现二元语法模型(Bi-gram)需要数以亿计的词汇才能达到最优表现,而三元语法模型(TriGram)则需要数十亿级别的词汇才能达成饱和。本世纪初,最流行的统计语言模型当属 N-gram,其属于典型的基于稀疏表示(Sparse Representation)的语言模型;近年来随着深度学习的爆发与崛起,以词向量(WordEmbedding)为代表的分布式表示(Distributed Representation)的语言模型取得了更好的效果,并且深刻地影响了自然语言处理领域的其他模型与应用的变革。除此之外,Ronald Rosenfeld[7] 还提到了基于决策树的语言模型(Decision Tree Models)、最大熵模型以及自适应语言模型(Adaptive Models)等。 统计语言模型可以用来表述词汇序列的统计特性,譬如学习序列中单词的联合分布概率函数。如果我们用$w_1$ 到 $w_t$ 依次表示这句话中的各个词,那么该句式的出现概率可以简单表示为:

统计语言模型训练目标也可以是采用极大似然估计来求取最大化的对数似然,公式为$\frac{1}{T}\sum^T{t=1}\sum{-c \le j\le c,j \ne0}log p(w{t+j}|w_t)$。其中$c$是训练上下文的大小。譬如$c$取值为 5 的情况下,一次就拿 5 个连续的词语进行训练。一般来说$c$越大,效果越好,但是花费的时间也会越多。$p(w{t+j}|wt)$表示$w_t$条件下出现$w{t+j}$的概率。常见的对于某个语言模型度量的标准即是其困惑度(Perplexity),需要注意的是这里的困惑度与信息论中的困惑度并不是相同的含义。这里的困惑度定义公式参考 Stolcke[11],为$exp(-logP(w_t)/|\vec{w}|)$,即是$1/P(w_t|w_1^{t-1})$的几何平均数。最小化困惑度的值即是最大化每个单词的概率,不过困惑度的值严重依赖于词表以及具体使用的单词,因此其常常被用作评判其他因素相同的两个系统而不是通用的绝对性的度量参考。

N-gram 语言模型

参照上文的描述,在统计学语言模型中我们致力于计算某个词序列$E = w_1^T$的出现概率,可以形式化表示为:

上式中我们求取概率的目标词序列$E$的长度为$T$,序列中第一个词为$w_1$,第二个词为$w_2$,等等,直到最后一个词为$w_T$。上式非常直观易懂,不过在真实环境下却是不可行的,因为序列的长度$T$是未知的,并且词表中词的组合方式也是非常庞大的数目,无法直接求得。为了寻找实际可行的简化模型,我们可以将整个词序列的联合概率复写为单个词或者单个词对的概率连乘。即上述公式可以复写为$P(w_1,w_2,w_3)=P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)$,推导到通用词序列,我们可以得到如下形式化表示:

此时我们已经将整个词序列的联合概率分解为近似地求 $P(wt | w_1, w_2, …, w{t-1})$。而这里要讨论的 N-gram 模型就是用 $P(wt | w{t-n+1}, …, w_{t-1})$ 近似表示前者。根据$N$的取值不同我们又可以分为一元语言模型(Uni-gram)、二元语言模型(Bi-gram)、三元语言模型(Tri-gram)等等类推。该模型在中文中被称为汉语语言模型(CLM, Chinese Language Model),即在需要把代表字母或笔画的数字,或连续无空格的拼音、笔画,转换成汉字串(即句子)时,利用上下文中相邻词间的搭配信息,计算出最大概率的句子;而不需要用户手动选择,避开了许多汉字对应一个相同的拼音(或笔画串、数字串)的重码问题。 一元语言模型又称为上下文无关语言模型,是一种简单易实现但实际应用价值有限的统计语言模型。该模型不考虑该词所对应的上下文环境,仅考虑当前词本身的概率,即是 N-gram 模型中当$N=1$的特殊情形。

N-gram 语言模型也存在一些问题,这种模型无法建模出词之间的相似度,有时候两个具有某种相似性的词,如果一个词经常出现在某段词之后,那么也许另一个词出现在这段词后面的概率也比较大。比如“白色的汽车”经常出现,那完全可以认为“白色的轿车”也可能经常出现。N-gram 语言模型无法建模更远的关系,语料的不足使得无法训练更高阶的语言模型。大部分研究或工作都是使用 Tri-gram,就算使用高阶的模型,其统计 到的概率可信度就大打折扣,还有一些比较小的问题采用 Bi-gram。训练语料里面有些 n 元组没有出现过,其对应的条件概率就是 0,导致计算一整句话的概率为 0。最简单的计算词出现概率的方法就是在准备好的训练集中计算固定长度的词序列的出现次数,然后除以其所在上下文的次数;譬如以 Bi-gram 为例,我们有下面三条训练数据:

  • i am from jiangsu.

  • i study at nanjing university.

  • my mother is from yancheng.

我们可以推导出词 am, study 分别相对于 i 的后验概率:

上述的计算过程可以推导为如下的泛化公式:

这里$c_{prefix}(\cdot)$表示指定字符串在训练集中出现的次数,这种方法也就是所谓的最大似然估计(Maximum Likelihood Estimation);该方法十分简单易用,同时还能保证较好地利用训练集中的统计特性。根据这个方法我们同样可以得出 Tri-gram 模型似然计算公式如下:

我们将 N-gram 模型中的参数记作$\theta$,其包含了给定前$n-1$个词时第$n$个词出现的概率,形式化表示为:

朴素的 N-gram 模型中对于训练集中尚未出现过的词序列会默认其概率为零 ,因为我们的模型是多个词概率的连乘,最终会导致整个句式的概率为零。我们可以通过所谓的平滑技巧来解决这个问题,即组合对于不同的$N$取值来计算平均概率。譬如我们可以组合 Uni-gram 模型与 Bi-gram 模型:

其中$\alpha$表示分配给 Uni-gram 求得的概率的比重,如果我们设置了$\alpha > 0$,那么词表中的任何词都会被赋予一定的概率。这种方法即是所谓的插入平滑(Interpolation),被应用在了很多低频稀疏的模型中以保证其鲁棒性。当然,我们也可以引入更多的$N$的不同的取值,整个组合概率递归定义如下:

[Stanley et al., 1996] 中还介绍了很多其他复杂但精致的平滑方法,譬如基于上下文的平滑因子计算(Context-dependent Smoothing Coefficients),其并没有设置固定的$\alpha$值,而是动态地设置为$\alpha{w{t-m+1}^{t-1}}$。这就保证了模型能够在有较多的训练样例时将更多的比重分配给高阶的 N-gram 模型,而在训练样例较少时将更多的比重分配给低阶的 N-gram 模型。目前公认的使用最为广泛也最有效的平滑方式也是 [Stanley et al., 1996] 中提出的 Modified Kneser-Ney smoothing( MKN ) 模型,其综合使用了上下文平滑因子计算、打折以及低阶分布修正等手段来保证较准确地概率估计。

神经网络语言模型

顾名思义,神经网络语言模型(Neural Network Language Model)即是基于神经网络的语言模型,其能够利用神经网络在非线性拟合方面的能力推导出词汇或者文本的分布式表示。在神经网络语言模型中某个单词的分布式表示会被看做激活神经元的向量空间,其区别于所谓的局部表示,即每次仅有一个神经元被激活。标准的神经网络语言模型架构如下图所示:

神经网络语言模型中最著名的当属 Bengio[10] 中提出的概率前馈神经网络语言模型(Probabilistic Feedforward Neural Network Language Model),它包含了输入(Input)、投影(Projection)、隐藏(Hidden)以及输出(Output)这四层。在输入层中,会从$V$个单词中挑选出$N$个单词以下标进行编码,其中$V$是整个词表的大小。然后输入层会通过$N \times D$这个共享的投影矩阵投射到投影层$P$;由于同一时刻仅有$N$个输入值处于激活状态,因此这个计算压力还不是很大。NNLM 模型真正的计算压力在于投影层与隐层之间的转换,譬如我们选定$N = 10$,那么投影层$P$的维度在 500 到 2000 之间,而隐层$H$的维度在于$500$到$1000$之间。同时,隐层$H$还负责计算词表中所有单词的概率分布,因此输出层的维度也是$V$。综上所述,整个模型的训练复杂度为:

Q=N×D+N×D×H+H×VQ = N \times D + N \times D \times H + H \times V

其训练集为某个巨大但固定的词汇集合$V$ 中的单词序列$w1...w_t$;其目标函数为学习到一个好的模型$f(w_t,w{t-1},\dots,w{t-n+2},w{t-n+1})=p(wt|w_1^{t-1})$,约束为$f(w_t,w{t-1},\dots,w{t-n+2},w{t-n+1}) > 0$并且$\Sigma{i=1}^{|V|} f(i,w{t-1},\dots,w{t-n+2},w{t-n+1}) = 1$。每个输入词都被映射为一个向量,该映射用$C$表示,所以$C(w{t-1})$即为$w{t-1}$的词向量。定义$g$为一个前馈或者递归神经网络,其输出是一个向量,向量中的第$i$个元素表示概率$p(w_t=i|w_1^{t-1})$。训练的目标依然是最大似然加正则项,即:

MaxLikelihood=max1Ttlogf(wt,wt1,,wtn+2,wtn+1;θ)+R(θ)Max Likelihood = max \frac{1}{T}\sum_tlogf(w_t,w_{t-1},\dots,w_{t-n+2},w_{t-n+1};\theta) + R(\theta)

其中$\theta$为参数,$R(\theta)$为正则项,输出层采用 sofamax 函数:

p(wtwt1,,wtn+2,wtn+1)=eywtieyip(w_t|w_{t-1},\dots,w_{t-n+2},w_{t-n+1})=\frac{e^{y_{w_t}}}{\sum_ie^{y_i}}

其中$yi$是每个输出词$i$的未归一化$log$概率,计算公式为$y=b+Wx+Utanh(d+Hx)$。其中$b,W,U,d,H$都是参数,$x$为输入,需要注意的是,一般的神经网络输入是不需要优化,而在这里,$x=(C(w{t-1}),C(w{t-2}),\dots,C(w{t-n+1}))$,也是需要优化的参数。在图中,如果下层原始输入$x$不直接连到输出的话,可以令$b=0$,$W=0$。如果采用随机梯度算法的话,梯度的更新规则为:

θ+ϵlogp(wtwt1,,wtn+2,wtn+1)θθ\theta + \epsilon \frac{\partial log p(w_t | w_{t-1},\dots,w_{t-n+2},w_{t-n+1})}{\partial \theta} \to \theta

其中$\epsilon$为学习速率,需要注意的是,一般神经网络的输入层只是一个输入值,而在这里,输入层$x$也是参数(存在$C$中),也是需要优化的。优化结束之后,词向量有了,语言模型也有了。这个 Softmax 模型使得概率取值为(0,1),因此不会出现概率为 0 的情况,也就是自带平滑,无需传统 N-gram 模型中那些复杂的平滑算法。Bengio 在 APNews 数据集上做的对比实验也表明他的模型效果比精心设计平滑算法的普通 N-gram 算法要好 10%到 20%。

循环神经网络语言模型

好的语言模型应当至少捕获自然语言的两个特征:语法特性与语义特性。为了保证语法的正确性,我们往往只需要考虑生成词的前置上下文;这也就意味着语法特性往往是属于局部特性。而语义的一致性则复杂了许多,我们需要考虑大量的乃至于整个文档语料集的上下文信息来获取正确的全局语义。神经网络语言模型相较于经典的 N-gram 模型具有更强大的表现力与更好的泛化能力,不过传统的 N-gram 语言模型与 [Bengio et al., 2003] 中提出的神经网络语言模型都不能有效地捕获全局语义信息。为了解决这个问题,[Mikolov et al., 2010; 2011] 中提出的基于循环神经网络(Recurrent Neural Network, RNN)的语言模型使用了隐状态来记录词序的历史信息,其能够捕获语言中的长程依赖。在自然语言中,往往在句式中相隔较远的两个词却具备一定的语法与语义关联,譬如He doesn't have very much confidence in himselfShe doesn't have very much confidence in herself 这两句话中的<He, himself><She, herself>这两个词对,尽管句子中间的词可能会发生变化,但是这两种词对中两个词之间的关联却是固定的。这种依赖也不仅仅出现在英语中,在汉语、俄罗斯语中也都存在有大量此类型的词对组合。而另一种长期依赖(Long-term Dependencies)的典型就是所谓的选择限制(Selectional Preferences);简而言之,选择限制主要基于已知的某人会去做某事这样的信息。譬如我要用叉子吃沙拉我要和我的朋友一起吃沙拉这两句话中,叉子指代的是某种工具,而我的朋友则是伴侣的意思。如果有人说我要用双肩背包来吃沙拉就觉得很奇怪了,双肩背包并不是工具也不是伴侣;如果我们破坏了这种选择限制就会生成大量的无意义句子。最后,某个句式或者文档往往都会归属于某个主题下,如果我们在某个技术主题的文档中突然发现了某个关于体育的句子,肯定会觉得很奇怪,这也就是所谓的破坏了主题一致性。

[Eriguchi et al., 2016] 中介绍的循环神经网络在机器翻译上的应用就很值得借鉴,它能够有效地处理这种所谓长期依赖的问题。它的思想精髓在于计算新的隐状态$\vec{h}$时引入某个之前的隐状态$\vec{h_{t-1}}$,形式化表述如下:

我们可以看出,在$t \geq 1$时其与标准神经网络中隐层计算公式的区别在于多了一个连接$W{hh}\vec{h}{t-1}$,该连接源于前一个时间点的隐状态。在对于 RNN 有了基本的了解之后,我们就可以将其直接引入语言模型的构建中,即对于上文讨论的神经网络语言模型添加新的循环连接:

注意,与上文介绍的前馈神经网络语言模型相对,循环神经网络语言模型中只是将前一个词而不是前两个词作为输入;这是因为我们假设$w{t-2}$的信息已经包含在了隐状态$\vec{h{t-1}}$中,因此不需要重复代入。

平滑法

方法一为平滑法。最简单的方法是把每个 n 元组的出现次数加 1,那么原来出现 k 次的某个 n 元组就会记为 k+1 次,原来出现 0 次的 n 元组就会记为出现 1 次。这种也称为 Laplace 平滑。当然还有很多更复杂的其他平滑方法,其本质都 是将模型变为贝叶斯模型,通过引入先验分布打破似然一统天下的局面。而引入 先验方法的不同也就产生了很多不同的平滑方法。

回退法

方法二是回退法。有点像决策树中的后剪枝方法,即如果 n 元的概率不到, 那就往上回退一步,用 n-1 元的概率乘上一个权重来模拟。

N-Pos 模型(Context = $c(w{t-n+1}),c(w{t-n+2}),\dots,c(w_{t-1})$)

严格来说 N-Pos 只是 N-Gram 的一种衍生模型。N-Gram 模型假定第 t 个词出现概率条件依赖它前 N-1 个词,而现实中很多词出现的概率是条件依赖于它前面词的语法功能的。N-Pos 模型就是基于这种假设的模型,它将词按照其语法功能进行分类,由这些词类决定下一个词出现的概率。这样的词类称为词性 (Part-of-Speech,简称为 POS)。N-Pos 模型中的每个词的条件概率表示为:

$p(s)=p(w^T1)=p(w_1,w_2,\dots,w_T)= \ \Pi^T{t=1}p(wt|c(w{t-n+1}),c(w{t-n+2}),\dots,c(w{t-1}))$

$c$为类别映射函数,即把$T$个词映射到$K$个类别($1 \le K \le T$),实际上 N-Pos 使用了一种聚类的思想,使得 N-Gram 中$w{t-n+1},w{t-n+2},\dots,w{t-1}$中的可能为$T^{n-1}$减少为$c(w{t-n+1}),c(w{t-n+2}),\dots,c(w{t-1})$中的$K^{N-1}$,同时这种减少还采用了语义有意义的类别。

基于决策树的语言模型

上面提到的上下文无关语言模型、n-gram 语言模型、n-pos 语言模型等等,都可以以统计决策树的形式表示出来。而统计决策树中每个结点的决策规则是一 个上下文相关的问题。这些问题可以是“前一个词时 w 吗? ”“前一个词属于类别 C,吗?”。当然基于决策树的语言模型还可以更灵活一些,可以是一些“前一个词是动词?”,“后面有介词吗?”之类的复杂语法语义问题。基于决策树的语言模型优点是:分布数不是预先固定好的,而是根据训练预 料库中的实际情况确定,更为灵活。缺点是:构造统计决策树的问题很困难,且时空开销很大。

最大熵模型

最大熵原理是 E.T. Jayness 于上世纪 50 年代提出的,其基本思想是:对一个 随机事件的概率分布进行预测时,在满足全部已知的条件下对未知的情况不做任何主观假设。从信息论的角度来说就是:在只掌握关于未知分布的部分知识时,应当选取符合这些知识但又能使得熵最大的概率分布。

$p(w|Context)=\frac{e^{\Sigma_i \lambda_i f_i(context,w)}}{Z(Context)}$

自适应语言模型

前面的模型概率分布都是预先从训练语料库中估算好的,属于静态语言模型。 而自适应语言模型类似是 Online Learning 的过程,即根据少量新数据动态调整模型,属于动态模型。在自然语言中,经常出现这样现象:某些在文本中通常很少出现的词,在某一局部文本中突然大量地出现。能够根据词在局部文本中出现的 情况动态地调整语言模型中的概率分布数据的语言模型成为动态、自适应或者基于缓存的语言模型。通常的做法是将静态模型与动态模型通过参数融合到一起, 这种混合模型可以有效地避免数据稀疏的问题。还有一种主题相关的自适应语言模型,直观的例子为:专门针对体育相关内 容训练一个语言模型,同时保留所有语料训练的整体语言模型,当新来的数据属 于体育类别时,其应该使用的模型就是体育相关主题模型和整体语言模型相融合 的混合模型。

Skip-Gram

A CloserLook at Skip-gram Modelling

根据论文中的定义可知道,常说的k-skip-n-grams在句子$w_1 \dots w_m$可以表示为:

${ w{i_1},w{i2}, \dots w{in} | \sum{j=1}^{n}ij - i{j-1} < k }$

Skip-gram 實際上的定義很簡單,就是允许跳几个字的意思… 依照原論文裡的定義,這個句子:

Insurgents killed in ongoing fighting.

在 bi-grams 的時候是拆成:{ `insurgents killed, killed in, in ongoing, ongoing fighting` }。
在 2-skip-bi-grams 的時候拆成:{ `insurgents killed, insurgents in, insurgents ongoing, killed in, killed ongoing, killed fighting, in ongoing, in fighting, ongoing fighting` }。
在 tri-grams 的時候是:{ `insurgents killed in, killed in ongoing, in ongoing fighting` }。
在 2-skip-tri-grams 的時候是:{ `insurgents killed in, insurgents killed ongoing, insurgents killed fighting, insurgentsin ongoing, insurgents in fighting, insurgents ongoing fighting, killed in ongoing, killed in fighting, killed ongoing fighting, in ongoing fighting` }。

对于上文的语言模型的目标公式而言,Skip-Gram 模型中的$p(w_{t+j} | w_t)$公式采用的是 Softmax 函数:

$p(wo | w_I) = \frac{exp(v'^T{wo}v{wI})}{\sum^W{w=1}exp(v'^Twv{w_I})}$

其中$p(wo | w_I)$表示在词语$w_I$条件下出现$w_o$的概率,$v{w_o}$表示$w_o$代表的词向量,而$v_w$代表词汇表中所有词语的向量。$W$是词汇表的长度。不过该公式不太切实际,因为$W$太大了,通常是$10^5–10^7$。

Hierarchical Softmax

这种是原始 skip-gram 模型的变形。我们假设有这么一棵二叉树,每个叶子节点对应词汇表的词语,一一对应。所以我们可以通过这棵树来找到一条路径来找到某个词语。比如我们可以对词汇表,根据词频,建立一棵 huffman 树。每个词语都会对应一个 huffman 编码,huffman 编码就反映了这个词语在 huffman 树的路径。对于每个节点,都会定义孩子节点概率,左节点跟右节点的概率不同的,具体跟输入有关。譬如,待训练的词组中存在一句:“我爱中国”。

输入:爱

预测:我

假设,“我”的 Huffman 编码是 1101,那么就在 Huffman 树上从根节点沿着往下走,每次走的时候,我们会根据当前节点和“爱”的向量算出(具体怎么算先不管),走到下一个节点的概率是多少。于是,我们得到一连串的概率,我们的目标就是使得这些概率的连乘值(联合概率)最大。

$p(w|wI)=\Pi{j=1}^{L(w)-1}\sigma([n(w,j+1)=ch(n(w,j))]*v'^T{n(w,j)}v{w_I})$

  • $L(w)$为词语$w$在二叉树路径中的长度

  • $\sigma(*)$即为 Sigmoid 函数

  • $n(w,j+1)$即指$w$在二叉树的第$j+1$个节点

  • $ch(n(w,j))$表示定义了任意一个固定的节点,要么是左,要么是右。合起来的意思是左右节点的正负号是不一致的,可以是左负右正,可以是左正右负。

而对于单一的选择左右节点的概率:

$\sigma(x)=\frac{1}{1+e^{-x}} \ \sigma(-x)=\frac{1}{1+e^{x}} \ \sigma(x) + \sigma(-x) = 1 $

显然,我们计算这个联合概率的复杂度取决了词语在 huffman 树的路径长度,显然她比 W 小得多了。另外,由于按词频建立的 huffman 树,词频高的,huffman 编码短,计算起来就比较快。词频高的需要计算概率的次数肯定多,而 huffman 让高频词计算概率的速度比低频词的快。这也是很犀利的一个设计。

NNLM

NNLM 是 Neural Network Language Model 的缩写,即神经网络语言模型。神经网络语言模型方面最值得阅读的文章是 Deep Learning 二号任人物 Bengio 的《A Neural Probabilistic Language Model》,JMLR 2003。NNLM 米用的是 Distributed Representation,即每个词被表示为一个浮点向量。其模型图如下:

目标是要学到一个好的模型:

$f(wt,w{t-1},\dots,w{t-n+2},w{t-n+1})=p(w_t|w_1^{t-1})$

需要满足的约束为:

上图中,