经典分类算法之最大熵模型

已获 深度学习这件小事 授权

作者 刘建平Pinard

zenRRan略有改动

最大熵模型(maximum entropy model, MaxEnt)也是很典型的分类算法了,它和逻辑回归类似,都是属于对数线性分类模型。在损失函数优化的过程中,使用了和支持向量机类似的凸优化技术。而对熵的使用,让我们想起了决策树算法中的ID3和C4.5算法。理解了最大熵模型,对逻辑回归,支持向量机以及决策树算法都会加深理解。本文就对最大熵模型的原理做一个小结。

熵和条件熵的回顾

熵度量了事物的不确定性,越不确定的事物,它的熵就越大。具体的,随机变量X的熵的表达式如下:

其中n代表X的n种不同的离散取值。而pi代表了X取值为i的概率,log为以2或者e为底的对数。

熟悉了一个变量X的熵,很容易推广到多个个变量的联合熵,这里给出两个变量X和Y的联合熵表达式:

有了联合熵,又可以得到条件熵的表达式H(Y|X),条件熵类似于条件概率,它度量了我们的Y在知道X以后剩下的不确定性。表达式如下:

用下面这个图很容易明白他们的关系。左边的椭圆代表H(X),右边的椭圆代表H(Y),中间重合的部分就是我们的互信息或者信息增益I(X,Y), 左边的椭圆去掉重合部分就是H(X|Y),右边的椭圆去掉重合部分就是H(Y|X)。两个椭圆的并就是H(X,Y)。

最大熵模型的定义

最大熵模型假设分类模型是一个条件概率分布P(Y|X),X为特征,Y为输出。

给定一个训练集(x(1),y(1)),(x(2),y(2)),...,(x(m),y(m)),其中x为n维特征向量,y为类别输出。我们的目标就是用最大熵模型选择一个最好的分类类型。

在给定训练集的情况下,我们可以得到总体联合分布P(X,Y)的经验分布P¯(X,Y),和边缘分布P(X)的经验分布P¯(X)。P¯(X,Y)即为训练集中X,Y同时出现的次数除以样本总数m,P¯(X)即为训练集中X出现的次数除以样本总数m。

上式就是最大熵模型学习的约束条件,假如我们有M个特征函数 fi(x,y)(i=1,2...,M)就有M个约束条件。可以理解为我们如果训练集里有m个样本,就有和这m个样本对应的M个约束条件。

这样我们就得到了最大熵模型的定义如下:

假设满足所有约束条件的模型集合为:

定义在条件概率分布P(Y|X)上的条件熵为:

我们的目标是得到使H(P)最大的时候对应的P(y|x),这里可以对H(P)加了个负号求极小值,这样做的目的是为了使−H(P)为凸函数,方便使用凸优化的方法来求极值。

最大熵模型损失函数的优化

在上一节我们已经得到了最大熵模型的函数H(P)。它的损失函数−H(P)定义为:

约束条件为:

由于它是一个凸函数,同时对应的约束条件为仿射函数,根据凸优化理论,这个优化问题可以用拉格朗日函数将其转化为无约束优化函数,此时损失函数对应的拉格朗日函数L(P,w)定义为:

其中wi(i=1,2,...m)为拉格朗日乘子。如果大家也学习过支持向量机,就会发现这里用到的凸优化理论是一样的,接着用到了拉格朗日对偶也一样。

我们的拉格朗日函数,即为凸优化的原始问题:

其对应的拉格朗日对偶问题为:

由于原始问题满足凸优化理论中的KKT条件,因此原始问题的解和对偶问题的解是一致的。这样我们的损失函数的优化变成了拉格朗日对偶问题的优化。

求解对偶问题的第一步就是求

这可以通过求导得到。这样得到的是关于w的函数。记为:

即为对偶函数,将其解记为:

具体的是求L(P,w)关于P(y|x)的偏导数:

令偏导数为0,可以解出P(y|x)关于w的表达式如下:

其中,Zw(x)为规范化因子,定义为:

这样我们就得出了P(y|x)和w的关系,从而可以把对偶函数ψ(w)里面的所有的P(y|x)替换成用w表示,这样对偶函数ψ(w)就是全部用w表示了。接着我们对ψ(w)求极大化,就可以得到极大化时对应的w向量的取值,带入P(y|x)和w的关系式, 从而也可以得到P(y|x)的最终结果。

对ψ(w)求极大化,由于它是连续可导的,所以优化方法有很多种,比如梯度下降法,牛顿法,拟牛顿法都可以。对于最大熵模型还有一种专用的优化方法,叫做改进的迭代尺度法(improved iterative scaling, IIS)。

