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

About

Geeks Mental is a community that publishes articles and tutorials about Web, Android, Data Science, new techniques and Linux security.