Kolmogorov Complexity and Music

A 15-455 project by Ryan Zhang

Which of these is simpler to describe? Kolmogorov complexity makes the question precise: the complexity of a string is the length of the shortest program that outputs it. This site develops the theory, shows why it can never be computed exactly, and then uses compression as a stand-in to cluster and classify music.

Outline

1. Introduction to Kolmogorov complexity

   Opens with two binary strings of the same length, one patterned ($0101\ldots01$) and one random-looking, alongside two short melodies: a repeated scale and an unpredictable line. Asks which is simpler to describe. Gives the formal definition $K_U(x) = \min\{|p| : U(p) = x\}$ for a fixed universal Turing machine $U$. Covers the bounds $K(x) \le |x| + c$ and $K(0^n) \le \log n + c$, and shows how structure in a string turns into a short program.

2. The invariance theorem (main theorem)

   States and proves that for any two universal Turing machines $U$ and $V$, there is a constant $c$ such that $|K_U(x) - K_V(x)| \le c$ for every string $x$. Explains why this means Kolmogorov complexity measures the string itself rather than the choice of programming language.

3. Incompressible strings

   Uses a counting argument to show that for every $n$, at least one string of length $n$ has $K(x) \ge n$, and that most strings are nearly incompressible. This gives a definition of what it means for a single string to be random.

4. Uncomputability and the halting problem

   Proves that $K$ is not computable, using a Berry-paradox argument and a connection to the halting problem. Also explains that $K$ can be approximated from above, but we can never know when the approximation has reached the true value.

5. Chaitin’s incompleteness theorem

   Shows that any consistent, sound formal system with a computable set of axioms can prove statements of the form $K(x) > L$ for only finitely many strings $x$, even though almost all strings satisfy them. Includes the proof and its relationship to Gödel’s incompleteness theorem.

6. From theory to practice: compression distance

   Introduces information distance and the normalized compression distance

   $$\mathrm{NCD}(x, y) = \frac{C(xy) - \min\{C(x), C(y)\}}{\max\{C(x), C(y)\}}$$

   where $C$ is the output length of a real compressor such as gzip or bzip2, used in place of the uncomputable $K$. Discusses what is lost in this approximation and why it still works well in practice.

7. Application: clustering music (Cilibrasi, Vitányi, de Wolf)

   Unsupervised setting: compute pairwise NCD between MIDI files using bzip2, then build a tree with the quartet method. Walks through how pieces group by genre (rock, jazz, classical) and by composer without any built-in musical knowledge. Covers limitations: dependence on file encoding, the compressor’s limited view of musical structure, and the difficulty of evaluating tree quality.

8. Application: classifying melodies (Li and Sleep)

   Supervised setting: assign melodies to one of four classes with a 1-nearest-neighbour classifier, using NID estimated by LZ phrase counts. Discusses the representation choice: absolute pitch contours versus interval contours, and why intervals did better.

   Worked example: encode a short melody and its transposition as interval sequences ($+2, +2, +1, \ldots$), show the two sequences are identical, and compute that their distance is near zero while the absolute-pitch versions look different. Closes by comparing the two papers: clustering versus classification, off-the-shelf compressor versus LZ estimator, and raw MIDI versus extracted melody.

9. References

   Textbooks, lecture notes, and papers used to build this site.