machine-learning-notes
  • 封面
  • 目录
  • 前言
  • 个人前言
  • 机器学习前言
    • 什么是机器学习和模式识别
    • 机器学习的应用
    • 机器学习的流程
    • 不同的机器学习算法对相同数据预测效果不同
    • 快速入门机器学习
    • 机器学习需要参考哪些书
    • 机器学习的学习路径
    • 深度学习的学习路径
    • 互联网机器学习特定岗位所需技能
  • 机器学习面试
  • 数学基础
  • 微积分
    • 泰勒展开
    • e的直观认识
    • 傅里叶变换
    • 希尔伯特空间
  • 线性代数
    • 范数
    • 矩阵求导
    • 特征值
    • 奇异值分解
  • 概率与信息论
    • 综述概率论基本定义
    • 概率论与贝叶斯先验
    • 正态分布
    • 贝叶斯概率
    • 概率符号说明
    • 共轭先验
    • 信息论
  • 数值计算与优化
    • 最小二乘法
    • 等式约束的拉格朗日乘子法
    • 凸优化
      • 凸集和凸函数
      • 凸优化问题
  • 梯度下降算法
    • 随机梯度下降SGD
    • 动量法Momentum
    • 牛顿动量Nesterov
    • AdaGrad
    • RMSprop
    • Adadelta
    • Adam
    • Nadam
    • AMSGrad
    • AdasMax
  • 概率图模型
    • 概率图模型概论
    • 概率图简介
  • 编程基础
  • linux
    • linux常用命令
    • shell
      • 输入输出重定向
  • python
    • python简介
    • python语法
      • 基础语法
      • 数据结构
      • 过程控制
      • 函数
      • 类和对象
      • 文件操作
      • 正则表达式
    • python库
      • numpy
      • pandas
      • scipy
      • matplotlib
      • scikit-learn
    • python应用
      • 排序算法
  • 数据结构与算法
    • 数据结构
    • 算法思想
      • 排序
        • 堆排序
        • 归并排序
        • 快速排序
      • 递归
    • 剑指offer
      • 链表
      • 二叉树
      • 数组
      • 字符串
      • 栈和队列
      • 递归
      • 动态规划
      • 其他
    • leetcode
    • 编程语言
      • c++
  • Hadoop
    • Hadoop简介
    • MapReduce
  • Hive
  • Spark
  • TensorFlow
    • TensorFlow1.0
      • TensorFlow基础
      • TensorFlow基础概念解析
      • TensorFlow机器学习基础
      • Tensorflow分布式架构
    • TensorFlow2.0
  • PyTorch
  • 机器学习
  • 机器学习概论
  • 特征工程
  • 感知机
  • k近邻
  • 朴素贝叶斯
  • 线性模型
    • 最大熵模型
    • 指数族分布与广义线性模型
    • 线性回归
      • Ridge回归(岭回归)
      • Lasso回归
    • Logistic回归-对数几率回归
  • 决策树
  • 支持向量机
    • 线性可分支持向量机与硬间隔最大化
    • 线性支持向量机与软间隔最大化
    • 非线性支持向量机与核函数
    • 序列最小最优化算法SMO
    • SVM总结
  • 集成学习
    • Bagging
      • 随机森林
    • Boosting
      • AdaBoost
      • GradientBoosting
        • GBDT
        • XGBoost
          • XGBoost理论
          • XGBoost实践
    • Stacking
  • 降维
    • PCA主成分分析
    • 流形学习
  • EM算法
  • HMM隐马尔科夫模型
  • CRF条件随机场
  • 聚类
    • k均值聚类
    • 高斯混合模型
  • 主题模型
    • LDA隐狄利克雷分布
  • 知识点
    • 损失函数
    • 负采样
  • 机器学习算法总结
  • 深度学习
  • 深度学习概论
  • ANN人工神经网络
  • 知识点
    • Batch Normalization
  • CNN卷积神经网络
  • 深度学习优化算法
  • RNN循环神经网络
  • LSTM长短期记忆网络
  • GRU门控循环单元
  • GNN图神经网络
    • GNN图神经网络综述
    • GCN图卷积网络
      • GCN图卷积网络初步理解
      • GCN图卷积网络的numpy简单实现
      • GCN图卷积网络本质理解
      • GCN图卷积网络全面理解
      • SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS ICLR2017
  • 神经网络架构搜索
    • Weight-Agnostic-Neural-Networks Google2019
  • 强化学习
  • 强化学习概论
  • 马尔科夫决策过程
  • 动态规划
  • 无模型方法一:蒙特卡洛
  • 无模型方法二:时间差分
  • 无模型方法三:多步自举
  • 函数近似和深度网络
  • 策略梯度算法
  • 深度强化学习
  • 基于模型的强化学习
  • 强化学习前景
  • 自然语言处理
  • 自然语言处理概论
  • 自然语言
  • 语言模型和中文分词
  • word2vec
    • word2vec概述
    • word2vec算法原理
    • word2vec源码分析
    • word2vec实践
  • Seq2Seq模型和Attention机制
  • Self-Attention和Transformer
  • 知识图谱
  • 推荐系统
  • 推荐系统概论
  • 基础知识
  • 进阶知识
    • 机器学习
      • Factorization Machines ICDM2010
    • embedding
      • Network Embedding
        • LINE: Large-scale Information Network Embedding
    • 深度学习
      • DeepFM: A Factorization-Machine based Neural Network for CTR Prediction 2017
      • DSSM: Learning Deep Structured Semantic Models for Web Search using Clickthrough Data CIKM2013
    • 图卷积网络
      • Graph Convolutional Neural Networks for Web-Scale Recommender Systems KDD2018
    • 强化学习
      • DRN基于深度强化学习的新闻推荐模型
  • 业界应用
    • YouTube
      • Deep Neural Networks for YouTube Recommendations RecSys2016
    • Alibaba
      • Learning Tree-based Deep Model for Recommender Systems KDD2018
      • Deep Interest Network for Click-Through Rate Prediction KDD2018
      • DSIN:Deep Session Interest Network for Click-Through Rate Prediction IJCAI2019
