1
$\begingroup$

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?

$\endgroup$

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.