最大熵原则

英文名：Principle of Maximum Entropy

最大熵模型是一种统计建模技术

如果对熵不了解，请查看熵(Entropy)与信息量详细介绍——统计机器学习核心概念
如果对统计建模不了解，请查看统计建模(Statistical Modeling)——统计机器学习建模介绍

对于上述例子，在没有任何语料支持的情况下，可以使用熵最大的均匀分布，即

p(介词) = p(动词) = p(量词) = p(名词) = 1/4

这就是所谓的最大熵原则

最大熵原则描述

• 熵描述了随机变量的不确定性
• 熵值越大表明该随机变量的不确定性越大, 该随机变量也就越接近均匀分布
• 在只掌握关于未知分布的部分知识时，应该选取符合这些知识但熵值最大的概率分布。

为什么用最大熵原则

• 按照最大熵原则进行统计建模，是人们可以作出的唯一不偏不倚的选择
• 任何其它的选择都意味着人们增加了额外的约束和假设
• 这些约束和假设根据人们掌握的信息是无法作出的。

基于最大熵原则构建的统计模型称为最大熵模型

利用最大熵原则进行统计建模的方法称为最大熵方法

最大熵模型

对于上述词性标注的例子，“把”的词性是一个集合 Y ={介词，动词，量词，名词}
统计建模后一定会输出一个 $y \in Y$， y 表示建模后得到的“把”的词性
输出 y 的过程中，可能受上下文信息的影响，我们把这个语境因素定义为 x, x 形成的集合为 X

X 表示句子出现在“把”周围的所有词汇

我们需要构建一个模型，该模型的任务是在给定上下文 x 的情况下，输出 y 的概率 $p(y|x)$

经验分布函数

为了得到模型，需要收集大量的语料样本 {$(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n}, y_{n})$}

但无论怎样，都只能收集一定数量的样本

我们引入一个新的经验分布函数 $\tilde{p}$ 来表示训练样本

$$\tilde{p}(x, y) = \frac{c(x,y)}{N}$$

特征函数

除了经验分布函数以及一些约束条件外，还可以考虑上下文依赖信息，这个信息叫做特征

• 通过特征表示样本数据中的已知知识。
• 特征可以定义为如下的二值函数： $f:X \times Y \rightarrow \{0,1\}$

该特征刻画了 x 与 y 之间的某种共现关系

• 若这种共现关系成立，则 $(x_{i}, y_{i}) = 1$
• 若这种共现关系不成立，则 $(x_{i}, y_{i}) = 0$

特征实际上是关于(x,y)的一个二值函数

*对于上述词性标注的例子，我们可以定义一个函数 $f(x,y)$.
x："一"出现在“把”之前
y：量词
则 $f(x,y)=1$，表示这两个条件共现*

特征函数的期望

特征 f 关于经验分布$\tilde{p}(x,y)$, 在训练样本中出现的期望(观察值)为：

$$E_{\tilde{p}}f = \sum_{x \in X, y \in Y} \tilde{p}(x,y)f(x,y), \qquad \tilde{p}(x, y) = \frac{c(x,y)}{N}$$

最大熵方法

方法描述

存在样本数据 O = { $(x_{1}, y_{1}),(x_{2}, y_{2}), ..., (x_{n}, y_{n})$ }， $x_{i} \in X, y_{i} \in Y$

求解模型分布 $P(x, y)$, 该分布应该满足下面两个条件

• $P(x, y)$ 是能最大化熵 H(p) 的概率分布，即

$$p^* = arg \max_{p} H(p)$$

• $P(x, y)$ 服从已知的样本分布

约束条件

特征 $f(x, y)$ 的模型期望可表示为

$$E_{p}f = \sum_{x \in X, y \in Y} p(x,y)f(x,y)$$

最大熵方法认为，为了使模型分布符合样本中的统计，特征的模型期望应该与特征的观察期望值一致

$$E_{p}f = E_{\tilde{p}}f$$

若共有k个特征， 则

$$E_{p}f_{j} = E_{\tilde{p}}f_{j}, \qquad 1 \leq j \leq k$$

• 通过约束使特征的模型期望与观察期望保持一致，从而保证得到模型分布符合样本数据的已知分布
• 满足所有约束条件的分布通常不止一个。若用 P 表示所有满足特征约束条件的分布，则

P = { $p | E_{p}f_{j} = E_{\tilde{p}}f_{j}, \quad 1 \leq j \leq k$ }

求解最大熵模型就成为一个约束最优化问题。

约束最优化

所有的约束条件如下

• 最大熵约束

$$p^{*} = \underset{p \in P}{\mathrm{argmax}} H(p), \qquad H(p) = -\sum_{x \in X, y \in Y}p(x,y)\log p(x,y)$$

• 特征的模型期望应该与特征的观察期望值一致

$$E_{p}f_{j} = E_{\tilde{p}}f_{j}, \qquad 1 \leq j \leq k$$

• 概率和为1

$$\sum_{x \in X, y \in Y}p(x, y) = 1$$

运用拉格朗日乘数法，构建拉格朗日函数

$$L(p, \wedge, \alpha) = H(p) + \sum_{j}\lambda_{j}(E_{p}f_{j}-E_{\tilde{p}f_{j}}) + \alpha(\sum_{x \in X,y \in Y}p(x,y)-1), \quad \wedge = (\lambda_{1}, \lambda_{2},..., \lambda_{k})$$

拉格朗日函数针对 p 求微分，并令其为 0，有

$$p(x,y) = \frac{1}{Z}exp(\sum_{i}\lambda_{i}f_{i}(x,y))$$

特征 $f_{i}$ 对分布的影响通过拉格朗日乘数 $\lambda_{i}$ 来体现
Z 是归一常数

$$Z=\sum_{x \in X,y \in Y}exp(\sum_{i}\lambda_{i}f_{i}(x,y))$$

上述分布即为符合最大熵原则的概率分布形式

最大熵模型是一种对数线性模型，其中指数部分表述为特征的一种线性加权组合

最大熵模型总结

最大熵方法的优点

• 利用最大熵方法进行统计建模时，只需根据具体的要求选择特征，无需花费精力考虑如何使用这些特
• 选择特征可以很灵活，无需考虑特征之间是否独
• 特征的类型和特征的数量都可以随时进行调整
• 利用最大熵建模，参数平滑甚至可以通过特征选择的方式加以考虑，每个特征对概率分布的贡献由参数 $\lambda_{i}$ 决定

特征选择策略

对于样本数据，可以设计出成千上万的特征，并非所有特征的样本期望值都是可靠的，很多特征的样本期望值带有偶然性，与特征的真实期望并不一致，引入这样的特征无益于统计建模工作，所以需要有特征选择策略

• 设置一个频率阈值，某特征只有在训练样本中的频率大于频率阈值 ，才会被包括在最终的特征集合中
• 采用特征选择算法，从所有特征集合 F 中选择对建模有益的特征 S 评价准则，好的特征集能引起样本数据的概率值增大

模型训练方法

可以采用数值最优化算法，两种考虑方式

• 以样本数据的熵值最大化作为优化目标
• 以样本数据的概率值最大化作为优化目标进行最大似然估计

二者训练结果是一致的, 即

$$p^{*} = \underset{p \in P}{\mathrm{argmax}} H(p) = \underset{q \in Q}{\mathrm{argmax}} L(q)$$

目前提出的用于训练最大熵模型的算法有(迭代)

• GIS 算法 (Generalized Iterative Scaling)
• IIS算法 (Improved Iterative Scaling)[收敛速度快]
• 梯度下降法、拟牛顿法等最优化算法也可用于训练最大熵模型，例如L-BFGS算法。