29.2 The Multiclass Fundamental Theorem 403
To define the Natarajan dimension, we first generalize the definition of shat-
tering.
definition29.1 (Shattering (Multiclass Version)) We say that a setC⊂X
is shattered byHif there exist two functionsf 0 ,f 1 :C→[k] such that
- For everyx∈C,f 0 (x) 6 =f 1 (x).
- For everyB⊂C, there exists a functionh∈Hsuch that
∀x∈B,h(x) =f 0 (x) and∀x∈C\B,h(x) =f 1 (x).
definition29.2 (Natarajan Dimension) The Natarajan dimension ofH, de-
noted Ndim(H), is the maximal size of a shattered setC⊂X.
It is not hard to see that in the case that there are exactly two classes,
Ndim(H) = VCdim(H). Therefore, the Natarajan dimension generalizes the VC
dimension. We next show that the Natarajan dimension allows us to general-
ize the fundamental theorem of statistical learning from binary classification to
multiclass classification.
29.2 The Multiclass Fundamental Theorem
theorem29.3 (The Multiclass Fundamental Theorem) There exist absolute
constantsC 1 ,C 2 > 0 such that the following holds. For every hypothesis classH
of functions fromXto[k], such that the Natarajan dimension ofHisd, we have
1.Hhas the uniform convergence property with sample complexity
C 1
d+ log(1/δ)
^2
≤mUCH(,δ)≤C 2
dlog (k) + log(1/δ)
^2
2.His agnostic PAC learnable with sample complexity
C 1
d+ log(1/δ)
^2 ≤mH(,δ)≤C^2
dlog (k) + log(1/δ)
^2.
3.His PAC learnable (assuming realizability) with sample complexity
C 1
d+ log(1/δ)
≤mH(,δ)≤C 2
dlog
(kd
)
+ log(1/δ)
29.2.1 On the Proof of Theorem 29.3
The lower bounds in Theorem 29.3 can be deduced by a reduction from the
binary fundamental theorem (see Exercise 5).
The upper bounds in Theorem 29.3 can be proved along the same lines of the
proof of the fundamental theorem for binary classification, given in Chapter 28
(see Exercise 4). The sole ingredient of that proof that should be modified in a
nonstraightforward manner is Sauer’s lemma. It applies only to binary classes
and therefore must be replaced. An appropriate substitute is Natarajan’s lemma:
