NO.26.tip： 互信息

背景

KL散度为我们提供了一种测量两种分布相似程度的方法。我们应该如何衡量两个随机变量的相互依赖性？我们可以把测量两个随机变量相互依赖性的问题变成关于这两个随机变量分布相似性的问题。这就产生了两个随机变量之间的互信息(Mutual Information, MI)的概念，接下来我们将定义互信息。

定义

随机变量的 $X$ 和 $Y$ 之间的互信息定义如下：

$$\mathbb{I}(X;Y)\triangleq D_{\mathrm{KL}}(p(x,y)\parallel p(x)p(y))=\sum _{y\in \mathcal{Y}}\sum _{x\in \mathcal{X}}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}\text{\hspace{1em}(1)}$$

在 $X$ 和/或 $Y$ 表示变量集合的情况下，记作 $\mathbb{I}(X;Y)$ 而不是 $\mathbb{I}(X,Y)$。例如，我们可以使用 $\mathbb{I}(X;Y,Z)$ 来表示 $X$ 和 $(Y,Z)$ 之间的互信息。对于连续随机变量，我们使用积分来代替求和。

很容易看出，即使对于连续随机变量，互信息也总是非负值，因为：

$$\mathbb{I}(X;Y)=D_{\mathrm{KL}}(p(x,y)\parallel p(x)p(y))\ge 0\text{\hspace{1em}(2)}$$

当且仅当 $p(x,y)=p(x)p(y)$ 时，我们达到边界 0。

解释

互信息是联合和因子边缘分布之间的 KL 散度，这表明如果我们之前将两个变量视为独立的模型 $p(x)p(y)$，现在更新为对其真实联合密度 $p(x,y)$ 建模的模型，则互信息测量信息增益。

为了进一步理解互信息的含义，我们可以借助于使用联合熵和条件熵的形式重新表达互信息，如下所示：

$$\mathbb{I}(X;Y)=\mathbb{H}(X)-\mathbb{H}(X\mid Y)=\mathbb{H}(Y)-\mathbb{H}(Y\mid X)\text{\hspace{1em}(3)}$$

因此，我们可以将 $X$ 和 $Y$ 之间的互信息解释为观察 $Y$ 之后，关于 $X$ 的不确定性有所减少；或者通过对称性，将互信息解释为观察 $X$ 之后，关于 $Y$ 的不确定性有所减少。顺便说一句，这个结论提供了另一种证明，即条件从平均程度上会减少熵的值。特别地，我们有 $0\le \mathbb{I}(X;Y)=\mathbb{H}(X)-\mathbb{H}(X\mid Y)$，因此 $\mathbb{H}(X\mid Y)\le \mathbb{H}(X)$。

我们也可以得到不同的解释。可以证明：

$$\mathbb{I}(X;Y)=\mathbb{H}(X,Y)-\mathbb{H}(X\mid Y)-\mathbb{H}(Y\mid X)$$

最后，我们可以证明：

$$\mathbb{I}(X;Y)=\mathbb{H}(X)+\mathbb{H}(Y)-\mathbb{H}(X,Y)\text{\hspace{1em}(4)}$$

数据处理不等式

假设有一个未知变量 $X$，我们观察到该变量的一个噪声函数，称之为 $Y$。如果我们以某种方式处理有噪声的观测结果，以创建一个新的变量 $Z$，那么直观上应该很明显，我们无法增加关于未知量 $X$ 的信息量。这被称为数据处理不等式。我们现在更正式地陈述这一点，然后加以证明。

定理 假设 $X\to Y\to Z$ 构成一个马尔可夫链，因此 $X\perp Z\mid Y$。于是，$\mathbb{I}(X;Y)\ge \mathbb{I}(X;Z)$。

证明

根据互信息的链式法则，我们可以通过两种不同的方式扩展互信息：

$$\begin{array}{rl}\mathbb{I}(X;Y,Z)& =\mathbb{I}(X;Z)+\mathbb{I}(X;Y\mid Z)\\ & =\mathbb{I}(X;Y)+\mathbb{I}(X;Z\mid Y)\end{array}\text{\hspace{1em}(5)(6)}$$

由于 $X\perp Z\mid Y$，我们有 $\mathbb{I}(X;Z\mid Y)=0$，因此

$$\mathbb{I}(X;Z)+\mathbb{I}(X;Y\mid Z)=\mathbb{I}(X;Y)\text{\hspace{1em}(7)}$$

