Universal codes and algorithmic information theory

Abram explains universal codes, the role of programming languages, and differences between probabilistic and algorithmic views.

Play episode from 07:25

chevron_right

Transcript

chevron_right

Transcript

Episode notes

Condensation: a theory of concepts is a model of concept-formation by Sam Eisenstat. Its goals and methods resemble John Wentworth's natural abstractions/natural latents research.[1] Both theories seek to provide a clear picture of how to posit latent variables, such that once someone has understood the theory, they'll say "yep, I see now, that's how latent variables work!".

The goal of this post is to popularize Sam's theory and to give my own perspective on it; however, it will not be a full explanation of the math. For technical details, I suggest reading Sam's paper.

Brief Summary

Shannon's information theory focuses on the question of how to encode information when you have to encode everything. You get to design the coding scheme, but the information you'll have to encode is unknown (and you have some subjective probability distribution over what it will be). Your objective is to minimize the total expected code-length.

Algorithmic information theory similarly focuses on minimizing the total code-length, but it uses a "more objective" distribution (a universal algorithmic distribution), and a fixed coding scheme (some programming language). This allows it to talk about the minimum code-length of specific data (talking about particulars rather than average [...]

---

Outline:

(00:45) Brief Summary

(02:35) Shannons Information Theory

(07:21) Universal Codes

(11:13) Condensation

(12:52) Universal Data-Structure?

(15:30) Well-Organized Notebooks

(18:18) Random Variables

(18:54) Givens

(19:50) Underlying Space

(20:33) Latents