Powered by GitBook
On this page
  • 信息论
  • 什么是信息
  • 自信息
  • 信息熵
  • 信息熵的定义
  • 信息熵的直观理解
  • 交叉熵与相对熵(KL散度)
  • 交叉熵
  • 相对熵(KL散度)
  • 条件熵、联和熵与互信息
  • 条件熵
  • 联和熵
  • 互信息(信息增益)
  • 各种熵之间关系的文氏图
  • 参考资料

Was this helpful?

  1. 概率与信息论

信息论

Previous共轭先验Next数值计算与优化

Last updated 5 years ago

Was this helpful?

信息论

信息论是应用数学的一个分支,主要研究的是对一个信号包含信息的多少进行量化。

概率论使我们能够提出不确定的声明,以及在不确定性存在的情况下进行推理,而信息论使我们能够量化概率分布中的不确定性总量。(《深度学习》Goodfellow第34页)

什么是信息

信息是我们一直在谈论的东西,但信息这个概念本身依然比较抽象。在百度百科中的定义:信息,泛指人类社会传播的一切内容,指音讯、消息、通信系统传输和处理的对象。

信息是不确定性的消除。比如我告诉你明天太阳会从东边升起,这没什么信息含量,因为并没有消除任何不确定性,太阳肯定会从东边升起。但是你告诉我应该抽奖抽哪张能赢头等奖500万,那这个信息量就很大了,消除了非常大的不确定性,或者说,随机抽奖,能中500万的概率是千万分之一,也就是概率很小,不确定性很大,但是你告诉了我这个信息,能够让这个概率很小的事情发生,那就是消除了很大的不确定性,所以这个信息就很大。再进一步说,你告诉了能中奖的那张奖券,其实还包含了其他的奖券都不能赢得头等奖500万(假设头等奖只有一个),将一千万种可能的结果坍缩到了唯一的确定结果,所以信息其实是一种不确定度(复杂度)的消除。

自信息

信息论的一个基本想法是一个不太可能发生的事件居然发生了,要比一个非常可能的事件发生,能提供更多的信息。消息说:“今天早上太阳升起”,信息量是如此之少,以至于没有必要发送;但一条消息说:“今天早上有日食”,信息量就很丰富。

我们想要通过这种基本想法来量化信息,特别是:

  • 非常可能发生的事件信息量要比较少,并且极端的情况下,确保能够发生的事件应该没有信息量。

  • 较不可能发生的事件具有更高的信息量。

  • 独立事件应具有增量的信息。例如,投掷的硬币两次正面朝上传递的信息,应该是透支一次硬币正面朝上的信息量的两倍。

为了满足上述3个性质,我们定义一个事件X=x的自信息为

其中,以e为底的对数的单位是奈特(nats),以2为底的对数的单位是比特(bit)或香农(shannons)。

信息熵

信息熵也叫香农熵。

信息熵的定义

信息可不可以被量化,怎样量化?答案当然是有的,那就是“信息熵”。早在1948年,香农(Shannon)在他著名的《通信的数学原理》论文中指出:“信息是用来消除随机不确定性的东西”,并提出了“信息熵”的概念(借用了热力学中熵的概念),来解决信息的度量问题。

自信息只处理单个的输出。我们可以用信息熵(香农熵)来对整个概率分布中的不确定性总量进行量化:

也记作$H(P)$。换言之,一个分布的信息熵是指遵循这个分布的事件所产生的期望信息总量。它给除了对依据概率分布P生成的符号进行编码所需的比特数在平均意义上的下界。那些接近确定性的分布(输出几乎可以确定)具有较低的熵;那些接近均匀分布的概率分布具有较高的熵。

对信息熵的另一种定义:最短平均编码长度。也就是说,当编码方案完美时,最短平均编码长度是多少。

信息熵的直观理解

  • 信息熵的直观理解

一种直观理解信息熵的说法:信息熵是“惊喜的期望值”。买彩票中五百万的可能性很小,一旦你真中了五百万,那你就会很惊喜,那么买彩票中五百万的信息熵就很大。信息会改变你对事物的未知度和好奇心,你拥有的信息量越大,你对事物越了解,进而你对事物的好奇心也会降低,因为你对事物的确定性越高。至此,为了抽象这个模型,聪明的香农总结出了信息熵这个概念。信息熵用以表示一个事物的非确定性,如果该事物的非确定性越高,你的好奇心越重,该事物的信息熵就越高。

信息熵是消除不确定性所需信息量的度量,也即未知事件可能含有的信息量。

一个事件或一个系统,准确的说是一个随机变量,它有着一定的不确定性。例如,“除东道主俄罗斯外,哪31个国家能进军2018年俄罗斯世界杯决赛圈”,这个随机变量的不确定性很高,要消除这个不确定性,就需要引入很多的信息,这些很多信息的度量就用“信息熵”表达。需要引入消除不确定性的信息量越多,则信息熵越高,反之则越低。例如“中国男足进军2018年俄罗斯世界杯决赛圈”,这个因为确定性很高,几乎不需要引入信息,因此信息熵很低。再拿上文中的抽奖来举例子,你要抽奖很多很多次(运气最差的情况:抽奖一千万减一次,即引入很多消除不确定性的信息量,才能确定买哪一张中奖),即你需要引入很多消除不确定性的信息量,所以抽奖中五百万这件事的信息熵很高。

  • 信息熵的计算

那信息熵如何计算呢?举个吴军在《数学之美》中一样的例子(吴军先生的《数学之美》这本书用了一章对信息熵做了通俗易懂的讲解),假设世界杯决赛圈32强已经产生,那么随机变量“2018年俄罗斯世界杯足球赛32强中,谁是世界杯冠军?”的信息量是多少呢?

根据香农(Shannon)给出的信息熵公式,对于任意一个随机变量X,它的信息熵定义如下,单位为比特(bit):

那么上述随机变量(谁获得冠军)的信息量是:

其中,p1,p2,…,p32分别是这32强球队夺冠的概率。

