%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Convergence of Discrete MDL for Sequential Prediction %% %% Jan Poland & Marcus Hutter: Start: 11.06.03 %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt,twoside]{article} \usepackage{latexsym,amssymb} \topmargin=0mm \oddsidemargin=5mm \evensidemargin=5mm \textwidth=15cm \textheight=22cm \sloppy \newenvironment{keywords}{\centerline{\bf\small Keywords}\vspace{-2ex}\begin{quote}\small}{\par\end{quote}\vskip 1ex} \newtheorem{nummer}{\hspace*{-0.33em}}[section] \newenvironment{Def} {\begin{nummer} {\bf Definition.} \begin{rm}} {\end{rm} \end{nummer}} \newenvironment{Lemma} {\begin{nummer} {\bf Lemma.}} {\end{nummer}} \newenvironment{Prop} {\begin{nummer} {\bf Proposition.}} {\end{nummer}} \newenvironment{Theorem} {\begin{nummer} {\bf Theorem.}} {\end{nummer}} \newenvironment{Cor} {\begin{nummer} {\bf Corollary.}} {\end{nummer}} \newenvironment{Remark} {\begin{nummer} {\bf Remark.}} {\end{nummer}} \newenvironment{Conj} {\begin{nummer} {\bf Conjecture.}} {\end{nummer}} \newenvironment{Claim} {\begin{nummer} {\bf Claim.}} {\end{nummer}} \newenvironment{Problem} {\begin{nummer} {\bf Problem.}} {\end{nummer}} \newenvironment{Example} {\begin{nummer} {\bf Example.} \begin{rm}} {\end{rm} \end{nummer}} \newenvironment{MyPar}[1] {\begin{nummer} {\bf #1.} \begin{rm}} {\end{rm} \end{nummer}} \newenvironment{Proof} {\vspace{1ex}\noindent \bf Proof. \rm} {\ \nolinebreak \hfill $\Box$ \vspace{2ex}} \def\beq{\begin{equation}} \def\eeq{\end{equation}} \def\beqn{\begin{displaymath}} \def\eeqn{\end{displaymath}} \def\bqa{\begin{eqnarray}} \def\eqa{\end{eqnarray}} \def\bqan{\begin{eqnarray*}} \def\eqan{\end{eqnarray*}} \def\AA{\mathcal A} \def\BB{\mathcal B} \def\CC{\mathcal C} \def\MM{\mathcal M} \def\NN{\mathcal N} \def\SS{\mathcal S} \def\XX{\mathcal X} \def\YY{\mathcal Y} \def\NNN{\mathbb N} \def\RRR{\mathbb R} \def\QQQ{\mathbb Q} \def\CCC{\mathbb C} \def\ZZZ{\mathbb Z} \def\BBB{\mathbb B} \def\M{M} \def\m{m} \def\K{K\!} \def\Kpre{K} \def\Km{K\!m} \def\Kr{K\!r} \def\KM{{\K M}} \def\E{{\bf E}} \def\P{{\bf P}} \def\rrho{\varrho} \def\eps{\varepsilon} \def\epstr{\epsilon} \def\equa{\stackrel+=} %\eqa unfortunately already used up \def\leqa{\stackrel+\leq} % don't put around another braces, \def\geqa{\stackrel+\geq} % since this messes up spacings \def\neqa{\not\stackrel+=} \def\eqm{\stackrel\times=} \def\leqm{\stackrel\times\leq} \def\geqm{\stackrel\times\geq} \def\neqm{\not\stackrel\times=} \def\leqt{_{1:t}} \def\ltt{_{0$ such that $\nu(x)\geq c(\nu_i)\cdot\nu_i(x)$ holds for all $x\in\XX^*$. The dominant semimeasure $\tilde\nu$ need not be contained in $\CC$, but if it is, we call it a {\it universal} element of $\CC$. Let $\CC$ be a countable class of (semi)measures, where each $\nu\in\CC$ is associated with a weight $w_\nu>0$ and $\sum_{\nu} w_\nu\leq 1$. We may interpret the weights as a {\it prior} on $\CC$. Then it is obvious that the Bayes mixture \beq \label{eq:xi} \xi(x)=\xi_{[\CC]}(x)=\sum_{\nu\in\CC}w_\nu \nu(x),\ x\in\XX^*, \eeq dominates $\CC$. Assume that there is some measure $\mu\in\CC$, the {\it true distribution}, generating sequences $x\ltinf\in\XX^\infty$. Normally $\mu$ is unknown. (Note that we require $\mu$ to be a measure, while $\CC$ may contain also semimeasures in general. This is motivated by the setting of universal sequence prediction as already indicated.) If some initial part $x\ltt$ of a sequence is given, the probability of observing $x_t\in\XX$ as a next symbol is given by \beq \label{eq:basicprediction} \mu(x_t|x\ltt)=\frac{\mu(x\ltt x_t)}{\mu(x\ltt)} \wenn \mu(x\ltt)>0 \ \und\ \mu(x_t|x\ltt)=0 \wenn \mu(x\ltt)=0. \eeq The case $\mu(x\ltt)=0$ is stated only for well-definedness, it has probability zero. Note that $\mu(x_t|x\ltt)$ can depend on $x\ltt$. We may generally define the quantity (\ref{eq:basicprediction}) for {\it any} function $\ph:\XX^*\to[0,1]$, we call $\ph(x_t|x\ltt)=\frac{\ph(x\leqt)}{\ph(x\ltt)}$ the {\it $\ph$-prediction}. Clearly, this is not necessarily a probability on $\XX$ for general $\ph$. For a semimeasure $\nu$ in particular, the $\nu$-prediction $\nu(\cdot|x\ltt)$ is a semimeasure on $\XX$. We define the {\it expectation} with respect to the true probability $\mu$: Let $n\geq 0$ and $f:\XX^n\to\RRR$ be a function, then \beq \label{eq:expectation} \E\ f=\E\ f(x\leqn)=\sum_{x\leqn\in\XX^n}\mu(x\leqn)f(x\leqn). \eeq Generally, we may also define the expectation as an integral over infinite sequences. But since we won't need it, we can keep things simple. We can now state a central result about prediction with Bayes mixtures in a form independent of Algorithmic Information Theory. \begin{Theorem} \label{Theorem:Solomonoff} For any class of (semi)measures $\CC$ containing the true distribution $\mu$ and any $n\geq 1$, we have \beq \label{eq:Solomonoff} \sum_{t=1}^n \E \sum_{a\in\XX} \Big( \mu(a|x\ltt)-\xi(a|x\ltt) \Big)^2 \ \leq \ \ln w_\mu^{-1}. \eeq \end{Theorem} This was found by Solomonoff (\cite{Solomonoff:78}) for universal sequence prediction. A proof is also given in \cite{Li:97} (only for binary alphabet) or \cite{Hutter:01alpha} (arbitrary alphabet). It is surprisingly simple once Lemma \ref{Lemma:EntropyIneq} is known. A few lines analogous to (\ref{Eq:TheoremRhoConvergesIMS0}) and (\ref{Eq:TheoremRhoConvergesIMS00}) exploiting the dominance of $\xi$ are sufficient. The bound (\ref{eq:Solomonoff}) asserts convergence of the $\xi$-predictions to the $\mu$-predictions {\it in mean sum (i.m.s.)}, since we define \beq \label{eq:IMS} \ph\toims\mu\quad\Longleftrightarrow\quad \exists\ C>0:\ \sum_{t=1}^\infty \E \sum_{a\in\XX} \Big( \mu(a|x\ltt)-\ph(a|x\ltt) \Big)^2 \leq C. \eeq Convergence i.m.s.\ implies convergence with $\mu$-probability one (w.$\mu$-p.1), since otherwise the sum would be infinite. Moreover, convergence i.m.s.\ provides a rate or speed of convergence in the sense that the expected number of times $t$ in which $\ph(a|x\ltt)$ deviates more than $\eps$ from $\mu(a|x\ltt)$ is finite and bounded by $C/\eps^2$ and the probability that the number of $\eps$-deviations exceeds $C\over\eps^2\delta$ is smaller than $\delta$. If the quadratic differences were monotonically decreasing (which is usually not the case), we could even conclude convergence faster than $\frac{1}{t}$. \begin{MyPar}{Probabilities vs.\ Description Lengths} \label{par:prob} \begin{sloppy} By the Kraft inequality, each (semi)measure can be associated with a code length or {\it complexity} by means of the negative logarithm, where all (binary) codewords form a prefix-free set. The converse holds as well. E.g. for the weights $w_\nu$ with $\sum w_\nu\leq 1$, codes of lengths $\lceil-\lb w_\nu\rceil$ can be found. It is often only a matter of notational convenience if description lengths or probabilities are used, but description lengths are generally preferred in Algorithmic Information Theory. Keeping the equivalence in mind, we will develop the general theory in terms of probabilities, but formulate parts of the results in universal sequence prediction rather in terms of complexities. \end{sloppy} \end{MyPar} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{MDL Estimator and Predictions}\label{secMDL} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Assume that $\CC$ is a countable class of semimeasures together with weights $(w_\nu)_{\nu\in\CC}$, and $x\in\XX^*$ is some string. Then the {\it maximizing element} $\nu^x$, often called MAP estimator, is defined as \beqn \nu^x = \nu^x_{[\CC]}=\arg\max_{\nu\in\CC}\{w_\nu\nu(x)\}. \eeqn In fact the maximum is attained since for each $\eps\in(0,1)$ only a finite number of elements fulfil $w_\nu\nu(x)>\eps$. Observe immediately the correspondence in terms of {\it description lengths} rather than {\it probabilities}: $\nu^x = \arg\min_{\nu\in\CC}\big\{-\lb w(\nu)-\lb \nu(x)\big\}$. Then the {\it minimum description length principle} is obvious: $\nu^x$ minimizes the joint description length of the model plus the data given the model% \footnote{Precisely, we define a MAP (maximum a posteriori) estimator. For two reasons, information theorists and statisticians would not consider our definition as MDL in the strong sense. First, MDL is often associated with a specific prior. Second, when coding some data $x$, one can exploit the fact that once the model $\nu^x$ is specified, only data which leads to the maximizing element $\nu^x$ needs to be considered. This allows for a description shorter than $\lb \nu^x(x)$. Since however most authors refer to MDL, we will keep using this general term instead of MAP, too.} (see the last paragraph of the previous section). As explained before, we stick to the product notation. For notational simplicity we set $\nu^*(x)=\nu^x(x)$. The {\it two-part MDL estimator} is defined by \beqn \rrho(x) = \rrho_{[\CC]}(x) = w_{\nu^x}\nu^x(x) = \max_{\nu\in\CC}\{w_\nu \nu(x)\}. \eeqn So $\rrho$ chooses the maximizing element with respect to its argument. We may also use the version $\rrho^y(x) := w_{\nu^y}\nu^y(x)$ for which the choice depends on the superscript instead of the argument. For each $x,y\in\XX^*$, $\xi(x)\geq\rrho(x)\geq\rrho^y(x)$ is immediate. We can define MDL predictors according to (\ref{eq:basicprediction}). There are {\it at least three} possible ways to use MDL for prediction. \begin{Def} \label{Def:DynamicMDL} The {\em dynamic} MDL predictor is defined as \beqn \rrho(a|x) = \frac{\rrho(xa)}{\rrho(x)} = \frac{\rrho^{xa}(xa)}{\rrho^x(x)}. \eeqn That is, we look for a short description of $xa$ and relate it to a short description of $x=x\ltt$. We call this dynamic since for each possible $a$ we have to find a new MDL estimator. This is the closest correspondence to the $\xi$-predictor. \end{Def} \begin{Def} \label{Def:StaticMDL} The {\em static} MDL predictor is given by \beqn \rrho^{\mathrm{\mathrm{static}}}(a|x) = \rrho^x(a|x) = \frac{\rrho^x(xa)}{\rrho(x)} = \frac{\rrho^x(xa)}{\rrho^x(x)} = \frac{\nu^x(xa)}{\nu^x(x)}. \eeqn Here obviously only {\it one} MDL estimator $\rrho^x$ has to be identified, which may be more efficient in practice. \end{Def} \begin{Def} \label{Def:HybridMDL} The {\em hybrid} MDL predictor is given by $ \rrho^{\mathrm{hyb}}(a|x) = \frac{\nu^*(xa)}{\nu^*(x)} $. This can be paraphrased as ``do dynamic MDL and drop the weights". It is somewhat in-between static and dynamic MDL. \end{Def} The range of the static MDL predictor is obviously contained in $[0,1]$. For the dynamic MDL predictor, this holds by $\rrho^x(x)\geq\rrho^{xa}(x)\geq\rrho^{xa}(xa)$, while for the hybrid MDL predictor it is generally false. Static MDL is omnipresent in machine learning and applications. In fact, many common prediction algorithms can be abstractly understood as static MDL, or rather as approximations. Namely, if a prediction task is accomplished by building a {\it model} such as a neural network with a suitable regularization to prevent ``overfitting", this is just searching an MDL estimator within a certain class of distributions. After that, only this model is used for prediction. Dynamic and hybrid MDL are applied more rarely due to their larger computational effort. For example, the similarity metric proposed in \cite{Li:03} can be interpreted as (a deterministic variant of) dynamic MDL. For hybrid MDL, we will see that the prediction properties are worse than for dynamic and static MDL. We will need to convert our MDL predictors to {\it measures} on $\XX$ by means of {\it normalization}. If $\ph:\XX^*\to[0,1]$ is any function, then \beqn \ph\_norm(a|x\ltt) \ = \ \frac{\ph(a|x\ltt)}{\sum_{a'\in\XX}\ph(a'|x\ltt)} \ = \ \frac{\ph(x\ltt a)}{\sum_{a'\in\XX}\ph(x\ltt a')} \eeqn (assume that the denominator is different from zero, which is always true with probability 1 if $\ph$ is an MDL predictor). This procedure is known as {\it Solomonoff normalization} (\cite{Solomonoff:78,Li:97}) and results in $\nu\_norm(x\leqn) = \nu(x\leqn)/\big[\nu(\epstr)N_\nu(x_{0$, $\nu(111\ldots)=\prod_1^\infty\nu_i(1)>0$, and $\frac{\nu(111\ldots)}{\mu(111\ldots)}$ is convergent but oscillates around its limit. Therefore, we can set $w_\mu$ and $w_\nu$ appropriately to prevent the maximizing element from stabilizing on $x\ltinf=111\ldots$ (Moreover, each sequence having positive measure under $\mu$ and $\nu$ contains eventually only ones, and the quotient oscillates.) \end{Example} The reason for the oscillation in this example is the fact that measures $\mu$ and $\nu$ are asymptotically very similar. One can also achieve a similar effect by constructing a measure which is \emph{dependent} on the past. This shows in particular that we need both parts of the following definition which states properties sufficient for a positive result. \begin{Def} \label{Def:FactorAndUniform} $(i)$ A (semi)measure $\nu$ on $\XX^\infty$ is called {\em factorizable} if there are (semi)measures $\nu_i$ on $\XX$ such that $\nu(x)=\prod_{i=1}^{\l(x)}\nu_i(x_i)$ for all $x\in\XX^*$. That is, the symbols of sequences $x\ltinf$ generated by $\nu$ are independent.\\ $(ii)$ A factorizable (semi)measure $\mu=\prod\mu_i$ is called {\em uniformly stochastic}, if there is some $\delta>0$ such that at each time $i$ the probability of all symbols $a\in\XX$ is either 0 or at least $\delta$. That is, $\mu_i(a)>0 \Rightarrow \mu_i(a)\geq \delta$ for all $a\in\XX$ and $i\geq 1$. \end{Def} In particular, all deterministic measures are uniformly stochastic. Another simple example of a uniformly stochastic measure is a probability distribution which generates alternately random bits by fair coin flips and the digits of the binary representation of $\pi$. \begin{Theorem} \label{Theorem:MDLstabilizes} Let $\CC$ be a countable class of factorizable (semi)measures and $\mu$ be uniformly stochastic. Then the maximizing element stabilizes almost surely. \end{Theorem} We omit the proof. So in particular, under the conditions of Theorem \ref{Theorem:MDLstabilizes}, the hybrid MDL predictions converge almost surely. No statement about the convergence speed can be made. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Complexities and Randomness}\label{secCR} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we concentrate on universal sequence prediction. It was mentioned already in the introduction that this is one interesting application of the theory developed so far. So $\CC=\MM$ is the countable set of all enumerable (i.e.\ lower semicomputable) semimeasures on $\XX^*$. (Algorithms are identified with semimeasures rather than measures since they need not terminate.) $\MM$ contains stochastic models in general, and in particular all models for computable deterministic sequences. One can show that this class $\MM$ is determined by {\it all} algorithms on some fixed universal monotone Turing machine $U$ \cite[Th. 4.5.2]{Li:97}. By this correspondence, each semimeasure $\nu\in\MM$ is assigned a \emph{canonical weight} $w_\nu=2^{-K(\nu)}$ (where $K(\nu)$ is the Kolmogorov complexity of $\nu$, see \cite[Eq. 4.11]{Li:97}), and $\sum w_\nu\leq 1$ holds. We will assume programs to be \emph{binary}, i.e. $p\in\BBB^*$, in contrast to outputs, which are strings $x\in\XX^*$. The MDL definitions in Section \ref{secMDL} directly transfer to this setup. All our results (Theorems \ref{Theorem:RhoConvergesIMS} - \ref{thSMDLBound}) therefore apply to $\rrho=\rrho_{[\MM]}$ if the true distribution $\mu$ is a measure, which is not very restrictive. Then $\mu$ is necessarily computable. Also, Theorem \ref{Theorem:Solomonoff} implies Solomonoff's important {\it universal induction} theorem: $\xi$ converges to the true distribution i.m.s., if the latter is computable. Note that the Bayes mixture $\xi$ is within a multiplicative constant of the {\it Solomonoff-Levin prior} $M(x)$, which is the algorithmic probability that $U$ produces an output starting with $x$ if its input is random. In addition to $\MM$, we also consider the set of all recursive measures $\tilde\MM$ together with the same canonical weights, and the mixture $\tilde \xi(x)=\sum_{\nu\in\tilde\MM}w_\nu\nu(x)$. Likewise, define $\tilde\rrho=\rrho_{[\tilde\MM]}$. Then we obviously have $\tilde\rrho(x)\leq\tilde \xi(x)\leq\xi(x)$ and $\rrho(x)\leq\xi(x)$ for all $x\in\XX^*$. It is even immediate that $\xi(x)\leqm\rrho(x)$ since $\xi\in\MM$. Here, by $f\leqm g$ we mean $f\leq g\cdot O(1)$, ``$\geqm$" and ``$\eqm$" are defined analogously. Moreover, for any string $x\in\XX^*$, there is also a {\it universal one-part MDL estimator} $m(x)=2^{-\Km(x)}$ derived from the monotone complexity $\Km(x)=\min\{\l(p):U(p)=x*\}$. (I.e. the monotone complexity is the length of the shortest program such that $U$'s output starts with $x$.) The minimal program $p$ defines a measure $\nu$ with $\nu(x)=1$ and $w_\nu\geq 2^{-\l(p)}\cdot O(1)$ (recall that programs are binary). Therefore, $m(x)\leqm\tilde\rrho(x)$ for all $x\in\XX^*$. Together with the following proposition, we thus obtain \beq \label{Eq:ComplexityRelations} m(x)\ \eqm\ \tilde\rrho(x)\ \leqm \ \tilde\xi(x) \ \leqm\ \rrho(x)\ \eqm\ \xi(x) \for_all x\in\XX^*. \eeq \begin{Prop} We have $\tilde \rrho(x) \leqm m(x)$ for all $x\in\XX^*$. \end{Prop} \begin{Proof} (Sketch only.) It is not hard to show that given a string $x\in\XX^*$ and a recursive measure $\nu$ (which in particular may be the MDL descriptor $\nu^*(x)$) it is possible to specify a program $p$ of length at most $-\lb w_\nu-\lb\nu(x)+c$ that outputs a string starting with $x$, where constant $c$ is independent of $x$ and $\nu$. This is done via arithmetic encoding. Alternatively, it is also possible to prove the proposition indirectly using \cite[Th.4.5.4]{Li:97}. This implies that $m(x)\geqm w_\nu\nu(x)$ for all $x\in\XX^*$ and all recursive measures $\nu$. Then, also $m(x)\geqm \max\{w_\nu\nu(x)\}$ holds. \end{Proof} On the other hand, we know from \cite{Gacs:83} that $m\neqm\xi$. Therefore, at least one of the two inequalities in (\ref{Eq:ComplexityRelations}) must be proper. \begin{Problem} Which of the inequalities $\tilde \rrho\leqm\tilde \xi$ and $\tilde \xi\leqm\rrho$ is proper (or are both)? \end{Problem} Equation (\ref{Eq:ComplexityRelations}) also has an easy consequence in terms of randomness criteria. \begin{Prop} A sequence $x\ltinf\in\XX^\infty$ is Martin-L{\"o}f random with respect to some computable measure $\mu$ iff for any $f\in\{\m,\tilde \rrho,\tilde\xi,r,\M\}$ there is a constant $C>0$ such that $f(x\leqn)\leq C\mu(x\leqn)$ for all $n\in\NNN$ holds. \end{Prop} \begin{Proof} It is a standard result that if $x\ltinf$ is random then $\M(x\leqn)\leq C\mu(x\leqn)$ for some $C$ \cite[Th.3]{Levin:73random}. Then by (\ref{Eq:ComplexityRelations}), $f(x\leqn)\leqm\mu(x\leqn)$ for all $f$. Conversely, if $f(x\leqn)\leqm\mu(x\leqn)$ for some $f$, then there is $C$ such that $\m(x\leqn)\leq C\mu(x\leqn)$. This implies $\mu$-randomness of $x\ltinf$ (\cite[Th.2]{Levin:73random} or \cite[p295]{Li:97}). \end{Proof} Interestingly, these randomness criteria partly depend on the weights. The criteria for $\tilde\xi$ and $\tilde\rrho$ are not equivalent any more if weights other than the canonical weights are used, as the following example will show. In contrast, for $\xi$ and $\rrho$ there is no weight dependency as long as the weights are strictly greater than zero, since $\xi\in\MM$. \begin{Example} There are other randomness criteria than Martin-L{\"o}f randomness, e.g.\ rec-randomness. A rec-random sequence $x\ltinf$ (with respect to the uniform distribution) satisfies $\nu(x\leqn)\leq c(\nu) 2^{-n}$ for each computable measure $\nu$ and for all $n$. It is obvious that Martin-L{\"o}f random sequences are also rec-random. The converse does not hold, there are sequences $x\ltinf$ that are rec-random but not Martin-L{\"o}f random, as shown e.g.\ in \cite{Schnorr:71,Wang:96}. Let $x\ltinf$ be such a sequence, i.e.\ $\nu(x\leqn)\leq c(\nu) 2^{-n}$ for all computable measures $\nu$ and for all $n$, but where $x\ltinf$ is not Martin-L{\"o}f random. Let $\nu_1,\nu_2,\ldots$ be a (non-effective) enumeration of all computable measures. Define $w'_i=2^{-i}c(\nu_i)^{-1}$. Then \beqn \tilde\M'(x\leqn)= \sum_{i=1}^\infty w'_i\nu_i(x\leqn)\leq\sum_{i=1}^\infty 2^{-i}c(\nu_i)^{-1}c(\nu_i)2^{-n}=2^{-n}\for_all n, \eeqn i.e.\ $x\ltinf$ is $\tilde\M'$-random. Thus, $x\ltinf$ is also $\tilde r'$-random with $\tilde r'=\max_i\{w'_i\nu_i\}$. \end{Example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Conclusions}\label{secDC} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We have proven convergence theorems for MDL prediction for arbitrary countable classes of semimeasures, the only requirement being that the true distribution $\mu$ is a measure. Our results hold for both static and dynamic MDL and provide a statement about convergence speed in mean sum. This also yields both on-sequence and off-sequence assertions. Our results are to our knowledge the strongest available for the discrete case. Compared to the bound for Solomonoff prediction in Theorem \ref{Theorem:Solomonoff}, the error bounds for MDL are exponentially worse, namely $w_\mu^{-1}$ instead of $\ln w_\mu^{-1}$. Our bounds are sharp in general, as Example \ref{Ex:LowerBound} shows. There are even classes of Bernoulli distributions where the exponential bound is sharp \cite{Poland:04mdlspeed}. In the case of continuously parameterized model classes, finite error bounds do not hold \cite{Barron:91,Barron:98}, but the error grows slowly as $\ln t$. Under additional assumptions (i.i.d. for instance) and with a reasonable prior, one can prove similar behavior of MDL and Bayes mixture predictions \cite{Rissanen:96}. In this sense, MDL converges as fast as Bayes mixture, and this is even true for the ``slow" Bernoulli example presented in \cite{Poland:04mdlspeed}. However in Example \ref{Ex:LowerBound}, the error grows as $t$, which shows that the Bayes mixture may be superior to MDL in general. \begin{small} \newcommand{\etalchar}[1]{$^{#1}$} \begin{thebibliography}{LCL{\etalchar{+}}03} \bibitem[BC91]{Barron:91} A.~R. Barron and T.~M. Cover. \newblock Minimum complexity density estimation. \newblock {\em IEEE Transactions on Information Theory}, 37(4):1034--1054, 1991. \bibitem[BRY98]{Barron:98} A.~R. Barron, J.~J. Rissanen, and B.~Yu. \newblock The minimum description length principle in coding and modeling. \newblock {\em IEEE Transactions on Information Theory}, 44(6):2743--2760, 1998. \bibitem[Cal02]{Calude:02} C.~S. Calude. \newblock {\em Information and Randomness}. \newblock Springer, Berlin, 2nd edition, 2002. \bibitem[G{\'a}c83]{Gacs:83} P.~G{\'a}cs. \newblock On the relation between descriptional complexity and algorithmic probability. \newblock {\em Theoretical Computer Science}, 22:71--93, 1983. \bibitem[Gr{\"u}98]{Gruenwald:98} P.~D. Gr{\"u}nwald. \newblock {\em The Minimum Discription Length Principle and Reasoning under Uncertainty}. \newblock PhD thesis, Universiteit van Amsterdam, 1998. \bibitem[Hut01a]{Hutter:01alpha} M.~Hutter. \newblock Convergence and error bounds of universal prediction for general alphabet. \newblock {\em Proceedings of the 12th Eurpean Conference on Machine Learning (ECML-2001)}, pages 239--250, December 2001. \bibitem[Hut01b]{Hutter:99errbnd} M.~Hutter. \newblock New error bounds for {Solomonoff} prediction. \newblock {\em Journal of Computer and System Sciences}, 62(4):653--667, June 2001. \bibitem[Hut03a]{Hutter:03optisp} M.~Hutter. \newblock Optimality of universal {B}ayesian prediction for general loss and alphabet. \newblock {\em Journal of Machine Learning Research}, 4:971--1000, 2003. \bibitem[Hut03b]{Hutter:03unimdl} M.~Hutter. \newblock Sequence prediction based on monotone complexity. \newblock In {\em Proceedings of the 16th Annual Conference on Learning Theory ({COLT-2003})}, Lecture Notes in Artificial Intelligence, pages 506--521, Berlin, 2003. Springer. \bibitem[LCL{\etalchar{+}}03]{Li:03} M.~Li, X.~Chen, X.~Li, B.~Ma, and P.~M.~B. Vit\'anyi. \newblock The similarity metric. \newblock In {\em Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA)}, 2003. \bibitem[Lev73]{Levin:73random} L.~A. Levin. \newblock On the notion of a random sequence. \newblock {\em Soviet Math. Dokl.}, 14(5):1413--1416, 1973. \bibitem[LV97]{Li:97} M.~Li and P.~M.~B. Vit\'anyi. \newblock {\em An introduction to {Kolmogorov} complexity and its applications}. \newblock Springer, 2nd edition, 1997. \bibitem[PH04]{Poland:04mdlspeed} J.~Poland and M.~Hutter. \newblock On the convergence speed of {MDL} predictions for {B}ernoulli sequences. \newblock submitted to International Conference on Algorithmic Learning Theory (ALT), 2004. \bibitem[Ris78]{Rissanen:78} J.~J. Rissanen. \newblock Modeling by shortest data description. \newblock {\em Automatica}, 14:465--471, 1978. \bibitem[Ris96]{Rissanen:96} J.~J. Rissanen. \newblock Fisher {I}nformation and {S}tochastic {C}omplexity. \newblock {\em IEEE Trans on Information Theory}, 42(1):40--47, January 1996. \bibitem[Ris99]{Rissanen:99} J.~J. Rissanen. \newblock Hypothesis selection and testing by the {MDL} principle. \newblock {\em The Computer Journal}, 42(4):260--269, 1999. \bibitem[Sch71]{Schnorr:71} C.~P. Schnorr. \newblock {\em Zuf{\"a}lligkeit und Wahrscheinlichkeit}, volume 218 of {\em Lecture Notes in Mathematics}. \newblock Springer, Chichester, England, 1971. \bibitem[Sol64]{Solomonoff:64} R.~J. Solomonoff. \newblock A formal theory of inductive inference: Part 1 and 2. \newblock {\em Inform. Control}, 7:1--22, 224--254, 1964. \bibitem[Sol78]{Solomonoff:78} R.~J. Solomonoff. \newblock Complexity-based induction systems: comparisons and convergence theorems. \newblock {\em IEEE Trans. Inform. Theory}, IT-24:422--432, 1978. \bibitem[Wan96]{Wang:96} Y.~Wang. \newblock {\em Randomness and Complexity}. \newblock PhD thesis, Ruprecht-Karls-Universit{\"a}t Heidelberg, 1996. \bibitem[WB68]{Wallace:68} C.~S. Wallace and D.~M. Boulton. \newblock An information measure for classification. \newblock {\em Computer Jrnl.}, 11(2):185--194, August 1968. \bibitem[ZL70]{Zvonkin:70} A.~K. Zvonkin and L.~A. Levin. \newblock The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. \newblock {\em Russian Mathematical Surveys}, 25(6):83--124, 1970. \end{thebibliography} \end{small} \end{document}