Consider a data setup of one-dimensional data ∈ R1, where the hypothesis space H is parametrized by {p,q} where x is classified as 1 iff p < x < q.
What will be the VC(H)?
Here's my approach: Since 1D data so we can represent the hypothesis space in a number line.
We will consider 2 points and try all possibilities and see if they can all be classified correctly.
Assume data points are d1 and d2.
case1: p < (d1, d2) < q
case2: d1 <= p and p < d2 < q
case3: p < d1 < q and q >= d2
case4: d1 <= p and q >= d2
In all the above cases we can correctly classify.
Let's now take 3 points and try to find a labelling order when it is not possible to classify using a line/hyperplane.
Assume data points are d1, d2, and d3.
d1 <= p, p < d2 < q, and q >= d3
In the above case, it is not possible to classify using a hyperplane. Hence, VC(H) = 2.
Please let me know if my thinking process is correct.
