Autumn2012 Lecture11:FurtherTopicsJyrkiKivinen Information-TheoreticModeling

(1)

Outline Kolmogorov Complexity Gambling

Information-Theoretic Modeling

Lecture 11: Further Topics

Jyrki Kivinen

Department of Computer Science, University of Helsinki

Autumn 2012

(2)

Lecture 11: Further Topics

(Peter Falk asColumbo, NBC)

(3)

1 Kolmogorov Complexity Definition

Basic Properties

2 Gambling

Gambler’s Ruin Kelly Criterion

(4)

Basic Properties

2 Gambling

(5)

Definition Basic Properties

Kolmogorov Complexity

We probably agree that the string

10101010101010101010. . .10

| {z }

10 million characters

is “simple”.

Why?

(One) Solution: The string has a short description:

“10 repeated 5 000 000 times”.

Remark: “Description” should be understood to mean a code that can be decoded by some algorithm (a formal procedure that halts).

(6)

Kolmogorov Complexity

10101010101010101010. . .10

| {z }

is “simple”.

Why?

(7)

Kolmogorov Complexity

10101010101010101010. . .10

| {z }

is “simple”.

Why?

(8)

Turing machines

To precisely define Kolmogorov complexity we need to fix a formal notion of algorithm.

Following tradition, we use here Turing Machine (TM), but any other universal model of computation could be used as well. For simplicity, we assume that the inputs and outputs are strings over the binary alphabet{0,1}.

If TMU on input p ∈ {0,1}^∗ halts and outputs x∈ {0,1}^∗, we writeU(p) =x.

IfU does not halt on inputp, we say that U(p) in undefined and writeU(p) =∅.

We use|p|to denote the length of string x.

(9)

Turing machines

If TMU on input p ∈ {0,1}^∗ halts and outputs x∈ {0,1}^∗, we writeU(p) =x.

We use|p|to denote the length of string x.

(10)

Turing machines

If TMU on input p ∈ {0,1}^∗ halts and outputsx ∈ {0,1}^∗, we writeU(p) =x.

We use|p|to denote the length of stringx.

(11)

Kolmogorov Complexity

TheKolmogorov complexity of stringx ∈ {0,1}^∗ with respect to a Turing machineU is defined as the length of shortest input on whichU outputsx:

K_U(x) = min{ |p| |U(p) =x} .

Notice thatK_U(x) depends on our choice ofU, which at this stage is abritrary. However, we can remove most of this dependence by limiting the set of machinesU we consider.

Turing machine U is a prefix machineif the set of inputs on which U halts is prefix-free.

Turing machine U isuniversal if for any other TMV there is a stringq_V such that V(p) =U(qvp) for allp ∈ {0,1}^∗. Hereqp means concatenation of stringsq andp.

(12)

Kolmogorov Complexity

K_U(x) = min{ |p| |U(p) =x} .

Notice thatKU(x) depends on our choice ofU, which at this stage is abritrary. However, we can remove most of this dependence by limiting the set of machinesU we consider.

(13)

Kolmogorov Complexity

K_U(x) = min{ |p| |U(p) =x} .

(14)

Kolmogorov Complexity

K_U(x) = min{ |p| |U(p) =x} .

Turing machine U isuniversal if for any other TMV there is a stringq_V such that V(p) =U(qvp) for all p ∈ {0,1}^∗.

Hereqp means concatenation of stringsq andp.

(15)

Kolmogorov Complexity

K_U(x) = min{ |p| |U(p) =x} .

Turing machine U isuniversal if for any other TMV there is a stringq_V such that V(p) =U(qvp) for all p ∈ {0,1}^∗. Hereqp means concatenation of stringsq andp.

(16)

Prefix property in practice

Requiring prefix property may seem a bit technical, but intuitively it just means we must be able to tell when the input ends.

In practical programming, this is done by methods such as end-of-file markers, or having the operating system keep track of file lengths.

End-of-file markers actually are a way of keeping the input set prefix free. However reserving one symbol for this special use is not generally acceptable if we are interested in optimal code lengths. Theoretically more satisfying way to make a set of inputs

prefix-free is to include the lenght of (the rest of) the input string using some prefix code.

(17)

Prefix property in practice

End-of-file markers actually are a way of keeping the input set prefix free. However reserving one symbol for this special use is not generally acceptable if we are interested in optimal code lengths. Theoretically more satisfying way to make a set of inputs

(18)

Prefix property in practice

