Understanding Machine Learning: From Theory to Algorithms

7.8 Exercises 99

3. Prove that for everyη >0, ifnis such thatD({xi})< ηfor alli > n, then
   for everym∈N,
   P
   S∼Dm

[∃xi: (D({xi})> ηandxi∈/S)]≤ne−ηm.

4. Conclude that ifXis countable then for every probability distributionD
   overXthere exists a functionmD: (0,1)×(0,1)→Nsuch that for every
   ,δ >0 ifm > mD(,δ) then
   P
   S∼Dm

[D({x:x /∈S})> ]< δ.

5. Prove thatMemorizeis a consistent learner for every class of (binary-
   valued) functions over any countable domain.