信息论基础

Posted on by

信息论是应用数学，电子信息工程和计算机科学相关信息量的一个分支。信息论最早是由香农同学发展起来的，他提出了信号处理操作如数据压缩和可靠地存储、传输数据的基本限制。现已推广并发展到多个领域：自然语言处理（NLP）、加密、包含通信网络更大范围的网络，如神经网，还有量子计算、其他形式的数据分析等等。

衡量信息的一个重要工具是熵（或者称为信息量，为统一起见，下文将全部用熵代替），它用来表示在信息中存储或通信一个符号需要的平均比特长度。熵量化了预测一个随机变量的值的不确定性。比如，说出一次投币过程的结果（两个等概率可能出现的结果）比说出一次掷骰子的结果（六个等概率可能出现的结果）的信息量要少。

应用到信息论基础涉及但不局限于以下方面：无损压缩、有损压缩和信号编码等。

 

一、 概述

通过人类最广泛使用的通信方法：语言可以帮助我们理解信息论的基础概念。一个简洁的语言包含两个重要方面：首先，最常用的字（比如中文中的“一”、“的”、“个”）应该比不常使用的字（比如“矍”、“儱”）笔画少，这样一个句子总体才不会笔画太多，同理英文中常用的字母短，才使得一个句子不会那么长。这种字笔画多少上的折中类似于数据压缩中的信源编码。其次，如果句子的一部分因为噪声，比如一个路过的汽车，没有被听到，听者也应该能够理解句子的含义。这种健壮性不仅对于一门语言，对一个通信系统也是一样的重要，适当地在通信过程中添加这种健壮性由信道编码完成。信源编码和信道编码是信息论的两大基本问题。

需要注意到这些问题都没有考虑到信息的重要性，比如，一次迎宾语“您好，欢迎光临！”和“快叫辆救护车”的字数是一样的，但后者在许多环境中更加重要、更有意义。然而信息论并不考虑信息的重要性或者意义，而只关心数据的数量和可读性，因为数量和可读性仅仅是由概率决定的。

香农同学在1948 年年发表的论文”A Mathematical Theory of Communication” 堪称信息论的奠基之作，经典的信息论主要讲的是信息在有噪声信道中传输这个工程问题。这个理论最基本的一个贡献就是香农信源编码理论，使用了比特数来代表不确定事件的熵；另一个重要贡献是香农噪声信道编码理论，阐明了在噪声信道上的可靠通信是可能的，只要通信速率低于一个特定阈值即可，这个阈值称为信道容量。在实际系统中，信道容量可以通过适当的编码解密方法达到。

信息论与许多被研究和应用于工程实际的纯理论和应用学科联系非常紧密，这些学科在过去的半个世纪甚至更长的时间里被全世界广泛的研究和评估测量：自适应系统，人工智能，机器学习，复杂度科学。信息论是一个广泛而深刻的数学理论，并适用于广泛而深入的应用中，其中及其重要的一个领域就是编码理论。

编码理论关心的是如何找到确切的方法，称为编码，增加效率、减少数据在噪声信道中传输的错误率，以达到香农证明的对于该信道最大可能的通信速率。这些编码可以粗略地细分为数据压缩（信源编码）和纠错技术（信道编码）。在纠错技术中，花费了很多年才找到编码方法证实香农限是可以达到的。第三类信息论编码是加密算法。

 

二、 历史背景

香农在信息论上里程碑式的论文一经发表，立即引起了全世界的广泛关注。在这篇文章之前，受限的信息论的想法已经在贝尔实验室有所研究，假设了所有事件的概率都是相等的。物理学家奎斯特也在1924 年自己的一篇文章中理论章节中谈到，“智能”和“线速度”在通信系统中有以下关系：

    $$W = K log m$$

  W 代表传输“智能”的速度，m 是每个时间步骤中可以选择的不同电压级别，K 是一个常数。Ralph Hartley 1928 年论文使用了信息作为度量，反映出接收者能够从其他串符号出区分出特定一串符号能力，因此量化信息为

    $$ H = log S^{n} = n log S$$

，其中S 是符号可能的数目，n 是一次传输中符号的数目。

在香农论文中的相关工作已经在贝尔实验室1944 年底完成，他第一次引入一个定性和定量的通信模型作为信息论的一个统计过程，开篇这样讲道

“The fundamental problem of communication is that of reproducing at one point, either exactly or approximately, a message selected at another point。”

“通信的根本问题就是将某点的信息，在另一个点无论是精确地还是近似地重现出来。”

接着文中主要有以下几点思想：

  • 信息源的信息熵和冗余度，以及与源编码理论的关系；
  • 互信息，和有噪声信道的信道容量，包括完美无损通信的噪声信道编码理论；
  • 对于一种特殊的噪声信道—高斯信道的信道容量；
  • 比特—一种新的新的方法表示信息的最小单位

三、 信息量—熵

信息论基于概率论和统计学。最重要的信息度量是熵，随机变量中的信息和互信息，以及两个变量的共有信息量。前面一个量表示了信息能够被压缩到如何程度，后一个能够用来发现一个信道的通信速率。下文公式中选择对数基，决定了信息熵的单位。最常用的信息单位是比特（bit），基于二进制对数。其他的单位还有比如纳特（nat），基于自然对数。下文中类似于 plog p 的表达式在p = 0 时为零，因为对于任何对数基：

    $$\lim_{p \rightarrow 0^{+}} p log p = 0$$

熵

熵，离散随机变量X 的熵H，是X 值不确定性的度量。

