Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-07T21:12:47.582Z Has data issue: false hasContentIssue false

Using the Perceptron Algorithm to Find Consistent Hypotheses

Published online by Cambridge University Press:  12 September 2008

Martin Anthony
Affiliation:
Department of Statistical and Mathematical Sciences, London School of Economics, Houghton Street, London WC2A 2AE, UK. e-mail: [email protected].
John Shawe-Taylor
Affiliation:
Department of Computer Science, Royal Holloway and Bedford New College Egham Hill, Egham, Surrey TW20 0EX, UK. e-mail: [email protected].

Abstract

The perceptron learning algorithm quite naturally yields an algorithm for finding a linearly separable boolean function consistent with a sample of such a function. Using the idea of a specifying sample, we give a simple proof that, in general, this algorithm is not efficient.

Type
Research Article
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Anthony, M. and Biggs, N. (1992) Computational Learning Theory: An Introduction, Cambridge University Press, Cambridge.Google Scholar
[2]Anthony, M., Brightwell, G., Cohen, D. and Shawe-Taylor, J. (1992) On exact specification by examples. In: COLT'92, Proceedings of the Fifth Annual Workshop on Computational Learning Theory.CrossRefGoogle Scholar
[3]Blumer, A., Ehrenfeucht, A., Haussler, D. and Warmuth, M. (1989) Learnability and the Vapnik-Chervonenkis Dimension. Journal of the ACM 36 (4) 929965.CrossRefGoogle Scholar
[4]Hampson, S. E. and Volper, D. J. (1986) Linear function neurons: structure and training. Biological Cybernetics 53 203217.CrossRefGoogle ScholarPubMed
[5]Littlestone, N. (1988) Learning quickly when irrelevant attributes abound: a new linear threshold learning algorithm. Machine Learning 2 (4) 285318.CrossRefGoogle Scholar
[6]Minsky, M. and Papert, S. (1969) Perceptrons, MIT Press, Cambridge, MA. (Expanded edition 1988.)Google Scholar
[7]Muroga, S. (1965) Lower bounds of the number of threshold functions and a maximum weight. IEEE Transactions on Electronic Computers 14 136148.CrossRefGoogle Scholar
[8]Rosenblatt, F. (1959) Two theorems of statistical separability in the perceptron. In: Mechanisation of Thought Processes: Proceedings of a Symposium Held at the National Physical Laboratory, 11 1958. Vol. 1, HM Stationery Office, London.Google Scholar
[9]Rosenblatt, F. (1962) Principles of Neurodynamics, Spartan, New York.Google Scholar