Finite hypothesis
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
definition 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