由于 $\mathbb{I}(X;Y\mid Z)\ge 0$，我们有 $\mathbb{I}(X;Y)\ge \mathbb{I}(X;Z)$。同样，我们可以证明 $\mathbb{I}(Y;Z)\ge \mathbb{I}(X;Z)$。 $\square$

充分统计量

接下来我们介绍数据处理不等式所产生的一个重要结果。假设我们有一个链 $\theta \to X\to s(X)$。于是

$$\mathbb{I}(\theta ;s(X))\le \mathbb{I}(\theta ;X)\text{\hspace{1em}(8)}$$

如果等式成立，那么我们称 $s(X)$ 是数据 $X$ 的充分统计量，该统计量用于推断 $\theta$。在这种情况下，我们可以等价地记作 $\theta \to s(X)\to X$，因为我们可以通过已知的 $s(X)$ 来重构数据，就像通过已知的 $\theta$ 来重构数据一样准确。

充分统计量的一个例子是数据本身，$s(X)=X$，但这作用不大，因为这个信息根本没有总结数据。因此，我们定义了一个最小充分统计量(minimal sufficient statistic) $s(X)$，该统计量是充分的，并且不包含关于 $\theta$ 的额外信息，因此 $s(X)$ 在不丢失与预测 $\theta$ 相关信息的情况下最大限度地压缩数据 $X$。更正式地，如果对于某个函数 $f$ 和所有充分统计量 $s^{\prime }(X)$，$s(X)=f(s^{\prime }(X))$ 成立，那么我们称 $s$ 是 $X$ 的最小充分统计量。我们可以将情况总结如下：

$$\theta \to s(X)\to s^{\prime }(X)\to X\text{\hspace{1em}(9)}$$

其中，$s^{\prime }(X)$ 取 $s(X)$ 并向其添加冗余信息，从而创建一对多的映射。

例如，一组 $N$ 个伯努利试验的最小充分统计量被简单地记为 $N$，并且 $N_1={\sum }_n\mathbb{I}[X_n=1]$ 是成功的次数。换句话说，我们不需要跟踪正面朝上和反面朝上的整个序列及其顺序，我们只需要跟踪正面朝上的总数和反面朝上的总数。类似地，为了推断具有已知方差的高斯分布的均值，我们只需要知道经验均值和样本数。

我们将指数族视为最小的分布族，因为指数族分布除了对数据的一些统计量进行约束之外，不包含其他信息。因此，用于生成指数族分布的统计数据是充分统计量，这是有道理的。这也暗示了 Pitman-Koopman-Darmois 定理的一个更显著的事实，该定理认为，对于任何域是固定的分布，只有指数族才能随着样本数量的增加而接受足够的有界维数统计信息。

多元互信息

接下来我们介绍几种可以将互信息的概念推广到一组随机变量的方法。

总相关性

定义多变量互信息的最简单方法是使用总相关性(total correlation)或多信息(multi-information)，其定义为：

$$\mathrm{TC}(\{X_1,\cdots ,X_D\})\triangleq D_{\mathrm{KL}}\left(p(\mathbf{x})\parallel \prod _{d}p(x_d)\right)\text{\hspace{1em}(10)}$$

$$=\sum _{\mathbf{x}}p(\mathbf{x})\log \frac{p(\mathbf{x})}{\prod _{d=1}^{D}p(x_d)}=\sum _d\mathbb{H}(x_d)-\mathbb{H}(\mathbf{x})\text{\hspace{1em}(11)}$$

例如，对于三个变量，该式变成：

$$\mathrm{TC}(X,Y,Z)=\mathbb{H}(X)+\mathbb{H}(Y)+\mathbb{H}(Z)-\mathbb{H}(X,Y,Z)\text{\hspace{1em}(12)}$$

其中，$\mathbb{H}(X,Y,Z)$ 是联合熵：

$$\mathbb{H}(X,Y,Z)=-\sum _x\sum _y\sum _{z}p(x,y,z)\log p(x,y,z)\text{\hspace{1em}(13)}$$

可以证明多信息总是非负的，并且当且仅当 $p(\mathbf{x})={\prod }_{d}p(x_d)$ 时多信息为零。然而，这意味着即使只有一对变量相互作用，这个量也是非零的。例如，如果 $p(X,Y,Z)=p(X,Y)p(Z)$，则总相关性将为非零值，即使不存在三向交互作用(3 way interaction; 又称为三阶交互作用)。

交互信息（协同信息）

条件互信息可用于给出多元互信息(Multivariate Mutual Information, MMI)的归纳定义，如下所示：

