专栏首页机器学习算法与Python学习机器学习(13)之最大熵模型详解

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

关键字全网搜索最新排名

【机器学习算法】:排名第一

【机器学习】:排名第二

【Python】:排名第三

【算法】:排名第四

前言

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

熵和条件熵

在(机器学习(9)之ID3算法详解及python实现)一文中,我们已经讲到了熵和条件熵的概念,这里我们对它们做一个简单的回顾。

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

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

两个变量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。

用特征函数f(x,y)描述输入x和输出y之间的关系。定义为:

特征函数f(x,y)关于经验分布P¯(X,Y)的期望值,用EP¯(f)表示为: 

特征函数f(x,y)关于条件分布P(Y|X)和经验分布P¯(X)的期望值,用EP(f)表示为:

如果模型可以从训练集中学习,我们就可以假设这两个期望相等。即:

上式就是最大熵模型学习的约束条件,假如我们有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)定义为:

约束条件为:

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

其中wi(i=1,2,...m)为拉格朗日乘子。由于原始问题满足凸优化理论中的KKT条件,因此原始问题的解和对偶问题的解是一致的。这样我们的损失函数的优化变成了拉格朗日对偶问题的优化。min L(P,w)是关于w的函数记为:

ψ(w)即为对偶函数,将其解记为:

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

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

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

小结

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

优点

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

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

缺点

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

参考:

1. 周志华《机器学习》

2. 博客园:作者(刘建平)http://www.cnblogs.com/pinard/p/6093948.html

3. 李航 《统计学习方法》

本文分享自微信公众号 - 机器学习算法与Python学习(guodongwei1991)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-08-25

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【学术】一文教你如何正确利用kNN进行机器学习

    AiTechYun 编辑:xiaoshan k最近邻算法(kNN)是机器学习中最简单的分类方法之一,并且是入门机器学习和分类的好方法。它基本上是通过在训练数据中...

    AiTechYun
  • 《机器学习实战》学习笔记:K-近邻算法入门及实战|万字长文

    作者:崔家华 东北大学|模式识别与智能系统研究生 量子位 已获授权编辑发布 在模式识别领域中,K-近邻算法(KNN算法)是一种用于分类和回归的非参数统计方法。 ...

    量子位
  • 永远在线的人工智能:通用神经形态硬件才是 AI 的未来吗?

    【新智元导读】2012年一项被誉为“最逼真人工大脑”的研究发表在 Science 杂志上,名为 Spaun 的这个系统一时引起许多关注。现在,Spaun 团队使...

    新智元
  • 推荐|机器学习中的模型评价、模型选择和算法选择!

    摘要:模型评估、模型选择和算法选择技术的正确使用在学术性机器学习研究和诸多产业环境中异常关键。 ? 本文回顾了用于解决以上三项任务中任何一个的不同技术,并参考理...

    IT派
  • 【科技】机器学习和大脑成像如何对嘈杂环境中的刺激物进行分类

    AiTechYun 编辑:nanan 学习识别和分类对象是一种基本的认知技能,可以让动物在世界上发挥作用。例如,将另一种动物识别为朋友或敌人,可以决定如何与之互...

    AiTechYun
  • 【学术】优步发布VINE,一个用于神经进化的开源交互式数据可视化工具

    AiTechYun 编辑:yuxiangyu 对于优步的规模来说,机器学习的进步可以显著提高更运输方案的技术,使之更为安全可靠。最近优步人工智能实验室发布了一个...

    AiTechYun
  • 【行业】苹果和IB将通过新的机器学习集成展开合作

    AiTechYun 编辑:nanan ? 周一晚些时候,苹果和IBM宣布扩大现有合作伙伴关系,允许客户通过苹果的Core ML和IBM的Watson(沃森)技术...

    AiTechYun
  • 【学术】一篇关于机器学习中的稀疏矩阵的介绍

    AiTechYun 编辑:Yining 在矩阵中,如果数值为0的元素数目远远多于非0元素的数目,并且非0元素分布无规律时,则称该矩阵为稀疏矩阵;与之相反,若非0...

    AiTechYun
  • TensorFlow产品经理:机器学习如何改变未来十年的软硬件?

    王瀚宸 编译自 South Park Commons博客 量子位 报道 | 公众号 QbitAI 最近,Google Brain员工,TensorFlow产品经...

    量子位
  • Python超过R,成为数据科学和机器学习的最常用语言

    陈桦 编译自 KDnuggets 量子位 报道 | 公众号 QbitAI ? 近期,数据挖掘资讯网站KDnuggets开展了一项调查,问题是“2016年和201...

    量子位

扫码关注云+社区

领取腾讯云代金券