Fat-shattering dimension

In words...

In binary classification, the fat-shattering dimension is a capacity measure generalizing the Vapnik-Chervonenkis dimension to classes of real-valued functions used as score functions by classifiers and that can be used to derive margin-based error bounds.

This dimension is based on the notion of fat-shattering. We say that a set of points is fat-shattered at a certain scale by a function class, if there is a set of real values assigned to these points such that for all possible binary labeling of the points, there is a function in the class whose graph passes above the real value of the positively labeled points and below the one of the negatively labeled points at a distance at least equal to the scale.

The fat-shattering dimension at a certain scale of a function class is defined as the maximal number of points that can be fat-shattered by this function class at that scale. It can be bounded for popular function classes such as for the set of linear functions.

In pictures...

Fat-shattering a set of points

Fat-shattering dimension

In maths...

For classes of real-valued functions, the notion of fat-shattering is defined as follows.

A set of $n$ points $S=\{x_1,\dots,x_n\} \subset \X^n$ is said to be fat-shattered to width $\gamma>0$ or $\gamma$-shattered by a function class $\G \subset \R^{\X}$ if there exists a vector $\g r \in \R^n$ such that $$ \forall \g y \in \{-1,+1\}^n,\quad \exists g\in\G, \mbox{ such that } y_i( g(x_i) - r_i) \geq \gamma,\ i=1,\dots,n, $$ where the condition $y_i( g(x_i) - r_i) \geq \gamma$ can be rewritten as $$ g(\g x_i)\ \begin{cases} \geq r_i + \gamma, & \mbox{if } y_i = 1 \\ \leq r_i - \gamma, & \mbox{if } y_i = -1 . \end{cases} $$

The fat-shattering dimension of a function class $\G \subset\R^{\X}$ at width $\gamma$ (or the $\gamma$-dimension of $\G$), denoted $\fat_{\gamma}(\G)$, is the size of the largest set of points that can be $\gamma$-shattered by $\G$.

Note that, as for the VC-dimension, this does not imply that $\G$ can $\gamma$-shatter any set of $\fat_{\gamma}(\G)$ points.