最大熵

  在学习最大熵模型前，我们需要知道熵是什么，在前面决策树那一节，我们介绍了决策树在选择特征时所采用的三种策略：信息增益、信息增益比和基尼指数，其中信息增益和信息增益比都是基于熵计算的，在那里介绍了熵是表示随机变量不确定性的度量，如果设随机变量$X$的概率分布为:
P ( X = x i ) = p i ,       i = 1 , 2 , ⋯   , n 
则随机变量 X 的熵定义为：
H ( X ) = − ∑ i = 1 n p i log ⁡ p i​
上式的 H ( X ) 为随机变量 X 的熵，也反映出随机变量 X 不确定性的度量，可以理解为无法确定的程度，就像两个事件：一、明天有98%的概率会下雨；二、明天有50%的概率会下雨。明显后者的不确定性更大，那么可以说第二个事件的熵比第一个事件的熵要大。
  何为最大熵，那就是使得 H ( X ) 值达到最大时对应的 X 分布，也称此模型为最大熵模型。由此我们也可以看出，最大熵模型是用来求解概率模型的，在所有的概率分布中，熵最大的模型就是最好的模型。一般情况下，概率分布都是有一些条件约束的，所以我们也称最大熵原理为在满足约束条件的模型集合中选取熵最大的模型。

最大熵模型

  为了给出最大熵模型的可学习形式，我们需要一步步进行推导。
  假设分类模型是一个条件概率分布$P(Y|X)$， X ∈ χ ∈ R n 表示输入， Y 表示输出。也就是说，这个模型就是给定输入 X ，需要我们以条件概率 P ( Y ∣ X ) 输出 Y 。
给定一个数据集
T = { ( x 1 , x 2 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } 
学习的目标就是用最大熵原理选择最好的分类模型。
  首先考虑模型应该满足的条件。给定数据集，可以用确定联合概率分布$P(X,Y)$的经验分布和边缘分布$P(X)$的经验分布，分别以 P ~ ( X , Y ) 表示，这里，

最大熵模型的学习方法

  在上一节中，我们学习到要想解决最大熵模型，其实就是找到熵最大的概率分布，那么如何找到最大的熵呢？总不能把所有的概率分布全部列出来，然后一个一个计算条件熵吧，这样做实在是太慢了。既然无法通过遍历的方法找到最大熵，那么我们可以将上面的第二个式子转化为一个优化模型，即定义下面的优化模型：
对于给定的特征训练集 T = { ( x 1 , x 2 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) }以及特征函数 f i ( x , y ) , i = 1 , 2 , ⋯   , n 最大熵模型的学习等价于约束最优化问题：

上面的式子看上去是不是很熟悉，没错，在SVM的数学形式其实就是这样。回想一下，在SVM中，我们利用拉格朗日乘数法将原问题转化为无约束优化的对偶问题。通过求解对偶问题求解原始问题。为什么要这么做呢？这是因为在原始问题上，求解过程中一直存在约束条件，如果将约束条件消去，那么求解过程将会简单很多。
借助SVM中的思想，我们这里理解起来将会容易很多。

求解对偶问题

  上面讲原始问题转化为求解下面的对偶问题:

求解思路和SVM中类似，首先求解内部的最小化问题 min ⁡ P ∈ C L ( p , w )这个函数的自变量是概率分布 P，加上该函数是凸函数，那么我可以用求偏导等于0的方法找到极值，具体的对函数求 L ( p , w )的偏导，得到：