文档章节

100天搞定机器学习|Day55 最大熵模型

字数 2562
阅读 29
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

1、熵的定义

熵最早是一个物理学概念,由克劳修斯于1854年提出,它是描述事物无序性的参数,跟热力学第二定律的宏观方向性有关:在不加外力的情况下,总是往混乱状态改变。熵增是宇宙的基本定律,自然的有序状态会自发的逐步变为混沌状态。 1948年,香农将熵的概念引申到信道通信的过程中,从而开创了”信息论“这门学科。香农用“信息熵”来描述随机变量的不确定程度,也即信息量的数学期望。 关于信息熵、条件熵、联合熵、互信息、相对熵、交叉熵请点击蓝字直达

2、最大熵模型 这里引用吴军博士《数学之美》中关于最大熵的论述

最大熵原理指出,当我们需要对一个随机事件的概率分布进行预测时,我们的预测应当满足全部已知的条件,而对未知的情况不要做任何主观假设。在这种情况下,概率分布最均匀,预测的风险最小。因为这时概率分布的信息熵最大,所以人们称这种模型叫“最大熵模型”

理解最大熵原理,最简单的例子就是掷色子,当我们对这个色子一无所知时,我们一般会假定它每面朝上的概率是均等的,即各点出现的概率均为 1/6。这就保留了最大的不确定性,也就是说让熵达到最大。当我们假定这个色子是韦小宝的,六点朝上的概率是 1/2,这样其他面朝上的概率是多少呢?在无其他信息情况下,其他面朝上的概率均为 1/10. 在满足已知条件前提下,如果没有更多的信息,则那些不确定部分都是“等可能的”。而等可能性通过熵最大化来刻画。最大熵模型要解决的问题就是已知 X,计算 Y 的概率,且尽可能让 Y 的概率最大。

由此,就可以引出最大熵模型的定义:

最大熵模型假设分类模型是一个条件概率分布$P(Y|X)$,X 为特征,Y 为输出。 给定一个训练集${(x^{(1)},y^{(1)}), (x^{(2)},y^{(2)}), ... ,(x^{(m)},y^{(m)})}$,其中 x 为n维特征向量,y 为类别输出。我们的目标就是用最大熵模型选择一个最好的分类类型。 在给定训练集的情况下,我们可以得到总体联合分布$P(X,Y)$的经验分布$\overline{P}(X,Y)$,和边缘分布$P(X)$的经验分布$\overline{P}(X)$。$\overline{P}(X,Y)$即为训练集中 X,Y 同时出现的次数除以样本总数 m,$\overline{P}(X)$即为训练集中 X 出现的次数除以样本总数 m。 用特征函数$f(x,y)$描述输入 x 和输出 y 之间的关系。定义为:

$$ f(x,y)=<br />\begin{cases}<br />1& {x与y满足某个关系}\<br />0& {否则}\end{cases} $$

可以认为只要出现在训练集中出现的$(x^{(i)},y^{(i)})$,其$f(x^{(i)},y^{(i)}) = 1$. 同一个训练样本可以有多个约束特征函数。 特征函数$f(x,y)$关于经验分布$\overline{P}(X,Y)$的期望值,用$E_{\overline{P}}(f)$表示为:  $$ E_{\overline{P}}(f) = \sum\limits_{x,y}\overline{P}(x,y)f(x,y) $$    特征函数$f(x,y)$关于条件分布$P(Y|X)$和经验分布$\overline{P}(X)$的期望值,用$E_{P}(f)$表示为: $$ E_{P}(f) = \sum\limits_{x,y}\overline{P}(x)P(y|x)f(x,y) $$ 如果模型可以从训练集中学习,我们就可以假设这两个期望相等。即: $$ E_{\overline{P}}(f) = E_{P}(f) $$ 上式就是最大熵模型学习的约束条件,假如我们有 M 个特征函数$f_i(x,y) (i=1,2...,M)$就有 M 个约束条件。可以理解为我们如果训练集里有 m 个样本,就有和这 m 个样本对应的 M 个约束条件。 这样我们就得到了最大熵模型的定义如下: 假设满足所有约束条件的模型集合为: $$E_{\overline{P}}(f_i) = E_{P}(f_i) (i=1,2,...M)$$ 定义在条件概率分布$P(Y|X)$上的条件熵为: $$ H(P) = -\sum\limits_{x,y}\overline{P}(x)P(y|x)logP(y|x) $$ 我们的目标是得到使$H(P)$最大的时候对应的$P(y|x)$,这里可以对$H(P)$加了个负号求极小值,这样做的目的是为了使$-H(P)$为凸函数,方便使用凸优化的方法来求极值。

最大熵模型的学习

最大熵模型的学习等价于约束最优化问题:

