Jan POLAND and Thomas ZEUGMANN Graduate School of Information Science and Technology Hokkaido University
Abstract
We present and relate recent results in prediction based on countable classes of either probability (semi-)distributions or base predictors. Learning by Bayes, MDL, and stochastic model selection will be considered as instances of the first category. In particular, we will show how analog assertions to Solomonoff's uni- versal induction result can be obtained for MDL and stochastic model selection. The second category is based on prediction with expert advice. We will present a recent construction to define a universal learner in this framework.
1
Introduction
If one aims at knowledge federation over the web, learning is indispensable. As a motivating example, we may consider all research papers available on the web. Clearly, not all papers are relevant to our own research. Assuming the papers to be distributed by some unknown probability distribution, we may aim to learn this distribution by interaction. That is, whenever a new paper is detected, the learner predicts whether or not it is relevant. Then the human user provides the true classification. Over time, we want to converge to predictor which (mostly) correctly classifies papers as relevant or not relevant. Then we could reduce or stop human interaction and use the predictor within an agent searching the web and selecting the papers relevant to our research. Such a task could be modeled within the following framework. Consider the following general online induction setup. An agent (in the following also called learner or predictor ) and an environment play a game that proceeds in rounds t = 1, 2, . . . In each round t , the environment first provides some input z t ∈ Z to the agent, where Z is the input space. Note that we also allow Z = {∅}. However, input is convenient to state important applications such as knowledge federation or pattern classification. After seeing the input z t , the agent and the environment simultaneously fix a decision d t ∈ D and a current state s t ∈ S , respectively, such that no player knows the other's move while making his own move.  Here, D is the space of possible decisions of the agent, and S the space of possible states of the environment. Now the environment learns the decision of the agent d t and provides an observation x t = G(s t,d t ) to the agent. The observation function G may depend on the current state and decision and possibly on some additional randomness. Finally, the current performance of the agent is measured in terms of a loss function ℓ t = ℓ( s t, d t ), which may depend on the current state and the agent's decision. Note that the agent does not necessarily get to know its own loss f . Throughout this paper, we will assume uniformly bounded losses, i.e., (possibly after rescaling) ℓ : S × D → [0, 1]. We will focus on two variants of this induction framework.  First, cases will be considered where the current decision d t is meant as an estimate of the current state s t . Here, the agent will work with a base class of possible stochastic environments, one of which is the data generating or true one. According to the observations, the agent updates its belief state by using Bayes rule. This setup is subject of Section 2. In the other setup, which is studied in Section 3, the agent directly tries to minimize the cumulative loss.  Here we may assume that we play against an adversary who chooses the state s t (and even the input z t ) in order to maximize the agent's cumulative loss L 1:T := ∑ t=1 ℓ t , while of course the agent aims to minimize this quantity.  We consider the worst case , without any assumption on the data generating process. Both observation function and loss function are assumed to be deterministic in this setup. The agent has access to the recommendations of a class of base agents or experts and follows the advice of one of them (if the decision space and the loss function are convex, it could also follow a mixture recommendation). Experts are weighted according to their past performance. All performance guarantees for the agent will be relative to the expert class. Although our online induction framework is already quite general, still extensions and generalizations are thinkable. For example, the input z t could be chosen by the agent instead of the environment.  This would enhance the possible applications to active learning, where the aim is not only a small cumulative loss, but also some guaranteed quality of the learner's hypothesis after a certain (small) amount of time steps.  Another modification is considering loss functions which depend on the actual observation x t instead of (or additionally to) the state s t . Later (Theorem 9), we will see how a bound on such a cumulative loss ∑ ℓ( x t , d t ) follows from a bound on a suitable cumulative loss ∑ ℓ(s t , d t ) in a Bayesian setting. In the experts setting, since the observation function is deterministic, a bound on ∑ ℓ( x t , d t ) is always weaker than a bound on ∑ ℓ( s t , d t ). In both variants, induction based on a model class and on an expert class, it is possible to work with universal classes which are defined by some fixed universal Turing machine. We will show below how to obtain such constructions (Definitions 2 and 10). This introduction is concluded by discussing some further standard problem setups in our framework. Pattern classification .  This is one of the most commonly studied problems in machine learning. In case of binary classification, the state is simply the probability that the observation will be one, depending on the input pattern (note that we allow stochastic concepts).  In the multi-class case we have a probability vector instead. Although classification has been also studied in the experts framework [CB97], it is usually treated by considering a model class (e.g. linear separators, then classification can be done by support vector machines). In this case, with stochastic concepts, the agent's decision d t is an estimate of the true probability s t , and the loss ℓ t often measures their difference. Universal Induction . Solomonoff [Sol78] has studied sequence prediction (without inputs, i.e.,  Z = {∅}) based on a universal model class.  We will discuss his construction below (Definition 2 and Theorem 6).  Parallel constructions can be obtained for a Minimum Description Length (MDL) predictor (Theorem 7) and a learner based on stochastic model selection (Theorem 8), the latter however has no (direct) finite bound for universal model class. Bandit Problems. In this setup, the agent decides to pull one “arm” of a K-armed bandit and learns only the loss of the selected arm, but not the losses of the alter- native arms. This is a basic instance of the exploration-exploitation tradeoff problem and has been studied both in the model-based framework [GJ74] and the expert frame- work [ACBFS02]. Geometric online decision problems are characterized by the fact that the loss is linear in the current state and decision, l t = 〈 s t , d t 〉 . Based on [Han57], Kalai and Vempala [KV03] show a very elegant way to treat these problems, on which our methods in Section 3 build. "Active" decision making agents can be based on either model or expert classes. They are characterized by the fact that they are guaranteed (or at least expected) to perform well also in certain cases where the future behavior of the environment depends on the agent's decision ( reactive problems ). We will present a construction with a universal expert class in Section 3, for a construction with a model class we point to [Hut04].
2
Model Classes and Bayes Learning
Let the observation space X = {1 . . . | X |} be a finite alphabet ( X = {0,1} in case of binary alphabet). Then, in case that there are inputs, a probability distribution ν : Z ∋ z → ( ν ( x | z )) x ∈ x ∈ [0, 1] x | is a function which assigns each input to a probability input, the distributions are independently and identically distributed (i.i.d.). In the case of sequence prediction, i.e.,  if there are no inputs, we conditionalize on the history instead of the inputs and consider arbitrary non-i.i.d. measures and semimeasures : For any history of observations x<t = x 1:t −1 = x 1 . . . x t −1 , the predictive (semi-)probability any mstory of strings ( v ( x < t ) z ∈ x = ( v ( x < t ) z ∈ x , where ν ( ε ) ≤ 1 and ν ( x < t ) ≥ ∑ z ∈ x ν ( x < t x ) for the empty string ϵ and any history x<t ∈ X* ( X* denotes the set of strings over X ). With equality in these inequalities, we call ν a measure, otherwise a semimeasure. The reason to study semimeasures at all is that the universal model class (Defi- nition 2 below) contains semimeasures. We could also consider semidistributions and conditionalize w.r.t. the history in the classification setup (with inputs), however this makes the presentation more complicated. Now, we consider a countable model class C = { ν 1 , ν 2 , . . .} of probability distribu- tions or semimeasures, respectively. Each ν ∈ C is assigned a prior weight w , ∈ (0 , 1) such that Evec wv ≤ 1. Example 1  Consider a binary classification problem with Z = R² and C ≥ Q², such that each model corresponds to a separating line with rational coefficients on the plane. For some (q1,q2) = ν ∈ C, we can set w, = 2–l(q1)–l(q2), where l(q) is the number of bits needed to specify a rational number q in a prefix-code. In the rest of this section, we shall drop the inputs z t from the notation and restrict to the sequence prediction case. Please keep in mind that all results equally apply to the classification setup with inputs. Next, we define a universal model class. Definition 2  (Universal Model Class) Consider a monotone function f : {0,1}* → X*, that is, if a string x ∈ {0,1}* is a prefix of another string x' ∈ {0,1}*, then also f(x) is a prefix of f(x') [LV97, Def. 4.5.2, Def. 4.5.3].  Fix a reference monotone Turing machine, then each monotone function f  corresponds to a program on this machine. With l(f) denoting the length of this program, we may set w(f) = 2-l(f) (assume that the program tape is binary).  According to [LV97, Theorem 4.5.2], each such f corresponds to a semimeasure ν ∈ M, where M is the set of all lower semicomputable (aka. enumerable) semimeasures. This defines w, for each ν ∈ M. It is possible to effectively enumerate M using the reference machine. Given a model class C together with the prior weights and a string of observations x<t , we can use Bayes' rule to define posterior weights. Then, a predictor can use these posterior weights for predicting in three different ways: Bayes mixture, MDL, or stochastic model selection. Definition 3 (Bayes mixture) For a class C consisting of (semi-)measures, a string x<t, and a character x ∈ X, let ξ(x<t) = ∑ν∈c wνν(x<t) and ξ(x|x<t) = ξ(x<t2) One can show [LV97, Theorem 4.5.3] that the Bayes mixture ξ( x <t ) is, within a multiplicative constant, equal to the Solomonoff prior , which is the probability of ob- taining x<t when running the reference monotone machine on an input of fair coin flips. Moreover, ξ( x <t ) is a semimeasure and lower semicomputable, thus a universal element of M , and the ξ -predictions are approximable. However, ξ and its predictions are not computable, i.e.,  they cannot be approximated by a program on the reference machine while knowing the approximation quality. Definition 4 (MDL, [PH05a]) Let C be a class containing (semi-)measures, x<t, x<i E X*, and x ∈ X. Define
Note that this definition is two-part MDL in the sense of the construction principle, choosing a model that simultaneously minimizes the description length of the model plus that of the data given the model. Thus, e coincides with a maximum a posteriori (MAP) estimator. Sometimes, the term MDL is used for more specific constructions, in particular with specific priors, or for a coding which avoids a redundancy arising in our construction [Ris96]. Further observe that dynamic MDL predictions select a different model for each possible continuation of the currently observed string x <t . Thus they are in practice (for finite model class) computationally more expensive than static MDL prediction, which use only the current string x<t for model selection. For the universal model class, none of the variants is computable. The MDL estimator o ( x <t ) is lower semicomputable, hence the dynamic MDL predictions are approximable. For the static MDL predictions, approximability is not obvious (and maybe not satisfied). Finally note that the normalized variants are constructed in order to define measures on X . selection) For a class C = { v } neasures, a string x<t, and a character x ∈ X, the stochastic model selection ictor Ξ samples a model according to the current (posterior) weights and uses this odel for prediction, i.e.,
o not define stochastic model selection for semimeasures, as the bounds in Theo- e infinite for the universal model class (Definition 2).  This is because the entropy = − ΣνεΜ w ν log w ν of this model class is infinite, which can be seen as follows: each string b ∈ {0,1}*, let K ( b ) be its prefix Kolmogorov complexity [LV97]. To ch such b , we can find a monotone program of length K ( b ) + O (1) bits that generates and afterwards random coin flips. But then, H(M) = Ω( ∑ b ∈{0,1}. K(b)2-K(b) = ∞, ce K ( b ) is the shortest possible coding of b save for an additive constant.  On the other nand, replacing the universal prior weights w( f ) = 2-1(f) by the slightly smaller weights (f) = 2-1(f)/l(f)2, we can define a universal stochastic model selection algorithm with nite bound. All of the above defined prediction methods have bounds on the expected cumu- lative difference of the predictive probabilities to the true probabilities, provided that here is a true data generating distribution μ in the model class, μ ∈ C . The state st rom the general framework in the introduction then becomes the current probability ector, s t = µ( · | x < t ). For a predictive distribution ϕ( · | x < t ), depending on the history nd possibly some additional randomness), we define the instantaneous quadratic and Hellinger distance, respectively: en the expected cumulative quadratic and Hellinger distance are given by Q 1:T ( ϕ ) = Eqt(ϕ, x<t) and H 1 : τ(ϕ) = ∑ t<τ Eht (ϕ, x<t) , where the expectation is w.r.t. the listribution μ over the possible outcomes of x<t and the possible randomness of predictor. Then we have the following performance guarantees for our previously ined predictors. eorem 6  (Bayes mixture performance guarantee, [Sol78]) Let C be a class of (semi- es and assume that there is a proper measure μ ∈ C which generates the data. 1:T(ξ) ≤ log w − 1 and H(ξ)1:T ≤ log w − 1 for all T ≥ 1. the following result for MDL, the theorem applies to the universal model class inition 2. Moreover recall that the theorem and all following also apply to the assification setup, i.e.,  in the presence of inputs. orem 7 (MDL performance guarantees, [PH05a]) Let C  contain (semi-)measures assume that there is a true measure μ ∈ C . Then, Q 1:T( ρ ) = O( w − 1 ) and H( ρ ) 1:T = ) hold for any T ≥ 1. The same is valid for all other MDL predictors onorm, ostatic, The bound for MDL is exponentially larger than that for the mixture. One can show that this is sharp in general, even for classes containing only Bernoulli distribu- tions [PH04]. This makes the bound practically irrelevant for all but very small model classes. Thus it motivates to select the prior more carefully when using MDL, resulting in better bounds [Ris96, PH04]. We will encounter a similarly exponential bound in Theorem 13, however for a different reason. Theorem 8  (Stochastic model selection performance guarantee, [Pol06]) Let C  contain proper measures and assume that there is a true measure μ ∈ C. Then, Q1:T(Ξ) and H 1:T (Ξ) are both O (Π · (log H + log w − 1 )) for any T ≥ 1. Here, H = H ((w ν )νες) = — E v ∈ c w ν log w ν is the entropy of the model class, while Π is the μ -entropy potential defined as Π((wv)vcc) = sup {H(( E wvpr,)v) : Pµ = 1 ∧ pv ∈ [0,1] ∀v ∈ C \ {µ}}. One can show that a finite bound on Q1:T(ϕ) (or H1:T(ϕ)) implies that the ϕ- predictive probabilities converge to the true μ -probabilities almost surely.  This nice property therefore holds for all of the above prediction methods. Moreover, consider the situation that the learner's aim is to minimize its expected loss which is a known function ℓ( x t , ˆ x t ) depending on the outcomes x t ∈ X (rather than the state s t , compare the introduction) and its estimate ˆ x t = d t ∈ X . Then the learner, which has access to a current belief probability ϕ( · | x < t ) may choose its prediction ˆ x t in a Bayes optimal way, i.e.,  î t = arg min ż ∑ x ♀( x < t ) ℓ( x, î ).  In this case, finite bounds on the cumulative Hellinger distance imply O( √ ī ) bounds on the loss, for arbitrary bounded loss function l : ( x t, î t ) → [0, 1] (the proof can be found in [PH05a, Lemma 24–26]). Theorem 9 (Loss bounds) Assume D = X and the losses ℓ( x t, ˆ x t ) ∈ [0, 1] depend on the outcome.  Then a predictor ϕ, knowing this loss function and making Bayes optimal predictions w.r.t. it's belief probability, has the loss bound EL i.T ≤ EL i.T + 2H i.T( ϕ ) + 2√2H1:T(ϕ)ELf.T, where Lf.T is the cumulative loss of the Bayes optimal predictor using the true probabilities.
3
Expert Classes
Theorem 9 is a bridge to the other type of learning algorithm considered in this paper, an agent based on a class of experts. If there is a known loss function, each model ν ∈ C recommends a decision d t ∈ X in each round t , namely the Bayes optimal one. Hence we may randomly select a model using the regret minimization algorithm FPL (Defi- nition 11 below) based on the past losses. Then we may apply a suitable performance guarantee in the spirit of Theorem 13, such as [HP05, Theorem 9] for countable model class. This gives essentially the assertion of Theorem 9 without expectation over μ (but with expectation over the agent's randomization) for arbitrary observations x 1 , x 2 , . . ., with no assumptions (!)  on the data generating process necessary.  By an applica- tion of Jensen's inequality, the assertion also follows in μ -expectation (as observed by M. Hutter). Regret minimization algorithms like FPL are always applicable with a class of base experts ξ = { c 1 , e 2 , . . . } , each e ∈ ξ suggesting a decision d ξ in each round t : we only need to observe the experts' losses ℓ( s t, đ ξ ) (at least some losses from time to time). Parallel to the model class setup, each expert e is assigned a prior weight w e > 0 such that ∑ e∈ε W e = 1. We may restrict to the case that state s t is the vector of all experts' current losses, s t = ( ℓξ ) e∈ε [KV03]. Recall that the observation function G is be deterministic. Performance guarantees (loss bounds) then usually n the worst case, without any assumption on the data generating process. However, the experts algorithms do not estimate probabilities, and they are likely to yield inferior predictions to a Bayesian method in cases where accurate estimates of the probabilities are possible and beneficial. This section sketches construction and performance guarantees of an expert algo- rithm which works with the universal expert class P from Definition 10 below. The results are mainly from (and extensions of) [PH05b, Pol05]. There is a huge literature of experts algorithms with different purpose which cannot be dealt with here. Definition 10 (Universal expert class) Let D be a finite or countable decision space. Fix a reference monotone universal Turing machine with binary output alphabet and let P = {p1,p2,...} be an enumeration of all programs. Then P defines an expert class, and each program p ∈ P is an expert with prior weight w p = 2-1(p): If the agent selects to follow p's recommendation, it runs p on the complete observation history, until the output tape contains the prefix code of a decision df ∈ D. If this never happens, we define that the expert chooses a fixed decision d 1 ∈ D . In this case, the computation does not halt, and (like the above learners for universal model class) the overall agent is not computable. It is however easy to impose an additional constraint on the computation time, e.g. aborting the computation after at maximum exp(t) steps (hence we have more time in later rounds). In order to simplify notation, we abbreviate the instantaneous and cumulative loss of each expert e E E as l E and L E . T , respectively. Definition 11 (FPL: Follow the Perturbed Leader algorithm with full observation) At time t, sample a perturbation rf  independently from the exponential distribution for ach expert e ∈ E .  With η t > 0 being the learning rate, follow the recommendation of the expert with the best perturbed score, ἕ = arg min{ηι L ξ t − log w e − r ξ : e ∈ E }, that is, d t = d t = d ξ . Observe that, in case that experts are identified with models, FPL is a stochastic model selection algorithm with a non-Bayesian posterior, i.e.,  different from Defi- nition 5.  In contrast to Bayesian stochastic model selection, FPL usually does not provide predictive probabilities, but is designed for minimizing the cumulative regret. The performance guarantee for this FPL algorithm states that the regret , which is the difference ELF.PL – ELf.T (expectations are w.r.t. FPL's randomization) is bounded by O( √T ) for any reference expert e and any sequence of loss vectors s 1 , s 2 , . . . This means, that the average per-round regret (divided by T ) goes to zero in expectation and, by the Borel-Cantelli-Lemma, even with probability one. Of course, regret is measured against the actual performance of an expert. In certain reactive cases, where the future actions of the environment depend on the current decision, some strong experts could display an unnecessarily weak performance.  An example is the repeated game of Prisoner's dilemma where the opponent plays the "tit-for-tat" strategy:  Although defecting is the dominant action, cooperating is the better long term strategy [dFM04].  A simple work- around giving better results in this and similar cases is to play a selected expert not for just one, but for B t time steps, with B t increasing in t . Hence, the expert selection or master algorithm will be invoked only after B 1 , B 1 + B 2 , . . . time steps, resulting in a time scale change. We will denote the new master time scale by t and the elementary t. All analysis is then on the new master time scale t. We set B ī = | t 178 nen the original time scale t is of order t 9/8. The basic FPL algorithm assumes that all losses are observed, which is not nec- ssarily so for all problems. In fact, for reactive problems, this assumption would be too strong, even if we observe the (hypothetical) performance of all experts: Those ex- perts other than the selected one would have computed different decisions and therefore would have had different performance. In the following, we construct an agent for the bandit setup , i.e.,  in each round f it learns only its own loss, but not that of the alter- natives. A common technique in bandit and more general partial observation setups is to introduce the quantity of the estimated loss setting ℓξ = ℓξ /P( ξ -observation) for the currently observed expert ξ , and ℓξ = 0 for all experts not observed. By letting P( ē -observation) be the probability of observing the expert ê’s loss, it is achieved that ℓ ī and consequently L are unbiased estimates for the rue performances. Dividing by these probabilities, we have to be careful that they cannot become too small, since the analysis of the algorithm crucially relies on the fact of bounded (estimated) losses.  In fact, there are two issues to address: First, the probabilities get arbitrarily small for experts with small prior weights.  Thus, we do not use all experts from the beginning, but for each expert e ∈ E , we define an introduction time τ e ≥ 1. At time t , we only work with the set of active experts {τ ≥ i} := {e : τ e ≥ ī}. Second, an expert could be assigned with small probability because of past bad performance. For the case that it is selected anyway, we replace the denominator by max{P( ē -observation), γ ī }, where γ ī > 0 decreases in  ξ . Finally, unlike weighted averaging algorithms (on which there is a rich literature, but we know of no variant with dynamic learning rate and countably many experts so far), the FPL algorithm does not have access to the explicity sampling probabilities P( ē -observation). We can get around this problem by estimating this quantity for the selected expert by sampling the leader for other [2 t 2 log(2 √ t )] = O( t 2 ) times and taking the relative frequency estimate. Definition 12 (Universal FPL algorithm) The uFPL algorithm is defined as the FPL algorithm based on the universal expert class P and with the modifications stated in the last paragraphs (new master time scale, loss estimates by dividing by the probability estimates, always working with a finite expert class increasing over time). Theorem 13 (Performance of uFPL, adapted from [PH05b, Pol05]) The uFPL algo- rithm with learning rate η i = 1 ξ − 1/2, time step parameter B i = [ ξ 1/8], denominator threshold γ ī =ｶī -3/4, and introduction times τ P = [w r 8], has a regret bound of at most EL uFPL − EL l l , T = O ( w − 12 + t 2/3 log w − 1 ). This holds against any expert p ∈ P, i.e., against any program on the fixed universal Turing machine, in expectation over FPL's randomization, on any sequence of loss vectors. Consequently, measured in terms of average per-round loss, uFPL performs (asymptotically) as well as any program. We would like to point the reader to an interesting detail: Most bandit variants for FPL have been defined such that the observations are used only in designated exploration phases.  Thus, the resulting algorithm is label efficient and has a lower regret bound of t 2/3 [CBLS04], while our algorithm has a basic bound of √ t. In fact a bound of t ž +ε can be obtained at the cost of increasing power of w ε 1 for decreasing ε . Working without explicit exploration is particularly facilitated by the fact that we work with losses instead of rewards: Then, experts which are not sampled can only gain weight, which results in implicit exploration [Pol05]. Of course, each of the modifications of the paragraphs preceeding Definition 12 may cause its own additional regret which has to be taken into account in the analysis. This is carried out in [PH05b, Pol05].  The conclusion of Theorem 13, "uFPL performs as well as any program, on any task", seems very strong. Moreover, uFPL is even computable, since it works with a finite expert class in each time step. With the trick stated in Definition 10, each expert can also be made computable, the reference is then the class for resource bounded programs. Still, uFPL is far from being practically relevant, since w ε 1 is huge for all but very small expert classes (in particular, w ε 1 is huge for any moderate program).  On the other hand, one can show that this bound is sharp for bandit problems [ACBFS02], for which our setup is an instance. This exponential blow-up, where bounds contain a huge w − 1 instead of a reasonable log w − 1 , occurs in different cases for different reasons. In MDL (Theorem 7), it can be viewed as the possible unbalancedness of the prior [PH05a].  Even in stochastic model selection (Theorem 8), there are (bad) instances where Π becomes exponentially large [Pol06]. But most seriously, in (re-)active problem setups this phenomenon seems unavoidable in general. It is one of the major open problems to resolve it, i.e., define conditions and algorithms for which bounds of reasonable size hold also for reactive problems.