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$
  • $\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 '10 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$ – John Moeller Oct 21 '10 at 1:28
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$
  • $\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$ – John Moeller Oct 12 '10 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$ – Sariel Har-Peled Oct 13 '10 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$ – John Moeller Oct 13 '10 at 23:54
  • $\begingroup$ Well. It is an extension of constant algebraic complexity. It might be remotely relevant - I frankly dont know. $\endgroup$ – Sariel Har-Peled Oct 14 '10 at 0:17

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.