Learning from a population of hypotheses

Machine LearningPublished 1 January 1995Open access

Michael Kearns, H. Sebastian Seung

DOI10.1007/bf00993412

Source URL

Citations8

SJR quartileQ1

SJR score1.15

SNIP2.14

View PDF

TL;DR

A new formal model in which a learning algorithm must combine a collection of potentially poor but statistically independent hypothesis functions in order to approximate an unknown target function arbitrarily well is introduced.

Abstract

We introduce a new formal model in which a learning algorithm must combine a collection of potentially poor but statistically independent hypothesis functions in order to approximate an unknown target function arbitrarily well. Our motivation includes the question of how to make optimal use of multiple independent runs of a mediocre learning algorithm, as well as settings in which the many hypotheses are obtained by a distributed population of identical learning agents.

Keywords

Computer Science

Springer series in statisticsConvergence of Stochastic Processes

1,821 Citations1984David Pollard

Information and ComputationDecision theoretic generalizations of the PAC model for neural net and other learning applications

871 Citations1992David Haussler

Theorems on the uniform convergence of empirical loss estimates to true expected loss rates for certain hypothesis spaces H are given, and it is shown how this implies learnability with bounded sample size, disregarding computational complexity.

The Annals of ProbabilityCentral Limit Theorems for Empirical Measures

574 Citations1978R. M. Dudley

View PDF

Physical Review AStatistical mechanics of learning from examples

513 Citations1992H. Sebastian Seung, Haim Sompolinsky +1 more

It is shown that for smooth networks, i.e., those with continuously varying weights and smooth transfer functions, the generalization curve asymptotically obeys an inverse power law, while for nonsmooth networks other behaviors can appear, depending on the nature of the nonlinearities as well as the realizability of the rule.

Neural ComputationFour Types of Learning Curves

146 Citations1992Шун-ичи Амари, Naotake FUJITA +1 more

The present paper uses the Bayesian approach to show that given the annealed approximation, learning curves can be classified into four asymptotic types.

How to use expert advice

132 Citations1993Nicolò Cesa‐Bianchi, Yoav Freund +4 more

This work analyzes algorithms that predict a binary value by combining the predictions of several prediction strategies, called `experts', and shows how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently known in this context.

An improved boosting algorithm and its implications on learning complexity

66 Citations1992Yoav Freund

The main result is an improvement of the boosting-by-majority algorithm, which shows that the majority rule is the optimal rule for combining general weak learners and extends the boosting algorithm to concept classes that give multi-valued labels and real-valuedlabel.