最大熵模型

机器学习

---

最大熵原理

在没有更多信息的情况下，那些不确定的部分都是“等可能的”，最大熵原理通过熵的最大化来表示等可能性。

---

建模

在给定训练集的情况下，我们可以得到总体联合分布$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)= \begin{cases} 1& {x与y满足某个关系}\\ 0& {否则} \end{cases}$$

可以认为只要训练集中出现的$(x^{(i)},y^{(i)})$，其$f(x^{(i)},y^{(i)}) = 1$。

特征函数$f(x,y)$关于经验分布$\overline{P}(X,Y)$的期望：

$$E_{\overline{P}}(f) = \sum\limits_{x,y}\overline{P}(x,y)f(x,y)$$

特征函数$f(x,y)$关于条件分布$P(Y|X)$和经验分布$\overline{P}(X)$的期望：

$$E_{P}(f) = \sum\limits_{x,y}\overline{P}(x)P(y|x)f(x,y)$$

分类模型要求的是条件概率分布$P(Y|X)$，如果模型可以从训练集中学习，我们就可以假设这两个期望相等。即：

$$E_{\overline{P}}(f) = E_{P}(f)$$

这是最大熵模型的约束。

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

$$H(P) = -\sum\limits_{x,y}\overline{P}(x)P(y|x)logP(y|x)$$

目标是得到使$H(P)$最大的时候对应的$P(y|x)$。

---

优化

$$\begin{aligned} \min_{P} \quad &-H(P) = \sum\limits_{x,y}\overline{P}(x)P(y|x)logP(y|x)\\ s.t. \quad &E_{\overline{P}}(f_i) - E_{P}(f_i) = 0 (i=1,2,...M)\\ &\sum\limits_yP(y|x) = 1 \end{aligned}$$

拉格朗日函数$L(P,w)$：

$$L(P,w) \equiv -H(P) + w_0(1 - \sum\limits_yP(y|x)) + \sum\limits_{i=1}^{M}w_i(E_{\overline{P}}(f_i) - E_{P}(f_i))$$

原始问题：

$$\min_P \max_w L(P, w)$$

对偶问题:

$$\max_w \min_P L(P, w)$$

第一步就是求

$$\psi(w)=\min_P L(P, w)$$

求$L(P,w)$关于$P(y|x)$的偏导数:

$$\begin{aligned} \frac{\partial L(P, w)}{\partial P(y|x)} &= \sum\limits_{x,y}\overline{P}(x)(logP(y|x) +1) - \sum\limits_yw_0 - \sum\limits_{x,y}(\overline{P}(x)\sum\limits_{i=1}^{M}w_if_i(x,y))\\ &= \sum\limits_{x,y}\overline{P}(x)(logP(y|x) +1- w_0 -\sum\limits_{i=1}^{M}w_if_i(x,y)) \end{aligned}$$

令偏导数为0

$$P(y|x) = exp(\sum\limits_{i=1}^{M}w_if_i(x,y) +w_0 -1) = \frac{exp(\sum\limits_{i=1}^{M}w_if_i(x,y))}{exp(1-w_0)}$$

由于$\sum\limits_yP(y|x) = 1$，可以得到最优解$P_w(y|x)$：

$$P_w(y|x) = \frac{1}{Z_w(x)}exp(\sum\limits_{i=1}^{M}w_if_i(x,y))$$

其中，$Z_w(x)$为规范化因子，定义为：

$$Z_w(x) = \sum\limits_yexp(\sum\limits_{i=1}^{M}w_if_i(x,y))$$

第二步对$\psi(w)$求极大，比如梯度下降法，牛顿法，拟牛顿法都可以。对于最大熵模型还有一种专用的优化方法，叫做改进的迭代尺度法(improved iterative scaling, IIS)。