Does snooping help?

V. V. V’yugin ^{1}

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-06

December 1999

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

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

1Address for correspondence: Troitskaya street 10-275, Moscow 129090, Russia

Abstract

One of the most efficient way of improving the performance of learning algorithms is “snooping”, i.e. using some information about the data to be predicted for choosing the parameters of the learning algorithm or the learning algorithm itself. Allowing different degrees of snooping α makes it possible to attain a better performance Loss_{P} (x) of a prediction strategy P on the given data set x. We study the “snooping curves” L_{x}(α) = inf_{K(P)≤α} Loss_{P} (x), where K(P) is the Kolmogorov complexity of

the prediction strategy P. Our main result states that “anything is possible”: we prove that any non-increasing function is a limit point of the family functions {L_{x}}. Our framework is that of on-line prediction; for simplicity we assume that sequences x are binary.

Prediction strategies 1

1 Prediction strategies

Suppose we are given a data set x_{1}, x_{2}, …, x_{i} …; in this paper we consider only the simplest case, where x_{i} ∈ {0, 1}. Our goal is to predict the elements of the 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 loss function λ(x_{i}, p_{i}), where the forecast is a real number p_{i} and the actual outcome is x_{i}. We suppose that this function is computable. For example, we consider the squared difference λ(x_{i}, p_{i}) = (x_{i} − p_{i})^{2} and the log-loss 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 (in the following log means the logarithm to the base 2). Other loss functions are considered in Vovk [6], Haussler, Kivinen, Warmuth [2] (log-loss, Hellinger, etc); Vovk and Watkins [8] (financial theory); Yamanishi [11] (logistic), etc]. An interesting theoretical possibility (and sometimes an unsightly phenomenon of the real life) is “snooping”, or choosing the learning algorithm depending on the sequence x. Of course, we can always built x into the learning algorithm and attain ideal performance, so we have to limit snooping; to do so, we will use the notion of Kolmogorov complexity of a finite object (see, e.g., Li and Vitanyi [3]). Since the computable prediction strategy S is defined by some algorithm, by complexity K(S) of this prediction strategy S we mean the Kolmogorov complexity of this algorithm. By definition of Kolmogorov complexity K(S) is equal to the length of the shortest program computing values of S under some optimal way of programming.

It is natural to suppose that all predictions are given according to a prediction strategy (or learning 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].

“Honest” learning algorithms S are those with small Kolmogorov complexity. Knowing x allows us to choose more complicated S (tuned for this particular x), but we will impose the restriction K(S) ≤ α, where α is a positive constant reflecting the degree of snooping allowed.

We impose the following restrictions on the loss function λ(ω, p): there exists a positive computable real number b such that

⋄ (1) λ(0, p) ≥ b or λ(1, p) ≥ b for each p;

⋄ (2) There exists a computable real number p̂ such that λ(0, p̂) = λ(1, p̂) = b;

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

⋄ (4) The loss function is perfectly mixable (see below).

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

These conditions looks unnatural but they follow from the more natural conditions communicated to author by Yura Kalnishkan:

⋄ (5) λ(0, p) = λ(1, 1 − p) for all p (symmetry condition);

⋄ (6) λ(0, \frac{1}{2}) ≠ 0 (or λ(1, \frac{1}{2}) ≠ 0);

⋄ (7) λ(0, 0) = 0 (or λ(1, 1) = 0);

⋄ (8) λ(0, p) ≤ λ(0, p′) and λ(1, p) ≥ λ(1, p′) if p ≤ p′ (monotonicity condition).

Without loss of generality we can normalize an arbitrary loss function λ(ω, p) satisfying conditions (1)-(4) λ′(ω, p) = b^{−1}λ(ω, p) for some b (satisfying (1)-(4)). So, in the following we suppose that our loss function satisfies conditions (1)-(4) with b = 1.

By “perfectly mixable” loss functions we mean the following. Let us fix η > 0 (the learning rate). Put β = e^{−η} ∈ (0, 1). The loss function (game) is perfectly η-mixable if for every sequence (p_{1}, p_{2}, …) of predictions and a sequence (r_{1}, r_{2}, …) of nonnegative weights summing to 1 there exists a prediction p such that, for all y

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

The loss function (game) is perfectly mixable if it is perfectly η-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], [2], [6] [8]) are perfectly mixable.

The important construction in this field is the Vovk’s aggregating algorithm AA [5], [6], [8], Section 2. 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. A variant of Vovk’s construction is given in Section A below.

Snooping curves 3

2 Snooping curves

We will consider loss functions satisfying conditions (1)-(4) with b = 1. For any data sequence x we consider the “snooping curve” (or “snooping function”)

L_{x}(α) = inf_{K(S|n)≤α} Loss_{S}(x),

where n is the length of the finite binary sequence x. In the following the length of x will be denoted by l(x).

An analogous function (for the logarithmic loss function) as a measure of stochasticity was introduced by Kolmogorov in the seventies [1], [4], [3] and studied by Levin and V’yugin [9], [10].

Evidently, the snooping function is non-negative and non-decreasing. For any sequence x we have by (2) L_{x}(α + c) ≤ l(x) for each non-negative α, c is a constant. A more refined estimate is

