Kolmogorov Complexity and you

Do you like to keep things simple? If you do, you are already acquainted with the concept Kolmogorov (or Algorithmic) Complexity, a mathematical concept with many links to other subjects. Literally, the complexity of a data set (e.g., a computer file with your memories) is the length (in bits) of the shortest program capable of reproducing the file. To be sure, you have to specify what language you will code your program, but the beautiful thing is that different coding languages provide basically the same complexities (up to a constant which stands for the translation of a program into the other). Here are a couple of examples. Take a simple text file with some prose and pass it through zip or other similar programs. The file will be compressed, and you will save disk space. This is lossless compression, meaning that you can recover exactly the same original file from the compressed one—they are fully equivalent. Kolmogorov complexity deals with lossless compression. Lossy compression (as in the jpeg format for images) is related to Kolmogorov but is not the same.

Cognitive systems such as humans rely on compression in a fundamental way. Science deals with compression of natural data into simple models. The universe is constantly generating data for our senses, and there are patterns in it. Once we "lock" into these patterns we make progress in compression and science as well as our daily lives. In physics, for instance, the dream is to compress all natural phenomena into a small set of equations—a Theory of Everything. Since the present approach to science is based on logic and inference, it follows that what we are really trying to do is to compress all phenomena (all data streams) into a simple, short, algorithm. The reader is perhaps familiar with Occam's razor, which is about compression in disguise. This rule of thumb asserts that simpler theories are more probable explanations than complex ones. One should not increase, beyond what is necessary, the number of entities required to explain anything. It is useful advice for science, business and anything else. Try it.

Imagine a robot in a maze for the first time. The robot receives data from its environment from sensors (perhaps a camera) in the form of bits. As it moves around the maze it accumulates data of very high complexity. In order to excel in the task of navigation, the robot needs to construct an internal representation of what is out there. Something simple, much simpler than the potential infinite quantities of data it can capture from its environment, but not too simple. Once it succeeds, it will be guided by a map in some form, of much smaller size than the accumulated data files. And a map is just a compressed representation of what is out there. In fact, in order to succeed and manage change, the robot’s brain—just like yours—needs to model its own body through a process of exploration and experimentation. A recent paper in Science describes just such an “existentially driven” robot, and it demonstrates the usefulness of building self-models in addition to environment models. Well, in fact, I would argue that our body is also part of the environment.

The human brain excels at the art of recognizing (and creating) patterns in vision and sound, and, incidentally, this is probably why we like and create music. A good painting is a "compressed" information package ready to be unzipped by a good viewer. And compression is also key to our survival. Now we need to really understand how this is done at the neural level and we will be on our way to its replication in artificial systems. And what a sight that will be!