PaperlayerView exact revision on arXiv

Source-linked AI summary

A Theory of Usable Information Under Computational Constraints

Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, Stefano Ermon

arXiv:2002.10689v1cs.LGstat.ML

TL;DR

The paper asks how information measures can reflect what computationally bounded observers can actually use, especially when high-dimensional estimation is difficult. It introduces predictive V-information through constrained predictive families, recovering mutual information and other predictiveness measures as special cases. The framework permits computation to create usable information and provides PAC-style estimation guarantees, supporting structure learning and fair representation learning.

  • Problem

    Classical information theory does not account for computational constraints, while Shannon information is difficult to estimate reliably in high-dimensional settings.

  • Method

    The paper defines predictive V-information as a variational information measure based on computationally constrained predictive families.

  • Results

    Predictive V-information recovers mutual information and other notions of predictiveness, can increase through computation, and can be estimated with PAC-style guarantees for applications including structure learning.

  • Takeaways & Limitations

    V-information captures usable information for computationally bounded observers and can be more effective than mutual information for structure learning and fair representation learning.

Abstract

from arXiv · show

We propose a new framework for reasoning about information in complex systems. Our foundation is based on a variational extension of Shannon's information theory that takes into account the modeling power and computational constraints of the observer. The resulting \emph{predictive $\mathcal{V}$-information} encompasses mutual information and other notions of informativeness such as the coefficient of determination. Unlike Shannon's mutual information and in violation of the data processing inequality, $\mathcal{V}$-information can be created through computation. This is consistent with deep neural networks extracting hierarchies of progressively more informative features in representation learning. Additionally, we show that by incorporating computational constraints, $\mathcal{V}$-information can be reliably estimated from data even in high dimensions with PAC-style guarantees. Empirically, we demonstrate predictive $\mathcal{V}$-information is more effective than mutual information for structure learning and fair representation learning.

1 INTRODUCTION

The paper extends information theory to account for computational constraints, defining usable information that can increase through computation. Predictive V-information also supports PAC-style estimation and improves applications including structure learning and representation learning.

  • Predictive V-information incorporates computational constraints into a variational extension of information theory.
  • Without constraints, predictive V-information specializes to mutual information; under restrictions, it captures notions such as the coefficient of determination.
  • Computation can create usable information, violating the data processing inequality that holds for Shannon mutual information.
  • Predictive V-information admits PAC-style statistical guarantees and outperforms approximations of Shannon information in high-dimensional structure learning and gene regulatory network inference.

2 DEFINITIONS AND NOTATIONS

Predictive V-information measures how much a computationally bounded predictive agent gains from side information. Its predictive family determines the resulting uncertainty notion, recovering Shannon information and several predictive or statistical quantities as special cases.

  • The framework models an agent predicting Y with or without real-valued side information X using a computationally bounded predictive family.
  • A predictive family is the set of models available to the agent under computational or statistical constraints, with optional ignorance allowing the agent to ignore X.
  • Predictive V-entropy is the smallest expected negative log-likelihood achievable when predicting Y with models from the selected family.
  • When the predictive family contains all possible models, V-entropy and V-information reduce to Shannon entropy, conditional entropy, and mutual information.
  • Restricted predictive families recover alternative uncertainty notions, including mean absolute deviation, trace of covariance, and maximum-entropy distributions matching sufficient statistics.
  • For linear-Gaussian prediction families, V-information equals the unnormalized maximum coefficient of determination R2 multiplied by tr(Cov(Y)).

3 PROPERTIES OF V-INFORMATION

V-information preserves useful properties of information measures while allowing computational preprocessing to increase predictiveness. This makes it suited to asymmetric relationships and learned representations that extract predictive features.

  • V-information preserves monotonicity across predictive families and assigns zero information to independent variables.
  • Optional ignorance supports these properties by ensuring side information does not restrict the densities available for prediction.
  • Decrypting RSA ciphertext can increase usable information because plaintext is easier to use for predicting labels than encrypted text.
  • Unlike Shannon mutual information, V-information can justify representation learning because predictive feature maps may improve prediction from raw inputs.
  • For one-way functions, polynomial-time computability can produce strongly asymmetric V-information between inputs and outputs.

