最大熵模型

最大熵原理

当你发现了一枚硬币，可能不知道硬币的密度是否均匀，材质如何。但如果有人让你猜测这枚硬币掉在地上时出现正面与反面的概率，你可能毫不犹豫的回答 $\frac 1 2$，可是你知道这看似简单的不能再简单的问题背后隐藏的原理吗？

最大熵原理就可一很清楚的解释这一问题。最大熵原理认为，学习概率模型时，所有的概率分布中，熵最大的模型总是最好的。

关于均匀分布

假设离散随机变量 $X$ 的分布是 $P(X)$，则其熵为：

$$H(P) = -\sum _{x}P(x)\log P(x)$$

熵满足下列不等式：

$$0\leq H(P)\leq \log|X|$$

当且仅当 $X$ 是均匀分布时，右边的等号成立，$H(P)$ 最大。

关于正态分布

对于连续的随机变量 $X$ 的分布是 $P(X)$，则其熵为：

$$H(P)=-\int_{-\infty}^{\infty}P(x)\log P(x)dx$$

如果已知分布的均值 $\mu$ 与方差 $\sigma^2$，如果想使得熵最大，那么则需要求解下面的规划问题：

$$\begin{align} \max_P & \quad H(P)=-\int_{-\infty}^{\infty}P(x)\log P(x)dx\\ \text{s.t.}&\quad \cases{ \int_{-\infty}^{\infty}P(x)dx=1\\ \int_{-\infty}^{\infty}xP(x)dx=\mu\\ \int_{-\infty}^{\infty}(x-\mu)^2P(x)dx=\sigma^2 } \end{align}$$

引入拉格朗日乘子 $\lambda_0,\lambda_1,\lambda_2$，则：

$$\begin{align} L(P,\lambda)=&-\int_{-\infty}^{\infty}P(x)\log P(x)dx+\lambda_0\left(\int_{-\infty}^{\infty}P(x)dx-1\right)\\ &+\lambda_1\left(\int_{-\infty}^{\infty}xP(x)dx-\mu\right)+\lambda_2\left(\int_{-\infty}^{\infty}(x-\mu)^2P(x)dx-\sigma^2\right)\\ =&\int_{-\infty}^{\infty}P(x)\log P(x)+\lambda_0P(x)+\lambda_1xP(x)+\lambda_2(x-\mu)^2P(x)dx+C \end{align}$$

令

$$\begin{align} F &=P(x)\log P(x)+\lambda_0P(x)+\lambda_1xP(x)+\lambda_2(x-\mu)^2P(x)\\ \end{align}$$

则 $F$ 为 $P(x)$ 的泛函：

$$F=J[P(x)]$$

根据欧拉-拉格朗日方程：

