Details

Autor(en) / Beteiligte

• Haussler, David

Titel

Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results

Ist Teil von

• COLT '89, 1989, p.385-385

Ort / Verlag

Elsevier Inc

Erscheinungsjahr

1989

Link zum Volltext

Beschreibungen/Notizen

• We consider the problem of learning functions on a domain X that take values in an arbitrary metric space Y. We assume only that the examples are generated by independent draws from an unknown distribution on X × Y. The learner's goal is to find a function in a given hypothesis space F of functions from X into Y that on average gives Y-values that are close to those observed in random examples (i.e. that has small error). We give a theorem on the uniform convergence of empirical error estimates to true error rates for certain hypothesis spaces F (generalizing a result of Pollard's), and show how this implies learnability, disregarding computational complexity. We generalize the notion of VC dimension to classes of functions mapping into a metric space and show that small VC dimension gives rapid uniform convergence for any distribution. We do this by relating the VC dimension of F to the metric dimension of certain embeddings of F, using results of Pollard and Dudley. As an application, we give a distribution-free uniform convergence result for certain classes of functions computed by neural nets. Here we fix a multi-layer feedforward neural net architecture in which each computation node applies a smooth sigmoid function to a weighted sum of its inputs. We then consider the class of functions defined by varying the weights. We also give uniform convergence results for classes of functions that are uniformly continuous on average, a new notion we introduce. These include classes of continuous functions with a uniform Lipschitz bound, and many classes of discontinuous functions, including indicator functions for regions of small boundary in the unit square. Our results are distribution-free in the former case, but distribution-specific in the latter case (we assume a “near uniform” distribution on the unit square). An extended abstract of this work is given in [1].