Next: Relation to a Popular
Up: The Speed Prior: A
Previous: Computable Predictions
Machine Dependence / Suboptimal Computation of the Data:
Expected Loss Bounds
So far we have assumed the process computing the data is
(asymptotically) optimally efficient, running on a particular
universal computer, our reference machine. In general, however,
we cannot know the machine used to run this process.
Furthermore, the process may be nonoptimal even with respect
to its machine. For such reasons
we now relax our initial assumption, and show that
-based predictions on our reference machine still work well.
Consider a finite but unknown program computing
.
What if Postulate 1 holds but is not optimally
efficient, and/or computed on a computer that differs from
our reference machine? Then we effectively do not sample
beginnings from but from an alternative semimeasure
for any
whose computation through costs more than time. Can we
still predict well? Yes, because the
Speed Prior dominates : For all ,
|
(7) |
where is a constant depending on but not on ,
because FAST computes faster than , and thus
.
This dominance is all we need to apply Hutter's recent loss bounds
[9]:
In practice we have to use
instead of .
Does that cost us a lot? Again
the answer is no, since for any ,
|
(8) |
where is a constant independent of .
That is, in analogy to Corollary 1
(using analogous notation) we obtain
|
(9) |
To summarize: The loss that we are expected to receive
by predicting according to computable
instead
of the true
but unknown does not exceed the optimal loss by much.
Subsections
Next: Relation to a Popular
Up: The Speed Prior: A
Previous: Computable Predictions
Juergen Schmidhuber
2003-02-25
Back to Speed Prior page