<p>The basic method works like this: Assume your inequalities are of the form </p>

<p>$$ \sum_{i \le d} a_i x^i \le 0$$</p>

<p>Then you construct a <em>lifting map</em> to a space of higher dimension in which each monomial corresponds to one dimension. Now the polynomial can be expressed as a linear combination of the new dimensions and you can invoke the usual result for half spaces in the resulting space. </p>

<p>I'm not sure where you get your bound from: the correct expression for the VC dimension of polynomials in d variables of degree D is $\binom{d + D}{d}$, which is the number of monomials of degree at most D formed from d variables. </p>

CC BY-SA 3.0
2012-10-22T01:47:07.897Z
Right. But the OP didn't say how many variables there were.
Suresh Venkat
CC BY-SA 3.0
2012-10-22T04:56:34.847Z
My inequalities involve y and a polynomial in x. I have made some changes in the problem, hoping to define the problem more exactly.
Karan
CC BY-SA 3.0
2012-10-22T04:58:07.340Z
And acc. to the problem I have stated, quadratics in x should shatter atleast 4 points (that I can see) and acc. to the formula i gave, it should shatter 6 points ! (not sure if it holds though)
Karan
CC BY-SA 3.0
2012-10-22T05:48:00.053Z
The formula is an upper bound.
Suresh Venkat
CC BY-SA 3.0
2012-10-22T05:49:24.327Z
In your modified problem, the answer is D + 1
Suresh Venkat
CC BY-SA 3.0
2012-10-22T01:30:24.080Z
2012-10-22T01:30:24.080Z
Suresh Venkat
<p>The following is based on Jiri Matousek's <a href="http://books.google.com/books?id=BKvXj1GisP0C&amp;lpg=PP1&amp;pg=PA140#v=onepage&amp;q&amp;f=false">Geometric Discrepancy</a> book.</p>

<p>Define a range space in $\mathbb{R}^d$ parametrized by $a_1, \ldots, a_p$ as follows. Let $f$ be a degree $D$ polynomial in $d + p$ variables. For each $a \in \mathbb{R}^p$, the set $S(a)$ is defined as $S(a) = \{x \in \mathbb{R}^d: f(x, a) \leq 0\}$. For example, circles are defined as $(x_1 - a_1)^2 + (x_2 - a_2)^2 - 1 \leq 0$.</p>

<p>We can get a bound on a quantity which is more delicate than VC dimension in this model. Define $\pi(m)$ as the maximum number of <em>distinct</em> sets induced by $\{S(a)\}$ on any set of $m$ points, i.e.
$$
\pi(m) = \max_{X \subseteq \mathbb{R}^d}{|\{S(a) \cap X\}|},
$$
where the max is taken over sets $X$ of $m$ points. This is the <em>primal shatter function</em> of the range space $\{S(a)\}$. Notice that the VC-dimension of of the range space is that maximum $m$ such that $\pi(m) = 2^m$. Also, if the VC-dimension of a range space is $k$, then its shatter function is bounded by $O(m^k)$. </p>

<p>For $m$ polynomials $f_1(a), \ldots, f_m(a)$, $\sigma = (\sigma_1, \ldots, \sigma_m) \in \{-, +\}^m$ is a sign pattern if there exists some $a$ such that for all $i$ the sign of $f_i(a)$ is $\sigma_i$. A result from algebraic geometry is that the maximum number of distinct sign patterns of $m$ degree $D$ polynomials in $p$ variables is bounded by $2^{O(p)}(Dm/p)^p$. </p>

<p>Let's use this theorem. Define $f_i(a) = f(x^i, a)$. We get that $|\{S(a) \cap X\}|$ is exactly the number of distinct sign patterns of $f_1, \ldots, f_m$. So, in particular, if a range space is given by a family of constant degree polynomials in $p$ parameters, its shatter function is bounded by $O(m^p)$. </p>

