15.097 Lecture 14: Introduction to Statistical Learning Theory

Introduction to Statistical Learning Theory MIT 15.097 Course Notes Cynthia Rudin Credit: A large part of this lecture was taken from an introduction to learning theory of Bousquet, Boucheron, Lugosi Now we are going to study, in a probabilistic framework, the properties of learning algorithms. At the beginning of the semester, I told you that it was important for our models to be “simple” in order to be able to generalize, or learn from data. I didn’t really say that precisely before, but in this lecture I will. Generalization = Data + Knowledge Finite data cannot replace knowledge. Knowledge allows you to choose a simpler set of models. Perhaps surprisingly, there is no one universal right way to measure simplicity or complexity of a set of models - simplicity is not an absolute notion. But we’ll give several precise ways to measure this. And we’ll precisely show how our ability to learn depends on the simplicity of the models. So we’ll make concrete (via proof) this philosophical argument that learning somehow needs simplicity. In classical statistics, the number of parameters in the model is the usual measure of complexity. Here we’ll use other complexity measures, namely the Growth Function and VC dimension (which is a beautiful combinatorial quantity), covering number (the one I usually use), and Rademacher average. Assumptions Training and test data are drawn iid from the same distribution. If there’s no relationship between training and test, there’s no way to learn of course. (That’s like trying to predict rain in Africa next week using data about horse-kicks in the Prussian war) so we have to make some assumption. 1 Each learning algorithm encodes specific knowledge (or a specific assumption, perhaps about what the optimal classifier must look like) and works best when this assumption is satisfied by the problem to which it is applied. Notation Input space X , output space Y = {−1, 1}, unknown distribution D on X × Y. We observe m iid pairs {(xi , yi )}m i=1 drawn iid from D. The goal is to construct a function f : X → Y that predicts y from x. We would like the true risk to be as small as possible, where the true risk is: Rtrue (f ) := P(X,Y )∼D (f (X) 6= Y ) = E(X,Y )∼D [1f (X)=Y ]. 6 Did you recognize this nice thing that comes from the definition of expectation and probability? We can flip freely between notation for probability and expectation. X PZ ∼D (Z = blah) = 1[outcome=blah] PZ ∼D (Z = outcome) = EZ∼D 1[Z=blah] . outcomes We introduce the regression function η(x) = E(X,Y )∼D (Y |X = x) and the target function (or Bayes classifier) t(x) = sign η(x). Think of the distribution D, which looks sort of like this: 2 Here’s the function η: Now take the sign of it: And that’s t: 3 The target function achieves the minimum risk over all possible measurable functions: Rtrue (t) = inf Rtrue (f ). f We denote the value Rtrue (t) by R∗ , called the Bayes Risk. Our goal is to identify this function t but since D is unknown, we cannot evaluate t at any x. The empirical risk that we can measure is: m R emp 1 X (f ) = 1[f (xi )= 6 yi ] . m i=1 Algorithm Most of the calculations don’t depend on a specific algorithm, but you can think of using regularized empirical risk minimization. fm ∈ argminf ∈F Remp (f ) + Ckf k2 for some norm. The regularization term will control the complexity of the model to prevent overfitting. The class of functions that we’re working with is F. 4 Bounds Remember, we can compute fm and Remp (fm ), but we cannot compute things like Rtrue (fm ). The algorithm chooses fm from the class of functions F. Let us call the best function in the class f ∗ , so that Rtrue (f ∗ ) = inf Rtrue (f ). f ∈F Then, I would like to know how far Rtrue (fm ) is from R∗ . How bad is the function we chose, compared to the best one, the Bayes Risk? Rtrue (fm ) − R∗ = = [Rtrue (f ∗ ) − R∗ ] + Approximation Error + [Rtrue (fm ) − Rtrue (f ∗ )] Estimation Error . The Approximation Error measures how well functions in F can approach the target (it would be zero if t ∈ F). The Estimation Error is a random quantity (it depends on data) and measures how close is fm to the best possible choice in F. Draw Approximation Error and Estimation Error Figuring out the Approximation Error is usually difficult because it requires knowledge about the target, that is, you need to know something about the distribution D. In Statistical Learning Theory, generally there is no assumption made about the target (such as its belonging to some class). This is probably the main reason why this theory is so important - it does not require any knowledge of the distribution D. Also, even if the empirical risk converges to the Bayes risk as m gets large (the algorithm is consistent), it turns out that the convergence can be arbitrarily slow if there is no assumption made about the regularity of the target. On the other hand, the rate of convergence of the Estimation Error can be computed without any such assumption. We’ll focus on the Estimation Error for this class. We would really like to understand how bad the true risk of our algorithm’s output, Rtrue (fm ), could possibly be. We want this to be as small as possible of 5 course. We’ll consider another way to look at Rtrue (fm ): Rtrue (fm ) = Remp (fm ) + [Rtrue (fm ) − Remp (fm )], (1) where remember we can measure Remp (fm ). We could upper bound the term Rtrue (fm ) − Remp (fm ), to make something like this: Rtrue (fm ) ≤ Remp (fm ) + Stuff(m, F). The “Stuff” will get more interesting as this lecture continues. A Bound for One Function f Let’s define the loss g corresponding to a function f . The loss at point (x, y) is: g(x) = 1f (x)=y 6 . Given F, define the loss class, which contains all of the loss functions coming from F. G = {g : (x, y) → 1f (x)=y : f ∈ F}. 6 So g doesn’t look at predictions f , instead it looks at whether the predictions were correct. Notice that F contains functions with range in {−1, 1} while G contains functions with range {0, 1}. There’s a bijection between F and G. You can go from an f to its g by g(x, y) = 1f (x)=y 6 . You can go from a g to its f by saying that if g(x, y) = 1 then set f (x) = −y, otherwise set f (x) = y. We’ll use the g notation whenever we’re bounding the difference between an empirical average and its mean because the notation is slightly simpler. Define this notation: P true g = E(X,Y )∼D [g(X, Y )] (true risk again) m P emp 1 X g= g(Xi , Yi ) (empirical risk again) m i=1 so that we have another way to write the true risk and empirical risk directly in terms of the loss. P emp is called the empirical measure associated to the 6 training sample. It just computes the average of a function at the training points. Remember, we are interested in the difference between the true risk and empirical risk, same thing as in the right side of (1), which we’re going to upper bound: P true gm − P emp gm . (2) (gm is the loss version of fm .) Hoeffding’s Inequality For convenience we’ll define Zi = (Xi , Yi ) and Z = (X, Y ), and probabilities will be taken with respect to Z1 ∼ D, ..., Zm ∼ D which we’ll write Z ∼ Dm . Let’s rewrite the quantity we’re interested in, for a general g this time: m P true g−P emp 1 X g = EZ∼Dm [g(Z)] − g(Zi ). m i=1 It’s a difference between an empirical mean and its expectation. By the law of large numbers we know asymptotically that the mean converges to the expectation in probability. So with probability 1, with respect to Z ∼ Dm , m 1 X lim g(Zi ) = EZ∼Dm [g(Z)]. m→∞ m i=1 So with enough data, the empirical risk is a good approximation to its true risk. There’s a quantitative version of the law of large numbers when variables are bounded: Theorem 1 (Hoeffding). Let Z1 ...Zm be m iid random variables, and h is a bounded function, h(Z) ∈ [a, b]. Then for all  > 0 we have: " #   m 1 X 2m2 PZ∼Dm h(Zi ) − EZ∼Dm [h(Z)] ≥  ≤ 2 exp − . m i=1 (b − a)2 The probability that the empirical average and expectation are far from each other is small. Let us rewrite the formula to better understand its consequences. 7 Let the right hand side be δ, so   2m2 δ = 2 exp − . (b − a)2 Then if I solve for , I get: s  = (b − a) log 2δ 2m So Hoeffding’s inequality, applied to the function g becomes:   s 2 log δ  ≤ δ. PZ∼Dm |P emp g − P true g| ≥ (b − a) 2m There’s a technique called “inversion” that we’ll use a lot. Inversion Using inversion, we get that with probability at least 1 − δ: s log 2δ emp true |P g − P g| ≤ (b − a) . 2m The expression above is “2-sided” in that there’s an absolute value on the left. This considers whether P emp g is larger than P true g or smaller than it. There’s also 1-sided versions of Hoeffding’s inequality where we look at deviations in one direction or the other, for instance here is a 1-sided version of Hoeffding’s: " #   m X 1 2m2 PZ∼Dm EZ∼Dm [h(Z)] − h(Zi ) ≥  ≤ exp − . m i=1 (b − a)2 If we again set the right side to δ and solve for , and invert, we get that with probability at least 1 − δ, s m log 1δ 1 X EZ∼Dm [h(Z)] − h(Zi ) ≤ (b − a) . m i=1 2m Here is the inverted one applied to g: with probability at least 1 − δ, s log 1δ true emp P g − P g ≤ (b − a) . 2m 8 Moving the empirical term to the right, we have that with probability at least 1 − δ, s log 1δ true emp P g ≤ P g + (b − a) . 2m Remember that g is the loss, so g(Z) = 1f (X)=Y and that way we have an upper 6 bound for the true risk, which we want to be small. This expression seems very nice, but guess what? It doesn’t apply when f (i.e., g) comes from any reasonable learning algorithm! Why not? Limitations The result above says that for each fixed function g ∈ G, there is a set S of “good” samples z1 , ..., zm , for which s log 1δ true emp P g − P g ≤ (1 − 0) 2m and this set of samples has measure PZ∼Dm [Z ∈ S] ≥ 1 − δ. However, these sets may be different for different functions g. In other words, for the sample S we actually observe, there’s no telling how many of the functions in G will actually satisfy this inequality! This figure might help you understand. Each point on the x-axis is a different function. The curve marked Rtrue (f ) is the true risk, which is a constant for each f since it involves the whole distribution (and not a sample). 9 If you give me a sample and a function f , I can calculate Remp (f ) for that sample, which gives me a dot on the plot. So, for each sample we get a different curve on the figure. For each f , Hoeffding’s inequality makes sure that most of the time, the Remp (f ) curves lie within a small distance of Rtrue (f ), though we don’t know which ones. In other words, for an observed sample, only some of the functions in F will satisfy the inequality, not all of them. But remember, our algorithms choose fm knowing the data. They generally try to minimize the regularized Remp (f ). Consider drawing a sample S, which corresponds to a curve on the figure. Our algorithm could (on purpose) meander along that curve until it chooses a fm that gives a small value of Remp . This value could be very far from Rtrue (fm ). This could definitely happen, and if there are more f ’s to choose from (if the function class is larger), then this happens more easily - uh oh! In other words, if F is large enough, one can find, somewhere along the axis, a function f for which the difference between the two curves Remp (f ) and Rtrue (f ) will be very large. 10 We don’t want this to happen! Uniform Bounds We really need to make sure our algorithm doesn’t do this - otherwise it will never generalize. That’s why we’re going to look at uniform deviations in order to upper bound (1) or (2): Rtrue (fm ) − Remp (fm ) ≤ sup(Rtrue (f ) − Remp (f )) f ∈F where we look at the worst deviation over all functions in the class. Let us construct a first uniform bound, using Hoeffding’s inequality and the union bound. Define: Cj = {z1 , ..., zm : P true gj − P emp gj ≥ }. This set contains all the “bad” samples, those for which the bound fails for function gj . From Hoeffding’s Inequality, for each j, PZ∼Dm [Z ∈ Cj ] ≤ δ. Consider two functions g1 and g2 . Say we want to measure how many samples are “bad” for either one of these functions or the other. We’re going to use the union bound to do this, which says: P[C1 ∪ C2 ] ≤ P[C1 ] + P[C2 ] ≤ 2δ, the probability that we hit a bad sample for either g1 or g2 is ≤ prob to hit a bad sample for C1 + prob to hit a bad sample for C2 . More generally, the union bound is: P[C1 ∪ ... ∪ CN ] ≤ N X j=1 11 P[Cj ] ≤ N δ So this is a bound on the probability that our chosen sample will be bad for any of the functions g1 , ..., gN . So we get: PZ∼Dm [∃g ∈ {g1 , ..., gN } : P true g − P emp g ≥ ] N X ≤ PZ∼Dm [P true gj − P emp gj ≥ ] j=1 ≤ N X exp(−2m2 ) Where did this come from? j=1 = N exp(−2m2 ). If we define a new δ so we can invert: δ := N exp(−2m2 ) and solve for , we get: s log N + log 1δ = . 2m Plugging that in and inverting, we find that with probability at least 1 − δ, s log N + log 1δ true emp . ∀g ∈ {g1 , ..., gN } : P g − P g ≤ 2m Changing g’s back to f ’s, we’ve proved the following: Theorem. (Hoeffding + Union Bound) For F = {f1 ...fN }, for all δ > 0 with probability at least 1 − δ, s log N + log 1δ true emp ∀f ∈ F, R (f ) ≤ R (f ) + . 2m Just to recap the reason why this bound is better than the last one, if we know our algorithm only picks functions from a finite function class F, we now have a bound that can be applied to fm , even though it depends on the data. Note the main difference with plain Hoeffding’s inequality is the extra log N term on the right hand side. This term is the one saying we want N bounds to hold simultaneously. 12 Estimation Error Let’s say we’re doing empirical risk minimization, that is, fm is the minimizer of the empirical risk Remp . We can use the theorem above (combined with (1)) to get an upper bound on the Estimation Error. Start with this: Rtrue (fm ) = Rtrue (fm ) − Rtrue (f ∗ ) + Rtrue (f ∗ ) Then we’ll use the fact that Remp (f ∗ ) − Remp (fm ) ≥ 0. Why is that? We’ll add that to the expression above: Rtrue (fm ) ≤ = ≤ ≤ [Remp (f ∗ ) − Remp (fm )] + Rtrue (fm ) − Rtrue (f ∗ ) + Rtrue (f ∗ ) Remp (f ∗ ) − Rtrue (f ∗ ) − Remp (fm ) + Rtrue (fm ) + Rtrue (f ∗ ) |Rtrue (f ∗ ) − Remp (f ∗ )| + |Rtrue (fm ) − Remp (fm )| + Rtrue (f ∗ ) 2 sup |Rtrue (f ) − Remp (f )| + Rtrue (f ∗ ). f ∈F We could use a 2-sided version of the theorem (with an extra factor of 2 somewhere) that with probability 1 − δ, that first term is bounded by the square root term in the theorem. Specifically, we know that with probability 1 − δ: s log N + log 2δ true + Rtrue (f ∗ ). R (fm ) ≤ 2 2m Actually, if you think about it, both terms in the right hand side depend on the size of the class F. If this size increases, the first term will increase, and the second term will decrease. Why? Summary and Perspective • Generalization requires knowledge (like restricting f to lie in a restricted class F). • The error bounds are valid with respect to the repeated sampling of training sets. 13 • For a fixed function f , for most of the samples, √ Rtrue (f ) − Remp (f ) ≈ 1/ m. • For most of the samples if the function class if finite, |F| = N , p sup[Rtrue (g) − Remp (g)] ≈ log N/m. g ∈G The extra term is because we choose fm in a way that changes with the data. • We have the Hoeffding + Union Bound Theorem above, which bounds the worst difference between empirical risk and true risk among functions in the class. There are several things that could be improved. For instance Hoeffding’s inequality only uses the boundedness of the functions, not their variance, which is something we won’t deal with here. The supremum over F of Rtrue (f ) − Remp (f ) is not necessarily what the algorithm would choose, so the upper bound could be loose. The union bound is in general loose, because it is as bad as if all the fj (Z)’s are independent. Infinite Case: VC Dimension Here we’ll show how to extend the previous results to the case where the class F is infinite. We’ll start with a simple refinement of the union bound that allows to extend the previous results to the (countably) infinite case. Recall that by Hoeffding’s inequality for a single function g, for each δ > 0, where possibly we could choose δ depending on g, which we write δ(g), we have: s   1 log δ(g)  ≤ δ(g). PZ∼Dm P true g − P emp g ≥ 2m Hence if we have a countable set G, the union bound gives: s   1 X log δ(g) true emp   m ≤ δ(g). PZ∼D ∃g ∈ G : P g − P g ≥ 2m g∈G 14 If we choose the δ(g)’s P so that they add up to a constant total value δ, that is, δ(g) = δ p(g) where g∈G p(g) = 1, then the right hand side is just δ and we get the following with inversion: with probability at least 1 − δ, s 1 log p(g) + log 1δ true emp ∀g ∈ G , P g ≤ P g + . 2m If G is finite with size N , and we take a uniform p(g) = as before. 1 N, we get the log N term General Case When the set G is uncountable, the previous approach doesn’t work because p(g) is a density, so it’s 0 for a given g and the bound will be vacuous. We’ll switch back to the original class F rather than the loss class for now. The general idea is to look at the function class’s behavior on the sample. Given z1 , ..., zm , we consider Fz1 ,...,zm = {f (z1 ), ..., f (zm ) : f ∈ F}. Fz1 ,...,zm is the set of ways the data z1 , ..., zm are classified by functions from F. Since the functions f can only take two values, this set will always be finite, no matter how big F is. Definition (Growth Function) The growth function is the maximum number of ways into which m points can be classified by the function class: SF (m) = sup |Fz1 ,...,zm |. (z1 ,...,zm ) Intuition for Growth Function and Example of Halfplanes We defined the growth function in terms of the initial class F but we can do the same with the loss class G since there’s a 1-1 mapping, so we’ll get SG (m) = SF (m). This growth function can be used as a measure of the ‘size’ of a class of functions as demonstrated by the following result: 15 Theorem-GrowthFunction (Vapnik-Chervonenkis) For any δ > 0, with probability at least 1 − δ with respect to a random draw of the data, s log SF (2m) + log 4δ true emp ∀f ∈ F R (f ) ≤ R (f ) + 2 2 m (proof soon). This bound shows nicely that simplicity implies generalization. The simpler the function class, the better the guarantee that Rtrue will be small. In the finite case where |F| = N (we have N possible classifiers), we have SF (m) ≤ N (at worst we use up all the classifiers when we’re computing the growth function). So this bound is always better than the one we had before (except for the constants). But we need to figure out how to compute SF (m). We’ll do that using VC dimension. VC dimension Since f ∈ {−1, 1}, it is clear that SF (m) ≤ 2m . If SF (m) = 2m there is a data set of size m points such that F can generate any classification on these points (we say F shatters the set). The VC dimension of a class F is the size of the largest set that it can shatter. Definition. (VC dimension) The VC dimension of a class F is the largest m such that SF (m) = 2m . What is the VC dimension of halfplanes in 2 dimensions? Can you guess the VC dimension of halfplanes in d dimensions? In the example, the number of parameters needed to define the half space in Rd is the number of dimensions, d. So a natural question to ask is whether the VC dimension is related to the number of parameters of the function class. In other 16 words, VC dimension is supposed to measure complexity of a function class does it just basically measure the number of parameters? Is the VC dimension always close to the number of parameters? So how can VC dimension help us compute the growth function? Well, if a class of functions has VC dim h, then we know that we can shatter m examples when m ≤ h, and in that case, SF (m) = 2m . If m > h, then we know we can’t shatter the points, so SF (m) < 2m otherwise. This doesn’t seem very helpful perhaps, but actually an intriguing phenomenon occurs for m ≥ h, shown below. The plot below shows for m ≥ h (where we can’t shatter) the number of ways we can classify - that’s the growth function. The growth function which is exponential up until the VC dimension, becomes polynomial afterwards! Typical behavior of the log growth function. This is captured by the following lemma. Lemma. (Vapnik and Chervonenkis, Sauer, Shelah) Let F be a class of 17 functions with finite VC dimension h. Then for all m ∈ N, SF (m) ≤ h   X m i=0 i Intuition and for all m ≥ h SF (m) ≤  em h . h Using this lemma for m ≥ h along with Theorem-GrowthFunction, we get: Theorem VC-Bound. If F has VC dim h, and for m ≥ h, with prob. at least 1 − δ, s 4 h log 2em emp true h + log δ . ∀f ∈ F R (f ) ≤ R (f ) + 2 2 m What is important to remember from this result is that the difference between the true and empirical risk is at most of order r h log m . m Before we used VC dim, the bound was infinite, i.e., vacuous! Recap Why is Theorem VC-Bound important? It shows that limiting the complexity of the class of functions leads to better generalization. An interpretation of VC dim and growth functions is that they measure the “effective” size of the class, that is, the size of the projection of the class onto finite samples. This measure doesn’t just count the number of functions in the class, but depends on the geometry of the class, that is, the projections onto the possible samples. Also since the VC dimension is finite, our bound shows that the empirical risk will converge uniformly over the class F to the true risk. Back to Margins How is it that SVM’s limit the complexity? Well, the choice of kernel controls the complexity. But also the margin itself controls complexity. There is a set of 18 linear classifiers called “gap-tolerant classifiers” that I won’t define precisely (it gets complicated) that require a margin of at least ∆ between points of the two different classes. The points are also forced to live inside a sphere of diameter D. So the class of functions is fairly limited, since they not only need to separate the points with a margin of ∆, but also we aren’t allowed to move the points outside of the sphere. “Theorem” VC-Margin. (Vapnik) For data in Rd , the VC dimension h of (linear) gap-tolerant classifiers classifiers with gap ∆ belong to a sphere of diameter D, is bounded by the inequality:  2   D h ≤ min , d + 1. ∆2 So the VC dimension (of the set of functions that separate points with some margin) is less than 1/margin. If we have a large margin, we necessarily have a small VC-dimension. What does this say about halfspaces in Rd ? (Think about the VC dimension example we did earlier.) Symmetrization We’ll do the proof of Theorem-GrowthFunction. The key ingredient is the symmetrization lemma. We’ll use what’s called a “ghost sample” which is an extra 0 (virtual) data set Z10 , ..., Zm . Denote P 0emp the corresponding empirical measure. (Lemma-Symmetrization) For any t > 0, such that mt2 ≥ 2,     true emp 0emp emp PZ∼Dm sup(P − P )g ≥ t ≤ 2PZ∼Dm ,Z0 ∼Dm sup(P − P )g ≥ t/2 . g ∈G g ∈G That is, if we can bound the difference between the behavior on one sample versus another, it gives us a bound on the behavior of a sample with respect to the true risk. Proof. Let gm be the function achieving the supremum in the lhs term, which depends on Z1 , ...Zm . Think about the event that: (P true − P emp )gm ≥ t (the 19 sample’s loss is far from the true loss) and (P true − P 0emp )gm < t/2 (the ghost sample’s loss is close to the true loss). If this event were true, it sort of means that things didn’t generalize well for Z1 , ..., Zm but that they did generalize well for 0 Z10 , ..., Zm . If we can show that this event happens rarely, then the ghost sample can help us. Again, the event that we want to happen rarely is (P true −P emp )gm ≥ t and (P true − P 0emp )gm < t/2. 1(P true −P emp )gm ≥t 1(P true −P 0emp )gm −t/2 ≤ 1(P true −P emp +P 0emp −P true )gm >t−t/2=t/2 = 1(−P emp +P 0emp )gm >t/2 . The inequality came from the fact that the event on the second last line ((P true − P emp )gm ≥ t and (P 0emp − P true )gm > −t/2) implies the event on the last line ((P true − P emp + P 0emp − P true )gm > t − t/2), so the event on the last line could happen more often. Taking expectations with respect to the second sample, and using the trick to change expectation into probability, 1(P true −P emp )gm ≥t PZ0 ∼Dm [(P true − P 0emp )gm < t/2] ≤ PZ0 ∼Dm [(P 0emp − P emp )gm > t/2]. (3) Do you remember Chebyshev’s Inequality? It says P[|X − EX| ≥ t] ≤ VarX/t2 . We’ll apply it now, to that second term on the left, inverted: 4Vargm PZ0 ∼Dm [(P true − P 0emp )gm ≥ t/2] ≤ . mt2 I hope you’ll believe me when I say that any random variable that has range [0, 1] has variance less than or equal to 1/4. Hence, 1 PZ0 ∼Dm [(P true − P 0emp )gm ≥ t/2] ≤ . mt2 Inverting back, so that it looks like the second term on the left of (3) again: 1 . PZ0 ∼Dm [(P true − P 0emp )gm < t/2] ≥ 1 − mt2 Multiplying both sides by 1(P true −P emp )gm ≥t I get back to the left of (3):   1 1(P true −P emp )gm ≥t 1 − ≤ 1(P true −P emp )gm ≥t PZ0 ∼Dm [(P true − P 0emp )gm < t/2] 2 mt ≤ PZ0 ∼Dm [(P 0emp − P emp )gm > t/2] from (3). 20 Taking the expectation with respect to the first sample, the term EZ∼Dm 1(P true −P emp )gm ≥t becomes PZ∼Dm [(P true − P emp )gm ≥ t]. And now we get:   1 ≤ PZ0 ∼Dm Z∼Dm [(P 0emp − P emp )gm > t/2] PZ∼Dm [(P true − P emp )gm ≥ t] 1 − 2 mt   1 PZ∼Dm [(P true − P emp )gm ≥ t] ≤ PZ0 ∼Dm Z∼Dm [(P 0emp − P emp )gm > t/2]. 1 1 − mt2 Only one more step, which uses our assumption mt2 ≥ 2. mt2 ≥ 2 1 1 ≤ mt2 2 1 1 1 ≥ 1 − = 1− 2 2 mt2  1 ≤ 2 1 − mt1 2 Plug: PZ∼Dm [(P true − P emp )gm ≥ t] ≤ 2PZ0 ∼Dm Z∼Dm [(P 0emp − P emp )gm > t/2]   ≤ 2PZ∼Dm ,Z0 ∼Dm sup(P 0emp − P emp )g > t/2 . g∈G We have an upper bound by changing the strict inequality “>” to a “≥.” Then the result is the same as the statement of the lemma.  Remember, we’re still in the middle of proving Theorem-GrowthFunction. The symmetrization is just a step in that proof. This symmetrization lemma allows us to replace the expectation P true g by an empirical average over the ghost sample. As a result, the proof will only depends on the projection of the class G on the double sample GZ1 ...Zm ,Z10 ...Zm0 , which contains finitely many different vectors. In other words, an element of this set is just the vector [g(x1 ), ..., g(xm )], and there are finitely many possibilities for vectors like this. So we can use the union bound that we used for the finite 21 case. The other ingredient that we need to prove Theorem-GrowthFunction is this one: 2 PZ∼Dm Z0 ∼Dm [P emp g − P 0emp g ≥ t] ≤ 2e−mt /2 . (4) This one comes itself from a mix of Hoeffding’s with the union bound: PZ∼Dm Z0 ∼Dm [P emp g − P 0emp g ≥ t] = PZ∼Dm Z0 ∼Dm [P emp g − P true g + P true g − P 0emp g ≥ t] ≤ PZ∼Dm [P emp g − P true g ≥ t/2] + PZ0 ∼Dm [P true g − P 0emp g ≥ t/2] 2 2 ≤ e−2m(t/2) + e−2m(t/2) 2 = 2e−mt /2 . We just have to put the pieces together now: PZ∼Dm [sup(P true − P emp )g ≥ t] g ∈G ≤ 2PZ∼Dm Z0 ∼Dm [sup(P 0emp − P emp )g ≥ t/2] Lemma-Symmetrization g ∈G = 2PZ∼Dm Z0 ∼Dm [ (P 0emp − P emp )g ≥ t/2] sup (restrict to data) g∈GZ1 ,...,Zm ,Z 0 ,...,Zm 0 1 X ≤ 2 PZ∼Dm Z0 ∼Dm [(P 0emp − P emp )g ≥ t/2] (union bound) g ∈GZ1 ,...,Zm ,Z 0 ,...,Zm 0 1 2 X ≤ 2 2e−m(t/2) /2 g∈GZ1 ,...,Zm ,Z 0 ,...,Zm 0 1 2 = 4e−mt X /8 1 g∈GZ1 ,...,Zm ,Z 0 ,...,Zm 0 1 −mt2 /8 = 4SG (2m) e . And using inversion, 2 PZ∼Dm [sup(P true − P emp )g ≤ t] ≥ 1 − 4SG (2m) e−mt g ∈G 2 Letting δ = 4SG (2m) e−mt /8 , solving for t yields: r 8 4SG (2m) t= log m δ 22 /8 . Plug:  s PZ∼Dm sup(P true − P emp )g ≤ 2 2 g ∈G log SG (2m) + log m  4 δ ≥ 1 − δ. So, with probability at least 1 − δ, s ∀g ∈ G (P true −P emp )g ≤ 2 log SG (2m) + log 4δ 2 . m That’s the result of Theorem-GrowthFunction.  Other kinds of capacity measures One important aspect of VC dimension is that it doesn’t depend on D, so it is a distribution independent quantity. The growth function is also distribution independent. That’s nice in some ways, because it allows us to get bounds that don’t depend on the problem at hand: the same bound holds for any distribution. Although this may seem like an advantage, it could also be a drawback since, as a result, the bound may be loose for most distributions. It turns out there are several different quantities that are distribution dependent, which we can use in generalization bounds. VC-entropy One quantity is called the (annealed) VC entropy. Recall the notation |Gz1 ,...,zm | which is the number of ways we can correctly/incorrectly classify z1 , ..., zm . VC-entropyG (m) := log EZ∼Dm [|GZ1 ,...,Zm |]. If the VC-entropy is large, it means that a lot of the time, there are a lot of different ways to classify m data points. So the capacity of the set of functions is somehow large. There’s a bound for the VC-entropy that’s very similar to the one for Theorem-GrowthFunction (which I won’t go into here). How does the VC-entropy relate to the Growth Function? 23 Covering Number Another quantity is called the covering number. Covering numbers can be defined in several different ways, but we’ll just define one of them. Let’s start by endowing the function class G with the following (random) metric: m 1 X dm (g, g ) = 1[g(Zi )=g 6 0 (Zi )] , m i=1 0 the fraction of times they disagree on the (random) sample. Also denote B(gj , ) as ball of radius  around gj , using the metric dm . In other words, B(gj , ) contains all the functions in G that are within distance  of gj according to our metric. We say that a set g1 , ..., gN covers G at radius  if: G⊂ N [ B(gj , ) j =1 that is, if G is contained within the collection of balls centered at the gj ’s. We then define the covering number. Definition. The covering number of G at radius  with respect to dm , denoted by N (G, , m) is the minimum size of a cover of radius . Illustration (Remember of course that since there’s a bijection between F and G that N (G, , m) = N (F, , m)). If the covering number is finite, it means we can approximately represent G by a finite set of functions that cover G. This allows us to use the (finite) union bound. Basically, the proof technique involves showing that things don’t change too much within an  ball, so we can characterize the whole ball of functions by its center, then union bound over the centers. This kind of proof technique is my favorite for creating generalization bounds - just because to me it seems more straightforward (of course this is highly subjective). 24 A typical result (stated without proof) is: Theorem-Covering. For any t > 0, 2 PZ∼Dm [∃f ∈ F : Rtrue (f ) ≥ Remp (f ) + t] ≤ 8EZ∼Dm [N (F, t, m)]e−mt /128 . We can relate the covering number to the VC dimension. Lemma (Haussler). Let F be a class of VC dimension h. Then for all  > 0, all m, and any sample, N (F, , m) ≤ Ch(4e)h h . (where C is a constant). One thing about this result is that the upper bound does not depend on the sample size m. Probably it is a loose upper bound, but it’s nice to be able to get this independent of m! Rademacher Averages Another way to measure complexity is to see how well functions from the class F can classify random noise. So if I arbitrarily start flipping the labels, how well can functions from my class fit those arbitrary labels. If the functions from F can fit those arbitrary labels really well, then F must have high complexity. That’s the intuition behind the Rademacher complexity measure that we’re going to introduce. I’m going to introduce some notation, m 1 X Rm g := σi g(Zi ) m i=1 where the σi ’s are independent {+1, −1}-valued random variables with probability 1/2 of taking either value. You can think of them as random coin flips. Denote Eσ the expectation taken with respect to the σi ’s. Definition. (Rademacher Averages) For a class G of functions, the Rademacher average is defined as: R(G) := Eσ,Z sup Rm g. g∈G 25 In other words, for each set of flips of the coin, you consider them as labels for your data, and find a function from G that matches them the best. If you can match a lot of random coin flips really well using functions from G, then G has high complexity. Here’s a bound involving Rademacher averages: Theorem-RademacherBound. With probability at least 1 − δ, s log 2δ true emp ∀g ∈ G, R (g) ≤ R (g) + 2R(G) + . 2m The proof of this requires a powerful tool called a concentration inequality. Actually, Hoeffding’s inequality is a concentration inequality, so you’ve seen one already. Concentration inequalities say that as m increases, the empirical average is concentrated around the expectation. McDiarmid’s concentration inequality is my favorite, and it generalizes Hoeffding’s in that applies to functions that depend on m iid random variables: Theorem. (McDiarmid’s Inequality) Assume for all i = 1, ..., m sup z1 ,...,zm ,zi0 |F (z1 , ..., zi , ..., zm ) − F (z1 , ..., zi0 , ..., zm )| ≤ c then for all  > 0, 22 P[|F − E[F ]| ≥ ] ≤ 2 exp − 2 mc   . This is a Hoeffding-like inequality that holds for any function of m variables, as long as replacing one of those variables by another one won’t allow the function to change too much. Proof of Theorem-RademacherBound We’ll follow two steps: • concentration to relate supg∈G (P true g − P emp g) to its expectation, 26 • symmetrization to relate the expectation to the Rademacher average. We want to use McDiarmid’s inequality on supg∈G (P true g − P emp g), so we’ll need to show that if we modify one training example, it doesn’t change too much. Denote P emp,i as the empirical measure obtained by replacing zi by zi0 of the sample. The following holds: | sup(P true g − P emp g ) − sup(P true g − P emp,i g)| ≤ sup |P emp,i g − P emp g|. g ∈G g ∈G (5) g ∈G This isn’t too hard to check. For instance, let’s say that the first term is larger than the second so we can remove the absolute value. Then say g ∗ achieves supg∈G (P true g − P emp g). Then sup(P true g − P emp g) − sup(P true g − P emp,i g ) g ∈G = (P g ∈G true ∗ emp ∗ true ∗ emp ∗ g −P g ) − sup(P true g − P emp,i g) g ∈G true ∗ ≤ (P g − P g ) − (P g − P emp,i g ∗ ) = P emp,i g ∗ − P emp g ∗ ≤ sup(P emp,i g − P emp g) g ∈G And if the second term is larger than the first, we do an identical calculation. So (5) holds. P P emp,i g−P emp g is a difference of two averages, since remember P emp g is m1 m i=1 g(Zi ) emp,i and P g is the same thing except that the ith term got replaced with g(Zi0 ). 1 1 |g(Zi0 ) − g(Zi )| ≤ m m where we used that g ∈ {0, 1} for the last inequality. |P emp,i g − P emp g| = This means from (5) that we have | sup(P true g − P emp g) − sup(P true g − P emp,i g)| ≤ g ∈G g ∈G 1 , m (6) the function F = supg∈G (P true g − P emp g) can’t change more than m1 when we fiddle with one of the Zi ’s. This means we can directly apply McDiarmid’s inequality to it with c = m1 .   2 2 PZ∼Dm [| sup(P true g−P emp g)−EZ∼Dm [sup(P true g−P emp g)]| ≥ ] ≤ 2 exp − 1 . m m2 g ∈G g ∈G 27 That’s the first part of the proof (the concentration part). Now for symmetrization, which we’ll use to prove that the expected difference between the true and empirical risks is bounded by twice the Rademacher average. Lemma. EZ∼Dm sup[P true g − P emp g] ≤ 2Eσ,Z sup Rm g = 2R(G) g ∈G g ∈G To prove it, we introduce a ghost sample and it’s corresponding measure P 0emp . We’re going to use that EZ∼Dm P 0emp g = P true g in the second line below. EZ∼Dm sup[P true g − P emp g] g ∈G = EZ∼Dm sup[EZ0 ∼Dm [P 0emp g − P emp g]] g ∈G ≤ EZ∼Dm Z0 ∼Dm sup[P 0emp g − P emp g] (uses Jensen’s Inequality, sup is convex) g∈G # " m X 1 = EZ,Z0 sup (g(Zi0 ) − g(Zi )) g ∈G m i=1 " # m X 1 = Eσ,Z,Z0 sup σi (g(Zi0 ) − g(Zi )) Why? g ∈G m i=1 " # " # m m X 1 X 1 σi g(Zi0 ) + Eσ,Z sup ≤ Eσ,Z sup −σi g(Zi ) g ∈G m i=1 g ∈G m i=1 = 2Eσ,Z sup Rm g. g∈G The last step uses that σi g(Zi ) and −σi g(Zi ) have the same distribution.  Let’s put the two parts of the proof of Theorem-RademacherBound together. The first part said:   2 2 PZ∼Dm [| sup(P true g−P emp g)−EZ∼Dm [sup(P true g −P emp g)]| ≥ ] ≤ 2 exp − . 1/m g ∈G g ∈G The second part said: EZ∼Dm sup[P true g − P emp g ] ≤ 2Eσ,Z sup Rm g = 2R(G ) g ∈G g ∈G 28 Let’s fiddle with the first part. First, let  2 2 δ := 2 exp − 1/m s  so that = log 2δ 2m So the first part looks like    PZ∼Dm  sup(P true g − P emp g) − EZ∼Dm sup(P true g − P emp g )] ≥ g ∈G s g ∈G  2 δ log 2m ≤ δ. Using inversion, with probability at least 1 − δ, sup(P true g−P emp g ∈G  g) − EZ∼Dm sup(P true g−P emp s  g) g ∈G ≤ log 2δ . 2m I can remove the absolute value and the left hand side only gets smaller. Then, s   log 2δ true emp true emp sup(P g − P g) ≤ EZ∼Dm sup(P g − P g)] + . 2m g ∈G g ∈G Using the second part, s sup(P true g−P emp g) ≤ 2R(G ) + g ∈G log 2δ . 2m Writing it all together, with probability at least 1 − δ, for all g ∈ G, s log 2δ true emp P g ≤ P g + 2R(G) + , 2m and that’s the statement of Theorem-RademacherBound. Relating the Rademacher Complexity of the Loss Class and the Initial Class Theorem RademacherBound is nice, but it only applies to the class G, and we also care about class F , so we need to relate the Rademacher average of G to 29 that of class F. We do this as follows, using the fact that σi and Yi σi have the same distribution. " R(G) = Eσ,Z m 1 X sup σi 1[f (Xi )=Y 6 i] g ∈G m i=1 # " # m X 1 1 = Eσ,Z sup σi (1 − Yi f (Xi )) Why? 2 g ∈G m i=1 " # m 1 1 X 1 = Eσ,Z sup σi Yi f (Xi ) = R(F ). Why? 2 2 g ∈G m i=1 Ok so we’ve related the two classes’ Rademacher averages. So, with probability at least 1 − δ, s log 2δ true emp ∀f ∈ F, R f ≤ R f + R(F) + . 2m Computing the Rademacher Averages Let’s assess the difficulty of actually computing Rademacher averages. Start here: # " m X 1 1 1 σi f (Xi ) R(F) = Eσ,Z sup 2 2 f ∈F m i=1 " # m X 1 1 1 − σi f (Xi ) = + Eσ,Z sup − 2 2 f ∈F m i=1 " # m 1 1 X 1 − σi f (Xi ) = − Eσ,Z inf f ∈F m 2 2 i=1 " # m 1 1 X = − Eσ,Z inf 1f (Xi )=σ 6 i . (1/2 comes through the inf) f ∈F m 2 i=1 Look closely at that last expression. The thing on the inside says to find the empirical risk minimizer, where the labels are the σi ’s. This expression shows that computing R(F) is not any harder than computing the expected empirical 30 risk minimizer over random labels. So we could design a hypothetical procedure, where we generate the σi ’s randomly, and minimize the empirical error in G with respect to the labels σi . (Of course we technically also have to do this over the possible Xi ’s, but there are some ways to get around this that I won’t go into here.) It’s also true that r h log em h R(F) ≤ 2 m So we could technically use the Rademacher complexity bound to get another VC-bound. So we’re done! We showed formally that limiting the complexity leads to better generalization. We gave several complexity measures for a set of models (Growth Function, VC-dimension, VC-entropy, Covering Number, Rademacher averages). 31