admin管理员组

文章数量:821242

MaxEnt: 最大熵模型(Maximum Entropy Models)

转自:.html

刚看完HMM,因为有个ME-HMM方法,所以再看看最大熵模型,最后再把CRF模型看看,这一系列理论大体消化一下,补充一下自己的大脑,方便面试什么的能够应付一些问题。

多读书,多思考,肚子里才有东西。

==========

什么是熵?咱们这里只看信息以及自然界的熵吧。《Big Bang Theory》中Sheldon也经常把这个熵挂在嘴边。在咱们的生活中,你打碎了一块玻璃,或者洒落了一盒火柴,很自然的事情就是玻璃碎的一塌糊涂,根本没有规律可言。火柴也是,很乱,你难道从中找到规律么?规律是什么东西?规律的反面是什么?其实很有意思的事情就是自然界的东西尽可能的互补以及平衡,火柴很乱,那就规律性很小。

乱+序=1.

既然=1,那么这个乱也能描述啦?这就是熵的概念,熵是描述事物无序性的参数,熵越大则无序性越强。

我们更关注的是信息熵,怎么用熵来描述信息,不确定性等等。怎么用数学式子进行形式化描述呢?前人已经做了很多工作了:

设随机变量 ξ ,他有 A1 、 A2 .... An 共 n 个不同的结果,每个结果出现的概率为 p1 , p2 .... pn ,那么 ξ 的不确定度,即信息熵为:

H(ξ)=∑i=1npilog1pi=−∑i=1npilogpi

熵越大,越不确定。熵为0,事件是确定的。例如抛硬币,每次事件发生的概率都是1/2的话,那么熵=1:H(X)=-(0.5log0.5+0.5log0.5)=1。

那么这个式子是怎么来的呢?为什么会用log表示?我也不知道啊,查查文献。不过【参考5】中举了几个简单的例子来说明一下过程,这里引用下。

==========

例子:称硬币的问题,说有5个硬币,其中有一个是假的,这个假硬币的重量很轻,所以打算用一个天平称称,问需要最少称几次就能够保证把这个假硬币给找出来?这个问题其实是一个很经典的问题,也有另外一个类似的问题是毒水和白鼠的问题,5瓶水其中一瓶有毒,用最少几只白鼠能够保证把毒水找出来?

其实这个问题有个统一的解法就是对半分呗,二叉树,二进制等。

拿硬币的例子,可以取四个放在天平两端,如果相等那么剩下的那个就是假的。如果不相等,把轻的一端的两个硬币再称一次就知道假的了。因为这样称两次就能够保证把假硬币找出来了。这里称的事件是有三个结果的:左边重、相等、右边重。

拿小白鼠的例子,小白鼠只有活着和中毒两种状态,咱们这里人性一点儿,有解药可以解毒的,只要实验达到目的就行。那么把水分成两组,一组两瓶,一组三瓶,让一只小白鼠和一组,如果中毒,假设是三瓶的那一组,那么再递归的讲这三瓶分组,最坏情况下是用3只小白鼠。这里小白鼠的事件只有两个结果:中毒、健康。

我们假设x是那瓶毒水的序号, x∈X={1,2,3,4,5} ,y是第i只小白鼠的症状, y∈Y={1,2} ,,1表示健康,2表示中毒。

用二进制的思想的话就是设计编码 y1y2...yn 使他能够把x全部表示出来。因为一个y只有两个状态,所以要有三个y并列起来才能表示 2×2×2=23=|Y|3=8>5 。所以是用三只小白鼠。上面称硬币的问题由于一个y可以表示三个状态,所以需要两个 3∗3=9>5 就可以表示完所有的x了。

思想是这样的,从上面的分析可以看出,我们只用到的是 x , y 的状态,而没有用 x , y 的内容以及意义。也就是说只用了 X 的“总不确定度”以及 Y 的“描述能力”。

