Article

Free access

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

Author:

Rocco A. ServedioAuthors Info & Claims

COLT '99: Proceedings of the twelfth annual conference on Computational learning theory

Pages 296 - 307

https://doi.org/10.1145/307400.307474

Published: 06 July 1999 Publication History

PDF eReader

References

[1]

D. Angluin. Queries and concept learning. Machine Learning, 2(4):319-342, 1988.]]

Crossref

Google Scholar

[2]

D. Angluin and P. Laird. Learning from noisy examples. Machine Learning, 2:343-370, 1988.]]

Digital Library

Google Scholar

[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.]]

Crossref

Google Scholar

[4]

M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying boolean functions using labelled examples. Discrete Applied Math., 61(1):1-25, 1993.]]

Digital Library

Google Scholar

[5]

E. Arfin. The Gamma Function. Holt, Rinehart and Winston, New York, 1964.]]

Google Scholar

[6]

P. Auer and M. Warmuth. Tracking the best disjunction. In "36th Symposium on Foundations of Computer Science'' pages 312-321, 1995.]]

Digital Library

Google Scholar

[7]

E. B. Baum. The perceptron algorithm is fast for nonmalicious distributions. Neural Computation, 2:248- 260,1990.]]

Digital Library

Google Scholar

[8]

E. B. Baum and Y-D. Lyuu. The transition to perfect generalization in perceptrons. Neural Computation, 3:386-401, 1991.]]

Crossref

Google Scholar

[9]

A. Blum, A. Frieze, R. Kannan, and S. Vempala. A polynomial time algorithm for learning noisy linear threshold functions. In "37th Symposium on Foundations of Computer Science," pages 330-338,1996.]]

Digital Library

Google Scholar

[10]

A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. ACM, 36(4):929-965, 1989.]]

Digital Library

Google Scholar

[11]

T. Bylander. Learning noisy linear threshold functions. Submitted for publication, available at http: //ringer. as. utsa. edu/~bylander / pubs/pubs, html, 1998.]]

Google Scholar

[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.]]

Crossref

Google Scholar

[13]

E. Cohen. Learning noisy perceptrons by a perceptron in polynomial time. In "38th Symposium on Foundations of Computer Science;', pages 514-523, 1997.]]

Digital Library

Google Scholar

[14]

M. L. Dertouzos. Threshold Logic: A Synthesis Approach. MIT Press, Cambridge, MA, 1965.]]

Google Scholar

[15]

Y. Freund and R. Schapire. Large margin classification using the Perceptron algorithm. In "1 lth Conference on Computational Learning Theory;' pages 209-217, 1998.]]

Digital Library

Google Scholar

[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.]]

Crossref

Google Scholar

[17]

J. H~stad. On the size of weights for threshold gates. SIAM J. Discrete Math., 7(3):484~492, 1994.]]

Digital Library

Google Scholar

[18]

S. Hampson and D. Volper. Linear function neurons: structure and training. Biological Cybernetics, 53:203- 217, 1986.]]

Digital Library

Google Scholar

[19]

D. Haussler. Space efficient learning algorithms. Technical Report UCSC-CRL-88-2, University of Calif., Santa Cruz, 1988.]]

Google Scholar

[20]

W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58:13-30, 1963.]]

Crossref

Google Scholar

[21]

N. Karmarkar. A new polynomial time algorithm for linear programming. Combinatorica, 4:373-395, 1984.]]

Digital Library

Google Scholar

[22]

M. Kearns. Efficient Noise-Tolerant Learning from Statistical Queries. In "25th Symposium on Theory of Computation," pages 392-401, 1993.]]

Digital Library

Google Scholar

[23]

M. Kearns and U. Vazirani. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, 1994.]]

Digital Library

Google Scholar

[24]

J. Kivinen, M. Warmuth, and P. Auer. The perceptron algorithm vs. winnow: linear vs. logarithmic mistake bounds when few input variables are relevant. In "8th Conference on Computational Learning Theory," pages 289-296, 1995.]]

