最大熵模型原理——选择符合所有事实，在其他方面尽可能均匀分布（熵最大）的模型，其实思想很简单，只是数学推导蛋疼

1.熵与最大熵原理

熵是随机变量不确定性的度量，不确定性越大，熵值就越大；若随机变量退化成定值，熵为0。均匀分布是“最不确定”的分布

假设离散随机变量X的概率分布为P(x)，则其熵为：

联合熵和条件熵

两个随机变量的X，Y的联合分布，可以形成联合熵，用H(X,Y)表示

条件熵H(X|Y) = H(X,Y) - H(Y)

 相对熵与互信息

 设p(x),q(x)是X中取值的两个概率分布，则p对q的相对熵是：

两个随机变量X，Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。

最大熵原理是统计学的一般原理，也是概率模型学习的一个准则。最大熵原理认为，学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。

2.最大熵模型

2.1最大熵模型的实例（参考[1])

在英汉翻译中，take有多种解释例如上文中存在7中，在没有任何限制的条件下，最大熵原理认为翻译成任何一种解释都是等概率的。

实际中总有或多的限制条件，例如t1,t2比较常见，假设满足

同样根据最大熵原理，可以得出：

实际的统计模型中，还需要引入特征提高准确率。例如take翻译为乘坐的概率小，但是当后面跟着交通工具的名词“bus"，概率就变得非常大。

用特征函数f(x,y)描述输入x,输出y之间的某一个事实，只有0和1两种值，称为二值函数。例如：

最大熵模型根据最大熵原理在类似上面的特征限制下选择最优的概率分布。

 再一个例子

我们通过一个简单的例子来了解最大熵的概念。假设现在需要做一个自动将英语到法语的翻译模型，为了方便说明，我们将这个问题简化为将英文句子中的单词{in}翻译成法语词汇。那么翻译模型p就是对于给定包含单词”in”的英文句子，需要给出选择某个法语单词f做为”in”的翻译结果的概率p(f)。为了帮助开发这个模型，需要收集大量已经翻译好的样本数据。收集好样本之后，接下来需要做两件事情：一是从样本中抽取规则（特征），二是基于这些规则建立模型。
从样本中我们能得到的第一个规则就是in可能被翻译成的法语词汇有：

{dans, en, à, aucours de, pendant}。

也就是说，我们可以给模型p施加第一个约束条件：

p(dans)+p(en)+ p(à)+p(aucours de)+p(pendant)= 1。

这个等式是翻译模型可以用到的第一个对样本的统计信息。显然，有无数可以满足上面约束的模型p可供选择，例如：

p(dans)=1，即这个模型总是预测dans

或者

p(pendant)=1/2and p(à)=1/2，即模型要么选择预测pendant，要么预测à。

这两个模型都只是在没有足够经验数据的情况下，做的大胆假设。事实上我们只知道当前可能的选项是5个法语词汇，没法确定究竟哪个概率分布式正确。那么，一个更合理的模型假设可能是：

p(dans)= 1/5

p(en)= 1/5

p(à)= 1/5

p(aucours de) = 1/5

p(pendant)= 1/5

即该模型将概率均等地分给5个词汇。但现实情况下，肯定不会这么简单，所以我们尝试收集更多的经验知识。假设我们从语料中发现有30%的情况下，in会被翻译成dans 或者en，那么运用这个知识来更新我们的模型，得到2模型约束：

p(dans)+ p(en)= 3/10

p(dans)+p(en)+ p(à)+p(aucours de)+p(pendant)= 1

同样，还是有很多概率分布满足这两个约束。在没有其他知识的情况下，最直观的模型p应该是最均匀的模型（例如，我拿出一个色子问你丢出5的概率是多少，你肯定会回答1/6），也就是在满足约束条件的情况下，将概率均等分配：

p(dans)= 3/20

p(en)= 3/20

p(à)= 7/30

p(aucours de) = 7/30

p(pendant)= 7/30

假设我们再一次观察样本数据，发现：有一半的情况，in被翻译成了dans 或 à。这样，我们有就了3个模型约束：

p(dans)+ p(en)= 3/10

p(dans)+p(en)+ p(à)+p(aucours de)+p(pendant)= 1

p(dans)+ p(à)=1/2

我们可以再一次选择满足3个约束的最均匀的模型p，但这一次结果没有那么明显。由于经验知识的增加，问题的复杂度也增加了，归结起来，我们要解决两组问题：第一，均匀(uniform)究竟是什么意思?我们怎样度量一个模型的均匀度(uniformity)？第二，有了上述两个问题的答案，我们如何找到满足所有约束并且均匀的模型？

最大熵算法可以回答上面的2组问题。直观上来将，很简单，即：对已知的知识建模，对未知的知识不做任何假设。换句话说，在给定一组事实（features+output）的情况下，选择符合所有事实，且在其他方面尽可能均匀的模型。这也是我们在上面的例子中，每次选择最恰当的模型用到的原理。俗话说，不把鸡蛋放在一个篮子里，正是运用的这个原理来规避风险。

 2.2 最大熵模型的数学推导（参考[2]）

对于给定的训练数据集T={（x1，y1）,（x2，y2）,(x3，y3)...(xn，yn)}以及特征函数fi(x,y),i=1,2,3...n，最大熵模型的学习等价于约束的最优化问题：

 引入朗格朗日算子W，定义拉格朗日函数L(P,w)

最优化的原始问题：

对偶问题是：

由于L(P,W)是P的凸函数，原始问题的解与对偶问题的解是等价的。这里通过求对偶问题的解来求原始问题的解。

第一步求解内部极小化问题，记为：

通过微分求导，得出P的解是：

第二步求外部的极大化问题：

最后的解记为：

第三步可以证明对偶函数的极大化等价于第一步求解出的P的极大似然估计，所以将最大熵模型写成更一般的形式.

案例：

已知有A,B,C,D,E五种可能出现的情况，已知A,B出现的概率之和是3/10，所有五个出现概率之和为1，使用最大熵模型进行优化获得这五种情况的概率分布。==》最后答案是P（A）=P（B）=3/20，P(C)=P(D)=P(E)=7/30，使用了复杂的最大熵推导，最后确得出了简单清晰的结论。

该问题主要通过使用拉格朗日的对偶性，然后通过求解对偶最优化问题得到解。

所以我们有：

第一步，求解原始问题：

第二步，利用拉格朗日乘子法：

第三步：对偶问题求解：

最终结果为：

这里我们先固定w0和w1，然后对L(P,w)求偏导数，可以带入得到

后我们可以通过另这些偏导为0，解得：

然后将P（y1）-- P（y5）全部代入L（P,w）,然后可以获得最小值,再去求解极大化问题：

再去对这个函数进行对w0、w1的求偏导并=0，可以得到

所以得到：

就得到最后的结果了。