526互联

A Theory of Usable Information Under Computational Constraints

发布时间 2023-04-03 16:03:59作者: 馒头and花卷

目录

Xu Y., Zhao S., Song J., Stewart R. and Ermon S. A theory of usable information under computational constraints. International Conference on Learning Representations (ICLR), 2020.

概

本文介绍了一种受约束的互信息, 相较于之前的香农互信息, 这种定义方式更加符合直觉.

符号说明

  • \(X\), 定义在样本空间 \(\mathcal{X}\) 之上的随机变量;
  • \(Y\), 定义在样本空间 \(\mathcal{Y}\) 之上的随机变量;
  • \(\mathcal{P}(\mathcal{X}), \mathcal{P}(\mathcal{Y})\) 定义在 \(\mathcal{X, Y}\) 之上的概率分布;
  • \(f: \mathcal{X} \cup \{\empty\} \rightarrow \mathcal{P}(\mathcal{Y})\), 给定 \(x \in \mathcal{X} \cup \{\empty \}\), \(f\) 将其映射为 \(\mathcal{Y}\) 上的一个概率分布. 注意, 在下文中我们使用 \(f[\cdot]\) 而非 \(f(\cdot)\) 表示用于和一般的映射进行区分.

Motivation

这部分内容借鉴 here 以便于说明.

  • 如上图所示, 假设有这样一个任务, 给定一个图片, 预测其标签. 上图中, 左边是普通的图片 \(X\), 右边是通过 RSA 机制进行加密过后的图片 \(t(X)\). 由于 RSA 是一种双射, 故在原先的香农的互信息的体系之下, 有

    \[I(X, t(X)) = H(X) - H(X|t(X)) = H(X). \]

    即二者具有相同的信息量. 因此,

    \[I(X; Y) = I(t(X); Y), \]

    即凡是通过明文能够预测出的标签, 皆可通过右图预测.

  • 显然, 咋看之下, 这个结论是相当离谱的, 起码对于人类而言, 通过左图预测其标签 ('熊猫') 比起右图而言要容易很多. 这背后的原因是, 香农互信息的前提是观测者具有无穷的计算能力, 显然对于一般人, 一般机器而言, 这是过于强的假设了. 也正因如此, 在机器学习领域, 应用香农互信息往往会产生一些反直觉的结论:

    1. 按照香农互信息的理论, 经过网络提取后的特征 \(g(X)\) 必定满足:

      \[I(g(X); Y) \le I(X; Y), \]

      但是在实际中, 对于分类器而言, 基于 \(g(X)\) 要比 \(X\) 更容易去预测 \(Y\);
    2. 在因果学习中, 倘若 \(X \rightarrow Y\), 那么通过 \(h(X)\) 预测 \(Y\) 是容易的, 反之则不是那么容易. 这和香农互信息的对称性质也是不一致的 (存疑?).

  • 这一切的原因, 正是香农互信息并没有考虑到绝大部分观测者的观测('计算')能力是有限的, 尽管加密后的图片并没有损失信息, 但是它大大增加了观测的复杂度.

