The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant

DOI10.1016/S0004-3702(97)00039-8zbMATH Open0904.68112MaRDI QIDQ1127362FDOQ1127362

Authors: Manfred K. Warmuth, Jyrki Kivinen, Peter Auer

Publication date: 13 August 1998

Published in: Artificial Intelligence (Search for Journal in Brave)

Recommendations

Perceptron, Winnow, and PAC Learning
General convergence results for linear discriminant updates
10.1162/1532443041424274
Direct and indirect algorithms for on-line learning of disjunctions

zbMATH Keywords

multiplicative updates perceptron algorithm linear threshold functions mistake bounds relevant variables

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Parallel algorithms in computer science (68W10)

Cites Work

On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Title not available (Why is that?)
Learnability and the Vapnik-Chervonenkis dimension
Title not available (Why is that?)
A theory of the learnable
Exponentiated gradient versus gradient descent for linear predictors
On-line learning of linear functions
Title not available (Why is that?)
How to use expert advice

Cited In (18)

Direct and indirect algorithms for on-line learning of disjunctions
Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
Prototype Classification: Insights from Machine Learning
Title not available (Why is that?)
Sequential correction of linear classifiers
Agnostic learning of geometric patterns
General convergence results for linear discriminant updates
Robust logics
Title not available (Why is that?)
Efficient learning with virtual threshold gates
On the perceptron learning algorithm on data with high precision
On approximating weighted sums with exponentially many terms
PAC analogues of Perceptron and Winnow via boosting the margin
10.1162/1532443041424274
Title not available (Why is that?)
Minimum generalization via reflection: A fast linear threshold learner
Selection of relevant features and examples in machine learning
Perceptron, Winnow, and PAC Learning

This page was built for publication: The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1127362)