Digital Library

Google Scholar

[25]

N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285-318, 1988.]]

Crossref

Google Scholar

[26]

N. Littlestone. Mistake Bounds and Logarithmic Linear-Threshold Learning Algorithms. Ph.D. thesis, Technical Report UCSC-CRL-89-11, University of Calif., Santa Cruz, 1989.]]

Digital Library

Google Scholar

[27]

N. Littlestone. Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow. In "4th Conference on Computational Learning Theory," pages 147-156, 1991.]]

Digital Library

Google Scholar

[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.]]

Digital Library

Google Scholar

[29]

P. Long. Halfspace learning, linear programming, and nonmalicious distributions. Information Processing Letters, 51:245-250, 1994.]]

Digital Library

Google Scholar

[30]

W. Maass and M. Warmuth. Efficient learning with virtual threshold gates. Technical Report UCSC-CRL-95- 37, University of Calif., Santa Cruz, 1995.]]

Digital Library

Google Scholar

[31]

W. Maass and G. Turan. How fast can a threshold gate learn? in "Computational Learning Theory and Natural Learning Systems: Volume I: Constraints and Prospects," S. J. Hanson, G. Drastal, & R. Rivest, eds., MIT Press, Cambridge, MA, pages 381-414, 1994.]]

Digital Library

Google Scholar

[32]

M. Minsky and S. Papert. Perceptrons: An Introduction to Computational Geometry. Expanded edition, MIT Press, Cambridge, MA, 1988.]]

Google Scholar

[33]

S. Muroga. Threshold Logic and its Applications. Wiley-Interscience, New York, 1971.]]

Google Scholar

[34]

M. Opper and D. Haussler. Calculation of the learning curve of Bayes optimal classification algorithm for learning a perceptron with noise. In "4th Conference on Computational Learning Theory," pages 75-87, 1991.]]

Digital Library

Google Scholar

[35]

I. Parberry. Circuit Complexity and Neural Networks. MIT Press, Cambridge, MA, 1994.]]

Digital Library

Google Scholar

[36]

L. Pitt and L. G. Valiant. Computational limitations on learning from examples. J. ACM, 35(4):965-984, 1988.]]

Digital Library

Google Scholar

[37]

F. Rosenblatt. Principles of Neurodynamics. Springer~ Verlag, New York, 1962.]]

Google Scholar

[38]

M. Schmitt. Identification criteria and lower bounds for Perceptron-like learning rules. Neural Computation, 10:235-250, 1998.]]

Digital Library

Google Scholar

[39]

H.S. Seung, H. Sompolinsky, and N. Tishby. Statistical mechanics of learning from examples. Physical Review A, 45(8):6056-6091, 1992.]]

Crossref

Google Scholar

[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.]]

Google Scholar

[41]

L. G. Valiant. A theory of the learnable. Comm. ACM, 27(11):1134-1142, 1984.]]

Digital Library

Google Scholar

[42]

L. G. Valiant. Projection learning. In "1 lth Conference on Computational Learning Theory;' pages 287-293, 1998.]]

Digital Library

Google Scholar

Cited By

View all

Feldman VGuzmán CVempala S(2021)Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex OptimizationMathematics of Operations Research10.1287/moor.2020.111146:3(912-945)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1287/moor.2020.1111
Menon ARooyen BNatarajan N(2018)Learning from binary labels with instance-dependent noiseMachine Language10.1007/s10994-018-5715-3107:8-10(1561-1595)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10994-018-5715-3
Feldman VGuzmán CVempala SKlein P(2017)Statistical query algorithms for mean vector estimation and stochastic convex optimizationProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039768(1265-1277)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039768
Show More Cited By

Index Terms

On PAC learning using Winnow, Perceptron, and a Perceptron-like algorithm
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
  2. Machine learning
