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

  1. Mohit Bansal
  2. Yejin Choi
  3. Percy Liang
  4. Yoshua Bengio
  5. Jianfeng Gao
  6. Luke S. Zettlemoyer
  7. Yonatan Belinkov
  8. Noah A. Smith

In Information Theory

  1. Kawin Ethayarajh
  2. Yejin Choi
  3. Swabha Swayamdipta
  4. Jacob Andreas
  5. Stefano Ermon
  6. Jiaming Song
  7. Xiang Ren
  8. Tiago Pimentel

Citations in the corpus