Upload your solutions at: https://tinyurl.com/AML-2021-ASSIGNMENT1
1. (0.5 points) Give an example of a finite hypothesis class H with VCdim(H) = 2021.
Justify your choice.
2. (0.5 points) Consider Hballs to be the set of all balls in R2
:
Hballs = {B(x,r), x ? ?2
, r ? 0 }, where B(x,r) = {y ? ?2
| || y x ||2 ? r}
As mentioned in the lecture, we can also view Hballs as the set of indicator functions of
the balls B(x,r) in the plane: Hballs ={ ?!.!: ?! ? 0,1 , ?!.! = ?!(!,!), ? ? ?!, ? > 0}.
Can you give an example of a set A in R2 of size 4 that is shattered by Hballs? Give
such an example or justify why you cannot find a set A of size 4 shattered by Hballs.
3. (1 point) Let X = R2 and consider H? the set of concepts defined by the area inside a
right triangle ABC with the two catheti AB and AC parallel to the axes (Ox and Oy)
and with AB/AC = ? (fixed constant > 0). Consider the realizability assumption. Show
that the class H? can be (?, ?) ? PAC learned by giving an algorithm A and
determining an upper bound on the sample complexity mH( ?, ?) such that the
de
finition of PAC-learnability is satisfied.
4. (1 point) Consider H to be the class of all centered in origin sphere classifiers in the
3D space. A centered in origin sphere classifier in the 3D space is a classifier hr that
assigns the value 1 to a point if and only if it is inside the sphere with radius r > 0 and
center given by the origin O(0,0,0). Consider the realizability assumption.
a. show that the class H can be (?, ?) ? PAC learned by giving an algorithm A and
determining an upper bound on the sample complexity mH(?, ?) such that the
definition of PAC-learnability is satisfied. (0.5 points)
b. compute VCdim(H). (0.5 points)
5. (1 point) Let H = {?!: ? ? 0,1 , ?! ? = ? !,!!! ?[!!!,!!) ? , ? ? ?}. Compute
VCdim(H).
6. (1 point) Let X be an instance space and consider H ? {0,1}! a hypothesis space with
finite VC dimension. For each ? ? X, we consider the function zx: H ?{0,1} such
that zx(h) = h(x) for each ? ? H. Let Z = {zx: H ?{0,1}, ? ? X}. Prove that
VCdim(Z) < 2VCdim(H)+1.
Ex-officio: 0.5 points
The post Math Analysis first appeared on COMPLIANT PAPERS.