11 - The Pseudo-Dimension and Fat-Shattering Dimension

Summary

Introduction

Chapters 4 and 5 show that the Vapnik-Chervonenkis dimension is crucial in characterizing learnability by binary-output networks, and that it can be used to bound the growth function. Chapter 10 shows that covering numbers are a generalization of the growth function useful for analysing classification by real-output neural networks (or, more generally, by real-valued function classes). We see later in the book that covering numbers are also important in analysing other models of learning. It is natural to ask whether there is a ‘combinatorial’ measure analogous to the VC-dimension that can be used to bound the covering numbers of a class of real-valued functions, and hence to quantify the sample complexity of classification learning. This is largely true, although the definitions and proofs are more complicated than for the binary classification case. In this chapter we introduce the key ‘dimensions’ that we use in our analysis of learning with real function classes and establish some associated basic results and useful properties. In the next chapter we show how these dimensions may be used to bound the covering numbers.

The Pseudo-Dimension

The definition of the pseudo-dimension

To introduce the first of the new dimensions, we first present a slightly different formulation of the definition of the VC-dimension. For a set of functions H mapping from X to {0, 1}, recall that a subset S = {x₁, x₂, … x_m} of X is shattered by H if H_|s has cardinality 2^m.