The perceptron algorithm vs. Winnow

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The perceptron algorithm vs. Winnow: linear vs. logarithmic mistake bounds when few input variables are relevant

Full text

Pdf (939 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the eighth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 289 - 296

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Jyrki Kivinen	Department of Computer Science, P.O. Box 26 (Teollisuuskatu 23), FIN-00014 University of Helsinki, Finland
Manfred K. Warmuth	Computer and Information Sciences, University of California, Santa Cruz, Santa Cruz, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
University of California : University of California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 32, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/225298.225333 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	BEHW89	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
	DH73	R, O. Duds and P. E. Hart. Paller~ Classzficaizon and Scene Analysis. Wiley, 1973.
	DK95	E. Dichterman and R. Khardon. A tight bound for the VC dimension of k-term DNF. Private communication.
	Kha79	L.G. Khachiyan. A polynomial algorithm in linear programming (in Russian). Dok'- lady Akadcmlz Nauk SSSR, 244:1093-1096, 1979. (English translation: Smqet Mathematics Doklady 20:191-194, 1979.)
	KW94	Jyrki Kivinen , Manfred Warmuth, EXPONENTIATED GRADIENT VERSUS GRADIENT DESCENT FOR LINEAR PREDICTORS, University of California at Santa Cruz, Santa Cruz, CA, 1994
	Lit88	Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
	Lit89	N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
	Lit91	Nicholas Littlestone, Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow, Proceedings of the fourth annual workshop on Computational learning theory, p.147-156, August 05-07, 1991, Santa Cruz, California, United States
	Lit95	N. Littlestone. Comparing several linearthreshold learning algorithms on tasks involving superfluous attributes. In Proc. 12th I, ler'natzonal Machine Learning Conference (ML-95), July 1995.
	LLW91	Nicholas Littlestone , Philip M. Long , Manfred K. Warmuth, On-line learning of linear functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.465-475, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103467]
	MT94	Wolfgang Maass , György Turán, How fast can a threshold gate learn?, Proceedings of a workshop on Computational learning theory and natural learning systems (vol. 1) : constraints and prospects: constraints and prospects, p.381-414, August 1994, Princeton, New Jersey, United States
	Ros58	F. Rosenblatt, The perception: a probabilistic model for information storage and organization in the brain, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988
	SST91	H. S. Seung , H. Sompolinsky , N. Tishby, Learning curves in large neural networks, Proceedings of the fourth annual workshop on Computational learning theory, p.112-127, August 05-07, 1991, Santa Cruz, California, United States
	Vai89	P M. Vaidya. A new algorithm for minimizing convex functions over convex sets. In Proc. 30lh Symposzum on Foundatwns of Computer Sczcnce, pages 338 343. IEEE Cornputer Society, 1989.
	Val84	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	VC71	V N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probab. and ~ts Apphcations, 16(2):264- 280, 1971.
	WRB93	T.L.H. Watkin, A. Rau, and M. Biehl. The statistical mechanics of learning a rule. Rev. Mod. Phys., 65:499-5,56, 1993.

CITED BY 11

	Adam R. Klivans , Rocco Servedio, Learning DNF in time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.258-265, July 2001, Hersonissos, Greece
	Rocco A. Servedio, On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm, Proceedings of the twelfth annual conference on Computational learning theory, p.296-307, July 07-09, 1999, Santa Cruz, California, United States
	David P. Helmbold , Yoram Singer , Robert E. Schapire , Manfred K. Warmuth, A comparison of new and old algorithms for a mixture estimation problem, Proceedings of the eighth annual conference on Computational learning theory, p.69-78, July 05-08, 1995, Santa Cruz, California, United States
	Leslie G. Valiant, Projection learning, Proceedings of the eleventh annual conference on Computational learning theory, p.287-293, July 24-26, 1998, Madison, Wisconsin, United States
	Leslie G. Valiant, Robust logics, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.642-651, May 01-04, 1999, Atlanta, Georgia, United States
	Dan Roth , Ming-Hsuan Yang , Narendra Ahuja, Learning to recognize three-dimensional objects, Neural Computation, v.14 n.5, p.1071-1103, May 2002
	Adam R. Klivans , Rocco A. Servedio, Learning DNF in time 2^{õ(n^1/3)}, Journal of Computer and System Sciences, v.68 n.2, p.303-318, March 2004
	Leslie G. Valiant, Projection Learning, Machine Learning, v.37 n.2, p.115-130, Nov.1.1999
	David P. Helmbold , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, A Comparison of New and Old Algorithms for a Mixture EstimationProblem, Machine Learning, v.27 n.1, p.97-119, April 1997
	Adam J. Grove , Nick Littlestone , Dale Schuurmans, General convergence results for linear discriminant updates, Proceedings of the tenth annual conference on Computational learning theory, p.171-183, July 06-09, 1997, Nashville, Tennessee, United States
	Michael Schmitt, Identification criteria and lower bounds for perceptron-like learning rules, Neural Computation, v.10 n.1, p.235-250, Jan. 1, 1998