0
$\begingroup$

I've been working on determining the VC-dimension of a specific family of classifiers, and I would like to get some feedback on the proof I've come up with. The family of classifiers is defined as follows: $$ \mathcal{H} = \{h_{a,b} : a, b \in \mathbb{R} \,|\, h_{a,b}(x, y) = \begin{cases} 1, & \text{if } x \geq a \text{ and } y \geq b, \\ 0, & \text{else}. \end{cases} $$

I've provided a proof for the VC-dimension of this class, and I would appreciate it if someone could check its correctness or suggest improvements. Here's the proof:

Find the VC-dimension of this class with a full proof.

\subsection*{Definition of Shattering:} In order to find the VC-dimension, we are looking for the largest set of points that can be shattered by the classifiers in $\mathcal{H}$. A set of points is shattered if, for every possible labeling of the points (assigning 0 or 1 to each point), there exists a classifier $h_{a,b}$ in $\mathcal{H}$ that produces that particular labeling.

Finding VC-dimension of $\mathcal{H}$

To find the VC-dimension of the given class of classifiers $\mathcal{H}$, we need to determine the maximum size of a shattered set. Let's analyze the class of classifiers given by equation~\ref{eq:classifier}. Let's consider a set of points $\{(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)\}$ and check the number of distinct labelings we can achieve with the classifiers in $\mathcal{H}$.

For each point $(x_i, y_i)$, the classifier $h_{a,b}$ assigns a label of 1 if $x_i \geq a$ and $y_i \geq b$, and a label of 0 otherwise.

Now, consider a set of $m$ points $\{(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)\}$. For each point, there are two possible labelings (0 or 1), so there are $2^m$ possible labelings for the entire set.

To find the VC-dimension, we need to find the largest $m$ such that $\Pi_{\mathcal{H}}(m) = 2^m$. This means we want to find the largest set of $m$ points that can be shattered by the classifiers in $\mathcal{H}$.

For the given class $\mathcal{H}$, it can shatter any set of $m$ points because we can always find $a$ and $b$ such that the labels assigned by $h_{a,b}$ match any labeling of the points. Therefore, $\Pi_{\mathcal{H}}(m) = 2^m$ for any $m$.

So, the VC-dimension of $\mathcal{H}$ is infinite: $VC_{\text{dim}}(\mathcal{H}) = \infty$.

Given any set of $m$ points, we can find $a$ and $b$ values such that the classifiers in $\mathcal{H}$ produce any possible labeling of the points. This is because we have the flexibility to adjust $a$ and $b$ to meet the conditions $x \geq a$ and $y \geq b$ for any combination of points. Therefore, $\Pi_{\mathcal{H}}(m) = 2^m$, meaning that the class $\mathcal{H}$ can shatter any set of $m$ points.

The VC-dimension is the size of the largest shattered set. Since $\Pi_{\mathcal{H}}(m) = 2^m$ for any $m$, there is no largest $m$. In this case, $VC_{\text{dim}}(\mathcal{H}) = \infty$ because $\mathcal{H}$ can shatter sets of any size.$$

Here is also the image form if you want to read more clearly: enter image description here

Any feedback, corrections, or suggestions on how to make the proof more robust would be highly valuable. Thank you!

$\endgroup$

1 Answer 1

2
$\begingroup$

The VC dimension of this family is not infinite.

Most of your text is fluff, restating definitions and what must be shown. Some of that can be useful, but IMO there's rather too much of it for a final writeup. The actual argument part seems to just be this:

For the given class $\mathcal{H}$, it can shatter any set of $m$ points because we can always find $a$ and $b$ such that the labels assigned by $h_{a,b}$ match any labeling of the points.

and this is not rigorous enough (and not true as noted at the beginning). How do you find such $a,b$ (again, you can't always)? As a concrete example, take the two points $(0,0), (1,1)$ with labels $1, 0$ respectively. I claim this labeling cannot be realized by $\mathcal{H}$; try to convince yourself of that. Now, that doesn't say anything about the VC dimension: there may be other sets of two (or more!) points that $\mathcal{H}$ shatters (so VCdim could still be two or higher), or not (so VC dimension could be 2 or even 1, as far as this example shows).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.