Foundations: compression & complexity

To compress is to understand: description length, complexity, randomness

In this chapter, you will learn to

Each exercise is graded automatically, in your browser. The full statements are available once you have an account.

What this is for in real life
Compressing and understanding are two sides of the same coin: whatever you have truly understood about some data, you can say in fewer words. - Language models are compressors. A model that is good at guessing…
The lightest parcel
You are finishing an internship in a team that deploys models on isolated sensors, connected to the server by a satellite link billed by the bit. You have trained a small linear model: a weight vector w that, on…
The peak of mixing
In a complex-systems laboratory, a very simple question, born from a cup of coffee, keeps you busy. You pour the milk on one side, the coffee on the other, and you stir. At the very start, the image is sharp and simple…
Signal or noise
You are building a pipeline that continuously receives data streams from unknown sources: sensors, logs, file fragments, with neither their format nor their origin known. Before training anything on them, a question…