2008-应用信息论基础-张林-Chap-1-129208415

1第一章信息论的基本概念BasicConceptsofInformationTheory©THU2008–Allrightsreserved清华大学电子系－张林2008年9月17日2008年9月24日2008年10月8日概率空间概念回顾„概率空间是一个三元组…Ω为样本空间…Ξ为事件集，E∈Ξ，…P为概率度量，„公理：(,,)PΩXE⊂Ω:[0,1]P→X©THU2008–Allrightsreserved2„公理：C12311.,2.E3.,,...iiEEEEE∞=ΦΩ∈∈∈∈∈UXXXXX若，则若，则()1231()12.()1()3.,,...()CiiiiPPEPEEEEEPEΩ==−=∑U.若彼此没有交集，则P本章知识脉络图©THU2008–Allrightsreserved31.1信息熵（Entropy）1.1.1随机事件的自信息1.1.2信息熵1.1.3信息熵的唯一性定理1.1.4联合熵与条件熵1.1.5信息熵的性质©THU2008–Allrightsreserved41.1.1随机事件的自信息„直觉的定义…信息量等于传输该信息所用的代价…两个相同的信源所产生的信息量两倍于单个信源的信息量„但是，直觉的定义立即会引起置疑：©THU2008–Allrightsreserved5…一卡车Beatles的单曲CD盘，承载的信息量很大吗？…“很高兴见到你”，“平安到达”，“生日快乐”，“妈妈，母亲节快乐！”等电文传达的信息与其长度等效吗？信息是对不确定性的消除„天气预报消息量…夏天预报下雪和冬天预报下雪，哪个消息含有更大信息量？„骗子股票分析员„特工00111如何为他提供的服务定价？用户来找00111是为了消除对某种不确定性©THU2008–Allrightsreserved6…用户来找00111是为了消除对某种不确定性…所消除的不确定性越多，收费越高2随机事件的自信息„四个基本问题：…随机性与概率的关系；…概率为1的事件的信息量；…概率为0的事件的信息量；…两个独立事件的联合信息量。©THU2008–Allrightsreserved71212121111121212,(()()()()1()0()0(),(,)()()aaPaPafafaPafaPafaaafaafafa====∞=+设为两个随机事件，（1）若），则（2）若，则（3）若，则（4）若为独立事件，则自信息1()log()iiIaPa=对数底与信息的单位以2为底：bit(binaryunit)以e为底nat(natureunit)©THU2008–Allrightsreserved8以e为底：nat(natureunit)以10为底：Hart(Hartley)换算关系：1nat=1.44bit1Hart=3.32bit一般不加说明时，取以2为底。9自信息大于等于零关于自信息的评注()0iIa≥0()11log0,()iipapa≤≤⎛⎞∴≥⎜⎟⎝⎠Q，证毕。©THU2008–Allrightsreserved99不同底（单位）之间的自信息之间的换算关系()(log)()log()loglog()iiiiIaIapapaααβββαβα==证明：，证毕。例1.1“比特”的意义„八个灯泡串联，其中一个灯丝断了。„如何用最少的步骤定位出哪一个坏了？最少需要用三次二元判定来定位故障因此这个事件所含有的信息Step1Step2Step3©THU2008–Allrightsreserved10„最少需要用三次二元判定来定位故障。因此，这个事件所含有的信息量是3比特。例1.2洗牌的信息一副52张的扑克牌，现将其充分洗牌，试问：（1）任意特定排列所给出的平均信息量是多少？（2）若任意从这副牌中抽出13张，所示的点数都不同，应获得多少信息量？解：（1）获得某一个特定的排列的概率是多少？©THU2008–Allrightsreserved11（2）获得“顺子”的概率是多少？11()logloglog52!225.58bit1{}52!IXP===＝任意特定排列11115248444135211()loglog13.21bit{}IYCCCCPP==⋅⋅⋅＝得到一副“顺子”1.1.2信息熵„上一节我们定义了对于随机事件的自信息„对于一个随机系统，我们如何定义信息的度量？a1~p(a1)a2~p(a2)a3~p(a3)1.每一个随机事件都有自信息I(ai)2.针对系统，取各随机事件自信息的统计平均©THU2008–Allrightsreserved12某离散信源或随机实验…a3p(a3)a4~p(a4)a5~p(a5)an-1~p(an-1)an~p(an)平均：()()()()log()piiiiiiiEIapaIapapa==−∑∑3定义1.1离散随机变量的信息熵离散随机变量X的信息熵H(X)定义为：()()log()xHXpxpx∈=−∑X©THU2008–Allrightsreserved139H(.)的综量是随机变量的分布，而非取值90log0=0（x→0时，xlogx→0），概率为0的事件不影响信息熵例1.3„设随机变量X如下N元概率空间：„平均不确定性，即信息熵为：12112,,...,,1,,...,()NNnnNxxxXpppppx=⎛⎞⎛⎞==⎜⎟⎜⎟⎝⎠⎝⎠∑©THU2008–Allrightsreserved141()logNnnnHXpp==−∑例1.4设则有：101pXp⎧=⎨−⎩以概率以概率©THU2008–Allrightsreserved159H(.)是随机变量的分布上凸（Concave）函数9p=0→H(X)=0，确定性系统信息量为零9p=0.5→H(X)最大熵例1.5设12141818abXcd⎧⎪⎪⎪=⎨⎪⎪⎪⎩以概率以概率以概率以概率©THU2008–Allrightsreserved169平均意义下，确定X的取值所需要的问题数最少是1.75个9如果X是一个随机信源，表达之所需要的最小比特数存在于H(X)和H(X)+1之间9可见，熵与信息的有效表达密切相关1.1.3信息熵的唯一性定理„香农给出了信息熵函数满足的三个条件1.连续性2.等概时的单调增函数特性3.可加性„定理1.1：满足上述三个条件的随机变量不确定性度量函数为：©THU2008–Allrightsreserved17________度量函数为：121(,,...,)logNNnnnfpppCpp==−∑参见板书证明证明思路流程1.等概情况下熵函数的形式2.由等概走向有理数非等概的情况3.由有理数走向无理数©THU2008–Allrightsreserved184A.I.Khinchin给出的条件1.连续性2.可加性3.极值条件12111max(,,...,)(,,,)NfpppfNNN=L©THU2008–Allrightsreserved194.零概率事件不影响不确定性1212(,,...,)(,,,,0)NNfpppfppp=LKhinchin条件与香农条件等价1.1.4联合熵与条件熵„定义1.2:一对离散随机变量(X,Y)的联合熵定义为：©THU2008–Allrightsreserved209多元扩展9问题：H(X,Y)=H(X)+H(Y)?12121212(,,)(,,)log(,,)nnnnxxxHXXXpxxxpxxx∈∈∈=−∑∑∑XXXLLLL例1.6袋子里装3个黑球，2个白球。进行两个随机试验X和Y。情况一：X—从中随机取出一个球，看颜色，放回；Y—再从中随机取出一球，看颜色。情况二：X—从中随机取出一个球，看颜色，不放回；Y—再从中随机取出一球，看颜色。©THU2008–Allrightsreserved21研究联合试验（XY）的不确定性。参见板书9H(X,Y)≤H(X)+H(Y)，等号在X、Y独立时成立。9联合信息小于等于独立观察信息量之和9缺少的信息哪里去了？条件熵定义„定义1.3:若(X,Y)~p(x,y)，则条件熵H(Y|X)定义为：©THU2008–Allrightsreserved22自己证明：9若X,Y统计独立，则H(X|Y)=H(X)，H(Y|X)=H(Y)定理1.2：H(X,Y)=H(X)+H(Y|X)自己证明：9H(X,Y|Z)=H(X|Z)+H(Y|X,Z)9H(X,Y)=H(Y)+H(X|Y)9若X,Y统计独立，H(X,Y)=H(X)+H(Y)证明参见板书©THU2008–Allrightsreserved23推论1.3：设随机变量X1,X2,…,Xn满足分布p(x1,x2,…,xn)，则证明参见板书例1.7设(X,Y)服从以下联合分布：„©THU2008–Allrightsreserved24„X的边缘分布为，H(X)=1.75比特„Y的边缘分布为，H(Y)=2比特„类似地，比特„比特51.1.5信息熵的性质„性质1.1对称性„性质1.2非负性H(p)≥0„性质1.3可加性H(X,Y)=H(X)+H(Y|X)…定理12与推论13),...,,(),...,,()()2()1(21NkkkNpppHpppH=©THU2008–Allrightsreserved25…定理1.2与推论1.3„性质1.4条件减少熵H(X|Y)≤H(X)…知道了统计相关性的变量，则可以减少不确定性…统计平均意义上条件减少不确定性，但是针对具体的Y取值则不一定思考题：证明最大离散熵定理„性质1.5离散随机变量X在等概率分布的时，熵取得________最大值。12111(,,...,)(,,...,)loglogNHpppHNNNN≤==X证明参见板书©THU2008–Allrightsreserved26证明参见板书1.2互信息与鉴别信息1.2.1互信息1.2.2互信息的基本性质1.2.3似然比与鉴别信息1.2.4熵、互信息与鉴别信息的关系©THU2008–Allrightsreserved271.2.1互信息„事物是普遍联系的，随机变量之间也存在相关关系©THU2008–Allrightsreserved28„如何从信息的角度刻画X与Y之间的相关程度？…单独观察X，得到的信息量是H(X)…已知Y之后，X的信息量变为H(X|Y)…了解了Y之后，X的信息量减少了H(X)－H(X|Y)…这个减少量是得知Y取值之后提供的关于X的信息离散互信息的定义„定义1.4:定义离散随机变量X与Y之间的互信息I(X;Y)为I(X;Y)=H(X)－H(X|Y)9也可以直接定义互信息为©THU2008–Allrightsreserved299I(X;Y)=H(X)+H(Y)－H(X,Y)9若X,Y独立，则I(X;Y)=09若X,Y一一映射，则I(X;Y)=H(X)(,)(;)(,)log()()xypxyIXYpxypxpy∈∈=∑∑XY从信道的角度看互信息定义„假定X是信道的输入，Y是信道的输出©THU2008–Allrightsreserved30„I(X;Y)表示了一个信道输入与输出之间的依存关系信道的传输能力„用p和Q＝[q(yj|xk)]J×K表示的互信息(;)IXY()()()()log()()xyxqyxIpxqyxpxqyx∈∈∈==∑∑∑p;QXYX6多变量的互信息„定义1.5:设有随机变量X,Y,Z，则定义(;,)()(,)(,)(,)IXYZHXHXYZHYZHYZX=−=−©THU2008–Allrightsreserved319也可以直接定义互信息为(,)(;,)(,,)log()(,,)(,,)log()(,)xyzxyzpxyzIXYZpxyzpxpxyzpxyzpxpyz∈∈∈∈∈∈==∑∑∑∑∑∑XYZXYZ多变量的条件互信息„定义1.6:设有随机变量X,Y,Z，则定义I(X;Y|Z)=H(X|Z)－H(X|Y,Z)=H(Y|Z)－H(Y|X,Z)9也可以直接定义条件互信息为(|)pxyz∑∑∑©THU2008–Allrightsreserved329条件互信息非负。9I(X;Y|Z)=H(X|Z)－H(X,Y|Z)+H(Y|