Find VC dimension of 1D data
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.
Topic vc-theory classifier
Category Data Science