基于最大熵原理的语言建模

基于最大熵原理的语言建模

1 问题的引入

在自然语言处理中，为了建立语言模型，需要使用上下文文本中的信息特征，利用不同的信息特征所建立的语言模型，对当前词预测所得的概率结果可能会有所不同，这样的信息特征在上下文

1

中有多种。例如，利用当前词wi前面的连续n-1个词(wiin1h)作为历史信息特征构造的n-gram

1模型，其概率估计为P(Wi|Wiin1)；而触发对语言模型，则是利用当前词前面的某个历史窗口中的

词作为触发词，要预测的当前词作为被触发词，该模型中所用的历史信息特征和n-gram中的就不同，它可以是历史窗口中与当前词相距为d的某个词或词串。例如，如果我们想估计在给定的文本历史情况下词“模型”的出现概率P(模型｜h)，如果使用Bigram模型，则就会将事件空间（h,模型）根据h的最后一个词划分成几个等价类，比如说，在训练文本中可能有“数学模型”、“语言模型”、“工程模型”、“汽车模型”等这样的短语，因此，“模型”一词的历史文本h的最后一个词可能就是“数学”、“语言”、“工程”、“汽车”等，并将它们分别看作一个等价类，Bigram模型为每个等价类赋以相同的概率。例如：

PBigram(模型｜语言）＝K (1) ｛语言，模型｝

这里，K{语言,模型}定义如下：

K{语言,模型}

Count(语言,模型)

Count(语言)

(2)

Count(语言,模型)是“语言”与“模型”两个词在训练语料中的同现次数，Count(语言)是“语

言”在训练语料中出现的次数。另一种对“模型”出现概率的估计方法就是根据特殊的触发对，比如说“建立汉语语言模型”或“使用语言模型”，我们就要考察在相同的历史信息h中，是否有“建立”或“使用”这样的词，这样，又可以形成对事件空间（h,模型）的另一种划分，利用Trigger模型，可以为同一个等价类赋以相同的概率：

P建立模型(模型|建立h)K(建立

这里定义K(建立

h,模型）

h,模型）

(3)

为：

K

＝

C(建立h,模型)

C(建立h)

(4)

(建立h,模型）

显然，利用Bigram和Trigger模型所使用的信息特征估计得到的“模型”出现概率是不一样的，同理，用前面提到的其他信息特征所得到的概率也会不一样，能不能将它们协调一致，建立一个符合多个信息特征约束的统一模型框架呢？1992年，Della Pietra等人利用最大熵原理建立语言模型就是对这一想法的尝试。 2 最大熵原理 2.1 基本思想

最大熵原理是E.T.Jayness于1950年提出的，其基本思想是：假设｛X｝是一个事件空间，有许多种能够刻画该事件空间的信息源特征（或称约束），可以用来对事件的出现概率P(X)进行表述，假设每个约束i与一个约束函数fi(X)和一个数学期望Ki相联系，则该约束可以写为：

def

EP(fi)

P(X)f(X)K

i

X

i

(5)

对于多个相容的约束条件，式（5）的唯一的最大熵解保证存在，其形式为：

P(X)



i

fi(X)i

(6)

其中λi为待求的未知常量，称为模型参数，它将使P(X)满足所有的约束。

由式（6）可以看出，事件X的出现概率完全由模型参数λi和特征约束函数fi(X)所决定，特征约束函数fi(X)可以看作是对信源特征i的表示，因此，求取事件X概率P(X)必须要考虑参数λi的计算和特征i(或特征约束函数fi(X))的选择。特征选择是选择出对模型有表征意义的特征，以此建立一组约束；参数估计则在这些约束下，用最大熵原理对每一个特征进行估值，最终建立起事件空间X的概率模型。 2.2 模型参数估计

Danroch和Ratcliff于1972年提出了一个GIS（Generalized Iterative Scaling Algorithm）算法，对每一个特征fi，找出满足所有约束的i，下面是求取式(6)中i的迭代算法： 算法1 GIS算法

输入：特征集f={f1,f2,„,fn}

输出：最优参数值1,2,„,n，最佳模型p(x) 过程：

(1) 变量初始化：给i赋任一初值(i0)，i=1,2,„,n。 (2) 按照式（6）计算初始P(X)：P(0)(X)



i

(0)ii

f(X)

。

(3) 在当前估计函数下按式（5）计算每个fi的期望，

i{1,2,„n}，

EP(j)(fi)

P

X

(j)

(X)fi(X)

(4) 将实际计算得到的概率EP(j)(fi)与期望概率Ki进行比较，并按下列公式对i进行更新:

(j1)

i

(ij)

KiE

P(j)

(7)

fj

(5) 根据新的i值计算概率估计函数P(X)：

P(j1)(X)(j1)ifi(X) (8)

i

(6) 若条件P(X)-P(X)≤ε满足，则迭代收敛，输出1, 2, „, n和P(X)，否则，转(3)。 3 基于最大熵原理的自然语言建模 3.1 问题描述

设自然语言是一个随机过程，如果将Y看作当前词的所有可能取值的有限集合，y∈Y可能是随机过程产生的输出，X为其上下文信息x组成的集合，则当前输出y的取值受上下文信息X的影响。可以将(X,Y)看作是自然语言文本的一个事件空间。例如，在中文文本校对中，当对文本中的错误词进行修正时，如果当前词的易混淆集或纠错建议候选集为Y，选择其中的哪一个词y替换错误词完全受上下文x∈X的影响。上下文信息就是出错词周围的一些词。

构造随机模型的任务是要对语言的这一过程特性进行描述。模型的目标是估计在给定上下文信息x出现的情况下，过程输出为y的条件概率,即P(y|x)。

(j+1)(j)

3.2 特征与约束

1. 经验概率分布

语言建模的目标是构造能够对实际文本进行准确描述的统计模型，即它的概率分布与训练语料中的经验概率分布应该相符。对于中文文本纠错，假设事先由人工完成了许多纠错的样例，即(x,y)样本。经过对训练语料的统计，可以得到在特定的上下文中一个错误词应更换为哪个候选建议的频率，从而通过最大似然法，可得到训练语料中上下文信息与输出的经验概率分布p(x,y)：

~p(x,y)

Count(x,y)

Count(x,y)x,y

~

(9)

式中，Count(x,y)为(x,y)在训练语料中出现的次数。

2. 特征与约束

随机过程的输出受上下文信息的影响。如在文本纠错过程中，选用哪个候选建议对错误词进行修改，与其上下文有关。我们可以将这些上下文看作是对当前词具有表征作用的特征。例如，如果在文本中出现这样的句子，“他们所承担的任务非常艰匡”，“艰匡”是一个错误词，易混淆集中提供了“简况”、“艰巨”、“艰难”、“艰苦”，“艰辛”等多个候选建议，选择那一个呢？显然，它的选择与上下文密切相关，其上下文信息有：“非常”、“任务”等等，根据人的判断，“任务”对建议的选择非常重要，当然，我们还可以对文本中的每个词标上词性，词性也可以成为选取建议的特征。上下文X中的特征信息可能有很多，如何选取有用的特征信息，在下面再作论述。现先引入特征的定义：

定义1（特征） 设x∈X，其长度≥1，它是当前过程输出y(∈Y)的上下文信息，如果x对y具有表征作用，则称(x, y)为模型的一个特征。x长度为1时称为原子特征，否则称为复合特征。

可以引入一个定义于｛0，1｝域上的二值函数来表示特征：

1若(x,y)(X,Y), 且满足某种条件 (10) f(x,y)

0否则

建立语言模型时，信息特征的获取来自训练语料，语料中当前词的上下文中的所有词与当前词

一起都可以作为模型的信息特征，因此与模型有关的候选信源特征组成的集合很大，其中只有一些特征是对模型有用的特征，这些特征组成的集合只是候选特征集合的一个子集，它可以较完整地表达训练语料中数据。那么，如何判断哪些特征对语言模型有用呢？可以通过所建模型与经验概率分布模型的一致性来判定特征的重要性。

~如果有特征f，它在训练样本中关于经验概率分布p(x,y)的数学期望可表示如下：

~E~p(f)p(x,y)f(x,y) (11)

x,y

假设所建立的语言模型的概率分布为p(x,y)，则特征f关于所建模型p的概率分布的数学期望为：

Ep(f)p(x,y)f(x,y) (12)

x,y

~而p(x,y)p(x)p(y|x)，由于所建模型应符合训练语料中的概率分布，所以，如果p(x)表~

示x在训练样本中的经验分布，可令p(x)p(x)，（12）变成

Ep(f)~p(x)p(y|x)f(x,y) (13)

x,y

如果特征f对模型是有用的，则应要求(13)式所表示的特征f的数学期望与它在训练样本中的数学期望相同，即：

Ep(f)E~p(f) (14)

定义2（约束） 称式（14）为语言建模的约束方程，简称约束。

这里需要指出特征与约束的区别：特征是(x,y)的一个二值函数，而约束则是特征在所建模型中的数学期望与它在训练语料中的数学期望的方程。 3.3 基于最大熵的模型遴选

假设存在n个特征fi（i=1,2,„,n），它们是语言建模过程中对输出有影响的统计单元，我们所建立的模型应满足所有这些特征，即所建立的模型p应属于这n个特征约束所产生的模型集合C：

C{p|Ep(f)E~p(f),i{1,2,n}} (15)

ii

这里，表示所有的（无条件或无约束）概率分布模型空间，C是在加入特征约束条件后得到的的一个子集。满足约束条件的模型集C中有许多模型，我们所需要的是具有最均匀分布的模型，而条件概率p(y|x)均匀性的一种数学测量方法为条件熵，定义为：

H(p)~p(x)p(y|x)logp(y|x) (16)

x,y

其中0H(p)log|y|。

模型遴选的最大熵原理：在满足n个约束条件的前提下，具有使H(p)值最大的模型即为具有最均匀分布的模型。即

pargmaxH(p) (17) *pC

可以证明，满足(17)式的解具有如下Gibbs分布形式：

p(y|x)

1Z(x)

exp(ifi(x,y)) (18)

i

其中， Z(x)exp(ifi(x,y)) (19)

y

i

Z(x)为保证对所有x，使得

y

p(y|x)1的归一常量。

3.4 模型参数估计

在(18)式的概率模型解中，i为特征fi的相应权重参数，估算参数i的值是建模过程的重要一步。算法1给出的GIS算法是一个应用最大熵方法求解问题时的通用参数求解迭代算法，Della Pietra等人在将最大熵方法应用于自然语言处理时，对GIS进行了改进，提出了一个改进的IIS算法（Improved Iterative Scaling Algorithm），它更具有针对性。

p(x)、p(y|x)，给定一组特征｛fi，1≤i≤n｝给定训练语料，可统计出经验分布~，则计算参数i和概率模型p(y|x)的IIS算法如下：

算法2 IIS参数估计算法

输入：特征集f={f1, f2, „, fn}，经验概率~p(x,y)

~

输出：最优参数值1, 2, „, n，最佳模型p(y|x) 过程：

1. 变量初始化i=0，i=1,2,„,n。 2. 对每个fi， i{1,2,„n} ·计算i，使其满足约束：

p(x)p(y|x)fi(x,y)exp(if~x,y

n#

其中, f(x,y)fi(x,y)

i1

#

(x,y))E~p(fi)

(20)

·更新i的值，使i =i +i。

3. 若i （i=1,2,„n）不收敛，转2；否则，过程结束。

#

在本算法中，若对所有的(x, y)，f(x,y)＝M（常量），则i可以由下式直接求出：



#

i



E~p(fi)1

logMEp(fi)

(21)

若f(x,y)不是常量，则i需通过数值迭代法求得，可以采用牛顿法来求解。经验概率p(x,y)计算中，若出现0概率时，可采用一些平滑方法处理。

4．模型参数计算及说明

4.1 模型参数求取算法

在开源代码中，采用GIS算法计算参数值λj，GIS算法要求对训练集中的每个实例，对实例中的任何(a,b) ∈A×B，特征函数之和为常数，即对每个实例均满足

~



j1

k

fj(a,b)C

（其中C为一常数） (22)

如果这个条件不能满足，则根据训练集选择C，C为在训练集所有实例中根据(22)式等号左边算得的最大值。还需要增加一个修正特征（correction feature）fl,其中l=k+1,

fl(a,b)Ckj1fj(a,b) (23)

GIS算法如下：

算法1# 设共有n个特征函数，Ep[i]表示特征函数fi的模型期望，E~p[i]表示特征函数fi的样本期望。

1、 初始化：λ[1..n]=0

2、 计算特征函数的训练语料样本期望： sum=0, E~p[1..n]=0

for each b for each a

for each i such that fi(a,b)0 E~p[i] +=fi(a,b); sum+=fi(a,b);

endfor endfor endfor

for each i

E~p[i]= E~p[i]/sum

endfor

3、 计算特征函数的模型期望：

Ep[1..n]=0 for each b z=0

for each a

sum[a]=0

for each i such that fi(a,b)0 sum[a]+= λ[i]* fi(a,b)

endfor

z+=exp(sum[a]) endfor

for each a

for each i such that fi(a,b)0 Ep[i]+= fi(a,b)*~p(b)*exp(sum[a])/z

endfor endfor endfor

4、 修正λ： for each i

λ[i]+=1/C*ln(Ep[i]/E~p[i]) endfor

5、 若满足终止条件,则结束，否则执行第3步

终止条件为：达到确定的循环次数(如100次)，或者对数似然(L(p))的变化小到可以忽略时。 其中L(p)





a,b

~p(a,b)logp(a|b)

，~p(a,b)为(a,b)在样本中的出现概率。

4.2 模型参数说明

以OpenNLP MaxEnt提供的java程序中的一个例子说明生成的模型参数文件中各项代表的意义。训练语料样本文件为“gameLocation.dat”，其内容如下（序号是后加上的）：

(1) Sunny Happy Outdoor

(2) Sunny Happy Dry Outdoor (3) Sunny Happy Humid Outdoor (4) Sunny Sad Dry Outdoor (5) Sunny Sad Humid Outdoor (6) Cloudy Happy Humid Outdoor (7) Cloudy Happy Humid Outdoor (8) Cloudy Sad Humid Outdoor (9) Cloudy Sad Humid Outdoor (10) Rainy Happy Humid Indoor (11) Rainy Happy Dry Indoor (12) Rainy Sad Dry Indoor (13) Rainy Sad Humid Indoor (14) Cloudy Sad Humid Indoor

(15) Cloudy Sad Humid Indoor

利用该训练语料主要是获取决定一项运动是在户内(Indoor)还是在户外(Outdoor)举行的知识。所能获得的特征信息与天气和情绪有关(如Sunny、Happy)。OpenNLP MaxEnt提供的java程序中有几个参数可以选择：

(1) cutoff：选为特征的最小出现数，为0表示不使用此参数，所有出现的上下文都选为特征； (2) USE_SMOOTHING：是否使用平滑；

(3)_useSlackParameter：是否使用修正特征函数。

当cutoff=0， USE_SMOOTHING = false时，特征函数为： f1(a,b)=

当a=Outdoor b=Sunny时 其它

当a=Outdoor b=Happy时 其它

当a=Indoor b=Happy时 其它

当a=Outdoor b=Dry时 其它

f10f8(a,b)=

1,当a=Outdoor b=Sad时 0,其它

f2(a,b)=

f9(a,b)=

1,当a=Indoor b=Sad时 0,其它

f3(a,b)=

f4(a,b)=

1,当a=Outdoor b=Cloudy时 0,其它

当a=Indoor b=Dry时

f5(a,b)=

其它 f6(a,b)=

当a=Outdoor b=Humid时 其它

f111,当a=Indoor b=Cloudy时 0,其它

f12

1,当a=Indoor b=Rainy时 0,其它

当a=Indoor b=Humid时 其它

在训练语料样本文件中有(Sunny,Outdoor)的出现，所以有上面的特征函数f1(a,b)，而由于没有(Sunny,Indoor)的出现，才没有特征函数 f7(a,b)=

f(a,b)=

1,当a=Indoor b=Sunny时 0,其它

的出现。根据这样的原则，得出了上面的f1~f12共12个特征函数。修正特征函数如下：

f13(a,b)C12j1fj(a,b) （24）

当不使用修正特征函数时，运用GIS算法求得的模型参数文件“gameLocationModel.txt”的

内容如下（序号是后加的）：

(1)GIS (2)3(3)0.0(4)2(5)Outdoor(6)Indoor(7)3(8)1 0(9)5 0 1(10)1 1 (11)7(12)Sunny(13)Happy(14)Dry(15)Humid(16)Sad(17)Cloudy(18)Rainy (19)9.[**************](20)1.[**************]6(21)-3.[**************]5 (22)-0.[**************]4(23)0.[**************]83(24)-0.[**************]98 (25)0.[**************]9(26)-0.[**************]3(27)0.[**************]2 (28)0.[**************]5(29)-1.[1**********]009(30)12.[**************] 预测条件：用来预测结果的条件，如“Sunny”、“Happy”

(1)GIS：表示所用的算法为GIS算法 (2)3：为C

(3)0.0：为修正特征函数对应的参数

(4)2：为输出结果数目，在义项标注中为词形或词性对应的标注记号的种数

(5)(6)：为输出结果，在义项标注中为词形或词性对应的标注记号，如对“斗争vn”的标注记号为“!1$”、“!2$”

(7)按预测条件对应的结果情况所做的分类数

(8)(9)(10)：按预测条件对应的结果情况所做的分类的具体情况

java程序对输出结果做了索引，其中Outdoor的索引为0，Indoor的索引为1 (8)1 0：表示输出结果仅为0(Outdoor)的预测条件数为1

(9)5 0 1：表示输出结果为0(Outdoor)和1(Indoor)两个输出结果的预测条件数为5 (10)1 1： 表示输出结果仅为1(Indoor)的预测条件数为1 (11)7：预测条件数

(12)-(18)：各种预测条件

(19)-(30)：特征函数f1~f12所对应的特征参数