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

在本教程中,我们将讨论最大熵文本分类器,也称为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上分享。

本文的版权归 用户1191492 所有,如需转载请联系作者。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT派

PyTorch实例:用ResNet进行交通标志分类

【导读】本文是机器学习工程师Pavel Surmenok撰写的一篇技术博客,用Pytorch实现ResNet网络,并用德国交通标志识别基准数据集进行实验。文中分...

2.6K00
来自专栏AI研习社

用 TensorFlow 让你的机器人唱首原创给你听

AI 研习社按:这篇文章会用一个简单的模型在 TensorFlow 上来实现一个音频生成器,GitHub 代码链接详见文末“阅读原文”。原文作者杨熹,载于作者的...

35590
来自专栏算法channel

@all: 新浪 机器学习算法岗 面试实录

二面面试官来了。是个算法大佬。是个专门做算法的。直接手出题,他说时间不多,就让我说思路。

19220
来自专栏机器之心

教程 | 从超参数到架构,一文简述模型优化策略

模型可以在训练过程中通过修正超参数而逐步建立。这在迁移学习中最为常见,在这种环境中,我们试图将现有模型的知识应用到新领域或新任务中。这是持续学习中更常见的问题,...

9630
来自专栏小鹏的专栏

深度学习这些坑你都遇到过吗?

原文地址:My Neural Network isn't working! What should I do? 如果你的神经网络不工作,该怎么办?本文作者列举...

21350
来自专栏PPV课数据科学社区

如何选择Microsoft Azure机器学习算法

编者按:机器学习的算法很多,如何选择一直是初学者的一个痛点。本文给出了机器学习算法选择的方法和实例,不仅适用于Microsoft Azure框架,同样可以应用于...

53160
来自专栏企鹅号快讯

深度学习的这些坑你都遇到过吗?神经网络11大常见陷阱及应对方法

如果你的神经网络不工作,该怎么办?本文作者列举了搭建神经网络时可能遇到的11个常见问题,包括预处理数据、正则化、学习率、激活函数、网络权重设置等,并提供解决方法...

43870
来自专栏目标检测和深度学习

CVPR2018 | CMU&谷歌Spotlight论文:超越卷积的视觉推理框架

选自arXiv 作者:陈鑫磊等 机器之心编译 参与:张倩、李泽南 人类在看到图像时可以进行合理的推理与预测,而目前的神经网络系统却还难以做到。近日,来自卡耐基梅...

30860
来自专栏目标检测和深度学习

深度学习之基础网络演进、分类与定位的权衡|牛喀技研

深度学习,目标检测,图像,智能驾驶 编译:牛喀网-钱伟 前言 本篇关注基础网络架构的演进和处理分类、定位这一矛盾问题上的进展。 基础网络结构的演进 基础网络(...

92970
来自专栏AI研习社

CNN+TensorFlow 就能教机器人作曲!

今天想来看看 AI 是怎样作曲的。 本文会用 TensorFlow 来写一个音乐生成器。 当你对一个机器人说:我想要一种能够表达出希望和奇迹的歌曲时,发生了什么...

49170

扫码关注云+社区

领取腾讯云代金券