《信息论初步课件.ppt》由会员分享，可在线阅读，更多相关《信息论初步课件.ppt（27页珍藏版）》请在三一办公上搜索。
1、统计机器学习与数据挖掘技术与方法研讨班讲义,信息论初步Introduction to Information Theory,陈 翀,提要,最优编码自信息熵联合熵、条件熵互信息交叉熵KL-divergence,信息论,Shannon 与20世纪40年代提出在非理想的通信信道内如何传输最大量的信息，包括数据压缩(与熵相关)传输率 (信道容量)信息量的度量在TIM领域，信息论被用来解决海量存储（文本压缩编码）推测不确定性-熵解释随机变量及其分布的关系-互信息、KL距离。,信息的度量,信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多
2、少信息量。直到 1948 年，香农提出了“信息熵” 的概念，才解决了对信息的量化问题。一条信息的信息量大小和它的不确定性有直接的关系。比如说，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，则不需要太多的信息就能把它搞清楚。从这个角度可认为，信息量的度量就等于不确定性的多少。例子：冠军队预测,信息论基本概念,编码长度：信源发出的不同信号在传输中需要用多长的编码传输，能够节省对信道的占用，并在接收方获得不歧义的信息Entropy（熵）：测量随机变量不确定性，反映混乱程度Mutual Information（互信息）：测量两个随机
3、变量的相关/相互依赖程度。解释当已知一个变量时能对减少另一个变量不确定性起到多大的贡献。Kullback-Leibler divergence：比较两个分布的差异,1.最优编码,1.最优编码,1.最优编码,2.自信息,一个信源可按某种概率发出若干不同的信号，每个信号带有的信息量称为其自信息。信源：随机变量；信号：随机变量的取值基于定性分析，自信息的特性应当是非负递增具有这样的特性的函数有很多，人们构造出如下定义式：n ：随机变量X的某个取值；P(n )：X取该值的概率,3.熵,定义：设随机变量X，取值空间，为有限集合。X的分布密度为p(x)，p(x)=P(X=x) xX，则该随机变量的取值不确
4、定程度，即其熵为：当使用log2时，熵的单位为比特反映一个信源发出不同信号，具有的平均信息量。,3.熵,熵的基本性质：H(X) 0，等号表明确定场（无随机性）的熵最小H(X) log|X|，等号表明等概场的熵最大。从编码压缩的角度解释：X的取值越随机，它的编码越难以压缩。,以抛硬币为例，匀质、非匀质、完全不匀质时，抛掷结果的不确定性如下：,P(Head),H(X),1.0,3.熵,3.熵,3.熵,3.熵,一本五十万字的中文书平均有多少信息量？我们知道常用的汉字（一级二级国标）大约有 7000 字。假如每个字等概率，那么我们大约需要 13 个比特（即 13 位二进制数）表示一个汉字。但汉字的使用
5、是不平衡的。实际上，前 10% 的汉字占文本的 95% 以上。因此，即使不考虑上下文的相关性，而只考虑每个汉字的独立的概率，那么，每个汉字的信息熵大约也只有 8-9 个比特。如果我们再考虑上下文相关性，每个汉字的信息熵只有5比特左右。所以，一本五十万字的中文书，信息量大约是 250 万比特。如果用一个好的算法压缩一下，整本书可以存成一个 320KB 的文件。如果我们直接用两字节的国标编码存储这本书，大约需要 1MB 大小，是压缩文件的三倍。这两个数量的差距，在信息论中称作“冗余度”（redundancy)。 需要指出的是我们这里讲的 250 万比特是个平均数，同样长度的书，所含的信息量可以差很
6、多。如果一本书重复的内容很多，它的信息量就小，冗余度就大。 不同语言的冗余度差别很大，而汉语在所有语言中冗余度是相对小的。这和人们普遍的认识“汉语是最简洁的语言”是一致的。,3.熵在TIM中的用途,Feature selection: If we use only a few words to classify 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)Text com
7、pression: Some documents (less random) can be compressed more than others (more random)Can we quantify the “compressibility”? In general, given a random variable X following distribution p(X), How do we measure the “randomness” of X? How do we design optimal coding for X?,3. 熵,熵率,4.联合熵、条件熵,H(Y|X)代表：
8、当接收方已知变量X时，信源方还需要提供平均多少信息才能传达变量Y,5.互信息,互信息的意义: - Measures how much reduction in uncertainty of X given info. about Y - Measures correlation between X and Y - Related to the “channel capacity” in information theory,5.互信息,一般计算中，常计算两个具体事件之间的互信息，称为“点互信息”,6.交叉熵,或者解释为： we encode X with a code optimized fo
9、r a wrong distribution q?Expected # of bits=?,显然有 H(X,q) H(X)，以p代表X，数学推导如下：,7.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?,Properties: - D(p|q)0 - D(p|q)D(q|p) - D(p|q)=0 iff p=q,KL-divergence度量同
10、一随机变量的不同分布的差异。它描述了因错用分布密度而增加的信息量。,Interpretation:Fix p, D(p|q) and H(p,q) vary in the same wayIf 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 Likelihood,Likelihood:,log Likelihood:,Criterion for selecti
11、ng a good model Perplexity(p),What You Should Know,信息论概念：编码长度、自信息、熵、交叉熵、条件熵、相对熵、互信息Know their definitions, how to compute themKnow how to interpret themKnow their relationships,Reference,信息论相关书籍计算语言学讲义，常宝宝，北大计算语言学研究所信息检索讲义, 翟成祥，UIUC数学之美(4)，(7)，(23)，吴军，google,练习,2-1. 任意摘录一段文字，统计这段文字中所有字符的相对频率。假设这些相对频率就是这些字符的概率，请计算其分布的熵。2-2. 任意取另外一段文字，按上述同样的方法计算字符分布的概率，然后计算两段文字中字符分布的KL距离。2-3. 举例说明（任意找两个分布p 和q ），KL 距离是不对称的，即D(p | q) D(q | p)。,