吴军的书中给出了几个结论:一是32强球队夺冠概率相同时,H=5;二是夺冠概率不同时,H<5;三是H不可能大于5。

对于第一个结论:结果是很显然的,夺冠概率相同,即每个球队夺冠概率都是1/32,所以

对于第二个结论和第三个结论:使用拉格朗日乘子法进行证明,详见《求约束条件下极值的拉格朗日乘子法》。这实际上是说系统中各种随机性的概率越均等,信息熵越大,反之越小。怎么直观理解夺冠概率相同时信息熵最大呢?信息熵表述的就是事物的信息状态。事物的信息怎么定义呢?如果你确定一件事件的发生概率是100%,你认为这件事情的信息量为0——可不是吗,既然都确定了,就没有信息量了;相反,如果你不确定这件事,你需要通过各种方式去了解,就说明这件事是有意义的,是有信息量的。好的,你应该注意到了一个词“确定”。是的,信息熵表述的就是事物的不确定程度。一场势均力敌的比赛结果的不确定性高于一场已经被看到结果的比赛,多么符合直观理解啊!

  • 信息熵公式的推导

从香农给出的数学公式上可以看出,信息熵其实是一个随机变量信息量的数学期望。

从上面的直观表述,我们发现信息熵其实可以有很直观的表述,表征的是事物的不确定性。继续抽象,我们应该定量表述事物的不确定性呢?这就是信息熵的数学表述了

我们知道,合理的数据定理都需要满足数学自洽性验证,我们已经知道确定的事件表述为P(A)=100%,则熵为0;假设一件事情,只有两种可能,则概率分布是P(A)和P(-A),其熵表述为

上式对应的数据分布是

可以发现,当P(A)=0.5的时候,也就是事件结果最难预测的时候,信息熵是最大的,值达到1——这同样是符合直觉判断的。

那么,为什么求熵的时候用的是对数log2呢?这个就得从香农提出的信息熵使用的场景说起,大家都知道,香农提出的信息熵是用于信息论的,而信息论主要解决的是通讯问题,所以说,信息熵是和计算机通讯相关的理论。计算机的基本存储单位是二进制位,即1bit,每个bit都尤其只有两种表达——0或1。如果一个事件有两种可能性,且概率均等,都为50%,那么需要用1bit表示;如果有4种可能,且概率均等,则用2bit表示——你会发现,1bit刚好就是我们上面证明的H的最大值。这样就解释通了,底数为何为2了。

交叉熵与相对熵(KL散度)

信息熵:最短平均编码长度。即,编码方案完美时,平均编码长度是多少。

交叉熵:编码方案不一定完美时(由于对概率分布的估计不一定正确),平均编码长度是是多少。

由以上定义,甚至不用计算就可以直观感受到:交叉熵的大小不会比信息熵更小,因为信息熵是方案最完美时的平均编码长度嘛。

而相对熵是两者的差值,即交叉熵减去信息熵。也叫KL散度。

交叉熵

这里再强调一遍:

  • 熵的本质含义是:编码方案完美时,最短平均编码长度的是多少

  • 交叉熵的本质含义是:编码方案不一定完美时(但你或者模型以为是完美的),平均编码长度的是多少

我们先直观地理解交叉熵,用信息编码来直观举例说明,然后再用严谨的数学语言来描述交叉熵的概念。

从信息编码的角度举个例子:

信息熵:

假设一个信源是一个随机变量X,且该随机变量取值的正确分布p如下:

因为我们知道信道传输是只能传二进制编码的,所以必须对A,B,C进行编码,根据哈夫曼(Huffman)树来实现,如下所示:

也就是说A被编码为0,B被编码为10,C被编码为11。所以ABC字符的平均编码长度为:

那么这个随机变量的信息熵是什么呢?

正好也是1.5。所以说信息熵是随机变量平均编码的最小长度。

交叉熵

有了信息上的概念后,然后就去看看交叉上的物理含义。假设我们用一个错误的分布q,对随机变量编码,q的分布如下:

那么我们得到的哈夫曼树为:

也就是说A被编码为11,B被编码为10,C被编码为0。但是实际上,ABC三个字符实际出现的概率还是1/2,1/4,1/4。所以在这种情况下,平均编码长度变成了

那么这个时候的交叉熵H(p,q)是什么呢?计算如下:

正好也是1.75的,所以这就是交叉熵的物理含义。

有了交叉熵和信息熵,那么相对熵就更好理解了。其实际含义就是用错误分布对随机变量编码时,其产生多余的编码长度。

这里就是

由上面的分析,我们很容易直观理解了交叉熵是一定大于信息熵的,那从数学上该怎么证明呢?这其实就是吉布斯不等式(Gibbs inequality):

下面用比较严谨的语言来说明交叉熵和相对熵:

现有关于样本集的2个概率分布p和q,其中p为真实分布,q为非真实分布(即你所估算出来的你认为的真实分布,但和真实分布p可能并不一致)。

按照真实分布p来衡量识别一个样本的所需要的编码长度的期望(即平均编码长度)为:

如果使用有误差(只是你个人觉得很完美)的分布q来表示来自真实分布p的平均编码长度,则应该是:

,因为用q来编码的样本来自分布p,所以期望H(p,q)中概率是p(i)。H(p,q)我们称之为“交叉熵”。

比如含有4个字母(A,B,C,D)的数据集中,真实分布p=(1/2,1/2,0,0),即A和B出现的概率均为1/2。C和D出现的概率都为0。计算H(p)为1,即只需要1位编码即可识别A和B。如果使用不恰当的分布Q=(1/4,1/4,1/4,1/4)来编码则得到H(p,q)=2,即需要2位编码来识别A和B(当然还有C和D,尽管C和D并不会出现,因为真实分布p中C和D出现的概率为0,这里就钦定概率为0的事件不会发生啦)。

