Information Theory for ML10 / 16

Module 10. Algorithmic Information Theory: Shortest Descriptions, MDL, and Universal Prediction

Choose your answers and select “Check”. Numbers accept a decimal point, comma, or simple fraction. Answers and drafts are saved in this browser and shared between RU/EN.

Checked: 0 / 25 · Correct: 0

Question 10.2.1

10.2. The shortest program as a description length

What does prefix Kolmogorov complexity $K_U(x)$ measure?

One correct optionAThe semantic value of the stringBThe entropy of an unknown distribution that generated

x

CThe runtime of the fastest algorithmDThe length of the shortest self-delimiting program for

x

on a fixed universal machine

U

A) The semantic value of the string

B) The entropy of an unknown distribution that generated $x$

C) The runtime of the fastest algorithm

D) The length of the shortest self-delimiting program for $x$ on a fixed universal machine $U$

Answer and explanation

Correct answer: D. K_U(x) measures program length, not runtime, semantics, or probability without a specified model.

Question 10.2.2

10.2. The shortest program as a description length

Why does a general upper bound for prefix complexity contain overhead beyond $|x|$ ?

One correct optionAA universal machine must be slowBPrefix complexity is defined only for random stringsCThe string is always encrypted firstDThe program must be self-delimiting, so the decoder must identify where the length description ends and

x

begins

A) A universal machine must be slow

B) Prefix complexity is defined only for random strings

C) The string is always encrypted first

D) The program must be self-delimiting, so the decoder must identify where the length description ends and $x$ begins

Answer and explanation

Correct answer: D. A typical bound is K(x)≤|x|+K(|x|)+O(1).

Question 10.2.3

10.2. The shortest program as a description length

What does the invariance theorem state?

One correct optionAAn optimal universal machine simulates another prefix machine with an additive constant independent of

x

BEvery universal machine has the same shortest programC

K(x)

is completely independent of programming languageDThe interpreter cost is always zero

A) An optimal universal machine simulates another prefix machine with an additive constant independent of $x$

B) Every universal machine has the same shortest program

C) $K(x)$ is completely independent of programming language

D) The interpreter cost is always zero

Answer and explanation

Correct answer: A. The machine remains part of the definition; the theorem controls the difference by a fixed interpreter cost.

Question 10.2.4

10.2. The shortest program as a description length

How should $K(x\mid y)$ be interpreted?

One correct optionAThe length of the shortest additional description of

x

when

y

is already available to the decoderBThe Hamming distance between

x

and

y

CThe decoding time of

x

DThe entropy of

y

after observing

x

A) The length of the shortest additional description of $x$ when $y$ is already available to the decoder

B) The Hamming distance between $x$ and $y$

C) The decoding time of $x$

D) The entropy of $y$ after observing $x$

Answer and explanation

Correct answer: A. y is side information, and the quantity concerns two individual objects.

Question 10.2.5

10.2. The shortest program as a description length

Which statement about a short algorithmic description is correct?

One correct optionAIt automatically provides a causal modelBIt proves that an intelligent agent created the objectCgzip will always find itDIt is evidence of regularity, but does not guarantee meaning, truth, usefulness, or fast computation

A) It automatically provides a causal model

B) It proves that an intelligent agent created the object

C) gzip will always find it

D) It is evidence of regularity, but does not guarantee meaning, truth, usefulness, or fast computation

Answer and explanation

Correct answer: D. Description length and semantic or computational properties are different levels of analysis.

Question 10.3.1

10.3. Incompressibility, uncomputability, and real compressors

According to the counting argument, what is the largest possible fraction of $n$ -bit strings with $K(x)<n-c$ ?

One correct optionA

1/c

BLess than

2^{-c}

CExactly

1/2

DIt approaches one

A) $x$

B) Less than $x$

C) Exactly $1/2$

D) It approaches one

Answer and explanation

Correct answer: B. There are fewer than 2^(n-c) programs shorter than n-c and 2^n strings of length n.

Question 10.3.2

10.3. Incompressibility, uncomputability, and real compressors

What computability property does $K(x)$ have?

One correct optionAIt is computable, but only exponentially slowlyBIt is lower semicomputableCIt equals the length of the best ZIP archiveDIt is upper semicomputable but uncomputable

A) It is computable, but only exponentially slowly

B) It is lower semicomputable

C) It equals the length of the best ZIP archive

D) It is upper semicomputable but uncomputable

Answer and explanation

Correct answer: D. Program enumeration improves upper bounds but cannot certify that the minimum has been reached.

Question 10.3.3

10.3. Incompressibility, uncomputability, and real compressors

What does a real lossless compressor $C$ provide for $K(x)$ ?

One correct optionAAn exact value within one bitBA lower boundCAn unbiased statistical estimateDA computable upper bound

K(x)\le |C(x)|+c_C

A) An exact value within one bit

B) A lower bound

C) An unbiased statistical estimate

D) A computable upper bound $x$

Answer and explanation

Correct answer: D. The constant pays for the decoder, format, and input conventions.

Question 10.3.4

10.3. Incompressibility, uncomputability, and real compressors

