# How to generalize VC dimension?

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.

• 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. – Gamow Mar 6 at 7:25
• What is your motivation for this concept? Do you think it will lead to sharper generalization bounds? – Aryeh Mar 6 at 8:24
• @Aryeh - I added my motivation. I don't think it will lead to sharper generalization bounds – Doggyy Mar 7 at 4:14
• So why is this notion an interesting one to explore then? – Aryeh Mar 7 at 6:31
• Thanks for sharing this post.It's useful for me. – user52357 Mar 22 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.