《统计学习方法》第 6 章“最大熵模型”学习笔记

用于分类问题

最大熵模型用于分类问题，其基本假设是：在满足约束条件的情况下，条件熵最大的模型就是最好的模型。正如一个著名的投资理念“鸡蛋不要放在一个篮子里”。

目标函数是条件熵，我们希望它最大，即条件概率的期望最大。

已知信息成为目标函数的约束，是客观存在的，必须得到满足。其它不作任何假设，越随机越合理。有多少个特征函数，就有多少个约束，再加上条件概率之和为 $1$ 。

认识条件熵

条件熵是熵的期望，它度量了我们的 $Y$ 在知道了 $X$ 以后的不确定性，条件熵定义的最原始形式是：

$H(Y|X)=\sum_{x\in X} p(x)H(Y|X=x)$

或者写成：

$H(Y|X)=\sum_{i=1}^{n} p(x_i)H(Y|X=x_i)$

条件熵表示在已知随机变量 $X$ 的条件下， $Y$ 的条件概率分布的熵对随机变量 $X$ 的数学期望。熵是数学期望（信息量的数学期望），条件熵也是数学期望，是数学期望的数学期望，有点拗口，不妨把定义多看几遍，就清楚了。

这里又假设随机变量 $Y$ 有 $m$ 个取值，将 $H(Y|X=x_i)$ 用定义式
$H(Y|X=x_i) = - \sum_{j=1}^{m} p(y_j|X=x_i)\log p(y_j|X=x_i)$

代入上式，得

$\begin{eqnarray} H(Y|X) &=& \sum_{i=1}^{n} p(x_i)H(Y|X=x_i) \\ &=& \sum_{i=1}^{n} p(x_i)\left(- \sum_{j=1}^{m} p(y_j|X=x_i) \log p(y_j|X=x_i)\right) \\ &=& -\sum_{i=1}^{n}p(x_i) \sum_{j=1}^{m} p(y_j|x_i) \log p(y_j|x_i) \end{eqnarray}$

即
$H(Y|X)=\sum_{i=1}^{n} p(x_i)H(Y|X=x_i) =-\sum_{i=1}^{n}p(x_i) \sum_{j=1}^{m} p(y_j|x_i) \log p(y_j|x_i)$

条件熵即按一个新的变量的每个值对原变量进行分类，比如《统计学习方法》中将是否同意贷款按照申请人是否有自己的房子分为两类。然后在每一个小类里面，都计算熵，然后每一个熵乘以各个类别的概率，然后求和（加权求和）。我们用另一个变量对原变量分类后，原变量的不确定性就会减小了，因为新增了 $Y$ 的信息，不确定程度减少了多少就是信息的增益。

经验条件熵如何计算： $H(D|A)$ 。

$\begin{equation}\begin{split} H(D|A) &= -\sum_{i,k}p(D_k,A_i)\log p(D_k,A_i) \\ &= -\sum_{i,k}p(A_i)p(D_k|A_i)\log p(D_k,A_i)【这一步把 p(D_k|A_i) 化开】\\ &= -\sum_{i=1}^{n}\sum_{k=1}^{K} p(A_i)p(D_k,A_i) \log p(D_k,A_i) \\ &= -\sum_{i=1}^{n} p(A_i) \sum_{k=1}^{K} p(D_k|A_i) \log p(D_k|A_i) \\ &= -\sum_{i=1}^{n} \frac{|D_i|}{|D|}\sum_{k=1}^{K} \frac{|D_{ik}|}{|D_i|} \log \frac{|D_{ik}|}{|D_i|} \end{split}\end{equation}$

决策树中条件熵和最大熵原理中的条件熵

决策树中特征选择，希望条件熵越小越好，这样信息增益就大，此时我们是在选最佳特征，是在已知特征中找最能把类标分清楚的特征。

在最大熵原理中，我们希望选择的模型“越平均越好”，选择的是概率模型，即在未知的概率模型中，选择一个除了满足已知信息以外，不做任何其它假设的概率模型，我们希望条件熵最大。

理解特征函数