拿小白鼠和毒水的例子, X 的"总不确定度": H(X)=log|X|=log5 。 Y 的“描述能力”为: H(Y)=log|Y|=log2 。

所以至少要用多少个Y才能够完全准确的把X表示出来呢?

H(X)H(Y)=log5log2=2.31

所以得用三只小白鼠。称硬币那个问题由于 Y 的表示能力强啊, log3 的表示能力,所以表示 X 的时候仅仅需要1.46的y就行了,所以就是称2次。

那么为什么用 log 来表示“不确定度”和“描述能力”呢?前面已经讲过了,假设一个 Y 的表达能力是 H(Y) 。显然, H(Y) 与 Y 的具体内容无关,只与 |Y| 有关。所以像是 log|Y|n 这种形式,把n就可以拿出来了,因为关系不大所以扔掉n就剩下 log|Y| 了。

“不确定度”和“描述能力”都表达了一个变量所能变化的程度。在这个变量是用来表示别的变量的时候,这个程度是表达能力。在这个变量是被表示变量的时候,这个程度是不确定度。而这个可变化程度,就是一个变量的熵(Entropy)。显然:熵与变量本身含义无关,仅与变量的可能取值范围有关。

==========

下面看称硬币以及小白鼠毒水问题的一个变种:

(1)已知第一个硬币是假硬币的概率是三分之一;第二个硬币是假硬币的概率也是三分之一,其他硬币是假硬币的概率都是九分之一。(2)毒水也是,第一瓶是毒水的概率是1/3。。。以此类推。

最后求称次数或者小白鼠数量n的期望。因为第一个、第二个硬币是假硬币的概率是三分之一,比其他硬币的概率大,我们首先“怀疑”这两个。第一次可以把这两个做比较。成功的概率是三分之二。失败的概率是三分之一。如果失败了,第二次称剩下的三个。所以,期望值是:

13×log3log3+13×log3log3+19×log9log3+19×log9log3+19×log9log3=43

小白鼠的也可以同理求出来。为什么分子会有 log3 、 log9 呢?其实分子的 log3 、 log9 表示的都是“不确定度”。事件发生的确定性为1/3,那么不确定度可以理解为 log3=log11/3 ,再除以y的“表达能力”,就是每一次猜测的输出结果了,再根据期望公式 ∑ixipi 就可以求一下期望。不知道理解的对不对?

==========

更广泛的,如果一个随机变量x的可能取值为 X={x1,x2,...,xk} ,要用n位 y:y1y2...yn 表示出X来,那么n的期望是:

∑i=1kp(x=xi)log1p(x=xi)log∣∣Y∣∣=∑i=1kp(x=xi)log1p(x=xi)log∣∣Y∣∣

其实分子式不确定度,分母就是表达能力。那么 X 的信息量为:

H(X)=∑i=1kp(x=xi)log1p(x=xi)

这就是熵的定义了是吧?我们就算凑出来了。X的具体内容跟信息量无关,我们只关心概率分布,于是H(X)可以写成:

H(X)=∑i=1kp(x)log1p(x)

==========

有时候我们知道x,y变量不是相互独立的,y的作用会影响x的发生,举个例子就是监督学习了,有了标记y之后肯定会对x的分布有影响,生成x的概率就会发生变化,x的信息量也会变化。那么此时X的不确定度怎么表示呢?

H(X|Y)=∑(x,y)∈X×Yp(x,y)log1p(x∣∣y)

这个其实就是条件熵Conditional Entropy。很显然,Y加入进来进行了标记之后,就引入了知识了,所以会减小X的不确定性,也就是减小了熵。所以知识能够减小熵。

那么有了部分标记,我们就有了知识,就可以预测一部分模型,这个模型对未知的知识还是保留着熵,只是这个熵被减少了。但是我们知道熵越大,数据分布越均匀,越趋向于自然。

