01基础算法思想.ppt

《01基础算法思想.ppt》由会员分享，可在线阅读，更多相关《01基础算法思想.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、应应 用用 信信 息息 论论 基基 础础Fundamentals of Applied Information Theory 内容安排 前言 第一章 信息论的基本概念 第二章 信源与信源无失真编码 第三章 信道及其信道容量 第四章 信道编码 第五章 信息速率失真函数 第六章 最大熵原理与最小鉴别信息原理 第七章 多用户信息论 前言前言一一.信息的概念二二.信息论产生背景三三.Shannon及其影响和贡献四四.Shannon信息论的局限性五五.课程知识要点六六.参考文献一一.信息的概念信息的概念 信 息Hartley,1928 信息是选择的自由度 贝尔系统技术杂志：信息传输 把信息理解为选择通信

2、符号的方式，且用选择的自由度来计量这种信息的大小。哈特莱认为，任何通信系统的发信端总有一个字母表（或符号表），发信者所发出的信息，就是他在通信符号表中选择符号的具体方式。Wiener,1948 信息就是信息，既不是物质也不是能量 信息是有序性的度量 信息是系统组织程度的度量 信息是通信传输的内容 信息是控制的指令 信息是人与外界相互作用的过程中所交换的内容的名称 Brillouin,1956 信息是加工知识的原材料信息是负熵 科学与信息论 Longo,1975 信息是事物之间的差异 信息是一种关系 信息论：新的趋势与未决问题一书的序言：信息是反映事物的形式、关系和差别的东西，它包含在事物的差异

3、之中，而不在事物本身。定义定义 众说纷云 缺乏：完整、明确、为世人所普遍公认的。原因：对信息的本质认识还不够。特点：从不同侧面，层次上揭示信息的特性。哲学 信息是客观事物状态和特征的反映，具有形式和内容之分。1 简单分类 广义信息 将信息的形式和内容全部包含在内的最广 泛意义上的信息。特点：形式和内容的统一 南唐诗人李中诗云：梦断美人沉信息 目穿长路依楼台 技术述语信息 计算机所处理的海量对象，如音频和视频数据、文档资料等。特点：具体形式，不包含内容。统计信息 可以用数学公式严格定义，反映了信息表达形式可以用数学公式严格定义，反映了信息表达形式在统计方面的性质。在统计方面的性质。Entropy

4、特点 有明确定义的科学名词，它与内容无关，而且不随信息的具体表达式的变化而变化。是独立于形式，反映了信息表达式中统计方面的性质。是统计学上的抽象概念。2 语义学上信息的三要素语义学上信息的三要素 信息信息 二二.信息论产生背景信息论产生背景数字通信发展大事件1837年 摩尔斯：有线电报1875年 Emile Baudot：定长电报编码1924年 奈奎斯特：给出了给定带宽的电报信道上无码间串扰的最大可用信号速率1928年 Hartley：在带限信道中当最大信号幅度为Amax，幅度失真为A的条件下，存在一个可靠通信的最大数据速率1939年，1942年 Kolmogorov 和 Wiener：最佳线

5、性（Kolmogorov-Wiener）滤波器1947年 Kotelnikov：基于几何方法的各种相干解调。通信的质量通信的质量检错性抗干扰性持续增长的信息量持续增长的信息量信信息息论论通信容量通信容量 噪声噪声信号信号数数量量和和质质量量有有效效性性与与可可靠靠性性有有线线与与无无线线通通信信面临的问题：计量信号中信息通信系统中信息传输效率信息传输的准确性噪声干扰频率特性 涉及到物理和数学两个方面 核心问题为：信息传输的有效性与可靠性 拉普拉斯决定论（宿命论观点）：拉普拉斯决定论（宿命论观点）：世间一切系统的因果关系都可以包含在确定性的微分方程之中，只要能够给定相应方程的初始条件，就可以唯一

6、地确定这个系统在未来任何时刻的结果。以香农为代表的学者的唯物论观点：以香农为代表的学者的唯物论观点：事物发展变化的因果关系是复杂的，即具有必然性，又存在偶然性，因而事件的结局存在不定性。正是存在不定性，人们才需要获得信息来消除这样的不定性。3.Hartley信息 从D个彼此不同的符号中取出N个符号组成一个“字”（词）。如果每个符号出现的概率相同，选取又是随机的，就可以得到DN个不同的“字”（词），从这些字中取了一个特定的字就对应着带来了一个信息量 I，Hartley 建议这个信息量表示为：Hartley理论的局限性 Hartley定义信息量时并没有考虑不定性问题，即出现概率不相等的情况。他对此