End-of-file markers actually are a way of keeping the input set prefix free. However reserving one symbol for this special use is not generally acceptable if we are interested in optimal code lengths.

Theoretically more satisfying way to make a set of inputs

(19)

Prefix property in practice

End-of-file markers actually are a way of keeping the input set prefix free. However reserving one symbol for this special use is not generally acceptable if we are interested in optimal code lengths.

Theoretically more satisfying way to make a set of inputs

(20)

Prefix code for integers

A straighforward prefix code for integers is the following:

Consider integerx with n bit binary representationx1x2x3. . .xn. We encodex asx₁x₁x₂x₂x₃x₃. . .x_nx_n01.

We denode this code forx byhxi.

For example, forx = 19 = 100112 we gethxi= 110000111101. The lenght of the prefix-free encoding is| hxi |= 2n+ 2 bits, wheren=dlog₂(x+ 1)e ≤log₂x+ 1 is the length of the original binary representation.

(21)

Prefix code for integers

For example, forx = 19 = 100112 we gethxi= 110000111101.

The lenght of the prefix-free encoding is| hxi |= 2n+ 2 bits, wheren=dlog₂(x+ 1)e ≤log₂x+ 1 is the length of the original binary representation.

(22)

Prefix code for integers

For example, forx = 19 = 100112 we gethxi= 110000111101.

The lenght of the prefix-free encoding is| hxi |= 2n+ 2 bits, wheren=dlog₂(x+ 1)e ≤log₂x+ 1 is the length of the original binary representation.

(23)

Prefix property for Turing Machines

We can now make the set of inputs prefix-free by inserting before each inputx its length encoded ash|x|i.

For example, input 1000100101101, which has 13 bits, becomes 1111001101

| {z }

code for 13 = 11012

1000100101101

| {z }

actual input

.

More generally, an input ofn bits gets code length of at most n+ 2 log₂n+ 2 bits.

For largen this is much better than 2n+ 2 we would get by applying the prefix-free encoding from previous slide directly tox. To summarize, the prefix property is reasonable from a practical point of view, and from a theoretical point of view can be assumed without increasing input lengths too much.

(24)

Prefix property for Turing Machines

| {z }

code for 13 = 11012

1000100101101

| {z }

actual input

.

(25)

Prefix property for Turing Machines

| {z }

code for 13 = 11012

1000100101101

| {z }

actual input

.

(26)

Prefix property for Turing Machines

| {z }

code for 13 = 11012

1000100101101

| {z }

actual input

.

For largen this is much better than 2n+ 2 we would get by applying the prefix-free encoding from previous slide directly tox.

To summarize, the prefix property is reasonable from a practical point of view, and from a theoretical point of view can be assumed without increasing input lengths too much.

(27)

Prefix property for Turing Machines

| {z }

code for 13 = 11012

1000100101101

| {z }

actual input

.

For largen this is much better than 2n+ 2 we would get by applying the prefix-free encoding from previous slide directly tox.

To summarize, the prefix property is reasonable from a practical point of view, and from a theoretical point of view can be assumed without increasing input lengths too much.

(28)

Universal Turing Machines

For any fixedx, there are Turing machines that output x with empty input, and other Turing machines that don’t outputx with any input.

Similarly, for any pair of different stringsx 6=y, there are Turing machines U andV such thatK_U(x)K_U(y) but

KV(x)KV(y).

For comparisons of Kolmogorov complexities to be meaningful, we requireU to beuniversal.

(29)

Universal Turing Machines

Similarly, for any pair of different stringsx 6=y, there are Turing machinesU andV such thatK_U(x)K_U(y) but

KV(x)KV(y).

(30)

Universal Turing Machines

Similarly, for any pair of different stringsx 6=y, there are Turing machinesU andV such thatK_U(x)K_U(y) but

KV(x)KV(y).

(31)

Universal Turing Machines

Universality

A Turing MachineU is said to be universal, if forany other Turing MachineV there is a string q_V ∈ {0,1}^∗ (which depends onV) such that for all stringsp we have

U(q_Vp) =V(p) .

That is when given the concatenated inputqp, TMU outputs the same string as TMV when given inputp.

If we think of stringsp as programs in the “machine language” of V, then q_v is an “interpreter” or “compiler” for V’s machine language, written for machineU (in the machine language ofU).

(32)

Universal Turing Machines

Universality

A Turing MachineU is said to be universal, if forany other Turing MachineV there is a string q_V ∈ {0,1}^∗ (which depends onV) such that for all stringsp we have