4 PAC GUARANTEES FOR V-INFORMATION ESTIMATION

The paper addresses the difficulty of estimating Shannon information in high dimensions by estimating V-information under explicit complexity constraints. PAC bounds connect predictive-family complexity to reliable estimation and downstream structure-learning guarantees.

  • Mutual information is difficult to compute from samples when the joint distribution is unknown, a common situation in structure learning.
  • High-dimensional Shannon-information estimators face scalability, bias, or variance problems, including CPC saturation at log N and NWJ variance growing at least exponentially in ground-truth mutual information.
  • V-information can be efficiently estimated with guarantees when the predictive family’s complexity, such as Rademacher or covering-number complexity, is bounded.
  • Theorem 1 gives a PAC bound for empirical V-information under bounded log-likelihoods, using the Rademacher complexity of the induced function family.
  • The predictive family must balance expressiveness against overfitting, since excessive complexity can overfit while excessive simplicity may miss relationships.

5 STRUCTURE LEARNING WITH V-INFORMATION

The paper replaces Shannon mutual information with asymmetric predictive V-information for directed-tree structure learning. The resulting algorithm is exactly optimizable and has finite-sample guarantees tied to estimation complexity.

  • Chow-Liu structure learning is difficult in high dimensions because mutual information is hard to estimate reliably at finite sample sizes.
  • The proposed algorithm assigns predictive families to directed edges and optimizes over directed trees because V-information is asymmetric.
  • The Chu-Liu algorithm constructs the maximal directed spanning tree exactly after estimating V-information for each edge.
  • With high probability, the learned tree's total edge weight is close to the optimal directed tree when the Rademacher complexity terms are small.
  • A larger objective value does not necessarily imply a better Chow-Liu tree, although the optimal trees empirically agree under commonly used predictive families.

6 EXPERIMENTAL RESULTS

Experiments evaluate predictive V-information on continuous structure learning, gene-network inference, video-frame ordering, and fair representation learning. Across these settings, it improves structure recovery or reveals limitations of fairness guarantees tied to a specific discriminator family.

  • 6.1 STRUCTURE LEARNING WITH CONTINUOUS HIGH-DIMENSIONAL DATA: V-information-based Chow-Liu trees are more accurate across data regimes than mutual-information-estimator baselines, despite misspecified predictive families.
  • 6.1 STRUCTURE LEARNING WITH CONTINUOUS HIGH-DIMENSIONAL DATA: About 100 samples suffice for V-information(Gaussian) to recover the ground-truth Chow-Liu tree in simulation-A.
  • 6.2 GENE REGULATORY NETWORK INFERENCE: V-information outperforms other methods in gene-regulatory-network inference AUC across different fractions of data used for estimation.
  • 6.3 RECOVERING THE ORDER OF VIDEO FRAMES: Predictive V-information decreases with frame distance on stochastic Moving-MNIST sequences, supporting recovery of their natural temporal order.
  • 6.3 RECOVERING THE ORDER OF VIDEO FRAMES: On deterministic Moving-MNIST, predictive V-information recovers frame order for distances below 9, whereas Shannon mutual information gives every frame pair the same value.
  • 6.4 INFORMATION THEORETIC APPROACHES TO FAIRNESS: Fair representations trained against one adversary family can leak information to different attacker families across Adult, German, and Heritage datasets.

7 RELATED WORK

The paper distinguishes predictive V-information from alternative information measures and from H entropy. Its emphasis is computationally bounded usable information and estimation in high-dimensional settings.

  • Rényi entropy and Rényi mutual information replace KL divergence with f-divergences but retain Shannon information's difficulty in high-dimensional problems.
  • H entropy associates an entropy definition with each prediction loss, whereas this paper emphasizes bounded computation and intuitive properties of usable information.
  • H entropy still faces high-dimensional estimation difficulty because its definitions do not restrict predictive functions to small-complexity classes.
  • Non-parametric mutual-information estimators such as kernel-density, k-nearest-neighbor, and KSG methods are generally not scalable to high dimensions.

8 CONCLUSION