IIS也是启发式方法,它假设当前的参数向量是w,我们希望找到一个新的参数向量w+δ,使得对偶函数ψ(w)增大。如果能找到这样的方法,就可以重复使用这种方法,直到找到对偶函数的最大值。

IIS使用的方法是找到ψ(w+δ)−ψ(w)的一个下界B(w|δ),通过对B(w|δ)极小化来得到对应的δ的值,进而来迭代求解w。对于B(w|δ),它的极小化是通过对δ求偏导数而得到的。

由于IIS一般只用于最大熵模型,适用范围不广泛,这里就不详述算法过程了,感兴趣的朋友可以直接参考IIS的论文The improved iterative scaling algorithm: A gentle introduction。

最大熵模型小结

最大熵模型在分类方法里算是比较优的模型,但是由于它的约束函数的数目一般来说会随着样本量的增大而增大,导致样本量很大的时候,对偶函数优化求解的迭代过程非常慢,scikit-learn甚至都没有最大熵模型对应的类库。但是理解它仍然很有意义,尤其是它和很多分类方法都有千丝万缕的联系。 

惯例,我们总结下最大熵模型作为分类方法的优缺点:

最大熵模型的优点有:

a) 最大熵统计模型获得的是所有满足约束条件的模型中信息熵极大的模型,作为经典的分类模型时准确率较高。

b) 可以灵活地设置约束条件,通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度

最大熵模型的缺点有:

a) 由于约束函数数量和样本数目有关系,导致迭代过程计算量巨大,实际应用比较难。

IELTS a bit

inhibit vt. 抑制;禁止

reflection n. 反射;沉思;映像

cereal n. 谷类,谷物;谷类食品;谷类植物

adj. 谷类的;谷类制品

scarcity n. 不足;缺乏

ambiguity n. 含糊;不明确;暧昧;模棱两可的话

原文发布于微信公众号 - 深度学习自然语言处理(zenRRan)

原文发表时间:2018-08-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SIGAI学习与实践平台

深入浅出聚类算法

聚类问题是机器学习中无监督学习的典型代表,在数据分析、模式识别的很多实际问题 中得到了应用。在本文中,SIGAI 将为大家深入浅出的介绍聚类问题的定义以及各种典...

21510
来自专栏智能算法

降维方法(一):PCA原理

PCA(Principal Component Analysis)是一种常用的数据分析方法。PCA通过线性变换将原始数据变换为一组各维度线性无关的表示,可用于提...

43090
来自专栏机器学习之旅

理论:正则化-Lasso规约

图中,红色的线存在明显的过拟合,绿色的线才是合理的拟合曲线,为了避免过拟合,我们可以引入正则化。

13320
来自专栏新智元

计算机视觉识别简史:从 AlexNet、ResNet 到 Mask RCNN

【新智元导读】 Medium 用户 Đặng Hà Thế Hiển 制作了一张信息图示,用专业、简洁并且最有吸引力的方式——信息图示,讲述计算机视觉(CV)物...

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

机器学习系列:(九)从感知器到支持向量机

从感知器到支持向量机 上一章我们介绍了感知器。作为一种二元分类器,感知器不能有效的解决线性不可分问题。其实在第二章,线性回归里面已经遇到过类似的问题,当时需要解...

45590
来自专栏小樱的经验随笔

损失函数详解

损失函数(loss function)是用来估量你模型的预测值f(x)与真实值Y的不一致程度,它是一个非负实值函数,通常使用L(Y, f(x))来表示,损失函数...

32820
来自专栏SIGAI学习与实践平台

图像分割技术介绍

图像分割(image segmentation)技术是计算机视觉领域的个重要的研究方向,是图像语义理解的重要一环。图像分割是指将图像分成若干具有相似性质的区域的...

24080
来自专栏SIGAI学习与实践平台

图像分割技术介绍

图像分割(image segmentation)技术是计算机视觉领域的一个重要的研究方向,是图像语义理解的重要一环。图像分割是指将图像分成若干具有相似性质的区域...

43040
来自专栏机器学习算法与Python学习

机器学习(13)之最大熵模型详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 前言 最大熵模型(maximum ...

41170
来自专栏机器学习算法原理与实践

最大熵模型原理小结

   最大熵模型(maximum entropy model, MaxEnt)也是很典型的分类算法了,它和逻辑回归类似,都是属于对数线性分类模型。在损失函数优化...

11110

扫码关注云+社区

领取腾讯云代金券