论文标题
无限序列的预测和算法统计
Predictions and algorithmic statistics for infinite sequence
论文作者
论文摘要
考虑以下预测问题。假设有一个块框，可以根据二进制树上的一些未知的计算分布产生位。我们知道第一个$ n $ bits $ x_1 x_2 \ ldots x_n $。我们想知道下一块等于$ 1 $的事件的概率。 Solomonoff建议将通用半含量M $用于解决此任务。他证明，对于每一个可计算的分布$ p $，对于\ {0,1 \} $的每一个$ b \ the以下内容：$$ \ sum_ {n = 1}^{\ sum_ {x：x：l（x）方面：Hutter和Muchnik证明，有一个通用的半点$ M $，可计算的分布$ P $和一个随机（在Martin -l {Ö} F Sense）序列$ x_1 x_1 x_2 \ ldots $，使得$ \ lim_ {n \ to \ fo \ to \ fo \ fo \ in \ infty} x_1 \ ldots x_n）\ nrightArrow 0 $。我们建议一种新的预测方式。对于每个有限的字符串$ x $，我们根据$ x $的最佳（某些宽度）分配预测新的位。我们证明了类似的结果，即我们的预测方式的所罗门诺夫定理。我们还表明，我们的预测方法没有那种负面方面作为所罗门诺夫的方法。
Consider the following prediction problem. Assume that there is a block box that produces bits according to some unknown computable distribution on the binary tree. We know first $n$ bits $x_1 x_2 \ldots x_n$. We want to know the probability of the event that that the next bit is equal to $1$. Solomonoff suggested to use universal semimeasure $m$ for solving this task. He proved that for every computable distribution $P$ and for every $b \in \{0,1\}$ the following holds: $$\sum_{n=1}^{\infty}\sum_{x: l(x)=n} P(x) (P(b | x) - m(b | x))^2 < \infty\ .$$ However, Solomonoff's method has a negative aspect: Hutter and Muchnik proved that there are an universal semimeasure $m$, computable distribution $P$ and a random (in Martin-L{ö}f sense) sequence $x_1 x_2\ldots$ such that $\lim_{n \to \infty} P(x_{n+1} | x_1\ldots x_n) - m(x_{n+1} | x_1\ldots x_n) \nrightarrow 0$. We suggest a new way for prediction. For every finite string $x$ we predict the new bit according to the best (in some sence) distribution for $x$. We prove the similar result as Solomonoff theorem for our way of prediction. Also we show that our method of prediction has no that negative aspect as Solomonoff's method.