U(q_Vp) =V(p) .

That is when given the concatenated inputqp, TMU outputs the same string as TMV when given inputp.

If we think of stringsp as programs in the “machine language” of V, then qv is an “interpreter” or “compiler” for V’s machine language, written for machineU (in the machine language ofU).

(33)

Examples

Examples of (virtually) universal ‘computers’:

1 C (compiler + operating system + computer),

2 Java (compiler + operating system + computer),

3 your favorite programming language (compiler/interpreter + OS + computer),

4 Universal Turing machine,

5 Universal recursive function,

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

Each of the above can mimic all the others.

(34)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(35)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(36)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(37)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(38)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(39)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(40)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(41)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(42)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(43)

Examples

6 Lambda calculus,

7 Arithmetics,

8 Game of Life

9 ...

(44)

Kolmogorov Complexity

For anyuniversalcomputer U, and any other computerV, we have KU(x)≤KV(x) +C ,

whereC is a constant independent ofx.

Proof: Let qV be such thatU(qVp) =V(p) for all p. Letp^∗_V(x) be the shortest program for which V(p_V^∗(x)) =x. Then

U(q_Vp^∗_V(x)) =x, so

K_U(x)≤ |q_Vp^∗_V(x)|=|p_V^∗(x)|+|q_V|=K_V(x) +|q_V| . Since we are restricting ourselves to prefix machines, we don’t need to worry about any overhead caused by encoding the pair (q_V,p), we can just concatenate them.

(45)

Kolmogorov Complexity

Proof: Let qV be such thatU(qVp) =V(p) for all p. Letp^∗_V(x) be the shortest program for whichV(p^∗_V(x)) =x. Then

K_U(x)≤ |q_Vp^∗_V(x)|=|p^∗_V(x)|+|q_V|=K_V(x) +|q_V| .

Since we are restricting ourselves to prefix machines, we don’t need to worry about any overhead caused by encoding the pair (q_V,p), we can just concatenate them.

(46)

Kolmogorov Complexity

Proof: Let qV be such thatU(qVp) =V(p) for all p. Letp^∗_V(x) be the shortest program for whichV(p^∗_V(x)) =x. Then

K_U(x)≤ |q_Vp^∗_V(x)|=|p^∗_V(x)|+|q_V|=K_V(x) +|q_V| . Since we are restricting ourselves to prefix machines, we don’t need to worry about any overhead caused by encoding the pair (q_V,p), we can just concatenate them.

(47)

Invariance Theorem

From now on we restrict the choice of the computerU in KU to universalcomputers.

Invariance Theorem

Kolmogorov complexity is invariant (up to an additive constant) under a change of the universal computer. In other words, for any two universal computers,U andV, there is a constantC such that

|K_U(x)−K_V(x)| ≤C for all x ∈ {0,1}^∗ .

Proof: Since U is universal, we have K_U(x)≤K_V(x) +C₁. Since V is universal, we haveK_V(x)≤K_U(x) +C₂. The theorem follows by settingC = max{C₁,C2}.

(48)

Invariance Theorem

|K_U(x)−K_V(x)| ≤C for all x ∈ {0,1}^∗ .

(49)

Invariance Theorem

|K_U(x)−K_V(x)| ≤C for all x ∈ {0,1}^∗ .

(50)

Kolmogorov Complexity

Upper Bound

We have the following upper bound onKU(x):

K_U(x)≤ |x|+ 2 log₂|x|+C

for some constantC which depends on the computerU but not on the stringx.

Proof: Remember that we have a prefix code where the code length forx is

`(x) =|x|+ 2 log₂|x|+ 2.

LetV be a TM that decodes this encoding. Then KV(x) =`(x). Therefore, for universalU we haveK_U(x)≤`(x) +C.

(51)

Kolmogorov Complexity

Upper Bound

We have the following upper bound onKU(x):

K_U(x)≤ |x|+ 2 log₂|x|+C

for some constantC which depends on the computerU but not on the stringx.

Proof: Remember that we have a prefix code where the code length forx is

`(x) =|x|+ 2 log₂|x|+ 2.

LetV be a TM that decodes this encoding. Then KV(x) =`(x).

Therefore, for universalU we haveK_U(x)≤`(x) +C.

(52)

Kolmogorov Complexity

Conditional Kolmogorov Complexity

Theconditional Kolmogorov complexityis defined as the length of the shortest program to printx when y is given:

KU(x|y) = min{ |p| |U(¯y p) =x} , where ¯y is a prefix-encoded representation ofy.

Upper Bound 2

We have the following upper bound onK_U(x | |x|): KU(x | |x|)≤ |x|+C for some constantC independentx.

(53)

Kolmogorov Complexity

Conditional Kolmogorov Complexity

Theconditional Kolmogorov complexityis defined as the length of the shortest program to printx when y is given:

KU(x|y) = min{ |p| |U(¯y p) =x} , where ¯y is a prefix-encoded representation ofy. Upper Bound 2

We have the following upper bound onK_U(x | |x|):

KU(x | |x|)≤ |x|+C for some constantC independentx.

(54)

Examples

Letn=|x|.

1 K_U(0101010101...01|n) =C. Program: print n/2 times 01.

2 KU(π1π2 . . . πn|n) =C.

Program: print the first n bits of π.

3 KU(English text|n)≈1.3×n+C. Program: Huffman code.

(Entropy of English is about 1.3 bits per symbol.)

4 K_U(fractal) =C.

Program: print # of iterations until zn+1=z_n²+c >T.

(55)

Examples

Letn=|x|.

1 KU(0101010101...01|n) =C. Program: print n/2 times 01.

2 KU(π1π2 . . . πn|n) =C.

4 K_U(fractal) =C.

(56)

Examples

Letn=|x|.

2 KU(π1π2 . . . πn|n) =C.

4 K_U(fractal) =C.

(57)

Examples

Letn=|x|.

2 KU(π1π2 . . . πn|n) =C.

3 K_U(English text|n)≈1.3×n+C. Program: Huffman code.

4 K_U(fractal) =C.

(58)

Examples

Letn=|x|.

2 KU(π1π2 . . . πn|n) =C.

3 K_U(English text|n)≈1.3×n+C. Program: Huffman code.

4 K_U(fractal) =C.

(59)

Examples

(60)

Martin-L¨ of Randomness

Examples (contd.):

5 K_U(x |n)≈n, for almost allx ∈ {0,1}ⁿ.

Proof: Upper bound K_U(x |n)≤n+C. Lower bound by a counting argument: less than 2^−k of strings compressible by more thank bits (Lecture 1).

Martin-L¨of Randomness

Stringx is said to beMartin-L¨of randomiff Ku(x|n)≥n. Consequence of point 5 above: An i.i.d. sequence of unbiased coin flips is with high probability Martin-L¨of random.

(61)

Martin-L¨ of Randomness

Examples (contd.):

Stringx is said to beMartin-L¨of randomiff Ku(x|n)≥n. Consequence of point 5 above: An i.i.d. sequence of unbiased coin flips is with high probability Martin-L¨of random.

(62)

Martin-L¨ of Randomness

Examples (contd.):

Stringx is said to beMartin-L¨of randomiff Ku(x|n)≥n.

Consequence of point 5 above: An i.i.d. sequence of unbiased coin flips is with high probability Martin-L¨of random.

(63)

Martin-L¨ of Randomness

Examples (contd.):

Stringx is said to beMartin-L¨of randomiff Ku(x|n)≥n.

Consequence of point 5 above: An i.i.d. sequence of unbiased coin flips is with high probability Martin-L¨of random.

(64)

Universal Prediction

Since the set of valid (halting) programs is required to be prefix-freewe can consider the probability distributionpⁿ_U:

pⁿ_U(x) = 2^−K^U^(x|n)

C , whereC = X

x∈Xⁿ

2^−K^U^(x|n).

Universal Probability Distribution

The distributionp_Uⁿ is universal in the sense that for any other computable distributionq, there is a constantC >0 such that

p_Uⁿ(x)≥C q(x) for allx ∈ Xⁿ. Proof idea: The universal computerU can imitate the Shannon-Fano prefix code with codelengths

log₂ 1 q(x)

.

(65)

Universal Prediction

pⁿ_U(x) = 2^−K^U^(x|n)

C , whereC = X

x∈Xⁿ

2^−K^U^(x|n).

p_Uⁿ(x)≥C q(x) for allx ∈ Xⁿ.

Proof idea: The universal computerU can imitate the Shannon-Fano prefix code with codelengths

log₂ 1 q(x)

.

(66)

Universal Prediction

pⁿ_U(x) = 2^−K^U^(x|n)

C , whereC = X

x∈Xⁿ

2^−K^U^(x|n).

p_Uⁿ(x)≥C q(x) for allx ∈ Xⁿ. Proof idea: The universal computerU can imitate the Shannon-Fano prefix code with codelengths

