<p>What is the VC dimension of $g: \mathbb{R}^n \times (\mathbb{R}^{n \times n} \times \mathbb{R}^n \times \mathbb{R}) \rightarrow \{-1,1\}$ defined as</p>

<p>$$ g( x, (P_1,p_2,p_3),  ) := \text{sgn} \left( x^\top P_1 x + p_2^\top x + p_3 \right) $$</p>

<p>(where $P_1$ is positive definite)?</p>

<p>Do you think that $(n^2 + 3n)/2$ from [http://arxiv.org/pdf/1109.4347.pdf] is correct?</p>

<p>In the book [Auger, Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments], on pag. 342, I found that $(n^2 + 3n)/2$ is an upper bound.</p>

CC BY-SA 3.0
2013-05-01T21:59:35.137Z
This is an "intuitive" answer rather than a rigorous one, but it looks like f and f' are the same function as far as VC dimension is concerned, the role of x is the role alpha took and the role of beta is the role that x took. By this reasoning the VC dimension of the first function is n+1.
Ross Snider
CC BY-SA 3.0
2013-05-01T22:18:14.617Z
VC dimension is defined for sets, or functions with binary range. if you are thinking of halfspaces, you need to take the sign of the linear form.
Sasho Nikolov
CC BY-SA 3.0
2013-05-02T06:11:39.527Z
Also, perhaps what you mean is: what is the VC dimension of ranges defined by the set of $f(x,\alpha) \ge 0$ over all $\alpha$ ?
Suresh Venkat
CC BY-SA 3.0
2013-05-02T06:29:26.310Z
@ Ross and Suresh: you are right, I meant $\text{sgn}(f)$ or, equivalently the set where $f \geq 0$. Let me point out that the first variable, $x$, is the parameter, while $\alpha$ is the "training" one. In other words, the shattering is done on the space where $\alpha$ lives, and the points/samples taken are like $\alpha^1$, $\alpha^2$, ... Let me try to make this more clear by relabeling the $x$ as $p$, and putting $\alpha$ as first argument.
user693
CC BY-SA 3.0
2013-05-02T08:09:15.027Z
Regarding point 2., seems that on the plane the VC dimension is 5 because 6 points cannot be shattered while 5 points can. So I am wondering if in general we have VC dimension less than $n^2+1$
user693
CC BY-SA 3.0
2013-05-02T08:22:45.333Z
Pt. 1 seems to be halfspaces, and they are well known to have VC-dim $n+1$ (upper bound by Radon's theorem). Your example I believe is wrong: it's halfspaces through the origin in $n+1$ dimensions, which have VC-dim $n+2$. The upper bound carries over from halfspaces, for the lower bound consider the $n+1$ standard basis vectors and $(-1, \ldots, -1)$.
Sasho Nikolov
CC BY-SA 3.0
2013-05-02T08:35:08.783Z
Thanks Sasho. I found that bound on a paper. So I guess it is wrong. I'll update the question so. I am now thinking on the quadratic case. Please let me know if you have thoughts about it.
user693
CC BY-SA 3.0
2016-06-08T10:12:03.417Z
See Corollary 4.2 in http://www.springer.com/us/book/9780387951171
Aryeh
CC BY-SA 3.0
2016-06-08T10:12:44.780Z
The analysis suggests that your VC bound should be $(n^2+3n)/2+2$ -- almost what you wrote.
Aryeh
<approximation-algorithms><machine-learning><lg.learning><vc-dimension>
VC dimension for ellipsoidal classifiers
user693
# VC dimension for ellipsoidal classifiers

(Asked by: username_0 on 2013-05-01)

What is the VC dimension of $g: \mathbb{R}^n \times (\mathbb{R}^{n \times n} \times \mathbb{R}^n \times \mathbb{R}) \rightarrow \{-1,1\}$ defined as

$$ g( x, (P\_1,p\_2,p\_3), ) := \text{sgn} \left( x^\top P\_1 x + p\_2^\top x + p\_3 \right) $$

(where $P\_1$ is positive definite)?

Do you think that $(n^2 + 3n)/2$ from [http://arxiv.org/pdf/1109.4347.pdf] is correct?

In the book [Auger, Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments], on pag. 342, I found that $(n^2 + 3n)/2$ is an upper bound.

**Tags:** approximation-algorithms, machine-learning, lg.learning, vc-dimension
> **Comments:**
> **username_1**: This is an "intuitive" answer rather than a rigorous one, but it looks like f and f' are the same function as far as VC dimension is concerned, the role of x is the role alpha took and the role of beta is the role that x took. By this reasoning the VC dimension of the first function is n+1.  
> **username_2**: VC dimension is defined for sets, or functions with binary range. if you are thinking of halfspaces, you need to take the sign of the linear form.  
> **username_3**: Also, perhaps what you mean is: what is the VC dimension of ranges defined by the set of $f(x,\alpha) \ge 0$ over all $\alpha$ ?  
> **username_0**: @ Ross and Suresh: you are right, I meant $\text{sgn}(f)$ or, equivalently the set where $f \geq 0$. Let me point out that the first variable, $x$, is the parameter, while $\alpha$ is the "training" one. In other words, the shattering is done on the space where $\alpha$ lives, and the points/samples taken are like $\alpha^1$, $\alpha^2$, ... Let me try to make this more clear by relabeling the $x$ as $p$, and putting $\alpha$ as first argument.  
> **username_0**: Regarding point 2., seems that on the plane the VC dimension is 5 because 6 points cannot be shattered while 5 points can. So I am wondering if in general we have VC dimension less than $n^2+1$  
> **username_2**: Pt. 1 seems to be halfspaces, and they are well known to have VC-dim $n+1$ (upper bound by Radon's theorem). Your example I believe is wrong: it's halfspaces through the origin in $n+1$ dimensions, which have VC-dim $n+2$. The upper bound carries over from halfspaces, for the lower bound consider the $n+1$ standard basis vectors and $(-1, \ldots, -1)$.  
> **username_0**: Thanks Sasho. I found that bound on a paper. So I guess it is wrong. I'll update the question so. I am now thinking on the quadratic case. Please let me know if you have thoughts about it.  
> **username_4**: See Corollary 4.2 in http://www.springer.com/us/book/9780387951171  
> **username_4**: The analysis suggests that your VC bound should be $(n^2+3n)/2+2$ -- almost what you wrote.  

---

## 0 answers