$$ \begin{eqnarray} \max\limits_{P\in\mathcal{C}}& H(P)=-\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\nonumber \ 4 E_P(f_k)=E_\tilde{P}(f_k),k=1,2,\cdots,K\nonumber \ && \sum_yP(y|x)=1\nonumber \end{eqnarray} $$

对应的最小化问题为:

$$ \begin{eqnarray} &\min\limits_{P\in\mathcal{C}}& -H(P)=\sum_{x,y}\tilde{P}(x)P(y|x)\log P(y|x)\nonumber \ &s.t.& E_P(f_k)-E_\tilde{P}(f_k)=0,k=1,2,\cdots,K\nonumber \ && \sum_yP(y|x)=1\nonumber \end{eqnarray} $$

引入拉格朗日乘子$\beta_0,\beta_1,\cdots,\beta_K$,定义拉格朗日函数$L(P,\beta)$

$$ \begin{eqnarray} L(P,\beta)&=& -H(P)+\beta_0(1-\sum_yP(y|x))+\sum_{k=1}^K\beta_k(E_\tilde{P}(f_i)-E_P(f_i)) \nonumber\ &=&\sum{x,y}\tilde{P}(x)P(y|x)\log P(y|x)+\beta_0(1-\sum_yP(y|x))\nonumber\ &+&\sum_{k=1}^K\beta_k(\sum\limits{x,y}\tilde{P}(x,y)f(x,y)-\sum\limits_{x,y}\tilde{P}(x)P(y|x)f(x,y))\nonumber \end{eqnarray} $$

将其解记作: $P_\beta=\arg\min\limits_{P\in\mathcal{C}}L(P,\beta)=P_\beta(y|x)$

求$L(P,β)$对$P(y|x)$的偏导数为 0

$$ \begin{eqnarray} \frac{\partial L(P,\beta)}{\partial P(y|x)}&=&\sum_{x,y}\tilde{P}(x)(\log P(y|x)+1)-\sum_y\beta_0-\sum_{x,y}(\tilde{P}(x)\sum_{k=1}^K\beta_kf_k(x,y)) \nonumber\ &=&\sum_{x,y}\tilde{P}(x)\Big{(}\log P(y|x)+1-\beta_0-\sum_{k=1}^K\beta_kf_k(x,y)\Big{)}\nonumber\ &=&0\nonumber \end{eqnarray} $$

得:

$$ P(y|x)=\exp(\sum\limits_{k=1}^K\beta_kf_k(x,y)+\beta_0-1)=\frac{\exp(\sum\limits_{k=1}^K\beta_kf_k(x,y))}{\exp(1-\beta_0)} $$

由$\sum_yP(y|x)=1$ 所以

$$ P_\beta(y|x)=\frac{1}{Z_\beta(x)}\exp(\sum\limits_{k=1}^K\beta_k f_k(x,y)) $$

其中$Z_\beta(x)=\sum\limits_y\exp(\sum\limits_{k=1}^K\beta_k f_k(x,y))$

当选定合适的特征函数时,最大熵模型可以导出多项逻辑模型,这个很显然。但二者并不等价,最大熵可以选择其他特征函数。 当选定合适的特征函数时,最大熵模型可以导出多项逻辑模型,这个很显然。但二者并不等价,最大熵可以选择其他特征函数。 记对偶函数为$\Psi(\beta)=\min\limits_{P\in\mathcal{C}}L(P,\beta)=L(P_\beta,\beta)$,接下来最大化$\Psi(\beta)$得到其解$\beta^*$.则最大熵模型为:

$$ P^=P_{\beta^}(y|x) $$

可证明,对偶函数等价于条件概率分布$P(Y|X)$的对数似然函数

$$ L_\tilde{P}(P_\beta)=\sum\limits_{x,y}\tilde{P}(x,y)\log P(y|x) $$

则最大熵模型的学习中的对偶函数极大化等价于最大熵模型的极大似然估计。

3.2 模型对比 最大熵模型与LR模型的关系: 最大熵模型和 LR 模型都属于对数线性模型,LR 及最大熵模型学习一般采用极大似然估计,或正则化的极大似然估计。LR 及最大熵模型学习可以形式化为无约束最优化问题,求解时有改进的迭代尺度法、梯度下降法、拟牛顿法。 逻辑回归跟最大熵模型没有本质区别。逻辑回归是最大熵对应类别为二类时的特殊情况,也就是当逻辑回归类别扩展到多类别时,就是最大熵模型。

最大熵模型与决策树模型的关系: 最大熵原理选取熵最大的模型,而决策树的划分目标选取熵最小的划分。原因在于:

最大熵原理认为在满足已知条件之后,选择不确定性最大(即:不确定的部分是等可能的)的模型。也就是不应该再施加任何额外的约束。因此这是一个求最大不确定性的过程,所以选择熵最大的模型。

