离散信源与信息熵(上).ppt

北京交通大学信息科学研究所,信息论基础Elements of Information Theory北京交大计算机与信息技术学院信息科学研究所现代信号处理与通信研究室教学九楼六层北606主讲：丁晓明 TEL:51688636;ftp:/202.112.147.192/sopc;ssopcE,第二章：信息的度量与信息熵(The measure of Information&Entropy)2.1 自信息与条件自信息(selfinformation&conditional selfinformation)2.2 自互信息与条件自互信息(selfmutual information&conditional selfmutual information),信 息 论 基 础,第二章.信息的度量与信息熵,2.1 自信息与条件自信息(selfinformation&conditional selfinformation)2.1.1 自信息(自信息量)若一随机事件的概率为,它的自信息的数学定义为：,def,首先解释一下自信息与自信息量的区别：信息是概念上的涵义，而信息量则是有单位，有数值大小的量。自信息则是一个具体事件的不确定度，而自信息量应是不确定度的解除量，二者仅在该事件完全确知后信息量才等于自信息。换句话说：自信息反映的是随机事件的不确定度完全被解除后的信息量。自信息为什么一定是这样的定义？是否一定是对数形式？,2.1 自信息与条件自信息,因为信息是与随机事件的不定度密切相关，所以它的度量应是事件概率的函数。设：,4.两个独立的随机事件 和，它们联合事件的自信息，应是它们各自信息的和，即：要保证 的函数形式对上述四个公理化条件均满足，则此函数一定是对数形式；这就是定义的唯一性定理(uniqueness)。,2.1 自信息与条件自信息,例21 一副充分洗乱了的扑克牌(所给的牌是52张)，试问：任意一副特定排列所给出的自信息是多少？若从中抽取十三张牌，当给出的点数均不相同时可 得到多少信息量？题解：任意一特定排列，即意味着第一张牌的取法有52种；第二张牌的取法有51种；。一共有52!种排列，所以每一种排列的概率为：,2.1 自信息与条件自信息,若从m个元素中抽取n个元素 的取法就是组合：,1.,又因为要保证所抽取的牌中点数均不相同，则可设想以下排列，每一点数有四种花色；根据点数的位置构成13张的排列数：1，2，3，4，,13 4 4 4 4 4=,2.1 自信息与条件自信息,就是从52张牌中抽取13张牌的取法,则：,2.1 自信息与条件自信息,2.1.2 条件自信息(conditional self-information)定义：为条件自信息，同样有：,def,定义所表达的是一个联合事件xy，在某一个变量x(或y)被确知之后，另一个变量y(或x)还剩下的不确定度；或者说另一个变量y(或x)将还能带给接收者多么大的信息量。,例22 棋盘与棋子 题解：前提，当棋子落入棋盘的位置是任意的；若将棋盘的行数编号为，棋盘的列数编号为；则棋子落入任何一格的概率均相等，为：,设在一正方形棋盘上共有64个棋格,如甲随意将棋子放入一格中让乙猜棋子落入位置，（1）若将棋格按顺序编号，令乙猜测棋子所在棋格的顺序号？（2）若棋格按行与列编号，当甲将棋子所在的行号（列号）告诉乙后，在令乙猜棋子的位置？,2.1 自信息与条件自信息,如果编码为：,且，,例23.某地女孩中有25%是大学生,她们其中75%是身高1.6m以上；而女孩中身高1.6m以上者超过一半。题解：设女孩中有大学生的概率为，或者说女孩是大学生是一随机事件；另设女孩中身高超过1.6m以上者为另一随机事件，其概率为：，又因女孩大学生中超过1.6m者的概率为：所问：当某女孩是身高1.6m以上，且她是大学生,则我们将得到多少信息量？即：为什么不是求：,2.1 自信息与条件自信息,从以上例题可以看出联合事件的自信息与单一事件和条件自信息的关系，即联合事件的自信息可以看成是某一事件的自信息加上此事件发生后另一事件所剩的条件自信息。为什么联合事件的自信息一定大于条件自信息呢？这实际上是自信息与条件自信息之间的概念差别，我们从系统模型分析出发加深理解。,2.1 自信息与条件自信息,显然：,在信源发出消息事件 之后，将通过信道传输由信宿接收。如果信道是透明传输，则输出也一定是，但实际是收到加噪声后的事件。因此如何根据收端接受到的事件判断发方所发的消息，这是通信译码准则所决定。但我们所关心的是如何依据理论分析来得到这些判决准则？,2.1 自信息与条件自信息,首先我们认为发端是以某种先验概率(Prior Probability)在发送消息,（即信源在发送消息之前就以统计出的概率）而另一种概率：则表达当收端已收到某种消息后,再统计发端的发送概率，所以此条件概率称为后验概率(Posterior Probability)。,因此我们说事件 以及它所对应的先验概率 而定义出的自信息，所表达的不论事件是否有人接收这个事件它所固有的不确定度，或者说它所能带来的信息量。而消息事件 它所对应的条件概率是在收端接收到已干扰的消息后的后验概率,如果当它为1则属于透明传输；若，说明事件发生之后多少也解除了事件 的部分不定度，即得到了事件 的部分信息。由于概率越大，不定度越小。从客观上讲，条件自信息一定不会大于无条件的自信息。同时也反映出要得知一些条件，原事件的不定度一定会减少，最坏的情况也不过保持不变，即条件与事件无关。,2.1 自信息与条件自信息,第二章.信息的度量与信息熵,2.2 自互信息与条件自互信息(selfmutual information&conditional selfmutual information),2.2.1 自互信息,我们还是用系统模型来定义自互信息：,2.2.自互信息与条件自互信息,从上述系统模型中的两个随机变量的相互关系来分析自互信息的定义和概念，为方便先给出随机变量的概率空间及简写方式：随机变量 X,Y 分别由,；,给出，为了书写方便以后写成：,和,一.Definition of the self-mutual information:,2.2.自互信息与条件自互信息,下面介绍自互信息的物理概念：,两者之差即信息量的概念，所谓不确定度的解除量。因此我们说自互信息才是从数值上、概念上真正反映出信息量的含义。,为什么要称它为“互”？因为它具有互易性(mutuality):,2.2.自互信息与条件自互信息,Bayes theorem,(statistical constraint extent),下面我们再分析两个特例：,2.2.自互信息与条件自互信息,可见自信息仅是自互信息的一个特例，即当随机事件 所含的不定度完全被解除掉以后，它的自信息就是自互信息。另一特例，当事件 与事件 相互独立时：则：,这说明事件 无法互相提供信息量，因为它门之间统计独立。,2.2.自互信息与条件自互信息,性质一、任何两个事件之间的自互信息不可能大于其中任何一事件的自信息。,因为自互信息表达的是不定度的解除量，是所获得新知识。要获得信息量就意味不确定度应有减少，否则信息量为零。这是从客观来描述事实，因此所谓增加负信息，或者说增加了原有事物的不定度，应带有观察的主观性。,性质二、,2.2.自互信息与条件自互信息,例23.再举一个系统模型在理想状态下如何分析的实例。(Ideal Channel),2.2.自互信息与条件自互信息,2.2.自互信息与条件自互信息,同理：,2.2.自互信息与条件自互信息,二.Definition of the conditional self-mutual information:,如果：随机变量X和Y与及第三个随即变量Z分别属于三个不同的概率集合空间：,和,当这三个随机变量中任何一个确知后，另外两个变量之间的相互关系可由条件自互信息所定义。,前者表达的是当事件 给定之后，事件 与 之间的自互信息。,而后者所描述的是单个事件 与联合事件 之间的自互信息。,由于自信息的可加性的存在，指使这两者之间有下列的关系:,2.2.自互信息与条件自互信息,下面 我们再从例题中加深理解这两个定义的区别：,2.2.自互信息与条件自互信息,2.2.自互信息与条件自互信息,2.2.自互信息与条件自互信息,下面我们从数学性质出发来证明几个自互信息与条件自互信息的互换关系。证：对于任意三个离散随机变量x,y 和 z 存在着下列关系：,One-to-one mapping,2.2.自互信息与条件自互信息,有了自互信息的定义以及与条件自互信息的转换关系，使我们日常生活中的许多事件，可以用数学公式定量地描述出。也使我们的工程设计而有章可循。下面我再举一个实际工程问题验证有关自信息、自互信息和条件自互信息的定义及关系。,2.2.自互信息与条件自互信息,例24.实际信道传输分析,2.2.自互信息与条件自互信息,一个等概率信源有八种消息符号，用四比特的码字序列输入信道，其编码定义如上表；用实验测定上述码字中的每一个二进制符号经信道输出可得二元符号y,已知条件概率(信道特性)为:,2.2.自互信息与条件自互信息,例题分析：,由此可见，利用四比特代码传三比特信息，一定有纠错功能。,因为只考虑具体事件的关系，则没有熵或互信息的概念，仅是自互信息。,2.2.自互信息与条件自互信息,2.2.自互信息与条件自互信息,.解法一,.解法二,.解法三,.解法四,2.2.自互信息与条件自互信息,2.2.自互信息与条件自互信息,.解法二,2.2.自互信息与条件自互信息,.解法三,Xn之间相互独立；但无法保证yn之间相互独立。,2.2.自互信息与条件自互信息,.解法四,2.2.自互信息与条件自互信息,2.2.自互信息与条件自互信息,显然，还有两种解法要比以上两种解法的概念清晰：,解法一、,2.2.自互信息与条件自互信息,解法二、,2.2.自互信息与条件自互信息,Q.E.D.,第二章.信息的度量与信息熵,2.3 离散信源的信息熵(Entropy of the Discrete Source)单个消息事件的数学描述是随机变量(random variable)单个的消息序列的描述是随机矢量(random vector),而消息集合信源的数学描述就应是概率空间(probability space)。因此，离散信源的数学模型就是离散概率空间。当信源输出的消息符号其取值是有限个种类，则这是离散型随机变量，此信源称离散信源，其数学模型为：,一个消息事件的概率为,它的自信息是,这也是一个随机变量。(因消息不同，它所含有的不定度也不同.因而其自信息本身也是随机的。)显然不能用它来作为整个信源的信息测度。(或者说是信源功能描述)要找一个集合的总体特征，从数学上看是求数学期望(mathematical expectation)，所以特定义自信息的数学期望为信源客观上的平均信息量，称为信源的信息熵(Entropy)。Definition of Entropy:,2.3 离散信源的信息熵,def,“熵”这个名词来源与统计热分子力学，其物理含义是表示分子运动的不均匀性，或描述分子运动的混乱程度。物质越热其热熵越大即分子运动越快。我们借用熵的含义反映信源这个消息集合中的总体特征平均不确定度。(Average Uncertainty),所表示某一事件 的自信息，当且仅当在该事件发生之后其不定度完全解除掉，我们才能说获得了大小与 相当的信息量；而信息熵 反映出对每一个消息事件在集合 整体上的平均不定度，一般情况下它并不等于信源所发出的每一个消息后所获得的平均信息量。因为只有在无干扰的情况下，接收者准确无误的收到每一条消息后，同时也完全解除了它们的不定度时才能说接收者所获得的平均信息量等于信息熵。,2.3 离散信源的信息熵,从数学来看，信息熵的引出仅仅由一个随机变量 的统计平均处理 所得到集合的统计平均值而已。但从物理意义上看，两者产生了性质的突变，仍是一个随机变量(variable);而 已变成了常量(constant)，它是代表集合的总体特征。,信息熵与平均信息量的关系：,所以一般来讲，信源的信息熵 H 并不等于接收者所获得的平均信息量。从客观性来看，信息熵仅表征了信源发送信息能力的客观标志，它与此刻信源发不发消息？在发哪条消息？毫无相关！,2.3 离散信源的信息熵,因此我们讲信息熵并不反映从信源中平均能获多少信息量，而是从平均的意义上，代表信源所客观存在着发送信息的能力。,例25.,则信息熵分别为：,（参见P15）,2.3 离散信源的信息熵,前提：模一次球后再放回袋中，以不破坏概率试验条件，且一旦球拿出其不定度一定完全解除。所以，摸n次以后所得到的总信息量为：,若经算术平均处理后，则平均信息量为：,所以在此条件下才有平均信息量等于信息熵。,第二章.信息的度量与信息熵,我们说信息熵是一个定值，是指针对信源的概率分布函数来说是一常量。如果分布函数不同，则信息熵也就不同。因此信息熵将是概率分布的函数，亦称熵函数。,2.4 熵函数的数学性质与其物理意义(Mathematical Properties of the Discrete Entropy Function),def,注意：这里所指的熵函数是针对离散信源而言，如果对连续信源其熵函数的性质就有一定的出入。下面我们分别介绍熵函数的数学性质及所涵盖的物理意义。,2.4 熵函数的数学性质与其物理意义,1.对称性(symmetry)这个性质的物理意义非常明确，即熵仅反映信源的总体特征，而与哪一个变量的取值无关。,2.非负性(non-negativity),2.4 熵函数的数学性质与其物理意义,扩展性反映出概率小的事件，虽然自信息很大，但在熵的计算中所占的比重却很小很小，几乎不影响信源的总体特征。,3.扩展性(expansibility),4.确定性(deterministic),2.4 熵函数的数学性质与其物理意义,可加性是熵函数的性质中最重要的一条性质，正因为有此性质才决定熵函数的形式必须要用对数形式。(换句话说：可体现熵可加性的函数形式只有对数形式，这也经熵函数的唯一性定理所证明。)但我们应关心此性质的物理含义，即知识的可积累性。具体的讲：熵函数是作为一个集合中的总体平均不定度特征，应对集合中元素的如何划分是无关的。从另一方面看，可加性所反映的是任何复杂问题，都可以分步解决。这也是说：对于某一事物存在有一定的不确定度，你无法一下完全解除不定度；你总可以分成不同的层次，一步一步地解除，直至最后完全解除其不确定度。,5.可加性(Additive property),或,2.4 熵函数的数学性质与其物理意义,但是如果我换一种问法：先取一个球问其是否为红色？如果是红色便停止取球；否则再从剩下的袋中取一球，问其颜色？判断当得知球为红色的信息量在两种取法中是否相同？,先举一个简单例子，然后介绍书中的内容：设我有三个不同颜色的小球在口袋中，分别为：红色、白色和黑色；问：、当随便从袋中拿出一个球，它的颜色是什么？显然：,2.4 熵函数的数学性质与其物理意义,2.4 熵函数的数学性质与其物理意义,这就是可加性的一种表示方法，而书中给出了另一种方法，由于物理意义表达不充分，我们换一种方式导入。,如果一个随机事件的集合可以看成是由两个随机变量的联合发生而形成，则可以写成以下形式：,2.4 熵函数的数学性质与其物理意义,按照信息熵的定义，我们可写出：,联合概率(joint probability)：,2.4 熵函数的数学性质与其物理意义,(conditional entropy),2.4 熵函数的数学性质与其物理意义,def,(Joint Entropy)它的平均不定度，应等于一个变量的无条件熵加上另一变量的有条件熵。,这是随机变量X与Y之间相互统计独立的重要性质，它是可加性的一特例。所以一般情况下可加性表示为：,2.4 熵函数的数学性质与其物理意义,上式表明，任何概率分布下的信息熵一定不会大于它对其它概率分布下自信息的数学期望。先证明一个常用的不等式，再证明极值性。,6.极值性(Extremum),2.4 熵函数的数学性质与其物理意义,下面证明极值性：,2.4 熵函数的数学性质与其物理意义,这就是离散信源下的最大熵定理：任何离散信源，不论它取何种概率分布，所得的信息熵 H(X),一定不会大于等概率分布时的信息熵(log n)。,2.4 熵函数的数学性质与其物理意义,有了这条性质，我们很容易证明条件熵一定不会大于无条件熵。,2.4 熵函数的数学性质与其物理意义,7.上凸性(Convexity)因为信息熵是一数学函数，故可按数学函数分析其凸、凹性。如果有一函数 f(x),若判断能满足：,成立，我们称此函数为下凸函数,或凹函数；否则为上凸函数。,Convexity,Concavity,2.4 熵函数的数学性质与其物理意义,证明：,2.4 熵函数的数学性质与其物理意义,2.4 熵函数的数学性质与其物理意义,The entropy function is a strictly convex function.因此，只有当函数具有上凸性时，在其值域中一定存在有绝对极大值，故熵函数必然有最大值问题 Maximum entropy theorem最简单的熵函数二元信息熵（The binary entropy function）,2.4 熵函数的数学性质与其物理意义,二维熵函数三元信息熵(The triple entropy function),2.4 熵函数的数学性质与其物理意义,2.4 熵函数的数学性质与其物理意义,2.4 熵函数的数学性质与其物理意义,2.4 熵函数的数学性质与其物理意义,2.4.2 各种熵函数的互换关系一、联合熵与信息熵、条件熵的关系,？,二、由熵函数可加性的推广可得：,2.4.2 各种熵函数的互换关系,三、联合熵与分部信息熵的关系,其中证明的难点一：,1,1,其中证明的难点二：,2.4.2 各种熵函数的互换关系,同理可推出：,等号成立的充分必要条件是：,