8
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Robin Kothari Oct 21 '12 at 23:29
  • 2
    $\begingroup$ 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) $\endgroup$ – Suresh Venkat Oct 22 '12 at 0:44
  • 1
    $\begingroup$ @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$. $\endgroup$ – Robin Kothari Oct 22 '12 at 1:49
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Right. But the OP didn't say how many variables there were. $\endgroup$ – Suresh Venkat Oct 22 '12 at 1:47
  • $\begingroup$ My inequalities involve y and a polynomial in x. I have made some changes in the problem, hoping to define the problem more exactly. $\endgroup$ – Karan Oct 22 '12 at 4:56
  • $\begingroup$ 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) $\endgroup$ – Karan Oct 22 '12 at 4:58
  • $\begingroup$ The formula is an upper bound. $\endgroup$ – Suresh Venkat Oct 22 '12 at 5:48
  • 1
    $\begingroup$ In your modified problem, the answer is D + 1 $\endgroup$ – Suresh Venkat Oct 22 '12 at 5:49
5
$\begingroup$

The following is based on Jiri Matousek's Geometric Discrepancy 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)$.

$\endgroup$

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.