Pseudo-dimension

The pseudo-dimension is a combinatorial dimension assigned to a class of real-valued functions. It extends the Vapnik–Chervonenkis dimension from binary classifiers to function classes whose outputs range over the real numbers. The quantity governs threshold complexity and appears in distribution-free bounds for statistical learning theory, particularly in the analysis of regression and real-valued empirical processes.

Despite its name, pseudo-dimension is not a dimension of physical space or an additional coordinate in a geometric model. The prefix distinguishes the threshold-dependent definition from the ordinary VC dimension of a class of sets.

Definition

Let (\mathcal F) be a class of functions (f:X\rightarrow\mathbb R). A finite set

[ S={x_1,\ldots,x_n}\subseteq X ]

is pseudo-shattered by (\mathcal F) when there is a threshold vector

[ (r_1,\ldots,r_n)\in\mathbb R^n ]

such that every binary labeling (b\in{0,1}^n) is realized by a function (f_b\in\mathcal F). Realization means that, for every index (i),

[ b_i=1\Rightarrow f_b(x_i)>r_i, \qquad b_i=0\Rightarrow f_b(x_i)<r_i. ]

The pseudo-dimension of (\mathcal F), written (\operatorname{Pdim}(\mathcal F)), is the largest cardinality of a pseudo-shattered subset of (X). Its value is infinite when pseudo-shattered sets exist at every finite cardinality.

The thresholds belong to the points rather than to the selected functions. Consequently, one threshold vector must support all (2^n) labelings of a pseudo-shattered set. Allowing a different threshold vector for every labeling would produce a weaker property and would not define pseudo-dimension.

For a binary-valued class (\mathcal F\subseteq{0,1}^X), thresholds between zero and one reproduce ordinary shattering. Therefore,

[ \operatorname{Pdim}(\mathcal F)

\operatorname{VCdim}(\mathcal F) ]

for binary function classes.

Subgraph characterization

Every (f:X\rightarrow\mathbb R) determines a strict subgraph

[ G_f={(x,t)\in X\times\mathbb R:t<f(x)}. ]

The associated set system is

[ \operatorname{subgraph}(\mathcal F)

{G_f:f\in\mathcal F}. ]

Pseudo-dimension is exactly the VC dimension of this subgraph class:

[ \operatorname{Pdim}(\mathcal F)

\operatorname{VCdim}\bigl(\operatorname{subgraph}(\mathcal F)\bigr). ]

The equivalence follows by identifying the point (x_i) and its threshold (r_i) with the augmented point ((x_i,r_i)). Membership of that augmented point in (G_f) records whether (f(x_i)) lies above the corresponding threshold. This construction transfers combinatorial results for binary set systems to real-valued function classes without converting the numerical outputs into a fixed global classification problem.

Historical development

David Pollard developed the subgraph-dimension formulation during the extension of empirical-process methods to real-valued functions in the 1980s. This formulation supplied a combinatorial interpretation of uniform convergence for classes whose elements were not indicator functions.

In 1989, You Watanabe formalized the threshold-vector presentation for bounded regression classes, proved its equivalence to subgraph shattering, and used it to derive finite-sample bounds for empirical risk. The threshold formulation subsequently became the conventional definition in computational learning theory because it expresses the combinatorial property directly on the original input space.

The name “pseudo-dimension” entered standard usage as real-valued extensions of the probably approximately correct learning framework were organized around loss minimization rather than binary consistency. The resulting theory preserved the logical structure of VC analysis while replacing set membership with comparisons against point-dependent real thresholds.

Growth and metric entropy

If (\operatorname{Pdim}(\mathcal F)=d<\infty), the threshold patterns induced by (\mathcal F) obey the Sauer–Shelah lemma after passage to the subgraph class. On (m) augmented points, the number of realizable binary patterns is at most

[ \sum_{j=0}^{d}\binom{m}{j} ]

when (m\ge d). This polynomial growth replaces the unrestricted total of (2^m) patterns.

