This page summarizes many of the key terms, in sufficient generality for future discussions. Much of this content is inspired by Li & Vitányi (2008).
4.1.1The primitives of reasoning¶
Below we describe some of the essential concepts for discussing reasoning:
Observations: data observed from some source.
Hypothesis: a model for describing the source of some observations.
Likelihood: a numerical measure of an hypothesis’ credibility.
Complexity notion: a numerical measure of an hypothesis’ inherent complexity against some fixed set of simple primitives.
Selection: any procedure for selecting or preferring an hypothesis.
Reasoning: any procedure for assigning and updating likelihoods to a class of hypotheses.
4.1.2Principles for selection and reasoning over hypotheses¶
Next we describe some of the principles that guide how we approach reasoning:
Induction (a.k.a., inductive reasoning): a form of reasoning which reassigns likelihoods to hypotheses upon receiving more observations.
Epicurus’ Principle of Multiple Explanations: a principle of induction which asserts that each hypothesis which is consistent with all observations ought to be considered with some nonzero likelihood.
Occam’s Razor Principle: a principle of selection which prefers the simplest hypothesis which is consistent with all observations.
Or, more generally, the principle of reasoning which asserts that simpler hypotheses ought to be assigned with greater likelihoods.
Minimum Description Length (MDL) Principle: the principle of selection which prefers the hypothesis which simultaneously has the (1) simplest description and (2) simplest explanation of the observations.
Bayes’ Rule: a mathematical rule for induction which quantifies how an hypothesis’s likelihood should be updated given additional observations: via conditional probabilities.
4.1.3Recap on Computability¶
An algorithm is any procedure implementable by an oracle Turing machine equipped with an appropriate oracle.
An effective algorithm is any procedure implementable by a regular Turing machine, or an algorithm realizable by any Turing-complete programming language. I.e., “computable” or “decidable”.
A compression algorithm is an algorithm which is interpreted as finding alternative representations for its inputs. I.e., an algorithm over some domain of “finitary objects” which is algorithmically invertible over its whole domain: so there must exist another algorithm being the inverse map, and vice versa.
Usually interpret the forward map as the compression step, and the backward map as the decompression step.
Invertibility axiom ⇒ both the forward and backward maps are injective.
“Lossy” compression relaxes invertibility: usually just ask for the forward map to satisfy some property across its domain with respect to some notion of “resemblance” between the original input and a
recover(forward(input))over the domain of the forward map.
An effective compression algorithm is a compression algorithm realized by effective forward and backward algorithms.
A complexity notion is just a map which assigns some score (say, from some totally ordered set like ) to its domain. A map is reasonably generic for our purposes. Interpret smaller values as signifying less complexity.
A complexity notion may be “algorithmic” if evaluating only involves answering questions about how algorithms interact with the input.
It might be universal with respect to some class of complexity notions if it “dominates”, “simulates”, or otherwise reasonably approximates an extremal scoring among all the complexity notions from that class.
It might qualify as an entropy notion if it satisfies some universality property across a class of other complexity notions.
It might satisfy the Kraft inequality if the sum converges. While this may look arbitrary, it proves to be very useful for recasting entropy in terms of measure theory.
Randomness is the notion of inscrutability with respect to the tools available to you:
If the tool = all algorithms ⇒ Shannon entropy.
If the tool = all effective algorithms ⇒ Kolmogorov complexity.
If the tool = ~poly-time algorithms ⇒ epiplexity (via pseudo-randomness).
4.1.4Reasoning up to computability¶
Perfect induction: induction by Bayes’ Rule using the true prior distribution on hypotheses, i.e., the distribution actually governing the source of the observations. Its predictions are necessarily optimal.
Solomonoff Induction: a method for performing “perfect” induction over any computable prior probability distribution, using the optimal lower semi-computable continuous semimeasure and by applying Bayes’ Rule.
Universal prior distribution: a lower semi-computable, continuous semi-measure (so, assigning non-negative likelihoods to all hypotheses so that they sum to at most 100%) which can essentially play the role of any prior distribution on hypotheses in Solomonoff induction, without significant sacrifice in reasoning capabilities.
- Li, M., & Vitányi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications. Springer.