CC BY-SA 3.0
2012-10-22T01:50:21.863Z
2012-10-22T01:50:21.863Z
Sasho Nikolov
<p>I think the paper <em>VC dimension of neural networks</em> answers the question. In Equation (6), the definition of VC dimension of real valued functions is the same as yours (and I saw some different definitions somewhere), and Theorem 1 claims that the VC dimension of polynomials is exactly the number of items in it. By the way, if the function set contains all the polynomials with degree no more than D, the VC dimension would be <span class="math-container">$C_{D+d}^d$</span> according to Suresh Venkat's answer.</p>

CC BY-SA 4.0
2020-11-05T02:41:44.697Z
Sorry. Sontag, Eduardo D. "VC dimension of neural networks." NATO ASI Series F Computer and Systems Sciences 168 (1998): 69-96. And if anything wrong please contact me since I 'm confused too :)
赵百川
CC BY-SA 4.0
2020-11-05T02:37:21.897Z
2020-11-05T02:37:21.897Z
赵百川
<p>Linear functions in one variable have VC dimension =3 and I remember reading somewhere that the VC for polynomials of degree $d$ is $(d^2 + 3d + 2)/2$.</p>

<p>I am searching for ideas that can prove the above claim (and perhaps generalize to many variables as well, though that seems too much to hope for).</p>

<p>Any approach, even an incomplete one, will be appreciated.</p>

<p>To define the problem properly: Given a plane (2D, x and y coordinates) what is the size of maximum set that can be shattered if you can use classifying functions that are polynomial ($y=p(x)$) of degree at mode $d$, and you are free to choose which side of the curve you want to label positive. </p>

<p>For example, label (x,y) as positive iff $y &gt; x^2 +5x +9$.</p>

CC BY-SA 3.0
2012-10-21T23:29:09.410Z
I don't work in the area, but I'd like to understand the question. What's the domain and range of these functions? Could you explain a little how linear functions in one variable have VC dimension 3?
Robin Kothari
CC BY-SA 3.0
2012-10-22T00:44:41.063Z
The statement is better rephrased as: range spaces defined by ranges that can be expressed as inequalities $f(x) \le 0$ where f(x) is a linear function have VC dimension 3 (this is because this range space is the range space of half spaces in 2D)
Suresh Venkat
CC BY-SA 3.0
2012-10-22T01:49:14.673Z
@Suresh: Thanks for the clarification. From your answer I guess the general question asked is what is the VC dimension of range spaces defined by degree-d (instead of linear) functions $f(x) \leq 0$ where $x \in \mathbb{R}^n$, instead of $\mathbb{R}^2$.
Robin Kothari
<cg.comp-geom><vc-dimension>
VC dimension of polynomials (in one variable) of degree d
Karan
# VC dimension of polynomials (in one variable) of degree d

(Asked by: username_0 on 2012-10-21)

Linear functions in one variable have VC dimension =3 and I remember reading somewhere that the VC for polynomials of degree $d$ is $(d^2 + 3d + 2)/2$.

I am searching for ideas that can prove the above claim (and perhaps generalize to many variables as well, though that seems too much to hope for).

Any approach, even an incomplete one, will be appreciated.

To define the problem properly: Given a plane (2D, x and y coordinates) what is the size of maximum set that can be shattered if you can use classifying functions that are polynomial ($y=p(x)$) of degree at mode $d$, and you are free to choose which side of the curve you want to label positive.

For example, label (x,y) as positive iff $y > x^2 +5x +9$.

**Tags:** cg.comp-geom, vc-dimension
> **Comments:**
> **username_1**: I don't work in the area, but I'd like to understand the question. What's the domain and range of these functions? Could you explain a little how linear functions in one variable have VC dimension 3?  
> **username_2**: The statement is better rephrased as: range spaces defined by ranges that can be expressed as inequalities $f(x) \le 0$ where f(x) is a linear function have VC dimension 3 (this is because this range space is the range space of half spaces in 2D)  
> **username_1**: @Suresh: Thanks for the clarification. From your answer I guess the general question asked is what is the VC dimension of range spaces defined by degree-d (instead of linear) functions $f(x) \leq 0$ where $x \in \mathbb{R}^n$, instead of $\mathbb{R}^2$.  

---

## 3 answers

