The Angular-Metric Traveling Salesman Problem
Motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a TSP tour for a set of points in Euclidean space, where the angle cost of a tour is the sum of t...
Motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a TSP tour for a set of points in Euclidean space, where the angle cost of a tour is the sum of t...
Navigation in Hypertext Is Easy Only Sometimes
One of the main unsolved problems confronting Hypertext is the navigation problem, namely, the problem of having to know where you are in the database graph representing the structure of a Hypertext ...
One of the main unsolved problems confronting Hypertext is the navigation problem, namely, the problem of having to know where you are in the database graph representing the structure of a Hypertext ...
You are not logged in to this journal. Log in
On Learning Functions from Noise-Free and Noisy Samples via Occam's Razor
SIAM J. Comput. Volume 29, Issue 3, pp. 712-727 (2000)
Issue Date: 2000
Connotea
CiteULike
del.icio.us
BibSonomy
An Occam approximation is an algorithm that takes as input a set of samples of a function and a tolerance $\epsilon$ and produces as output a compact representation of a function that is within $\epsilon$ of the given samples. We show that the existence of an Occam approximation is sufficient to guarantee the probably approximate learnability of classes of functions on the reals even in the presence of arbitrarily large but random additive noise. One consequence of our results is a general technique for the design and analysis of nonlinear filters in digital signal processing.
©1999 Society for Industrial and Applied Mathematics| Permalink: | http://dx.doi.org/10.1137/S0097539794277111 |
KEYWORDS and AMS
PUBLICATION DATA
0097-5397 (print)
1095-7111 (online)
SIAM