The paper defines V-information as a computationally constrained extension of mutual information aimed at measuring usable information. It argues that V-information can be estimated with guarantees and applied effectively to structure and fair representation learning.

  • V-information is a variational extension of mutual information that incorporates computational constraints and captures usable information.
  • Unlike Shannon mutual information, V-information can violate the data processing inequality.
  • V-information can be provably estimated and used for structure learning and fair representation learning.

A.1 PROOF OF PROPOSITION 1

The section establishes that predictive V-information generalizes Shannon information while depending on the allowed predictive family. It also derives monotonicity, independence, finite-sample guarantees, and consequences for structure learning.

  • For the unrestricted predictive family Ω, V-entropy and V-information reduce to Shannon entropy, conditional entropy, and mutual information.
  • Restricting the predictive family recovers alternative uncertainty measures, including mean absolute deviation, covariance trace, and maximum entropy under sufficient-statistic constraints.
  • With linear-Gaussian predictive models, V-information equals the unnormalized maximum coefficient of determination R2 multiplied by tr(Cov(Y)).
  • If one predictive family is contained in another, its conditional and unconditional V-entropies are no smaller.
  • Independent variables have zero V-information in either direction, because optional ignorance makes the reverse directional quantity nonpositive while V-information is nonnegative.
  • Under bounded log densities, predictive V-information admits high-probability estimation bounds based on Rademacher complexity, which support guarantees for a V-information Chow-Liu tree.

B ANALYSIS OF APPROXIMATE ESTIMATORS FOR SHANNON INFORMATION

This section examines CPC and NWJ as approximate estimators of Shannon information and identifies practical limitations that motivate alternatives. It also describes replacing mutual information with empirical V-information in Chow-Liu structure learning.

  • CPC and NWJ optimize parameterized lower bounds intended to approximate mutual information, but their ideal behavior does not carry over reliably to practical settings.
  • The CPC estimator is bounded above by log N, so it incurs large bias when I(X; Y) ≥ log N.
  • The NWJ estimator contains a term that can be dominated by rare high-scoring data points and may exhibit high variance at its optimum.
  • Algorithm 1 computes empirical V-information as directed edge weights and applies the Chow-Liu algorithm to construct a maximal directed spanning tree.
  • The simulations evaluate tree recovery across Gaussian, exponential, and mixed conditional distributions, including star and depth-two ground-truth trees.

D.2 FAIRNESS

The fairness objective adapts V-information to minimize sensitive-attribute information under a chosen predictive family. Experiments show that representations protected against one attacker family can remain vulnerable to different attacker families.

  • Fairness objective: Minimizing IV(Z →U) provides a fairness objective when U is discrete and the predictive family has a softmax output.Under these conditions, HV(U) = H(U), so minimizing V-information corresponds to minimizing −HV(Y |X).
  • Cross-family leakage: On Adult, German, and Heritage, prior methods prevent leakage against their trained adversary class but fail against different adversary classes.The datasets use gender, age, and age-gender configurations as sensitive attributes, respectively.
  • Cross-family leakage: An example attacker using a two-layer MLP with softmax achieves AUC 0.857 on features trained with VA-information minimization.The corresponding visualization shows sensitive-attribute groups more evenly spread, yet the alternate attacker still predicts the sensitive attribute effectively.
  • Evaluation setup: The (i, j) matrix entries represent attacker family Vi applied to features trained with Vj-information minimization.Diagonal entries are usually the smallest in their rows, indicating that mismatched attacker families extract more information.

F LIMITATIONS AND FUTURE WORK

The paper identifies limitations in the algebraic behavior of general V-information and points to broader integration with machine learning as future work.

  • Limitations: General V-information does not generally support Shannon-style additive identities such as H(X, Y) = H(X) + H(Y | X).The paper suggests that mathematically simple predictive families, such as polynomial-time computable functions, might recover additional theoretical structure.
  • Future work: Future work could frame representation learning, active learning, classification, and reinforcement learning through V-information-theoretic analyses.The paper presents these as potential directions for studying the production, acquisition, and exploitation of usable information.
Loading 2002.10689v1…