概率图模型系列（2）：最大熵原理和最大熵模型

本系列虽然讲概率图模型，但是搞明白最大熵模型需要理解熵、最大熵原理、最大熵分布、最小熵原理与最大熵模型（MEM）。最大熵模型也是CRF模型的基础。

最大熵原理

最大熵原理就是说在未知的事情面前，我们选择不确定性最大的那一个。这样做意味着我们不引入任何假设，承认自己除了已经观察到的信息外，对其事情无知。简而言之：自知无知！

反过来想，如果我们不承认无知，而是对其引入假设（假设不是观察信息），如果正确，那对我们建模当然有用，如果错误，只会偏离正确结果更远，那么我们如何保证我们的假设是正确的。这样一来，引入假设反而有风险，既然如此，还不如不做假设，自知无知更好！

例如一颗骰子在面前，对各个点数 $\Omega = {1, 2, 3, 4, 5, 6}$，那么每颗骰子点数出现的概率是多数呢？由于没有更多信息，这里不做任何假设，自知无知。认为每个点数等可能出现是最优的做法。于是有，

$$p(x) = \frac{1}{|\Omega|} = \frac{1}{6}$$

有未知分布$p(x)$​​​，其具体形式和参数都不知道，满足最大熵的模型为，

$$p^{*} = \arg \max_{p \in \mathbb{P}} H[p] = \arg \max_{p \in \mathbb{P}} \Big [-\int_{\Omega} p(x) \log p(x) dx \Big]$$

最大熵模型

熵的最大化可以作为模型选择的一种策略，即在给定（满足）约束条件下，选择熵最大的模型作为目标模型。

一般来说，我们要建立的概率模型是判别模型，即条件概率$p(y|x)$​​，其熵（条件熵）为，

$$\begin{align} H[p(y|x)] &= H[p(x,y)] - H[p(x)] \newline &= -\sum_x\sum_y p(x,y)\log p(y|x) \end{align}$$

考虑到我们已经有观察样本$[x_1, x_2, \dots, x_n]$，即有关于$x$的经验分布$\tilde{p}(x)$，于是上式可以改为，

$$H[p(y|x)] = -\sum_x\sum_y \tilde{p}(x)p(y|x)\log p(y|x)$$

另外，我们从$D = [(x_1,y_1), (x_2,y_2), \dots, (x_n,y_n)]$​中获得某种观察结论，可以表示为，

$$f_{i}(x,y) = \left\{\begin{matrix} 1 & (x,y) \; \text{满足某种观察条件}\\ 0 & \text{otherwise.} \end{matrix}\right.$$

例如情感倾向性分类中，

$$f_{i}(x,y) = \left\{\begin{matrix} 1 & \; \text{y为正向情感，x中包括开心关键词}\\ 0 & \text{otherwise.} \end{matrix}\right.$$

这样的观察结论称为特征，这样的特征可以感觉实际情况自行构造多个$f_1(x,y), f_2(x,y), \dots, f_m(x,y)$​​​。

在已有数据$D$中，这些特征关于经验分布$\tilde{p}(x, y)$​​的期望为，

$$E_{\tilde{p}}(f_i) = \sum_x \sum_y \tilde{p}(x, y) f_i(x, y)$$

同时，这些特征关于分布$p(x, y) = \tilde{p}(x)p(y|x)$​​的期望为，

$$E_{p}(f_i) = \sum_x \sum_y \tilde{p}(x)p(y|x) f_i(x, y)$$

我们要寻找的目标模型$p(y|x)$除了满足熵最大外，还需要满足以上特征函数描述的观察事实，因此还需要满足约束，

$$E_{\tilde{p}}(f_i) - E_{p}(f_i) = 0 ,\; i=1, \dots, m$$

因此有带约束优化问题，

$$\begin{align} \max_{p \in \mathbb{P}} H[p] &=-\sum_x\sum_y \tilde{p}(x)p(y|x)\log p(y|x) \newline \operatorname{s.t.} \; & \begin{cases} E_{\tilde{p}}(f_i) - E_{p}(f_i) = 0 ,\; i=1, \dots, m \newline \newline \displaystyle \sum_y p(y|x) = 1 \end{cases} \end{align}$$

通过拉格朗日函数容易解得，

$$p(y|x) = \frac{1}{Z(x)} \exp\Big[ \sum_{i=1}^{m} \lambda_i f_i(x, y) \Big] \\ Z(x) = \sum_y \exp\Big[ \sum_{i=1}^{m} \lambda_i f_i(x, y) \Big]$$

其中$\lambda_i$是模型参数。

导出逻辑回归

假设有样本$\boldsymbol{x} = [x_1, x_2, \dots, x_n]$，其包括$n$个特征，我们的目标是训练一个而分类模型，

$$P(y|\boldsymbol{x})$$

为此，定义$n$​个约束，每个约束为，

$$f_i(\boldsymbol{x}, y) = \begin{cases} x_i, \quad &y=1 \newline 0, \quad &y=0 \end{cases}$$

于是，根据最大熵原理有，

$$\begin{align} P(y=1|\boldsymbol{x}) &= \frac{\exp\Big[\displaystyle \sum_{i=1}^{m} \lambda_i f_i(x, y) \Big]}{Z} \newline &= \frac{\exp(\boldsymbol{\lambda} \cdot \boldsymbol{x})}{Z} \end{align}$$

类似地，

$$\begin{align} P(y=0|\boldsymbol{x}) &= \frac{\exp\Big[\displaystyle \sum_{i=1}^{m} \lambda_i f_i(x, y) \Big]}{Z} \newline &= \frac{1}{Z} \end{align}$$

而归一化因子，

$$Z(x) = \sum_y \exp\Big[ \sum_{i=1}^{m} \lambda_i f_i(x, y) \Big] = 1 + \exp(\boldsymbol{\lambda} \cdot \boldsymbol{x})$$

于是也就有逻辑回归，

$$\ln \frac{P(y=1| \boldsymbol{x})}{P(y=0| \boldsymbol{x})} = \boldsymbol{\lambda } \cdot \boldsymbol{x}$$

总结

参考

[1] 信息论基础

[2] https://en.wikipedia.org/wiki/Pointwise_mutual_information

[3] https://en.wikipedia.org/wiki/Min-entropy