机器学习教程：最大熵文本分类器

在本教程中，我们将讨论最大熵文本分类器，也称为MaxEnt分类器。最大熵分类器是自然语言处理，语音和信息检索问题中常用的判别分类器。使用像JAVA，C++或PHP这样的标准编程语言实现最大熵分类器都可以，但是，为了估计模型的权重，必需解决数值优化问题。

更新：Datumbox机器学习框架现在是开源的，可以免费下载。查看包com.datumbox.framework.machinelearning.classification以查看Java中Max Entropy Classifier的实现。

请注意，最大熵分类器对于不少文本分类问题（例如情感分析）表现得非常好，它也是我们常用的机器学习API之一。

什么是最大熵分类器？

最大熵分类器是属于指数模型类的概率分类器。不像我们在前面的文章中讨论过的朴素贝叶斯分类器，最大熵并不假定这些特征是有条件地相互独立的。MaxEnt基于最大熵原理，并从适合我们训练数据的所有模型中选择具有最大熵的模型。最大熵分类器可以用来解决大量的文本分类问题，如语言检测，主题分类，情感分析等。

何时使用MaxEnt文本分类器？

由于最大熵分类器所做的最小假设，当我们对先前的分布没有任何了解以及做出的假设是不安全的时候，我们通常使用它。此外，当我们不能假定特征间的条件独立性时，使用最大熵分类器。文本分类问题十分符合这样的特点，其特征通常是显然不相互独立的单词。和朴素贝叶斯相比，最大熵需要更多的时间来训练，主要是为了解决估计模型的参数优化问题。然而，解决了这个问题之后，该方法可以提供可靠的结果，并且在CPU和内存占用方面具有竞争力。

最大熵的理论背景

我们的目标是使用文档的上下文信息（一元文法，二元文法，或其他文本特征），以便将其分类到给定的类别（正面/中性/负面，客观/主观等）。按照自然语言处理和信息检索中常用的标准词袋框架，令{w_1,...,w_m}为文档中出现的m个词。然后每个文档由一个稀疏数组表示，用1和0表示一个特定的单词w_i是否存在于文档的上下文中。这个方法是由Bo Pang和Lillian Lee（2002）提出的。

我们的另一个目标是构建一个随机模型，如Adam Berger（1996）所描述的那样，准确地表示随机过程的行为：以文档的上下文信息x为输入，产生输出值y。和朴素贝叶斯的情况一样，构建这个模型的第一步是收集大量的训练数据，这些训练数据由以下格式表示的样本组成：(x_i,y_i)，其中x_i包括文档（稀疏数组）的上下文信息，而y_i是包含这些信息的类。第二步是根据经验概率分布来概括训练样本：

\begin{equation} \tilde p(x,y)\equiv\frac {1}{N}\times在样本中(x,y)出现的次数 \end{equation} [1]

其中N是训练数据集的大小。

我们将使用上述经验概率分布来构建随机过程的统计模型，该过程根据其上下文信息将文本分配给特定类别。我们模型的构建块将是来自我们的训练数据集（即经验概率分布）的一组统计量。

我们介绍下面的指标功能：

