专栏首页人工智能机器学习教程:最大熵文本分类器

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

在本教程中,我们将讨论最大熵文本分类器,也称为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 条评论
登录 后参与评论

相关文章

  • 构建基于JAVA的朴素贝叶斯文本分类器

    在前面的文章中,我们讨论了朴素贝叶斯文本分类器的理论背景以及在文本分类中使用特征选择技术的重要性。在本文中,我们将结合两种方法,用JAVA简单实现朴素贝叶斯文本...

    人工智能资讯小编
  • 机器学习教程:朴素贝叶斯文本分类器

    在本教程中,我们将讨论朴素贝叶斯文本分类器。朴素贝叶斯是最简单的分类器之一,只涉及简单的数学表达,并且可以使用PHP,C#,JAVA等语言进行编程。

    人工智能资讯小编
  • 基于神经网络的图像压缩技术

    (本文由软件工程师 Nick Johnston 和 David Minnen 发布)

    人工智能资讯小编
  • 机器学习中如何处理不平衡数据?

    假设老板让你创建一个模型——基于可用的各种测量手段来预测产品是否有缺陷。你使用自己喜欢的分类器在数据上进行训练后,准确率达到了 96.2%!

    机器之心
  • 手把手教你用PyTorch实现图像分类器(第一部分)

    经过几个月富有挑战性但是受益良多的学习,我最近从Udacity的Python Nanodegree program AI编程专业毕业。最后一个项目是用PyTor...

    AI研习社
  • 机器学习-使用TF.learn识别手写的数字图像

    我们今天要解决的问题是从MNIST数据集中分类手写数字,并且写一个简单的分类器,被认为是计算机视觉的Hello World。现在MNIST是一个多类别的分类问题...

    亚乐记
  • 脑机接口EEG信号分类算法

    人工智能的发展也给脑机接口技术带来了很广阔的空间,目前限制脑机接口技术的走出实验室的主要原因是脑电信号的因人而异性,在线脑机接口的信号传输率,准确率等。下面对目...

    脑机接口社区
  • 机器学习两大利器:Boosting 与 AdaBoost

    最近, 技术在 Kaggle 竞赛以及其它预测分析任务中大行其道。本文将尽可能详细地介绍有关 Boosting 和 的相关概念。

    小小詹同学
  • 机器学习入门(四) — 分类模型1 分类-分析情感2 从主题预测情感:智能餐厅评价系统3 分类器应用4 线性分类器5 决策边界6 训练和评估分类器7 什么是好的精度

    JavaEdge
  • 【机器学习】--Adaboost从初始到应用

    AdaBoost算法和GBDT(Gradient Boost Decision Tree,梯度提升决策树)算法是基于Boosting思想的机器学习算法。在Boo...

    LhWorld哥陪你聊算法

扫码关注云+社区

领取腾讯云代金券