《自然语言的熵》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第8讲 信源冗余度与自然语言的熵,背景知识:,实际的信源可能是非平稳的，其极限熵 不一定存在。,可以假定它是平稳的，用平稳信源的 来代替。,对于一般平稳的离散信源，求 值也是极其困难的。,进一步假设它是m阶马尔可夫信源，用m阶马尔可夫信源的信息熵 来近似。,最简单的马尔可夫信源是记忆长度为m=1的信源，信源的熵：,对于一般的离散信源都可以近似地用不同记忆长度的马尔可夫信源来逼近。进一步简化，可以建设信源为无记忆信源，信源符号有一定的概率分布。最后可以假定是等概率分布的离散无记忆信源。,由此看出，由于信源输出符号间的依赖关系也就是信源信号的相关性使信源的实际熵减小。信源输出符号间统计约束关系越长，信源的实际熵越小。当信源输出符号间彼此不存在依赖关系且为等概率分布时，信源的实际熵等于最大熵。,定义：,一个信源的熵率（极限熵）与具有相同符号集的最大熵的比值称为,熵的相对率,：,可见对于有记忆信源，最小单个消息熵应为 ，即从理论上看，对有记忆信源只需传送 即可。,但是这必需要掌握信源全部概率统计特性和所有的记忆关系。这显然是不现实的。,实际上，往往只能掌握有限的N维，这时只需传送 ，那么与理论值相比，就多传送了 。,为了定量描述信源熵的有效性，定义了,信源冗余度：,信源的冗余度来自两个方面:,1、信源符号间的相关性,信源符号间相关程度越大，符号间的依赖关系越长，信源的实际熵越小;,2、另一方面是信源符号分布的不均匀性使信源的实际熵越小。,为了更经济有效的传送信息，需要尽量压缩信源的,冗,余度，压缩,冗,余度的方法就是尽量减小符号间的相关性，并且尽可能的使信源符号等概率分布。,从提高信息传输效率的观点出发，人们总是希望尽量去掉冗余度。,但是从提高抗干扰能力角度来看，却希望增加或保留信源的冗余度，因为冗余度大的消息抗干扰能力强。,信源编码是减少或消除信源的冗余度以提高信息的传输效率。,信道编码则通过增加冗余度来提高信息传输的抗干扰能力。,中华人民共和国,中国,母亲病愈，身体健康,母病愈,例：一个输出A、B、C、D四个符号的信源，它输出10个符号的序列包含最大可能的信息量为：,当信源的符号间有依赖关系时，或概率分布不均匀时，信源熵要下降，因此信源输出的序列总信息量也要下降。假定信源由于符号间的相关性或不等概率，信源熵下降到,比特/符号,正由于信源存在着冗余度，即存在着不必要传送的信息，因此信源也就存在进一步压缩信息率的可能性。冗余度越大，压缩潜力也就越大。可见它是信源编码，数据压缩的前提与理论基础。,下面，以英文为例，计算文字信源的冗余度。,首先给出英文字母（含空档）出现概率如下：,字母,字母,字母,空档,E,T,O,A,N,I,R,0.2,0.105,0.072,0.0654,0.063,0.059,0.055,0.054,S,H,D,L,C,F.U,M,P,0.0502,0.047,0.035,0.029,0.023,0.0225,0.021,0.0175,Y.W,G,B,V,K,X,J.Q,Z,0.012,0.011,0.0105,0.008,0.003,0.002,0.001,0.001,下面，首先求得独立等概率情况，即,其次，计算独立不等概率情况,再次，若仅考虑字母有一维相关性，求,还可进一步求出：,最后，利用统计推断方法求出 ，由于采用的逼近的方法和所取的样本的不同，推算值也有不同，这里采用,Shannon,的推断值。,这样，可以计算出：,这一结论说明，英文信源，从理论上看71是多余成分。即有71%是由语言结构定好的，而剩下的29%可由写文章的人自由发挥的。,直观地说100页英文书，理论上看仅有29页是有效的，其余71页是多余的。正是由于这一多余量的存在，才有可能对英文信源进行压缩编码。,为计算这些熵，要计算字母之间的一维条件概率、二维条件概率,二阶马尔可夫信源，条件概率为 个。,香农做法：,对于其它文字，也有不少人作了大量的统计工作，现简述如下：,英文,法文,德文,西班牙文,中文,（按8千汉字计算）,汉字的编码,GB2312-80,国家标准汉字编码简称国标码。该编码集的全称是“信息交换用汉字编码字符集基本集”，国家标准代号是“GB2312-80”。该编码的主要用途是作为汉字信息交换码使用。,国标码中收集了二级汉字，共约7445个汉字及符号。其中，一级常用汉字3755个，汉字的排列顺序为拼音字典序；二级常用汉字3008个，排列顺序为偏旁序；还收集了682个图形符号。一般情况下，该编码集中的二级汉字及符号已足够使用。,国标码规定：一个汉字用两个字节来表示，每个字节只用前七位，最高位均未作定义（见图）。为了方便书写，常常用四位十六进制数来表示一个汉字。,b,7,b,6,b,5,b,4,b,3,b,2,b,1,b,0,b,7,b,6,b,5,b,4,b,3,b,2,b,1,b,0,0,0,国标码的格式,例如：汉字“大”的国标码是“3473”（十六进制数）。,国标码是一种机器内部编码，其主要作用是：用于统一不同的系统之间所用的不同编码。通过将不同的系统使用的不同编码统一转换成国标码，不同系统之间的汉字信息就可以相互交换。,GB2312 编码表的格式和布局,国际汉字编码也用类似于ASCCII码表的形式给出，将汉字和必要的非汉字字符排列在9494方阵的区域中。方阵中的每一个位置的行和列分别用一个七位二进制编码表示,称为区码和位码，每一个汉字和非汉字字符对应于方阵中的一个位置，因此，可以把汉字和非汉字字符所在位置的区码和位码作为它们的编码。区码和位码的存储各占一个字节，所以在国际汉字编码中，每个汉字和非汉字字符占用俩个字节。表2-6给出了GB2312编码表的局部格式。,表,GB2312,编码局部表,位码：,低7位,区码:高7位,010 010 010 010 010 010 010 010 010,0001,0010,0011,0100,0101,0110,0111,1000,1001,01 02 03 04 05 06 07 08 09,0110000 16,0110001 17,0110010 18,0110011 19,0110100 20,0110101 21,啊 阿 埃 挨 哎 唉 哀 皑 癌,薄 雹 保 堡 饱 宝 抱 报 暴,病 并 玻 菠 播 拨 钵 波 博,场 尝 常 长 偿 肠 厂 敞 畅,础 储 矗 搐 触 处 揣 川 穿,怠 耽,担 丹 单 郸 掸 胆 旦,在“国际基本集”中,从16区到55区是常用的一级汉字,从56区到87区是二级汉字除此之外还收录了一般符号202个（包括间隔、标点、运算符号、单位符号、制表符号），序号60个（120共20个，（1）（20）共20个，共10个，（一）（十）共10个），数字22个（09共10个，共12个），拉丁字母52个，日本假名169个，希腊字母48个，俄文字母66个，汉语拼音符号、注音符号63个。这些符号占1区到10 区。该字符集共收入了汉字和图形符号共7445个。因为全表共94区、94位，所以最多可表示的字符个数为9494，即8836个。表中的空位作为扩充之用。,GB2312编码表的总体布局如下表所示。,GB2312编码表总体布局,位,区,01,94位,01,至,94,区,1,2,3,4,5,6,7,8,9,16,55,56,87,88,94,常用符号（94）,序号、罗马数字（72）,GB1988图形字符集（94）,日文平假名（83）,日文片假名（86）,希腊字母（48）,俄文字母（66）,汉语拼音符（26）、注音字母（37）,制表符（76）,第一级汉字（3755个）,第二级汉字（3008个）,GB2312中的6763个汉字是在文化部1965年发布的印刷通用汉字字形表（6196字）的基础上，根据需要增加了500多个科技名词、地名和姓名用字，既基本上满足了各方面的需要，又有利于降低汉字信息处理系统的成本，提高汉字编码的效率，有利于汉字信息处理技术的推广和应用。,GB2312广泛应用于我国通用汉字系统的信息交换及硬、软件设计中。例如，目前汉字字模库的设计都以GB2312为准，绝大部分汉字数据库系统、汉字情报检索系统等软件也都以GB2312为基础进行设计。,GB2312是汉字信息处理技术领域内的基础标准，许多其他标准都与它密切相关，例如，汉字点阵字型标准、磁盘格式标准的制定均根据GB2312标准。,什么是信息？,关于信息的定义，众说纷纭。,哲学家说，信息就是认识论。,数学家则认为信息是概率论。,物理学家把信息定义为熵。,通信专家把信息看作是消除不确定性。,表明信息科学尚未形成一套统一的、完整的、得到公认的理论。,获取信息的过程是一个由未知到已知的过程（哲学），或者说由不确定到确定的过程（通信）。因此信息可以看作是消除不确定性。,信息分析与统计的工具是概率论（数学）。,具有实际意义的平均信息量称为熵（物理）。,对信息量的认识理解,衡量信息多少的物理量称为信息量。,信息量的大小与消息所描述事件的出现概率有关。,若概率很小，受信者感觉很突然，该消息所含信息量就很大；,若概率很大，受信者事先已有所估计，则该消息信息量就越小；,若受信者收到完全确定的消息，则没有信息.,临 床 诊 断 的 信 息 分 析,诊断是要在互不相容的疾病中作出鉴别。设每个疾病发生的先验概率分别为P（a,1,），P（a,2,），P（a,n,）,医生做诊断前，病人所患的疾病是不确定，如上所述，信源的熵就是这种不确定性大小的量度。,请用信息论思想阐述临床诊断的实质和过程。,在诊断过程中，每进行一项检查获得一个征候信息表现时，它就给医生对疾病的认识带来一定的信息量，医生对患者所患疾病认识的不确定性就会减少。设征候S有m个互不相容的表现s,1,，s,2,，s,m,，当s,j,出现时，疾病a,i,发生的概率设为,P(a,i,|s,j,),i=1,2,n，j=1,2,m,在获得征候表现s,j,后，信源（患者）不确定性大小，按信息论，可以用条件熵度量，即H（x|s,j,）,临 床 诊 断 的 信 息 分 析,信源的熵由,H（X）,降到获得征候表现S,j,后的,H（x|s,j,），,此时，两个熵值之差就是征候表现S,j,提供给医生的信息量：,I（X，S,j,）=H（X）-H（X|S,j,）,上面各式可计算和比较各征候及每个征候各临床表现的信息量，信息量越大的征候或征候表现，其临床诊断的价值就越大。,临 床 诊 断 的 信 息 分 析,