Most sequences are predictable

V.V. V’yugin

Institute for Information Transmission Problems,

Russian Academy of Sciences,

Bol’shoi Karetnyi per. 19, Moscow GSP-4, 101447, Russia

and

Computer Learning Research Centre Royal Holloway, University of London Egham, Surrey TW20 0EX, England

Technical Report

CLRC-TR-99-01

December 1999

����� ����� �����

Department of Computer Science Egham, Surrey TW20 0EX, England

Abstract

Recent work in the theory of prediction with expert advice has shown that there exists an intrinsic measure of the difficulty of prediction of data sequences; this measure, which is a generalization of the notion of Kolmogorov complexity, is called “predictive complexity”. The predictive complexity of a data sequence gives a limit on the predictive performance of simply described prediction algorithms. We say that a data sequence is “predictable” if there exists a simply described prediction algorithm whose performance is close to the predictive complexity. In this paper we argue that data sequences normally occurring in the real world are predictable; more formally, we prove that Levin’s a priori semimeasure of non-predictable sequences is small.

Introduction 1

1 Introduction

We present the formal results suggesting some possible explanation of the following phenomenon: for many data sets the performance of the best prediction algorithms (Support Vector Machines, neural nets, boosting in the prediction of hand-written digits) is comparable. Possible explanation is based on a new notion of predictive complexity. The predictive complexity of a data sequence gives a lower limit on the predictive performance of simply described prediction algorithms. We suppose that the state-of-the-art algorithms attain predictive complexity.

This is not true for all possible data sequences; but we can try to prove this for “normal”, in some sense, sequences.

Our problem is closely related to Kolmogorov’s theory of stochastic sequences (for the log-loss game), see Shen [4]. Similar results (for stochastic setting) were obtained earlier by V’yugin [9].

The plan of this paper is as follows. First we give formal definitions of predictive strategy, loss function, predictive complexity. After that we discuss the notion of a “normal” sequence (according to Leonid Levin’s philosophy) and define the a priori semimeasure. In Sections 4 and 5 we state our main results giving lower and upper bounds on the a priori semimeasure of non-predictable sequences.

2 Predictive complexity

Suppose we are given a sequence x_{1}, x_{2}, …, x_{i} … of some data. In this paper we consider only the simplest case, where x_{i} ∈ {0, 1}. Our goal is to predict the elements of this data set on-line: we predict x_{1}, then predict x_{2} given x_{1}, …, then predict x_{i+1} given x_{1}, x_{2}, … x_{i}, etc. At every step i the loss is measured by the some function λ(x_{i}, p_{i}), where the forecast is a real number p_{i} and the actual outcome is x_{i}. We consider only loss functions computable by algorithms. For example, we consider the squared difference λ(x_{i}, p_{i}) = (x_{i} − p_{i})^{2} and the logloss function λ(x_{i}, p_{i}) = − log p_{i} if x_{i} = 1 and λ(x_{i}, p_{i}) = − log(1 − p_{i}) if x_{i} = 0. Here log means logarithm to the base 2. Other loss functions are considered in Vovk [6], Haussler, Kivinen, Warmuth [1] (log-loss, Hellinger, etc.), Vovk and Watkins [8] (financial theory), Yamanishi [13] (logistic, etc).

It is natural to suppose that all predictions are given according to a prediction strategy (or prediction algorithm) p_{i} = S(x_{1}x_{2} … x_{i−1}). The total loss incurred by Predictor who follows the strategy S over the first n trials x_{1}, x_{2}, …, x_{n} is defined

Loss_{S}(x_{1}x_{2} … x_{n}) = ∑_{i=1}^{n} λ(x_{i}S(x_{1}x_{2} … x_{i−1})).

The main task is to minimize the total loss suffered on a sequence x = x_{1}x_{2} … x_{n} of outcomes. The corresponding game-theoretic interpretation is given in Vovk [7] or in Vovk and Watkins [8].

Predictive complexity 2

Let us fix η > 0 (the learning rate) and put β = e^{−η} ∈ (0, 1). A generalized prediction is defined to be any function on finite binary sequences taking real values. Three important classes of generalized predictions g are given by the following definitions from Vovk [6]:

⋄ g is a permitted prediction if there exists a prediction p such that, for all y, g(y) = λ(y, p) (i.e., g describes the potential losses implied by p);

