A Theory of Usable Information Under Computational Constraints
By Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, Stefano Ermon. 2020
217 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Information Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Mohit Bansal
- Yejin Choi
- Percy Liang
- Yoshua Bengio
- Jianfeng Gao
- Luke S. Zettlemoyer
- Yonatan Belinkov
- Noah A. Smith
In Information Theory
- Kawin Ethayarajh
- Yejin Choi
- Swabha Swayamdipta
- Jacob Andreas
- Stefano Ermon
- Jiaming Song
- Xiang Ren
- Tiago Pimentel
Citations in the corpus
- Understanding Dataset Difficulty with V-Usable Information (2021, positive): “To understand why a dataset is difficult, we extend recent work in information theory (Xu et al., 2019).”
- What Context Features Can Transformer Language Models Use? (2021, methodology): “This paper offers an answer to that question via the V -information framework of Xu et al. (2020).”
- Acquisition of chess knowledge in AlphaZero (2021, background): “When the observer is restricted to using linear functions, predictive V-information is proportional to the r2 of the best such function.”
- Lossy Compression for Lossless Prediction (2021, background): “The difference in test accuracy (which is also similar for training) must thus come from the fact that some information is easier to use/decode from [51, 52].”
- Multi-label Contrastive Predictive Coding (2020, background): “Variational mutual information estimators Estimating mutual information from samples is challenging [36, 54].”
- Information-Theoretic Measures of Dataset Difficulty (2021, methodology): “Usable information can be measured under a framework called predictive V-information, which generalizes Shannon information to measure how much information can be extracted fromX about Y when constrained to functions V , written as IV(X → Y ) (Xu et al., 2019).”
- Towards Out-Of-Distribution Generalization: A Survey (2021, methodology): “[164] present the first quantitative definition of predictive heterogeneity using V-information [275], and propose an information maximization algorithm to explore this latent heterogeneity.”
- REV: Information-Theoretic Evaluation of Free-Text Rationales (2022, background): “Additional details on the setup are provided in Appendix B.”
- A Bayesian Framework for Information-Theoretic Probing (2021, background): “Then, we discuss why it does not respect the data-processing inequality, and its connection to mutual information and to V -information (Xu et al., 2020).”
- Conditional probing: measuring usable information beyond a baseline (2021, methodology): “V - information as presented by Xu et al. (2020) considers only a single predictive variable X .”