log₂ 1 q(x)

.

(67)

Universal Prediction

The universal probability distributionpⁿ_U is a good predictor.

This follows from the relationship between codelengths and probabilities (Kraft!):

K_U(x) is small ⇒ p_Uⁿ(x) is large

⇒

n

Y

i=1

p_Uⁿ(xi |x1, . . . ,xi−1) is large

⇒ pⁿ_U(x_i |x₁, . . . ,xi−1) is large for most i ∈ {1, . . . ,n}, wherex_i denotes theith bit in stringx.

(68)

Universal Prediction

⇒

n

Y

i=1

(69)

Universal Prediction

⇒

n

Y

i=1

(70)

Universal Prediction

⇒

n

Y

i=1

⇒ p_Uⁿ(x_i |x₁, . . . ,xi−1) is large for most i ∈ {1, . . . ,n}, wherex_i denotes theith bit in stringx.

(71)

Berry Paradox

The smallest integer that cannot be described in ten words?

Whatever this number is, we have just described (?) it in ten words.

The smallest uninteresting number?

Whatever this number is, it is quite interesting!

(72)

Berry Paradox

(73)

Berry Paradox

(74)

Berry Paradox

(75)

Non-computability

It is impossible to construct a general procedure (algorithm) to computeK_U(x).

Non-Computability

Kolmogorov complexityK_U : {0,1}^∗→Nis non-computable.

Proof: Assume, by way of contradiction, that it would be possible to computeKU(x). Then for anyM >0, the program

print a string x for which K_U(x)>M.

would print a string withK_U(x)>M. A contradiction follows by lettingM be larger than the Kolmogorov complexity of this program. Hence, it cannot be possible to computeK_U(x).

(76)

Non-computability

Non-Computability

Proof: Assume, by way of contradiction, that it would be possible to computeKU(x).

Then for any M >0, the program print a string x for which K_U(x)>M.

(77)

Non-computability

Non-Computability

print a string x for which KU(x)>M. would print a string withK_U(x)>M.

A contradiction follows by lettingM be larger than the Kolmogorov complexity of this program. Hence, it cannot be possible to computeK_U(x).

(78)

Non-computability

Non-Computability

print a string x for which KU(x)>M.

(79)

Summary: Kolmogorov complexity and MDL

Universal codes (or models) in MDL were defined to be universal with respect tosome model classM, which from an application point of view is “user-specified”.

There are universal codes with respect to quite general model classes (such as Lempel-Ziv for finite-order Markov models), but still this may feel a bit unsatisfactory from a philosophical point of view.

Kolmogorov complexity gives a code that is universal with respect to any computable model class, which seems the best we can hope for.

(80)

Summary: Kolmogorov complexity and MDL

(81)

Summary: Kolmogorov complexity and MDL

(82)

Summary: Kolmogorov complexity and MDL

Unfortunately Kolmogorov complexity itself is not computable, limiting its applicability in practive. However Kolmogorov complexity is useful as an idealization and for understanding our limitations.

One should also remember that even in principle, Kolmogorov complexity is defined only up to an additive constant (depending on the choice ofU).

(83)

Summary: Kolmogorov complexity and MDL

Unfortunately Kolmogorov complexity itself is not computable, limiting its applicability in practive. However Kolmogorov complexity is useful as an idealization and for understanding our limitations.

One should also remember that even in principle, Kolmogorov complexity is defined only up to an additive constant (depending on the choice ofU).

(84)

Basic Properties

2 Gambling

(85)

Gambling

Bet moneybx on horsex. Get moneyαxbx ifx wins (odds). Expected winE[bxαx] =P

pxαxbx.

Maximized by betting everything on arg maxpxαx.

(86)

Gambling

Bet moneyb_x on horsex. Get money α_xb_x ifx wins (odds).

Expected winE[bxαx] =P

pxαxbx.

(87)

Gambling

pxαxbx.

(88)

Gambling

pxαxbx.

(89)

Gambling

If odds are “fair”, thenα_x = 1 px

, and hence p_xα_xb_x =b_x for all i.

Assume now that we haveinside informationabout the winning horse.

Insider X Noisy Channel X^ Gambler

In the extreme case, ˆX =X, we know the outcome: V_n=α_x_iα_x₂· · ·α_x_nV₀

= 2^Gn

V₀ exponential rate of growth, G

whereV_t is the capital on tth step

, andG = ^log

Pα_xi

n .