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

CC BY-SA 4.0
2019-03-08T08:08:52.893Z
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.
domotorp
CC BY-SA 4.0
2019-03-07T22:17:01.607Z
2019-03-07T22:17:01.607Z
domotorp
<p>Let's try to generalize the <span class="math-container">$VC$</span>-dimension (of the class of hyperplanes) to include accuracy/error.  Let <span class="math-container">$S$</span> be a set of points in <span class="math-container">$R^d$</span> and <span class="math-container">$t$</span> in <span class="math-container">$[0,1]$</span>.  We say that the class of hyperplanes <span class="math-container">$t$</span>-shatters <span class="math-container">$S$</span> if for every binary labeling of the points in <span class="math-container">$S$</span>, there exists some hyperplane which separates <span class="math-container">$S$</span> with accuracy at least <span class="math-container">$t$</span> (i.e., at least <span class="math-container">$t*|S|$</span> of the points in <span class="math-container">$S$</span> are classified correctly by the hyperplane).  We then define the <span class="math-container">$VC(t)$</span>-dimension of the class of hyperplanes (in a feature space of dimension <span class="math-container">$d$</span>) to be the size of the largest set <span class="math-container">$S$</span> which the hyperplanes <span class="math-container">$t$</span>-shatter, i.e.,</p>

<p><span class="math-container">$VC(t) = max_{S \subset R^d}{|S|}$</span>, subject to the constraint that the hyperplanes <span class="math-container">$t$</span>-shatter <span class="math-container">$S$</span>.</p>

<p>For example, the usual VC-dimension is <span class="math-container">$VC(1)$</span>.  So <span class="math-container">$VC(1)=d+1$</span>.  <span class="math-container">$VC(t)$</span> is clearly nonincreasing in <span class="math-container">$t$</span>.  <span class="math-container">$VC(0)=\infty$</span> (in fact, I think <span class="math-container">$VC(0.5)=\infty$</span>).</p>

<p>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 <span class="math-container">$VC(t)$</span>?  Thanks!</p>

<p>Edit: Here's the motivation for my question.  For any set of non-coplanar <span class="math-container">$d+1$</span> points in <span class="math-container">$R^d$</span>, and any binary labeling of these points, there is a linear classifier (a hyperplane) which classifies these points with 100% accuracy.  More generally, given <span class="math-container">$n&gt;d+1$</span> 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 <span class="math-container">$t \in [0,1]$</span> and <span class="math-container">$VC(t) \geq n$</span>, then we know that for any <span class="math-container">$n$</span> points in <span class="math-container">$R^d$</span> (satisfying some "weak" condition) and any labeling of these points, there is a linear classifier which has accuracy at least <span class="math-container">$t$</span> on these points.</p>

CC BY-SA 4.0
2019-03-06T07:25:12.353Z
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
CC BY-SA 4.0
2019-03-06T08:24:21.820Z
What is your motivation for this concept? Do you think it will lead to sharper generalization bounds?
Aryeh
CC BY-SA 4.0
2019-03-07T04:14:29.107Z
@Aryeh - I added my motivation.  I don't think it will lead to sharper generalization bounds
ccriscitiello
CC BY-SA 4.0
2019-03-07T06:31:46.067Z
So why is this notion an interesting one to explore then?
Aryeh
CC BY-SA 4.0
2019-03-22T11:52:29.360Z
Thanks for sharing this post.It's useful for me.
user52357
<machine-learning><vc-dimension>
How to generalize VC dimension?
ccriscitiello
# How to generalize VC dimension?

(Asked by: username_0 on 2019-03-06)

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.

**Tags:** machine-learning, vc-dimension
> **Comments:**
> **username_1**: 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.  
> **username_2**: What is your motivation for this concept? Do you think it will lead to sharper generalization bounds?  
> **username_0**: @Aryeh - I added my motivation.  I don't think it will lead to sharper generalization bounds  
> **username_2**: So why is this notion an interesting one to explore then?  
> **username_3**: Thanks for sharing this post.It's useful for me.  

---

## 1 answers

### Answer by username_4 on 2019-03-07. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_4**: 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.  

---