Why can a PRNG stream with a short seed compress poorly under gzip despite having small $K(x)$ relative to its length?

One correct optionAgzip searches a restricted class of regularities rather than enumerating all programsBA PRNG must use genuine physical randomnessCKolmogorov complexity applies only to textDThe seed is not part of the description

A) gzip searches a restricted class of regularities rather than enumerating all programs

B) A PRNG must use genuine physical randomness

C) Kolmogorov complexity applies only to text

D) The seed is not part of the description

Answer and explanation

Correct answer: A. The short generative description may lie outside the language of the chosen compressor.

Question 10.4.1

10.4. Where Shannon and Kolmogorov meet

How are the entropy of a computable distribution $P$ and expected prefix complexity related?

One correct optionAThey are exactly equal for every individual outcomeB

\mathbb E K(X)\le0

H_2(P)\le\mathbb E K(X)\le H_2(P)+K(P)+O(1)

DThey are unrelated even in expectation

A) They are exactly equal for every individual outcome

B) $x$

C) $y$

D) They are unrelated even in expectation

Answer and explanation

Correct answer: C. The upper bound additionally pays for describing the distribution; on long blocks this cost vanishes per symbol.

Question 10.5.1

10.5. Algorithmic probability and Solomonoff induction

Why is $2^{-|p|}$ a natural weight for a prefix program $p$ ?

One correct optionAAll programs have the same lengthBPrefix programs satisfy Kraft's inequality, so these weights sum to at most oneCThis choice makes the universal predictor computableDThe weight is independent of the universal machine

A) All programs have the same length

B) Prefix programs satisfy Kraft's inequality, so these weights sum to at most one

C) This choice makes the universal predictor computable

D) The weight is independent of the universal machine

Answer and explanation

Correct answer: B. Prefix-freeness turns program lengths into admissible code weights.

Question 10.5.2

10.5. Algorithmic probability and Solomonoff induction

How does the sequential Solomonoff $M(x)$ differ from an ordinary probability measure?

One correct optionAIt is always uniformBIt is a semimeasure: mass may be lost to programs that halt or compute foreverCIt does not use programsDIt is defined only for a one-symbol alphabet

A) It is always uniform

B) It is a semimeasure: mass may be lost to programs that halt or compute forever

C) It does not use programs

D) It is defined only for a one-symbol alphabet

Answer and explanation

Correct answer: B. Hence M(x)≥M(x0)+M(x1) in general.

Question 10.5.3

10.5. Algorithmic probability and Solomonoff induction

What does universal dominance express?

One correct optionAAll computable models have the same priorB

M

equals the true source after one symbolCFor any computable model

\mu

M

assigns at least

\mu(x)

times a factor determined by the model's description complexityDEvery LLM implements

M

A) All computable models have the same prior

B) $x$ equals the true source after one symbol

C) For any computable model $\mu$ , $M$ assigns at least $\mu(x)$ times a factor determined by the model's description complexity

D) Every LLM implements $M$

Answer and explanation

Correct answer: C. Typically M(x)≥2^(-K(μ)-O(1))μ(x), which bounds excess cumulative log loss.

Question 10.5.4

10.5. Algorithmic probability and Solomonoff induction

Why can Solomonoff induction not be implemented directly?

One correct optionAThe universal mixture is uncomputable because of the halting problemBIt requires a very large but finite datasetCIt applies only to Gaussian sourcesDIt cannot use conditional probabilities

A) The universal mixture is uncomputable because of the halting problem

B) It requires a very large but finite dataset

C) It applies only to Gaussian sources

D) It cannot use conditional probabilities

Answer and explanation

Correct answer: A. One cannot decide which additional programs will eventually contribute to the required prefix.

Question 10.5.5

10.5. Algorithmic probability and Solomonoff induction

[Optional]

What distinction is hidden by the popular notation “universal probability $\approx2^{-K}$ ”?

One correct optionAThe two expressions are identical for every choice of universal machineBOne formula uses bits and the other always uses natsCThe sequential semimeasure contains no programsDFinite-output and sequential semimeasures use related but nonidentical machine models and complexity notions

A) The two expressions are identical for every choice of universal machine

B) One formula uses bits and the other always uses nats

C) The sequential semimeasure contains no programs

D) Finite-output and sequential semimeasures use related but nonidentical machine models and complexity notions

Answer and explanation

Correct answer: D. A coding theorem must specify whether it concerns a finite output, a prefix, and the corresponding complexity notion.

Question 10.6.1

10.6. MDL: the model must pay for itself

What does a simple two-part MDL code minimize?

One correct optionATraining loss onlyBParameter count onlyC

L(h)+L(D\mid h)

DTraining time only

A) Training loss only

B) Parameter count only

C) $L(h)+L(D\mid h)$

D) Training time only

Answer and explanation

Correct answer: C. The model is paid for together with the residual data it fails to explain.

Question 10.6.2

10.6. MDL: the model must pay for itself

What does a prequential code measure beyond one final accuracy value?

One correct optionAOnly the size of the weight fileBHow quickly the learning algorithm begins assigning good probabilities to new labelsCAccelerator temperatureDExact Kolmogorov complexity

