The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant
From MaRDI portal
Publication:1127362
DOI10.1016/S0004-3702(97)00039-8zbMath0904.68112MaRDI QIDQ1127362
Peter Auer, Manfred K. Warmuth, Jyrki Kivinen
Publication date: 13 August 1998
Published in: Artificial Intelligence (Search for Journal in Brave)
perceptron algorithm; linear threshold functions; multiplicative updates; mistake bounds; relevant variables
68T05: Learning and adaptive systems in artificial intelligence
68W10: Parallel algorithms in computer science
Related Items
Agnostic learning of geometric patterns, Robust logics, Selection of relevant features and examples in machine learning, Efficient learning with virtual threshold gates, On approximating weighted sums with exponentially many terms, Learning DNF in time \(2^{\widetilde O(n^{1/3})}\), Prototype Classification: Insights from Machine Learning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exponentiated gradient versus gradient descent for linear predictors
- On-line learning of linear functions
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- How to use expert advice
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities