|
About
NeuroCOLT
Papers
Archive
Books
info@neurocolt.org
|
NeuroCOLT
Technical Report NC-TR-94-011
Valid
Generalisation from Approximate Interpolation
Martin
Anthony
Department of Mathematics
The London School of Economics
Peter Bartlett
Research School of Information Sciences and Engineering
Australian National University
Yuval
Ishai
Department of Computer Science
Technion
John
Shawe-Taylor
Department of Computer Science
Royal Holloway, University of London
Abstract
Let $\H$ and $\C$ be sets of functions from domain $X$ to the reals.
We say that $\H$ validly generalises $\C$ from approximate interpolation
if and only if for each $\eta>0$ and $\epsilon, \delta \in (0,1)$
there is a number $m_0(\eta,\epsilon, \delta)$ such that for any function
$t \in \C$ and any probability distribution $P$ on $X$, if $m \ge
m_0$ then with $P^m$-probability at least $1-\delta$, a sample $\vx
=(x_1, x_2, \dots, x_m) \in X^m$ satisfies $$\forall h \in \H, \,|h(x_i)
- t(x_i)|< \eta, \,(1 \le i \le m) \Longrightarrow P(\{x: |h(x)
-t(x)| \ge \eta\}) < \epsilon.$$ We find conditions that are necessary
and sufficient for $\H$ to validly generalise $\C$ from approximate
interpolation, and we obtain bounds on the sample length $m_0(\eta,
\epsilon, \delta)$ in terms of various parameters describing the expressive
power of $\H$.
Download Compressed
Postscript
|