最大熵模型

熵的概念

熵度量了事物的不确定性，越不确定的事物，它的熵越大，表示如下：

[H(X)=-sum_{i=1}^np_ilog p_i ]

n代表X的n种不同离散取值，而(p_i)代表了X取值为i的概率。

多个变量联合熵表示为

[H(X,Y)=-sum_{i=1}^np(x_i,y_i)log p(x_i,y_i) ]

条件熵的表达H(Y|X)表示如下：

[H(Y|X)=sum_{j=1}^np(x_j)H(Y|x_j)=-sum_{i=1}^np(x_i,y_i)log p(y_i|x_i)quad(1)\ H(Y|X)=-sum_{i=1}^np(x_i,y_i)log p(y_i|x_i)=sum_{j=1}^np(x_j)H(Y|x_j) ]

可以按式(1)顺序推导证明，注意区别熵H和概率P，条件熵的定义可以理解为在X划分下，Y的纯度。

[egin{split} H(Y|X)&=sum_xp(x)H(Y|X=x)\ &=-sum_xp(x)sum_yp(y|x)log p(y|x)\ &=-sum_xsum_yp(x)p(y|x)log p(y|x)\ &=-sum_xsum_yp(x,y)log p(y|x)\ &=-sum_{x,y}p(x,y)log p(y|x) end{split} ]

同时可以证明

[H(Y|X)=H(X,Y)-H(X)\ H(X|Y)=H(X,Y)-H(Y) ]

最大熵模型的定义

最大熵模型是一个条件概率分布(P(Y|X))，X为特征，Y为输出。

给定一个训练集((x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(m)},y^{(m)}))，其中x为n维向量，y为类别输出，我们的目标是用最大熵模型选择一个最好的分类类型。

给定训练集情况下，使用联合分布(P(X,Y))的经验分布(overline P(X,Y))和边缘分布(P(X))的经验分布(overline P(X))，(overline P(X,Y))即为训练集X，Y同时出现的次数除以样本总数m，(overline P(X))即为训练集中X出现的次数除以样本总数m。

用特征函数(f(x,y))描述输入x和输出y之间的关系，定义为：

[f(x,y)= egin{cases} 1qquad x与y满足某个关系\ 0qquad 否则 end{cases} ]

可以认为只要出现在训练集中出现的((x^{(i)},y^{(i)}))其(f(x^{(i)},y^{(i)})=1)，同一个训练样本可以有多个约束特征函数。

特征函数(f(x,y))关于经验分布(overline P(X,Y))的期望值，用(E_{overline P}(f))表示为：

[E_{overline P}(f)=sum_{x,y}overline P(x,y)f(x,y) ]

特征函数(f(x,y))关于条件分布(P(Y|X))和经验分布(overline P(X))的期望值，用(E_P(f))表示为：

[E_P(f)=sum_{x,y}overline P(x)P(y|x)f(x,y) ]

如果模型可以从训练集中学习，我们可以假设这两个期望相等，即

[E_{overline P}(f)=E_p(f) ]

以上就是最大熵模型学习的约束条件，假如我们有M个特征函数(f_i(x,y)(i=1,2,...,M))就要M个约束条件，可以理解我们如果训练集有m个样本，就有和这m个样本对应的M个约束条件。

这样我们就得到了最大熵模型的定义如下：

假设满足所有约束条件的模型集体为：

[E_{overline P}(f_i)=E_P(f_i)(i=1,2,...,M) ]

定义在条件概率分布$P(Y|X)上的条件熵为

[H(P)=-sum_{x,y}overline P(x)P(y|x)log P(y|x) ]

我们的目标是得到使(H(P))最大的时候对应的(P(y|x))，这里对(H(P))加一个负号，方便优化求解。

最大熵模型损失函数的优化

定义最大熵模型的损失函数(-H(P))如下：

[underbrace{min}_P-H(P)=sum_{x,y}overline P(x)P(y|x)log P(y|x) ]

求解过程使用了拉格朗日乘子，过程略。。。。

最大熵模型总结

越确定的情况，不确定性越小，信息量越少；

不确定的情况，不确定性越大，信息量越大。

信息增益越大，消除了更多的不确定性，越适合做分类特征。

最大熵模型优点：

获得满足约束条件的模型中信息熵极大的模型，作为经典的分类模型时准确率较高。
可以灵活设置约束条件，来调节模型对未知数据的拟合成度。

最大熵模型缺点：

约束条件与样本数量有关，导致迭代过程计算量巨大。实际应用较难。