$$\mathbb{I}(X_1;\cdots ;X_D)=\mathbb{I}(X_1;\cdots ;X_{D-1})-\mathbb{I}(X_1;\cdots ;X_{D-1}\mid X_D)\text{\hspace{1em}(14)}$$

这被称为多重互信息(multiple mutual information)或协同信息(coinformation; 又称为共同信息)。这个定义相当于交互信息(interaction information)，只是有一个符号改变。

对于三个变量，多元互信息的定义为：

$$\begin{array}{rl}\mathbb{I}(X;Y;Z)& =\mathbb{I}(X;Y)-\mathbb{I}(X;Y\mid Z)\\ & =\mathbb{I}(X;Z)-\mathbb{I}(X;Z\mid Y)\\ & =\mathbb{I}(Y;Z)-\mathbb{I}(Y;Z\mid X)\end{array}\text{\hspace{1em}(15)(16)(17)}$$

这可以解释为当以第三个变量为条件时，两对变量之间互信息的变化。请注意，这个量的自变量是对称的。

根据条件互信息的定义，我们有：

$$\mathbb{I}(X;Z\mid Y)=\mathbb{I}(Z;X,Y)-\mathbb{I}(Y;Z)\text{\hspace{1em}(18)}$$

因此，我们可以将式(16)改写如下：

$$\mathbb{I}(X;Y;Z)=\mathbb{I}(X;Z)+\mathbb{I}(Y;Z)-\mathbb{I}(X,Y;Z)\text{\hspace{1em}(19)}$$

这表明，多元互信息是我们在分别给定 $X$ 和 $Y$ 的情况下对 $Z$ 学习的程度与在联合给定 $X$ 和 $Y$ 的情况下对 $Z$ 学习的程度之间的差异。

协同和冗余

多元互信息为 $\mathbb{I}(X;Y;Z)=\mathbb{I}(X;Z)+\mathbb{I}(Y;Z)-\mathbb{I}(X,Y;Z)$。我们发现，它可以是正值、零，或者负值。如果由 $X$ 提供的关于 $Z$ 的一些信息也由 $Y$ 提供，那么在 $X$ 和 $Y$ 之间存在一些冗余(redundancy)(相对于 $Z$)。在这种情况下，$\mathbb{I}(X; Z) + \mathbb{I}(Y; Z) > \mathbb{I}(X, Y; Z)$。相比之下，如果当我们同时提供 $X$ 和 $Y$ 的信息时，我们就会对 $Z$ 有更多的了解，也就是说在 $X$ 和 $Y$ 之间存在一些协同(synergy)(相对于 $Z$)。在这种情况下，$\mathbb{I}(X; Z) + \mathbb{I}(Y; Z) < \mathbb{I}(X, Y; Z)$，因此多元互信息将为负值。

多元互信息和因果关系

多元互信息的符号可以用于区分不同类型的有向图模型，这些模型有时可以使用因果进行解释。例如，考虑一个形式为 $X\leftarrow Z\to Y$ 的模型，其中 $Z$ 是 $X$ 和 $Y$ 的"原因"。具体示例如下，假设 $X$ 表示下雨的事件，$Y$ 表示天空阴沉的事件，$Z$ 表示天空多云的事件。以共同原因 $Z$ 为条件会使子节点 $X$ 和 $Y$ 变得独立，因为如果我们知道天气多云，同时注意到天空阴沉，这并不会改变我们对是否会下雨的信念。结果 $\mathbb{I}(X;Y\mid Z)\le \mathbb{I}(X;Y)$，因此 $\mathbb{I}(X;Y;Z)\ge 0$。

现在考虑一种情况，$X\to Z\leftarrow Y$，其中 $Z$ 是 $X$ 和 $Y$ 共同作用的效果。在这种情况下，由于解释效应现象(见 4.2.4.2 节)，对 $Z$ 的条件作用使得 $X$ 和 $Y$ 依赖。例如，如果 $X$ 和 $Y$ 是独立的随机比特，$Z$ 是 $X$ 和 $Y$ 的异或操作，则观察到 $Z=1$ 意味着 $p(X\ne Y\mid Z=1)=1$，因此 $X$ 和 $Y$ 现在是相互依赖的(理论上的信息，而不是因果信息)，即使 $X$ 和 $Y$ 是先验独立的。结果 $\mathbb{I}(X;Y\mid Z)\ge \mathbb{I}(X;Y)$，因此 $\mathbb{I}(X;Y;Z)\le 0$。

