Random Thoughts on Interestingness
As a computer scientist and an information scientist, I have always been fascinated by fundamental questions of computational complexity and compressibility . These days, I am less concerned with big questions like Turing completeness and the P vs. NP problem , and more concerned with quantifying interestingness, especially when randomization is involved.
Let us consider a sequence of n musical notes. For simplicity, we restrict our attention to the 12 notes in a single octave of the chromatic scale , and we assume that they are all of the same duration (e.g., whole notes ).
I hope we agree that the least interesting possible sequence of n notes is a sequence of identical notes, e.g., all Cs . Such a sequence, aside from being boring for listeners, has high compressibility. Indeed, we can validate its high compressibility by using any standard compression algorithm , and we can intuitively see that producing a sequence of n identical notes does not require a program of length proportional to n. Indeed, the only part of the program that grows with n is that we need log? (n) bits to represent n.
Let us now consider the other extreme case: a sequence of n notes, each of which is independently chosen at random from among the 12 available notes. While Sch?nberg might have approved of such dodecaphony , I think that most of us would find such random “music” unlistenable and hardly more interesting than the previous sequence of identical notes. But such a sequence does not have high compressibility. With high probability, the sequence is incompressible : reproducing it would require a program of length proportional to n.
So both extreme cases of low and high compressibility are uninteresting!
But is this random sequence of n notes really incompressible? After all, I just described it concisely as a random sequence of n notes.
A program that produces a random sequence of n notes is essentially the same length as a program that produces a sequence of n identical notes. The only difference is that the program to produce a sequence of n identical notes is deterministic , while the program to produce a sequence of n random notes is non-deterministic because it uses randomization.
领英推荐
But is a program that produces a sequence of n random notes really a compressed version of its output? Not according to conventional information theory. But, to a human ear, all random noise seems interchangeable and equivalent. So what is happening here?
Also, there is an important philosophical distinction between a sequence of n notes generated at random and that same sequence of n notes chosen intentionally. It is the sort of thing about which Borges could have written an eloquent short story (like this one ). But someone who only observes the sequence of notes cannot distinguish between these two scenarios.
Intuitively, I feel that there is some notion of interestingness that relates to the length of the shortest program that can produce a sequence — but only if we can allow for non-determinism. According to this hypothetical measure, a sequence of identical notes and a sequence of random notes would be equally uninteresting. But how do we formalize such a measure?
I don’t know.
The question has bothered me for decades, but no one has ever offered a satisfactory answer or convinced me to give up the quest for one.
But perhaps someone reading this post will enlighten me.
Product leader, specializing in productizing data science, machine learning and AI. Rich entrepreneurial experience in early and growth startups.
10 个月"Interestingness" is so complex. It is related to how surprised you are, but it is not exactly it, since if string of notes that was made just to be unusual is not necessarily interesting. It is related to what you call the the length of the shortest program that can emit that sequence, but it is not it, since if you have seen an elaborate pattern (one that took a long program to emit) many times ago, you are unlikely to find it interesting. Maybe there is not such thing as "globally interesting", and instead, it depends on the goal you are trying to achieve.
AI Alchemist
10 个月My intuition says that 'interestingness' can't be quantified absent historical context. The most interesting music often plays on our expectations by echoing things we've heard before and are trained to expect, but then deviating in a new way from what's come before. The deviation is what piques our interest! Put differently, to a person who had never heard anything *but* repeated C's, the addition of a C# is of profound interest! But jumping straight from there to a 12-bar blues is too far out of context and probably sounds like noise to that particular listener. In all cases, it depends on the frame of reference established to date. For text (fiction or non-fiction), I think the same holds true. Take someone who already has read a lot on, say, quantum mechanics. A piece of writing that ties in 95% of material which is familiar, and *one* new thing they had never heard before, becomes fundamentally interesting! But, to many other readers, who don't come in with that historical context, it's effectively noise. Jumping straight into Finnegan's Wake is not recommended for 99.9% of readers! But to a select few, it is a profoundly interesting piece of text.