Understanding Artificial Intelligence
through Algorithmic Information Theory
Shrinking objects
Information is what is left after maximal compression.
How far can a given object be compressed?Can we compress all objects?For the kind of objects that can be stored on a computer, such as videos, file sizes give us a hint.For instance, a three-minute video such as this one weighs 70 MB in mkv format.
Appearances may be deceptive, though. This video has been generated by a 4 kB program! So a shrinking ratio of 17 000 to one. This video won the Breakpoint PC 4K Intro competition in 2009. If you are aware of what 4 KB means, and if you watch the video, you can only be amazed. It is an example of what is called a demoscene.
Whenever an object can be compressed
down to a small description,
we know that there is not much information in it.
(a) 1100110011001100110011001100110011001100110011001100
(b) 1001001000011111101101010100010001000010110100011000
(c) 0010100101110110101101000101101011011010001011001011 Sequence (a) is obviously simple. It can be described concisely.
In python: '1100' * 13.
This program can be seen as a compressed version of (a), since (a) can be recovered from it.
(a) 1100110011001100110011001100110011001100110011001100
(b) 1001001000011111101101010100010001000010110100011000
(c) 0010100101110110101101000101101011011010001011001011Sequence (b) is an attempt to write down ‘random’ binary digits by hand.
There seems to be no easy way to compress it.
(a) 1100110011001100110011001100110011001100110011001100
(b) 1001001000011111101101010100010001000010110100011000
(c) 0010100101110110101101000101101011011010001011001011Sequences (c) seems complex at first sight.
But an informed observer would know that sequence (c) represents the first digits of π in binary representation.
So (c) and any longer version of it can be compressed down to any short program that generates π.
def pi(N):
PiDividedByFour = 0
for i in range(N):
PiDividedByFour += (–1)**i /float(2*i+1)
return 4* PiDividedByFour
(a) 1100110011001100110011001100110011001100110011001100
(b) 1001001000011111101101010100010001000010110100011000
(c) 0010100101110110101101000101101011011010001011001011It seems that many sequences can be compressed, or shrunk, down to a short description that captures their information content. Really?
|
000000000000 000000000001 000000000010 000000000011 000000000100 . . . 111111111110 111111111111 |
Consider all binary sequences of size N. There are 2N of them. For instance, there are 4096 binary sequences of length N = 12. Some of these strings, such as the first and the last ones, are highly compressible. For instance, we can represent the last one as '1' * N, and this can be coded with log2(N) + O(1) bits, which is much less than N if N is not too small.
How many of these N-long sequences can be shrunk?
|
000000000000 000000000001 000000000010 000000000011 000000000100 . . . 111111111110 111111111111 |
Suppose we use a compressing program to compress the binary sequences of size N.
How many of them, at most, can be compressed by exactly k bits (k < N)?
|
000000000000 000000000001 000000000010 000000000011 000000000100 . . . 111111111110 111111111111 |
A sequence of N bits that is compressed by exactly k bits must be represented using N-k bits. N-k bits can represent only 2N-k different sequences. Since we want compression to be reversible, only 2N-k sequences of length N at most can be compressed by exactly k bits.
|
000000000000 000000000001 000000000010 000000000011 000000000100 . . . 111111111110 111111111111 |
If we count all sequences of size \(N\) that are possibly compressible by at least \(k\) bits, we get: \(\sum\limits_{i=k}^{N} 2^{N-i} = \sum\limits_{j=0}^{N-k} 2^{j} = 2^{N-k+1} - 1\)
Compared with \(2^N\), this makes a proportion of roughly \(\frac{2^{N-k+1}}{2^N} = 1/2^{k-1}\).
This means that only a tiny proportion of sequences may be compressed by at least k bits as soon as k is significant.
In other words, there is no miracle.
Shrinking has its limits. If one considers all possible objects
(here, binary strings),
compression can spare you a lot of bits on some of them, but
these compressible objects are rare.