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

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

首发于微信公众号：机器学习与统计学

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 220,367评论 6赞 512
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,959评论 3赞 396
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 166,750评论 0赞 357
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 59,226评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 68,252评论 6赞 397
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,975评论 1赞 308
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,592评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,497评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 46,027评论 1赞 319
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 38,147评论 3赞 340
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,274评论 1赞 352
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,953评论 5赞 347
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,623评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,143评论 0赞 23
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,260评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,607评论 3赞 375
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,271评论 2赞 358

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

推荐阅读更多精彩内容