最后，考虑一个马尔可夫链 $X\to Y\to Z$。我们有 $\mathbb{I}(X;Z\mid Y)\le \mathbb{I}(X;Z)$，所以多元互信息必须是正值。

多元互信息和熵

我们也可以使用熵来表述多元互信息。具体来说，我们已知：

$$\mathbb{I}(X;Y)=\mathbb{H}(X)+\mathbb{H}(Y)-\mathbb{H}(X,Y)\text{\hspace{1em}(20)}$$

以及：

$$\mathbb{I}(X;Y\mid Z)=\mathbb{H}(X,Z)+\mathbb{H}(Y,Z)-\mathbb{H}(Z)-\mathbb{H}(X,Y,Z)\text{\hspace{1em}(21)}$$

因此，我们可以将式(15)改写为如下形式：

$$\mathbb{I}(X;Y;Z)=[\mathbb{H}(X)+\mathbb{H}(Y)+\mathbb{H}(Z)]-[\mathbb{H}(X,Y)+\mathbb{H}(X,Z)+\mathbb{H}(Y,Z)]+\mathbb{H}(X,Y,Z)\text{\hspace{1em}(22)}$$

更普遍地说，我们有：

$$\mathbb{I}(X_1,\cdots ,X_D)=-\sum _{T\subseteq \{1,\cdots ,D\}}(-1{)}^{|T|}\mathbb{H}(T)\text{\hspace{1em}(23)}$$

对于大小为 1、2 和 3 的集合，其扩展如下：

$$I_1=H_1\text{\hspace{1em}(24)}$$

$$I_{12}=H_1+H_2-H_{12}\text{\hspace{1em}(25)}$$

$$I_{123}=H_1+H_2+H_3-H_{12}-H_{13}-H_{23}+H_{123}\text{\hspace{1em}(26)}$$

我们可以使用默比乌斯反演公式(Möbius inversion formula)来推导出以下对偶关系。对于变量 $S$ 的集合：

$$\mathbb{H}(S)=-\sum _{T\subseteq S}(-1{)}^{|T|}\mathbb{I}(T)\text{\hspace{1em}(27)}$$

使用熵的链式法则，我们还可以导出三向多元互信息的表达式，如下所示：

$$\mathbb{I}(X;Y;Z)=\mathbb{H}(Z)-\mathbb{H}(Z\mid X)-\mathbb{H}(Z\mid Y)+\mathbb{H}(Z\mid X,Y)\text{\hspace{1em}(28)}$$

源与流

互信息的变分上下界

对于计算困难的分布，我们将讨论使用其变分近似来计算互信息上界和下界的方法。这对表征学习十分有用。

变分上界

假设联合 $p(x,y)$ 难以计算，但我们可以从 $p(x)$ 中采样并计算条件分布 $p(y\mid x)$。此外，假设使用 $q(y)$ 来近似 $p(y)$。然后我们就可以计算互信息的上界，如下所示：

$$\begin{array}{rl}\mathbb{I}(x;y)& ={\mathbb{E}}_{p(x,y)}\left[\log \frac{p(y\mid x)q(y)}{p(y)q(y)}\right]\\ & ={\mathbb{E}}_{p(x,y)}\left[\log \frac{p(y\mid x)}{q(y)}\right]-D_{\mathrm{KL}}(p(y)\parallel q(y))\\ & \le {\mathbb{E}}_{p(x)}\left[{\mathbb{E}}_{p(y\mid x)}\left[\log \frac{p(y\mid x)}{q(y)}\right]\right]\\ & ={\mathbb{E}}_{p(x)}[D_{\mathrm{KL}}(p(y\mid x)\parallel q(y))]\end{array}\text{\hspace{1em}(29)(30)(31)(32)}$$

如果 $q(y)=p(y)$，那么上下界都具有紧密性。

进一步解释如下：我们有 $\mathbb{I}(Y;X)=\mathbb{H}(Y)-\mathbb{H}(Y\mid X)$，假设已知 $p(y\mid x)$，所以可以很好地计算 $\mathbb{H}(Y\mid X)$。虽然不知道 $\mathbb{H}(Y)$ 的值，但我们可以使用一些模型 $q(y)$ 来确定其上界。我们的模型永远不会比 $p(y)$ 本身(KL 散度的非负性)做得更好，熵估计误差太大，因此我们的互信息估计将是一个上界。

BA下界

假设联合概率 $p(x,y)$ 难以计算，但我们可以评估 $p(x)$ 的值。此外，假设我们使用 $q(x\mid y)$ 来近似计算 $p(x\mid y)$。然后我们可以在互信息上导出以下变分下界：

