The VC inequality is a powerful generalization of the bounds we obtained for
the hyperplane classifier in the previous lecture. The basic idea of the proof
is quite similar. Before starting the inequality, we need to introduce the
concept of shatter coefficients
and VC dimension
.
Let AA be a collection of subsets of RdRd,
definition
: The nthnth shatter coefficient
of AA is defined by
S
A
(
n
)
=
m
a
x
x
1
,
...
,
x
n
ϵ
R
d
{
{
x
1
,
...
,
x
n
}
⋂
A
,
A
ϵ
A
}
S
A
(
n
)
=
m
a
x
x
1
,
...
,
x
n
ϵ
R
d
{
{
x
1
,
...
,
x
n
}
⋂
A
,
A
ϵ
A
}
(1)
The shatter coefficients are a measure of the richness of the collection
AA. SA(n)SA(n) is the largest number of
different subsets of a set of nn points that can be generated by intersecting
the set with elements of AA.
example
: In 1-d, Let A={-∞,t,tϵR}A={-∞,t,tϵR}
Possible subsets of {x1,...,xn}{x1,...,xn} generated by intersecting with sets of the form -∞,t-∞,t are
{x1,...,xn},{x1,...,xn-1},...,{x1},φ{x1,...,xn},{x1,...,xn-1},...,{x1},φ.
Hence Sd(n)=n+1Sd(n)=n+1.
example
: In 2-d, Let AA = {{ all rectangles in R2R2}}
Consider a set {x1,x2,x3,x4}{x1,x2,x3,x4} of training points.
If we arrange the four points into the corner of a diamond shape. It's easy
to see that we can find a rectangle in R2R2 to cover any
subsets of the four points as the above picture, i.e.
SA(4)=24=16SA(4)=24=16.
Clearly, SA(n)=2n,n=1,2,3SA(n)=2n,n=1,2,3 as well.
However, for n=5,SA(n)<25n=5,SA(n)<25. This is because we
can always select four points such that the rectangle, which just contains four
of them, contains the other point. Consequently, we cannot find a rectangle
classifier which contains the four outer points and does not contain the inner
point as shown above.
Note the SA≤2nSA≤2n.
If {{x1,...,xn}⋂A,AϵA}=2n{{x1,...,xn}⋂A,AϵA}=2n then we say that AA shatters
x1,...,xnx1,...,xn.
definition
: The VC dimension
VAVA of a collection of sets AA is defined as the largest interger nn such that
SA(n)=2nSA(n)=2n.
example
: A={-∞,t;tϵR},SA=n+1A={-∞,t;tϵR},SA=n+1 hence VA=1VA=1.
example
: AA = {{ all rectangles in R2R2}}
SA=2n,n=1,2,3,4SA=2n,n=1,2,3,4 and SA≤2n,n=4SA≤2n,n=4, Hence VA=4VA=4.
The VC dimension provides a useful bound on the growth of the shatter coefficients.
Let AA be a collection of set with VC dimension VA<∞VA<∞. Then ∀n,SA(n)≤∑i=0VAni∀n,SA(n)≤∑i=0VAni, also SA(n)≤(n+1)VA,∀nSA(n)≤(n+1)VA,∀n.
Let FF be a collection of classifiers of the form f:Rd→{0,1}f:Rd→{0,1}
Define A={{x:f(x)=1}×{0}⋃{x:f(x)=0}×{1},fϵF}A={{x:f(x)=1}×{0}⋃{x:f(x)=0}×{1},fϵF}
In words, this is collection of subsets of X×YX×Y for which on fϵFfϵF maps the features xx to a label opposite of yy. The size of AA expresses the richness of FF. The larger AA is the more likely it is that there exists an fϵFfϵF for which
R(f)=P(f(X)≠Y)R(f)=P(f(X)≠Y) is close to the Bayes risk
R*=P(f*(X)≠Y)R*=P(f*(X)≠Y) where f*f* is the Bayes classifier.
The nthnth shatter coefficient of FF is defined as SF(n)=SA(n)SF(n)=SA(n)
and the VC dimesion of FF is defined as VF=VAVF=VA.
example
: linear (hyperplane) classifiers in RdRd
Consider dd = 2. Let nn be the number of trainning points, It is easy to see that when n=1n=1, Let AA be as above.
By using linear classifiers in R2R2, it is easy to see that we can assign 1 to all possible subsets
{{x1},φ}{{x1},φ} and 0 to their complements. Hence SF(1)=2SF(1)=2.
When n=2n=2, we can also assign 1 to all possible subsets
{{x1,x2},{x1},{x2},φ}{{x1,x2},{x1},{x2},φ} and 0 to their complements, and vice versa. Hence SF(2)=4=22SF(2)=4=22.
When n=3n=3, we can arrange arrange the point x1,x2,x3x1,x2,x3(non-colinear) so that the set of linear classifiers shatters the three points, hence SF(3)=8=23SF(3)=8=23
When n=4n=4, no matter where the points x1,x2,x3,x4x1,x2,x3,x4 and what designated binary values y1,y2,y3,y4y1,y2,y3,y4 are. It's clear that AA does not shatter the four points. To see the claim, first observe that the four points will form a 4-gon (if the four points are co-linear, or if the three points are co-linear then clearly linear classifiers cannot shatter the points). The two points that belong to the same diagonal lines form 2 groups and no linear classifier can assign different values to the 2 groups. Hence SF(4)<16=24SF(4)<16=24 and VF=3VF=3.
We state here without proving it that in general the class of linear classifiers in RdRd has VF=d+1VF=d+1.
Let X1,,...,XnX1,,...,Xn be i.i.d. RdRd-valued random
variables. Denote the common distribution of Xi,1≤i≤nXi,1≤i≤n
by μ(A)=P(X1ϵA)μ(A)=P(X1ϵA)
for any subset A⊂RdA⊂Rd. Similarly, define the empirical distribution
μn(A)=1n∑1n1{XiϵA}μn(A)=1n∑1n1{XiϵA}.
Thm(VC'71)
For any probablilty measure μμ and collection of subsets AA, and for any ϵ>0ϵ>0.
P
s
u
p
A
ϵ
A
μ
n
(
A
)
-
μ
(
A
)
>
ϵ
≤
8
S
A
(
n
)
e
-
n
ϵ
2
/
32
P
s
u
p
A
ϵ
A
μ
n
(
A
)
-
μ
(
A
)
>
ϵ
≤
8
S
A
(
n
)
e
-
n
ϵ
2
/
32
(2)
and
E
s
u
p
A
ϵ
A
μ
n
(
A
)
-
μ
(
A
)
≤
2
log
2
S
A
(
n
)
n
E
s
u
p
A
ϵ
A
μ
n
(
A
)
-
μ
(
A
)
≤
2
log
2
S
A
(
n
)
n
(3)
Before giving a proof to the theorem. We present a Corollary.
Corollary
: Let FF be a collection of classifiers of the formf:Rd→{0,1}f:Rd→{0,1} with VC dimension VF<∞VF<∞, Let R(f)=P(f(X)≠Y)R(f)=P(f(X)≠Y) and R^n(f)=1n∑1n1{f(Xi)≠Yi}R^n(f)=1n∑1n1{f(Xi)≠Yi}, where Xi,Yi,1≤i≤nXi,Yi,1≤i≤n are i.i.d. with joint distributionPXYPXY.
Define
f^n=argminfϵFR^n(f)f^n=argminfϵFR^n(f).
Then
E
[
R
(
f
^
n
)
]
-
i
n
f
f
ϵ
F
R
(
f
)
≤
4
V
F
log
n
+
1
+
log
2
n
E
[
R
(
f
^
n
)
]
-
i
n
f
f
ϵ
F
R
(
f
)
≤
4
V
F
log
n
+
1
+
log
2
n
(4)
Proof
:
Let A={{x:f(x)=1}×{0}⋃{x:f(x)=0}×{1},fϵF}A={{x:f(x)=1}×{0}⋃{x:f(x)=0}×{1},fϵF}
Note that
P
(
f
(
X
)
≠
Y
)
=
P
(
(
X
,
Y
)
ϵ
A
)
:
=
μ
(
A
)
P
(
f
(
X
)
≠
Y
)
=
P
(
(
X
,
Y
)
ϵ
A
)
:
=
μ
(
A
)
(5)
where A={x:f(x)=1}×{0}⋃{x:f(x)=0}×{1}A={x:f(x)=1}×{0}⋃{x:f(x)=0}×{1}
Similarly,
1
n
∑
1
n
1
{
f
(
X
i
)
≠
Y
i
}
=
1
n
∑
1
n
1
{
(
X
i
,
Y
i
)
ϵ
A
}
:
=
μ
(
A
)
1
n
∑
1
n
1
{
f
(
X
i
)
≠
Y
i
}
=
1
n
∑
1
n
1
{
(
X
i
,
Y
i
)
ϵ
A
}
:
=
μ
(
A
)
(6)
Therefore, according to the VC theorem.
E
s
u
p
f
ϵ
F
R
^
n
(
f
)
-
R
(
f
)
=
E
s
u
p
A
ϵ
A
μ
n
(
A
)
-
μ
(
A
)
≤
2
log
2
S
A
(
n
)
n
=
2
log
2
S
F
(
n
)
n
E
s
u
p
f
ϵ
F
R
^
n
(
f
)
-
R
(
f
)
=
E
s
u
p
A
ϵ
A
μ
n
(
A
)
-
μ
(
A
)
≤
2
log
2
S
A
(
n
)
n
=
2
log
2
S
F
(
n
)
n
(7)
Since VF<∞,SF(n)≤(n+1)VFVF<∞,SF(n)≤(n+1)VF and
E
s
u
p
f
ϵ
F
R
^
n
(
f
)
-
R
(
f
)
≤
2
V
F
log
(
n
+
1
)
+
log
2
n
E
s
u
p
f
ϵ
F
R
^
n
(
f
)
-
R
(
f
)
≤
2
V
F
log
(
n
+
1
)
+
log
2
n
(8)
Next, note that
R
f
^
n
-
i
n
f
f
ϵ
F
R
(
f
)
=
R
f
^
n
-
R
^
n
f
^
n
+
R
^
n
f
^
n
-
i
n
f
f
ϵ
F
R
(
f
)
=
R
f
^
n
-
R
^
n
f
^
n
+
s
u
p
f
ϵ
F
R
^
n
(
f
^
n
)
-
R
(
f
)
≤
R
f
^
n
-
R
^
n
f
^
n
+
s
u
p
f
ϵ
F
R
^
n
(
f
)
-
R
(
f
)
≤
2
s
u
p
f
ϵ
F
R
^
n
(
f
)
-
R
(
f
)
R
f
^
n
-
i
n
f
f
ϵ
F
R
(
f
)
=
R
f
^
n
-
R
^
n
f
^
n
+
R
^
n
f
^
n
-
i
n
f
f
ϵ
F
R
(
f
)
=
R
f
^
n
-
R