最大熵模型

在真实的语言环境里，某一观测值对应的隐藏状态有上下文环境（观测、状态）决定，引入特征函数可使我们能够自由地选取特征（观测或状态的组合）。可以说是用特征（观测组合）来代替观测，避免生成模型HMM、朴素贝叶斯的观测独立性假设的局限性。

最大熵模型（maximum entropy model）由最大熵原理推导实现。

1. 最大熵原理

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

假设离散随机变量\(X\)的概率分布是\(P(X)\)，则其熵为 \[H(P) = - \sum_{\pmb{x}} P(\pmb{x}) \log P(\pmb{x})\] 熵满足下列不等式： \[0 \leqslant H(P) \leqslant \log |X|\] 式中，\(|X|\)是\(X\)的取值个数，当且仅当\(X\)的分布是均匀分布时右边的等号成立。即当\(X\)服从均匀分布时，熵最大。

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

2. 最大熵模型的定义

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

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

给定一个训练数据集 \[T = \{(\pmb{x}_1, y_1), (\pmb{x}_2, y_2), \cdots, (\pmb{x}_N, y_N)\}\] 学习的目标是用最大熵原理选择最好的分类模型。

首先考虑模型应该满足的条件。给定训练数据集，可以确定联合分布\(P(X,Y)\)的经验分布和边缘分布\(P(X)\)的经验分布，分别以\(\tilde{P}(X,Y)\)和\(\tilde{P}(X)\)表示： \[\begin{align} \tilde{P}(X = \pmb{x},Y = y) &= \frac{v(X = \pmb{x}, Y = y)}{N} \nonumber \\ \tilde{P}(X = \pmb{x}) &= \frac{v(X = \pmb{x})}{N} \nonumber \end{align}\]

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

用特征函数\(f(\pmb{x},y)\)描述输入\(\pmb{x}\)和输出\(y\)之间的某一个事实。其定义为 \[f(\pmb{x}, y) = \begin{cases} 1,\quad \pmb{x}与y满足某一事实 \\ 0, \quad 否则 \end{cases}\] 上式为一个二值函数（一般地，特征函数可以使任意实值函数），当\(\pmb{x}\)和\(y\)满足这个事实时取值为1，否则取值为0。

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

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

如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值相等，即 \[E_P(f) = E_{\tilde{P}} (f)\] 或 \[\sum_{\pmb{x},y} \tilde{P} (\pmb{x}) P(y|\pmb{x}) f(\pmb{x},y) = \sum_{\pmb{x},y} \tilde{P} (\pmb{x}, y) f(\pmb{x},y)\] 这里将上式作为模型学习的约束条件。假如有\(n\)个特征函数\(f_i(\pmb{x},y), i=1,2,\cdots,n\)，那么就有\(n\)个约束条件。

最大熵模型：假设满足所有约束条件的模型集合为 \[C \equiv \{ P \in \mathscr{P} | E_P (f_i) = E_{\tilde{P}} (f_i), \quad i=1,2,\cdots,n \}\] 定义在条件概率分布\(P(Y|X)\)上的条件熵为 \[H(P) = - \sum_{\pmb{x},y} \tilde{P} (\pmb{x}) P(y|\pmb{x}) \log P(y | \pmb{x})\] 则模型集合\(\mathscr{C}\)中条件熵\(H(P)\)最大的模型称为最大熵模型，式中的对数为自然对数。

3. 最大熵模型的学习

最大熵模型的训练包括两个基本任务：

特征选择：选择一个能表达随机过程统计特征的特征集合；
模型选择：即模型估计或参数估计，为每个入选的特征估计权重\(w_i\)。

3.1. 特征选择

在所有的特征中，选择最具有代表性的特征，构造约束集合。

特征选取算法：

增量式特征选取算法：每一步用贪心的规则，挑选当前能使熵减少最多的特征；
基于频数阈值的特征选择方法：当某个特征出现的次数大于一定的值时才将其加入。

3.2. 模型选择

最大熵模型的模型选择就是模型学习的过程，也就是求解最大熵模型的过程。最大熵模型的学习可以形式化为约束最优化问题。

对于给定的训练数据集\(T = \{(\pmb{x}_1,y_1), (\pmb{x}_2,y_2), \cdots, (\pmb{x}_N, y_N)\}\)以及特征函数\(f_i(\pmb{x},y),i=1,2,\cdots, n\)，最大熵模型的学习等价于约束最优化问题： \[\begin{align} & \max_{P \in C} \quad H(P) = - \sum_{\pmb{x},y} \tilde{P}(\pmb{x}) P(y|\pmb{x}) \log P(y|\pmb{x}) \nonumber \\ & s.t. \quad E_P (f_i) = E_{\tilde{P}} (f_i), \quad i=1,2,\cdots,n \nonumber \\ & \qquad \quad \sum_{y} P(y | \pmb{x}) = 1 \nonumber \end{align}\]

按照最优化问题的习惯，将最大值问题改写为等价的最小值问题： \[\begin{align} & \min_{P \in C} \quad -H(P) = \sum_{\pmb{x},y} \tilde{P}(\pmb{x}) P(y|\pmb{x}) \log P(y|\pmb{x}) \nonumber \\ & s.t. \quad E_P (f_i) - E_{\tilde{P}} (f_i) = 0, \quad i=1,2,\cdots,n \nonumber \\ & \qquad \quad \sum_{y} P(y | \pmb{x}) = 1 \nonumber \end{align}\]

将约束最优化的原始问题转换为无约束最优化的对偶问题。

首先，引进拉格朗日乘子\(w_0,w_1,w_2,\cdots,w_n\)，定义拉格朗日函数\(L(P,\pmb{w})\)： \[\begin{align} L(P,\pmb{w}) & \equiv - H(P) + w_0 \left( 1 - \sum_y P(y|\pmb{x}) \right) + \sum_{i=1}^n w_i (E_{\tilde{P}}(f_i) - E_P(f_i)) \nonumber \\ & = \sum_{\pmb{x},y} \tilde{P}(\pmb{x}) P(y|\pmb{x}) \log P(y|\pmb{x}) + w_0 \left( 1 - \sum_y P(y | \pmb{x}) \right) \nonumber \\ & \quad + \sum_{i=1}^n w_i \left( \sum_{\pmb{x},y} \tilde{P} (\pmb{x}, y) f_i(\pmb{x},y) - \sum_{\pmb{x},y} \tilde{P} (\pmb{x}) P(y | \pmb{x}) f_i (\pmb{x},y) \right) \nonumber \end{align}\]

最优化的原始问题是： \[\min_{P \in C} \max_{\pmb{w}} L(P,\pmb{w})\]

对偶问题是 \[\max_{\pmb{x}} \min_{P \in C} L(P,\pmb{w})\]

拉格朗日函数\(L(P,\pmb{w})\)是\(P\)的凸函数，原始问题的解与对偶问题的解是等价的。

\(\min_{P \in C} L(P,\pmb{w})\)是\(\pmb{w}\)的函数，记作 \[\Psi (\pmb{w}) = \min_{P \in C} L(P , \pmb{w}) = L(P_{\pmb{w}}, \pmb{w})\] \(\Psi (\pmb{w})\)称为对偶函数，同时，将其解记为 \[P_{\pmb{w}} = \mathop{\arg \min}_{P \in C} L(P,\pmb{w}) = P_{\pmb{w}} (y | \pmb{x})\]

求\(L(P,\pmb{w})\)对\(P(y|\pmb{x})\)的偏导数 \[\begin{align} \frac{\partial L(P,\pmb{w})}{\partial L(y | \pmb{x})} &= \sum_{\pmb{x},y} \tilde{P} (\pmb{x}) (\log P(Y | \pmb{x}) + 1) - \sum_y w_0 - \sum_{\pmb{x},y} \left( \tilde{P} (\pmb{x}) \sum_{i=1}^n w_i f_i (\pmb{x},y) \right) \nonumber \\ & = \sum_{\pmb{x},y} \tilde{P} (\pmb{x}) \left( \log P(Y | \pmb{x}) + 1 - w_0 - \sum_{i=1}^n w_i f_i(\pmb{x},y) \right) \nonumber \end{align}\]

令偏导数为0，在\(\tilde{P}(\pmb{x}) > 0\)的情况下，解得 \[P(y | \pmb{x}) = \exp \left( \sum_{i=1}^n w_i f_i(\pmb{x},y) + w_0 - 1 \right) = \frac{\exp ( \sum_{i=1}^n w_i f_i (\pmb{x},y) )}{\exp (1 - w_0)}\] 由于\(\sum_y P(y | \pmb{x}) = 1\)，得 \[P_{\pmb{w}} (y | \pmb{x}) = \frac{1}{Z_{\pmb{w}}} \exp \left( \sum_{i=1}^n w_i f_i(\pmb{x},y) \right)\] 其中 \[Z_{\pmb{w}} (\pmb{x}) = \sum_y \exp (\sum_{i=1}^n w_i f_i (\pmb{x},y))\] \(Z_{\pmb{w}}\)称为规范化因子；\(f_i(\pmb{x},y)\)是特征函数；\(w_i\)是特征的权值。由上述两个公式表示的模型\(P_{\pmb{w}} = P_{\pmb{w}} (y|\pmb{x})\)就是最大熵模型，\(\pmb{w}\)是最大熵模型中的参数变量。

之后，求解对偶问题外部的极大化问题 \[\max_{\pmb{w}} \Psi (\pmb{w})\] 将其解记为\(\pmb{w}^*\)，即 \[\pmb{w}^* = \mathop{\arg \max}_{\pmb{w}} \Psi(\pmb{w})\] 这里应用最优化算法求对对偶函数\(\Psi(\pmb{w})\)的极大化，得到\(\pmb{w}^*\)，用来表示\(P^* \in C\)。这里，\(P^* = P_{\pmb{w}^*} = P_{\pmb{w}^*}(y | \pmb{x})\)是学习到的最优模型（最大熵模型），最大熵模型的学习归结为对偶函数\(\Psi(\pmb{w})\)的极大化。

求解参数\(\pmb{w}\)的最优化算法：

通用迭代尺度算法（Generalized Iterative Scaling, GIS）
改进的迭代尺度算法（Improved Iterative Scaling, IIS）
SCGIS算法

4. 相关

最大熵模型的应用：词性标注、短语识别、指代消解、语法分析、机器翻译、文本分类、问题回答、语言模型……

开源工具包：

OpenNLP:http://incubator.apache.org/opennlp/
张乐:http://homepages.inf.ed.ac.uk/lzhang10/maxent.html
Malouf:http://tadm.sourceforge.net/
Tsujii:http://www-tsujii.is.s.u-tokyo.ac.jp/~tsuruoka/maxent/

最大熵模型的优点：

可以把众多复杂的因素综合考虑到一个模型中，在金融（股票、期货）等领域有较好的表现；
建模时，用户只需集中精力选择特征，而不需要花费精力考虑如何使用这些特征；
特征选择灵活，且不需要额外的独立假设或者内在约束；
模型可移植性强，可应用于不同的领域；
可结合更丰富的信息。

最大熵模型的缺点：

时空开销大；
数据稀疏性问题严重；
对语料库的依赖性较强。