Compression as a means to learn structure

Warning: Wiki should not be edited directly. Edit the files in the ./wiki/ folder instead and make a PR.

Here are a few papers (and books) that are relevant:

• One of the papers that got me really thinking along these lines (other than my own work on simplification) was Todd Veldhuizen's Parsimony Principles for Software Components and Metalanguages. This one should be a must-read. Interestingly, Krzysztof Czarnecki understood the value of this at one point (see the abstract for this talk Understanding Variability Abstraction at ICSR 2011), but didn't seem to pursue it aggressively. Todd had said similar things in Software Libraries and Their Reuse: Entropy, Kolmogorov Complexity, and Zipf's Law where there is actually some empirical data.
• Compression and Machine Learning: A New Perspective on Feature Space Vectors
• Interestingly, I find Music Analysis and Kolmogorov Complexity to be one of the closest papers to what we are attempting.
• The books Minimum Description Length and Advances in Minimum Description Length (both of which I [Jacques] own), are very good. One can find a pdf of the first two chapters of the latter book online.

There are various papers that explain the theory, such as

• Shannon information and Kolmogorov Complexity. This is a good reference, but is not as helpful as a guide for how to actually come up with good models.
• and the Ph.D. thesis Minimum Description Length Model Selection.

These are mathematically interesting, but probably not useful for us:

• On statistical learning via the lens of compression