可以看到上例中根据非真实(只是你个人以为是真实的)分布q得到的平均编码长度H(p,q)大于根据真实分布p得到的平均编码长度H(p)。事实上,根据吉布斯不等式(Gibbs' inequality)可知,H(p,q)>=H(p)恒成立,当q为真实分布p时取等号。

这里要完全理解交叉熵的关键就是,一定要意识到信息熵是最短平均编码长度。即编码方案完美时的平均编码长度,其他任何编码方案的平均编码长度都要大于信息熵。

交叉熵损失函数

交叉熵可在机器学习中作为损失函数,p表示真实标记的分布,q则为训练后的模型的预测标记分布,交叉熵损失函数可以衡量p与q的相似性。交叉熵作为损失函数还有一个好处在神经网络中使用sigmod函数在梯度下降时能避免均方误差损失函数学习速率降低的问题,因为学习速率可以被输入的误差所控制。

PS:通常“相对熵”也可以称之为“交叉熵”,因为真实分布p是固定的,D(p||q)由H(p,q)决定。当然也有特殊情况,彼时两者须区别对待。

大部分机器学习和现代的神经网络使用最大似然来训练。这意味着代价函数就是负的对数似然。它与训练数据和模型分布之间的交叉熵等价。这个代价函数表示为

可以看出:任何一个由负对数似然组成的损失都是定义在训练集上的经验分布和定义在模型上的概率分布之间的交叉熵。例如,均方误差是经验分布和高斯模型之间的交叉熵。在《深度学习》第235页中,Goodfellow也提到,均方误差就是与单位高斯分布的输出相关联的交叉熵损失。

交叉熵和最大似然的等价性

交叉熵这东西你如果理解为两个概率分布会发现它就是nonsense,你得把对数里面那个分布理解为真实的随机变量分布,而将对数外面那个理解为观察到的频率。然后你就会发现它就是最最原始的MLE(最大似然估计)套了个时髦的壳而已。

比如说现在有一个真实分布为P(x)的随机变量,我们对它进行了N次独立同分布实验,对于每个可能的结果x观察到的次数为N(x),那么它的似然值就可以写成

很好理解对吧,乘法公式,把每次实验的概率乘起来,然后合并相同的项写成幂次。这是个乘积的形式,取个对数可以得到求和的形式:

这个式子有两个缺点,第一它是个负数,第二它的数值跟样本数有关,样本越多数值越小,因此除以一下总的样本数归一化,再取个相反数,然后改用频率表示:

就齐活了。

求偏导得到

因此在有模型约束的条件下求交叉熵最小值,也就是让模型输出的分布尽量能接近训练数据的分布。

相对熵(KL散度)

相对熵的本质是:你所以为或者你估算出的完美编码方案,和实际的完美方案相比,平均编码长度多出来的长度。

我们将由存在误差(只是你自己以为正确无误)的q分布得到的平均编码长度比由p分布得到的平均编码长度多出的bit数称为“相对熵”:

注意,KL散度不对称,没有交换律。因为所基于的真实分布p不一样。

如果对于同一个随机变量x有两个单独的概率分布P(x)和Q(x),可以使用KL散度来衡量这两个分布的差异:

在离散型随机变量的情况下,KL散度衡量的是,当我们使用一种被设计成能够使得概率分布Q产生的消息长度最小的编码,发送包含由概率分布P产生的符号的消息时,所需要的额外信息量。

PS:通常“相对熵”也可称为“交叉熵”,因为真实分布p是固定的,D(p||q)由H(p,q)决定。针对q最小化交叉熵等价于最小化KL散度,因为q并不参与被省略的H(p)项。当然也有特殊情况,彼时2者须区别对待。

相对熵与TF-IDF

在吴军的《数学之美》中,相关性那一节提到TF-IDF算法可以理解为相对熵的应用:词频在整个语料库的分布与词频在具体文档中分布之间的差异性。

首先大致介绍下什么是TF_IDF:

在一份给定的文件里,词频(term frequency,TF)指的是某一个给定的词语在该文件中出现的频率。对于在某一特定文件里的词语ti来说,它的重要性可表示为:

以上式子中n_{i,j}是该词在文件d_j中的出现次数,而分母则是在文件d_j中所有字词的出现次数之和。

逆向文件频率(inverse document frequency,IDF)是一个词语普遍重要性的度量。某一特定词语的IDF,可以由总文件数目除以包含该词语之文件的数目,再将得到的商取以10为底的对数得到:

其中,

  • 上式分子为语料库中的文件总数

  • 上式分母为包含词语t_i的文件数目(即n_{i,j}≠0的文件数目)

则词语t_i在文件d_j中的重要程度为:

TF-IDF权重计算方法经常会和余弦相似性(cosine similarity)一同使用于向量空间模型中,用以判断两份文件之间的相似性。

下面讨论相对熵与TF-IDF的关系:

先进行一些假设:

  • 假设1:每个词的出现是独立事件

  • 假设2:每篇文档大小基本相同,都为m个词

  • 假设3:一个词wi如果出现在文档中,则在每个文档中出现的次数ni都相同

    注:我也觉得这个假设太过理想了

有了以上假设后,我们可以估计每个词的概率分布进而求解其信息量了。

设共有D篇文档,每篇文档有m个词,其中包含词wi的文档有D(wi)篇,有:

设词wi在文档d中的真实概率分布为p‘,于是

然后把p'、q套进相对熵公式:

上式如何理解呢?

  • 当这个相对熵(TF-IDF之和)越大,q对文档d的描述越差,说明文档d的内容指向性越强,因为q是对整个语言中所有词的概率分布的估计

  • 当这个相对熵越小(TF-IDF之和)越小,q对文档d的描述越好,说明文档d的内容指向性越差,越可能是随机按q选取词堆砌成文

条件熵、联和熵与互信息

条件熵

条件熵就是按照一个分类变量对原变量数据进行分类后,原变量的不确定性就会减小了,因为新增加了这个新的分类变量的信息。这个不确定程度减小了多少就是信息的增益,而还剩下多少不确定性程度就是条件熵。

条件熵是另一个变量Y的熵对X(条件)的期望而已。

由信息熵引出条件熵

我们首先知道信息熵是考虑该随机变量的所有可能取值,即所有可能发生事件所带来的信息量的期望。公式如下:

我们的条件熵的定义是:定义为给定X条件下,Y的条件概率分布的熵的数学期望。

这个还是比较抽象,下面我们解释一下:

设有随机变量(X,Y),其联合概率分布为

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。

随机变量X给定的条件下随机变量Y的条件熵H(Y|X)

条件熵公式

下面推导一下条件熵的公式:

注意,这个条件熵,不是指在给定某个数(某个变量为某个值)的情况下,另一个变量的熵是多少,变量的不确定性是多少?而是期望!

因为条件熵中X也是一个变量,意思是在一个变量X的条件下(变量X的每个值都会取),另一个变量Y的熵对X的期望。

条件熵是另一个变量Y的熵对X(条件)的期望。

这是最容易错的!

举例解释条件熵

下面通过例子来解释一下:

假如我们有上面数据,则设随机变量Y={嫁, 不嫁},我们就可以统计出,嫁的个数为6/12 = 1/2,不嫁的个数为6/12 = 1/2,那么Y的熵,根据熵的公式来算,可以得到

为了引出条件熵,我们现在还有一个变量X,代表长相是帅还是不帅,当长相是不帅的时候,统计如下红色所示:

可以得出,当已知不帅的条件下,满足条件的只有4个数据了,这四个数据中,不嫁的个数为1个,占1/4,

嫁的个数为3个,占3/4,那么此时是否嫁人的熵为

同理我们可以得到,当已知帅的条件下,满足条件的有8个数据了,这八个数据中,不嫁的个数为5个,占5/8

嫁的个数为3个,占3/8,那么此时是否嫁人的熵为

我们终于可以计算我们的条件熵了,我们现在需要求:

也就是说,我们想要求出当已知长相的条件下的条件熵。根据公式我们可以知道,长相可以取帅与不帅两种。

由于条件熵是另一个变量Y熵对X(条件)的期望。公式为:

则有

然后将上面已经求得的答案带入即可求出条件熵!

这里比较容易犯的错误就是忽略了X也是可以取多个值,然后对其求期望!!

条件熵总结

其实条件熵意思是按一个新的变量的每个值(并非单一的某个值)对原变量进行分类,比如上面这个题把嫁与不嫁按帅,不帅分成了俩类。然后在每一个小类里面,都计算一个小熵,然后每一个小熵乘以各个类别的概率,然后求和。

我们用另一个变量对原变量分类后,原变量的不确定性就会减小了,因为新增了Y的信息,可以感受一下。不确定程度减少了多少就是信息的增益。

条件熵是另一个变量Y的熵对X(条件)的期望。

联和熵

  • 两个随机变量X、Y的联合分布,可形成联和熵(Joint Entropy),用H(X, Y)表示。

  • H(X,Y)-H(X)=H(Y|X)

    • (X, Y)发生所包含的熵 - X单独发生包含的熵 = 在X发生的前提下Y发生“新”带来的熵

    • 该式子定义为X发生前提下,Y的熵,即条件熵H(Y|X)

互信息(信息增益)

  • 两个随机变量X,Y的互信息,定义为X,Y的联合分布和独立分布乘积的相对熵(KL散度)

  • 或者根据文氏图,也可将互信息定义为:I(X,Y) = H(X) + H(Y) - H(X,Y)

条件熵也可由H(X)-I(X,Y)推出:

互信息和信息增益的异同:

  • 互信息的大小和信息增益相等,即由于Y的引入,使X的熵减小的量。

  • 但我个人认为两者意义不一样,互信息度量的是X和Y的相关性。如果X和Y是独立的,那么X和Y的互信息就是零。

    说互信息的时候,X,Y两个随机变量的地位是相同的

    说信息增益的时候,是把一个变量堪称减小另一个变量不确定度的手段。

各种熵之间关系的文氏图

整理得到的等式

  • 条件熵定义

    H(Y|X) = H(X,Y) - H(X)

  • 根据互信息定义展开得到

    H(Y|X) = H(Y) - I(X,Y)

  • 对偶式

    H(Y|X) = H(X,Y) - H(X)

    H(Y|X) = H(Y) - I(X,Y)

  • 多数文献,将该式作为互信息的定义式

    I(X,Y) = H(X) + H(Y) - H(X,Y)

  • H(Y|X) ≤ H(Y)

参考资料

  • 《深度学习》Goodfellow,第三章,概率与信息论

“自信息”一章参考此书;“交叉熵与相对熵(KL散度)”一章参考此书。

"条件熵"一节参考此博客。

"交叉熵"一节参考此博客。

"交叉熵和最大似然的等价性"参考此知乎回答。

"相对熵与TF-IDF"一节参考此博客。

“各种熵之间关系的文氏图”一节参考子ppt。

===

有时间看下下面的网址

I(x)=−logP(x)I(x)=-logP(x)I(x)=−logP(x)
H(x)=Ex∼P[I(x)]=−Ex∼P[logP(x)]H(x)=\mathbb{E}_{x\sim P}[I(x)]=-\mathbb{E}_{x\sim P}[log P(x)]H(x)=Ex∼P​[I(x)]=−Ex∼P​[logP(x)]
H(x)=−∑x∈Xp(x)⋅logp(x)H(x) = -\sum_{x\in X}{p(x)\cdot log{p(x)}}H(x)=−x∈X∑​p(x)⋅logp(x)
H=−(p1⋅logp1+p2⋅logp2+...+p32⋅logp32)H=-(p1\cdot log{p1}+p2\cdot log{p2}+...+p32\cdot log{p32})H=−(p1⋅logp1+p2⋅logp2+...+p32⋅logp32)
H=−(132⋅log132+132⋅log132+...+132⋅log132)H=-(\frac{1}{32}\cdot log{\frac{1}{32}}+\frac{1}{32}\cdot log{\frac{1}{32}}+...+\frac{1}{32}\cdot log{\frac{1}{32}})H=−(321​⋅log321​+321​⋅log321​+...+321​⋅log321​)
H=−(p(A)⋅log2p(A)+(1−p(A))⋅log2(1−p(A)))H=-(p(A)\cdot log_{2}p(A)+(1-p(A))\cdot log_2(1-p(A)))H=−(p(A)⋅log2​p(A)+(1−p(A))⋅log2​(1−p(A)))
A:12,B:14,C:14A:\frac{1}{2},\quad B:\frac{1}{4},\quad C:\frac{1}{4}A:21​,B:41​,C:41​
12×1+14×2+14×2=1.5\frac{1}{2}\times 1+\frac{1}{4}\times 2+\frac{1}{4}\times 2=1.521​×1+41​×2+41​×2=1.5
H(X)=−12log2(12)−14log2(14)−14log2(14)=0.5+0.5+0.5=1.5\begin{aligned} H(X)&=-\frac{1}{2}\text{log}_2(\frac{1}{2})-\frac{1}{4}\text{log}_2(\frac{1}{4})-\frac{1}{4}\text{log}_2(\frac{1}{4})\\ &=0.5+0.5+0.5\\ &=1.5 \end{aligned}H(X)​=−21​log2​(21​)−41​log2​(41​)−41​log2​(41​)=0.5+0.5+0.5=1.5​
A:14,B:14,C:12A:\frac{1}{4},\quad B:\frac{1}{4},\quad C:\frac{1}{2}A:41​,B:41​,C:21​
12×2+14×2+14×1=1.75\frac{1}{2}\times 2+\frac{1}{4}\times 2+\frac{1}{4}\times 1=1.7521​×2+41​×2+41​×1=1.75
H(p,q)=−12log2(14)−14log2(14)−14log2(12)=1+0.5+0.25=1.75\begin{aligned} H(p,q)&=-\frac{1}{2}\text{log}_2(\frac{1}{4})-\frac{1}{4}\text{log}_2(\frac{1}{4})-\frac{1}{4}\text{log}_2(\frac{1}{2})\\ &=1+0.5+0.25\\ &=1.75 \end{aligned}H(p,q)​=−21​log2​(41​)−41​log2​(41​)−41​log2​(21​)=1+0.5+0.25=1.75​
DK,L(p∣∣q)=H(p,q)−H(p)=1.75−1.5=0.25D_{K,L}(p||q)=H(p,q)-H(p)=1.75-1.5=0.25DK,L​(p∣∣q)=H(p,q)−H(p)=1.75−1.5=0.25
DK,L(p∣∣q)=H(p,q)−H(p)=−∑i∈Ipiln qi−(−∑i∈Ipiln pi)=−∑i∈Ipiln qipi⩾−∑i∈Ipi(qipi−1) since ln x⩽x−1=−∑i∈Iqi+∑i∈Ipi=0\begin{aligned} D_{K,L}(p||q)&=H(p,q)-H(p)\\ &=-\sum_{i\in I}p_i\text{ln}\ q_i - (-\sum_{i\in I}p_i\text{ln}\ p_i)\\ &=-\sum_{i\in I}p_i\text{ln}\ \frac{q_i}{p_i}\\ &\geqslant-\sum_{i\in I}p_i\left( \frac{q_i}{p_i}-1 \right)\ \text{since}\ \text{ln}\ x \leqslant x -1\\ &=-\sum_{i\in I}q_i+\sum_{i\in I}p_i\\ &=0\\ \end{aligned}DK,L​(p∣∣q)​=H(p,q)−H(p)=−i∈I∑​pi​ln qi​−(−i∈I∑​pi​ln pi​)=−i∈I∑​pi​ln pi​qi​​⩾−i∈I∑​pi​(pi​qi​​−1) since ln x⩽x−1=−i∈I∑​qi​+i∈I∑​pi​=0​
H(p)=∑ip(i)log1p(i)H(p)=\sum_ip(i)\text{log}\frac{1}{p(i)}H(p)=i∑​p(i)logp(i)1​
H(p,q)=∑ip(i)log1q(i)H(p,q)=\sum_ip(i)\text{log}\frac{1}{q(i)}H(p,q)=i∑​p(i)logq(i)1​
J(θ)=−Ex,y∼p^datalog pmodel(y∣x)J(\theta)=-\mathbb E_{x,y\sim\hat{p}_{\text{data}}}\text{log}\ p_{\text{model}}(y|x)J(θ)=−Ex,y∼p^​data​​log pmodel​(y∣x)
L=ΠxP(x)N(x)L=\mathop{\Pi}_xP(x)^{N(x)}L=Πx​P(x)N(x)
lnL=∑xN(x)lnP(x)lnL=\sum_{x}N(x)lnP(x)lnL=x∑​N(x)lnP(x)
−∑xN(x)NlnP(x)=−∑xP0(x)lnP(x)-\sum_x\frac{N(x)}{N}lnP(x)=-\sum_xP_0(x)lnP(x)−x∑​NN(x)​lnP(x)=−x∑​P0​(x)lnP(x)

因此可以看出,交叉熵最小实质上就是似然值最大。我们可以证明,在给定$P_0$的情况下,使交叉熵最小的分布P一定有P=P0P=P_0P=P0​,只需要用拉格朗日乘子法就可以:

W=−∑P0(x)lnP(x)+λ(∑xP(x)−1)W=-\sum P_0(x)lnP(x)+\lambda\left(\sum_xP(x)-1\right)W=−∑P0​(x)lnP(x)+λ(x∑​P(x)−1)
−P0(x)P(x)+λ=0-\frac{P_0(x)}{P(x)}+\lambda=0−P(x)P0​(x)​+λ=0

即P0P_0P0​和P成比例,再根据归一化条件得到P=P0P=P_0P=P0​

D(p∣∣q)=H(p,q)−H(p)=∑ip(i)logp(i)q(i)D(p||q)=H(p,q)-H(p)=\sum_ip(i)log\frac{p(i)}{q(i)}D(p∣∣q)=H(p,q)−H(p)=i∑​p(i)logq(i)p(i)​

,其又被称为(Kullback-Leibler divergence, KLD)。它表示两个函数或概率分布的差异性:差异越大则相对熵越大,差异越小则相对熵越小,特别地,若两者相同则熵为0。

DKL(P∣∣Q)=Ex∼P[logP(x)Q(x)]=Ex∼P[logP(x)−logQ(x)]D_{KL}(P||Q)=\mathbb{E}_{x\sim P}\left[log\frac{P(x)}{Q(x)}\right]=\mathbb{E}_{x\sim P}[logP(x)-logQ(x)]DKL​(P∣∣Q)=Ex∼P​[logQ(x)P(x)​]=Ex∼P​[logP(x)−logQ(x)]

是一种统计方法,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加,但同时会随着它在语料库中出现的频率成反比下降。

TFi,j=ni,j∑knk,j\text{TF}_{i,j}=\frac{n_{i,j}}{\sum_{k}n_{k,j}}TFi,j​=∑k​nk,j​ni,j​​
IDFi=lg∣D∣∣{j:ti∈dj}∣\text{IDF}_i=\text{lg}\frac{|D|}{|\{ j:t_i\in d_j \}|}IDFi​=lg∣{j:ti​∈dj​}∣∣D∣​
TF-IDFi,j=TFi,j×IDFi\text{TF-IDF}_{i,j}=\text{TF}_{i,j}\times \text{IDF}_iTF-IDFi,j​=TFi,j​×IDFi​
q(wi)=niD(wi)mDq(w_i)=\frac{n_iD(w_i)}{mD}q(wi​)=mDni​D(wi​)​
p′(wi)=nimp'(w_i)=\frac{n_i}{m}p′(wi​)=mni​​
DKL(p′∣∣q)=∑i=1kp′(wi)log2p′(wi)q(wi)=∑i=1knimlog2ni/mniD(wi)/mD=∑i=1knimlog21D(wi)/D=∑i=1kTF(wi)⋅IDF(wi)\begin{aligned} D_{KL}(p'||q)&=\sum_{i=1}^kp'(w_i)\text{log}_2\frac{p'(w_i)}{q(w_i)}\\ &=\sum_{i=1}^k\frac{n_i}{m}\text{log}_2\frac{n_i/m}{n_iD(w_i)/mD}\\ &=\sum_{i=1}^k\frac{n_i}{m}\text{log}_2\frac{1}{D(w_i)/D}\\ &=\sum_{i=1}^k\text{TF}(w_i)\cdot\text{IDF}(w_i)\\ \end{aligned}DKL​(p′∣∣q)​=i=1∑k​p′(wi​)log2​q(wi​)p′(wi​)​=i=1∑k​mni​​log2​ni​D(wi​)/mDni​/m​=i=1∑k​mni​​log2​D(wi​)/D1​=i=1∑k​TF(wi​)⋅IDF(wi​)​
H(x)=−∑i=1np(xi)log p(xi)H(x)=-\sum_{i=1}^np(x_i)\text{log}\ p(x_i)H(x)=−i=1∑n​p(xi​)log p(xi​)
p(X=xi,Y=yi)=pij, i=1,2,...,n, j=1,2,...,mp(X=x_i,Y=y_i)=p_{ij}, \ i=1,2,...,n,\ j=1,2,...,mp(X=xi​,Y=yi​)=pij​, i=1,2,...,n, j=1,2,...,m
H(Y∣X)=∑x∈Xp(x)H(Y∣X=x)=−∑x∈Xp(x)∑y∈Yp(y∣x)log p(y∣x)=−∑x∈X∑y∈Yp(x,y)log p(y∣x)\begin{aligned} H(Y|X)&=\sum_{x\in X}p(x)H(Y|X=x)\\ &=-\sum_{x\in X}p(x)\sum_{y\in Y}p(y|x)log\ p(y|x)\\ &=-\sum_{x\in X}\sum_{y\in Y}p(x,y)log\ p(y|x)\\ \end{aligned}H(Y∣X)​=x∈X∑​p(x)H(Y∣X=x)=−x∈X∑​p(x)y∈Y∑​p(y∣x)log p(y∣x)=−x∈X∑​y∈Y∑​p(x,y)log p(y∣x)​
H(Y)=−12log12−12log12H(Y)=-\frac{1}{2}log\frac{1}{2}-\frac{1}{2}log\frac{1}{2}H(Y)=−21​log21​−21​log21​
H(Y∣X=不帅)=−14log14−34log34p(X=不帅)=4/12=1/3\begin{aligned} &H(Y|X=\text{不帅})=-\frac{1}{4}log\frac{1}{4}-\frac{3}{4}log\frac{3}{4}\\ &p(X=\text{不帅})=4/12=1/3 \end{aligned}​H(Y∣X=不帅)=−41​log41​−43​log43​p(X=不帅)=4/12=1/3​
H(Y∣X=帅)=−58log58−38log38p(X=帅)=8/12=2/3\begin{aligned} &H(Y|X=\text{帅})=-\frac{5}{8}log\frac{5}{8}-\frac{3}{8}log\frac{3}{8}\\ &p(X=\text{帅})=8/12=2/3\\ \end{aligned}​H(Y∣X=帅)=−85​log85​−83​log83​p(X=帅)=8/12=2/3​
H(Y∣X=长相)H(Y|X=\text{长相})H(Y∣X=长相)
H(Y∣X)=∑x∈Xp(x)H(Y∣X=x)H(Y|X)=\sum_{x\in X}p(x)H(Y|X=x)H(Y∣X)=x∈X∑​p(x)H(Y∣X=x)
H(Y∣X=长相)=p(X=帅)×H(Y∣X=帅)+p(X=不帅)×H(Y∣X=不帅)H(Y|X=\text{长相})=p(X=\text{帅})\times H(Y|X=\text{帅})+p(X=\text{不帅})\times H(Y|X=\text{不帅})H(Y∣X=长相)=p(X=帅)×H(Y∣X=帅)+p(X=不帅)×H(Y∣X=不帅)
H(X,Y)−H(X)=−∑x,yp(x,y)log p(x,y)+∑xp(x)log p(x)=−∑x,yp(x,y)log p(x,y)+∑x(∑yp(x,y))log p(x)=−∑x,yp(x,y)log p(x,y)+∑x,yp(x,y)log p(x)=−∑x,yp(x,y)log p(x,y)p(x)=−∑x,yp(x,y)log p(y∣x)=−∑xp(x)∑yp(y∣x)log p(y∣x)=−∑xp(x)H(y∣x)\begin{aligned} &H(X,Y)-H(X)\\ =&-\sum_{x,y}p(x,y)\text{log}\ p(x,y)+\sum_xp(x)\text{log}\ p(x)\\ =&-\sum_{x,y}p(x,y)\text{log}\ p(x,y)+\sum_x(\sum_yp(x,y))log\ p(x)\\ =&-\sum_{x,y}p(x,y)\text{log}\ p(x,y)+\sum_{x,y}p(x,y)\text{log}\ p(x)\\ =&-\sum_{x,y}p(x,y)\text{log}\ \frac{p(x,y)}{p(x)}\\ =&-\sum_{x,y}p(x,y)\text{log}\ p(y|x)\\ =&-\sum_{x}p(x)\sum_{y}p(y|x)\text{log}\ p(y|x)\\ =&-\sum_{x}p(x)H(y|x)\\ \end{aligned}=======​H(X,Y)−H(X)−x,y∑​p(x,y)log p(x,y)+x∑​p(x)log p(x)−x,y∑​p(x,y)log p(x,y)+x∑​(y∑​p(x,y))log p(x)−x,y∑​p(x,y)log p(x,y)+x,y∑​p(x,y)log p(x)−x,y∑​p(x,y)log p(x)p(x,y)​−x,y∑​p(x,y)log p(y∣x)−x∑​p(x)y∑​p(y∣x)log p(y∣x)−x∑​p(x)H(y∣x)​
I(X,Y)=D(P(X,Y)∣∣P(X)P(Y))=∑x,yp(x,y)logp(x,y)p(x)p(y)I(X,Y)=D(P(X, Y)||P(X)P(Y))=\sum_{x,y}p(x,y)\text{log}\frac{p(x,y)}{p(x)p(y)}I(X,Y)=D(P(X,Y)∣∣P(X)P(Y))=x,y∑​p(x,y)logp(x)p(y)p(x,y)​
H(X)−I(X,Y)=−∑xp(x)log p(x)−∑x,yp(x,y)log p(x,y)p(x)p(y)=−∑x(∑yp(x,y))log p(x)−∑x,yp(x,y)log p(x,y)p(x)p(y)=−∑x,yp(x,y))log p(x)−∑x,yp(x,y)log p(x,y)p(x)p(y)=∑x,yp(x,y)log p(x,y)p(y)=∑x,yp(x,y)log p(x∣y)=H(X∣Y)\begin{aligned} &H(X)-I(X,Y)\\ =&-\sum_xp(x)\text{log}\ p(x)-\sum_{x,y}p(x,y)\text{log}\ \frac{p(x,y)}{p(x)p(y)}\\ =&-\sum_x(\sum_yp(x,y))\text{log}\ p(x)-\sum_{x,y}p(x,y)\text{log}\ \frac{p(x,y)}{p(x)p(y)}\\ =&-\sum_{x,y}p(x,y))\text{log}\ p(x)-\sum_{x,y}p(x,y)\text{log}\ \frac{p(x,y)}{p(x)p(y)}\\ =&\sum_{x,y}p(x,y)\text{log}\ \frac{p(x,y)}{p(y)}\\ =&\sum_{x,y}p(x,y)\text{log}\ p(x|y)\\ =&H(X|Y)\\ \end{aligned}======​H(X)−I(X,Y)−x∑​p(x)log p(x)−x,y∑​p(x,y)log p(x)p(y)p(x,y)​−x∑​(y∑​p(x,y))log p(x)−x,y∑​p(x,y)log p(x)p(y)p(x,y)​−x,y∑​p(x,y))log p(x)−x,y∑​p(x,y)log p(x)p(y)p(x,y)​x,y∑​p(x,y)log p(y)p(x,y)​x,y∑​p(x,y)log p(x∣y)H(X∣Y)​
Venn-diagram-of-entropy

