Let's try to generalize the $VC$-dimension (of the class of hyperplanes) to include accuracy/error. Let $S$ be a set of points in $R^d$ and $t$ in $[0,1]$. We say that the class of hyperplanes $t$-shatters $S$ if for every binary labeling of the points in $S$, there exists some hyperplane which separates $S$ with accuracy at least $t$ (i.e., at least $t*|S|$ of the points in $S$ are classified correctly by the hyperplane). We then define the $VC(t)$-dimension of the class of hyperplanes (in a feature space of dimension $d$) to be the size of the largest set $S$ which the hyperplanes $t$-shatter, i.e.,

$VC(t) = max_{S \subset R^d}{|S|}$, subject to the constraint that the hyperplanes $t$-shatter $S$.

For example, the usual VC-dimension is $VC(1)$. So $VC(1)=d+1$. $VC(t)$ is clearly nonincreasing in $t$. $VC(0)=\infty$ (in fact, I think $VC(0.5)=\infty$).

Question: Have people studied this generalization of VC-dimension, or something similar? If so, what is it called, and can you point me to resources about it? What is the best lower bound on $VC(t)$? Thanks!

Edit: Here's the motivation for my question. For any set of non-coplanar $d+1$ points in $R^d$, and any binary labeling of these points, there is a linear classifier (a hyperplane) which classifies these points with 100% accuracy. More generally, given $n>d+1$ points (satisfying some "weak" condition like non-coplanarity) and a binary labeling of them, what can we say about the accuracy of a linear classifier for these points? If $t \in [0,1]$ and $VC(t) \geq n$, then we know that for any $n$ points in $R^d$ (satisfying some "weak" condition) and any labeling of these points, there is a linear classifier which has accuracy at least $t$ on these points.

  • $\begingroup$ The VC-dimension is defined on hypergraphs, and the geometric setting is just a highly structured special case. If you generalize the geometric setting as you are doing, you simply end up with the same old VC-dimension on another hypergraph. $\endgroup$ – Gamow Mar 6 '19 at 7:25
  • $\begingroup$ What is your motivation for this concept? Do you think it will lead to sharper generalization bounds? $\endgroup$ – Aryeh Mar 6 '19 at 8:24
  • $\begingroup$ @Aryeh - I added my motivation. I don't think it will lead to sharper generalization bounds $\endgroup$ – ccriscitiello Mar 7 '19 at 4:14
  • $\begingroup$ So why is this notion an interesting one to explore then? $\endgroup$ – Aryeh Mar 7 '19 at 6:31
  • $\begingroup$ Thanks for sharing this post.It's useful for me. $\endgroup$ – user52357 Mar 22 '19 at 11:52

If the $VC$-dimension is $d$, then the number of sets that can be cut out from $m$ points by your family is $(em/d)^d$. (This is called the shatter function.) Every set that you can cut out, can be changed at most $\sum_{i=0}^{tm} \binom mi$ ways to contribute to the $t$-shattering. So if you want to $t$-shatter a set of size $m$, then you need $2^m\le (em/d)^d \sum_{i=0}^{tm} \binom mi\le(em/d)^d 2^{H(t)m}$ (if $t\le 1/2$) where $H(t)=-t\log_2 t-(1-t)\log_2(1-t)$ is the binary entropy. From this we get $VC(t)\lessapprox d/(1-H(t))$. Also note that $VC(t)\ge d/(1-t)$ holds trivially. Of course, these bounds are general and not only for halfspaces.

| cite | improve this answer | |
  • $\begingroup$ Thanks for accepting, but I don't think I've really answered your question about halfspaces, I've only provided a lower and an upper bound. $\endgroup$ – domotorp Mar 8 '19 at 8:08

Your Answer

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

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