最大熵模型

1. 简介

最大熵模型由最大熵原理推导实现。

2. 最大熵原理

最大熵原理是概率模型学习的一个原则。最大熵原理认为，学习概率模型时，在所有可能的概率模型中，熵最大的模型是最好的模型。通常用约束条件来确定概率模型的集合，因此最大熵原理也可以表述为在满足约束条件的模型集合中选取熵最大的模型。

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

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

熵满足下列不等式：

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

式中， $|X|$ 是 $X$ 的取值个数，当且仅当 $X$ 的分布是均匀分布时右边的等号成立。

直观上来看，最大熵原理认为要选择的概率模型首先必须满足已有事实，即约束条件。在没有更多信息的情况下，那些不确实的部分都是「等可能的」。最大熵原理通过熵的最大化来表示等可能性。

3. 最大熵模型

假设分类模型是一个条件概率分布 $P(Y | X)$ ， $X \in \mathcal{X} \subseteq \mathbf{R}^n$ 表示输入， $Y \in \mathcal{Y}$ 表示输出， $\mathcal{X}$ 和 $\mathcal{Y}$ 分别是输入和输出的集合。这个模型表示的是对于给定的输入 $X$ ，以条件概率 $P(Y | X)$ 输出 $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)$ 表示：

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

其中， $\nu(X = x, Y = y)$ 表示训练数据中样本 $(x, y)$ 出现的频数， $\nu(X = x)$ 表示训练数据中输入 $x$ 出现的频数， $N$ 表示训练样本容量。

用特征函数 $f(x, y)$ 描述输入 $x$ 和输出 $y$ 之间的某一个事实，其定义是

$f(x, y) = \begin{cases} 1, x \text{ 与 } y \text{ 满足某一事实 } \\ 0, \text{否则} \end{cases}$

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

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

特征函数 $f(x, y)$ 关于模型 $P(Y | X)$ 与经验分布 $\tilde{P}(X)$ 的期望值，用 $E_P(f)$ 表示：

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

如果模型能够获取到训练数据中的信息，那么就可以假设这两个期望值相等，即 $E_{P}(f) = E_{\tilde{P}}(f)$ 。

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

$C \equiv \{ P \in \mathcal{P} | E_P (f_i) = E_{\tilde{P}} (f_i), i = 1,2,\cdots,n \}$

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

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

则模型集合 $\mathcal{C}$ 中条件熵 $H(P)$ 最大的模型称为最大熵模型。
模型学习：最大熵模型的学习可以形式化为约束最优化问题。对于给定训练数据集 $T = \{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$ ，以及特征函数 $f_i(x, y), i=1,2,\cdots,n$ ，最大熵模型的学习等价于约束最优化问题：

$\begin{aligned} \max_{P \in \mathbf{C}} \qquad& H(P) = -\sum_{x,y} \tilde{P}(x) P(y | x) \log{P(y | x)} \\ \mathrm{s.t.} \qquad& E_P(f_i) = E_{\tilde{P}}(f_i), i=1,2,\cdots,n \\ & \sum_y P(y | x) = 1 \end{aligned}$

可以使用拉格朗日乘子法求解该问题的对偶问题。最后求得的最大熵模型为：

$P_w(y | x) = \frac{1}{Z_w(x)} \exp{\left( \sum_{i=1}^n w_i f_i(x, y) \right)} \\ Z_w(x) = \sum_{y} \exp{\left( \sum_{i=1}^n w_i f_i(x, y) \right)}$

其中， $Z_w(x)$ 称为规范化因子， $f_i(x, y)$ 是特征函数， $w_i$ 是特征函数的权值。然后，便可使用极大似然估计估计模型参数，上述最大熵模型的对数似函数如下：

$L_{\tilde{P}}(P_w) = \log{\prod_{x,y} P(y | x)^{\tilde{P}(x, y)}} = \sum_{x, y} \tilde{P}(x, y) \log P(y | x)$

最后再使用梯度下降法或拟牛顿法进行求解。