Understanding Machine Learning: From Theory to Algorithms

28.3 The Upper Bound for the Realizable Case 401 28.3.1 From-Nets to PAC Learnability theorem28.4 LetHbe a hypothesis class ove ...

29 Multiclass Learnability Contents xvii In Chapter 17 we have introduced the problem of multiclass categorization, in which the ...

29.2 The Multiclass Fundamental Theorem 403 To define the Natarajan dimension, we first generalize the definition of shat- terin ...

404 Multiclass Learnability lemma29.4 (Natarajan) |H|≤|X|Ndim(H)·k2Ndim(H). The proof of Natarajan’s lemma shares the same spiri ...

29.3 Calculating the Natarajan Dimension 405 By Sauer’s lemma,|(Hbin)C|≤|C|d. We conclude that 2 |C| ≤ ∣∣ ∣ ( HOvAbin,k ) C ∣∣ ∣ ...

406 Multiclass Learnability theorem29.7 Ndim(HΨ)≤d. Proof LetC ⊂ X be a shattered set, and letf 0 ,f 1 :C→ [k] be the two functi ...

29.4 On Good and Bad ERMs 407 learnable by some ERM, but other ERMs will fail to learn it. Clearly, this also implies that the c ...

408 Multiclass Learnability Proof LetDbe a distribution overXand suppose that the correct labeling ishA. For any sample,Agoodret ...

29.6 Exercises 409 29.6 Exercises Letd,k >0. Show that there exists a binary hypothesisHbinof VC dimension dsuch that Ndim(H ...

30 Compression Bounds Throughout the book, we have tried to characterize the notion of learnability using different approaches. ...

30.1 Compression Bounds 411 theorem30.2 Letkbe an integer and letB:Zk→ Hbe a mapping from sequences ofkexamples to the hypothesi ...

412 Compression Bounds definition30.5 (Compression Scheme for Unrealizable Sequences) LetHbe a hypothesis class of functions fro ...

30.2 Examples 413 A Compression Scheme: W.l.o.g. assume all labels are positive (otherwise, replacexibyyixi). The com- pression ...

414 Compression Bounds Note thatp(x) can be rewritten as〈w,ψ(x)〉where the elements ofψ(x) are all the monomials ofxup to degreer ...

31 PAC-Bayes The Minimum Description Length (MDL) and Occam’s razor principles allow a potentially very large hypothesis class b ...

416 PAC-Bayes later show how in some cases this idea leads to the regularized risk minimization principle. theorem31.1 LetDbe an ...

31.2 Bibliographic Remarks 417 Next, we claim that for allhwe haveES[e2(m−1)∆(h) 2 ]≤m. To do so, recall that Hoeffding’s inequa ...

418 PAC-Bayes 2.• Suppose thatHis a finite hypothesis class, set the prior to be uniform over H, and set the posterior to beQ(hS ...

Appendix A Technical Lemmas lemmaA.1 Leta > 0. Then:x≥ 2 alog(a) ⇒ x≥alog(x). It follows that a necessary condition for the i ...

420 Technical Lemmas Proof For alli= 0, 1 , 2 ,...denoteti=a(i+ √ log(b)). Sincetiis monotonically increasing we have that E[|X− ...