以比特衡量依赖
两个变量各自可能不确定,但仍能互相透露信息。互信息通过比较联合分布与边际分布的乘积来度量这种依赖。它是对称的,尽管所用的相对熵并不对称;它本身也不是因果影响的度量。
定义 9.2.1
(互信息)
令 有有限取值域,对数以二为底。以 表示联合概率, 表示边际概率。求和时省略概率为零的项,等价于取 。只要 ,两个边际值均为正,故下式的比值有定义。互信息为
这是以比特计的相对熵 。
定义 9.2.2
(熵与条件熵)
对有限随机变量 ,定义
只有概率为正的 才需要条件概率。
定理 9.2.3
(非负性与独立)
对有限随机变量 ,,且等号恰在对所有 都有 时成立,亦即 独立。
证明
(互信息就是一个相对熵)
定义 的和式,就是联合分布 相对于乘积分布 在数对字母表上的相对熵,以二为底计算。两者在该字母表上都是概率分布,而且凡 为正之处 也为正。交叉熵与相对熵一节的 Gibbs 不等式给出非负性,且等号恰在 时成立。改变对数的底只是乘以正常数 。这个结论使用完整联合分布,而非只检查相关性为零。
命题 9.2.4
(互信息是不确定性的减少)
对有限随机变量 ,
证明
(拆开比值的对数)
当 ,写 。乘以 并求和:第一部分给出 ;第二部分中,把 对 求和得 ,所以给出 。交换 与 的角色,便得另一个表达式。
因此观察 使关于 的平均不确定性减少 比特。单个观测结果可能不同;此等式对结果取平均。
条件信息与链式法则
定义 9.2.5
(条件互信息)
对每个 的 ,构造条件联合分布及其条件边际分布。定义
每个求和项都非负。当且仅当 与 在 的每个正概率取值下条件独立时,结果为零。
在 的每个取值内应用上面的恒等式再取平均,得 。
定理 9.2.6
(互信息的链式法则)
对有限随机变量 ,
无需任何独立性假设。
证明
(条件熵逐项相消)
对联合变量 应用无条件恒等式,得 。把它写成 。第一个括号是 ,第二个是 :中间项相消。交换 与 的角色,便得第二个表达式。
处理不能增加关于输入的信息
定义 9.2.7
(马尔可夫(Markov)链)
若对每个概率为正的 , 与 在给定 时条件独立,即 ,则称 构成马尔可夫(Markov)链。
定理 9.2.8
(数据处理不等式)
若 是马尔可夫链,则 。等号恰在 时成立,亦即 与 在 的每个正概率取值下条件独立。
证明
(链式法则的两种次序)
马尔可夫条件表明 中每个条件相对熵都是零,所以 。于是由链式法则,。把同一个量按另一种次序展开,得 。因此
因为条件互信息非负。差距恰为 ,这也给出取等号的条件。
证明透视
马尔可夫条件在哪里起作用
证明把同一个量 按两种次序计算。次序 是用到马尔可夫假设的地方:它令第二项为零,所以在 之外加入 ,并不能再多透露关于 的信息。次序 不需要任何假设,那里只用到条件互信息是相对熵的平均、因而非负这一点。所以不等式的差距恰是被丢弃的那一项 。去掉马尔可夫条件,被破坏的只是第一种次序,下面的反例显示结论此时可以失效。
这个数据处理不等式针对满足该条件独立性的指定联合分布。它并不是说 的每个函数都保留全部信息,也不是说光凭箭头记法就证明了因果关系。
反例模式
没有马尔可夫条件,额外的变量可以增加信息
设想一个断言:只要 由 与其他变量构成,就有 。令 为独立的公平比特,。取 、、。由独立性,。给定 时,比特 决定 ,所以条件联合分布在两个格上各有概率 ,边际均匀,它相对于边际乘积的相对熵为 。因此 。由于 是与 独立的公平比特,链式法则给出 。所以 带有关于 的整整一个比特,而 一点也没有。 不是马尔可夫链:给定 时,比特 决定 。
算例
例题 9.2.9
(两级噪声)
令 为公平比特。令 相互独立,。设 、,其中 为模二加法。这些变量满足 。 与 都是公平比特,且
其中 。有效错误率 来自 恰有一个为一:。第一式由 与 得到;第二式因为 独立于 ,且为参数 的伯努利(Bernoulli)变量,故 。数值上 、 比特。不等式保证第二个信道没有增加关于 的信息。
例题 9.2.10
(含零概率格的联合表)
设 、、、。边际分布为 与 。省略零概率格,
核对:,而 ,因为 迫使 , 时 是公平比特。所以 ,两者一致。
例题 9.2.11
(有损的函数与无损的函数)
令 在 上均匀分布,,故 比特。取 。给定 时, 在两个值上均匀,所以 ,。差距为 ,与取等条件的预测一致。改取 ,这是一个一一对应的重新标记,则 、,等号成立。极端情形是常数 ,此时 。
常见错误
常见错误
(相关性为零不等于独立)
令 在 上均匀分布,。则 ,,所以相关性为零。但 是 的函数,故 , 比特。独立要求整个联合分布可以分解。
常见错误
(互信息是平均值,并不保证每次观测都减少不确定性)
令 ,;每当 就有 ,且 。则 ,,所以观测到 时,关于 的不确定性由 比特升至一比特。观测到 (概率 )则确定 。平均而言 ,所以 比特为正。这种减少只是对结果的平均。
练习
快速检查
(若 是公平比特 的确定性副本,求 。若 改为独立的公平比特,结果如何?)
使用 。
解答 · 答案
若为副本,,所以 比特。若 是独立的公平比特,联合分布等于边际分布的乘积,定义中每个比值都是一,故 。
快速检查
(在两级噪声的例子中,解释为何 的概率是 ,以及为何两个噪声必须具有所述独立性才能这样计算。)
两者之和为一,恰当一个噪声比特为一而另一个为零。
解答 · 答案
恰当两个比特中一个为一、另一个为零。有独立性时,概率为 ;没有独立性,两个事件的联合概率就不是乘积。噪声 还必须独立于 ,这样 才相当于错误率 的信道,且 。
快速检查
(当 是常数时,比较 与 ,并在不假设 与 独立的情况下解释这个不等式。)
常数 的 是多少?
解答 · 答案
常数 给出 ,所以 。互信息非负,故无论 与 的依赖如何,。这是数据处理不等式的平凡情形: 是马尔可夫链,因为常数与任何变量都独立。