最大熵模型(Maximum entropy model)
今天我们开始学习最大熵模型，该模型主要用于分类。
1 模型
熵表示对事物不确定性度量，不确定越高，熵越大。熵的计算方式如下：
在没有更多信息情况下，我们对未知情况不做任何主观假设，即将不确定部分视为等可能的。在构建分类时，对于一系列可能的条件概率分布模型，在满足已知约束情况下，我们从模型空间中选择熵最大的作为最终的分类模型。
举个非常简单的栗子，我们投掷一个6面骰子，估计1、2、3、4、5和6点出现的概率。按照最大熵原理，在没有已知约束下，每个点的概率都为1/6。若我们知道P(1)+P(2)=1/2，则1和2点概率为1/4，3、4、5和6点出现概率为1/8。
2 策略
面对更一般的情况，当我们获得一堆数据，如何以该数据为基础来求得最大熵模型？
(1) 经验联合分布和经验边缘分布
(2) 特征函数或指示函数
用来描述数据样本规律，表示某个元素x是否属于集合y。比如经典的二值函数，
(3) 约束条件
我们将特征函数在经验联合分布上的期望与在联合分布上的期望一致，以此作为约束，即：
(4) 目标函数
在约束条件下，求熵最大时的P(y|x)
3 算法
(1) 两种求解方法
a 基于拉格朗日对偶求解
基于上述的目标函数和约束，我们将约束优化化为无约束优化：
原始问题：
对偶问题：
在对偶基础上进行如下计算：
在对偶原始
b 极大似然估计求解
我们也可以采用极大似然估计求解，在拉格朗日对偶求解的第一步基础上，求解以下最大值下的P：
带入在拉格朗日对偶求解第一步解P(y|x)得到：
（2）最优化算法
IIS改进迭代尺度算法
目标函数:
基本思想：变尺度迭代wi->wi+δi，直到找到L(w)最大值
权值更新的核心推导如下(其中涉及到-logα>=1-α，jensen不等式)：
基本流程
