18.657 Mathematics of Machine Learning, Lecture 19 Notes

18.657: Mathematics of Machine Learning Lecture 19 Nov. 16, 2015 Lecturer: Alexander Rakhlin Scribe: Kevin Li 4. PREDICTION OF INDIVIDUAL SEQUENCES In this lecture, we will try to predict the next bit given the previous bits in the sequence. Given completely random bits, it would be impossible to correctly predict more than half of the bits. However, certain cases including predicting bits generated by a human can be correct greater than half the time due to the inability of humans to produce truly random bits. We will show that the existence of a prediction algorithm that can predict better than a given threshold exists if and only if the threshold satifies certain probabilistic inequalities. For more information on this topic, you can look at the lecture notes at http://stat.wharton.upenn.edu/~rakhlin/courses/stat928/stat928_notes.pdf 4.1 The Problem To state the problem formally, given a sequence y1 , . . . , yn , . . . ∈ {−1, +1}, we want to find a prediction algorithm ŷt = ŷt (y1 , . . . , yt−1 ) that correctly predicts yt as much as possible. iid In order to get a grasp of the problem, we will consider the case where y1 , . . . , yn ∼ Ber(p). It is easy to see that we can get " n # 1X IE 1{ŷt 6= yt } → min{p, 1 − p} n t=1 by letting ŷt equal majority vote of the first t − 1 bits. Eventually, the bit that occurs with higher probability will always have occurred more times. So the central limit theorem shows that our loss will approach min{p, 1 − p} at the rate of O( √1n ). Knowing that the distribution of the bits are iid Bernoulli random variables made the prediction problem fairly easy. More surprisingly is the fact that we can achieve the same for any individual sequence. Claim: There is an algorithm such that the following holds for any sequence y1 , . . . , yn , . . .. n 1X 1{ŷt 6= yt } − min{ȳn , 1 − ȳn} ≤ 0 a.s. lim sup n→∞ n t=1 It is clear that no deterministic strategy can achieve this bound. For any deterministic strategy, we can just choose yt = −ŷt and the predictions would be wrong every time. So we need a non-deterministic algorithm that chooses q̂t = IE[ŷt ] ∈ [−1, 1]. To prove this claim, we will look at a more general problem. Take a fixed horizon n ≥ 1, and function φ : {±1}n → R. Does there exist a randomized prediction strategy such that for any y1 , . . . , yn n 1X IE[ 1{ŷt 6= yt }] ≤ φ(y1 , . . . , yn ) ? n t=1 171 For certain φ such as φ ≡ 0, it is clear that no randomized strategy exists. However for φ ≡ 12 , the strategy of randomly predicting the next bit (q̂t = 0) satisfies the inequality. Lemma: For a stable φ, the following are equivalent n a) ∃(q̂t )t=1,...,n ∀y1 , . . . , yn 1X 1{ŷt 6= yt }] ≤ φ(y1 , . . . , yn ) IE[ n t=1 1 b) IE[φ(ǫ1 , . . . , ǫn )] ≥ where ǫ1 , . . . , ǫn are Rademacher random variables 2 where stable is defined as follows Definition (Stable Function): A function φ : {±1}n → R is stable if |φ(. . . , yi , . . .) − φ(. . . , −yi , . . . )| ≤ 1 n P IE[ n1 nt=1 1{ˆ yt 6= Proof. (a =⇒ b) Suppose IEφ < 12 . Take (y1 , . . . , yn ) = (ǫ1 , . . . , ǫn ). Then P ǫt }] = 12 > IE[φ] so there must exist a sequence (ǫ1 , . . . , ǫn ) such that IE[ n1 nt=1 1{ŷt 6= ǫt }] > φ(ǫ1 , . . . , ǫn ). (b =⇒ a) Recursively define V (y1 , . . . , yt ) such that ∀y1 , . . . , yn 1  V (y1 , . . . , yt−1 ) = min max IE[1{ŷt = 6 yt }] + V (y1 , . . . yn ) qt ∈[−1,1] yt ∈±1 n P Looking at the definition, we can see that IE[ n1 nt=1 1{ŷt 6= yt }] = V (∅) − V (y1 , . . . , yn ). Now we note that V (y1 , . . . , yt ) = − 2tn − IE[φ(y1 , . . . , yt , ǫt+1 , . . . , ǫn )] satisfies the recursive definition since 1 t min max IE[1{ŷt 6= yt }] − IE[φ(y1 , . . . , yt , ǫt+1 , . . . , ǫn )] − y q̂t t n 2n −q̂t yt t−1 = min max − IE[φ(y1 , . . . , yt , ǫt+1 , . . . , ǫn )] − yt q̂t 2n 2n q̂t t − 1 qˆt t−1 = min max{− − IE[φ(y1 , . . . , yt−1 , 1, ǫt+1 , . . . , ǫn )] − , − IE[φ(y1 , . . . , yt−1 , −1, ǫt+1 , . . . , ǫn )] − } q̂t 2n 2n 2n 2n t−1 = − IE[φ(y1 , . . . , yt−1 , ǫt , ǫt+1 , . . . , ǫn )] − 2n =V (y1 , . . . , yt−1 ) The first equality uses the fact that for a, b ∈ {±1}, 1{a 6= b} = 1−ab 2 , the second uses the fact that yt ∈ {±1}, the third minimizes the entire expression by choosing q̂t so that the two expressions in the max are equal. Here the fact that φ is stable means q̂t ∈ [−1, 1] and is the only place where we need φ to be stable. Therefore we have n 1X 1 IE[ 1{ŷt 6= yt }] = V (∅)−V (y1 , . . . , yn ) = −IE[φ(ǫ1 , . . . , ǫn )]+ +φ(y1 , . . . , yn ) ≤ φ(y1 , . . . , yn) n 2 t=1 172 by b). By choosing φ = min{ȳ, 1 − ȳ} + original claim. √c , n this shows there is an algorithm that satisfies our 4.2 Extensions 4.2.1 Supervised Learning We can extend the problem to a regression type problem by observing xt and trying to predict yt . In this case, the objective we are trying to minimize would be 1X 1X l(ŷt , yt ) − inf l(f (xt ), yt ) f ∈F n n It turns out that the best achievable performance in such problems is governed by martingale (or, sequential) analogues of Rademacher averages, covering numbers, combinatorial dimensions, and so on. Much of Statistical Learning techniques extend to this setting of online learning. In addition, the minimax/relaxation framework gives a systematic way of developing new prediction algorithms (in a way similar to the bit prediction problem). 4.2.2 Equivalence to Tail Bounds We can also obtain probabilistic tail bound on functions φ on hypercube by using part a) of 1 P the earlier lemma. Rearranging part a) of the lemma we get 1 − 2φ(y1 , . . . , yn ) ≤ n q̂t yt . This implies IP φ(ǫ1 , . . . , ǫn ) < So IEφ ≥ 1 2

