29.6 Exercises 409
29.6 Exercises
- Letd,k >0. Show that there exists a binary hypothesisHbinof VC dimension
dsuch that Ndim(HbinOvA,k) =d.
- Prove Lemma 29.6.
- Prove Natarajan’s lemma.
Hint:Fix somex 0 ∈ X. Fori,j∈[k], denote byHijall the functionsf:
X {x 0 } →[k] that can be extended to a function inHboth by defining
f(x 0 ) =iand by definingf(x 0 ) =j. Show that|H|≤|HX{x 0 }|+
∑
i 6 =j|Hij|
and use induction.
- Adapt the proof of the binary fundamental theorem and Natarajan’s lemma
to prove that, for some universal constantC >0 and for every hypothesis
class of Natarajan dimensiond, the agnostic sample complexity ofHis
mH(,δ)≤C
dlog
(kd
)
+ log(1/δ)
^2
.
- Prove that, for some universal constantC >0 and for every hypothesis class
of Natarajan dimensiond, the agnostic sample complexity ofHis
mH(,δ)≥C
d+ log(1/δ)
^2.
Hint:Deduce it from the binary fundamental theorem.
- LetHbe the binary hypothesis class of (nonhomogenous) halfspaces inRd.
The goal of this exercise is to prove that Ndim(HOvA,k)≥(d−1)·(k−1).
- LetHdiscretebe the class of all functionsf: [k−1]×[d−1]→ { 0 , 1 }for
which there exists somei 0 such that, for everyj∈[d−1]
∀i < i 0 ,f(i,j) = 1 while∀i > i 0 ,f(i,j) = 0.
Show that Ndim(HOvAdiscrete,k) = (d−1)·(k−1).
- Show thatHdiscretecan be realized byH. That is, show that there exists
a mappingψ: [k−1]×[d−1]→Rdsuch that
Hdiscrete⊂{h◦ψ : h∈H}.
Hint:You can takeψ(i,j) to be the vector whosejth coordinate is 1, whose
last coordinate isiand the rest are zeros.
- Conclude that Ndim(HOvA,k)≥(d−1)·(k−1).
