- (0.5 points) Give an example of a finite hypothesis class H with VCdim(H) = 2021.
Justify your choice. - (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. - (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. - (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) - (1 point) Let H = {ℎ!: ℝ → 0,1 , ℎ! � = � !,!!! ∪[!!!,!!) � , � ∈ ℝ}. Compute
VCdim(H). - (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
Our Free Services
Paper Formatting
- Double or single-spaced
- 1-inch margin
- 12 Font Arial or Times New Roman
- 300 words per page
No Lateness!
Our orders are delivered strictly on time without delay
Our Guarantees
- Free Unlimited revisions
- Guaranteed Privacy
- Money Return guarantee
- Plagiarism Free Writing
Finite hypothesis
Our Services
- Research Paper Writing
- Essay Writing
- Dissertation Writing
- Thesis Writing
Daily Statistics
- 134 New Projects
- 235 Projects in Progress
- 432 Inquiries
- 624 Repeat clients
Why Choose Us
- Money Return guarantee
- Guaranteed Privacy
- Written by Professionals
- Paper Written from Scratch
- Timely Deliveries
- Free Amendments