假设传输了1000 个比特（0 或者1 ）。 如果这些比特实现已经知道了（以绝对概率为某特定值），那么从逻辑上讲，没有传输任何值。当如果每一个比特都等概率的为0 或者1 ，那么传输了1000 个比特（从信息论上）。在这两种极端情况之间，信息是这样度量的：如果X 是所有信息{x1, … ,xn} 的集合，并且p(x) 是x∈X 的概率，那么X 的熵定义为：

    $$H(X) = E_{X}[I(X)] = -\displaystyle\sum_{x \in X}p(x)log p(x)$$

（这里I(x) 是自信息，指的是单独一个消息的熵贡献，EX 是它的期望值。）有一个重要特性就是当每个消息都是都是等概率p(x) = 1/n 出现下熵最大，对应着最难预测的情况H(X) = log n。有一种特殊情况是随机变量只有两种结果的信息熵，常用2 作为对数底：

    $$H_{b}(p) = -p log_{2} p - (1-p)log_{2}(1-p)$$

H(X) 作为熵有以下含义：

  1. H(X) 表示每个离散信息所提供的平均信息量
  2. X 如果是信源发出的一个消息，那么H(X) 表示信源的不确定度
  3. H(X) 表示变量X 的随机性

联合熵

两个离散随机变量X 和Y 的联合熵指的就是它们一对(X, Y) 的熵。这意味着如果X 和Y 是独立的，那么它们的联合熵等于它们单独熵的和。比如(X, Y) 代表棋盘上的一个棋子位置—第X 行第Y 列，那么棋子所在行与棋子所在列的熵就是棋子所在位置的熵。

    $$H(X, Y) = E_{X, Y}[-log p(x, y)] = -\displaystyle\sum_{x, y} p(x, y)log p(x, y)$$

虽然有点类似，但请区分开联合熵和交互熵。另外中文的教材中常用H(XY) ，其实和这里的H(X, Y) 是一样的。

条件熵（条件信息量）

给定变量Y，变量X 条件熵或条件不确定性指的是已知Y 的平均条件熵（也称为关于Y 的X 的条件信息量）：

    $$H(X|Y) = E_{Y}[H(X|y)] = -\displaystyle\sum_{y\in Y}p(y) \displaystyle\sum_{x\in X}p(x|y) log p(x|y) = -\displaystyle\sum_{x,y}p(x,y)log\frac{p(x, y)}{p(y)}$$

因为条件熵有两类，一是随机变量的条件熵（H(X|Y)），二是某个值的随机变量的条件熵（H(x|Y)），注意不要搞混淆这两种条件熵，前者更常用一些。这种熵有一个基础性质：

H(X|Y) = H(X, Y) – H(Y)

互信息

互信息量用来度量通过观察一个随机变量可以获得另外一个随机变量信息的信息量。互信息量在通信中有重要作用，比如接受方收到一个信息，那么他可以以多大的概率肯定发送方发送的就是这个消息呢？这就可以用互信息量来表示。X 相对于Y 的互信息量是：

    $$ I(X ; Y) = E_{X, Y}[SI(x, y)] = \displaystyle\sum_{x,y}p(x,y) log\frac{p(x, y)}{p(x)p(y)}$$

其中SI 指的是点互信息，即X 和Y 为特定值的互信息。互信息的一个基本性质是：

H(X; Y) = H(X) – H(X|Y)

也就是说如果知道Y，那么我们可以通过编码X 减少平均I(X; Y) 比特数据，相比较不知道Y 而言。互信息量是对称的：

I(X; Y) = I(Y; X) = H(X) + H(Y) – H(X, Y)

如果将X 和Y 的信息量看做两个圆，那么两个圆相交的面积就是互信息量。

一个例子

下面通过一个简单的例子来说明各种熵和信息量的含义。在一次通信中发送方发送信息X ，接收方接受到信息Y。

条件熵H(Y|X) 表示发送方发出X 后，对收到的变量Y 仍旧存在的不确定度。如果信道中没有任何噪声，那么X 和Y 必然存在一定的对应关系，那么Y 的不确定性就是由传输信道中的噪声造成的。也称为噪声熵。

条件熵H(X|Y) 表示接收方在收到Y 后，对发送方发送变量X 的不确定性，这是Y 关于X 的后验不确定度，也成为信道疑义度，它代表了信息在信道中的损失，称为损失熵。

互信息量I(X; Y) 指的是收到Y 后，获得的X 的信息量，等于I(Y; X)。

它们之间的关系如下图

image

且存在以下性质：

I(Y; X) = H(Y) – H(Y|X) 这是说明，X 对Y 的平均互信息量I(Y; X) 等于发出X 前、后关于Y 的不确定度减少量。

I(X; Y) = H(X) + H(Y) – H(XY) 中H(X) + H(Y) 可以看做系统的先验不确定度，H(XY) 是系统的后验不确定度，那么就是说通道两端随机变量X, Y 之间的平均互信息量等于通信前、后整个系统不确定度减少的量。从一个事件获得另一个事件的平均互信息量需要消除不确定度，一旦消除了不确定度，就获得了信息，所以“信息就是负熵”。

 

四、 编码理论

编码理论是信息论最直接也是最重要的应用。进一步可以分为信源编码理论和信道编码理论。利用数据的统计描述，信息论量化了需要描述的数据大小，也就是源信息熵。源编码即对数据进行压缩，包括无损压缩和有损压缩；信道编码常称为纠错编码，和源编码相反，通过添加冗余在噪声信道中有效的传输信息。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。