# On the equivalence of incompressibility and incompleteness in machine learning

## Motivation:

Motivated by the question of what problems are suitably addressed using methods in machine learning, I decided to formulate this general problem using Algorithmic Information Theory. My reason for this formulation is that the Kolmogorov Complexity $$K(\cdot)$$ appears to be a suitable measure of both incompressibility and epistemic uncertainty.

I specifically found an inequality that appears to have subtle epistemological implications. This inequality suggests that randomness is not observer independent, that there is a fundamental relationship between incompressibility and inextricable epistemic uncertainty(i.e. incompleteness) in machine learning, and that in some settings the bounds on epistemic uncertainty may be more important than bounded rationality.

I wonder whether this result and its epistemic implications may be known by a particular name as my colleagues in the machine learning community appear to be unfamiliar with this result and its consequences.

## Bounds on epistemic uncertainty via expected Kolmogorov Complexity:

Given the family of probabilistic models $$P_M$$, the Minimum Description Length of a dataset $$X$$ of $$N$$ samples from a discrete probability distribution $$P_X$$ relative to the optimal model $$\Omega \in P_M$$ is given by:

$$$$\mathbb{E}[K(X)] = H(X|\Omega) + H(\Omega) \tag{1}$$$$

where $$H(\Omega)$$ is the inextricable epistemic uncertainty of $$\Omega$$ concerning its own operation and $$H(X|\Omega)$$ is the inextricable epistemic uncertainty of $$\Omega$$ relative to $$P_X$$. For clarity, $$\mathbb{E}[K(X)]$$ is simultaneously a measure of incompressibility, algorithmic randomness and incompleteness where incompleteness is understood as a measure of inextricable epistemic uncertainty. The reason for this three-way correspondence is given in the next section.

In (1) I used the fact that $$\Omega$$ is a probabilistic program so it makes sense to compute the expected Kolmogorov Complexity, as well as the fact that the expected Kolmogorov Complexity of a random variable equals the Shannon entropy of that variable [1]. I also implicitly assumed that ergodic assumptions are satisfied, which is the case in the regime of repeatable scientific experiments.

Now, from (1) we may derive the following upper and lower bounds on epistemic uncertainty:

$$$$H(\Omega) \leq \mathbb{E}[K(X)] \leq N \cdot H(P_X) \tag{2}$$$$

where the upper-bound results from an application of Shannon's source coding theorem. My question concerns the non-trivial epistemological implications of (2).

## Analysis:

If $$\Omega$$ is identified with what physicists call an observer i.e. a system that collects data $$X$$ and tests hypotheses concerning the probabilistic structure of $$X$$ in order to discover $$P_X$$ then we find that relative to this observer, incompressibility, algorithmic randomness and incompleteness(as defined) are all equivalent to $$\mathbb{E}[K(X)]$$. We also find that the inextricable epistemic uncertainty of $$\Omega$$ relative to $$P_X$$ is bounded by:

$$$$\mathbb{E}[K(X)] \geq H(\Omega) \tag{3}$$$$

This suggests that perceived randomness is not observer independent. More generally it suggests that the scientific method is not observer independent and it provides an information-theoretic formulation of Planck's claim that:

Science can’t solve the ultimate mystery of nature. And that is because, in the last analysis, we ourselves are a part of the mystery that we are trying to solve.-Planck

To be precise, the epistemic uncertainty of $$\Omega$$ concerning itself is exactly $$H(\Omega)$$ i.e. the Minimum Description Length of $$\Omega$$ relative to a universal computer. It follows that the structure underlying the fundamental axioms embedded in $$\Omega$$ is beyond the knowledge of $$\Omega$$. In particular, since $$\Omega$$ implicitly contains a theory of computation and all such theories require arithmetic an optimal encoding of arithmetic is beyond the knowledge of $$\Omega$$ independently of the amount of data and computational resources available to $$\Omega$$.

I have colleagues in the machine learning community that would like to use AI to investigate the Riemann Hypothesis, and I suspect that a closer inspection of (3) would provide a very useful analysis of the epistemic limits of such an enterprise. Furthermore, I think a closer inspection of the inequality (2) might also explain why the most fundamental theories in physics, Quantum Field Theory in particular, appear to describe algorithmically random phenomena.

### The precise question:

To be precise I am looking for quantitative bounds on epistemic uncertainty expressed in terms of the Expected Kolmogorov Complexity as in (2) from which we may deduce an observer dependence theorem as conjectured by Max Planck. This may implicitly require assuming the Physical Church-Turing thesis, which many theoretical computer scientists and theoretical physicists find plausible. The implications of this thesis are consistent with the 'unreasonable effectiveness of mathematics' in the natural sciences [4].

Note: From these insights I recently managed to derive the prime number theorem using information-theoretic arguments.

## References:

1. Peter Grünwald and Paul Vitányi. Shannon Information and Kolmogorov Complexity. 2010.
2. Olivier Rioul. This is IT: A Primer on Shannon’s Entropy and Information. Séminaire Poincaré. 2018.
3. Marcus Hutter. Algorithmic information theory. Scholarpedia. 2007.
4. Eugene Wigner. The Unreasonable Effectiveness of Mathematics in the Natural Sciences. 1960.
5. Aidan Rocke (https://mathoverflow.net/users/56328/aidan-rocke), information-theoretic derivation of the prime number theorem, URL (version: 2021-02-20): https://mathoverflow.net/q/384109
• Can you make the question more precise? Are you after some impossibility result? Feb 20 at 20:54
• I am looking for quantitative bounds on epistemic uncertainty expressed in terms of the Expected Kolmogorov Complexity as in (2) from which we may deduce an observer dependence theorem as conjectured by Max Planck. Feb 20 at 21:26
• How is epistemic uncertainty formally defined? Feb 20 at 21:34
• @Aryeh It is defined in terms of (1) for the reason that algorithmic randomness may not be diminished by methods in statistical learning. So epistemic uncertainty is a harder bound on knowledge discovery unlike statistical uncertainty which may be reduced with enough data. Feb 20 at 21:47