\begin{equation*} f_j(x,y)= \left\{ \begin{array}{rl} 1 & \text{如果}y=c_i并且x包含w_k\\ 0 & \text{其他} \end{array} \right. \end{equation*} [2]

我们称上述指标功能为“特征”。仅当特定文档的类是c_i且文档包含单词w_k时，该二进制值指示符函数才返回1 。

我们将训练数据集的所有统计量表示为适当的二值指示函数f_j的期望值。因此特征fj相对于经验分布的期望值\tilde p (x,y)\等于：

\tilde p(f_j)\equiv\sum\tilde p(x,y)f_j(x,y) [3]

如果每个训练样本(x,y)在训练数据集中出现一次，则\tilde p (x,y) 等于1/N。

当一个特定的统计量对我们的分类有用时，我们要求我们的模型符合这个统计量。为此，我们将限制模型赋予特征函数f_j的期望值的期望值。特征f_j相对于该模型的期望值p(y|x)等于：

p(f_j)\equiv\sum_{x,y}\tilde p(x)p(y|x)f_j(x,y) [4]

其中\tilde p(x)是训练数据集中x的经验分布，通常设为1/N。

通过限制期望值等于经验值，并从方程[3]，[4]中我们得到：

\sum_{x,y}\tilde p(x)p(y|x)f_j(x,y)=\sum_{x,y}\tilde p(x,y)f_j(x,y) [5]

等式[5]称为约束，而我们的约束和特征函数数目一样，都是j个。

有无数的模型可以满足上述约束。所以为了建立我们的模型，我们需要根据一个特定的标准选择最好的候选模型。根据最大熵原理，我们应该选择尽可能接近均匀的模型。换句话说，我们应该选择具有最大熵的模型p^*

p^*={arg\ max}_{peC}\Bigl(-\sum_{x,y}\tilde p(x)p(y|x)log\ p(y|x)\Bigl) [6]

给定：

1. p(y|x)≥0对所有x,y都成立 [7]
2. \sum_yp(y|x)=1对所有x都成立 [8]
3. \sum_{x,y}\tilde p(x)p(y|x)f_j(x,y)=\sum_{x,y}\tilde p(x,y)f_j(x,y)对所有j\in\{1,2,\dots,n\}都成立 [9]

为了解决上面所说的优化问题，我们引入拉格朗日乘数，并专注于无约束双重问题，而且用最大似然法估计lamda自由变量\{\lambda_1,\dots,\lambda_n\}。

可以证明，如果我们找到了\{\lambda_1,\dots,\lambda_n\}，最大限度提高了偶问题的参数，给出一个文件X被归类为y的概率等于：

p^*(y|x)=\frac {exp\big(\sum_i\lambda_if_i(x,y)\big)}{\sum_yexp\big(\sum_i\lambda_if_i(x,y)\big)} [10]

考虑到我们已经找到了我们模型的lamda参数，所以，为了对新文档进行分类，我们所需要做的就是使用“最大后验”决策规则，并选择出现概率最高的类别。

估计lamda参数需要使用迭代缩放算法，如GIS（通用迭代算法）或IIS（改进的迭代尺度法）。

估计Lamda参数\\\quad\text输入：特征函数f_1,f_2,\dots,f_n；经验分布\tilde p(x,y)\\\quad输出：最优参数值\Lambda_i^*；最优模型p^*\\1.从\lambda_i=0开始，其中i\in\{1,2,\dots,n\}\\2.对所有i\in\{1,2,\dots,n\}:\\\quad a.让\Delta\lambda_i是\\\qquad\sum_{x,y}\tilde p(x)p(y|x)f_i(x,y)exp\Bigl(\Delta\lambda_if^\#(x,y)\Bigl)=\tilde p(f_i)\\\quad当f^\#(x,y)\equiv\sum_{i=1}^{n}f_i(x,y)时\\\quad b.由\lambda_i\leftarrow\lambda_i+\Delta\lambda_i重新得到\lambda_i的值\\3.如果不是所有的\lambda_i都收敛，回到步骤2

f^\#(x,y)是对特定的(x,y)对有效的特征总数。如果这个数字对于所有文档都是恒定的，那么\Delta \lambda_i可以用数学形式来计算：

\Delta\lambda_i=\frac{1}{C}log\frac{\tilde p(f_i)}{p(f_i)} ，当C=f^\#(x,y) 时[11]

在实践中，很难满足f=(x,y)一直不变。为了解决这个问题，IIS的某些版本提出了一个“松弛”指示器功能，帮助保持有效特征的数量不变。不幸的是，引入这样的功能大大增加了训练时间。而幸运的是，如Goodman（2002）和Ratnaparkhi（1997）所证明的那样，指标函数的总和受f^\#(x,y) 所限制，而不一定等于它。因此，我们可以选择C作为我们的训练数据集中，所有(x,y)对的有效特征的最大数目：

C=C_{max}={arg\ max}_{x,y}\ f^\#(x,y) [16]

采取上面的措施，我们可以在IIS（改进的迭代缩放）的标准版本上找到{\lambda_1，...，\lambda_n }参数，并以较快的速度构建我们的模型。

正如我们在之前的文章“ 中性类在情感分析中的重要性 ”中所讨论的那样，当我们在情感分析和包含中性类时使用最大熵分类器，它几乎无法胜任。如果您想查看一些最大熵的应用程序，请查看我们的情感分析或主观性分析API。要使用我们的API只需注册一个免费帐户，并从您的个人信息页面获取您的API密钥。

你喜欢这篇文章吗？请花点时间在Twitter上分享。