A) Only the size of the weight file

B) How quickly the learning algorithm begins assigning good probabilities to new labels

C) Accelerator temperature

D) Exact Kolmogorov complexity

Answer and explanation

Correct answer: B. Early mistakes increase message length even when final performance is equal.

Question 10.6.3

10.6. MDL: the model must pay for itself

When does a Gaussian prior induce an $L_2$ penalty as MAP?

One correct optionAIn a fixed parameterization with the corresponding prior and likelihoodBFor every optimizer and parameterization without conditionsCOnly for discrete parametersDNever

A) In a fixed parameterization with the corresponding prior and likelihood

B) For every optimizer and parameterization without conditions

C) Only for discrete parameters

D) Never

Answer and explanation

Correct answer: A. A literal coding interpretation for continuous parameters also requires a base measure and representation precision.

Question 10.7.1

10.7. Similarity through shared structure

What does practical NCD substitute for uncomputable $K$ ?

One correct optionAPearson correlationBEuclidean distanceCLengths produced by a particular compressor

C

DNeural-network parameter count

A) Pearson correlation

B) Euclidean distance

C) Lengths produced by a particular compressor $L(h)+L(D\mid h)$

D) Neural-network parameter count

Answer and explanation

Correct answer: C. NCD therefore inherits the inductive bias, headers, and limitations of the chosen compressor.

Question 10.7.2

10.7. Similarity through shared structure

Why are both $C(xy)$ and $C(yx)$ sometimes computed for NCD?

One correct optionAA real compressor may be sensitive to concatenation orderBTo double the datasetCBecause

K(x)=K(y)

DTheoretical NID is always negative

A) A real compressor may be sensitive to concatenation order

B) To double the dataset

C) Because $L(h)+L(D\mid h)$

D) Theoretical NID is always negative

Answer and explanation

Correct answer: A. Taking the minimum or average reduces artificial asymmetry.

Question 10.8.1

10.8. LLMs and universal prediction

Which connection between a language model and compression is exact?

One correct optionAA probabilistic predictor plus a matching entropy coder yields a lossless compressorBLow perplexity proves understandingCContext length equals the Kolmogorov complexity of the textDAn LLM sums over all computable programs

A) A probabilistic predictor plus a matching entropy coder yields a lossless compressor

B) Low perplexity proves understanding

C) Context length equals the Kolmogorov complexity of the text

D) An LLM sums over all computable programs

Answer and explanation

Correct answer: A. Prediction–compression equivalence is operational; semantic conclusions require separate evidence.

Question 10.8.2

10.8. LLMs and universal prediction

What is the most accurate description of the Bayesian interpretation of in-context learning?

One correct optionAIt is a universal theorem for every Transformer and promptBIt can be derived rigorously in specific generative settings and can be a useful model, but is not a universal mechanismCICL is independent of the pretraining distributionDIt makes an LLM equivalent to the Solomonoff predictor

A) It is a universal theorem for every Transformer and prompt

B) It can be derived rigorously in specific generative settings and can be a useful model, but is not a universal mechanism

C) ICL is independent of the pretraining distribution

D) It makes an LLM equivalent to the Solomonoff predictor

Answer and explanation

Correct answer: B. A structured mixture of HMMs is one setting in which such an analysis can be proved.

Question 10.9.1

10.9. Mathematical deepening: AIXI

[Optional]

What is the precise status of AIXI?

One correct optionAA practical polynomial-time algorithmBA machine-independent upper bound on intelligenceCAn uncomputable normative object combining universal prediction with expected-reward planningDA standard supervised classifier

A) A practical polynomial-time algorithm

B) A machine-independent upper bound on intelligence

C) An uncomputable normative object combining universal prediction with expected-reward planning

D) A standard supervised classifier

Answer and explanation

Correct answer: C. Its properties depend on the universal machine, environment class, reward, and other details of the setup.

Question 10.10.1

10.10. Optional physical bridge

[Optional]

What does the bound $k_BT\ln2$ directly concern?

One correct optionAEvery FLOP regardless of hardwareBThe minimum average heat dissipated by quasistatic erasure of a fair bitCShortest-program lengthDEvery LLM token

A) Every FLOP regardless of hardware

B) The minimum average heat dissipated by quasistatic erasure of a fair bit

C) Shortest-program length

D) Every LLM token

Answer and explanation

Correct answer: B. Relating it to a real device requires a physical implementation and identification of logically irreversible operations.

Question 10.12.1

10.12. Takeaways

Which statement best summarizes the boundaries of the module?

One correct optionAThe best archive program computes

K(x)

BCompression, prediction, understanding, and intelligence are one numberCBefore comparing “complexity,” specify the code, language, decoder, precision, compute budget, and included costsDA short program always runs quickly

A) The best archive program computes $x$

B) Compression, prediction, understanding, and intelligence are one number

C) Before comparing “complexity,” specify the code, language, decoder, precision, compute budget, and included costs

D) A short program always runs quickly

Answer and explanation

Correct answer: C. The module studies several related but distinct notions of complexity and description cost.