MATH 475 - Spring 2022 – Homework 4
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 - δ.
2022-03-14