For classes bounded in ([0,1]), finite pseudo-dimension also bounds empirical covering numbers. Under the empirical (L_1) metric, the logarithm of a covering number at resolution (\varepsilon) has order

[ O!\left(d\log\frac{1}{\varepsilon}\right), ]

subject to the usual measurability conditions. David Haussler established covering-number inequalities of this form in the decision-theoretic extension of distribution-free learning. These inequalities connect the discrete threshold definition with metric approximations of entire real-valued function classes.

The covering estimates also control Rademacher complexity through entropy integrals. Pseudo-dimension therefore enters learning bounds indirectly even when the final statement is expressed through a metric or probabilistic complexity measure.

Uniform convergence

Let (Z_1,\ldots,Z_m) be independent observations with common distribution (P), and let every (f\in\mathcal F) take values in ([0,1]). For pseudo-dimension (d), standard VC-subgraph bounds give, with probability at least (1-\delta),

[ \sup_{f\in\mathcal F} \left| \mathbb E_P[f(Z)]

\frac{1}{m}\sum_{i=1}^{m}f(Z_i) \right|

O!\left( \sqrt{ \frac{d\log(m/d)+\log(1/\delta)}{m} } \right) ]

for (m\ge d). The displayed form records the direct combinatorial estimate; entropy and localization arguments yield related bounds with different logarithmic factors under additional structural assumptions.

Equivalently, an accuracy level (\varepsilon) follows from a sample size of the standard order

[ O!\left( \frac{ d\log(1/\varepsilon)+\log(1/\delta) }{ \varepsilon^2 } \right). ]

Boundedness prevents isolated function values from dominating the empirical average. Measurability ensures that the supremum and its associated probability statements are well defined.

These bounds extend to bounded loss functions derived from prediction classes. When the loss is Lipschitz in the prediction argument, contraction inequalities transfer complexity control from the prediction class to the induced loss class. This is the principal connection between pseudo-dimension and distribution-free regression guarantees.

Parametric function classes

Pseudo-dimension frequently reflects the number of independent real parameters, although the relation depends on the algebraic structure through which those parameters determine function values.

The class of affine functions on (\mathbb R^p),

[ x\longmapsto w^\mathsf{T}x+b, ]

has pseudo-dimension (p+1), provided the domain contains (p+1) affinely independent points. The parameter vector and intercept form a linear space of dimension (p+1), while the threshold comparisons become linear inequalities in that parameter space.

More generally, a (q)-dimensional vector space of real-valued functions has pseudo-dimension at most (q). Equality holds when evaluations on (q) domain points have full rank. Univariate polynomials of degree at most (k), on a domain containing sufficiently many distinct points, consequently have pseudo-dimension (k+1).

For artificial neural networks, parameter count alone does not determine the exact value. Bounds additionally reflect the network’s computational depth and the algebraic complexity of its activation functions. Networks with piecewise-polynomial activations have finite pseudo-dimension bounded through the number of parameters and the number of computational operations.

Relation to fat-shattering dimension

The fat-shattering dimension adds a positive margin (\gamma) to the threshold inequalities. A set is (\gamma)-fat-shattered when every labeling is represented with function values at least (\gamma) above or below the relevant thresholds. Hence,

[ \operatorname{fat}_{\gamma}(\mathcal F) \le \operatorname{Pdim}(\mathcal F) ]

for every (\gamma>0).

For a finite pseudo-shattered set, the finitely many witnessing inequalities possess a positive minimum separation after one witness function is fixed for each labeling. It follows that

[ \operatorname{Pdim}(\mathcal F)

\sup_{\gamma>0} \operatorname{fat}_{\gamma}(\mathcal F). ]

The distinction remains important in quantitative analysis. Pseudo-dimension records whether arbitrarily small separations suffice, whereas fat-shattering dimension records complexity at a specified numerical resolution. The latter therefore retains information about scale that pseudo-dimension discards.

See also