7、解释说：至于出现不定的情况，是人臆想的心理活动，应由心理学家而不是数学家解释。4.Shannon理论理论 1946年，Shannon将Hartley的公式扩大到概率不相等的情况，得到了信息熵的公式。有观点认为，Shannon信息论研究的是语法信息，而排除了语义和语用要素。原因：(1)可靠传递信息，含义和效用由信息的使用者 自己的思维来处理。(2)知识上的局限性。信息 用来消除接收者某种认识上不确 定性的东西。信息论 研究信息的本质、描述和度量方 法以及传输和处理的基本原理 的理论。5 5 信息科学信息科学信息科学信息科学 信息科学是研究信息规律和指导信息技术开发及应用信息科学是研究信息规律和指

8、导信息技术开发及应用 的学问。的学问。6 6 信息技术信息技术信息技术信息技术 运用信息科学为经济和社会发展而共同协作组成的各运用信息科学为经济和社会发展而共同协作组成的各 种工具和规则体系。种工具和规则体系。有观点有观点：日本大坂大学的两位学者小淹一彦和水永政志认为信息技术并未改变世界，迄今为止，它对人类经济的影响微乎其微。三.Shannon及其影响和贡献1.Shannon Claude Elwood19161916年年4 4月月3030日出生于美国密日出生于美国密执安州的加洛德。执安州的加洛德。早年获得了密执安州大学的早年获得了密执安州大学的数学和电子工程学的学士学数学和电子工程学的学士学

9、位。位。19401940年获得麻省理工学院博年获得麻省理工学院博士学位。士学位。19411941年至年至19721972年间，在贝尔年间，在贝尔实验室工作。实验室工作。从从19581958年在麻省理工学院任年在麻省理工学院任教，至教，至19781978年退休。年退休。20012001年年2 2月月2424日在马萨诸塞州日在马萨诸塞州的的MedfordMedford因老年痴呆症与世因老年痴呆症与世长辞，享年长辞，享年8484岁。岁。2.贡献贡献奠定了大型数字计算机构建奠定了大型数字计算机构建的理论基础。的理论基础。19381938年：年：继电器和开关电继电器和开关电路的符号分析路的符号分析 首次

10、用布尔代数进行开关电首次用布尔代数进行开关电路分析，证明了布尔代数的路分析，证明了布尔代数的逻辑运算，可以通过继电器逻辑运算，可以通过继电器电路来实现，给出了实现加，电路来实现，给出了实现加，减，乘，除等运算的电子电减，乘，除等运算的电子电路的设计方法。这篇论文成路的设计方法。这篇论文成为开关电路理论的开端。为开关电路理论的开端。开创了信息论开创了信息论 19481948年：年：The The Mathematical Theory Mathematical Theory of Communication of Communication 1949 1949年：年：Communication

