Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH 475 - Spring 2022 – Homework 4

Questions

1. Let D be a distribution over x and c : S → {0, 1} a target concept.  This question is about estimating the probability

p = Px~D (c(x) = 1) ,

from a sample S.

(a) Let S = (x1 , . . . , xm) ~ Dm  be a sample. Show that the random variable

m

i=1

satisfies ES~Dm (p¯) = p.

(b) Using Bernstein’s inequality show that

PS~Dm  (|p - p¯| > ∈) < 2e_me2 ,

for any 0 < ∈ < 1, where  > 0 is a constant.

2. Let x = R2  and C be the concept class of circles centred at the origin.  That is, each c e C corresponds to a circle Br  with some radius r > 0:

Br  = ←z = (x1 , x2 )T  : x1(2) + x2(2)  < r│ .

(a) Let A be the algorithm that, given a sample S, produces the hypothesis hS corresponding to the circle with smallest radius containing all the points in S with label 1. By modifying

the proof of the axis-aligned rectangles example shown in class, prove that PS~Dm (E(hS ) > ∈) < e_me .

Hint: instead of four rectangles, construct an annulus A with P(A) = ∈ .

(b) Deduce that the concept class is PAC-learnable, and find a precise condition on m (in terms of ∈ and δ) so that

PS~Dm (E(hS ) < ∈) > 1 - δ.