L_{x}(α + c) ≤ n − α

for all positive α ≤ n, where n = l(x) is the length of x and c is a non-negative constant. To prove this inequality we define the following prediction strategy

S(x_{1}x_{2} … x_{i−1}) = \{ \begin{matrix}x_{i}, if i ≤ α, \\ p̂, otherwise , \end{matrix}

where the number p̂ satisfies the condition (2). By definition K(S|n) ≤ α + c for some positive constant c and Loss_{S}(x) ≤ n − α.

We present the general description of all possible forms of snooping functions for different x. We prove that for any finite simple function f(α) (i.e. function, whose domain is a union of finite number of intervals, and the function is constant on each of them) there is a finite binary sequence x such that L_{x}(α) is close to f(α).

Theorem 1 For any δ > 0 the constants c_{1} and c_{2} exist such that for any positive n and k and for any sequence

α_{1}, …, α_{k}, m_{1}, …, m_{k}

of positive integer numbers satisfying

c_{1} ≤ α_{1} < … < α_{k}

and

n > m_{1} > … > m_{k},

there exists a binary sequence x of the length n such that for 1 ≤ i ≤ k + 1 and all α satisfying the inequality

α_{i−1} + log_{2} i + c_{2} ≤ α ≤ α_{i}

the following estimate holds

m_{i} − (k − i)(c_{η}α_{k} + 1) ≤ L_{x}(α) ≤ m_{i},

where c_{η} = (1 + δ)(η log e)^{−1} and we put α_{0} = 0, α_{k+1} = ∞, m_{k+1} = 0.

Proof. It is naturally to include the information on the sequence I = (α_{1}, …, α_{k}, m_{1}, …, m_{k}) in the condition, i.e. we consider the conditional Kolmogorov complexity K(S|n, I) of a prediction strategy given n and I (see Li and Vitanyi [3]). For simplicity of the exposition we omit these conditions and write K(S).

For any prediction strategy P we consider the loss incurred over a fragment y_{m+1} … y_{k} of a sequence y_{1} … y_{n}, where m < k ≤ n.

Loss_{P} (y_{m+1} … y_{k}|y_{1} … y_{m}) = ∑_{i=m+1}^{k} λ(y_{i}, P (y_{1} … y_{i−1})).

Define m′_{i} = m_{i} − m_{i+1}, where i = 1, 2 …, k. For any α_{i} let P_{1}, P_{2}, …, P_{k(i)} be all computable prediction strategies P such that K(P) ≤ α_{i}. We have k(i) < 2^{α_{i}+1}. By means of AA (Section A) given the sequence m_{1}, …, m_{k+1} and 1 ≤ i ≤ k we can define an averaging prediction strategy P_{α_{i}} such that for any y = y_{1} … y_{n}

β^{Loss_{Pα_{i}} (y_{m+1}...y_{n}|y_{1}...y_{m})} ≥ ∑_{j=1}^{k(i)}(k(i))^{−1}β^{Loss_{P_{j}} (y_{m+1}...y_{n}|y_{1}...y_{m})},  (2)

where m = m_{1}−m_{i}. By construction of AA we can compute all values of P_{α_{i}}(z), where l(z) ≤ n, with an arbitrary degree of accuracy by means the program p_{i} with the following properties. The length of p_{i} is ≤ α_{i} and this program has the maximal terminating time among all programs computing values P_{j}(z) for all j ≤ k(i) and all z of the length ≤ n with given corresponding degree of accuracy. The important feature of this program is that using p_{i} we can compute also all values of P_{α_{j}}(z) for all j ≤ i.

Let us define a sequence y of the length m_{1} by mathematical induction on i. Let 1 ≤ i ≤ k and y_{1} … y_{m_{1}−m_{i}} is defined. We suppose that this sequence is empty when i = 1.

For m_{1} − m_{i} < s ≤ m_{1} − m_{i+1} define

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

Since these conditions are overlapped, we choose that the first was computed.

So, for any 1 ≤ i ≤ k we defined a sequence y_{1} … y_{m_{1}−m_{i+1}}.

The total loss incurred over y_{m_{1}−m_{j}+1} … y_{m_{1}−m_{j+1}} by the prediction strategy P_{α_{j}} is estimated from below

Loss_{P_{α_{j}}} (y_{m_{1}−m_{j}+1} … y_{m_{1}−m_{j+1}}|y_{1} … y_{m_{1}−m_{j}}) ≥ m′_{j} − 1.

By (2) for any i ≤ j ≤ k it holds

Loss_{P} (y_{m_{1}−m_{j}+1} … y_{m_{1}−m_{j+1}}|y_{1} … y_{m_{1}−m_{j}}) ≥ m′_{j} − c_{η}α_{j} − 1  (3)

for each prediction strategy P such that K(P) ≤ α_{j}.

Put y = y_{1} … y_{m_{1}} and x = y0^{n−m_{1}} (0 is concatenated n − m_{1} times).

We have K(P) ≤ α_{i} ≤ α_{i+1} ≤ … ≤ α_{k}. Summing the inequalities (3) for j = i, i + 1 … k we obtain

Loss_{P} (y_{1} … y_{n}) = Loss_{P} (y_{1} … y_{m_{1}−m_{i}}) +
Loss_{P} (y_{m_{1}−m_{i}+1} … y_{m_{1}−m_{i+1}}|y_{1} … y_{m_{1}−m_{i}}) +
Loss_{P} (y_{m_{1}−m_{i+1}+1} … y_{m_{1}−m_{i+2}}|y_{1} … y_{m_{1}−m_{i+1}}) + … +
Loss_{P} (y_{m_{1}−m_{k}+1} … y_{m_{1}−m_{k+1}}|y_{1} … y_{m_{1}−m_{k}}) ≥
m′_{i} + m′_{i+1} + … + m′_{k} − (k − i)(c_{η}α_{k} + 1) ≥
m_{i} + (k − i)(c_{η}α_{k} + 1).

for each strategy P such that K(P) ≤ α_{i}.

In order to obtain the upper bounds for any i = 1, 2 … k consider the prediction strategy U_{i}, depending on y_{1} … y_{m_{1}−m_{i+1}}, such that for any sequence z_{1} … z_{j−1}

U_{i}(z_{1}z_{2} … z_{j−1}) = \{ \begin{matrix}y_{j}, if 1 ≤ j ≤ m_{1} − m_{i+1}, \\ p̂, if m_{1} − m_{i+1} < j ≤ m_{1}, \\ 0, otherwise , \end{matrix}

where y_{j} is the j-th bit of the sequence y, and the number p̂ satisfies the condition (2). By definition

Loss_{U_{i}}(x) = m_{i+1}.

We have also K(U_{i}) ≤ α_{i} + 2 log_{2} i + c for some constant c, since the prediction strategy U_{i} can be defined by the number i and by the program p_{i}. □

Let ν(n) and μ(n) be two non-negative non-decreasing unbounded functions such that μ(n) < n for all n and ν(n) = o(μ(n)) as n tends to infinity. We will study the asymptotic behaviour of snooping curve in the rectangle 0 ≤ α ≤ ν(n) and 0 ≤ β ≤ μ(n). To do this, consider the family of “normalized” functions

f_{x}(t) = \frac{L_{x}(ν(n)t)}{μ(n)},

where n = l(x) and 0 ≤ t ≤ 1.

We consider the space L_{∞} = L_{∞}([0, 1]) with the norm ||f|| = sup_{x∈[0,1]} |f(x)|.

Then from Theorem 1 it follows

Corollary 1 Each non-increasing function whose graph is in the unit square is a limit point in metrics L_{∞} of the family functions {f_{x}}, where x ∈ Ξ.

Appendix: Aggregating algorithm 6

The most interesting case is ν(n) = O(log n).

Notice, that Theorem 1 cannot explain the situation in the case, where ν(n) = o(μ(n)) does not hold. It is an open problem to describe snooping curves in the case when the values of α and L_{x}(α) are of the same order.

Acknowledgements

I am grateful to Volodya Vovk for an idea of “snooping” interpretation and to Yura Kalniskan for useful discussions.

A Appendix: Aggregating algorithm

For any prediction strategy P we consider the loss incurred over a fragment y_{m+1} … y_{n} of a sequence y_{1} … y_{n}, where m < n.

Loss_{P} (y_{m+1} … y_{n}|y_{1} … y_{m}) = ∑_{i=m+1}^{n} λ(y_{i}, P (y_{1} … y_{i−1})).

We present the Vovk’s aggregating algorithm in a form convenient to us.

Proposition 1 Let a loss function λ(ω, p) be η-mixable and β = e^{−η}. For any 1 ≤ m ≤ n, any 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, a computable prediction strategy P exists such that for any binary sequence y_{1} … y_{n}

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

Proof. Remember that for any prediction strategy P the loss incurred on a fragment y_{m+1} … y_{n} of a sequence y_{1} … y_{n} is defined

Loss_{P} (y_{m+1} … y_{n}|y_{1} … y_{m}) = ∑_{i=m+1}^{n} λ(y_{i}, P (y_{1} … y_{i−1})).

Let r_{0}(i) = r(i), i = 1, …, k. Trials y_{1}, …, y_{m} are used as parameters. After each trial y_{m+j}, j = 1, …, n − m the weights are updated as follows

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

As follows from the definition

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

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

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

REFERENCES 7

where

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

are normalized weights.

Since the loss function is η-mixable for any j = 1, …, n − m 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_{m+j−1}) = p_{j}.

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

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

The inequality (4) will be follow from (5) when t = n − m.

When t = 1 we have

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

When t > 1 we have

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

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

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

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

□

References

[1] Cover, T.M., Gács, P. and Gray, R.M. (1989) Kolmogorov’s contributions to information theory and algorithmic complexity. Ann. Probab., 17, 840– 865.

[2] 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, [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., 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. (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.

[10] V’yugin, V.V. (1999) Algorithmic complexity and stochastic properties of finite binary sequences, The Computer Journal, 42:4, 294–317.

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