所以我们就想,能够弄出个模型,在符合已知知识的前提下,对未知事物不做任何假设,没有任何偏见。也就是让未知数据尽可能的自然。这就是最大熵模型(Maximum Entropy Models)了。

==========

【【未完待续:MaxEnt: 最大熵模型(Maximum Entropy Models)(二)】】

上面《MaxEnt: 最大熵模型(Maximum Entropy Models)(一)》其实就是讲了下熵,下面我们继续最大熵模型(Maximum Entropy Models)。

最大熵原理指出,当我们需要对一个随机事件的概率分布进行预测时,我们的预测应当满足全部已知的条件,而对未知的情况不要做任何主观假设。在这种情况下,概率分布最均匀,预测的风险最小。因为这时概率分布的信息熵最大,所以人们称这种模型叫“最大熵模型”。我们常说,不要把所有的鸡蛋放在一个篮子里,其实就是最大熵原理的一个朴素的说法,因为当我们遇到不确定性时,就要保留各种可能性。说白了,就是要保留全部的不确定性,将风险降到最小。----摘自《Google黑板报》作者:吴军

link

========

继续用【参考5】的例子。

“学习”这个词可能是动词,也可能是名词。可以可以被标为主语、谓语、宾语、定语……
令 x1 表示“学习”被标为名词, x2 表示“学习”被标为动词。令 y1 表示“学习”被标为主语, y2 表示被标为谓语, y3 表示宾语, y4 表示定语。得到下面的表示:

p(x1)+p(x2)=1∑i=14p(yi)=1

如果没有其他的知识,根据信息熵的理论,概率趋向于均匀。所以有:

p(x1)=p(x2)=0.5p(y1)=p(y2)=p(y3)=p(y4)=0.25

但是在实际情况中,“学习”被标为定语的可能性很小,只有0.05。我们引入这个新的知识: p(y4)=0.05 ,在满足了这个约束的情况下,其他的事件我们尽可能的让他们符合自然,符合均匀分布:

p(x1)=p(x2)=0.5p(y1)=p(y2)=p(y3)=0.953

嗯,如果再加入一个知识,当“学习”被标作动词的时候,它被标作谓语的概率为0.95,这个其实是很自然的事情。都已经是动词了,那么是谓语的可能性就很大了:

p(y2|x1)=0.95

已经有了两个知识了,第二个还是条件概率的知识,那么其他的我们尽可能的让他们不受约束,不受影响,分布的均匀一些,现在应该怎么让他们符合尽可能的均匀分布呢?

其实就是使熵尽可能的大就行了。也就是有个分布p,他尽可能的把训练集中的知识表示出来,损失最小,并且还能够保证p的熵最大:

p∗=argmaxpH(p)

那约束是什么呢?

用概率分布的极大似然对训练语料表示如下,其中是 Count(x,y) 在语料中出现的次数,N为总次数:

p¯(x,y)=1N×Count(x,y)

在实际问题中,由于条件x和结果y取值比较多样化,为模型表示方便起见,通常我们将条件x和结果y表示为一些二制特征。对于一个特征 (x0,y0) ,定义特征函数:

f(x,y)={1:y=y0&x=x00:others

特征函数在样本中的期望值为:

p¯(f)=∑(xi,yi)p¯(xi,yi)f(xi,yi)

其中 p¯(x,y) 在前面已经数了,数数次数就行。

有了训练集,我们就能够训练一个模型出来,特征f在这个模型中的期望值为:

p(f)=∑(xi,yi)p(xi,yi)f(xi,yi)=∑(xi,yi)p(yi|xi)p(xi)f(xi,yi)=∑(xi,yi)p(yi|xi)p¯(xi)f(xi,yi)

其中 p¯(xi) 为x出现的概率,数数归一化就行。

好了,约束来了,有了样本的分布,有了模型,那么对每一个特征(x,y),模型所建立的条件概率分布要与训练样本表现出来的分布相同:

p(f)=p¯(f)

==========

目标函数有了,约束有了,归纳一下最大熵模型(Maximum Entropy Models)。

p∗=argmaxp∈PH(Y|X)

P={p|p是y|x的概率分布并且满足下面的条件},对训练样本,对任意给定的特征 fi :

p(fi)=p¯(fi)

展开:

p∗=argmaxp∈P∑(x,y)p(y|x)p¯(x)log1p(y∣∣x)

约束P为:

P=⎧⎩⎨⎪⎪⎪⎪p(y|x)∣∣∣∣∣∀fi:∑(x,y)p(y|x)p¯(x)fi(x,y)=∑(x,y)p¯(x,y)fi(x,y)∀x:∑yp(y|x)=1⎫⎭⎬⎪⎪⎪⎪

========

都齐了,该求解了吧?哈哈,有没有看过wiki上的关于拉格朗日乘子Lagrange Multiplier的问题,恰好这里面有个例子就是求最大熵的,哈哈。所以我们可以用拉格朗日乘子法来求解。

对于有k个约束的优化问题:

 

maxH(p)s.t.:Ci(p)=bi,i=1,2,...,k

 

可以引入k个拉格朗日算子

 

Λ=[λ1,λ2,...,λk]T

 

,那么拉格朗日函数为:

 

L(p,λ)=H(p)+∑i=1kλi[Ci(p)−bi]

 

OK,咱们开始一步一步的带入求解 ∂L∂p=0 。

由于约束中有两部分组成,对于第二部分,我们引入拉格朗日算子为 γ :

 

L(p,Λ,γ)=∑(x,y)p(y|x)p¯(x)log1p(y|x)+    ∑i=1kλi∑(x,y)(p(y|x)p¯(x)fi(x,y)−p¯(x,y)fi(x,y))+   γ⎛⎝∑yp(y|x)−1⎞⎠

 

下面就是就偏微分=0计算最优解了:

 

∂L∂p(y|x)=p¯(x)(log1p(y|x)−1)+∑i=1kλip¯(x)fi(x,y)+γ=0

 

求得最优解的参数形式:

 

p∗(y|x)=e∑iλifi(x,y)+γp¯(x)−1

 

但是里面还有参数,所以我们必须求得 γ∗ 和 Λ∗ 。

巧妙的是我们发现最后节的后面部分有个类似的常数项:

 

e∑iλifi(x,y)+γp¯(x)−1=e∑iλifi(x,y)eγp¯(x)−1

 

而且有意思的是,前面问题的第二个约束中有:

 

∀x:∑yp(y|x)=1

 

从而:

 

∑yp∗(y|x)=∑y(e∑iλifi(x,y)eγp¯(x)−1)=1eγp¯(x)−1∑ye∑iλifi(x,y)=1eγp¯(x)−1=1∑ye∑iλifi(x,y)=Z(x)

 

也就是式子中的关于 γ 的常数项我们用关于 Λ 的常数项进行代替了,这样参数就剩下一个了:

 

p∗(y|x)=Z(x)e∑iλifi(x,y)Z(x)=1∑ye∑iλifi(x,y)

 

那么剩下的一个参数 Λ 应该怎么进行求解呢?

解法以及最大熵模型与最大似然估计的关系在参考5中很详细,还有GIS以及IIS的方法进行求解,以后再写《MaxEnt: 最大熵模型(Maximum Entropy Models)(三)》。

有什么问题请留言。

参考:

1、A maximum entropy approach to natural language processing (Adam Berger)

2、A Brief MaxEnt Tutorial (Adam Berger)

3、Learning to parse natural language with maximum entropy models (Adwait Ratnaparkhi)

4、中科院刘群教授《计算语言学-词法分析(四)》

5、《最大熵模型与自然语言处理》:laputa,NLP Group, AI Lab, Tsinghua Univ.

 

本文标签: MaxEnt 最大熵模型(Maximum Entropy Models)