Description length measures how many bits or symbols are needed to specify something. In algorithmic information theory, Kolmogorov complexity is the length of the shortest program that generates an object. Because that exact quantity is uncomputable, practical estimates use the size of a compressed representation instead. section 8.1.1
Figure 8.2 Illustration of the construction of the coarse-grained array using an example grain size of 3. The values of the shaded cells on the left are averaged to produce the value of the shaded cell on the right. Used with permission granted by the lead author (Scott Aaronson).
The diagram shows how averaging neighborhoods creates a coarse-grained array, a simpler representation whose compressed size can estimate apparent complexity. section 8.1.1
Compression distinguishes patterns that look alike in size but differ in structure. A 10,000-character random sequence resists compression; a repeated “HT” sequence can be specified by a short repetition rule. In simulations of mixing coffee and cream, the coarse-grained pattern can become most structured—and hardest to compress—at an intermediate point. section 8.1.1 section 8.1.2
A short description does not necessarily mean an easy computation: a Busy Beaver program can be compact yet take an unknowably long time to run. Description length therefore captures the size of an explanation, not the resources required to produce its result. section 8.2
For neural networks, the full weight matrix is a microstate; the learned function and representations are more useful macrostates to measure. In grokking experiments on modular arithmetic, estimated description length rises during memorization and falls as the model settles on a simpler rule-like solution and test performance improves. section 8.1.2 section 8.5