11、in Communication in Presence of NoisePresence of Noise3.影响影响是是2020世纪最杰出的人世纪最杰出的人物之一。如果没有他，物之一。如果没有他，很多我们现在使用的很多我们现在使用的物品根本就不可能存物品根本就不可能存在。数字革命是由香在。数字革命是由香农最初发起的。农最初发起的。内尔内尔 斯罗恩斯罗恩 （香农理论选集的编（香农理论选集的编辑辑）Shannon 理论的问世，象是引爆了一枚重磅的原子弹，震撼了整个科学界。J.Pierce(香农的合作者和朋友）四四.香农理论的局限性香农理论的局限性 “要知道，企望一次就能揭开自然界的全部奥秘是不

12、切实际的”。香农对自己的理论的局限性有清醒的认识，1952年他说：“信息论肯定不是通信工作者的灵丹妙药，对于其他领域的人更是如此。实际上，信息论在核心本质上是数学的分枝，是一个严密的演绎系统。信息论的基本结果都是针对某些特殊的问题，他们未必适合于象心理学，经济学其他以及一些社会科学。”Shannon Theory dead or alive 信息论的主要贡献信息论的主要贡献 把统计信息定义为“用来消除信息接收者某种认识上的不定性的东西”，并给出了其度量公式：熵和互信息；建立了一些重要的性能界：信源输出的最大可能的信息量 满足一定失真度的要求所必须传递的 最小信息量 信道最大可能通过的能力等建立

13、了一组重要的编码定理，从理论上指明了为达到上述性能界限应当遵循的信息处理的方法和原则。不仅从定性方面而且也从定量方面深刻地揭示了信息传递和处理的规律，使通信的研究从经验的阶段发展到科学高度。五五.知识要点知识要点掌握信息论的基本概念：熵、互信息和鉴别信息。了解信息论针对信息传输、存储及压缩的基本理论。了解信息准则取代最小二乘（均方差）准则作为信息工程的普遍准则，掌握其应用方法。六六.参考书目参考书目朱雪龙，应用信息论基础。清华出版社，2001年。傅祖芸，信息论基础理论与应用。电子工业出版社，2001年。周炯槃，信息理论基础。人民邮电出版社，1983年。沈连丰 等，信息论与编码，科学出版社，20

14、04年BIBLIOGRAPHYCover Thomas M,Thomas Joy A.Elements of Cover Thomas M,Thomas Joy A.Elements of Information Theory.John Wiley and Sons.Inc.,1991.Information Theory.John Wiley and Sons.Inc.,1991.Roman Steven.Coding and Information Theory.New Roman Steven.Coding and Information Theory.New York:Springer

15、-Verlag,1992.York:Springer-Verlag,1992.McEliece Robert J.The Theory of Information and McEliece Robert J.The Theory of Information and Coding:A Mathematical Framework for Communication.Coding:A Mathematical Framework for Communication.Addison Wesley Publishing Company,1977.Addison Wesley Publishing

16、Company,1977.Sergio Verdu.Fifty Years of Shannon Theory.IEEE Sergio Verdu.Fifty Years of Shannon Theory.IEEE Tran.on Inf.Theory.Vol.44,No.6,1998.Tran.on Inf.Theory.Vol.44,No.6,1998.Robert G.Gallager.Claude E.Shannon:A Retrospective Robert G.Gallager.Claude E.Shannon:A Retrospective on His Life,Work,

17、and Impact.IEEE Tran.on Inf.Theory.on His Life,Work,and Impact.IEEE Tran.on Inf.Theory.Vol.47,No.7,2001.Vol.47,No.7,2001.第一章 信息论的基本概念1.熵(Entropy)与互信息(Mutual Information)1.1 不确定性与自信息 1.2 Shannon 离散熵 1.2.1 1.2.1 单变量熵函数单变量熵函数 1.2.2 1.2.2 形式的唯一性形式的唯一性 1.2.3 1.2.3 的性质的性质 1.2.4 1.2.4 最大离散熵定理最大离散熵定理 1.3 离散

18、互信息 1.3.1 1.3.1 概念概念 1.3.3 1.3.3 互信息函数的性质互信息函数的性质 1.3.2 1.3.2 多变量情况下的互信息多变量情况下的互信息1.4 连续随机变量的熵和互信息 1.4.1 1.4.1 随机变量微分熵随机变量微分熵 1.4.2 1.4.2 随机变量函数的微分熵随机变量函数的微分熵 1.4.3 1.4.3 互信息互信息 1.4.4 1.4.4 微分熵的变换不变性微分熵的变换不变性2.鉴别信息(Discrimination Information)2.1 随机变量分布差异性的量度 2.1.1 2.1.1 假设检验与对数似然假设检验与对数似然 2.2.2 2.2.

19、2 散度与鉴别信息散度与鉴别信息 2.2 鉴别信息与熵和互信息的关系 2.2.1 2.2.1 鉴别信息与互信息鉴别信息与互信息 2.2.2 2.2.2 鉴别信息与熵鉴别信息与熵 2.2.3 2.2.3 鉴别信息与微分熵鉴别信息与微分熵2.3 鉴别信息的性质 2.3.1 2.3.1 非负性与凸性非负性与凸性 2.3.2 2.3.2 可加性、不变性和方向性可加性、不变性和方向性1.熵(Entropy)1.1 不确定性与自信息 对于通信系统，其传递的信息是具有随机性。定量描述信息应基于随机事件。随机事件的重要特性：结果具有不确定性。例：（1）第一次出门遇见的乌鸦的颜色是白色。X（2）第一次出门遇见的

20、人用手习惯是左撇子。Y（3）第一次出门遇见的人的性别是女性。Z X=(x X=(x1 1,x,x2 2)=()=(白，黑）白，黑）Y=Y=（y y1 1,y,y2 2)=()=(左，右）左，右）Z=Z=（z z1 1,z,z2 2)=()=(女，男）女，男）判断X=x1,Y=y1,Z=z1的不确定性:p(x1)p(y1)(Y y=y1)(Zz=z1)随机事件发生的不确定性与发生的概率有关不确定性的量化：随机事件发生的不确定性为概率的函数，设为 f(pi),该函数应具有如下性质：（1）单调性：pi f(pi)(2)f(pi)非负 f(pi)0：任何随机事件发生存在不确定性。（3）可加性 多随机事

21、件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和。例：事件X=x1,Y=y1同时发生，其发生概率为 p(X=x1,Y=y1）=p(x1)p(y1)，而 f 应满足：f(p(X=x1,Y=y1）)=f(p(x1)+f(p(y1)f 能够将积变成和的功能。可设为对数函数：随机变量X取值xi的概率为pi，则其取值xi的不确定性的量度f(pi)可用下面函数表示：f(pi)为随机事件X取值xi所带来的自信息。信息量：消除不确定性所获得的信息。信息量信息量=不确定性的减少量不确定性的减少量 不确定性消除的量就是量就是我们所获的信息量量 平均不确定性平均不确定性 设随机变量设随机变量X

22、X如下如下N N元概率空间：元概率空间：1.2 Shannon 熵 1.2.1 单变量离散熵函数定义：随机变量X概率空间如上，则其不确定性的量度可表示为：Shannon单变量离散熵函数。1.2.2 熵函数形式的唯一性定理1.1 对于随机变量X存在这样的表示不确定性的量度的函数,为概率分布p1,p2,pN的函数:且该函数满足以下三个先验条件:(1)(1)连续性:是 的连续函数。(2)(2)单调性：等概时为单增函数，（3）可加性：当随机变量当随机变量X X的取值不是通过一次试验，的取值不是通过一次试验，而是若干次试验才最后得到时，则而是若干次试验才最后得到时，则X X在各次试验中的在各次试验中的不

23、确定程度应该可加，且其和始终与通过一次试验取不确定程度应该可加，且其和始终与通过一次试验取得结果的不确定程度相同：得结果的不确定程度相同：即 则函数有下面的唯一形式：熵函数：表示随机变量X的不确定性的量度，称为Shannon熵。随机变量X，Y，熵表示为 H(X),H(Y),为多元函数。可加性解释：设随机变量X 通过一次试验观察通过一次试验观察 x x1 1 发生的不确定程度为发生的不确定程度为下面分两次试验来观察：下面分两次试验来观察：（试验（试验1 1）随机变量）随机变量 那么那么 发生的不确定程度可表示为发生的不确定程度可表示为（试验（试验2 2）随机变量）随机变量 则计算得 =+熵函数形

24、式的唯一性定理的证明可参见参考书熵函数形式的唯一性定理的证明可参见参考书1 1和和3 3。熵值的单位熵值的单位 以以2 2为底：为底：bit (binary unit)bit (binary unit)以以e e为底：为底：nat (nature unit)nat (nature unit)以以1010为底：为底：Hart (Hartley)Hart (Hartley)换算关系：换算关系：1 nat=1.44 bit 1 Hart=3.32 bit1 nat=1.44 bit 1 Hart=3.32 bit 一般取一般取以以2 2为底，为底，1 bit1 bit的信息量就是二元概率空间在等的信

25、息量就是二元概率空间在等概时的熵值。概时的熵值。注：计算机技术中的述语注：计算机技术中的述语“比特比特”表示一个二元数字，表示一个二元数字，每个二元数字所能提供的最大平均信息量为每个二元数字所能提供的最大平均信息量为1 1比特。比特。例1.一副副5252张的扑克牌，现将其充分洗牌，试问：张的扑克牌，现将其充分洗牌，试问：（1 1）任意特定组合所给出的平均信息量是多少？）任意特定组合所给出的平均信息量是多少？（2 2）若任意从这副牌中抽出）若任意从这副牌中抽出1313张，所示的点数都张，所示的点数都 不同，应获得多少信息量？不同，应获得多少信息量？解解：（1 1）（2 2）将将5252张牌中的点

26、数相同而花色不同的四张牌看作张牌中的点数相同而花色不同的四张牌看作一类，共分一类，共分1313类。例如其中一类为：类。例如其中一类为：红桃红桃A A，黑桃，黑桃A A，方块，方块A A，草花，草花AA 则其发生的概率为：则其发生的概率为：1.2.3 熵函数的性质 性质1.非负性,即 0.引理(信息论基本不等式):当基于此,性质性质2.2.熵函数具有凸性，即熵函数具有凸性，即 是概率矢量集是概率矢量集 上的上凸函数上的上凸函数,其中其中关于凸集和凸函数关于凸集和凸函数 凸集凸集:若对集合若对集合D D中任意两点中任意两点 和和 ，均有：均有：则称则称集合集合D D 是是凸凸集。集。可以验证，可以验证，集合集合 是一个是一个N-1N-1维维凸凸集。集。凸函数：定义在凸集 D 上的函数 称为下凸函数，如果 思考题1 1有有1212个外形相同的球，其中一个球（废品球）与其他球个外形相同的球，其中一个球（废品球）与其他球的重量不一样，现有一个天平，但没有砝码。的重量不一样，现有一个天平，但没有砝码。问问：最少用天平几次，才能把废品球找出来，并指出其轻：最少用天平几次，才能把废品球找出来，并指出其轻重？重？