输入 $x$ 和输出 $y$ 之间的关系，使用特征函数 $f(x, y)$ 来表示，可以想象 $x$ 取某个值的时候， $y$ 就有一个值与之对应，它描述的是输入变量和输出变量的关系，用特征函数来刻画：

$f(x,y)=\begin{cases} 1, & x 与 y 满足某一事实 \\ 0, & 否则 \\ \end{cases}$

特征函数是把自变量和因变量的关系都考虑进去的函数。可以在皮果提的文章：最大熵学习笔记（三）最大熵模型中找到具体的例子，理解特征函数的定义。

还可以参考这篇知乎问答：如何理解最大熵模型里面的特征？。

image.png

公式推导

1、计算两个经验分布，所谓经验分布，就是从训练数据集中统计出来的频率值。只要是经验分布，我们在表示概率的时候，都在上面加上“一弯”进行区别。从训练数据集可以得到：

（1）联合分布 $P(Y|X)$ 的经验分布：
$\widetilde P(X=x,Y=y) = \frac{v(X=x,Y=y)}{N}$

（2）边缘分布 $P(X)$ 的经验分布：
$\widetilde P(X=x) = \frac{v(X=x)}{N}$

其中 $v(X=x,Y=y)$ 表示训练样本中 $(x,y)$ 出现的频数； $v(X=x)$ 表示训练数据集中输入 $x$ 出现的频数， $N$ 表示训练样本容量。

2、通过这两个经验分布，建立与特征函数和目标函数的等式，形成约束条件。因为 $P(x,y)$ 未知，但是可以用 $\widetilde P(x,y)$ 代替，而 $P(y|x)$ 为所求，又有 $P(x,y)=P(x)P(y|x)$ ， $P(x)$ 也未知，但是可以用 $\widetilde P(x)$ 代替，于是就有：

（1）特征函数 $f(x,y)$ 关于经验分布（训练数据集的分布） $\widetilde P(X,Y)$ 的期望值：
$E_{\widetilde P}(f) = \sum_{x,y}\widetilde P(x,y)f(x,y)$

（2）特征函数 $f(x,y)$ 关于模型 $P(Y|X)$ 与经验分布 $\widetilde P(X)$ 的期望值：

$E_{P}(f) =\sum_{x,y} \widetilde P(x)P(y|x)f(x,y)$

如果模型能够获取从训练数据集中的信息，那么就可以假设这两个期望值相等。

$E_{P}(f) = E_{\widetilde P}(f)$

即：
$\sum_{x,y} \widetilde P(x)P(y|x)f(x,y) = \sum_{x,y}\widetilde P(x,y)f(x,y)$

上面的两个等式作为条件概率的最大熵的约束条件。如果有 $n$ 个特征函数，那么就有 $n$ 个约束条件。

于是最大熵模型就可以表示成：
1、目标函数：条件熵，最优化的方向是使其最大。

2、约束条件：
（1）有多少个特征函数，就有多少个约束条件。
（2）条件概率之和为 1。

3、有约束的最大化问题可以使用拉格朗日乘子法。
引入拉格朗日乘子，写出拉格朗日函数。接下来的步骤和 SVM 是一样的。
利用拉格朗日对偶性，求解对偶问题。即：原始问题是 $\min_p \max_w$ 的，对偶问题是 $\max_w \min_p$ 的。

最大熵模型的学习可以归结为对偶函数的极大化问题。对偶函数的极大化等价于最大熵模型的极大似然估计。

总结：
$\sum_{x,y}\widetilde P(x,y)f(x,y) = \sum_{x,y}P(x,y)f(x,y)$
左边 $E_{\widetilde P}(f) = \sum_{x,y}\widetilde P(x,y)f(x,y)$ 表示特征函数 $f(x,y)$ 在训练数据集上关于经验分布 $\widetilde P(x,y)$ 的数学期望；

右边 $E_{P}(f) =\sum_{x,y}P(x,y)f(x,y)$ 表示特征函数 $f(x,y)$ 在模型上关于理论分布 $P(x,y)$ 的数学期望。

下面是我的手写笔记：

