Page 90 - Understanding Machine Learning

Nonuniform Learnability
72

for each such K n a function f n : K n →{0,1} so that no h ∈ H n agrees with f n on
the domain K n . Finally, define f : X →{0,1} by combining these f n ’s and prove

that f ∈ H \ H n .
n∈N
5. Construct a class H 1 of functions from the unit interval [0,1] to {0,1} that is
nonuniformly learnable but not PAC learnable.
6. Construct a class H 2 of functions from the unit interval [0,1] to {0,1} that is not
nonuniformly learnable.
7.6 In this question we wish to show that the algorithm Memorize is a consistent learner
for every class of (binary-valued) functions over any countable domain. Let X be a
countable domain and let D be a probability distribution over X.
1. Let {x i : i ∈ N} be an enumeration of the elements of X so that for all i ≤ j,
D({x i }) ≤ D({x j }). Prove that

lim D({x i }) = 0.
n→∞
i≥n
2. Given any
> 0 prove that there exists
D > 0 such that
D({x ∈ X : D({x}) <
D }) <
.
3. Prove that for every η> 0, if n is such that D({x i }) <η for all i > n, then for every
m ∈ N,
P [∃x i :(D({x i }) >η and x i /∈ S)] ≤ ne −ηm .
S∼D m
4. Conclude that if X is countable then for every probability distribution D over
X there exists a function m D :(0,1) × (0,1) → N such that for every
,δ > 0if
m > m D (
,δ)then
P [D({x : x /∈ S}) >
] <δ.
S∼D m
5. Prove that Memorize is a consistent learner for every class of (binary-valued)
functions over any countable domain.