[SOLVED] ML-Homework 2 Union Of Intervals

Description

Union Of Intervals. In this question, we will study the hypothesis class of a finite union of disjoint intervals, and the properties of the ERM algorithm for this class.

To review, let the sample space be X = [0,1] and assume we study a binary classification problem, i.e. Y = {0,1}. We will try to learn using an hypothesis class that consists of k intervals. More explicitly, let I = {[l₁,u₁],…,[l_k,u_k]} be k disjoint intervals, such that 0 ≤ l₁ ≤ u₁ ≤ l₂ ≤ u₂ ≤ … ≤ u_k ≤ 1. For each such k disjoint

intervals, define the corresponding hypothesis as

(

1           if x ∈ [l₁,u₁],…,[l_k,u_k]

h_I(x) =

0     otherwise

Finally, define H_k as the hypothesis class that consists of all hypotheses that correspond to k disjoint intervals:

H_k = {h_I|I = {[l₁,u₁],…,[l_k,u_k]}, 0 ≤ l₁ ≤ u₁ ≤ l₂ ≤ u₂ ≤ … ≤ u_k ≤ 1}

We note that H_k ⊆ H_k+1, since we can always take one of the intervals to be of length 0 by setting its endpoints to be equal. We are given a sample of size m = hx₁,y₁i,…,hx_n,y_mi. Assume that the points are sorted, so that 0 ≤ x₁ < x₂ < … < x_m ≤ 1.