Page 376 - Understanding Machine Learning

Multiclass Learnability
358

1. Let H discrete be the class of all functions f :[k − 1] × [d − 1] →{0,1} for which
there exists some i 0 such that, for every j ∈ [d − 1]
∀i < i 0 , f (i, j) = 1 while ∀i > i 0 , f (i, j) = 0.
OvA,k
Show that Ndim(H ) = (d − 1) · (k − 1).
discrete
2. Show that H discrete can be realized by H. That is, show that there exists a
d
mapping ψ :[k − 1]× [d − 1] → R such that
H discrete ⊂{h ◦ψ : h ∈ H}.
Hint: You can take ψ(i, j) to be the vector whose jth coordinate is 1, whose
last coordinate is i, and the rest are zeros.
OvA,k
3. Conclude that Ndim(H ) ≥ (d − 1) · (k − 1).