【Method】最大熵模型

原理

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

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

\[H(P) = -\sum_x P(x)logP(x)\]

熵满足下列不等式：

\[0 \leq H(P) \leq log \mid X \mid\]

式中，\(\mid X \mid\)是X的取值个数，当且仅当X的分布是均匀分布时右边的等号成立。这就是说，当X服从均匀分布时，熵最大。

直观地，最大熵原理认为要选择的概率模型首先必须满足已有的事实，即约束条件。在没有更多信息的情况下，那些不确定的部分都是“等可能的”。最大熵原理通过熵的最大化来表示等可能性。“等可能”不容易操作，而熵则是一个可优化的数值指标。

最大熵原理是统计学习的一般原理，将它应用到分类得到最大熵模型。

假设分类模型是一个条件概率分布\(P(Y \mid X), X \in X \subseteq R^n\)表示输入，\(Y \in Y\)表示输出，X和Y分别是输入和输出的集合。这个模型表示的是对于给定的输入X，以条件概率\(P(Y \mid X)\)输出Y。

给定一个训练数据集

\[T = {(x_1, y_1), (x_2, y_2),...,(x_N,y_N)}\]

学习的目标是用最大熵原理选择最好的分类模型。

首先考虑模型应该满足的条件。给定训练数据集，可以确定联合分布P(X,Y)的经验分布和边缘分布P(X)的经验分布，分别以\(\tilde{P}(X,Y)\)和\(\tilde{P}(X)\)表示，这里

\[\tilde{P}(X=x, Y=y) = \frac{v(X=x, Y=y)}{N}\] \[\tilde{P}(X=x) = \frac{v(X=x)}{N}\]

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

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

\[f(x)=\left\{ \begin{aligned} 1 & , & x与y满足某一事实 \\ 0 & , & 否则 \\ \end{aligned} \right.\]

它是一个二值函数，当x和y满足这个事实时取值为1，否则取值为0.

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

\[E_{\hat{P}}(f) = \sum_{x,y} \tilde{P}(x,y)f(x,y)\]

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

\[E_P(f) = \sum_{x,y} \tilde{P}(x)P(y \mid x)f(x,y)\]

如果模型能够获得训练数据中的信息，那么就可以假设这两个期望值相等，即