[section] [section]

[section] [section] [section]

Optimal Predictors: A Bayesian Notion of Approximation Algorithm

AbstractThe concept of an "approximation algorithm" is usually only applied to optimization problems since in optimization problems the performance of the algorithm on any given input is a continuous parameter. We introduce a new concept of approximation applicable to decision problems and functions, inspired by Bayesian probability. From the perspective of a Bayesian reasoner with limited computational resources, the answer to a problem that cannot be solved exactly is uncertain and therefore should be described by a random variable. It thus should make sense to talk about the expected value of this random variable, an idea we formalize in the language of average-case complexity theory by introducing the concept of "optimal predictor." We show that optimal predictors exhibit many parallels with "classical" probability theory, prove some existence theorems and demonstrate some applications to artificial general intelligence.

[section] [section]

[section] [section] [section]

Imagine you are strolling in the city with a friend when a car passes by with the license plate number “7614829”. Your friend proposes a wager, claiming that the number is composite and offering 10 : 1 odds in your favor. Knowing that your friend has no exceptional ability in mental arithmetic and that it’s highly unlikely they saw this car before, you realize they are just guessing. Your mental arithmetic is also insufficient to test the number for primality, but is sufficient to check that \(7614829 \equiv 1 \pmod{3}\) and \(\frac{1}{\ln 7614829} \approx 0.06\). Arguing from the prime number theorem and observing that 7614829 is odd and is divisible neither by 3 nor by 5, you conclude that the probability 7614829 is prime is \(\frac{1}{\ln 7614829} \times 2 \times \frac{3}{2} \times \frac{5}{4} \approx 22\%\). Convinced that the odds are in your favor you accept the bet^{1}.

Alas, \(7614829 = 271 \times 28099\).↩

[section] [section]

[section] [section] [section]

From the perspective of frequentist probability the question “what is the probability 7614829 is prime?” seems meaningless, since it is either prime or not so there is no frequency to observe (unless the frequency is 0 or 1). From a Bayesian perspective, probability represents a degree of confidence, however in classical Bayesian probability theory it is assumed the only source of uncertainty is the lack of information. The number 7614829 already contains all information needed to determine whether it’s prime so the probability again has to be 0 or 1. However, real life uncertainty is not only information-theoretic but also complexity-theoretic. Even when we have all information to obtain the answer, out computational resources are limited so we remain uncertain. The rigorous formalization of this idea is the main goal of the present work.

[section] [section]

[section] [section] [section]

The idea of assigning probabilities to purely mathematical questions was studied by several authors (Gaifman 2004)(Hutter 2013)(Demski 2012)(Christiano 2014)(Garrabrant 2015), mainly in the setting of formal logic. That is, their approach was looking for functions from the set of sentences in some formal logical language to \([0,1]\). However, although there is a strong intuitive case for assigning probabilities to sentences like “7614829 is prime” it is much less clear there is a meaningful assignment of probabilities to sentences like \(\varphi_1 := \text{"there are no odd perfect numbers"}\) or (even worse) \(\varphi_2 := \text{"there is no cardinality } \kappa \text{ s.t. } \aleph_0 < \kappa < 2^{\aleph_0} \text{."}\). The problem is that a wager on \(\varphi_1\) can only become resolved in one direction while a wager on \(\varphi_2\) cannot be resolved at all.