熵、相对熵与互信息

1第二章熵、相对熵与互信息第二章熵、相对熵与互信息2.1熵2.2联合熵和条件熵2.3相对熵与互信息2.4熵与互信息的关系2.5熵、相对熵与互信息的链式法则2.6Jensen不等式及其结果2.7对数和不等式应用2.8数据处理不等式2.10费诺不等式要点第二章熵、相对熵与互信息¾¾“信息”“信息”不同于消息不同于消息（消息是表现形式，信息是实（消息是表现形式，信息是实质；质；¾¾““信息信息””不同于情报不同于情报，，情报的含义比“信息”情报的含义比“信息”窄的窄的多，一般只限于特殊的领域，是一类特殊的信息；多，一般只限于特殊的领域，是一类特殊的信息；¾¾信息不同于信号信息不同于信号，信号是承载消息的物理量；，信号是承载消息的物理量；¾¾信息不同于知识信息不同于知识，知识是人们根据某种目的，知识是人们根据某种目的,,从自然界从自然界收集得来的数据中整理、概括、提取得到的有价值的信收集得来的数据中整理、概括、提取得到的有价值的信息，是一种高层次的信息。息，是一种高层次的信息。z信息是信息论中昀基本、昀重要的概念，既抽象又复杂什么是信息第二章熵、相对熵与互信息消息：消息：用文字等能够被人们感觉器官所感知的形式，用文字等能够被人们感觉器官所感知的形式，把客观物质运动和主观思维活动的状态表达出来。把客观物质运动和主观思维活动的状态表达出来。知识：知识：一种具有普遍和概括性质的高层次的信息一种具有普遍和概括性质的高层次的信息，，以实践为基础，通过抽象思维，对客观事物规律性的以实践为基础，通过抽象思维，对客观事物规律性的概括。概括。情报：情报：是人们对于某个特定对象所见、所闻、所理解是人们对于某个特定对象所见、所闻、所理解而产生的知识而产生的知识。它们之间有着密切联系但不等同它们之间有着密切联系但不等同，信息的含义更深，信息的含义更深刻、广泛。刻、广泛。与信息相关的概念(1)第二章熵、相对熵与互信息信号：是信息的物理表达层，是一个物理量，是一个载荷信息的实体，可测量、可描述、可显示。消息：(或称为符号)是信息的数学表达层，可以定量地加以描述，是物理信号的进一步数学抽象。信号分类：‹离散(数字)消息，一组未知量，可用随机序列来描述：X=(X1…Xi…Xn)‹连续(模拟)消息，可用随机过程来描述：X(t,ω)与信息相关的概念(2)第二章熵、相对熵与互信息什么是信息目前尚未有统一定义，各种定义从不同的侧面和不同的层次来揭示信息的本质的。特莱(Hartley)在《信息传输》一文中提出：发信者所发出的信息，就是他在通信符号表中选择符号的具体方式。两个问题：¾该定义不涉及到信息的价值和具体内容，只考虑选择的方式。¾即使考虑选择的方法，但没有考虑各种可能选择方法的统计特性。关于信息的定义第二章熵、相对熵与互信息z难以准确定义和把握。z于任何一个概率分布，可以定义一个称为熵(entropy)的量，它具有许多特性符合度量信息的直观要求。z互信息(mutualinformation)，互信息是一种测度，用来度量一个随机变量包含另一个随机变量的信息量。熵恰好变成一个随机变量的自信息。z相对熵(relativeentropy)是个更广泛的量，它是刻画两个概率分布之间的距离的一种度量，而互信息又是它的特殊情形。z关系：密切相关，存在许多简单的共性，本章会论述其中的一些性质。z应用：通信、统计学、复杂度和博弈。什么是信息2第二章熵、相对熵与互信息§2.12.1熵熵1212()()()()KKaaaXpapapapx⎛⎞⎛⎞=⎜⎟⎜⎟⎝⎠⎝⎠信源模型：11Kiip==∑X中，包含该信源包含的所有可能输出的消息，p中包含对应消息的概率密度，各个消息的输出概率总和应该为1。如何度量信源的不确定性？第二章熵、相对熵与互信息定义一个离散随机变量X的熵H(X)定义为：121()(,,,)logKKnnnHXHppppp===−∑熵的定义熵的单位：2Æbit（常用），eÆnat，10Æhat备注：在上述定义中，约定0log0=0。熵是随机变量X的泛函，仅与X的分布相关。(2.1)第二章熵、相对熵与互信息解释：随机变量X的熵可看为随机变量log(1/p(X))的数学期望，其中p(x)为X的概率密度函数。即H(X)=E[log(1/p(X))](2.3)熵的进一步说明熵的进一步说明用E表示数学期望。若X～p(x)，则随机变量g(X)的期望为E[g(X)]=Σg(x)p(x)(2.2)特别地，当特别地，当g(X)=log(1/p(X))时的数学期望具有重要的时的数学期望具有重要的意义。意义。第二章熵、相对熵与互信息12()0.990.01Xaapx⎛⎞⎡⎤=⎜⎟⎢⎥⎝⎠⎣⎦12()0.50.5Yaapy⎛⎞⎡⎤=⎜⎟⎢⎥⎝⎠⎣⎦计算其熵，得：得：HH((XX)=0.08)=0.08（（bit/bit/符号）符号）HH((YY)=1)=1（（bit/bit/符号）符号）H(Y)＞H(X)，信源Y比信源X的平均不确定性要大。熵的含义熵的含义熵是整个集合的统计特性，平均意义上表征信源的总体特征。信源输出后，信息熵H(X)表示每个消息提供的平均信息量；在信源输出前，信息熵H(X)表示信源的平均不确定性；信息熵H(X)表征了变量X的随机性。例如例如，有两信源有两信源XX、、YY，，其概率空间分别其概率空间分别第二章熵、相对熵与互信息例：天气预报，有两个信源1,21()1/4,3/4aaXpx⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦1,22()1/2,1/2aaXpx⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦1134()log4log0.809443HX=+=211()log2log2122HX=+=则：说明第二个信源的平均不确定性更大一些熵的例子熵的例子第二章熵、相对熵与互信息熵的直观性质熵的直观性质z熵的这个定义与热力学中的熵有联系。z公理化定义：定义随机变量的熵必须满足的某些性质。z本定义：根据自然问题的答案确立定义，如“随机变量的昀短描述的平均长度是多少”。z熵定义的性质：引理2.1.1非负性：H(X)=0;由于0≤pi≤1,所以logpi≤0，　　　logpi≥0，则总有H(X)≥0。引理2.1.2换底公式：Hb(X)=(logba)Ha(X);3第二章熵、相对熵与互信息01()1Xpxpp⎛⎞⎛⎞=⎜⎟⎜⎟−⎝⎠⎝⎠例2.1.1设()log(1)log(1)()HXppppHp=−−−−此时该函数的图形如图2.1所示。熵的基本性质说明：上凸函数，确定事件熵为0，昀大值。(2.4)(2.5)特殊信源的熵(1)第二章熵、相对熵与互信息图2.1H(p)与p的关系图第二章熵、相对熵与互信息1111()2488abcdXpx⎛⎞⎛⎞⎜⎟=⎜⎟⎜⎟⎝⎠⎝⎠例2.1.2设111111117()loglogloglog224488884HX=−−−−=此时该结果表示，为描述此信源，每个符号至少需要7/4比特。后面将会看到，描述该信源的比特数在[H(X),H(X)+1]。(2.7)特殊信源的熵(2)第二章熵、相对熵与互信息二元信源模型：设二元随机变量(X,Y)可能的取值为(ak,bj)，k=1,2,…,K,j=1,2,…,J，二元信源模型为111213111213...(,)(,)(,)...(,)()KJKJababababXYpabpabpabpabpXY⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦11(,)1KJkjkjpab===∑∑§2.22.2联合熵与条件熵联合熵与条件熵第二章熵、相对熵与互信息定义仿照一元熵的定义，联合熵定义为：11(,)(,)log(,)KJkjkjkjHXYpabpab===−∑∑称为二元随机变量(X,Y)的联合熵，是二元随机变量的不确定性度量。同样，联合熵也可以看为是-logp(X,Y)的数学期望，即H(X,Y)=-E[logp(X,Y)](2.9)(2.8)联合熵第二章熵、相对熵与互信息条件熵条件熵定义若(X,Y)~p(x,y)，则条件熵H(Y|X)定义为11(|)()(|)(,)log(|)xKJkjjkkjHYXpxHYXxpabpba∈=====−∑∑∑X它是X取值ak条件下Y的熵H(Y|ak)的平均值，H(Y|ak)称为X取值ak条件Y的条件熵。(2.12)(2.10)4第二章熵、相对熵与互信息Th2.2.1Th2.2.1（链式法则）：（链式法则）：H(X,Y)=H(X)+H(Y|X)。11(,)(,)log(,)KJkjkjkjHpabpab===−∑∑XY11(,)log(()(|))KJkjkjkkjpabpapba===−∑∑11()log()(|)(|)KJkkjkkjpapapbaHYX===−+∑∑()(|)HXHYX=+1111()(|)log()(,)log(|)KJKJkjkkkjjkkjkjpapbapapabpba=====−−∑∑∑∑条件熵与联合熵关系第二章熵、相对熵与互信息(,)()()HXYHXHY=+独立：p(ak,bj)=p(ak)p(bj)p(ak|bj)=p(ak),p(bj|ak)=p(bj)(,)()(|)()(|)HXYHXHYXHYHXY=+=+(|)()(|)()HXYHXHYXHY==概括：联合熵等于单个随机变量熵之和；条件熵等于无条件熵（绝对熵）。简单推广简单推广推论推论：：第二章熵、相对熵与互信息4321XY1/41/161/161/810001/161/161/161/321/321/81/321/321/16432例2.2.1有两个同时输出的信源X和Y，信源符号为{1，2，3，4}，已知p(x,y)的分布如下表。求联合信源的联合熵和条件熵。联合熵和条件熵例子第二章熵、相对熵与互信息()()()()(1/4)1/2,1/4,1/8,1/8(1/4)1/2,1/4,1/8,1/8(1/4)1/4,1/4,1/4,1/4(1/4)1,0,0,0(1/4)(7/4)(1/4)(7/4)(1/4)2(1/4)0HHHH=+++=×+×+×+×解：信源X,Y的边际分布分别为：(1/2,1/4,1/8,1/8)，(1/4,1/4,1/4,1/4)则H(X)=7/4,H(Y)=2。41(|)()(|)iHXYpYiHXYi====∑11/8(/)BitSymbol=(2.22)(2.25)(2.23)第二章熵、相对熵与互信息(,)()()HXYHXHY≤+一般情况：(|)()(|)()HXYHXHYXHY≤≤稍后证明结论：条件熵不大于绝对熵。同样：H(Y|X)=13/8比特，H(X,Y)=27/8比特。H(Y|X)≠H(X,Y)。第二章熵、相对熵与互信息“条件熵不大于绝对熵”是平均意义下的结论。如对某个ak来说，H(Y|ak)H(Y)，H(Y|ak)=H(Y)，H(Y|ak)H(Y)三种情况均有可能。同样，对某个bj来说，H(X|bj)H(X)，H(X|bj)=H(X)，H(X|bj)H(X)，三种情况亦有可能。注意5第二章熵、相对熵与互信息()()HXYHX=()()HXYHY=若X与Y有确定的函数关系，且X可以完全确定Y（或Y完全确定X），则H(Y|X)＝0（或H(X|Y)＝0）。故或确定关系第二章熵、相对熵与互信息Kullback(1903Kullback(1903--1994)1994)§2.3相对熵与互信息相对熵(relativeentropy)也称为鉴别信息(discriminationinformation)：两种概率分布之间差异性的度量，又称为Kullback熵。第二章熵、相对熵与互信息KullbackKullback简介简介1903－1994，美国密码学家和数学家；大学毕业后回到中学教书，后离职；1930年成为美军“信号智能服务(SIS)”三专家之一，该单位后发展成为NSA；直到1962退休，一直担任NSA的首席科学家；退休后任教于华盛顿大学。第二章熵、相对熵与互信息概述概述z熵是随机变量不确定度的度量。z相对熵(relativeentropy)是两个随机分布之间距离的度量。z在统计学中，它对应的是似然比的对数期望。z意