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

DOI10.1016/S0004-3702(97)00039-8MaRDI QIDQ1127362zbMATHFDO

Authors Manfred K. Warmuth, Jyrki Kivinen, Peter Auer

Publication date 13 August 1998

Published in Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

multiplicative updatesperceptron algorithmlinear threshold functionsmistake boundsrelevant variables

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 1306864 (Why is no real title available?)
• scientific article; zbMATH DE number 3436645 (Why is no real title available?)
• A theory of the learnable
• Exponentiated gradient versus gradient descent for linear predictors
• How to use expert advice
• Learnability and the Vapnik-Chervonenkis dimension
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On-line learning of linear functions

Cited in

(18)

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

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)