如何比特币通俗解释的解释交叉熵与相对熵
点击联系发帖人
时间：2017-07-15 10:59
&p&讨论这个问题需要从香农的信息熵开始。&/p&&p&小明在学校玩王者荣耀被发现了，爸爸被叫去开家长会，心里悲屈的很，就想法子惩罚小明。到家后，爸爸跟小明说：既然你犯错了，就要接受惩罚，但惩罚的程度就看你聪不聪明了。这样吧，我出一个题目，你猜答案，你每猜一次，不管对错，你就一个星期不能玩王者荣耀，当然，猜对，游戏停止，否则继续猜。&/p&&br&&p&题目1：爸爸拿来一个箱子，跟小明说：里面有橙、紫、蓝及青四种颜色的小球任意个，各颜色小球的占比不清楚，现在我从中拿出一个小球，你猜我手中的小球是什么颜色？&/p&&p&为了使被罚时间最短，小明发挥出最强王者的智商，瞬间就想到了以最小的代价猜出答案，简称策略1，小明的想法是这样的。&/p&&img src=&/v2-97e76bdbfcf75_b.png& data-rawwidth=&300& data-rawheight=&213& class=&content_image& width=&300&&&p&在这种情况下，小明什么信息都不知道，只能认为四种颜色的小球出现的概率是一样的。所以，根据策略1，1/4概率是橙色球，小明需要猜两次，1/4是紫色球，小明需要猜两次，其余的小球类似，所以小明预期的猜球次数为：&/p&&p&H = 1/4 * 2 + 1/4 * 2 + 1/4 * 2 + 1/4 * 2 = 2&/p&&br&&p&题目2：爸爸还是拿来一个箱子，跟小明说：箱子里面有小球任意个，但其中1/2是橙色球，1/4是紫色球，1/8是蓝色球及1/8是青色球。我从中拿出一个球，你猜我手中的球是什么颜色的？&/p&&p&小明毕竟是最强王者，仍然很快得想到了答案，简称策略2，他的答案是这样的。&/p&&img src=&/v2-cf726dcdabded7b0fa916_b.png& data-rawwidth=&300& data-rawheight=&231& class=&content_image& width=&300&&&p&在这种情况下，小明知道了每种颜色小球的比例，比如橙色占比二分之一，如果我猜橙色，很有可能第一次就猜中了。所以，根据策略2，1/2的概率是橙色球，小明需要猜一次，1/4的概率是紫色球，小明需要猜两次，1/8的概率是蓝色球，小明需要猜三次，1/8的概率是青色球，小明需要猜三次，所以小明预期的猜题次数为：&/p&&p&H = 1/2 * 1 + 1/4 * 2 + 1/8 * 3 + 1/8 * 3=
1.75&/p&&br&&p&题目3：其实，爸爸只想让小明意识到自己的错误，并不是真的想罚他，所以拿来一个箱子，跟小明说：里面的球都是橙色，现在我从中拿出一个，你猜我手中的球是什么颜色？&/p&&p&最强王者怎么可能不知道，肯定是橙色，小明需要猜0次。&/p&&br&&p&上面三个题目表现出这样一种现象：针对特定概率为p的小球，需要猜球的次数 = &img src=&///equation?tex=%5Clog_2+%5Cfrac%7B1%7D%7Bp%7D& alt=&\log_2 \frac{1}{p}& eeimg=&1&& ，例如题目2中，1/4是紫色球， &img src=&///equation?tex=%5Clog_2+4& alt=&\log_2 4& eeimg=&1&&
= 2 次，1/8是蓝色球， &img src=&///equation?tex=%5Clog_2+8& alt=&\log_2 8& eeimg=&1&&
= 3次。那么，针对整个整体，预期的猜题次数为： &img src=&///equation?tex=%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7B1%7D%7Bp_k%7D& alt=&\sum_{k=1}^N p_k \log_2 \frac{1}{p_k}& eeimg=&1&& ，这就是&b&信息熵，&/b&上面三个题目的预期猜球次数都是由这个公式计算而来，第一题的信息熵为2，第二题的信息熵为1.75，最三题的信息熵为1&b& *&/b& &img src=&///equation?tex=%5Clog+1& alt=&\log 1& eeimg=&1&& = 0 &b&。&/b&那么信息熵代表着什么含义呢？&/p&&p&&b&信息熵代表的是随机变量或整个系统的不确定性，熵越大，随机变量或系统的不确定性就越大。&/b&上面题目1的熵 & 题目2的熵 & 题目3的熵。在题目1中，小明对整个系统一无所知，只能假设所有的情况出现的概率都是均等的，此时的熵是最大的。题目2中，小明知道了橙色小球出现的概率是1/2及其他小球各自出现的概率，说明小明对这个系统有一定的了解，所以系统的不确定性自然会降低，所以熵小于2。题目3中，小明已经知道箱子中肯定是橙色球，爸爸手中的球肯定是橙色的，因而整个系统的不确定性为0，也就是熵为0。所以，在什么都不知道的情况下，熵会最大，针对上面的题目1~~题目3，这个最大值是2，除此之外，其余的任何一种情况，熵都会比2小。&/p&&p&所以，每一个系统都会有一个真实的概率分布，也叫真实分布，题目1的真实分布为（1/4，1/4，1/4，1/4），题目2的真实分布为（1/2，1/4，1/8，1/8），而根据真实分布，我们能够找到一个最优策略，以最小的代价消除系统的不确定性，而这个代价大小就是&b&信息熵，记住，信息熵衡量了系统的不确定性，而我们要消除这个不确定性，所要付出的努力（猜题次数、编码长度等）的大小就是信息熵&/b&。具体来讲，题目1只需要猜两次就能确定任何一个小球的颜色，题目2只需要猜测1.75次就能确定任何一个小球的颜色。&/p&&p&现在回到题目2，假设小明只是钻石段位而已，智商没王者那么高，他使用了策略1，即&/p&&img src=&/v2-97e76bdbfcf75_b.png& data-rawwidth=&300& data-rawheight=&213& class=&content_image& width=&300&&&p&爸爸已经告诉小明这些小球的真实分布是（1/2，1/4, 1/8，1/8），但小明所选择的策略却认为所有的小球出现的概率相同，相当于忽略了爸爸告诉小明关于箱子中各小球的真实分布，而仍旧认为所有小球出现的概率是一样的，认为小球的分布为（1/4，1/4，1/4，1/4），这个分布就是&b&非真实分布&/b&。此时，小明猜中任何一种颜色的小球都需要猜两次，即1/2 * 2 + 1/4 * 2 + 1/8 * 2 + 1/8 * 2 = 2。&/p&&p&很明显，针对题目2，使用策略1是一个坏的选择，因为需要猜题的次数增加了，从1.75变成了2，小明少玩了1.75的王者荣耀呢。因此，当我们知道根据系统的真实分布制定最优策略去消除系统的不确定性时，我们所付出的努力是最小的，但并不是每个人都和最强王者一样聪明，我们也许会使用其他的策略（非真实分布）去消除系统的不确定性，就好比如我将策略1用于题目2（原来这就是我在白银的原因），那么，当我们使用非最优策略消除系统的不确定性，所需要付出的努力的大小我们该如何去衡量呢？&/p&&p&这就需要引入&b&交叉熵，其用来衡量在给定的真实分布下，使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小&/b&。&/p&&p&正式的讲，交叉熵的公式为： &img src=&///equation?tex=%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7B1%7D%7Bq_k%7D& alt=&\sum_{k=1}^N p_k \log_2 \frac{1}{q_k}& eeimg=&1&& ，其中 &img src=&///equation?tex=p_k& alt=&p_k& eeimg=&1&& 表示真实分布， &img src=&///equation?tex=q_k& alt=&q_k& eeimg=&1&& 表示非真实分布。例如上面所讲的将策略1用于题目2，真实分布 &img src=&///equation?tex=p_k+%3D+%28%5Cfrac+%7B1%7D%7B2%7D%2C%5Cfrac+%7B1%7D%7B4%7D%2C%5Cfrac+%7B1%7D%7B8%7D%2C%5Cfrac+%7B1%7D%7B8%7D%29& alt=&p_k = (\frac {1}{2},\frac {1}{4},\frac {1}{8},\frac {1}{8})& eeimg=&1&& ， 非真实分布 &img src=&///equation?tex=q_k+%3D+%28%5Cfrac+%7B1%7D%7B4%7D%2C%5Cfrac+%7B1%7D%7B4%7D%2C%5Cfrac+%7B1%7D%7B4%7D%2C%5Cfrac+%7B1%7D%7B4%7D%29& alt=&q_k = (\frac {1}{4},\frac {1}{4},\frac {1}{4},\frac {1}{4})& eeimg=&1&& ，交叉熵为 &img src=&///equation?tex=%5Cfrac%7B1%7D%7B2%7D+%2A+%5Clog_2+4+%2B+%5Cfrac%7B1%7D%7B4%7D+%2A+%5Clog_2+4+%2B+%5Cfrac%7B1%7D%7B8%7D+%2A+%5Clog_2+4+%2B+%5Cfrac%7B1%7D%7B8%7D+%2A+%5Clog_2+4+%3D+2& alt=&\frac{1}{2} * \log_2 4 + \frac{1}{4} * \log_2 4 + \frac{1}{8} * \log_2 4 + \frac{1}{8} * \log_2 4 = 2& eeimg=&1&&
，比最优策略的1.75来得大。&/p&&p&因此，交叉熵越低，这个策略就越好，最低的交叉熵也就是使用了真实分布所计算出来的信息熵，因为此时 &img src=&///equation?tex=p_k+%3D+q_k& alt=&p_k = q_k& eeimg=&1&& ，交叉熵 = 信息熵。这也是为什么在机器学习中的分类算法中，我们总是最小化交叉熵，因为交叉熵越低，就证明由算法所产生的策略最接近最优策略，也间接证明我们算法所算出的非真实分布越接近真实分布。&/p&&br&&p&最后，我们如何去衡量不同策略之间的差异呢？这就需要用到&b&相对熵，其用来衡量两个取值为正的函数或概率分布之间的差异&/b&，即：&/p&&p&KL(f(x) || g(x)) = &img src=&///equation?tex=%5Csum_%7B+x+%5Cin+X%7D+f%28x%29+%2A+%5Clog_2+%5Cfrac%7Bf%28x%29%7D%7Bg%28x%29%7D& alt=&\sum_{ x \in X} f(x) * \log_2 \frac{f(x)}{g(x)}& eeimg=&1&&&/p&&p&针对上面的问题，我们想知道某个策略和最优策略之间的差异，则相对熵 = 某个策略的交叉熵 - 信息熵（根据系统真实分布计算而得的信息熵，为最优策略），公式如下：&/p&&p&KL（p || q） = H（p，q） - H（p） = &img src=&///equation?tex=+%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7B1%7D%7Bq_k%7D+-+%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7B1%7D%7Bp_k%7D+%3D+%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7Bp_k%7D%7Bq_k%7D& alt=& \sum_{k=1}^N p_k \log_2 \frac{1}{q_k} - \sum_{k=1}^N p_k \log_2 \frac{1}{p_k} = \sum_{k=1}^N p_k \log_2 \frac{p_k}{q_k}& eeimg=&1&&&/p&&p&所以将策略1用于题目2，所产生的相对熵为2 - 1.75 = 0.25.&/p&&br&&p&参考：&/p&&p&《数学之美》吴军&/p&&p&&a href=&///?target=https%3A//www.khanacademy.org/computing/computer-science/informationtheory/moderninfotheory/v/information-entropy& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Information entropy&i class=&icon-external&&&/i&&/a&&/p&&p&还有，小明同学，我帮你分析得这么清楚，快带我上王者。&/p&
讨论这个问题需要从香农的信息熵开始。小明在学校玩王者荣耀被发现了，爸爸被叫去开家长会，心里悲屈的很，就想法子惩罚小明。到家后，爸爸跟小明说：既然你犯错了，就要接受惩罚，但惩罚的程度就看你聪不聪明了。这样吧，我出一个题目，你猜答案，你每猜一…
已有帐号？
无法登录？
社交帐号登录
598 人关注
124 条内容
306 人关注
879 人关注
247 条内容
30252 人关注
1970 条内容G4算法实现与布局问题的相对熵算法研究—硕士毕业论文下载
很抱谦，您的浏览器并不支持 IFrame，请与管理员联系，也可。
G4算法实现与布局问题的相对熵算法研究
硕士博士毕业论文站内搜索
全站论文库
硕士博士论文库
普通期刊论文库
分类：→数理科学和化学论文→→
G4算法实现与布局问题的相对熵算法研究
[硕士论文]论文目录&致谢第1-6
页 中文摘要第6-7
页 ABSTRACT第7-11
页 1 绪论第11-25
页 · 布局问题概述第11-15
页 · 布局问题的起源第11
页 · 布局问题的分类第11-15
页 · 布局问题的研究现状第15-21
页 · 布局问题实体建模方法第15-16
页 · 布局问题建模研究现状第16-18
页 · 布局求解方法现状第18-21
页 · 课题的提出第21-22
页 · 本课题的来源及提出第21-22
页 · 课题的学术及工程意义第22
页 · 作者的主要工作和论文结构第22-24
页 · 本章小结第24-25
页 2 装盘问题的G4算法第25-42
页 · 动态规划法概要第25-28
页 · 动态规划的基本概念第26-28
页 · 动态规划的基本思想与实质第28
页 · 装盘问题G4算法的主要内容第28-34
页 · 装盘问题G4-结构定义第29-30
页 · 装盘问题G4启发式算法第30-34
页 · G4算法相关数据结构和程序框图设计第34-38
页 · G4算法相关数据结构第34-38
页 · 算法相关程序框图说明第38
页 · 实验验结果和分析第38-41
页 · 本章小结第41-42
页 3 交叉熵算法理论基础第42-51
页 · 熵、信息熵与交叉熵概念第42-44
页 · 熵的起源发展第42-43
页 · 信息熵与交叉熵第43-44
页 · 交叉熵模拟小概率事件的基本原理第44-46
页 · 交叉熵求解优化问题基本原理第46-47
页 · 交叉熵算法与经典元启发式算法的比较第47-50
页 · 本章小结第50-51
页 4 二维布局问题的交叉熵算法研究第51-62
页 · 交叉熵求解2D-R-ODP第51-57
页 · 随机样本的生成第52
页 · 2D-R-ODP的DROP和DROPF解码原则第52-56
页 · 采用交叉熵求解2D-R-ODP参数的更新第56-57
页 · 实验结果与对比第57-60
页 · 结论第60
页 · 本章小结第60-62
页 5 集装箱布局的交叉熵算法研究第62-71
页 · 集装箱布局的编码方法第63-64
页 · 集装箱布局的解码策略第64-67
页 · 参数更新方式第67-68
页 · 试验及其结果第68-70
页 · 结果分析第70
页 · 本章小结第70-71
页 6 总结与展望第71-73
页 · 全文总结第71-72
页 · 展望第72-73
页 参考文献第73-77
页 作者简历第77-79
页 学位论文数据集第79页
本篇论文共79页，
更多相关论文
栏 目 导 航
版权申明：本目录收录网站
生成，本站并未收录论文原文，如果你是作者，需要删除这篇论文目录，。
||||||||||
Copyright(C) All Rights Reserved如何通俗的解释交叉熵与相对熵? - 知乎452被浏览30620分享邀请回答该回答已被折叠 折叠原因：对问题或其他回答的评论02 条评论分享收藏感谢收起与世界分享知识、经验和见解<meta property="og:title" content="离散随机变量的相对熵和机器学习 KL divergence and Machine Learning">
<meta name="twitter:title" content="离散随机变量的相对熵和机器学习 KL divergence and Machine Learning">
离散随机变量的相对熵和机器学习 KL divergence and Machine Learning | ChangChun Master Li
熵和交叉熵 基础
相对熵 性质
证明一 Infomation inequality(信息不等性)
证明二 KL and maximum likelihood(极大似然估计相对熵最小)
熵和交叉熵
机器学习的核心问题 建立一个模型，它能够预测那种类型的数据是可能的，哪种不可能在信息论中，频繁出现的信息通常编码较短（如汉语中 的 是）
引入概念 熵$$ H(X)=-\sum_{k=1}^Kp(X=k)\log_2p(X=k) $$有离散随机变量X，有K个状态，服从分布p。熵的输入为随机变量的分布，输出为分布的不确定性。
例子 拥有最大熵的离散分布是平均分布，并且$H(X)=\log_2K$
X服从二项分布$$\begin{align}X\in{0,1}\ ,\ \ p(X=1) &=\theta,\ \ p(X=0)=1-\theta \\\Rightarrow H(X) &=-[\theta\log_2\theta + (1-\theta)log_2(1-\theta)] \\\end{align}$$
引入概念 交叉熵cross entropy
$$ H(p,q)=-\sum_kp_klogq_k $$可以看出，交叉熵是数据来源于p当为p编码平均需要的比特数（wikipedia：In information theory, the cross entropy between two probability distributions p and q over the same underlying set of events measures the average number of bits needed to identify an event drawn from the set）
与熵的关系$ H(p)=H(p,p) $
概念 KL divergence
KL散度也叫相对熵
用于衡量两种概率分布p和q不相似的程度$$ KL(p,q)=\sum_{k=1}^Kp_klog\frac{p_k}{q_k} $$
另一种形式$$ KL(p,q)=\sum_kp_k\log{p_k}-\sum_kp_k\log{q_k}=-H(p)+H(p,q) $$也就是说，相对熵是使用分布q为分布p的数据编码平均需要额外的比特数
性质 KL divergence
asymmetric.
相对熵不是距离
例子:$ P,Q\sim Bournuli(X) $$
P(X=0)=0.8, P(X=1)=0.2 Q(X=0)=0.5, Q(X=1)=0.5 $$
K(P,Q)=0.0837,\ \ K(Q,P)=0.0969 $
Nonnegativity.$$ \forall P,Q\ \ KL(P,Q)\geq0 $$$$ \text{and}\ KL(P,Q)=0\ \text{iff}\ P=Q $$
Chain rule for KL divergence.
定义: 两个条件分布P(X|Y), Q(X|Y)的相对熵$ KL(P(X|Y),Q(X|Y))=\sum_yP(y)(\sum_xP(x|y)\log\frac{P(x|y)}{Q(x|y)}) $
直观理解： P(X|Y = y) 和 Q(X|Y = y)) 对于随机变量y的期望
可以证明链式规则$$ KL(P(X,Y)|Q(X,Y))=KL(P(X)|Q(X))+KL(P(Y|X)|Q(Y|X)) $$
KL and maximum likelihood
对于密度估计问题，假如给定一个训练集
$ {x^{(i)};i=1,2,3\cdots n} $
经验分布$ \hat{P}(X)=\frac{1}{m}\sum_{i=1}^m1{x^{(i)}=x},\ \ \text{即}\hat{P}\text{是均值分布}$
我们有参数为$ \theta $的分布$ P_\theta $，可以发现$ \theta $的最大似然估计等于使得$ P_\theta $和$ \hat{P} $相对熵最小的$ \theta $，即
$$ \arg\min_\theta{KL(\hat{P}|P_\theta)}=\arg\max_\theta{\sum_{i=1}^{m}\log P_{\theta}(x^{(i)})} $$
$$ KL(P,Q)\geq0，当且仅当\ p = q\ 时，等号成立 $$
引理: 詹森不等式(Jensen’s inequality)$$ f\left(\sum_{i=1}^n\lambda_ix_i\right)\leq\sum_{i=1}^n\lambda_if(x_i) $$其中$ \lambda_i\geq0 $且$ \sum_{i=1}^n\lambda_i=1 $
推导:$$\begin{align}-KL(p|q) &= -\sum_{x\in A}p(x)\log\frac{p(x)}{q(x)}=\sum_{x\in A}p(x)\log\frac{q(x)}{p(x)} \\&\leq\log\sum_{x\in A}p(x)\frac{q(x)}{p(x)}=\log\sum_{x\in A}q(x) &\text{詹森不等式*}\\&\leq\log\sum_{x\in X}q(x)=log1=0 \\\text{其中}A = {x:\ p(x)&0}\end{align}$$
具有最大熵的离散分布是均值分布，更精确的表述是$ H(X)\leq\log|X| $其中$ |X| $是随机变量X所有的状态。p(x)为均值分布使得等号成立
使$ u(x)=1/|X| $$$\begin{align}0\ \le\ KL(p|u)\ &=\ \sum_xp(x)\log\frac{p(x)}{u(x)} \\&=\ \sum_xp(x)\log p(x)-\sum_xp(x)\log u(x) \\&=\ -H(X)+\log|X|\end{align}$$
不充分理由原则 principle of insufficient reason:
当没有理由去选择哪一个分布的时候，应该使用均值分布，KL可以用来创建满足特定限制的分布。
例如，高斯分布是满足两个力矩的限制具有最大熵的分布
KL and maximum likelihood对于密度估计问题，假如给定一个训练集$ {x^{(i)};i=1,2,3\cdots n} $
经验分布$ \hat{P}(X)=\frac{1}{m}\sum_{i=1}^m1{x^{(i)}=x},\ \ \text{即}\hat{P}\text{是均值分布}$
我们有参数为$ \theta $的分布$ P_\theta $，可以发现$ \theta $的最大似然估计等于使得$ P_\theta $和$ \hat{P} $相对熵最小的$ \theta $，即
$$ \arg\min_\theta{KL(\hat{P}|P_\theta)}=\arg\max_\theta{\sum_{i=1}^{m}\log_{\theta}P(x^{(i)})} $$
$$\begin{align}\arg \min_{\theta}KL(\hat{P}|P_{\theta})\ &=\ \arg \min_{\theta}\sum_x\hat{P}(x)\log\hat{P}(x)-\hat{P}(x)\log P_{\theta}(x) & \text{相对熵定义} \\&=\ \arg \min_{\theta}\sum_x-\hat{P}(x)\log P_{\theta}(x) & \text{去掉常量} \\&=\ \arg \max_{\theta}\sum_x\hat{P}(x)\log P_{\theta}(x) & \text{翻转符号} \\&=\ \arg \max_{\theta}\sum_x\frac{1}{m}\sum_{i=1}^m1{x^{(i)}=x}\log P_{\theta}(x) & \hat{P}\text{定义} \\&=\ \arg \max_{\theta}\frac{1}{m}\sum_{i=1}^m\sum_x1{x^{(i)}=x}\log P_{\theta}(x) & \text{变换求和顺序} \\&=\ \arg \max_{\theta}\frac{1}{m}\sum_{i=1}^m\log P_{\theta}(x^{(i)}) & \text{约减指示函数} \\&=\ \arg \max_{\theta}\sum_{i=1}^m\log P_{\theta}(x^{(i)}) \\\end{align}$$
相对熵应用ensemble集成算法transfer learning迁移学习}
1.75&/p&&br&&p&题目3：其实，爸爸只想让小明意识到自己的错误，并不是真的想罚他，所以拿来一个箱子，跟小明说：里面的球都是橙色，现在我从中拿出一个，你猜我手中的球是什么颜色？&/p&&p&最强王者怎么可能不知道，肯定是橙色，小明需要猜0次。&/p&&br&&p&上面三个题目表现出这样一种现象：针对特定概率为p的小球，需要猜球的次数 = &img src=&///equation?tex=%5Clog_2+%5Cfrac%7B1%7D%7Bp%7D& alt=&\log_2 \frac{1}{p}& eeimg=&1&& ，例如题目2中，1/4是紫色球， &img src=&///equation?tex=%5Clog_2+4& alt=&\log_2 4& eeimg=&1&&
= 2 次，1/8是蓝色球， &img src=&///equation?tex=%5Clog_2+8& alt=&\log_2 8& eeimg=&1&&
= 3次。那么，针对整个整体，预期的猜题次数为： &img src=&///equation?tex=%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7B1%7D%7Bp_k%7D& alt=&\sum_{k=1}^N p_k \log_2 \frac{1}{p_k}& eeimg=&1&& ，这就是&b&信息熵，&/b&上面三个题目的预期猜球次数都是由这个公式计算而来，第一题的信息熵为2，第二题的信息熵为1.75，最三题的信息熵为1&b& *&/b& &img src=&///equation?tex=%5Clog+1& alt=&\log 1& eeimg=&1&& = 0 &b&。&/b&那么信息熵代表着什么含义呢？&/p&&p&&b&信息熵代表的是随机变量或整个系统的不确定性，熵越大，随机变量或系统的不确定性就越大。&/b&上面题目1的熵 & 题目2的熵 & 题目3的熵。在题目1中，小明对整个系统一无所知，只能假设所有的情况出现的概率都是均等的，此时的熵是最大的。题目2中，小明知道了橙色小球出现的概率是1/2及其他小球各自出现的概率，说明小明对这个系统有一定的了解，所以系统的不确定性自然会降低，所以熵小于2。题目3中，小明已经知道箱子中肯定是橙色球，爸爸手中的球肯定是橙色的，因而整个系统的不确定性为0，也就是熵为0。所以，在什么都不知道的情况下，熵会最大，针对上面的题目1~~题目3，这个最大值是2，除此之外，其余的任何一种情况，熵都会比2小。&/p&&p&所以，每一个系统都会有一个真实的概率分布，也叫真实分布，题目1的真实分布为（1/4，1/4，1/4，1/4），题目2的真实分布为（1/2，1/4，1/8，1/8），而根据真实分布，我们能够找到一个最优策略，以最小的代价消除系统的不确定性，而这个代价大小就是&b&信息熵，记住，信息熵衡量了系统的不确定性，而我们要消除这个不确定性，所要付出的努力（猜题次数、编码长度等）的大小就是信息熵&/b&。具体来讲，题目1只需要猜两次就能确定任何一个小球的颜色，题目2只需要猜测1.75次就能确定任何一个小球的颜色。&/p&&p&现在回到题目2，假设小明只是钻石段位而已，智商没王者那么高，他使用了策略1，即&/p&&img src=&/v2-97e76bdbfcf75_b.png& data-rawwidth=&300& data-rawheight=&213& class=&content_image& width=&300&&&p&爸爸已经告诉小明这些小球的真实分布是（1/2，1/4, 1/8，1/8），但小明所选择的策略却认为所有的小球出现的概率相同，相当于忽略了爸爸告诉小明关于箱子中各小球的真实分布，而仍旧认为所有小球出现的概率是一样的，认为小球的分布为（1/4，1/4，1/4，1/4），这个分布就是&b&非真实分布&/b&。此时，小明猜中任何一种颜色的小球都需要猜两次，即1/2 * 2 + 1/4 * 2 + 1/8 * 2 + 1/8 * 2 = 2。&/p&&p&很明显，针对题目2，使用策略1是一个坏的选择，因为需要猜题的次数增加了，从1.75变成了2，小明少玩了1.75的王者荣耀呢。因此，当我们知道根据系统的真实分布制定最优策略去消除系统的不确定性时，我们所付出的努力是最小的，但并不是每个人都和最强王者一样聪明，我们也许会使用其他的策略（非真实分布）去消除系统的不确定性，就好比如我将策略1用于题目2（原来这就是我在白银的原因），那么，当我们使用非最优策略消除系统的不确定性，所需要付出的努力的大小我们该如何去衡量呢？&/p&&p&这就需要引入&b&交叉熵，其用来衡量在给定的真实分布下，使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小&/b&。&/p&&p&正式的讲，交叉熵的公式为： &img src=&///equation?tex=%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7B1%7D%7Bq_k%7D& alt=&\sum_{k=1}^N p_k \log_2 \frac{1}{q_k}& eeimg=&1&& ，其中 &img src=&///equation?tex=p_k& alt=&p_k& eeimg=&1&& 表示真实分布， &img src=&///equation?tex=q_k& alt=&q_k& eeimg=&1&& 表示非真实分布。例如上面所讲的将策略1用于题目2，真实分布 &img src=&///equation?tex=p_k+%3D+%28%5Cfrac+%7B1%7D%7B2%7D%2C%5Cfrac+%7B1%7D%7B4%7D%2C%5Cfrac+%7B1%7D%7B8%7D%2C%5Cfrac+%7B1%7D%7B8%7D%29& alt=&p_k = (\frac {1}{2},\frac {1}{4},\frac {1}{8},\frac {1}{8})& eeimg=&1&& ， 非真实分布 &img src=&///equation?tex=q_k+%3D+%28%5Cfrac+%7B1%7D%7B4%7D%2C%5Cfrac+%7B1%7D%7B4%7D%2C%5Cfrac+%7B1%7D%7B4%7D%2C%5Cfrac+%7B1%7D%7B4%7D%29& alt=&q_k = (\frac {1}{4},\frac {1}{4},\frac {1}{4},\frac {1}{4})& eeimg=&1&& ，交叉熵为 &img src=&///equation?tex=%5Cfrac%7B1%7D%7B2%7D+%2A+%5Clog_2+4+%2B+%5Cfrac%7B1%7D%7B4%7D+%2A+%5Clog_2+4+%2B+%5Cfrac%7B1%7D%7B8%7D+%2A+%5Clog_2+4+%2B+%5Cfrac%7B1%7D%7B8%7D+%2A+%5Clog_2+4+%3D+2& alt=&\frac{1}{2} * \log_2 4 + \frac{1}{4} * \log_2 4 + \frac{1}{8} * \log_2 4 + \frac{1}{8} * \log_2 4 = 2& eeimg=&1&&
，比最优策略的1.75来得大。&/p&&p&因此，交叉熵越低，这个策略就越好，最低的交叉熵也就是使用了真实分布所计算出来的信息熵，因为此时 &img src=&///equation?tex=p_k+%3D+q_k& alt=&p_k = q_k& eeimg=&1&& ，交叉熵 = 信息熵。这也是为什么在机器学习中的分类算法中，我们总是最小化交叉熵，因为交叉熵越低，就证明由算法所产生的策略最接近最优策略，也间接证明我们算法所算出的非真实分布越接近真实分布。&/p&&br&&p&最后，我们如何去衡量不同策略之间的差异呢？这就需要用到&b&相对熵，其用来衡量两个取值为正的函数或概率分布之间的差异&/b&，即：&/p&&p&KL(f(x) || g(x)) = &img src=&///equation?tex=%5Csum_%7B+x+%5Cin+X%7D+f%28x%29+%2A+%5Clog_2+%5Cfrac%7Bf%28x%29%7D%7Bg%28x%29%7D& alt=&\sum_{ x \in X} f(x) * \log_2 \frac{f(x)}{g(x)}& eeimg=&1&&&/p&&p&针对上面的问题，我们想知道某个策略和最优策略之间的差异，则相对熵 = 某个策略的交叉熵 - 信息熵（根据系统真实分布计算而得的信息熵，为最优策略），公式如下：&/p&&p&KL（p || q） = H（p，q） - H（p） = &img src=&///equation?tex=+%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7B1%7D%7Bq_k%7D+-+%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7B1%7D%7Bp_k%7D+%3D+%5Csum_%7Bk%3D1%7D%5EN+p_k+%5Clog_2+%5Cfrac%7Bp_k%7D%7Bq_k%7D& alt=& \sum_{k=1}^N p_k \log_2 \frac{1}{q_k} - \sum_{k=1}^N p_k \log_2 \frac{1}{p_k} = \sum_{k=1}^N p_k \log_2 \frac{p_k}{q_k}& eeimg=&1&&&/p&&p&所以将策略1用于题目2，所产生的相对熵为2 - 1.75 = 0.25.&/p&&br&&p&参考：&/p&&p&《数学之美》吴军&/p&&p&&a href=&///?target=https%3A//www.khanacademy.org/computing/computer-science/informationtheory/moderninfotheory/v/information-entropy& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Information entropy&i class=&icon-external&&&/i&&/a&&/p&&p&还有，小明同学，我帮你分析得这么清楚，快带我上王者。&/p&
讨论这个问题需要从香农的信息熵开始。小明在学校玩王者荣耀被发现了，爸爸被叫去开家长会，心里悲屈的很，就想法子惩罚小明。到家后，爸爸跟小明说：既然你犯错了，就要接受惩罚，但惩罚的程度就看你聪不聪明了。这样吧，我出一个题目，你猜答案，你每猜一…
已有帐号？
无法登录？
社交帐号登录
598 人关注
124 条内容
306 人关注
879 人关注
247 条内容
30252 人关注
1970 条内容G4算法实现与布局问题的相对熵算法研究—硕士毕业论文下载
很抱谦，您的浏览器并不支持 IFrame，请与管理员联系，也可。
G4算法实现与布局问题的相对熵算法研究
硕士博士毕业论文站内搜索
全站论文库
硕士博士论文库
普通期刊论文库
分类：→数理科学和化学论文→→
G4算法实现与布局问题的相对熵算法研究
[硕士论文]论文目录&致谢第1-6
页 中文摘要第6-7
页 ABSTRACT第7-11
页 1 绪论第11-25
页 · 布局问题概述第11-15
页 · 布局问题的起源第11
页 · 布局问题的分类第11-15
页 · 布局问题的研究现状第15-21
页 · 布局问题实体建模方法第15-16
页 · 布局问题建模研究现状第16-18
页 · 布局求解方法现状第18-21
页 · 课题的提出第21-22
页 · 本课题的来源及提出第21-22
页 · 课题的学术及工程意义第22
页 · 作者的主要工作和论文结构第22-24
页 · 本章小结第24-25
页 2 装盘问题的G4算法第25-42
页 · 动态规划法概要第25-28
页 · 动态规划的基本概念第26-28
页 · 动态规划的基本思想与实质第28
页 · 装盘问题G4算法的主要内容第28-34
页 · 装盘问题G4-结构定义第29-30
页 · 装盘问题G4启发式算法第30-34
页 · G4算法相关数据结构和程序框图设计第34-38
页 · G4算法相关数据结构第34-38
页 · 算法相关程序框图说明第38
页 · 实验验结果和分析第38-41
页 · 本章小结第41-42
页 3 交叉熵算法理论基础第42-51
页 · 熵、信息熵与交叉熵概念第42-44
页 · 熵的起源发展第42-43
页 · 信息熵与交叉熵第43-44
页 · 交叉熵模拟小概率事件的基本原理第44-46
页 · 交叉熵求解优化问题基本原理第46-47
页 · 交叉熵算法与经典元启发式算法的比较第47-50
页 · 本章小结第50-51
页 4 二维布局问题的交叉熵算法研究第51-62
页 · 交叉熵求解2D-R-ODP第51-57
页 · 随机样本的生成第52
页 · 2D-R-ODP的DROP和DROPF解码原则第52-56
页 · 采用交叉熵求解2D-R-ODP参数的更新第56-57
页 · 实验结果与对比第57-60
页 · 结论第60
页 · 本章小结第60-62
页 5 集装箱布局的交叉熵算法研究第62-71
页 · 集装箱布局的编码方法第63-64
页 · 集装箱布局的解码策略第64-67
页 · 参数更新方式第67-68
页 · 试验及其结果第68-70
页 · 结果分析第70
页 · 本章小结第70-71
页 6 总结与展望第71-73
页 · 全文总结第71-72
页 · 展望第72-73
页 参考文献第73-77
页 作者简历第77-79
页 学位论文数据集第79页
本篇论文共79页，
更多相关论文
栏 目 导 航
版权申明：本目录收录网站
生成，本站并未收录论文原文，如果你是作者，需要删除这篇论文目录，。
||||||||||
Copyright(C) All Rights Reserved如何通俗的解释交叉熵与相对熵? - 知乎452被浏览30620分享邀请回答该回答已被折叠 折叠原因：对问题或其他回答的评论02 条评论分享收藏感谢收起与世界分享知识、经验和见解<meta property="og:title" content="离散随机变量的相对熵和机器学习 KL divergence and Machine Learning">
<meta name="twitter:title" content="离散随机变量的相对熵和机器学习 KL divergence and Machine Learning">
离散随机变量的相对熵和机器学习 KL divergence and Machine Learning | ChangChun Master Li
熵和交叉熵 基础
相对熵 性质
证明一 Infomation inequality(信息不等性)
证明二 KL and maximum likelihood(极大似然估计相对熵最小)
熵和交叉熵
机器学习的核心问题 建立一个模型，它能够预测那种类型的数据是可能的，哪种不可能在信息论中，频繁出现的信息通常编码较短（如汉语中 的 是）
引入概念 熵$$ H(X)=-\sum_{k=1}^Kp(X=k)\log_2p(X=k) $$有离散随机变量X，有K个状态，服从分布p。熵的输入为随机变量的分布，输出为分布的不确定性。
例子 拥有最大熵的离散分布是平均分布，并且$H(X)=\log_2K$
X服从二项分布$$\begin{align}X\in{0,1}\ ,\ \ p(X=1) &=\theta,\ \ p(X=0)=1-\theta \\\Rightarrow H(X) &=-[\theta\log_2\theta + (1-\theta)log_2(1-\theta)] \\\end{align}$$
引入概念 交叉熵cross entropy
$$ H(p,q)=-\sum_kp_klogq_k $$可以看出，交叉熵是数据来源于p当为p编码平均需要的比特数（wikipedia：In information theory, the cross entropy between two probability distributions p and q over the same underlying set of events measures the average number of bits needed to identify an event drawn from the set）
与熵的关系$ H(p)=H(p,p) $
概念 KL divergence
KL散度也叫相对熵
用于衡量两种概率分布p和q不相似的程度$$ KL(p,q)=\sum_{k=1}^Kp_klog\frac{p_k}{q_k} $$
另一种形式$$ KL(p,q)=\sum_kp_k\log{p_k}-\sum_kp_k\log{q_k}=-H(p)+H(p,q) $$也就是说，相对熵是使用分布q为分布p的数据编码平均需要额外的比特数
性质 KL divergence
asymmetric.
相对熵不是距离
例子:$ P,Q\sim Bournuli(X) $$
P(X=0)=0.8, P(X=1)=0.2 Q(X=0)=0.5, Q(X=1)=0.5 $$
K(P,Q)=0.0837,\ \ K(Q,P)=0.0969 $
Nonnegativity.$$ \forall P,Q\ \ KL(P,Q)\geq0 $$$$ \text{and}\ KL(P,Q)=0\ \text{iff}\ P=Q $$
Chain rule for KL divergence.
定义: 两个条件分布P(X|Y), Q(X|Y)的相对熵$ KL(P(X|Y),Q(X|Y))=\sum_yP(y)(\sum_xP(x|y)\log\frac{P(x|y)}{Q(x|y)}) $
直观理解： P(X|Y = y) 和 Q(X|Y = y)) 对于随机变量y的期望
可以证明链式规则$$ KL(P(X,Y)|Q(X,Y))=KL(P(X)|Q(X))+KL(P(Y|X)|Q(Y|X)) $$
KL and maximum likelihood
对于密度估计问题，假如给定一个训练集
$ {x^{(i)};i=1,2,3\cdots n} $
经验分布$ \hat{P}(X)=\frac{1}{m}\sum_{i=1}^m1{x^{(i)}=x},\ \ \text{即}\hat{P}\text{是均值分布}$
我们有参数为$ \theta $的分布$ P_\theta $，可以发现$ \theta $的最大似然估计等于使得$ P_\theta $和$ \hat{P} $相对熵最小的$ \theta $，即
$$ \arg\min_\theta{KL(\hat{P}|P_\theta)}=\arg\max_\theta{\sum_{i=1}^{m}\log P_{\theta}(x^{(i)})} $$
$$ KL(P,Q)\geq0，当且仅当\ p = q\ 时，等号成立 $$
引理: 詹森不等式(Jensen’s inequality)$$ f\left(\sum_{i=1}^n\lambda_ix_i\right)\leq\sum_{i=1}^n\lambda_if(x_i) $$其中$ \lambda_i\geq0 $且$ \sum_{i=1}^n\lambda_i=1 $
推导:$$\begin{align}-KL(p|q) &= -\sum_{x\in A}p(x)\log\frac{p(x)}{q(x)}=\sum_{x\in A}p(x)\log\frac{q(x)}{p(x)} \\&\leq\log\sum_{x\in A}p(x)\frac{q(x)}{p(x)}=\log\sum_{x\in A}q(x) &\text{詹森不等式*}\\&\leq\log\sum_{x\in X}q(x)=log1=0 \\\text{其中}A = {x:\ p(x)&0}\end{align}$$
具有最大熵的离散分布是均值分布，更精确的表述是$ H(X)\leq\log|X| $其中$ |X| $是随机变量X所有的状态。p(x)为均值分布使得等号成立
使$ u(x)=1/|X| $$$\begin{align}0\ \le\ KL(p|u)\ &=\ \sum_xp(x)\log\frac{p(x)}{u(x)} \\&=\ \sum_xp(x)\log p(x)-\sum_xp(x)\log u(x) \\&=\ -H(X)+\log|X|\end{align}$$
不充分理由原则 principle of insufficient reason:
当没有理由去选择哪一个分布的时候，应该使用均值分布，KL可以用来创建满足特定限制的分布。
例如，高斯分布是满足两个力矩的限制具有最大熵的分布
KL and maximum likelihood对于密度估计问题，假如给定一个训练集$ {x^{(i)};i=1,2,3\cdots n} $
经验分布$ \hat{P}(X)=\frac{1}{m}\sum_{i=1}^m1{x^{(i)}=x},\ \ \text{即}\hat{P}\text{是均值分布}$
我们有参数为$ \theta $的分布$ P_\theta $，可以发现$ \theta $的最大似然估计等于使得$ P_\theta $和$ \hat{P} $相对熵最小的$ \theta $，即
$$ \arg\min_\theta{KL(\hat{P}|P_\theta)}=\arg\max_\theta{\sum_{i=1}^{m}\log_{\theta}P(x^{(i)})} $$
$$\begin{align}\arg \min_{\theta}KL(\hat{P}|P_{\theta})\ &=\ \arg \min_{\theta}\sum_x\hat{P}(x)\log\hat{P}(x)-\hat{P}(x)\log P_{\theta}(x) & \text{相对熵定义} \\&=\ \arg \min_{\theta}\sum_x-\hat{P}(x)\log P_{\theta}(x) & \text{去掉常量} \\&=\ \arg \max_{\theta}\sum_x\hat{P}(x)\log P_{\theta}(x) & \text{翻转符号} \\&=\ \arg \max_{\theta}\sum_x\frac{1}{m}\sum_{i=1}^m1{x^{(i)}=x}\log P_{\theta}(x) & \hat{P}\text{定义} \\&=\ \arg \max_{\theta}\frac{1}{m}\sum_{i=1}^m\sum_x1{x^{(i)}=x}\log P_{\theta}(x) & \text{变换求和顺序} \\&=\ \arg \max_{\theta}\frac{1}{m}\sum_{i=1}^m\log P_{\theta}(x^{(i)}) & \text{约减指示函数} \\&=\ \arg \max_{\theta}\sum_{i=1}^m\log P_{\theta}(x^{(i)}) \\\end{align}$$
相对熵应用ensemble集成算法transfer learning迁移学习}
我要回帖
更多关于 相对论通俗解释 的文章
更多推荐
- ·谁给推荐一个3.13的70TBC魔兽世界70级公益服私服，装备能外拍的？
- ·怎样解除网络强制解封游戏账号号封锁
- ·植物大战僵尸植物僵尸二怎么过二左上角那里，那植物大战僵尸植物僵尸二怎么过什么什么怎么搞？
- ·怎么能生出儿子生个儿子啊，大家可以推荐嘛？
- ·野蛮人大作战卡卡比配什么隋宠2萨萨塔有什么技能？
- ·20172017年贵州农村信用社社招聘笔试过后多久出成绩
- ·哪位大神知道此女名字这个叫什么
- ·华林dds生物电疗仪骗局靠谱么？长期通电对人体伤害大么
- ·洋湖北大资源时光光理想家园离洋湖新城多远
- ·德国恩德斯豪斯液位音叉液位开关中压力a和b代表什么意思
- ·成都哪里有做钢边钢带木箱包装def56的？
- ·几年前容易自动钻孔机txlyjx的钢材为什么钻不动
- ·make cmake与makefilee cmake qmake都是什么，有什么区别
- ·网络学习平台显示重复进入同个公司会议室布置图片是什么原因
- ·关于做无创产前基因检测的实验室要哪些资质
- ·有移民倾向的福建学生真的拿不到澳洲移民局的签证条款签证吗
- ·韩语圣经离线朗读播放全集朗读下载
- ·动物生仔不够血腥，人生孩子怎么就很恐怖动物
- ·我脑胀一个多星期了后脑勺发胀是怎么回事事呢，之前还头晕过几天
- ·世界上哪个城市印度经济最发达的城市
- ·如何比特币通俗解释的解释交叉熵与相对熵
- ·《一千零一个烦恼读后感》读后感
- ·膝关节十字韧带断裂韧带断裂，这个病严重吗
- ·宝宝不缺钙可以补钙吗，除了补钙，食物中还有什么含钙量高的
- ·我是河北考生，艺体生，报考的江西考生报考外省二本科技师范大学，专业分己通过，分化课己过，今年为啥没录取？
- ·杏芎氯化钠注射液怎么读
- ·越自闭和逆境中消沉的名人例子了怎么办呢感觉自己不是一个特别内
- ·消化内科论文范文，肝病医生帮忙看下
- ·如何理解“抓关键词理解句子问题评价”与“多元评价”之间的关系
- ·为什么 《美团点评机器学习实践践
- ·怎么样可以搭一座人可以进去的力体的漂亮立体小房子的折法
- ·自控 阻尼行业竞争激烈程度指标的改变主要看哪些指标
- ·叔叔阿姨 求助1 设 设函数f x lnx x 1 f（x）=x的平方
- ·稳压二极管的二极管反向击穿后为什么可以复原？
