18.657 Mathematics of Machine Learning, Lecture 4 Notes

18.657: Mathematics of Machine Learning Lecture 4 Sep. 21, 2015 Lecturer: Philippe Rigollet Scribe: Cheng Mao In this lecture, we continue to discuss the effect of noise on the rate of the excess risk ˆ = R(h) ˆ − R(h∗ ) where h ˆ is the empirical risk minimizer. In the binary classification E(h) model, noise roughly means how close the regression function η is from 21 . In particular, if η = 12 then we observe only noise, and if η ∈ {0, 1} we are in the noiseless case which has been studied last time. Especially, we achieved the fast rate lognM in the noiseless case by ¯ = h∗ . This assumption was essential for the proof assuming h∗ ∈ H which implies that h and we will see why it is necessary again in the following section. 3.2 Noise conditions The noiseless assumption is rather unrealistic, so it is natural to ask what the rate of excess risk is when the noise is present but can be controlled. Instead of the condition η ∈ {0, 1}, we can control the noise by assuming that η is uniformly bounded away from 12 , which is the motivation of the following definition. Definition (Massart’s noise condition): The noise in binary classification is said to satisfy Massart’s condition with constant γ ∈ (0, 21 ] if |η(X) − 12 | ≥ γ almost surely. Once uniform boundedness is assumed, the fast rate simply follows from last proof with appropriate modification of constants. ˆ denote the excess risk of the empirical risk minimizer h ˆ=h ˆ erm . Theorem: Let cE(h) If Massart’s noise condition is satisfied with constant γ, then ˆ ≤ log(M/δ) E(h) γn with probability at least 1 − δ. (In particular γ = 1 2 gives exactly the noiseless case.) ¯ i) = ¯ = h∗ and the Proof. Define Zi (h) = 1I(h(X 6 Yi ) − 1I(h(Xi ) = 6 Yi ). By the assumption h ˆ=h ˆ erm , definition of h ˆ = R(h) ˆ − R(h) ¯ E(h)
ˆ −R ¯ +R ¯ −R ˆ − R(h) ¯ − R(h) ˆ ˆ n (h) ˆ n (h) ˆ n (h) ˆ n (h) =R n
1X ˆ − IE[Zi (h ˆ )] . ≤ Zi (h) n (3.1) (3.2) i=1 Hence it suffices to bound the deviation of hope to apply Bernstein’s inequality. Since P i Zi from its expectation. To this end, we ¯ i )], Var[Zi (h)] ≤ IE[Zi (h)2 ] = IP[h(Xi ) 6= h(X 21 we have that for any 1 ≤ j ≤ M , n 1X Var[Zi (hj )] ≤ IP[hj (X) 6= ¯h(X)] =: σj2 . n i=1 Bernstein’s inequality implies that n 1 X  nt2
δ IP (Zi (hj ) − IE[Zi (hj )]) > t ≤ exp − 2 2 =: . n M 2σj + 3 t i=1 Applying a union bound over 1 ≤ j ≤ M and taking s 2σj2 log(M/δ) 2 log(M/δ)
t = t0 (j) := max , , n 3n we get that n 1X (Zi (hj ) − IE[Zi (hj )]) ≤ t0 (j) n (3.3) i=1 for all 1 ≤ j ≤ M with probability at least 1 − δ. ˆ = hˆ . It follows from (3.2) and (3.3) that with probability at least 1 − δ, Suppose h j ˆ ≤ t0 (j). ˆ E(h) (Note that so far the proof is exactly the same as the noiseless case.) Since |η(X) − 12 | ≥ γ ¯ = h∗ , a.s. and h ˆ = IE[|2η(X) − 1|1I(h(X) ˆ ¯ 6= h∗ (X))] ≥ 2γIP[hˆj (X) 6= h(X)] E(h) = 2γσˆj2 . Therefore, ˆ ≤ max E(h) s ˆ log(M/δ) 2 log(M/δ)
E(h) , , γn 3n (3.4) so we conclude that with probability at least 1 − δ, ˆ ≤ log(M/δ) . E(h) γn ¯ = h∗ was used twice in the proof. First it enables us to ignore The assumption that h the approximation error and only study the stochastic error. More importantly, it makes the excess risk appear on the right-hand side of (3.4) so that we can rearrange the excess risk to get the fast rate. Massart’s noise condition is still somewhat strong because it assumes uniform boundedness of η from 12 . Instead, we can allow η to be close to 12 but only with small probability, and this is the content of next definition. 22 Definition (Tsybakov’s noise condition or Mammen-Tsybakov noise condition): The noise in binary classification is said to satisfy Tsybakov’s condition if there exists α ∈ (0, 1), C0 > 0 and t0 ∈ (0, 12 ] such that α 1 IP[|η(X) − | ≤ t] ≤ C0 t 1−α 2 for all t ∈ [0, t0 ]. α In particular, as α → 1, t 1−α → 0α, so this recovers Massart’s condition with γ = t0 and we have the fast rate. As α → 0, t 1−α → 1, so the condition is void and we have the slow rate. In between, it is natural to expect fast rate (meaning faster than slow rate) whose order depends on α. We will see that this is indeed the case. Lemma: Under Tsybakov’s noise condition with constants α, C0 and t0 , we have IP[h(X) 6= h∗ (X)] ≤ CE(h)α for any classifier h where C = C(α, C0 , t0 ) is a constant. Proof. We have E(h) = IE[|2η(X) − 1|1I(h(X) 6= h∗ (X))] 1 ≥ IE[|2η(X) − 1|1I(|η(X) − | > t)1I(h(X) 6= h∗ (X))] 2 1 ≥ 2tIP[|η(X) − | > t, h(X) 6= h∗ (X)] 2 1 ≥ 2tIP[h(X) 6= h∗ (X)] − 2tIP[|η(X) − | ≤ t] 2 1 ∗ 1−α ≥ 2tIP[h(X) 6= h (X)] − 2C0 t 1−α where Tsybakov’s condition was used in the last step. Take t = cIP[h(X) 6= h∗ (X)] α for some positive c = c(α, C0 , t0 ) to be chosen later. We assume that c ≤ t0 to guarantee that t ∈ [0, t0 ]. Since α ∈ (0, 1), 1 E(h) ≥ 2cIP[h(X) 6= h∗ (X)]1/α − 2C0 c 1−α IP[h(X) 6= h∗ (X)]1/α ≥ cIP[h(X) 6= h∗ (X)]1/α by selecting c sufficiently small depending on α and C0 . Therefore IP[h(X) 6= h∗ (X)] ≤ 1 E(h)α cα and choosing C = C(α, C0 , t0 ) := c−α completes the proof. Having established the key lemma, we are ready to prove the promised fast rate under Tsybakov’s noise condition. 23 Theorem: If Tsybakov’s noise condition is satisfied with constant α, C0 and t0 , then there exists a constant C = C(α, C0 , t0 ) such that
1 ˆ ≤ C log(M/δ) 2−α E (h) n with probability at least 1 − δ. This rate of excess risk parametrized by α is indeed an interpolation of the slow (α → 0) ˆ does not and the fast rate (α → 1). Futhermore, note that the empirical risk minimizer h depend on the parameter α at all! It automatically adjusts to the noise level, which is a very nice feature of the empirical risk minimizer. Proof. The majority of last proof remains valid and we will explain the difference. After establishing that ˆ ≤ t0 (ĵ), E(h) we note that the lemma gives ˆ ¯ ˆ α. σˆj2 = IP[h(X) 6= h(X)] ≤ CE(h) It follows that ˆ ≤ max E(h) s and thus ˆ ≤ max E(h) ˆ α log(M/δ) 2 log(M/δ)
2CE(h) , n 3n  2C log n M δ
1 2−α , 2 log(M/δ)  . 3n 4. VAPNIK-CHERVONENKIS (VC) THEORY The upper bounds proved so far are meaningful only for a finite dictionary H, because if M = |H| is infinite all of the bounds we have will simply be infinity. To extend previous results to the infinite case, we essentially need the condition that only a finite number of elements in an infinite dictionary H really matter. This is the objective of the VapnikChervonenkis (VC) theory which was developed in 1971. 4.1 Empirical measure Recall from previous proofs (see (3.1) for example) that the key quantity we need to control is
ˆ n (h) − R(h) . 2 sup R h∈H Instead of the union bound which would not work in the infinite case, we seek some bound that potentially depends on n and the complexity of the set H. One approach is to consider some metric structure on H and hope that if two elements in H are close, then the quantity evaluated at these two elements are also close. On the other hand, the VC theory is more combinatorial and does not involve any metric space structure as we will see. 24 By definition n
1X 1I(h(Xi ) = R̂n (h) − R(h) = 6 Yi ) − IE[1I(h(Xi ) 6= Yi )] . n i=1 Let Z = (X, Y ) and Zi = (Xi , Yi ), and let A denote the class of measurable sets in the sample space X × {0, 1}. For a classifier h, define Ah ∈ A by {Zi ∈ Ah } = {h(Xi ) 6= Yi }. Moreover, define measures µn and µ on A by n 1X µn (A) = 1I(Zi ∈ A) and n µ(A) = IP[Zi ∈ A] i=1 for A ∈ A. With this notation, the slow rate we proved is just r ˆ n (h) − R(h) = sup |µn (A) − µ(A)| ≤ log(2|A|/δ) . sup R 2n h∈H A∈A Since this is not accessible in the infinite case, we hope to use one of the concentration inequalities to give an upper bound. Note that µn (A) is a sum of random variables that may not be independent, so the only tool we can use now is the bounded difference inequality. If we change the value of only one zi in the function z1 , . . . , zn 7→ sup |µn (A) − µ(A)|, A∈A the value of the function will differ by at most 1/n. Hence it satisfies the bounded difference assumption with ci = 1/n for all 1 ≤ i ≤ n. Applying the bounded difference inequality, we get that r log(2/δ) sup |µn (A) − µ(A)| − IE[ sup |µn (A) − µ(A)|] ≤ 2n A∈A A∈A with probability at least 1 − δ. Note that this already precludes any fast rate (faster than n−1/2 ). To achieve fast rate, we need Talagrand inequality and localization techniques which are beyond the scope of this section. It follows that with probability at least 1 − δ, r log(2/δ) sup |µn (A) − µ(A)| ≤ IE[ sup |µn (A) − µ(A)|] + . 2n A∈A A∈A We will now focus on bounding the first term on the right-hand side. To this end, we need a technique called symmetrization, which is the subject of the next section. 4.2 Symmetrization and Rademacher complexity Symmetrization is a frequently used technique in machine learning. Let D = {Z1 , . . . , Zn } be the sample set. To employ symmetrization, we take another independent copy of the sample set D ′ = {Z1′ , . . . , Zn′ }. This sample only exists for the proof, so it is sometimes referred to as a ghost sample. Then we have µ(A) = IP[Z ∈ A] = IE[ n n i=1 i=1 1X 1X 1I(Zi′ ∈ A)] = IE[ 1I(Zi′ ∈ A)|D] = IE[µ′n (A)|D] n n 25 where µ′n := 1 n Pn ′ i=1 1I(Zi ∈ A). Thus by Jensen’s inequality,   IE[ sup |µn (A) − µ(A)|] = IE sup µn (A) − IE[µ′n (A)|D] A∈A A∈A   ≤ IE sup IE[|µn (A) − µ′n (A)| |D ] A∈A   ≤ IE sup |µn (A) − µ′n (A)| A∈A n
 1X 1I(Zi ∈ A) − 1I(Zi′ ∈ A) . = IE sup A∈A n  i=1 Since D ′ has the same distribution of D, by symmetry 1I(Zi ∈ A) − 1I(Zi′ ∈ A) has the same
distribution as σi 1I(Zi ∈ A) − 1I(Zi′ ∈ A) where σ1 , . . . , σn are i.i.d. Rad( 12 ), i.e. 1 IP[σi = 1] = IP[σi = −1] = , 2 and σi ’s are taken to be independent of both samples. Therefore, n 
 1X IE[ sup |µn (A) − µ(A)|] ≤ IE sup σi 1I(Zi ∈ A) − 1I(Zi′ ∈ A) A∈A A∈A n  ≤ 2IE sup A∈A i=1 n X 1 n  σi 1I(Zi ∈ A) . (4.5) i=1 Using symmetrization we have bounded IE[supA∈A |µn (A)−µ(A)|] by a much nicer quantity. Yet we still need an upper bound of the last quantity that depends only on the structure of A but not on the random sample {Zi }. This is achieved by taking the supremum over all zi ∈ X × {0, 1} =: Y. Definition: The Rademacher complexity of a family of sets A in a space Y is defined to be the quantity n  1X Rn (A) = sup IE sup σi 1I(zi ∈ A) . z1 ,...,zn ∈Y A∈A n  i=1 The Rademacher complexity of a set B ⊂ IRn is defined to b e n   1X σ i bi . Rn (B) = IE sup b∈B n i=1 We conclude from (4.5) and the definition that IE[ sup |µn (A) − µ(A)|] ≤ 2Rn (A). A∈A Pn In the definition of Rademacher complexity of a set, the quantity n1 i=1 σi bi measures how well a vector b ∈ B correlates with a random sign pattern {σi }. The more complex B is, the better some vector in B can replicate a sign pattern. In particular, if B is the full hypercube [−1, 1]n , then Rn (B) = 1. However, if B ⊂ [−1, 1]n contains only k-sparse 26 vectors, then Rn (B) = k/n. Hence Rn (B) is indeed a measurement of the complexity of the set B. The set of vectors to our interest in the definition of Rademacher complexity of A is T (z) := {(1I(z1 ∈ A), . . . , 1I(zn ∈ A))T , A ∈ A}. Thus the key quantity here is the cardinality of T (z), i.e., the number of sign patterns these vectors can replicate as A ranges over A. Although the cardinality of A may be infinite, the cardinality of T (z) is bounded by 2n . 27