$$\begin{array}{rl}\mathbb{I}(x;y)& ={\mathbb{E}}_{p(x,y)}\left[\log \frac{p(x\mid y)}{p(x)}\right]\\ & ={\mathbb{E}}_{p(x,y)}\left[\log \frac{q(x\mid y)}{p(x)}\right]+{\mathbb{E}}_{p(y)}[D_{\mathrm{KL}}(p(x\mid y)\parallel q(x\mid y))]\\ & \ge {\mathbb{E}}_{p(x,y)}\left[\log \frac{q(x\mid y)}{p(x)}\right]={\mathbb{E}}_{p(x,y)}[\log q(x\mid y)]+h(x)\end{array}\text{\hspace{1em}(33)(34)(35)}$$

其中，$h(x)$ 是 $x$ 的微分熵。这被称为 BA 下界，以作者 Barber 和 Agakov 的名字命名。

NWJ下界

BA 下界需要一个可处理的归一化分布 $q(x\mid y)$，我们可以逐点计算该归一化分布。如果我们采用一种巧妙的方式重新参数化这个分布，就可以生成一个不需要归一化分布的下界，记作：

$$q(x\mid y)=\frac{p(x)e^{f(x,y)}}{Z(y)}\text{\hspace{1em}(36)}$$

其中，$Z(y)={\mathbb{E}}_{p(x)}[e^{f(x,y)}]$ 是归一化常数或配分函数。将其代入上述 BA 下界，我们可以得到：

$$\begin{array}{rl}{\mathbb{E}}_{p(x,y)}\left[\log \frac{p(x)e^{f(x,y)}}{p(x)Z(y)}\right]& ={\mathbb{E}}_{p(x,y)}[f(x,y)]-{\mathbb{E}}_{p(y)}[\log Z(y)]\\ & ={\mathbb{E}}_{p(x,y)}[f(x,y)]-{\mathbb{E}}_{p(y)}\left[\log {\mathbb{E}}_{p(x)}\left[e^{f(x,y)}\right]\right]\\ & \triangleq I_{\mathrm{DV}}(X;Y)\end{array}\text{\hspace{1em}(37)(38)(39)}$$

这是 Donsker-Varadhan 下界(DV 下界)。

我们可以通过使用以下事实来构造一个更易于处理的版本。使用下式，对数函数可以由一条直线构成上界：

$$\log x\le \frac{x}{a}+\log a-1\text{\hspace{1em}(40)}$$

如果设置 $a=e$，那么我们得到：

$$\mathbb{I}(X;Y)\ge {\mathbb{E}}_{p(x,y)}[f(x,y)]-e^{-1}{\mathbb{E}}_{p(y)}Z(y)\triangleq I_{\mathrm{NWJ}}(X;Y)\text{\hspace{1em}(41)}$$

这被称为 NWJ 下界(以作者 Nguyen、Wainwright 和 Jordan 的名字命名)，或者 $f$ 生成式对抗性网络 KL 散度，或者 MINE-$f$ 分数。

InfoNCE下界

如果转而探索对上述 DV 下界的多样本扩展，我们可以生成以下下界：

$$\begin{array}{rl}{I}_{\mathrm{NCE}}& =\mathbb{E}\left[\frac{1}{K}\sum _{i=1}^K\log \frac{e^{f(x_i,y_i)}}{\frac{1}{K}{\sum }_{j=1}^K{e}^{f(x_i,y_j)}}\right]\\ & =\log K-\mathbb{E}\left[\frac{1}{K}\sum _{i=1}^K\log \left(1+\sum _{j\ne i}{e}^{f(x_i,y_j)-f(x_i,y_i)}\right)\right]\end{array}\text{\hspace{1em}(42)(43)}$$

其中，期望是来自联合分布 $p(X,Y)$ 的成对样本。式(43)中的量被称为 InfoNCE 估计。

其直观理解是，互信息是联合分布 $p(x,y)$ 和边缘分布乘积 $p(x)p(y)$ 之间的散度。换句话说，互信息是对联合分布采样对与独立采样 $x$ 和 $y$ 之间差异的测量。式(43)中的 InfoNCE 界通过尝试对模型进行训练来区分这两种情况，并提供了真实互信息的下界。

尽管这是一个有效的下界，但如果互信息很大，我们可能需要使用较大批次规模的 $K$ 来估计互信息，因为 $I_{\mathrm{NCE}}\le \log K$。