最大熵模型手写笔记-1

最大熵模型手写笔记-2

最大熵模型手写笔记-3

最大熵模型的优点

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

最大熵模型的优点有：

1、最大熵统计模型获得的是所有满足约束条件的模型中条件熵极大的模型，作为经典的分类模型时准确率较高；

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

最大熵模型的缺点

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

参考资料

[1] 李航. 统计学习方法（第 2 版）第 6 章“最大熵模型”. 北京：清华大学出版社，2019.

[2] 吴军. 数学之美（第 20 章“不要把鸡蛋放到一个篮子里”）. 北京：人民邮电出版社，2012.

[3]皮果提的系列文章：
最大熵学习笔记（零）目录和引言
 最大熵学习笔记（一）预备知识
 最大熵学习笔记（二）最大熵原理
 最大熵学习笔记（三）最大熵模型
 最大熵学习笔记（四）模型求解
 最大熵学习笔记（五）最优化算法
 最大熵学习笔记（六）优缺点分析

以下为草稿，我自己留着备用，读者可以忽略，欢迎大家批评指正。

参考资料

函数 $y = x - 1$ 与 $y = ln(x)$ 的图像：

image.png

1、温暖的蛋壳：最大熵模型
地址：http://47.96.227.134/index.php/2018/06/17/maxentropy/
说明：这篇文章指出了：最大熵模型是一种很抽象的描述，在不同的场景和业务中我们可能需要定义不同的特征函数求出对应的权重值，来解决不同的问题。

2、码农场：逻辑斯谛回归与最大熵模型
地址：http://www.hankcs.com/ml/the-logistic-regression-and-the-maximum-entropy-model.html

3、统计学习方法|最大熵原理剖析及实现
地址：https://www.pkudodo.com/2018/12/05/1-7/

4、白马负金羁：最大熵模型（MaxEnt）：万法归宗（上）

最大熵模型（MaxEnt）：万法归宗（下）

5、李航·统计学习方法笔记·第6章 logistic regression与最大熵模型（2）·最大熵模型

6、马同学：如何理解拉格朗日乘子法？

7、自然语言处理之一：最大熵模型

https://blog.csdn.net/chjjunking/article/details/6452051

8、李航统计学习－最大熵模型之我的理解

https://blog.csdn.net/szq34_2008/article/details/79186664

9、最大熵原理

https://blog.csdn.net/longshenlmj/article/details/8697472

10、最大熵与逻辑回归的等价性

https://blog.csdn.net/buring_/article/details/43342341

12、统计学习-逻辑回归(LR)和最大熵模型

https://blog.csdn.net/u013207865/article/details/52728137

13、机器学习——最大熵原理

https://blog.csdn.net/u012654283/article/details/45505711

14、最大熵模型与GIS ，IIS算法

https://blog.csdn.net/u014688145/article/details/55003910

15、机器学习笔记（二十）——求解最大熵模型

https://blog.csdn.net/chunyun0716/article/details/53574630

在机器学习中， $P$ 往往用来表示样本的真实分布，比如 $[1,0,0]$ 表示当前样本属于第一类。 $Q$ 用来表示模型所预测的分布，比如 $[0.7,0.2,0.1]$ 。即 $P$ 表示真实类别的独热编码， $Q$ 表示预测的概率分布。

16、机器学习笔记（十九）——最大熵原理和模型定义

https://blog.csdn.net/chunyun0716/article/details/53365968

17、一步一步理解最大熵模型

https://www.cnblogs.com/wxquare/p/5858008.html

18、李航·统计学习方法笔记·第6章 logistic regression与最大熵模型（2）·最大熵模型

https://blog.csdn.net/tina_ttl/article/details/53542004

（本节完）

最后编辑于：2019.05.17 16:08:45

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

《统计学习方法》第 6 章“最大熵模型”学习笔记

用于分类问题

认识条件熵

决策树中条件熵和最大熵原理中的条件熵

理解特征函数

公式推导

最大熵模型的优点

最大熵模型的缺点

参考资料

参考资料

推荐阅读更多精彩内容