Maximum Entropy Model

定义

最大熵模型也是判别模型,其基本思想是最大熵思想,即在给定关于概率分布不完全信息的情况下,仅有的无偏假设就是使得模型尽可能地均匀,通俗点说就是对一个随机事件的概率分布进行预测时,预测应当满足全部已知的约束,而对未知的情况不要做任何主观假设。在这种思想下,合适的模型就是在满足给定限制情况下最大化模型的熵。对于条件模型$p(y|x)$,其条件熵的定义为

其中,$Z$包含$x,y$的所有可能组合。

训练样本由输入、标签表征。这里引入特征函数的概念,特征函数和以前看到的特征不大一样,它是对输入和输出同时抽取特征,表示为$f(x,y)$。特征函数可以定义为二值函数,如果$x,y$满足一定的事实,那么$f(x,y)$为1,否则为0。

约束

假设训练数据集$T$有$n$条数据,特征个数为$m$个,第$i$个特征对应的特征函数为$f_i(x,y)$。令由训练数据得到的经验联合分布为$\hat{p}(x,y)$,那么特征$f_i$关于经验分布的期望值为

同样地,在模型分布上的特征函数均值可以表示为

其中,$Z$是$x,y$所有可能组合。(这里因为$x,y$所有可能组合会很多,计算上不可行)。$x$仅考虑训练集中的$x$,而$y$则是所有可能的取值,但是在实际中,$y$的可能取值是有限的、比较少的,所以这里的计算也是高效的。

至此,得到第一种约束。如果模型可以从数据中获取足够多的信息,就可以认为经验值约等于期望值,即


第二种约束为概率本身的限制,即:


类似地,可以得到

目标函数

按照最优化问题的优化习惯,将最大化问题改写成最小化问题

模型训练

带约束的优化问题可以参考拉格朗日乘子法,引入参数$\lambda=(\lambda_1,…,\lambda_{m+1})$,令

考虑上式与原始优化问题之间联系,对于约束问题,如果有一个不满足条件,那么将对应的$\lambda$分量扩展到$\infty$,那么整个公式的值就变成了$+\infty$。所以可以得到

因为函数$\Gamma(p,\lambda)$是$p(y|x)$的凸函数,所以根据拉格朗日对偶性有


首先看$\min_{p(y|x)}\Gamma(p,\lambda)$:
我们可以求$\Gamma(p,\lambda)$对$p(y|x)$的导数。逐项考虑,首先

第二项

第三项比较简单,就不单独列出来了,所以$\Gamma(p,\lambda)$对$p(y|x)$的导数可以表示为:

令上式等于0可以得到:

为了使$p(y|x)$的表达式只与特征函数有关,我们最好消去$\hat{p}(x)$。注意到$\sum_y p(y|x)=1$,将上式两边对$y$求和,可以得到

进一步可以得到

综上所述,最大熵模型也就是


第二步,求解$\lambda^{}$:
令$\Psi_{p^{
}}= \min_{p(y|x)}\Gamma(p,\lambda)$,下一步就是


可以证明,最大熵模型是适定的(well-defined),其解存在且唯一。

参考文献
[1]. Classical Probabilistic Models and Conditional Random Fields.pdf
[2]. 统计学习方法. 李航

分享到