1、统计机器学习与数据挖掘技术与方法研讨班讲义信息论初步Introduction to Information Theory陈 翀提要n最优编码n自信息n熵n联合熵、条件熵n互信息n交叉熵nKL-divergence信息论nShannon 与20世纪40年代提出在非理想的通信信道内如何传输最大量的信息，包括n数据压缩(与熵相关)n传输率(信道容量)信息量的度量n在TIM领域，信息论被用来解决海量存储（文本压缩编码）推测不确定性-熵解释随机变量及其分布的关系-互信息、KL距离。噪声信道信源接收方XX信息的度量n信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如
2、一本五十万字的中文书到底有多少信息量。直到 1948 年，香农提出了“信息熵”的概念，才解决了对信息的量化问题。n一条信息的信息量大小和它的不确定性有直接的关系。比如说，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，则不需要太多的信息就能把它搞清楚。从这个角度可认为，信息量的度量就等于不确定性的多少。n例子：冠军队预测信息论基本概念n编码长度：信源发出的不同信号在传输中需要用多长的编码传输，能够节省对信道的占用，并在接收方获得不歧义的信息nEntropy（熵）：测量随机变量不确定性，反映混乱程度nMutual Informa
3、tion（互信息）：测量两个随机变量的相关/相互依赖程度。解释当已知一个变量时能对减少另一个变量不确定性起到多大的贡献。nKullback-Leibler divergence：比较两个分布的差异1.最优编码1.最优编码1.最优编码2.自信息n一个信源可按某种概率发出若干不同的信号，每个信号带有的信息量称为其自信息。信源：随机变量；信号：随机变量的取值n基于定性分析，自信息的特性应当是非负递增n具有这样的特性的函数有很多，人们构造出如下定义式：n：随机变量X的某个取值；P(n)：X取该值的概率3.熵n定义：设随机变量X，取值空间，为有限集合。X的分布密度为p(x)，p(x)=P(X=x)xX，
4、则该随机变量的取值不确定程度，即其熵为：当使用log2时，熵的单位为比特反映一个信源发出不同信号，具有的平均信息量。2()()()log()0log00,loglogxH XH pp xp xall possible valuesDefine 3.熵n熵的基本性质：H(X)0，等号表明确定场（无随机性）的熵最小H(X)log|X|，等号表明等概场的熵最大。从编码压缩的角度解释：X的取值越随机，它的编码越难以压缩。1()0.5()01()0.80()1fair coin p HeadH Xbetweenandbiased coin p Headcompletely biased p Head以抛
5、硬币为例，匀质、非匀质、完全不匀质时，抛掷结果的不确定性如下：P(Head)H(X)1.03.熵3.熵3.熵3.熵n一本五十万字的中文书平均有多少信息量？我们知道常用的汉字（一级二级国标）大约有 7000 字。假如每个字等概率，那么我们大约需要 13 个比特（即 13 位二进制数）表示一个汉字。但汉字的使用是不平衡的。实际上，前 10%的汉字占文本的 95%以上。因此，即使不考虑上下文的相关性，而只考虑每个汉字的独立的概率，那么，每个汉字的信息熵大约也只有 8-9 个比特。如果我们再考虑上下文相关性，每个汉字的信息熵只有5比特左右。所以，一本五十万字的中文书，信息量大约是 250 万比特。如果
6、用一个好的算法压缩一下，整本书可以存成一个 320KB 的文件。如果我们直接用两字节的国标编码存储这本书，大约需要 1MB 大小，是压缩文件的三倍。这两个数量的差距，在信息论中称作“冗余度”（redundancy)。需要指出的是我们这里讲的 250 万比特是个平均数，同样长度的书，所含的信息量可以差很多。如果一本书重复的内容很多，它的信息量就小，冗余度就大。不同语言的冗余度差别很大，而汉语在所有语言中冗余度是相对小的。这和人们普遍的认识“汉语是最简洁的语言”是一致的。3.熵在TIM中的用途nFeature selection:If we use only a few words to clas
7、sify docs,what kind of words should we use?P(C|“computer”=1)v.s.p(C|“the”=1):which is more random?(C is the category of the topics)nText compression:Some documents(less random)can be compressed more than others(more random)Can we quantify the“compressibility”?nIn general,given a random variable X fo
8、llowing distribution p(X),How do we measure the“randomness”of X?How do we design optimal coding for X?3.熵n熵率4.联合熵、条件熵H(Y|X)代表：当接代表：当接收方已知变量收方已知变量X时，时，信源方还需要提供信源方还需要提供平均多少信息才能平均多少信息才能传达变量传达变量Y5.互信息互信息的意义互信息的意义:-Measures how much reduction in uncertainty of X given info.about Y -Measures correlation b
9、etween X and Y -Related to the“channel capacity”in information theory5.互信息n一般计算中，常计算两个具体事件之间的互信息，称为“点互信息”6.交叉熵或者解释为：we encode X with a code optimized for a wrong distribution q?Expected#of bits=?显然有 H(X,q)H(X)，以p代表X，数学推导如下：()(,)()()log()()log()0()xxq xH p qH pp xp xq xp xp x:()(),1iiiiiiiiBy Jensen
10、s inequalityp f xfp xwheref is a convex function andp7.Kullback-Leibler Divergence D(p|q)Relative entropyWhat if we encode X with a code optimized for a wrong distribution q?How many bits would we waste?()(|)(,)()()log()xp xD p qH p qH pp xq xProperties:-D(p|q)0-D(p|q)D(q|p)-D(p|q)=0 iff p=q KL-dive
11、rgence度量同一随机变量的不同度量同一随机变量的不同分布的差异。它描述了因错用分布密度而分布的差异。它描述了因错用分布密度而增加的信息量。增加的信息量。Interpretation:-Fix p,D(p|q)and H(p,q)vary in the same way-If p is an empirical distribution,minimize D(p|q)or H(p,q)is equivalent to maximizing likelihood 也称为：相对熵、KL发散度、KL距离Cross Entropy,KL-Div,and Likelihood11/:(,.,)11:(
12、)(,)(,)0.NNiiData Sample for XYyyif xyEmpirical distributionp xy xy xo wN 11()()log()log()()log()()log()NiiNiixxL Yp XyL Yp Xyc xp XxNp xp x Likelihood:log Likelihood:1log()1log()(,)(|)()1,argmaxlog()argmin(,)argmin(,)argmin 2L YNppppL YH p pD ppH pNFix the dataL YH p pD p pN Criterion for selecting
13、 a good model Perplexity(p)Nxcxp/)()(What You Should Known信息论概念：编码长度、自信息、熵、交叉熵、条件熵、相对熵、互信息Know their definitions,how to compute themKnow how to interpret themKnow their relationshipsReference 信息论相关书籍 计算语言学讲义，常宝宝，北大计算语言学研究所 信息检索讲义,翟成祥，UIUC 数学之美(4)，(7)，(23)，吴军，google练习n2-1.任意摘录一段文字，统计这段文字中所有字符的相对频率。假设这些相对频率就是这些字符的概率，请计算其分布的熵。n2-2.任意取另外一段文字，按上述同样的方法计算字符分布的概率，然后计算两段文字中字符分布的KL距离。n2-3.举例说明（任意找两个分布p 和q），KL 距离是不对称的，即D(p|q)D(q|p)。
