tech rep on overfitting, decision theory, PAC learning, and...

[David Haussler]

TECHNICAL REPORT AVAILABLE
----------------------------

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

David Haussler
UCSC-CRL-91-02
September, 1989 
Revised: December, 1990
haussler at saturn.ucsc.edu
Baskin Center for Computer Engineering and Information Sciences
University of California, Santa Cruz, CA 95064

Abstract:
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 \in X$ and an outcome $y \in Y$, and tries to find 
a hypothesis $h : X \rightarrow A$, where $h \in \cH$, that specifies
the appropriate action $a \in 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 \times 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 hypothesis spaces $\cH$,
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 Pollard's work, 
and a notion of {\em capacity} and {\em metric dimension}
for classes of functions that map into a bounded metric space.


The report can be retrieved by anonymous ftp from the UCSC Tech
report library. An example follows:

unix> ftp midgard.ucsc.edu       # (or ftp 128.114.134.15)
Connected ... 
Name (...): anonymous
Password: yourname at cs.anyuniversity.edu  (i.e. your email address) 
	(Please use your email address so we can correspond with you.)
Guest login ok, access restrictions apply.
ftp> cd pub/tr
ftp> binary
ftp> get ucsc-crl-91-02.ps.Z
200 PORT command successful.
150 Opening BINARY mode data connection for ucsc-crl-91-02.ps.Z (576429 bytes).
226 Transfer complete.
local: ucsc-crl-91-02.ps.Z remote: ucsc-crl-91-02.ps.Z
576429 bytes received in 10 seconds (70 Kbytes/s)
ftp> quit
unix> uncompress ucsc-crl-91-02.ps.Z
unix> lpr -P(your_local_postscript_printer) ucsc-crl-91-02.ps

(Note: you will need a printer with a large memory.)
(also: some other UCSC tech reports are available as well and more will be
added soon.  ftp the file INDEX to see what's there.)

If you have any difficulties with the above, please send e-mail to
jean at cis.ucsc.edu.   DO NOT "reply" to this message, please.

										 -David