最大熵模型

1. 早餐问题

所谓最大熵模型，就是遵循两个原则：

(1) 为所有已知的信息建模；

(2) 对未知不做任何假设，保持均衡。

很多资料在讲最大熵模型时，都用骰子做例子，这里就不重复了。举个更实际点的例子，用来说明最大熵的运用。

假设Y公司为鼓励员工按时上班，规定在早晨9点以前到公司的员工由公司提供一份免费的早餐。公司可以提供两种两种套餐，套餐A是中式的包子豆浆，价值5元，套餐B是西式的咖啡汉堡价值8元，每位9点以前到的员工只能订一份早餐，经过一段时间的运营，公司发现在这项福利上的开销大约是人均4元。请问，选择套餐A和套餐B的员工比例最有可能是多少？

设选择A套餐的员工比例是P(A)，选择B套餐的员工比例是P(B)，不要忘记9点以后来的不能享受免费早餐的那些兄弟，假设他们的比例是P(C)，很显然，依据题意有：

P(A)+P(B)+P(C)=1 (1)

P(A)*5+P(B)*8+P(C)*0=4 (2)

以上(1)(2)两式即是对已知信息建模。显然上式有三个变量，但只有两个方程式，解有无穷多个。比如P(A)=0.2，P(B)=0.375，P(C)=0.425或者P(A)=0.4, P(B)=0.25, P(C)=0.35，这两组都是上述模型的解。

这里就可以引入最大熵模型的概念了，前面我们已经满足了最大熵模型的第一条法则：对所有已知信息建模。那么第二条法则：对未知不做任何假设，保持均衡。如果只是前半句：“不做任何假设”，我们发现解可以有无穷多个，但注意后半句“保持均衡”。什么叫保持均衡呢？这就体现了最大熵模型名字的由来——即模型认为，熵最大的时候就是最均衡的时候。什么是熵，请参考吴军老师的《数学之美——怎样度量信息》，这里就不再赘述了。熵是度量信息的单位，要保持信息量最大，就要使熵最大，因此，直接引入熵的计算公式：

即可得H=-[P(A)logP(A)+P(B)logP(B)+P(C)logP(C)] (3)

所谓的“保持均衡”即要使得(3)式最大。由(1)(2)式，可将P(B)和P(C)都化为由P(A)表示，带入(3)式，H即成为只有一个自变量P(A)的函数，求最大，即对(3)式求导，使得导数为0，解出P(A)，再反解出P(B)和P(C)，这就是最大熵模型假设下早餐问题的解。令P(A)=x（注意这里的x与上面熵公式中的x不是同一个，这里只是为了让式子好看），由(3)求导得方程式：

(4)

要解出(4)式不是一件容易的事情，这里先略过，总之由最大熵模型，我们是可以给出早餐问题的解的。

通过对早餐问题的分析，我们引入了最大熵模型的概念，并能够理解它的两条准则：对已知建模和对未知保持均衡。现在我们需要更进一步，看看自然语言处理中的最大熵模型是什么样子的。

2. feature和建模

首先还是从一个实际的例子开始，我们使用自然语言处理的经典问题——词性标注(Part-Of-Speech Tagger)作为例子，假设我们要标注“把/这/篇/报道/编辑/一下。”(事先已经分好词)，其期待的标注结果是：“把/p（介词）这/r（代词）篇/q（量词）报道/n（名词）编辑/v（动词）一下/mq（数量词）”，这里“报道”和“编辑”都是既可以做动词又可以做名词的，但它们在这句话里的词性是确定的，这是由它们所处的上下文决定的。以标注“报道”为例，我们截取它的上下文（设定上下文以前后2个term为窗口）：“这(w_i-2)/篇(w_i-1)/报道(w_i)/编辑(w_i+1)/一下(w_i+2)”，用符号x表示上下文(context)，则x=(w_i-2, w_i-1, w_i, w_i+1, w_i+2)，用符号y表示标记结果(label)，要标记的词是w_i，则问题即是在给定x的情况下，y是什么。用概率论来表达，即要求:

最大熵模型就是要解决计算P(y|x)的问题（直接对P(y|x)建模，所以它是判别式模型（Discriminative Model））。自然的，对于给定的上下文x，其要标注的w_i是各种y的概率之和应为1，即P(y|x)应该满足下面的约束条件:

(5)

我们知道机器学习的模型都有feature的概念，通过feature来表示样本或者新看到的条目，进而计算出预测值y。最大熵模型也不例外，现在我们开始引入feature，我们使用wi的前一个词，前两个词，后一个词，后两个词，wi本身，w_i的前一个POS Tag(记为t_i-1)以及前2个POS tag(t_i-2t_i-1)作为feature template，则具体的feature可以定义成：

由上可见一个feature是一个二值函数，表示在x中，满足某种条件(contexual predicate，简称cp)并且lable为某个特定的y时，feautre函数值为1（称feature函数值为1时叫命中feature），否则为0。注意feauture的主要意思都表示在其下标i中，如上例中的f₁的1下标表示了“在上下文x中，w_i-1='篇'”并且标注y=n”的意思，而f括号中的两个自变量，则是当前样本中你所遇到的真实的x和y，所以当你遇到一个在训练样本中y=v的条目时，f₁(x,y)一定等于0。

一个feature template可以产生很多的feature，比如feature template: w_i的前一个词，可以产生W*M数量级的feature(W是词的数量，M是label y可能的数量，注意这里用的表述是数量级，也是这个template能产生feature的上限，具体的数目取决于训练样本中出现的情况)，而feature template: 前两个POS tag则可以产生M³数量级的feature。下表列出了词性标注例子中所用的feature template以及可能产生feature的数量级：

表1 feature template 和 feature的关系
feature template	产生feature的数量级	说明
w_i-1	W*M	wi的前一个词
w_i-2w_i-1	W²*M	wi的前两个词
w_i+1	W*M	wi的后一个词
w_i+1w_i+2	W²*M	wi的后两个词
w_i	W*M	wi本身
t_i-1	M²	w_i的前一个POS Tag
t_i-2t_i-1	M³	w_i的前2个POS tag

你也可以再定义自己的feature template，如可以用汉字的字形做feature template: w_i中含有以"扌"为部首的字(是动词的可能性较大)。可以看出，最大熵模型产生的feature是很惊人的，所以求解模型参数是学术界很重要的一个研究问题。

由feature的定义，可以写出一个feature f_i 在训练集合上命中(feauture函数为1)的概率是：

(6)

解释一下(6)，它意味着你遍历所有的训练样本，对命中了f_i的样本计数，再除以总样本数，即为。记住i代表了feature的主要意义，对于那些y不符合下标i中要求的样本，f_i(x,y)=0。另外：

，意味着训练样本中可能出现重复的<x,y>对，去重之后就如(6)式那样计算。

(6)式是在训练样本中实际观察到的情况，而模型本身就是要求解P(y|x)，由贝叶斯公式可知：P(x,y)=P(y|x)P(x)，那么模型期望的P(f_i)(注意与观察值的区别在于头顶没有~)就可以写成下式：

(7)

记住最大熵模型的第一个原则：对所有已知的信息建模。这就要求模型算出后，对每一个feature函数命中的期望概率p(f_i)应该完全等于在训练样本中观察得到的概率，所以我们又得到了第二个约束条件（称上面的(5)式为第一个约束条件，叫归一化约束条件）：

上式中左边是模型的对f_i命中的期望概率，右边是训练样本中观察到的f_i命中的实际概率。左边的P(x)可以直接用似然估计，即样本中观察到的x的数量除以总数N作为P(x)，即：，代入上式则可以写成：

(8)

(8)式即为第二个约束条件，是由模型第一个原则推导出来的约束条件。

