My aim is to prove a vc-dimension $d$ for different problems. All the problems I have do not have visualised target function (or concept) . I know this is unnecessarily. But 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 find and prove the vc-dimension for this problem. Since I do not know what the target function looks like, I can't test the sample points. All what I know is that if $|x|$ is finite then $h^*(x)=+$ otherwise $-$.

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 how to test for example $(-,+)$ against my function behaviour. Any hints on how to shatter without visualising the target behaviour?


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.