On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm

Full text

Pdf (1.32 MB)

Source

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

Santa Cruz, California, United States

Pages: 296 - 307

Year of Publication: 1999

ISBN:1-58113-167-4

Author

Rocco A. Servedio

Division of Engineering and Applied Sciences, Harvard University, Cambridge, MA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Univ. of California, : University of California at Santa Cruz

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 22, Citation Count: 9

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/307400.307474 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.

	1	Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
	2	Dana Angluin , Philip Laird, Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988 [doi>10.1023/A:1022873112823]
	3	D. Angluin and L. G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. of Computer and System Sciences, 18(2): 155-193, 1979.
	4	Martin Anthony , Graham Brightwell , John Shawe-Taylor, On specifying Boolean functions by labelled examples, Discrete Applied Mathematics, v.61 n.1, p.1-25, July 7, 1995 [doi>10.1016/0166-218X(94)00007-Z]
	5	E. Arfin. The Gamma Function. Holt, Rinehart and Winston, New York, 1964.
	6	P. Auer , M. K. Warmuth, Tracking the best disjunction, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.312, October 23-25, 1995
	7	Eric B. Baum, The perceptron algorithm is fast for nonmalicious distributions, Neural Computation, v.2 n.2, p.248-260, Apr. 1990 [doi>10.1162/neco.1990.2.2.248]
	8	Eric B. Baum , Yuh-Dauh Lyuu, The transition to perfect generalization in perceptrons, Neural Computation, v.3 n.3, p.386-401, Fall 1991
	9	A. Blum , A. Frieze, A polynomial-time algorithm for learning noisy linear threshold functions, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.330, October 14-16, 1996
	10	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]
	11	T. Bylander. Learning noisy linear threshold functions. Submitted for publication, available at http: //ringer. as. utsa. edu/~bylander / pubs/pubs, html, 1998.
	12	H. Chemoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist., 23:493-507, 1952.
	13	E. Cohen, Learning noisy perceptrons by a perceptron in polynomial time, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.514, October 19-22, 1997
	14	M. L. Dertouzos. Threshold Logic: A Synthesis Approach. MIT Press, Cambridge, MA, 1965.
	15	Yoav Freund , Robert E. Schapire, Large margin classification using the perceptron algorithm, Proceedings of the eleventh annual conference on Computational learning theory, p.209-217, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279985]
	16	E. Gardner and B. Derrida. Three unfinished works on the optimal storage capacity of networks. J. Phys. A: Math. Gen., 22:1983-1994, 1989.
	17	Johan Hastad, On the Size of Weights for Threshold Gates, SIAM Journal on Discrete Mathematics, v.7 n.3, p.484-492, Aug. 1994 [doi>10.1137/S0895480192235878]
	18	S E Hampson , D J Volper, Linear function neurons: Structure and training, Biological Cybernetics, v.53 n.4, p.203-218, Feb. 1986 [doi>10.1007/BF00336991]
	19	D. Haussler. Space efficient learning algorithms. Technical Report UCSC-CRL-88-2, University of Calif., Santa Cruz, 1988.
	20	W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58:13-30, 1963.
	21	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	22	Michael Kearns, Efficient noise-tolerant learning from statistical queries, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.392-401, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167200]
	23	Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
	24	Jyrki Kivinen , Manfred K. Warmuth, The perceptron algorithm vs. Winnow: linear vs. logarithmic mistake bounds when few input variables are relevant, Proceedings of the eighth annual conference on Computational learning theory, p.289-296, July 05-08, 1995, Santa Cruz, California, United States [doi>10.1145/225298.225333]
	25	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]
	26	N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
	27	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
	28	P. Long. On the sample complexity of PAC learning halfspaces against the uniform distribution. In IEEE Trans. on Neural Networks, 6(6): 1556-1559, 1995.
	29	Philip M. Long, Halfspace learning, linear programming, and nonmalicious distributions, Information Processing Letters, v.51 n.5, p.245-250, Sept. 12, 1994 [doi>10.1016/0020-0190(94)90003-5]
	30	Wolfgang Maass , Manfred Warmuth, EFFICIENT LEARNING WITH VIRTUAL THRESHOLD GATES, University of California at Santa Cruz, Santa Cruz, CA, 1995
	31	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
	32	M. Minsky and S. Papert. Perceptrons: An Introduction to Computational Geometry. Expanded edition, MIT Press, Cambridge, MA, 1988.
	33	S. Muroga. Threshold Logic and its Applications. Wiley-Interscience, New York, 1971.
	34	Manfred Opper , David Haussler, Calculation of the learning curve of Bayes optimal classification algorithm for learning a perceptron with noise, Proceedings of the fourth annual workshop on Computational learning theory, p.75-87, August 05-07, 1991, Santa Cruz, California, United States
	35	Ian Parberry, Circuit complexity and neural networks, MIT Press, Cambridge, MA, 1994
	36	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
	37	F. Rosenblatt. Principles of Neurodynamics. Springer~ Verlag, New York, 1962.
	38	Michael Schmitt, Identification criteria and lower bounds for perceptron-like learning rules, Neural Computation, v.10 n.1, p.235-250, Jan. 1, 1998 [doi>10.1162/089976698300017962]
	39	H.S. Seung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Physical Review A, 45(8):6056-6091, 1992.
	40	P. Vaidya. A new algorithm for minimizing convex functions over convex sets. In "30th Symposium on Foundations of Computer Science" pages 338-343, 1989.
	41	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]
	42	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 [doi>10.1145/279943.279999]

CITED BY 9

	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
	Philip M. Long, An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution, Information Processing Letters, v.87 n.5, p.229-234, 15 September 2003
	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
	Adam R. Klivans , Ryan O'Donnell , Rocco A. Servedio, Learning intersections and thresholds of halfspaces, Journal of Computer and System Sciences, v.68 n.4, p.808-840, June 2004
	Nader H. Bshouty , Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning DNF from random walks, Journal of Computer and System Sciences, v.71 n.3, p.250-265, October 2005
	R. Servedio, PAC Analogues of Perceptron and Winnow Via Boosting the Margin, Machine Learning, v.47 n.2-3, p.133-151, May-June 2002
	Roni Khardon , Gabriel Wachman, Noise Tolerant Variants of the Perceptron Algorithm, The Journal of Machine Learning Research, 8, p.227-248, 5/1/2007
	Claudio Gentile, A new approximate maximal margin classification algorithm, The Journal of Machine Learning Research, 2, 3/1/2002
	Sanjoy Dasgupta , Adam Tauman Kalai , Claire Monteleoni, Analysis of Perceptron-Based Active Learning, The Journal of Machine Learning Research, 10, p.281-299, June 2009