15-859(B) Machine Learning Theory 02/01/10
VC-dimension II
* Sauer's lemma
* Proving the main result
========================================================================
Plan for today: two very nice proofs.
(1) Sauer's lemma: the number of different ways of labeling m points
using functions in class C is at most (m <=d), where d=VCdim(C).
(2) the uniform convergence bound where we (roughly) replace |C| with
C[2m].
Given a concept class C and set of examples S, let C[S] be the set of
possible labelings of S using concepts in C. C[m] = max_{S:|S|=m} |C[S]|.
SAUER'S LEMMA: C[m] <= (m <=d), where d = VCdim(C) and we define
(m <=d) = # ways of choosing d or fewer items out of m. I.e.,
(m <=d) = (m 0) + (m 1) + (m 2) + ... + (m d).
Note: (m <=d) = (m-1 <=d) + (m-1 <=d-1).
Proof: to choose d or fewer out of m you either choose the
first element and then d-1 or fewer out of the remaining m-1 or you
don't, and then choose d or fewer out of the remaining m.
PROOF OF SAUER'S LEMMA: Let's say we have a set S of m examples. We
want to bound |C[S]|.
Pick some x in S. So, we know that C[S - {x}] has at most (m-1 <=d)
distinct partitions by induction.
How are there more splittings of S are there than of S - {x}? As in
the special case we examined last class, |C[S]| - |C[S - {x}]| = the
number of pairs in C[S] that differ only on x, since these are the
ones that collapse when you remove x.
For each pair, let's focus on the one that labels x positive.
Let C' = {c in C[S] that label x positive for which there is another
concept in C[S] that is identical to c except it labels x negative}.
(Remember, these are concepts that are only defined on S)
Claim: VCDIM(C) >= VCDIM(C') + 1.
Proof: Pick set S' of pts in S that are shattered by C'. S' doesn't
include x since all functions in C' label x positive. Now, S' U {x}
is shattered by C because of how C' was defined.
This means VCDIM(C') <= d-1 and we are done. QED
---------------------------------------------------------------------
THEOREM 1: For any class C, distrib D, if we draw a sample S from D of
size:
m > (2/epsilon)[log_2(2C[2m]) + log_2(1/delta)],
then with prob 1-delta, all h with err_D(h)>epsilon have err_S(h)>0.
Proof: Given set S of m examples, define A = event there exists h in
C with err_D(h)>epsilon but err_S(h)=0.
We want to show Pr[A] is low.
Now, consider drawing *two* sets S, S' of m examples each. Let A be
defined as before. Define B = event that there exists
a concept h in C with err_S(h)=0 but err_{S'}(h) >= epsilon/2.
Claim: Pr[A]/2 <= Pr[B]. So, if Pr[B] is low then Pr[A] is low.
Pf: Pr[B] >= Pr[B|A]Pr[A]. Conditioned on event A (pick some such
h), Pr[B|A] > 1/2 by Chernoff since m > 8/epsilon. (the bad h has
true error > epsilon so unlikely it will have observed error <
epsilon/2). This means that Pr[B] >= Pr[A]/2. QED
Now, show Pr[B] is low. (Note: no longer need to talk about "bad"
hyps. Reason: for really good hyps, unlikely to satisfy the second part)
To do this, consider related event: draw S = {x1, x2, ..., xm} and S'
= {x1', x2', ..., xm'} and now create sets T, T' using the following
procedure Swap:
For each i, flip a fair coin:
- If heads, put xi in T and put xi' in T'.
- If tails, put xi' in T and put xi in T'.
Claim: (T,T') has the same distribution as (S,S'). So, equivalent to
bound the probability of B_T = event that exists concept h in C with
err_T(h)=0 but err_{T'}(h) >= epsilon/2.
What's the point of all this?? Instead of Pr_{S,S'}[B] we have
Pr_{S,S',swap}[B_T]. Will show this is small by showing that for
*all* S,S', Pr_{swap}[B_T] is small.
In particular, the key here is that even if there are infinitely many
concepts in C, once we have drawn S,S', the number of different
labelings we have to worry about is at most C[2m], and will argue that
whp (over the randomness in "swap") none of them will hurt us.
Now, fix S,S' and fix some splitting h. If, for any i, h makes a
mistake on *both* xi and xi' then Pr_{swap}(err_T(h)=0) = 0. If h
makes a mistake on less than epsilon*m/2 points, then
Pr_{swap}(err_{T'}(h) >= epsilon/2)=0.
Else,
Pr_{swap}(err_T(h)=0 AND err_{T'}(h) >= epsilon/2) <= 2^{-epsilon*m/2}.
Now, we apply union bound:
Pr[B] <= C[2m] * 2^{-epsilon*m/2}. Set this to delta/2.
That's it. Gives us Theorem 2.
===========================================
How about an agnostic/uniform-convergence version of Theorem 1?
Theorem 1': For any class C, distrib D, if:
m > (8/epsilon^2)[ln(2C[2m]) + ln(1/\delta)]
then with prob 1-delta, all h in C have |err_D(h)-err_S(h)| < epsilon.
Just need to redo proof using Hoeffding. Draw 2m examples:
A = event that on 1st m, there exists hyp in C with empirical and
true error that differ by at least epsilon. (This is what we want to
bound for the theorem).
B = event that there exists a concept in C whose empirical error on
1st half differs from empirical error on 2nd half by at least
epsilon/2.
Pr[B|A] >= 1/2 so Pr[A] <= 2*Pr[B]. Now, show Pr[B] is low:
As before, let's pick S, S' and do the random procedure swap to
construct T, T'. Show that for *any* S,S',
Pr_{swap}(exists h in C with |err_T(h)-err_{T'}(h)| > epsilon/2)
is small.
Again, at most C[2m] labelings of S \union S', so fix one such h.
Can think of any i such that exactly one of h(xi) and h(xi') is
correct as a "coin". Asking: if we flip m' <= m coins, what is
Pr(|heads-tails| > epsilon*m/2). Write this as being off from
expectation by more than epsilon*m/4 = (1/4)(epsilon*m/m')m'.
By Hoeffding, Prob is at most 2*e^{-(epsilon*m/m')^2 m'/8}
and this is always <= 2*e^{-epsilon^2 m/8}. Now multiply by C[2m] and
set to delta.
==========================================================================
To get Cor 3, use: C[2m] <= (2m <=d) <= (2em/d)^d. Then just some
rearranging...
===========================================================================
More notes: It's pretty clear we can replace C[2m] with a "high
probability" bound with respect to the distribution D. I.e. a number
such that with high probability, a random set S,S' of 2m points drawn
from D wouldn't have more than this many labelings. With
extra work, you can reduce it further to the *expected* number of
labelings of a random set of 2m points. In fact, there's been a lot
of work on reducing it even further to "the number of possible
labelings of your actual sample". See, e.g., the paper "Sample Based
Generalization Bounds".