⋄ g is a superprediction if there exists a prediction p such that, for all y, g(y) ≥ λ(y, p) (i.e., g is a permitted prediction, perhaps plus some extra losses);

⋄ g is an η-mixture of predictions if there exist a sequence (p_{1}, p_{2}, … of predictions and a sequence (r_{1}, r_{2}, …) of nonnegative weights summing to 1 such that, for all y,

g(y) = log_{β} ∑_{i=1}^{∞} β^{λ(y,p_{i})}r_{i}.

The loss function (game) is perfectly η-mixable if every η-mixture of predictions is a superprediction. From this follows, that every η-mixture of superpredictions is also a superprediction. The loss function (game) is perfectly mixable if it is η-mixable for some η > 0. It is known that many popular loss functions such as the log-loss function, square-loss function, Cover’s loss function, long-short loss function, Kullback–Leibler loss function, χ^{2} loss function, Hellinger loss function etc. (see, e.g., [5], [1], [6] [8] are perfectly mixable.

The important construction in this field is the Vovk’s aggregating algorithm AA [5], [6]. In the case of perfectly mixable loss functions this algorithm given a finite sequence of predictive strategies S_{1}, S_{2}, … S_{k} and weights r_{1}, r_{2} … r_{k}, summing to 1, allows us to define theirs “mixture” - a prediction strategy S such that

Loss_{S}(x) ≤ log_{β} ∑_{i=1}^{k} r_{i}β^{Loss_{S_{i}}(x)}  (1)

for all x, where β = e^{−η} and the corresponding loss function is η-mixable. The exact construction is given in Section A.

Later Vovk extended the idea of AA to arbitrary infinite sequence of loss processes. In the framework of Kolmogorov complexity for a wide class of computable loss functions he defined a minimal possible total loss of prediction. Now we briefly review the concept of predictive complexity from Vovk and Gammerman [7] and Vovk and Watkins [8] in binary case.

Without loss of generality we consider the loss processes corresponding to computable prediction strategies S. In this case, the value Loss_{S}(x) can be interpreted as predictive complexity of x. This value, however, depends on S and it is unclear which S to choose. In the most interesting cases a smallest loss functions does not exist - given a computable prediction strategy S, it is easy to construct a computable prediction strategy that greatly outperforms S on at least one outcome sequence. Levin [12], developing ideas of Kolmogorov and Solomonoff, suggested (for a particular loss function) a very natural solution to the problem of nonexistence of a smallest computable loss process. Vovk [7] extended these ideas in a more general setting - for arbitrary loss-prosesses.

We will say that a function K(x) is a measure of predictive complexity if the following two conditions hold:

⋄ (i) K is a superloss process, which means that K(□) = 0 (where □ is the empty sequence) and for any x there exists an p such that

K(xj) ≥ K(x) + λ(j, p)  (2)

for each j = 0, 1.

⋄ (ii) K is semicomputable from above, which means that there exists a computable sequence of computable functions K^{t} such that, for every x, K(x) = inf_{t} K^{t}(x).

Requirement (i) means that the measure of predictive complexity must be valid: there must exists a prediction strategy that achieves it. (Notice that if ≥ is replaced by = in (2), the definition of a loss process will be obtained.) Requirement (ii) means that it must be “computable in the limit”; since we are interested in a universal measure of predictive complexity K, we cannot hope that we will be able to compute it in finite time; all we can do is to output more and more accurate approximations K_{i} to it so that in the limit we obtain K. (In (ii) we can assume, without loss of generality, that the sequence K_{n} is decreasing.)

A smallest, to within an additive constant, measure K of predictive complexity will be said to be universal. In other words, a measure K of predictive complexity is universal if, for any other measure K′ of predictive complexity,

K(x) ≤ K′(x) + c,

for some constant c (depending on K′). In Vovk and Gammerman [7] and Vovk and Watkins [8] it was shown that for any perfectly mixable loss function (game) a universal measure of predictive complexity KG(x) can be defined

KG(x) = log_{β} ∑_{i=1}^{∞} β^{K_{i}(x)}r_{i},  (3)

where K_{i}(x) is semicomputable from above sequence of all measures of predictive complexity, r_{i} be a semicomputable from below sequence of real numbers such that the the series ∑_{i=1}^{∞} r_{i} is convergent and its sum does not exceed 1. For

instance, we can take r_{i} = 2^{−K(i)}, where K(i) is the prefix Kolmogorov complexity of a program i (see e.g. Li and Vitanyi [3], Section 3). The conditions (i) and (ii) for KG(x) will be verifyed in Section A.

A priori semimeasure 4

KG(x) will be called the predictive complexity of x in G.

By (3) for any computable prediction strategy S it holds

KG(x) ≤ Loss_{S}(x) + c_{η}K(S) + c,  (4)

where c_{η} = (η log e)^{−1}, c is a positive constant and K(S) is the Kolmogorov prefix complexity of the program computing S.

3 A priori semimeasure

The concept of predictive complexity is based on thoughtful ideas of Solomonoff and Kolmogorov on the existence of the universal objects in some classes of constructive objects. Solomonoff proposed the philosophical ideas on defining of the a priori probability distribution on the basis of the general theory of algorithms. The main problem was that the maximal computable probability distribution does not exist.

Levin [12] gives a precise form of Solomonoff ideas in a concept of a maximal semimeasure semicomputable from below (see also [3], Section 4.5). A realvalued function P (x), where x is a finite binary sequence, is called semimeasure if

⋄ P (□) ≤ 1;

⋄ P (x) ≥ P (x0) + P (x1) for all x;

⋄ the function P is semicomputable from below (see (ii) of the analogous definition of predictive complexity).

Levin proved that there exists a maximal to within a multiplicative constant factor semimeasure M semicomputable from below, i.e. for any semimeasure P semicomputable from below a constant c exists such that the inequality

cM(x) ≥ P (x)  (5)

holds for all x.

It is easy to see that the function KL(x) = − log M(x) is a variant of the predictive complexity for log-loss function (Levin game). ¿From (4) it follows that log-loss complexity is the maximal (to within a constant factor) among predictive complexities from a very natural class.

Proposition 1 For any η-mixable loss function λ(ω, p) (game G) satisfying λ(0, 0) = λ(1, 1) = 0 and any δ > 0 a constant c exists such that the following hold

⋄ (i) KG(x) ≤ c_{η}K(x) + c;

⋄ (ii) KG(x) ≤ (1 + δ)c_{η}KL(x) + c,

where c_{η} = (η log e)^{−1}.

Proof. To prove the item (i) consider the prediction strategy S which on any sequence of the length i − 1 outputs the i-th element x_{i} of the sequence x = x_{1} … x_{n} using the code of x under an optimal mode of description of finite objects. The length of this code is equal to the prefix complexity K(x) [3], Section 3. By definition Loss_{S}(x) = 0. The item (ii) follows from the inequalities between K(x) and KL(x) [3], Section 4. □

At the rest of this section we consider some notions needed to give an interpretation of Theorem 2 below. Levin [2] considered the combinations of probabilistic and deterministic processes as the most general class of processes of generating data. With each probabilistic process some computable probability distribution can be assigned. Each deterministic process is realized by means of an algorithm. Algorithmic processes transformed sequences generating by probabilistic processes into new sequences. More precise, a probabilistic computer F is a Turing machine supplied with an additional input tape. In the process of computation this machine reads a sequence ω on this tape and produces a sequence ω′ = F (ω). We suppose that there is a computable probability distribution μ in the set of all possible ω. So we can calculate the probability

P (x) = μ{ω|x ⊆ F (ω)}

of that the result F (ω) of the computation begins with a finite sequence x. More precise, P (x) is not a probability distribution, since F (ω) may be finite for an infinite ω. It is easy to see that P (x) is a semimeasure semicomputable from below. The converse result is proved in [12]: for any semimeasure P (x) semicomputable from below a probabilistic computer F (ω) exists such that

P (x) = μ{ω|x ⊆ F (ω)},

for all x, where μ(x) = 2^{−l(x)} is the uniform probability distribution in the set of all binary sequences.

Therefore, by (5) M(x) is an universal upper bound of the probability of generating sequences x by probabilistic computers.

Let A be any set of the binary sequences of the length n. We define

M(A) = ∑_{x∈A} M(x).

Let some property Π_{n} defines for any n a set A_{n} of binary sequences of the length n. Then for any probability distribution μ and algorithmic process F there exists a constant c (depending only on μ and F) such that

μ{ω|F (ω) ∈ A_{n}} ≤ cM(A_{n})

for all n. According to our framework, if M(A_{n}) ⟶ 0 as n tends to infinity, then for all sufficiently large n the sequences of the length n having property Π_{n} form a scarce part of all objects generating in combinations of deterministic and probabilistic processes.

Predictable and non-predictable sequences 6

4 Predictable and non-predictable sequences

Let α and γ be some nonnegative numbers. A sequence x of the length n is called (α, γ)-predictable if there exists a prediction strategy S such that K(S) ≤ α and

Loss_{S}(x) − KG(x) ≤ γ.

The interesting case when resource bound α is small with respect to the length n of the sequence x (for instance α = O(log n)).

The following Theorem 1 shows that for a wide class of loss functions nonpredictible sequences exist. Consider some conditions for a loss function sufficient to following theorem holds:

⋄ (i) λ(0, 0) = λ(1, 1) = 0;

⋄ (ii) there exists a computable positive number b such that λ(0, p) ≥ b or λ(1, p) ≥ b for each p;

⋄ (iii) the loss function λ(ω, p) is perfectly mixable.

The log-loss function and the squared difference satisfy these condition with b = 1, and b = \frac{1}{4}, accordingly.

Theorem 1 For any loss function satisfying the conditions (i)-(iii) above a positive constant c exists such that for any n there exists a binary sequence x of the length n satisfying

⋄ Loss_{P} (x)−KG(x) ≥ bn−2c_{η}α−c_{η}(log n+2 log log n)−c for each prediction strategy P such that K(P) ≤ α, where c_{η} = (η log e)^{−1};

⋄ M(x) ≥ 2^{−α−log n−2 log log n−c}.

5 Most sequences are predictable

The predictive complexity determines asymptotically the minimal possible loss of forecasting. It includes also arbitrarily complex prediction strategies. Here we impose the restriction K(S) ≤ α, where α reflecting a degree of computational resources allowed. We show that even in the case when α is small with respect to the length n of binary sequences (for instance α = O(log n)) it can help us to reach almost the minimal possible loss incurred over the most elements of the data set.

In this section we estimate how large can be the set of non-predictable sequences of the length n. We prove that the a priori semimeasure of this set is asymptotically decreases as n increases.

Most sequences are predictable 7

Let D_{α,γ}^{n} be the set of all binary sequences of the length n which are not (α, γ)- predictable. For any x ∈ D_{α,γ}^{n} we have

Loss_{S}(x) − KG(x) > γ

for each prediction strategy S such that K(S) ≤ α.

Theorem 2 ⋄ For any perfectly mixable loss function satisfying condition (i) from Section 4 a constant c exists such that, for any n, α and 1 ≤ γ ≤ n the estimate

M(D_{α,γ}^{n}) = ∑_{x∈D_{α,γ}^{n}} M(x) ≤ 2^{−α+2 log n+2 log log n−log γ+c}  (6)

holds;

⋄ If the predictive complexity is based on the log-loss function the corresponding estimate is the following

M(D_{α,γ}^{n}) = ∑_{x∈D_{α,γ}^{n}} M(x) ≤ 2^{−α+log n+2 log log n+c},  (7)

This theorem is a generalization of Theorem 3 [9] for wide class of loss functions.

Inequality (6) or (7) can be interpreted as an upper bound on the probability of generating non-predictible sequences by a probabilistic computer.

For any m by Theorem 2 the probability of generating (α, γ)-predictable sequences is ≥ 1 − 2^{−m} when α + log γ > 2 log n + log log n + c + m. The last condition wittingly holds for any 1 ≤ γ ≤ n if

α ≥ 2 log n + log log n + c + m.  (8)

Theorem 2 shows that given an upper bound α satisfying (8) on the complexity of prediction strategies most sequences x are predictable with respect to the simple prediction strategy Q with K(Q) ≤ α, i.e. Loss_{Q}(x) is close to its minimal value KG(x).

By Theorem 1 non-learnable objects can also exist, but by Theorem 2 and Levin’s philosophy we shall meet them very rarely; non-predictable fluctuations of prices on financial markets formed a scarce part in the stream of all financial data.

Now we formulate the main corollary from Theorems 1 and 2.

Corollary 1 For any loss function satisfying conditions (i)-(iii) of Section 4 a positive constant c exists such that

2^{−α−log n−2 log log n−c} ≤ M(D_{α,γ}^{n}) ≤ 2^{−α+2 log n+2 log log n−log γ+c}

for each 0 ≤ γ ≤ bn − 2c_{η}α − c_{η}(log n + 2 log log n) − c.

Proofs 8

The logarithmic additive terms in the exponent of (7) can be eliminated (and log n + 2 log log n can be subtracted in the exponent of (6)) if we replace the condition K(S) ≤ n on K(S|n) ≤ n in the definition of D_{α,γ}^{n} (this follows from the proof of Theorem 2). An open problem arises - can we eliminate or minimize the remainder term log n in the right-side of the inequality (6).

6 Proofs

6.1 Proof of Theorem 1

For any α let P_{1}, P_{2}, …, P_{k} be all computable prediction strategies with complexity ≤ α. Evidently, k < 2^{α+1}. By means of AA we can define a mixture P_{α} of these strategies such that

Loss_{P_{α}}(x) ≤ log_{β} ∑_{i=1}^{k} k^{−1}β^{Loss_{P_{i}}(x)}.  (9)

By construction of AA we can compute k and all values of P_{i}(z), l(z) ≤ n, with degree of accuracy given below by means of program p with the following properties. The length of p is ≤ α and this program has the maximal terminating time among all programs computing values P_{j}(z) for all j ≤ k and all z of the length ≤ n with given corresponding degree of accuracy.

After that we can define a sequence x as follows

x_{s} = \{ \begin{matrix}1, if λ(1, P_{α}(x_{1} … x_{s−1})) > b − 2^{−(s+1)}, \\ 0, if λ(0, P_{α}(x_{1} … x_{s−1})) > b − 2^{−(s+1)}. \end{matrix}

for all 1 ≤ s ≤ n, where x_{0} = □. Since these conditions are overlapped, we choose that was first defined. As follows from the definition Loss_{P_{α}}(x) ≥ bn−1. By (9)

Loss_{P_{i}}(x) ≥ bn − c_{η}α − 1

for all i ≤ k (i.e. for all P such that K(P) ≤ α), where c_{η} = (η log e)^{−1}.

By definition K(x|n) ≤ α + c, for some positive constant c. The ordinary inequalities between conditional and unconditional prefix complexities (see [3], Section 3) implies

K(x) ≤ K(x|n) + log n + 2 log log n + c  (10)

for some positive constant c. Adding (i) of Proposition 1 we obtain

KG(x) ≤ c_{η}(α + log n + 2 log log n) + c

for some c. Hence, for all P such that K(P) ≤ α, we have

Loss_{P} (x) − KG(x) ≥ bn − 2c_{η}α − c_{η}(log n + 2 log log n) − c

for some positive constant c.

Since KL(x) ≤ K(x) + c holds for some c (see [3], Section 4.5), by (10) we have

M(x) ≥ 2^{−α−log n−2 log log n−c}.

□.

6.2 Proof of Theorem 2

Simple intuitive explanation of the idea of the proof: the α-simple prediction strategy will be an approximation to the universal “prediction semistrategy”.

Since the universal measure of predictive complexity is semicomputable from above, the function Q(x) = β^{KG(x)} is lower semicomputable. This means that there exists a non-decreasing computable sequence of functions k_{i}(x) taking rational values such that Q(x) = sup_{i} k_{i}(x).

The proof is much simpler when KG(x) = KL(x) = − log M(x) is the Levin’s predictive complexity for log-loss function. In this case β = \frac{1}{2} and Q(x) = M(x). By definition of M we have

∑_{l(x)=n} β^{KG(x)}(x) = ∑_{l(x)=n} M(x) ≤ 1.  (11)

Let p be a finite binary sequence representing the rational approximation of the real number ∑_{l(x)=n} M(x) from below with accuracy 2^{−α}. Then using p and n we

can effectively find integer numbers t and k such that the following conditions hold

⋄ (i) ∑_{l(x)=n} β^{KG^{t,k}(x)} > ∑_{l(x)=n} β^{KG(x)} − 2^{−α}, where

KG^{t,k}(x) = log_{β} ∑_{i=1}^{k} β^{K_{i}^{t}(x)}2^{−i}, and K_{i}^{t}(x) is some approximation from

above of K_{i}(x) computed in t steps.

⋄ (ii) for each x of the length ≤ n and for each i ≤ k the difference K_{i}^{t}(xj)− K_{i}^{t}(x) is a superprediction.

The mixture of superpredictions is also a superprediction. Then by (ii) the difference KG^{t,k}(xj) − KG^{t,k}(x) is a superprediction for each x of the length ≤ n, and by the definition of the superprediction and by AA there exists a prediction strategy Q such that Loss_{Q}(x) ≤ KG^{t,k}(x) for all such x. Since this construction is algorithmically effective,

K(Q|n) ≤ α + c,  (12)

where c is a constant.

Temporarily in the definition of D_{α,γ}^{n} we will consider prediction strategies S α-simple conditional with respect to n, i.e. such that K(S|n) ≤ α.

By definition for any x ∈ D_{α,γ}^{n} we have

Loss_{S}(x) − KG(x) > γ

for each prediction strategy S such that K(S|n) ≤ α.

Therefore, by (3) and (i) for any x ∈ D_{α−c,γ}^{n} we obtain

β^{γ} ∑_{x∈D_{α−c,γ}^{n}} β^{KG(x)} > ∑_{x∈D_{α−c,γ}^{n}} β^{Loss_{Q}(x)} ≥

∑_{x∈D_{α−c,γ}^{n}} β^{KG^{k,t}(x)} > ∑_{x∈D_{α−c,γ}^{n}} β^{KG(x)} − 2^{−α},

where c is such that (12) holds. From this it follows

(1 − β^{γ}) ∑_{x∈D_{α−c,γ}^{n}} β^{KG(x)} ≤ 2^{−α}.  (13)

In the case of log-loss function β = \frac{1}{2} and β^{KG(x)} = M(x), and then by (13) we have

M(D_{α−c,γ}^{n}) ≤ 2^{−α+1}

for any γ ≥ 1.

For other types of predictive complexities the sum ∑_{l(x)=n} β^{KG(x)} can exceed 1.

For instance, in the case of square-loss function this sum is of order of exponent from n. Let us consider the general case. We replace the inequality (11) on

∑_{l(x)=n} β_{n}^{KG(x)}M(x) ≤ 1,

where β_{n} = e^{− \frac{1}{n}}. Let p be a finite binary sequence representing the rational approximation of the real number ∑_{l(x)=n} β_{n}^{KG(x)}M(x) from below with accuracy

2^{−α}. After that, as above using p and n we effectively find t and k such that the conditions (i’) and (ii) hold, where the condition

⋄ (i’) ∑_{l(x)=n} β_{n}^{KG^{t,k}(x)}M^{t}(x) > ∑_{l(x)=n} β_{n}^{KG(x)}M(x) − 2^{−α}.

is used instead of condition (i) above. Here

KG^{t,k}(x) = log_{β} ∑_{i=1}^{k} β^{K_{i}^{t}(x)}2^{−i},

where β = e^{−η} and η is such that our loss function is η-mixable, K_{i}^{t}(x) is some approximation from above of K_{i}(x) and M^{t}(x) is some approximation from below of M(x) computed in t steps.

There exists a prediction strategy Q such that Loss_{Q}(x) ≤ KG^{t,k}(x) for all x of the length ≤ n and K(Q|n) ≤ α + c, where c is a constant. ¿From this and (i’) we obtain

∑_{l(x)=n} β_{n}^{Loss_{Q}(x)}M(x) ≥ ∑_{l(x)=n} β_{n}^{KG(x)}M(x) − 2^{−α}.  (14)

By definition for any x ∈ D_{α−c,γ}^{n} we have

Loss_{Q}(x) − KG(x) > γ.

Therefore, by (14) we obtain

β_{n}^{γ} ∑_{x∈D_{α−c,γ}^{n}} β_{n}^{KG(x)}M(x) > ∑_{x∈D_{α−c,γ}^{n}} β_{n}^{Loss_{Q}(x)}M(x) ≥

∑_{x∈D_{α−c,γ}^{n}} β_{n}^{KG(x)}M(x) − 2^{−α}.

¿From this it follows

(1 − β_{n}^{γ}) ∑_{x∈D_{α−c,γ}^{n}} β_{n}^{KG(x)}M(x) ≤ 2^{−α}.  (15)

By condition (ii) of Proposition 1 for any δ > 0 a constant c > 0 exists such that KG(x) ≤ (1 + δ)c_{η}KL(x) + c. We have also KL(x) ≤ n + c for some c > 0 ([3], Section 4.5). Hence KG(x) ≤ cn for some c > 0, where n is the length of x.

Since β_{n} = e^{− \frac{1}{n}} we have

β_{n}^{KG(x)} = e^{− \frac{1}{n} KG(x)} ≥ e^{−c},

and

1 − β_{n}^{γ} ≥ \frac{γ}{2n}

for 0 < γ ≤ n. ¿From this and (15) we obtain the estimate

∑_{x∈D_{α−c,γ}^{n}} M(x) ≤ 2^{−α} \frac{2n}{γ}e^{c} = 2^{−α+log n−log γ+c log e+1}.  (16)

To eliminate the condition n in K(Q|n) we consider the following estimate of prefix Kolmogorov complexity [3], Section 3.

K(Q) ≤ K(Q|n) + K(n) + c′ ≤ α + log n + 2 log log n + c

for some positive constants c′ and c. Replacing α in (16) on α − log n − 2 log log n − c and returning to the previous (unconditional) definition of D_{α,γ}^{n} we obtain the needed estimate

∑_{x∈D_{α,γ}^{n}} M(x) ≤ 2^{−α+2 log n+2 log log n−log γ+c}  (17)

for some positive constant c. □

Appendix 12

Acknowledgements

The motivation of this paper is due to Volodya Vovk and Alex Gammerman. Author is deeply grateful to them for valuable discussions.

A Appendix

A.1 Aggregating algorithm

In this section we present the Vovk’s aggregating algorithm AA. Let a loss function λ(ω, p) be η-mixable and β = e^{−η}. Let also a finite sequence P_{1}, P_{2}, …, P_{k} of computable prediction strategies and a sequence r(1), …, r(k) of nonnegative real numbers summing to 1 are given.

A computable prediction strategy P will be defined such that for any binary sequence y_{1} … y_{n} the inequality

Loss_{P} (y_{1} … y_{m}) ≤ log_{β} ∑_{i=1}^{k} r(i)β^{Loss_{P_{i}}(y_{1}...y_{m})}  (18)

holds.

Put initial weghts r_{0}(i) = r(i), i = 1, …, k. After each trial y_{j}, j = 1, …, n, the weights are updated as follows

r_{j}(i) = β^{λ(y_{j},P_{i}(y_{1}...y_{j−1}))}r_{j−1}(i).

As follows from this definition

r_{j}(i) = β^{Loss_{P_{i}}(y_{1}...y_{j})}r_{0}(i).

After each trial y_{j−1} a superprediction g_{j} is defined

g_{j}(ω) = log_{β} ∑_{i=1}^{k} β^{λ(ω,P_{i}(y_{1}...y_{j−1}))}r_{j−1}^{∗}(i),

where

r_{j−1}^{∗}(i) = \frac{r_{j−1}(i)}{∑_{s=1}^{k} r_{j−1}(s)}

are the normalized weights.

Since the loss function is η-mixable for any j = 1, …, n a real number p_{j} exists (can be effectively computed with arbitrary degree of accuracy) such that

λ(ω, p_{j}) ≤ g_{j}(ω)

for all ω (= 0, 1 in our case). Define P (y_{1} … y_{j−1}) = p_{j}.

By mathematical induction on t = 1, … n we shall prove that

∑_{j=1}^{t} g_{j}(y_{j}) = log_{β} ∑_{i=1}^{k} β^{Loss_{P_{i}}(y_{1}...y_{t})}r(i).  (19)

The inequality (18) will be follow from (19) when t = n.

When t = 1 we have

g_{1}(y_{1}) = log_{β} ∑_{i=1}^{k} β^{λ(y_{1},P_{i}(□))}r(i).

When t > 1 we have

log_{β} ∑_{i=1}^{k} β^{Loss_{P_{i}}(y_{1}...y_{t})}r(i) − log_{β} ∑_{i=1}^{k} β^{Loss_{P_{i}}(y_{1}...y_{t−1})}r(i) =

log_{β} _{\frac{∑_{i=1}^{k} β^{Loss_{P_{i}} (y_{1}...y_{t−1})+λ(y_{t},P_{i}(y_{1}...y_{t−1}))}r(i)}{∑_{i=1}^{k} β^{Loss_{P_{i}} (y_{1}...y_{t−1})}r(i)}} =

log_{β} ∑_{i=1}^{k} β^{λ(y_{t},P_{i}(y_{1}...y_{t−1}))}r_{t−1}^{∗}(i) = g_{t}(y_{t}).

A.2 Properties of predictive complexity

The construction of the predictive complexity KG(x) is based on applying the idea of AA to semicomputable from above sequence K_{i}(x) of all measures of predictive complexity satisfying conditions (i)-(ii) of Section 2. KG(x) was defined in Section 2 by equation (3), where r_{i} is a semicomputable from below

sequence of real numbers such that the series ∑_{i=1}^{∞} r_{i} is convergent and its sum

does not exceed 1.

By definition KG(x) is semicomputable from above, i.e (i) holds. We must verify (ii). Indeed, by (3) for any x and j = 0, 1

KG(xj) − KG(x) = log_{β} ∑_{i=1}^{∞} q_{i}β^{K_{i}(xj)−K_{i}(x)} ≥

log_{β} ∑_{i=1}^{∞} q_{i}β^{λ(j,γ_{i})} ≥ λ(j, γ),

where

q_{i} = \frac{r_{i}β^{K_{i}(x)}}{∑_{s=1}^{∞} r_{s}β^{K_{s}(x)}} .

Here γ_{i} satisfying

K_{i}(xj) − K_{i}(x) ≥ λ(j, γ_{i})

exists since each element of the sequence K_{i}(x) satisfies the condition (i) of the measure of predictive complexity (Section 2), and γ satisfying the last inequality exists by definition of η-mixability. For further details see [8], Section 7.6.

REFERENCES 14

References

[1] Haussler, D., Kivinen, J. and Warmuth, M.K. (1994) Tight worst-case loss bounds for predicting with expert advice. Technical Report UCSC-CRL-94-36, University of California at Santa Cruz, revised December 1994. Short version in P. Vitányi, editor, Computational Learning Theory, Lecture Notes in Computer Science, volume 904, pages 69–83, Springer, Berlin, 1995.

[2] Levin, L.A. (1984) Randoness conservation inequalities; Information and independence in mathematical theories. Inform. Comp., 61, 15–37.

[3] Li, M. and Vitányi, P. (1997) An Introduction to Kolmogorov Complexity and Its Applications. Springer, New York, 2nd edition.

[4] Shen, A. (1983) The concept of (α, β)-stochasticity in the Kolmogorov sense and its properties. Sov. Math. Dokl., 28, 295–299.

[5] Vovk, V. (1990) Aggregating strategies. In M. Fulk and J. Case, editors, Proceedings of the 3rd Annual Workshop on Computational Learning Theory, pages 371–383, San Mateo, CA, 1990. Morgan Kaufmann.

[6] Vovk, V. (1998) A game of prediction with expert advice. J. Comput. Syst. Sci., 56:153–173.

[7] Vovk, V. and Gammerman, A. (1999) Complexity estimation principle, The Computer Journal, 42:4, 318–322.

[8] Vovk, V., Watkins, C.J.H.C. (1998) Universal portfolio selection, Proceedings of the 11th Annual Conference on Computational Learning Theory, 12–23.

[9] V’yugin, V.V. (1985) Nonstochastic objects, Problems Inform. Transmission 21, 77–88.

[10] V’yugin, V.V. (1987) On the defect of randomness of a finite object with respect to measures with given complexity bounds, SIAM Theory Probab. Appl. 32, 508–512.

[11] V’yugin, V.V. (1998) Non-stochastic infinite and finite sequences, Theoretical Computer Science. 207, 363–382.

[12] Zvonkin, A.K. and Levin, L.A. (1970) The complexity of finite objects and the algorithmic concepts of information and randomness, Russ. Math. Surv. 25, 83–124.

[13] Yamanishi, K. (1995) Randomized approximate aggregating strategies and their applications to prediction and discrimination, in Proceedings, 8th Annual ACM Conference on Computational Learning Theory, 83–90, Assoc. Comput. Mach., New York.