<p>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.  </p>

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

CC BY-SA 2.5
2010-10-12T07:22:17.970Z
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.
Josephine Moeller
CC BY-SA 2.5
2010-10-13T03:53:25.447Z
There is some work on o-minimal structures/theory that tries to handle such things. http://en.wikipedia.org/wiki/O-minimal_theory#Examples
Sariel Har-Peled
CC BY-SA 2.5
2010-10-13T23:54:19.923Z
@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?
Josephine Moeller
CC BY-SA 2.5
2010-10-14T00:17:25.233Z
Well. It is an extension of constant algebraic complexity. It might be remotely relevant - I frankly dont know.
Sariel Har-Peled
CC BY-SA 2.5
2010-10-12T06:27:35.867Z
2010-10-12T06:27:35.867Z
Jeff Phillips
<p>I wish to know the VC-dimension of a range space $(X,\mathcal{R})$ constructed as follows:</p>

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

<p>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.</p>

<p>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}$. </p>

<p>I know that this range space has <strong>at least</strong> 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:</p>

<ol>
<li>Circular disks in $\mathbb{R}^2$ have VC-dim 3</li>
<li>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</li>
</ol>

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

CC BY-SA 2.5
2010-10-20T11:00:04.077Z
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?
James King
CC BY-SA 2.5
2010-10-21T01:28:24.617Z
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))$.
Josephine Moeller
<cg.comp-geom><vc-dimension>
VC-dimension of Cylinders within a Cylinder
Josephine Moeller
# VC-dimension of Cylinders within a Cylinder

(Asked by: username_0 on 2010-10-12)

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
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)?

**Tags:** cg.comp-geom, vc-dimension
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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))$.  

---

## 1 answers

### Answer by username_2 on 2010-10-12. Score: 4

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

> **Comments:**
> **username_0**: 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.  
> **username_3**: There is some work on o-minimal structures/theory that tries to handle such things. http://en.wikipedia.org/wiki/O-minimal_theory#Examples  
> **username_0**: @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?  
> **username_3**: Well. It is an extension of constant algebraic complexity. It might be remotely relevant - I frankly dont know.  

---

