率失真、单边信息、信息瓶颈与最小充分统计量的探讨

为了更为经济的存储、传递、处理信息, 在发送端人们往往会对输入符号进行数据压缩。简化的信息处理模型如图1所示。对数据的压缩主要分为两种:无损压缩和有损压缩。其中有损压缩是指原始符号不能在接收端完全重建, 而只能是“足够”近似于原始符号。但是究竟能压缩到何种程度, 同时接收端还能近似的重建原始符号呢?为了解决这个问题, 香农提出了数据压缩的理论基础:率失真理论。

1 率失真理论

率失真理论给出了信道可以传递的信息量的最小值, 使得在不超过给定失真D的情况下, 输入符号可以在接收端近似重建。公式 (1) 为率失真函数。

其中随机变量X的值x为有限集合, 服从概率为p (x) 的分布。T是X的压缩, 由x到t的映射定义, 服从概率为p (t|x) 的分布。I (T;X) 是用来度量T的压缩程度的互信息。公式2为期望失真。

通过引入朗格拉尔乘子β, 率失真函数的解为对公式3最小化的解

这里变分问题的解是指数形式。

2 具有单边信息的率失真理论

很多情况下, 除了常规输入, 发送端和/或接收端还会有关于源符号或信道的额外信息。通过使用这个边信息, 可以降低数据的传输率。

边信息的应用有两种情况, 解码器具有边信息的源编码Wyner-Ziv coding (WZC) 和编码器具有边信息的信道编码Gel’fandPinsker coding (GPC) 。其中源编码WynerZiv coding (WZC) 的模型如图2所示。

公式4为具有边信息的率失真函数。

其中X和S是两个独立同分布的信源, 具有联合概率p (x, s) 。T是辅助随机变量。是失真映射。

3 信息瓶颈

机器学习指找到数据的压缩表示 (簇或者低维特征) , 从而找到数据的隐含结构。从这个方面来说, 机器学习也是数据压缩的信息处理过程。在这个数据压缩过程中, 除了上节提到的关于源符号的额外信息S, 还有关于想要保留的相关结构Y的信息。信息瓶颈方法将这个相关变量Y引入到压缩中, 在压缩X的同时, 尽可能的保留关于相关变量Y的信息。

在率失真理论中, 问题的建立包括对失真度量的定义, 该失真度量最终出现在最优形式解中。相反, 信息瓶颈理论则不需要提前给出失真度量。而且幸运的是, Tishby给出了IB问题的完整形式最优解, 如公式5所示。

其中信息差异是IB变分原理推导出的有效失真度量, 而不是提前给定的。因此, 可以将其看做是正确的失真度量。

4 充分统计量

充分统计量 (Fisher, 1922) 定义了样本中和参数有关的部分。

定义1 (充分统计量) :

令Y是一组概率分布的参数指标, X是由Y决定的概率分布的随机变量, T是X的确定函数。如果, 则T是Y的充分统计量。

定义2 (最小充分统计量) :

当且仅当对于任意充分统计量X, 存在一个确定函数f, 使得对于任意的X, S=f (T) , 则S是最小充分统计量。

简要的说, 最小充分统计量是在不损失信息的前提下, 不能进一步压缩的充分统计量。

5 结语

我们可以看出, 在信息理论的范畴内, 人们关注的是信息的传递过程。在机器学习领域, 人们关注的是对于接收端来说, 所传递的信息的价值。以上各理论之间的关系可以概括如下。

(1) 率失真和边信息是给定失真函数的通信问题, 最小充分量统计是参数统计原理, 而信息瓶颈是非参数的统计分析技术, 只依赖于变量X和Y的选择及其联合概率。

(2) 信息瓶颈可以被看做率失真的一种特殊情况。对于有损压缩问题, 如果想要满足以下特点:可加性, 输出端的充分性, 数据处理不等式和瓶颈公式, 就必须采用信息差异作为失真度量, 这时便是信息瓶颈方法。

(3) 率失真算法在给定划分的基础上进行计算。而信息瓶颈中, 根据不同β值, 划分在迭代过程中确定。

(4) 信息瓶颈和边信息都处理学习过程中源符号X的多余信息。但是信息瓶颈处理目标结构Y+, 边信息处理和X有关但是和目标结构无关的的信息Y-。

(5) 信息瓶颈将最小充分统计量的概念由参数统计扩展到绝对的分布 (将相关的概念扩展到任意X和Y的联合分布) , 不仅仅局限于指数形式。信息瓶颈放松了充分的条件, 只保留关于相关变量Y的部分 (而不是全部) 互信息。基于信息差异这个失真度量, 信息瓶颈最大化关于参数变量Y的互信息, 这与最小充分统计量中Y的充分性对应, 另一方面最小化I (X;Y) , 这与最小充分统计量中统计的最小性相对应。然而, 与传统的充分统计量和最小充分统计量的概念不同, 信息瓶颈提供一个两个目标间的平衡, 通过设置的β值, 可以获得对最小充分统计量不同程度的近似。

摘要：文章分析了率失真理论、单边信息理论、信息瓶颈理论和最小充分统计量的内涵及关系, 指出在数据处理过程中, 可以利用关于源符号、信道以及目标结构的额外信息对问题进行求解, 并给出了相应的前提条件。

关键词：率失真,最小充分统计量,单边信息,信息瓶颈,数据压缩

参考文献

[1] N.Tishby, F.C.Pereira, and W.Bialek.The information bottleneck method.In Proc.Of the37-th Annual Allerton Conference on Comunnication, Control and Computing, 1999:368～377.

[2] Cover, T.M., &Thomas, J.A.Elements of information theory.John Wiley&Sons, 1991.

[3] N.Slonim.The information bottleneck:Theory and application[Ph.D.dissertation].Hebrew University, Jerusalem, 2002.

[4] Sze.Ming Cheng.Coding with Side Information[Ph.D.dissertation].Texas A&M University, 2004.

[5] Shamir, O., Sabato, S., &Tishby, N.Learning and generalization with the information bottleneck method.2008.