Pseudo-dimension of real-valued functions

For a set of real-valued functions F = {f:X->R}, How to calc开发者_高级运维ulate the *Pseudo-dimension of F?

providing with an example will help my understanding. like cases where X = {(x,y,z): 0<x<a,0<y<b,0<z<c}

*Pseudo-dimension is a generalization of VC-dimension

---

Dimensions like this are meant to capture the number of degrees of freedom of a concept class, which you label as F in your question. Intuitively, the VC dimension and pseudo dimension will often be a number very close to what you might guess as the number of degrees of freedom.

For example, the set of rectangles in the plane has VC dimension 4, since you can shatter a set of at most 4 points. (Pick any four points that are placed at the end-points of a + sign; you can assign any desired +/- signs to those four points by choosing the appropriate rectangle.) And 4 is a good guess for a number of dimensions for rectangles, since you can specify any rectangle with (x,y) of a certain corner along with (width, height).

For pseudo dimension, you are basically taking the indicator sets {(x,y) : f(x) > y} and taking the VC dimension of that new set.

For example, let F = { f(x) : f(x) = kx for some real number k }. Then the indicator sets will be { (x,y) : kx > y } for each k. In other words, you'll get all the lower half-planes that go through the origin, excluding the vertical line x=0. This set only has VC dimension 1, but that makes sense because your only degree of freedom in F is to choose k.

By the way, this question could also be asked on metaoptimize.com.

---

Just don't get too confused on VC dimensions, you can easily create examples of families of functions that have 1 degree of freedom and infinite VC dimension, for example:

F={1_{sin(ax)>0, a\in Reals}

It has only one degree of freedom but it is easy to see that for every n there is a set of n elements that you can shatter with this family of functions, so the VC dimension is infinite. There are also examples of families that have infinite amount of free parameters nevertheless have finite VC dimension. Like hyperplanes w*x+b on an infinite dimensional space but where the norm of w is bounded.