- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Juergen Schmidhuber <juergen.domain.name.hidden>

Date: Fri, 23 Jan 2004 11:07:33 +0100

I browsed through recent postings and hope

this delayed but self-contained message can clarify

a few things about probabilities and measures

and predictability etc.

What is the probability of an integer being, say,

a square? This question does not make sense without

a prior probability distribution on the integers.

This prior cannot be uniform. Try to find one!

Under _any_ distribution some integers must be

more likely than others.

Which prior is good? Is there a `best' or

`universal' prior? Yes, there is. It assigns to

each integer n as much probability as any other

computable prior, save for a constant factor that

does not depend on n. (A computable prior can be

encoded as a program that takes n as input and

outputs n's probability, e.g., a program that

implements Bernoulli's formula, etc.)

Given a set of priors, a universal prior is

essentially a weighted sum of all priors in the

set. For example, Solomonoff's famous weighted sum

of all enumerable priors will assign at least as

much probability to any square integer as any

other computable prior, save for a constant

machine-dependent factor that becomes less and

less relevant as the integers get larger and

larger.

Now let us talk about all computable universe

histories. Some are finite, some infinite. Each

has at least one program that computes it. Again

there is _no_ way of assigning equal probability

to all of them! Many are tempted to assume a

uniform distribution without thinking much about

it, but there is _no_ such thing as a uniform

distribution on all computable universes, or on

all axiomatic mathematical structures, or on

all logically possible worlds, etc!

(Side note: There only is a uniform _measure_ on

the finitely many possible history _beginnings_

of a given size, each standing for an uncountable

_set_ of possible futures. Probabilities

refer to single objects, measures to sets.)

It turns out that we can easily build universal

priors using Levin's important concept of self-

delimiting programs. Such programs may

occasionally execute the instruction "request new

input bit"; the bit is chosen randomly and will

remain fixed thereafter. Then the probability of

some universe history is the probability of guessing

a program for it. This probability is `universal'

as it does not depend much on the computer (whose

negligible influence can be buried in a constant

universe-independent factor). Some programs halt or

go in an infinite loop without ever requesting

additional input bits. Universes with at least one

such short self-delimiting program are more probable

than others.

To make predictions about some universe, say,

ours, we need a prior as well. For instance,

most people would predict that next Tuesday it

won't rain on the moon, although there are

computable universes where it does. The anthropic

principle is an _insufficient_ prior that does not

explain the absence of rain on the moon - it does

assign cumulative probability 1.0 to the set of all

universes where we exist, and 0.0 to all the other

universes, but humans could still exist if it did

rain on the moon occasionally. Still, many tend to

consider the probability of such universes as small,

which actually says something about their prior.

We do not know yet the true prior from which

our universe is sampled - Schroedinger's wave

function may be an approximation thereof. But it

turns out that if the true prior is computable

at all, then we can in principle already predict

near-optimally, using the universal prior instead:

http://www.idsia.ch/~juergen/unilearn.html

Many really smart physicists do not know this

yet. Technical issues and limits of computable

universes are discussed in papers available at:

http://www.idsia.ch/~juergen/computeruniverse.html

Even stronger predictions using a prior based

on the fastest programs (not the shortest):

http://www.idsia.ch/~juergen/speedprior.html

-Juergen Schmidhuber

Received on Fri Jan 23 2004 - 05:08:33 PST

Date: Fri, 23 Jan 2004 11:07:33 +0100

I browsed through recent postings and hope

this delayed but self-contained message can clarify

a few things about probabilities and measures

and predictability etc.

What is the probability of an integer being, say,

a square? This question does not make sense without

a prior probability distribution on the integers.

This prior cannot be uniform. Try to find one!

Under _any_ distribution some integers must be

more likely than others.

Which prior is good? Is there a `best' or

`universal' prior? Yes, there is. It assigns to

each integer n as much probability as any other

computable prior, save for a constant factor that

does not depend on n. (A computable prior can be

encoded as a program that takes n as input and

outputs n's probability, e.g., a program that

implements Bernoulli's formula, etc.)

Given a set of priors, a universal prior is

essentially a weighted sum of all priors in the

set. For example, Solomonoff's famous weighted sum

of all enumerable priors will assign at least as

much probability to any square integer as any

other computable prior, save for a constant

machine-dependent factor that becomes less and

less relevant as the integers get larger and

larger.

Now let us talk about all computable universe

histories. Some are finite, some infinite. Each

has at least one program that computes it. Again

there is _no_ way of assigning equal probability

to all of them! Many are tempted to assume a

uniform distribution without thinking much about

it, but there is _no_ such thing as a uniform

distribution on all computable universes, or on

all axiomatic mathematical structures, or on

all logically possible worlds, etc!

(Side note: There only is a uniform _measure_ on

the finitely many possible history _beginnings_

of a given size, each standing for an uncountable

_set_ of possible futures. Probabilities

refer to single objects, measures to sets.)

It turns out that we can easily build universal

priors using Levin's important concept of self-

delimiting programs. Such programs may

occasionally execute the instruction "request new

input bit"; the bit is chosen randomly and will

remain fixed thereafter. Then the probability of

some universe history is the probability of guessing

a program for it. This probability is `universal'

as it does not depend much on the computer (whose

negligible influence can be buried in a constant

universe-independent factor). Some programs halt or

go in an infinite loop without ever requesting

additional input bits. Universes with at least one

such short self-delimiting program are more probable

than others.

To make predictions about some universe, say,

ours, we need a prior as well. For instance,

most people would predict that next Tuesday it

won't rain on the moon, although there are

computable universes where it does. The anthropic

principle is an _insufficient_ prior that does not

explain the absence of rain on the moon - it does

assign cumulative probability 1.0 to the set of all

universes where we exist, and 0.0 to all the other

universes, but humans could still exist if it did

rain on the moon occasionally. Still, many tend to

consider the probability of such universes as small,

which actually says something about their prior.

We do not know yet the true prior from which

our universe is sampled - Schroedinger's wave

function may be an approximation thereof. But it

turns out that if the true prior is computable

at all, then we can in principle already predict

near-optimally, using the universal prior instead:

http://www.idsia.ch/~juergen/unilearn.html

Many really smart physicists do not know this

yet. Technical issues and limits of computable

universes are discussed in papers available at:

http://www.idsia.ch/~juergen/computeruniverse.html

Even stronger predictions using a prior based

on the fastest programs (not the shortest):

http://www.idsia.ch/~juergen/speedprior.html

-Juergen Schmidhuber

Received on Fri Jan 23 2004 - 05:08:33 PST

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:09 PST
*