My aim is to prove a VC-dimension $d$ for different problems. All the problems I have do not have a target function (or concept) explicitly stated. This unlike most of the examples I came through. For example in the interval problem, the target function $h^*$ is: if point $x\in [a,b]$ then $x=+$ and $-$ otherwise. I do not know where $[a,b]$ resides in $R$ but at least I know its an interval. Therefore, three points of $(+,-,+)$ cannot be shattered by any concept.

I am given an infinite input space $X$ and $H$ is the class of all finite languages over $X$ and asked to prove the VC-dimension for this problem. I have no clue what the target function looks like.

Assume I got two points $x_1,x_2\in X$, there are $2^2$ possibilities $(-,-),(-,+),(+,-),(+,+)$. I am stucking here since I don't know what is shattered (i.e. realisable) and what is not without knowing the target function $h^*$. Should I assume such function exists and then workout based on its behaviour? am I missing something?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.