2. Theory of computation
  1. Logic

Recommendations

Perceptron, Winnow, and PAC Learning

We analyze the performance of the widely studied Perceptron and Winnow algorithms for learning linear threshold functions under Valiant's probably approximately correct (PAC) model of concept learning. We show that under the uniform distribution on ...
PAC Analogues of Perceptron and Winnow Via Boosting the Margin

We describe a novel family of PAC model algorithms for learning linear threshold functions. The new algorithms work by boosting a simple weak learner and exhibit sample complexity bounds remarkably similar to those of known online algorithms such as ...
Perceptron-based learning algorithms

A key task for connectionist research is the development and analysis of learning algorithms. An examination is made of several supervised learning algorithms for single-cell and network models. The heart of these algorithms is the pocket algorithm, a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLT '99: Proceedings of the twelfth annual conference on Computational learning theory

July 1999

333 pages

ISBN:1581131674

DOI:10.1145/307400

Chairmen:
Shai Ben-David,
Phil Long

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

COLT99

Sponsor:

SIGAI
Univ. of California,
SIGACT

COLT99: The 12th Annual Conference on Computation Learning Theory

July 7 - 9, 1999

California, Santa Cruz, USA

Acceptance Rates

COLT '99 Paper Acceptance Rate 35 of 71 submissions, 49%;

Overall Acceptance Rate 35 of 71 submissions, 49%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
725
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)14

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Feldman VGuzmán CVempala S(2021)Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex OptimizationMathematics of Operations Research10.1287/moor.2020.111146:3(912-945)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1287/moor.2020.1111
Menon ARooyen BNatarajan N(2018)Learning from binary labels with instance-dependent noiseMachine Language10.1007/s10994-018-5715-3107:8-10(1561-1595)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s10994-018-5715-3
Feldman VGuzmán CVempala SKlein P(2017)Statistical query algorithms for mean vector estimation and stochastic convex optimizationProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039768(1265-1277)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039768
Clarkson KHazan EWoodruff D(2012)Sublinear optimization for machine learningJournal of the ACM10.1145/2371656.237165859:5(1-49)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2371656.2371658
Clarkson KHazan EWoodruff D(2010)Sublinear Optimization for Machine LearningProceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science10.1109/FOCS.2010.50(449-457)Online publication date: 23-Oct-2010
https://dl.acm.org/doi/10.1109/FOCS.2010.50
Khardon RWachman G(2007)Noise Tolerant Variants of the Perceptron AlgorithmThe Journal of Machine Learning Research10.5555/1248659.12486678(227-248)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.5555/1248659.1248667
Kalai AKlivans AMansour YServedio R(2005)Agnostically Learning HalfspacesProceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science10.1109/SFCS.2005.13(11-20)Online publication date: 23-Oct-2005
https://dl.acm.org/doi/10.1109/SFCS.2005.13
Bshouty NMossel EO'Donnell RServedio R(2005)Learning DNF from random walksJournal of Computer and System Sciences10.1016/j.jcss.2004.10.01071:3(250-265)Online publication date: 1-Oct-2005
https://dl.acm.org/doi/10.1016/j.jcss.2004.10.010
Dasgupta SKalai AMonteleoni C(2005)Analysis of perceptron-based active learningProceedings of the 18th annual conference on Learning Theory10.1007/11503415_17(249-263)Online publication date: 27-Jun-2005
https://dl.acm.org/doi/10.1007/11503415_17
Klivans AO'Donnell RServedio R(2004)Learning intersections and thresholds of halfspacesJournal of Computer and System Sciences10.1016/j.jcss.2003.11.00268:4(808-840)Online publication date: 1-Jun-2004
https://dl.acm.org/doi/10.1016/j.jcss.2003.11.002
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Perceptron, Winnow, and PAC Learning

PAC Analogues of Perceptron and Winnow Via Boosting the Margin

Perceptron-based learning algorithms