## 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