Perceptron

From Freepedia

The perceptron is a type of artificial neural network invented in 1957 at the Cornell Aeronautical Laboratory by Frank Rosenblatt. It can be seen as the simplest kind of feedforward neural network.

Contents 1 Definition 2 History 3 See also 4 References 5 External links

Definition

The perceptron is a kind of binary classifier that maps its input <math>x</math> (a real-valued vector in the simplest case) to an output value <math>f(x)</math> calculated as

<math> f(x) = \langle w,x \rangle + b </math>

where <math>w</math> is a vector of weights and <math>\langle \cdot,\cdot \rangle</math> denotes dot product. Since the inputs are fed directly to the output via the weights, the perceptron can be considered the simplest kind of feedforward network. The sign of <math>f(x)</math> is used to classify <math>x</math> as either a positive or a negative instance. The perceptron is trained by a simple online learning algorithm in which examples are presented iteratively and corrections to the weight vectors are made each time a mistake occurs. In order to describe the training procedure, let <math>D_m = \{(x_1,y_1),\dots,(x_m,y_m)\}</math> denote a training set of <math>m</math> examples where <math>x_i</math> and <math>y_i</math> denote the input and the output portions, respectively, of the i-th example. For convenience, we assume that <math>y_i=1</math> for positive examples and <math>y_i=-1</math> for negative ones. The correction to the weight vector when a mistake occurs is <math>x_i y_i</math>. Novikoff (1962) proved that this algorithm converges after a finite number of iterations provided that the training set <math>D_m</math> is linearly separable, that is there exists a weight vector <math>w</math> such that <math>y_i(\langle w, x_i \rangle +b) > 0 </math> for all <math>i</math>.

History

Although the perceptron initially seemed promising, it was quickly proved that perceptrons could not be trained to recognise many classes of patterns. This led to the field of neural network research stagnating for many years, before it was recognised that a feedforward neural network with three or more layers (also called a multilayer perceptron) had far greater processing power than simpler perceptrons (also called a single layer perceptron). In facts, perceptrons are only capable of learning linearly separable patterns; in 1969 a famous monograph entitled Perceptrons by Marvin Minsky and Seymour Papert showed that it was impossible for these classes of network to learn an XOR function. They conjectured (incorrectly) that a similar result would hold for a perceptron with three or more layers. The discovery in the 1980s that multi-layer neural networks did not, in fact, have these problems contributed to the resurgence of neural network research. More recently, interest in the perceptron learning algorithm has increased again after Freund and Schapire (1998) presented a voted formulation of the original algorithm (attaining large margin) and suggested that one can apply the kernel trick to it. The kernel-perceptron not only can handle nonlinearly separable data but can also go beyond vectors and classify instances having a relational representation (e.g. trees, graphs or sequences).

See also

• Artificial intelligence
• Artificial neural network
• Data mining
• Linear classifier
• Linear discriminant analysis
• Logit (for Logistic Regression)
• Machine learning
• Pattern recognition
• Support vector machines

References

• Freund, Y. and Schapire, R. E. 1998. Large margin classification using the perceptron algorithm. In Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT' 98). ACM Press.
• Rosenblatt, Frank (1958), The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain, Cornell Aeronautical Laboratory, Psychological Review, v65, No. 6, pp. 386-408.
• Minsky M L and Papert S A 1969 Perceptrons (Cambridge, MA: MIT Press)
• Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615-622. Polytechnic Institute of Brooklyn.
• Widrow, B., Lehr, M.A., "30 years of Adaptive Neural Networks: Peceptron, Madaline, and Backpropagation," Proc. IEEE, vol 78, no 9, pp. 1415-1442, (1990).

External links

• History of perceptrons
• Mathematics of perceptrons
• Perceptron demo applet
• Perceptron demo applet and a introduction by examples

---

"Perceptron" is also the name of a Michigan company that sells technology products to automakers.