8
$\begingroup$

I wish to know the VC-dimension of a range space $(X,\mathcal{R})$ constructed as follows:

  1. $X$ is the cylinder $\{(x,y,z)\in\mathbb{R}^3|x^2+y^2\leq 1\}$
  2. The ranges in $\mathcal{R}$ are formed by taking the union of circular disks such that:
    • the plane containing the disk is orthogonal to the z axis (we "stack" the disks in the z direction)
    • a disk is tangent to the cylinder boundary at the point $(1,0,z)$
    • a disk has diameter $f(z)+1$, where $f(z)$ is bounded (strictly) by $-1<f(z)<1$, and strictly monotonically increasing, strictly monotonically decreasing, or constant.
  3. Any set constructed by rotating one of these ranges about the z axis by an arbitrary angle is also a range.

Intuitively, imagine taking a set of coins (circular, of course) and sorting them by diameter, either decreasing or increasing. Then drop them carefully into a tube (the main cylinder) in that order, so each rests on the last. Now tip the tube slightly so that they all rest against the side of the cylinder. If our coins had zero thickness and we had one for every real number, this would be our range.

I'm mostly interested in the case that $f(z)$ is sigmoid, like the error function or $\tanh$. Specifically, I'm interested in the cylindrical ranges formed by the family of functions $\tanh(\alpha(z-\beta))$, where $\alpha,\beta\in\mathbb{R}$.

I know that this range space has at least VC-dim 4 (I can construct a set of four points that it shatters), but I'm interested in putting an upper bound on it and understanding why. I know that:

  1. Circular disks in $\mathbb{R}^2$ have VC-dim 3
  2. Subsets of the strip $\{-1\leq y\leq 1\}\subset\mathbb{R}^2$ that are bounded above or below by $\tanh(\alpha(z-\beta))$ have at least VC-dim 3, probably equal to 3, because the slope part of the $\tanh$ function acts much like a line

Is there any way to combine these facts to obtain an upper bound on the VC-dimension? Is there anything to say about general $f(z)$ that meet the criteria in (2)?

$\endgroup$
2
  • $\begingroup$ I seem to be misunderstanding something. If the function $f$ is fixed, then each range is uniquely determined by the angle of rotation about the $z$ axis. You then end up essentially trying to shatter circular intervals with points. What is it that I'm missing? Can the function $f$ be different for different ranges? $\endgroup$
    – James King
    Oct 20, 2010 at 11:00
  • 1
    $\begingroup$ Good question. Yes, $f$ may be different. As noted in the answer below, you have to be careful about $f$, but $f$ may belong to a family of functions. As in the example above, $f$ may belong to the family of functions $\tanh(\alpha(z-\beta))$. $\endgroup$ Oct 21, 2010 at 1:28

1 Answer 1

4
$\begingroup$

You need the sigmoid restriction on $f$ for the VC-dimension to be finite. Otherwise, you can let $f$ behave like a staircase, with arbitrarily many steps. Then these staircases can have arbitrarily many intersections. This allows $n$ ranges to admit $2^n$ different subsets.

If $f(z)$ is a polynomial, then you can bound the VC-dimension using the degree of the polynomial (combined with the degree of the polynomial (2) describing the disc). But not sure how to apply this type of result for $\tanh$.

$\endgroup$
4
  • $\begingroup$ Right. If you have a polynomial $f(t)$ you can use the bound described in Matousek. But a transcendental $f(t)$ poses problems in this regard. $\endgroup$ Oct 12, 2010 at 7:22
  • 1
    $\begingroup$ There is some work on o-minimal structures/theory that tries to handle such things. en.wikipedia.org/wiki/O-minimal_theory#Examples $\endgroup$ Oct 13, 2010 at 3:53
  • $\begingroup$ @Sariel: Are you saying that this would this be a way, for example, to define some kind of lift to a space built from transcendental functions of the coordinates, instead of polynomial ones? Because the hyperbolic functions are Pfaffian? $\endgroup$ Oct 13, 2010 at 23:54
  • $\begingroup$ Well. It is an extension of constant algebraic complexity. It might be remotely relevant - I frankly dont know. $\endgroup$ Oct 14, 2010 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.