$$\frac{\partial F}{\partial P(x)}-\frac{d}{dx}\left(\frac{\partial F}{\partial P'(x)}\right)=0$$

$\frac{\partial L}{\partial p}=0$ 等价于

$$\frac{\partial F}{\partial P(x)}=\log P(x)+1+\lambda_0+\lambda_1x+\lambda_2(x-\mu)^2=0$$

可得

$$\begin{align} P(x)&=\exp(-1-\lambda_0)\exp(\lambda_1x+\lambda_2(x-\mu)^2)\\ &=C\exp\lambda_2(x-\mu+\frac{\lambda_1}{2\lambda_2} )^2 \end{align}$$

可知分布 $P(x)$ 关于 $x=\mu-\frac{\lambda_1}{2\lambda_2}$ 对称，则 $\mu =\mu-\frac{\lambda_1}{2\lambda_2}$。可知 $\lambda_1=0$。

根据约束可最终得出结论：当知道分布的均值与方差（或者一阶矩与二阶矩）时，正态分布 $P\sim \mathcal N(\mu,\sigma^2)$ 熵最大。

最大熵模型

而将最大熵原理应用于分类问题中，就得到了最大熵模型。

假设分类模型是一个条件分布 $P(Y|X)$，$X\in \mathcal X\subseteq\mathbb R^n$ 表示输入，$Y\in \mathcal Y$ 表示输出。给定一个训练集

$$T = \{ (x_1, y_1),(x_2, y_2),\cdots,(x_N, y_N) \}$$

根据数据集可以确定联合分布 $P(X,Y)$ 与边缘分布 $P(X)$ 的经验分布 $\tilde{P}(X,Y),\tilde P(X)$，记 $\nu(X=x,Y=y)$ 为指样本中出现 $(x,y)$ 的频数，$\nu(X=x)$ 为指样本中输入 $x$ 的频数。计算方式如下：

$$\begin{align} &\tilde P(X=x,Y=y)=\frac{\nu(X=x,Y=y)}N\\ &\tilde P(X=x)=\frac{\nu(X=x)}N \end{align}$$

知道了分布之后，那么你就可以求得一些关于分布 $\tilde P$ 统计量，比如 $E\tilde P(x)$， $Var\tilde P(x)$ 之类的。

由于已知的样本的可能需要满足一些约束，或者说既定事实，那么我们假设某一输入 $x$ 和输出 $y$ 存在一些约束，并且用一特征函数 $f(x,y)$ 来表示：

$$\begin{cases} 1，\quad 输入x 和输出 y 存在约束关系\\ 0，\quad 否则 \end{cases}$$

这样，我们可以得到特征函数 $f(x,y)$ 关于 $\tilde{P}(X,Y)$ 的期望：

$$E_\tilde P(f) = \sum_{x,y}\tilde P(x,y)f(x,y)=\Delta$$

👇 其实这里挺难理解的，什么是既定事实呢？

假如一个骰子🎲是特殊的，在数据集中没有点数为 6 的结果，因为点数为 6 的结果都被记作了 5，那么我们的模型就需要下面这个约束，或者说既定事实：

$$\tilde P(X=5)=\frac 2 6$$

或者说根据先验知识和数据可以知道：

$$\tilde P(X=1) + \tilde P(X=5) = \frac 1 2$$

👆 这些约束进行数学语言的描述就成了上面的式子。

定义 $P(Y\ |\ X)$ 的条件熵为：（关于条件熵，大家可以看👉熵）

$$H(P)=-\sum_{x,y}\tilde P(x)P(y\ |\ x)\log P(y\ |\ x)$$

而最大熵模型需要训练目标函数则是得出一个分布 $P$，使得条件熵最大，并且这个分布还要满足根据数据所知的既定事实 $E_\tilde P(f)$：

$$\begin{align} \max_P&\quad H(P)\\ \text{s.t.}&\quad \cases{ \sum_y P(y\ |\ x)=1\\ E_P(f_i)=E_\tilde P(f_i)=\Delta_i,\quad i=1,2,\cdots,n } \end{align}$$

其中

$$E_P(f)=\sum_{x,y}\tilde P(x)P(y\ |\ x)f(x,y)$$

表示特征函数 $f(x,y)$ 关于模型 $P(Y\ |\ X)$ 的期望值。

将最大化问题改写成最小化问题：

$$\begin{align} \min_P&\quad \sum_{x,y}\tilde P(x)P(y\ |\ x)\log P(y\ |\ x)\\ \text{s.t.}&\quad \cases {\sum_y P(y\ |\ x)=1\\ E_P(f_i)=E_\tilde P(f_i)=\Delta_i,\quad i=1,2,\cdots,n} \end{align}$$

引入一组拉格朗日乘子 $\lambda_0,\lambda_1,\lambda_2,\cdots,\lambda_n$，定义拉格朗日函数：

$$\begin{align} L(P,\lambda) &=\sum_{x,y}\tilde P(x)P(y\ |\ x)\log P(y\ |\ x) +\lambda_0\left(1-\sum_y P(y\ |\ x)\right)\\ &+\sum_{i=1}^n\lambda_i\left(\sum_{x,y}\tilde P(x)P(y\ |\ x)f_i(x,y) - \sum_{x,y}\tilde P(x,y)f_i(x,y) \right) \end{align}$$

原始优化问题是

$$\min_P\max_\lambda L(P,\lambda)$$

则其对偶问题是

$$\max_\lambda\min_PL(P,\lambda)$$

求 $L$ 对 $P$ 的偏导：

$$\frac{\partial L(P,\lambda)}{\partial P(y\ |\ x)}=\sum_{x,y}\tilde P(x)\left( \log P(y\ |\ x)+1-\lambda_0-\sum_{i=1}^n\lambda_if_i(x,y) \right)$$

在 $\tilde P(x)>0$ 的情况下，解得

$$P(y\ |\ x) = \exp\left(\sum_{i=1}^n\lambda_if_i(x,y)+\lambda_0-1\right)=\frac {\exp\left(\sum_{i=1}^n\lambda_if_i(x,y)\right)} {\exp(1-\lambda_0)}$$

由于 $\sum_yP(y\ |\ x)=1$，得

$$P^*(y\ |\ x)=\frac {1} {Z(x)} \exp\left(\sum_{i=1}^n\lambda_if_i(x,y)\right)$$

$Z(x)$ 为配分函数，

$$Z(x) = \sum_y\exp\left(\sum_{i=1}^n\lambda_if_i(x,y)\right)$$

在 统计学习方法第二版 6.2.4 节 中证明了 $\max_\lambda P^*(y\ |\ x)$ 与最大熵模型的极大似然等价，有兴趣可以看看。

6.2.4 节的最后还提到：二分类的逻辑回归模型为

$$P(Y=1|x)=\frac{\exp(w^Tx)}{1+\exp(w^Tx)}\\ P(Y=0|x)=\frac{1}{1+\exp(w^Tx)}$$

与最大熵模型相近，而学习的方式也是求对数似然估计：

$$\begin{align} \max_w\log J(w)&= \max_w\log h(x)^{\nu(y=1)}(1-h(x))^{\nu(y=0)} \\ &=\max_w\sum_{i=1}^{m}\left [y^{(i)}\log h(x)+(1-y^{(i)})log(1-h(x))\right] \\ \end{align}$$