The Mathematics Of Generalization

David. H Wolpert, David. H Wolpert

• Publisher: CRC Press
• Year: 2018
• ISBN:
  9780429972157
• Edition: 1
• Topic: Mathematics
• Subtopic: Mathematics General
• Index: Mathematics

This book provides different mathematical frameworks for addressing supervised learning. It is based on a workshop held under the auspices of the Center for Nonlinear Studies at Los Alamos and the Santa Fe Institute in the summer of 1992.

David Haussler

Baskin Center for Computer Engineering and Information Sciences, University of California, Santa Cruz, CA 95064; e-mail: [email protected].

Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications

This chapter, reprinted by permission, originally appeared in Information and Computation 100(1) (1992): 78–150. Copyright © by Academic Press.

We describe a generalization of the PAC learning model that is based on statistical decision theory. In this model the learner receives randomly drawn examples, each example consisting of an instance x ∈ X and an outcome y ∈ Y, and tries to find a decision rule h: X → A, where h ∈ $\mathcal{H}$, that specifies the appropriate action a ∈ A to take for each instance x, in order to minimize the expectation of a loss l(y,a). Here X, Y, and A are arbitrary sets, l is a real-valued function, and examples are generated according to an arbitrary joint distribution on X × Y. Special cases include the problem of learning a function from X into Y, the problem of learning the conditional probability distribution on Y given X (regression), and the problem of learning a distribution on X (density estimation).

We give theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain decision rule spaces $\mathcal{H}$, and show how this implies learnability with bounded sample size, disregarding computational complexity. As an application, we give distribution-independent upper bounds on the sample size needed for learning with feedforward neural networks. Our theorems use a generalized notion of VC dimension that applies to classes of real-valued functions, adapted from Vapnik and Pollard’s work, and a notion of capacity and metric dimension for classes of functions that map into a bounded metric space.

1. INTRODUCTION

The introduction of the Probably Approximately Correct (PAC) model^4,86 of learning from examples has done an admirable job of ...

Table of contents

• Cover
• Half Title
• Title Page
• Copyright Page
• Table of Contents
• Preface
• The Status of Supervised Learning Science circa 1994—The Search for a Consensus
• Reflections After Refereeing Papers for NIPS
• The Probably Approximately Correct (PAC) and Other Learning Models
• Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications
• The Relationship Between PAC, the Statistical Physics Framework, the Bayesian Framework, and the VC Framework
• Statistical Physics Models of Supervised Learning
• On Exhaustive Learning
• A Study of Maximal-Coverage Learning Algorithms
• On Bayesian Model Selection
• Soft Classification, a.k.a. Risk Estimation, via Penalized Log Likelihood and Smoothing Spline Analysis of Variance
• Current Research
• Preface to Simplifying Neural Networks by Soft Weight Sharing
• Simplifying Neural Networks by Soft Weight Sharing
• Error-Correcting Output Codes: A General Method for Improving Multiclass Inductive Learning Programs
• Image Segmentation and Recognition
• Index