再来看最大熵模型的第二条原则：对未知不做任何假设，保持均衡。如前面所讲的例子，保持均衡即使熵最大。而模型本身是对条件概率P(y|x)建模，所以熵也相应的变成条件熵，即使得H(y|x)最大。把x和y看成随机变量，条件熵衡量的是在给定x的情况下，y还能提供多少信息量，即去掉x提供的信息量后，y剩下的信息量。它是随机变量x和y一共提供的信息量（成为联合熵H(x,y)）减去x的信息量(H(x))，于是有：

(9)

所谓第二条原则，就是要使(9)式最大。我们看到很容易计算（从训练样本中统计即可），而P(y|x)是未知的，需要建模的，于是可以把(9)式看成是P(y|x)的函数，为方便起见，简写成看成是p的函数，所以模型就是要找到一组在训练样本上的P(y|x)，使得相对熵H(y|x)最大，即：

(10)

联立(5)(8)(9)式，我们就得到了最大熵模型的数学表述：

也就是在满足归一化约束条件和原则一的约束条件的基础上，使得(10)式取得最大值。注意两个约束条件的数学表达式其实是两组表达式，因为对样本中的每一个上下文x_i，在所有lable集合Y上，概率都要为1；对每一个feature函数f_i，命中概率的约束都相等。

本节我们引入了feature的概念，并运用最大熵模型的两条原则，推导出了其数学描述。下一节将讲一讲如何求解模型。

3. 求解模型

 1 /**
 2  * 求解早餐问题：牛顿法求解方程g(x)=log(x)-5log(4-5x)/8-3log(4-3x)/8+3=0
 3  *
 4  * @author wowarsenal
 5  *
 6  */
 7 public class Newton {
 8     
 9     public static double[] inits = new double[] {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7};
10     
11     public double solve(double init) {
12         
13         double curr = init;
14         double prev = 0;
15         int iter=0;
16         do {
17             //计算g(curr)
18             double g_curr=Math.log(curr)-5*Math.log(4-5*curr)/8-3*Math.log(4-3*curr)/8+3;
19             //计算g'(curr)
20             double gg_curr=1/curr+25/(8*(4-5*curr))+9/(8*(4-3*curr));
21             double next = curr-g_curr/gg_curr;
22             prev=curr;
23             curr=next;
24             iter++;
25         } while (Math.abs(curr-prev)>0.001);
26         System.out.print("iter="+iter);
27         return curr;
28     }
29     
30     public static void main(String[] args) {
31         Newton nt = new Newton();
32         for (double d: inits) {
33             System.out.print("init="+d + ", ");
34             double pa=nt.solve(d);
35             double pb=(4-5*pa)/8;
36             double pc=(4-3*pa)/8;
37             System.out.println(", resloved: pa="+pa+", pb="+pb+", pc="+pc);
38         }
39         
40     }
41 }

1 init=0.1, iter=3, resloved: pa=0.16421345158484768, pb=0.39736659275947017, pc=0.43841995565568215
2 init=0.2, iter=3, resloved: pa=0.1642138478722876, pb=0.39736634507982027, pc=0.43841980704789213
3 init=0.3, iter=4, resloved: pa=0.16421384843837025, pb=0.3973663447260186, pc=0.43841980683561116
4 init=0.4, iter=4, resloved: pa=0.16421382337391127, pb=0.39736636039130546, pc=0.43841981623478327
5 init=0.5, iter=4, resloved: pa=0.16421384101970118, pb=0.3973663493626868, pc=0.43841980961761207
6 init=0.6, iter=4, resloved: pa=0.16421384854944376, pb=0.39736634465659765, pc=0.4384198067939586
7 init=0.7, iter=5, resloved: pa=0.1642138429126999, pb=0.39736634817956257, pc=0.4384198089077376

由上，我们可以得到早餐问题大致的比例分布式：P(A)=16.4%, P(B)=39.7%, P(C)=43.9%，也就是说，老板只要统计一下每月人均早餐开销，就能大致推断出有多少人没有正点上班了:)。