µ2 1 − µ
1X = IP 1 − 2φ(ǫ1 , . . . , ǫn ) > µ ≤ IP q̂t ǫt > µ ≤ e− 2n 2 n =⇒ existence of a strategy =⇒ tail bound for φ < 21 . We can extend the results to higher dimensions. Consider z1 , . . . , zn ∈ B2 where B2 is a ball in a Hilbert space. We can define recursively ŷ0 = 0 and ŷt+1 = ProjB2 (ŷt − √1n zt ). P yt − y ∗ , zt i ≤ √1n . Based on the properties of projections, for every y ∗ ∈ B2 , we have n1 hˆ P zt Taking y ∗ = P , k zt k ∀z1 , . . . , zn , k n X zt k − √ n≤ t=1 n X hŷt , −zt i t=1 Take a martingale difference sequence Z1 , . . . , Zn with values in B2 . Then IP k n X Zt k − n X
√ nµ2 n > µ ≤ IP( hŷt , −Zt i > µ) ≤ e− 2 t=1 t=1 Integrating out the tail, IEk n X √ Zt k ≤ c n t=1 173 It can be shown using Von Neumann minimax theorem that ∃(ŷt )∀z1 , . . . , zn , y ∗ ∈ B2 n X hŷt − y ∗ , zt i ≤ t=1 sup MDSW1 ,...,Wn Ek n X √ Wt k ≤ c n t=1 where the supremum is over all martingale difference sequences (MDS) with values in B2 . √ By the previous part, this upper bound is c n. We conclude an interesting equivalence of (a) deterministic statements that hold for all sequences, (b) tail bounds on the size of a martingale, and (c) in-expectation bound on this size. In fact, this connection between probabilistic bounds and existence of prediction strategies for individual sequences is more general and requires further investigation. 174