决策树的划分目标是为了通过不断的划分从而不断的降低实例所属的类的不确定性,最终给实例一个合适的分类。因此这是一个不确定性不断减小的过程,所以选取熵最小的划分。

3.4 关于最大熵和朴素贝叶斯的联系 最大熵和朴素贝叶斯的联系 两者都使用了P(y|x),区别在于朴素贝叶斯使用先验概率求解,最大熵利用最大化条件熵求解。

朴素贝叶斯倾向于从基本信息中提取新的信息,而最大熵将提取信息的程度进行了量化(就好像强迫自己获得概率一定是要均匀分布一样)。

最大熵模型的 Python 实现

这里就不再贴代码,网上有许多优秀的博主已经共享过了,这里推荐大家看一下 SmirkCao https://github.com/SmirkCao/Lihang

一个具体的案例是 Dod-o 用最大熵模型来做手写数字识别,正确率 96.9%,运行时长:8.8h https://github.com/Dod-o/Statistical-Learning-Method_Code

参考文献: 李航《统计学习方法》6.2 最大熵模型 https://www.cnblogs.com/pinard/p/6093948.html https://www.cnblogs.com/ooon/p/5677098.html https://blog.csdn.net/ltc844139730/article/details/92011520 http://www.huaxiaozhuan.com/统计学习/chapters/14_maxent.html

首发于微信公众号:机器学习与统计学 欢迎扫码关注,领取海量资料

© 著作权归作者所有

机器学习算法与Python实战
粉丝 1
博文 20
码字总数 27528
作品 0
武汉
程序员
私信 提问
100天搞定机器学习|Day11 实现KNN

机器学习100天|Day1数据预处理 100天搞定机器学习|Day2简单线性回归分析 100天搞定机器学习|Day3多元线性回归 100天搞定机器学习|Day4-6 逻辑回归 100天搞定机器学习|Day7 K-NN 100天搞定机器...

jpld
07/10
0
0
《统计学习方法》笔记(五)逻辑斯蒂回归与最大熵模型

LR回归(Logistic Regression) LR回归,虽然这个算法从名字上来看,是回归算法,但其实际上是一个分类算法。在机器学习算法中,有几十种分类器,LR回归是其中最常用的一个。 LR回归是在线性...

ch1209498273
2018/05/23
0
0
火爆GitHub:100天搞定机器学习编程(超赞信息图+代码+数据集)

你是想喝一辈子糖水,还是想用AI改变世界? 但怎么想是一回事,怎么做往往是另一回事。学习和健身一样,不少人都停留在口头上,有各种借口不曾付诸实施。 为此,YouTube网红Siraj Raval发起了...

技术小能手
2018/08/08
0
0
最大熵模型与GIS ,IIS算法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/55003910 最大熵模型与GIS ,IIS算法 前言 在学习最大熵模型时,令我最大的困惑点...

Demon的黑与白
2017/02/12
0
0
从马尔科夫到最大熵到条件随机场

马尔科夫模型 对于某个系统包含了n个有限状态,某个状态随着时刻推移而转移到另一个状态。如果t时刻状态与前面m个时刻相关则称为m阶马尔科夫链,即马尔可夫过程是一个随机过程,系统从一个状...

超人汪小建
05/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

学习记录 互联网项目---3(Ribben优化)

3.3 负载均衡策略 {服务名称}.ribbon.NFLoadBalancerRuleClassName=具体策略 service:#服务名 ribbon: NFLoadBalancerRuleClassName : com.netflix.loadbalancer.RandomRule ......

Pole丶逐
31分钟前
3
0
redis - 的线程模型

redis 的线程模型 redis 内部使用文件事件处理器 file event handler,这个文件事件处理器是单线程的,所以 redis 才叫做单线程的模型。它采用 IO 多路复用机制同时监听多个 socket,根据 so...

Canaan_
32分钟前
7
0
IT兄弟连 HTML5教程 使用盒子模型的浮动布局

虽然使用绝对定位可以实现页面布局,但由于调整某个盒子模型时其他盒子模型的位置并不会跟着改变,所以并不是布局的首选方式。而使用浮动的盒子模型可以向左或向右移动,直到它的外边缘碰到包...

老码农的一亩三分地
32分钟前
3
0
ubuntu上编译和使用easy_profiler对C++程序进行性能分析

本文首发于个人博客https://kezunlin.me/post/91b7cf13/,欢迎阅读最新内容! tutorial to compile and use esay profiler with c++ on ubuntu 16.04 <!--more--> Guide compile git clone h......

kezunlin
54分钟前
5
0
nginx master-worker进程工作原理

nginx的master-worker进程模型是其能够高性能的处理用户请求的原因之一,而且这里的每个worker进程都只会启动一个线程来处理用户请求。通常我们会将worker进程的数量设置得与我们的CPU数量一...

爱宝贝丶
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部