Universal Inductors

post by Scott Garrabrant · 2016-09-14T00:09:42.000Z · LW · GW · 0 comments

Contents

  If P∞ and P′∞ are the limits of two different universal inductors, do they necessarily dominate each other? i.e. does there exist a constant ε>0 such that P′∞(σ)>εP∞(σ) for all prefixes σ?
None
No comments

Now that the Logical Induction paper is out, I am directing my attention towards decision theory. The approach I currently think will be most fruitful is attempting to make a logically updateless version of Wei Dai's Updateless Decision Theory. Abram Demski has posted on here about this, but I think Logical Induction provides a new angle with which we can attack the problem. This post will present an alternate way of viewing Logical Induction which I think will be especially helpful for building a logical UDT. (The Logical Induction paper is a prerequisite for this post.)

This post will make several informal claims without proof. Many of the claims are analogous to things proven in the Logical Induction paper, and the math is not substantially difficult. I might extend the paper to have a section talking about the following concepts more formally.

A Universal Inductor is an infinite sequence of probability distributions on infinite bit strings. Satisfying the following two properties:

  1. The function is computable, where is a finite prefix, and is the probability that an infinite bit string begins with the prefix .

  2. Consider the propositional theory whose th atom is identified with the event "the th bit in the infinite bit string is a 1." Then the probability distribution induces an function from sentences in the language of this theory to probabilities. The sequence of probability assignments must form a Logical Inductor over the empty deductive process.

Note that a Universal Inductor corresponds to a Logical Inductor, but the associated Logical Inductor will not have finite support, and so will be different from the one constructed in the paper. Never the less, Universal Inductors can be shown to exist using a similar construction. Note that the second condition technically implies the first, but I separate them for emphasis.

Here are some facts about Universal Inductors:

  1. The probability distributions converge to a limiting distribution on infinite bit strings, .

  2. This limiting distribution dominates the universal semi measure. In particular, every finite prefix is given nonzero probability.

  3. Given any consistent deductive process, we can construct a logical inductor over that deductive process simply by associating atoms of the theory with bits in the bit string (in an efficient computable manner), conditioning on the event corresponding to the th list in the deductive process, and taking the function from logical sentences to probabilities induced by that probability distribution. (Thus, a Universal inductor can be used to construct a Logical Inductor over PA by looking at some of the conditional probabilities, and can be used to construct a Logical Inductor over ZFC by looking at other conditional probabilities (Hence the name Universal Inductor))

The 2 major differences between the Universal Inductor and Logical Inductor formalisms are:

  1. Universal Inductors are probability distributions at every finite stage, not just in the limit, so we can more naturally talk about conditional probabilities at every stage.

  2. Universal Inductors are only over empty deductive processes, and we simulate nontrivial deductive processes only through conditioning.

I feel that this will especially make for a better framework for thinking about logical updatelessness.

Here is an open question about Universal Inductors:

If and are the limits of two different universal inductors, do they necessarily dominate each other? i.e. does there exist a constant such that for all prefixes ?

(This is equivalent to the analogous question about logical inductors over the same theory, but it feels more natural to state in this framework.)

0 comments

Comments sorted by top scores.