KL散度
初学机器学习:直观解读KL散度的数学概念
TF-IDF
通俗理解条件熵
如何通俗的解释交叉熵与相对熵?
为什么交叉熵(cross-entropy)可以用于计算代价?
信息论随笔3: 交叉熵与TF-IDF模型
北京2014年10月机器学习班之邹博的最大熵模型PPT
信息论的熵
从香农熵到手推KL散度:纵览机器学习中的信息论
如何通俗的解释交叉熵与相对熵?
机器学习各种熵:从入门到全面掌握
为什么交叉熵(cross-entropy)可以用于计算代价?
信息量,熵,交叉熵,相对熵与代价函数
http://blog.csdn.net/saltriver/article/details/53056816
http://blog.csdn.net/xuxurui007/article/details/21788551
https://www.zhihu.com/search?type=content&q=%E4%BF%A1%E6%81%AF%E7%86%B5
https://www.zhihu.com/question/26521135
https://www.zhihu.com/question/26446385
https://www.zhihu.com/question/40185590
https://zhuanlan.zhihu.com/p/28564865
https://zhuanlan.zhihu.com/p/26486223
http://www.jianshu.com/p/67425a89df47
https://ask.julyedu.com/question/6897
https://ask.julyedu.com/people/zoubo
https://ask.julyedu.com/question/628
https://www.zhihu.com/question/21149770/answer/219143281
返回顶层目录
返回上层目录
什么是信息
自信息
信息熵
信息熵的定义
信息熵的直观理解
交叉熵与相对熵(KL散度)
交叉熵
交叉熵损失函数
交叉熵和最大似然的等价性
相对熵(KL散度)
相对熵与TF-IDF
条件熵、联和熵与互信息
条件熵
联和熵
互信息(信息增益)
各种熵之间关系的文氏图
参考资料
huffman_tree_1
huffman_tree_2
marry_or_not
marry_not_handsome