### Answer by username_2 on 2012-10-22. Score: 8

The basic method works like this: Assume your inequalities are of the form

$$ \sum\_{i \le d} a\_i x^i \le 0$$

Then you construct a *lifting map* to a space of higher dimension in which each monomial corresponds to one dimension. Now the polynomial can be expressed as a linear combination of the new dimensions and you can invoke the usual result for half spaces in the resulting space.

I'm not sure where you get your bound from: the correct expression for the VC dimension of polynomials in d variables of degree D is $\binom{d + D}{d}$, which is the number of monomials of degree at most D formed from d variables.

> **Comments:**
> **username_2**: Right. But the OP didn't say how many variables there were.  
> **username_0**: My inequalities involve y and a polynomial in x. I have made some changes in the problem, hoping to define the problem more exactly.  
> **username_0**: And acc. to the problem I have stated, quadratics in x should shatter atleast 4 points (that I can see) and acc. to the formula i gave, it should shatter 6 points ! (not sure if it holds though)  
> **username_2**: The formula is an upper bound.  
> **username_2**: In your modified problem, the answer is D + 1  

---

### Answer by username_3 on 2012-10-22. Score: 7

The following is based on Jiri Matousek's [Geometric Discrepancy](http://books.google.com/books?id=BKvXj1GisP0C&lpg=PP1&pg=PA140#v=onepage&q&f=false) book.

Define a range space in $\mathbb{R}^d$ parametrized by $a\_1, \ldots, a\_p$ as follows. Let $f$ be a degree $D$ polynomial in $d + p$ variables. For each $a \in \mathbb{R}^p$, the set $S(a)$ is defined as $S(a) = \{x \in \mathbb{R}^d: f(x, a) \leq 0\}$. For example, circles are defined as $(x\_1 - a\_1)^2 + (x\_2 - a\_2)^2 - 1 \leq 0$.

We can get a bound on a quantity which is more delicate than VC dimension in this model. Define $\pi(m)$ as the maximum number of *distinct* sets induced by $\{S(a)\}$ on any set of $m$ points, i.e.
$$
\pi(m) = \max\_{X \subseteq \mathbb{R}^d}{|\{S(a) \cap X\}|},
$$
where the max is taken over sets $X$ of $m$ points. This is the *primal shatter function* of the range space $\{S(a)\}$. Notice that the VC-dimension of of the range space is that maximum $m$ such that $\pi(m) = 2^m$. Also, if the VC-dimension of a range space is $k$, then its shatter function is bounded by $O(m^k)$.

For $m$ polynomials $f\_1(a), \ldots, f\_m(a)$, $\sigma = (\sigma\_1, \ldots, \sigma\_m) \in \{-, +\}^m$ is a sign pattern if there exists some $a$ such that for all $i$ the sign of $f\_i(a)$ is $\sigma\_i$. A result from algebraic geometry is that the maximum number of distinct sign patterns of $m$ degree $D$ polynomials in $p$ variables is bounded by $2^{O(p)}(Dm/p)^p$.

Let's use this theorem. Define $f\_i(a) = f(x^i, a)$. We get that $|\{S(a) \cap X\}|$ is exactly the number of distinct sign patterns of $f\_1, \ldots, f\_m$. So, in particular, if a range space is given by a family of constant degree polynomials in $p$ parameters, its shatter function is bounded by $O(m^p)$.


---

### Answer by username_4 on 2020-11-05. Score: 0

I think the paper *VC dimension of neural networks* answers the question. In Equation (6), the definition of VC dimension of real valued functions is the same as yours (and I saw some different definitions somewhere), and Theorem 1 claims that the VC dimension of polynomials is exactly the number of items in it. By the way, if the function set contains all the polynomials with degree no more than D, the VC dimension would be $C\_{D+d}^d$ according to Suresh Venkat's answer.

> **Comments:**
> **username_4**: Sorry. Sontag, Eduardo D. "VC dimension of neural networks." NATO ASI Series F Computer and Systems Sciences 168 (1998): 69-96. And if anything wrong please contact me since I 'm confused too :)  

---