\(\mathcal{V}\)-information

  • 首先, 我们对观测者的观测能力进行限制, 下为 Predictive Family 的定义: 令 \(\Omega = \{f: \mathcal{X} \cup \{\empty\} \rightarrow \mathcal{P}(\mathcal{Y})\}\), 则称 \(\mathcal{V} \subset \Omega\) 为一 predictive family 若

    \[\tag{1} \forall f \in \mathcal{V}, \forall P \in \text{range}(f), \: \exist f' \in \mathcal{V}, \quad s.t. \: \forall x \in \mathcal{X}, f'[x] = P, f'[\empty] = P \]

    成立. 注意到, 条件 (1) 允许观测者忽视给定的额外的信息, 直接给出预测 (虽然感觉很奇怪, 但是细想起来是相当一般的假设).

  • 接下来, 我们定义 Predictive conditional \(\mathcal{V}\)-entropy: 假设 \(X, Y\) 为两个随机变量, 则 predictive conditional \(\mathcal{V}\)-entropy 定义为:

    \[H_{\mathcal{V}}(Y | X) = \inf_{f \in \mathcal{V}} \mathbb{E}_{x, y \sim X, Y} [-\log f[x](y)], \\ H_{\mathcal{V}}(Y) := H_{\mathcal{V}}(Y | \empty) = \inf_{f \in \mathcal{V}} \mathbb{E}_{y \sim Y} [-\log f[\empty](y)]. \]

    这两个定义其实和香农信息论中的 条件熵 和 信息熵 相对应.

  • 于是我们可以模仿香农互信息:

    \[I(X; Y) = H(Y) - H(Y|X) \]

    来定义 \(\mathcal{V}\)-information:

    \[I_{\mathcal{V}}(X \rightarrow Y) = H_{\mathcal{V}}(Y|\empty) - H_{\mathcal{V}} (Y|X), \]

    注意到, 这里我们使用 \(X \rightarrow Y\) 是由于 \(\mathcal{V}\)-information 是非对称的 (但是更符合直觉的).

Special Cases

让我们首先观察几个特例, 以便更好地理解 \(\mathcal{V}\)-information.

Shannon entropy

\(\mathcal{V} = \Omega\) 时, \(H_{\mathcal{V}=\Omega}(Y)\) 退化为普通的信息熵, \(H_{\mathcal{V}=\Omega}(Y|X)\) 退化为普通的条件熵, \(I_{\mathcal{V}=\Omega}(X \rightarrow Y)\) 退化为普通的互信息.

proof:

\[\begin{array}{ll} H_{\mathcal{V}}(Y|X) &=\inf_{f \in \mathcal{V}} \mathbb{E}_{x, y \sim X, Y} [-\log f[x](y)] \\ &=\inf_{f \in \mathcal{V}} \mathbb{E}_{x, y \sim X, Y} \Big[\log \frac{P(y|x)}{f[x](y) P(y|x)} \Big] \\ &= H(Y|X) + \inf_{f \in \mathcal{V}} \mathbb{E}_{x \sim X} [\text{KL}(P_{Y|x}\| f[x])] \\ &\ge H(Y|X). \end{array} \]

Mean absolute deviation

令 \(\mathcal{Y} = \mathbb{R}^d\), \(\mathcal{V} = \{f: \{\empty\} \rightarrow P_{\mu} | \mu \in \mathbb{R}^d\}\), 其中 \(P_{\mu}\) 的密度函数形如:

\[\frac{1}{Z} e^{-\|y - \mu\|_2}, \: Z = \int e^{-\|y - \mu \|_2} \text{d} y. \]

则随机变量 \(Y\) 的 \(\mathcal{V}\)-entropy 等价于它的 mean absolute deviation.

proof:

\[\begin{array}{ll} H_{\mathcal{V}}(Y) &= \inf_{f \in \mathcal{V}} \mathbb{E}_{y \sim Y} [-\log f[\empty](y)] \\ &= \inf_{\mu \in \mathcal{V}} \mathbb{E}_{y \sim Y} [-\log \frac{1}{Z} e^{-\|y - \mu\|_2}] \\ &= \inf_{\mu \in \mathcal{V}} \mathbb{E}_{y \sim Y} [\|y - \mu\|_2] + \log Z \\ &\mathop{=}\limits^{?} \mathbb{E}_{y \sim Y} [\|y - \mathbb{E}[Y]\|_2] + \log Z \\ \end{array} \]

注: \(?\) 的地方证明不过去吧. 不晓得是不是作者笔误了.

令 \(\mathcal{Y} = \mathbb{R}^d\), \(\mathcal{V} = \{f: \{\empty\} \rightarrow \mathcal{N}(\mu, \Sigma) | \mu \in \mathbb{R}^d, \Sigma=1/2 I_{d \times d}\}\), 则随机变量 \(Y\) 的 \(\mathcal{V}\)-entropy 等价于 \(\frac{1}{2} \text{tr}(\text{Cov}(Y))\).

proof:

\[\begin{array}{ll} H_{\mathcal{V}}(Y) &= \inf_{f \in \mathcal{V}} \mathbb{E}_{y \sim Y} [-\log f[\empty](y)] \\ &= \inf_{\mu \in \mathcal{V}} \mathbb{E}_{y \sim Y} [-\log \frac{1}{Z} e^{-\|y - \mu\|_2^2}] \\ &= \inf_{\mu \in \mathcal{V}} \mathbb{E}_{y \sim Y} [\|y - \mu\|_2^2] + \log Z \\ &= \mathbb{E}_{y \sim Y} [\|y - \mathbb{E}[Y]\|_2^2] + \log Z \\ &= \frac{1}{2} \text{tr}(\text{Cov}(Y, Y)) + \log Z. \\ \end{array} \]

Maximum Shannon entropy

令 \(\mathcal{V}= \{f: \{\empty\} \rightarrow Q_{t, \theta}, \theta \in \Theta\}\), 其中 \(Q{t, \theta}\) 是一指数族分布, 参数为 \(\Theta\), \(t: \mathcal{Y} \rightarrow \mathbb{R}^d\) 为充分统计量. 令 \(\mu_Y := \mathbb{E}[t(Y)]\), 则 \(Y\) 的 \(\mathcal{V}\)-entropy 为所有具有相同期望 \(\mathbb{E}[t(\hat{Y})] = \mu_Y\) 的随便变量中的最大 Shannon entropy.

proof:

指数族分布形如 (见 here):

\[f_{\theta}(x) = \exp(\theta^T t(y) - A(\theta) + C(y)), \]

则

\[\begin{array}{ll} H_{\mathcal{V}}(Y) &=\inf_{f \in \mathcal{V}} \mathbb{E}_{y \sim Y} [-\log f[\empty](y)] \\ &=\inf_{\theta \in \Theta} \mathbb{E}_{y \sim Y} [-\log \exp(\theta^T t(y) - A(\theta))] \\ &=-\sup_{\theta \in \Theta} \mathbb{E}_{y \sim Y} [\theta^T t(y) - A(\theta)] \\ &=-\sup_{\theta \in \Theta} \Big\{\theta^T \mathbb{E}_{y \sim Y}[t(y)] - A(\theta) \Big\} \\ &=-A^*(\mathbb{E}_{y \sim Y}[t(y)]) = H(P_\mu), \end{array} \]

其中 \(P_{\mu}\) 为:

\[P_{\mu} = \arg\max_{\mathbb{E}_{y \sim P}[t(y)] = \mu_Y} H(P). \]

Determination

令 \(\mathcal{Y} = \mathbb{R}^d\), \(\mathcal{X}\) 为任意的向量空间, 且

\[\mathcal{V} = \{f: x \rightarrow \mathcal{N}(\phi(x), \Sigma), x \in \mathcal{X}; \empty \rightarrow \mathcal{N}(\mu, \Sigma)| \mu \in \mathbb{R}^d, \Sigma = 1/2 I_{d \times d}, \phi \in \Phi\}, \]

其中 \(\Phi\) 为一组线性映射. 则 \(\mathcal{V}\)-information \(I_{\mathcal{V}}(X \rightarrow Y)\) 等价于线性回归中 (未标准化的) determination \(R^2 \cdot \text{tr}(\text{Cov}(Y))\) 的最大系数.

proof:

\[\begin{array}{ll} I_{\mathcal{V}}(X \rightarrow Y) &= H_{\mathcal{V}}(Y) - H_{\mathcal{V}}(Y | X) \\ &= \inf_{\mu \in \mathbb{R}^d} \mathbb{E}_{x, y \sim X, Y} [\|y - \mu\|_2^2] - \inf_{\phi \in \Phi} \mathbb{E}_{x, y \sim X, Y} [\|y - \phi(x)\|_2^2] \\ &= \text{tr}(\text{Cov}(Y)) \Bigg( 1 - \frac{\inf_{\phi \in \Phi} \mathbb{E}_{x, y \sim X, Y} [\|y - \phi(x)\|_2^2]}{\text{tr}(\text{Cov}(Y))} \Bigg) \\ &= \text{tr}(\text{Cov}(Y)) \cdot R^2. \end{array} \]

其它性质

Monotonicity

若 \(\mathcal{V} \subset \mathcal{U}\), 则

\[H_{\mathcal{V}}(Y) \ge H_{\mathcal{U}}(Y), H_{\mathcal{V}}(Y|X) \ge H_{\mathcal{U}}(Y|X). \]

proof:

显然.

Non-Negativity

\[I_{\mathcal{V}}(X \rightarrow Y) \ge 0. \]

proof:

\[\begin{array}{ll} H_{\mathcal{V}}(Y) &=\inf_{f \in \mathcal{V}} \mathbb{E}_{y \sim Y} [-\log f[\empty](y)] \\ &= \inf_{f \in \mathcal{V}} \mathbb{E}_{x, y \sim X, Y} [-\log f[\empty](y)] \\ &= \inf_{f \in \mathcal{V}_{\empty}} \mathbb{E}_{x, y \sim X, Y} [-\log f[\empty](y)] \\ &= \inf_{f \in \mathcal{V}_{\empty}} \mathbb{E}_{x, y \sim X, Y} [-\log f[x](y)] \\ &\ge \inf_{f \in \mathcal{V}} \mathbb{E}_{x, y \sim X, Y} [-\log f[x](y)] = H_{\mathcal{V}}(Y|X). \end{array} \]

其中 \(\mathcal{V}_{\empty} := \{f \in V| f(x) = f(\empty), \forall x \in \mathcal{X}\}\).

Independence

若 \(X \perp \!\!\!\perp Y\), 则

\[I_{\mathcal{V}}(X \rightarrow Y) =I_{\mathcal{V}}(Y \rightarrow X) = 0. \]

proof:

只需证明:

\[H_{\mathcal{V}}(Y) \le H_{\mathcal{V}} (Y | X). \]

\[\begin{array}{ll} H_{\mathcal{V}}(Y|X) &= \text{inf}_{f \in \mathcal{V}} \mathbb{E}_{x, y \sim X, Y} [-\log f[x](y)] \\ &= \text{inf}_{f \in \mathcal{V}} \mathbb{E}_{x \sim X} \mathbb{E}_{y \sim Y} [-\log f[x](y)] \\ &\ge \mathbb{E}_{x \sim X} \: \text{inf}_{f \in \mathcal{V}} \mathbb{E}_{y \sim Y} [-\log f[x](y)] \\ &= \mathbb{E}_{x \sim X} \: \text{inf}_{f \in \mathcal{V}_{\empty}} \mathbb{E}_{y \sim Y} [-\log f[x](y)] \\ &= \text{inf}_{f \in \mathcal{V}_{\empty}} \mathbb{E}_{y \sim Y} [-\log f[\empty](y)] \\ &\ge \text{inf}_{f \in \mathcal{V}} \mathbb{E}_{y \sim Y} [-\log f[\empty](y)] = H_{\mathcal{V}} (Y). \end{array} \]

其中 \(\mathcal{V}_{\empty} := \{f \in V| f(x) = f(\empty), \forall x \in \mathcal{X}\}\).

注: 关于 \(\mathcal{V}\)-information 的 PAC 界请回看原文.