Developing theoretical foundations for learning is a key step towards
understanding intelligence. 'Learning from examples' is a paradigm
in which systems (natural or artificial) learn a functional relationship
from a training set of examples. Within this paradigm, a learning
algorithm is a map from the space of training sets to the hypothesis
space of possible functional solutions. A central question for the
theory is to determine conditions under which a learning algorithm
will generalize from its finite training set to novel examples. A
milestone in learning theory1, 2, 3, 4, 5 was a characterization
of conditions on the hypothesis space that ensure generalization
for the natural class of empirical risk minimization (ERM) learning
algorithms that are based on minimizing the error on the training
set. Here we provide conditions for generalization in terms of a
precise stability property of the learning process: when the training
set is perturbed by deleting one example, the learned hypothesis
does not change much. This stability property stipulates conditions
on the learning map rather than on the hypothesis space, subsumes
the classical theory for ERM algorithms, and is applicable to more
general algorithms. The surprising connection between stability and
predictivity has implications for the foundations of learning theory
and for the design of novel algorithms, and provides insights into
problems as diverse as language learning and inverse problems in
physics and engineering.
%0 Journal Article
%1 Poggio:2004a
%A Poggio, Tomaso
%A Rifkin, Ryan
%A Mukherjee, Sayan
%A Niyogi, Partha
%D 2004
%J Nature
%K imported
%P 419-422
%T General conditions for predictivity in learning theory
%V 428
%X Developing theoretical foundations for learning is a key step towards
understanding intelligence. 'Learning from examples' is a paradigm
in which systems (natural or artificial) learn a functional relationship
from a training set of examples. Within this paradigm, a learning
algorithm is a map from the space of training sets to the hypothesis
space of possible functional solutions. A central question for the
theory is to determine conditions under which a learning algorithm
will generalize from its finite training set to novel examples. A
milestone in learning theory1, 2, 3, 4, 5 was a characterization
of conditions on the hypothesis space that ensure generalization
for the natural class of empirical risk minimization (ERM) learning
algorithms that are based on minimizing the error on the training
set. Here we provide conditions for generalization in terms of a
precise stability property of the learning process: when the training
set is perturbed by deleting one example, the learned hypothesis
does not change much. This stability property stipulates conditions
on the learning map rather than on the hypothesis space, subsumes
the classical theory for ERM algorithms, and is applicable to more
general algorithms. The surprising connection between stability and
predictivity has implications for the foundations of learning theory
and for the design of novel algorithms, and provides insights into
problems as diverse as language learning and inverse problems in
physics and engineering.
@article{Poggio:2004a,
abstract = {Developing theoretical foundations for learning is a key step towards
understanding intelligence. 'Learning from examples' is a paradigm
in which systems (natural or artificial) learn a functional relationship
from a training set of examples. Within this paradigm, a learning
algorithm is a map from the space of training sets to the hypothesis
space of possible functional solutions. A central question for the
theory is to determine conditions under which a learning algorithm
will generalize from its finite training set to novel examples. A
milestone in learning theory1, 2, 3, 4, 5 was a characterization
of conditions on the hypothesis space that ensure generalization
for the natural class of empirical risk minimization (ERM) learning
algorithms that are based on minimizing the error on the training
set. Here we provide conditions for generalization in terms of a
precise stability property of the learning process: when the training
set is perturbed by deleting one example, the learned hypothesis
does not change much. This stability property stipulates conditions
on the learning map rather than on the hypothesis space, subsumes
the classical theory for ERM algorithms, and is applicable to more
general algorithms. The surprising connection between stability and
predictivity has implications for the foundations of learning theory
and for the design of novel algorithms, and provides insights into
problems as diverse as language learning and inverse problems in
physics and engineering.},
added-at = {2009-06-26T15:25:19.000+0200},
author = {Poggio, Tomaso and Rifkin, Ryan and Mukherjee, Sayan and Niyogi, Partha},
biburl = {https://www.bibsonomy.org/bibtex/23d79e49fdf87d38ea072c9eea539b159/butz},
description = {diverse cognitive systems bib},
interhash = {9cb6884efea9a5fecfef74495668dac9},
intrahash = {3d79e49fdf87d38ea072c9eea539b159},
journal = {Nature},
keywords = {imported},
owner = {martin},
pages = {419-422},
timestamp = {2009-06-26T15:25:50.000+0200},
title = {General conditions for predictivity in learning theory},
volume = 428,
year = 2004
}