信息论初步课件

信息论初步

IntroductiontoInformationTheory陈翀统计机器学习与数据挖掘技术与方法研讨班讲义信息论初步

IntroductiontoInformat1提要最优编码自信息熵联合熵、条件熵互信息交叉熵KL-divergence提要最优编码2信息论Shannon与20世纪40年代提出在非理想的通信信道内如何传输最大量的信息，包括数据压缩(与熵相关)传输率 (信道容量)信息量的度量在TIM领域，信息论被用来解决海量存储（文本压缩编码）推测不确定性-熵解释随机变量及其分布的关系-互信息、KL距离。。。。。。噪声信道信源接收方XX’信息论Shannon与20世纪40年代提出噪声信道信源接收3信息的度量信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到1948年，香农提出了“信息熵”的概念，才解决了对信息的量化问题。

一条信息的信息量大小和它的不确定性有直接的关系。比如说，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，则不需要太多的信息就能把它搞清楚。从这个角度可认为，信息量的度量就等于不确定性的多少。例子：冠军队预测信息的度量信息是个很抽象的概念。我们常常说信息很多，或者信息4信息论基本概念编码长度：信源发出的不同信号在传输中需要用多长的编码传输，能够节省对信道的占用，并在接收方获得不歧义的信息Entropy（熵）：测量随机变量不确定性，反映混乱程度MutualInformation（互信息）：测量两个随机变量的相关/相互依赖程度。解释当已知一个变量时能对减少另一个变量不确定性起到多大的贡献。Kullback-Leiblerdivergence：比较两个分布的差异信息论基本概念编码长度：信源发出的不同信号在传输中需要用多长51.最优编码1.最优编码61.最优编码1.最优编码71.最优编码1.最优编码82.自信息一个信源可按某种概率发出若干不同的信号，每个信号带有的信息量称为其自信息。信源：随机变量；信号：随机变量的取值基于定性分析，自信息的特性应当是非负递增具有这样的特性的函数有很多，人们构造出如下定义式：ωn：随机变量X的某个取值；P(ωn)：X取该值的概率2.自信息一个信源可按某种概率发出若干不同的信号，每个信号带93.熵定义：设随机变量X，取值空间Ω，Ω为有限集合。X的分布密度为p(x)，p(x)=P(X=x)x∈X，则该随机变量的取值不确定程度，即其熵为：当使用log2时，熵的单位为比特反映一个信源发出不同信号，具有的平均信息量。3.熵定义：103.熵熵的基本性质：H(X)≧0，等号表明确定场（无随机性）的熵最小H(X)≦log|X|，等号表明等概场的熵最大。 从编码压缩的角度解释：X的取值越随机，它的编码越难以压缩。以抛硬币为例，匀质、非匀质、完全不匀质时，抛掷结果的不确定性如下：P(Head)H(X)1.03.熵熵的基本性质：以抛硬币为例，匀质、非匀质、完全不匀质时113.熵3.熵123.熵3.熵133.熵3.熵143.熵一本五十万字的中文书平均有多少信息量？我们知道常用的汉字（一级二级国标）大约有7000字。假如每个字等概率，那么我们大约需要13个比特（即13位二进制数）表示一个汉字。但汉字的使用是不平衡的。实际上，前10%的汉字占文本的95%以上。因此，即使不考虑上下文的相关性，而只考虑每个汉字的独立的概率，那么，每个汉字的信息熵大约也只有8-9个比特。如果我们再考虑上下文相关性，每个汉字的信息熵只有5比特左右。所以，一本五十万字的中文书，信息量大约是250万比特。如果用一个好的算法压缩一下，整本书可以存成一个320KB的文件。如果我们直接用两字节的国标编码存储这本书，大约需要1MB大小，是压缩文件的三倍。这两个数量的差距，在信息论中称作“冗余度”（redundancy)。需要指出的是我们这里讲的250万比特是个平均数，同样长度的书，所含的信息量可以差很多。如果一本书重复的内容很多，它的信息量就小，冗余度就大。

不同语言的冗余度差别很大，而汉语在所有语言中冗余度是相对小的。这和人们普遍的认识“汉语是最简洁的语言”是一致的。3.熵一本五十万字的中文书平均有多少信息量？153.熵在TIM中的用途Featureselection:Ifweuseonlyafewwordstoclassifydocs,whatkindofwordsshouldweuse?P(C|“computer”=1)v.s.p(C|“the”=1):whichismorerandom?(Cisthecategoryofthetopics)Textcompression:Somedocuments(lessrandom)canbecompressedmorethanothers(morerandom)Canwequantifythe“compressibility”?Ingeneral,givenarandomvariableXfollowingdistributionp(X),Howdowemeasurethe“randomness”ofX?HowdowedesignoptimalcodingforX?3.熵在TIM中的用途Featureselection:163.熵熵率3.熵熵率174.联合熵、条件熵H(Y|X)代表：当接收方已知变量X时，信源方还需要提供平均多少信息才能传达变量Y4.联合熵、条件熵H(Y|X)代表：当接收方已知变量X时，信185.互信息5.互信息19互信息的意义:-MeasureshowmuchreductioninuncertaintyofXgiveninfo.aboutY-MeasurescorrelationbetweenXandY-Relatedtothe“channelcapacity”ininformationtheory互信息的意义:205.互信息一般计算中，常计算两个具体事件之间的互信息，称为“点互信息”5.互信息一般计算中，常计算两个具体事件之间的互信息，称为“216.交叉熵或者解释为：weencodeXwithacodeoptimizedforawrongdistributionq?Expected#ofbits=?显然有H(X,q)H(X)，以p代表X，数学推导如下：6.交叉熵或者解释为：weencodeXwitha227.Kullback-LeiblerDivergenceD(p||q)RelativeentropyWhatifweencodeXwithacodeoptimizedforawrongdistributionq?Howmanybitswouldwewaste?Properties:-D(p||q)0-D(p||q)D(q||p)-D(p||q)=0iffp=q

KL-divergence度量同一随机变量的不同分布的差异。它描述了因错用分布密度而增加的信息量。Interpretation:Fixp,D(p||q)andH(p,q)varyinthesamewayIfpisanempiricaldistribution,minimizeD(p||q)orH(p,q)isequivalenttomaximizinglikelihood

也称为：相对熵、KL发散度、KL距离7.Kullback-LeiblerDivergence23CrossEntropy,KL-Div,andLikelihoodLikelihood:logLikelihood:CriterionforselectingagoodmodelPerplexity(p)CrossEntropy,KL-Div,andLik24WhatYouShouldKnow信息论概念：编码长度、自信息、熵、交叉熵、条件熵、相对熵、互信息Knowtheirdefinitions,howtocomputethemKnowhowtointerpretthemKnowtheirrelationshipsWhatYouShouldKnow信息论概念：编码长度25Reference信息论相关书籍《计算语言学》讲义，常宝宝，北大计算语言学研究所《信息检索》讲义,翟成祥，UIUC数学之美(4)，(7)，(23)，吴军，googleReference信息论相关书籍