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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.