Perceptron

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: a linear classifier.

Definition

The perceptron is a binary classifier which maps its input $x$ (a real-valued vector) to an output value $f(x)$ (a single binary value) across the matrix.

$f(x)={\begin{cases}1&{\text{if }}w\cdot x+b>0\\0&{\text{else}}\end{cases}}$

where $w$ is a vector of real-valued weights and $w\cdot x$ is the dot product (which computes a weighted sum). $b$ is the 'bias', a constant term that does not depend on any input value.

The value of $f(x)$ (0 or 1) is used to classify $x$ as either a positive or a negative instance, in the case of a binary classification problem. If $b$ is negative, then the weighted combination of inputs must produce a positive value greater than $|b|$ in order to push the classifier neuron over the 0 threshold. Spatially, the bias alters the position (though not the orientation) of the decision boundary. The perceptron learning algorithm does not terminate if the learning set is not linearly separable.

The perceptron are considered the simplest kind of feed-forward neural network.

Learning algorithm

The learning algorithm is the same across all neurons, therefore everything that follows is applied to a single neuron in isolation. We first define some variables:

• $x(j)$ denotes the j-th item in the n-dimensional input vector
• $w(j)$ denotes the j-th item in the weight vector
• $f(x)$ denotes the output from the neuron when presented with input $x$
• $\alpha$ is a constant where $0<\alpha \leq 1$ (learning rate)

Assume for the convenience that the bias term $b$ is zero. An extra dimension $n+1$ can be added to the input vectors x with $x(n+1)=1$, in which case $w(n+1)$ replaces the bias term.

the appropriate weights are applied to the inputs, and the resulting weighted sum passed to a function which produces the output y

Let $D_{m}=\{(x_{1},y_{1}),\dots ,(x_{m},y_{m})\}$ be training set of $m$ training examples, where $x_{i}$ is the input vector to the perceptron and $y_{i}$ is the desired output value of the perceptron for that input vector.

Learning Algorithm steps:

1. Initialise weights and threshold.

    Set $wi(t)$, (1 <= i <= n), to be the weight i at time t, and ø to be the threshold value in the output node.
    Set w0 to be -ø,the bias, and x0 to be always 1.
    Set $w_{i}(1)$ to small random values, thus initialising the weights and threshold.

2. Present input and desired output

    Present input $x_{1},x_{2},...,x_{n}$and desired output d(t)

3. Calculate the actual output

    $y(t)=fh[w_{1}(t)x_{1}(t)+w_{2}(t)x_{2}(t)+....+w_{n}(t)x_{n}(t)]$

4. Adapts weights

    wi(t+1) = wi(t) + ñ[d(t) - y(t)]xi(t) , where 0 <= ñ <= 1 is a positive gain function that controls the adaption rate.

Steps 3 and 4 are repeated until the iteration error is less than a user-specified error threshold or a predetermined number of iterations have been completed.

Separability and Convergence

---

The training set $D_{m}$ is said to be linearly separable if there exists a positive constant $\gamma$ and a weight vector $w$ such that $y_{i}\cdot (\langle w,x_{i}\rangle +b)>\gamma$ for all $i$. That is, if we say that $w$ is the weight vector to the perceptron, then the output of the perceptron, $\langle w,x_{i}\rangle +b$, multiplied by the desired output of the perceptron, $y_{i}$, must be greater than the positive constant, $\gamma$, for all input-vector/output-value pairs $(x_{i},y_{i})$ in $D_{m}$.

Novikoff (1962) proved that the perceptron algorithm converges after a finite number of iterations if the data set is linearly separable. The idea of the proof is that the weight vector is always adjusted by a bounded amount in a direction that it has a negative dot product with, and thus can be bounded above by $O({\sqrt {t}})$ where t is the number of changes to the weight vector, but it can also be bounded below by $O(t)$ because if there exists an (unknown) satisfactory weight vector, then every change makes progress in this (unknown) direction by a positive amount that depends only on the input vector. This can be used to show that the number of mistakes (changes to the weight vector, i.e. $t$) is bounded by $(2R/\gamma )^{2}$ where $R$ is the maximum norm of an input vector. However, if the training set is not linearly separable, the above online algorithm will not converge.

Note that the decision boundary of a perceptron is invariant with respect to scaling of the weight vector, i.e. a perceptron trained with initial weight vector $w$ and learning rate $\alpha$ is an identical estimator to a perceptron trained with initial weight vector $w/\alpha$ and learning rate 1. Thus, since the initial weights become irrelevant with increasing number of iterations, the learning rate does not matter in the case of the perceptron and is usually just set to one.

Variants

The pocket algorithm with ratchet (Gallant, 1990) solves the stability problem of perceptron learning by keeping the best solution seen so far "in its pocket". The pocket algorithm then returns the solution in the pocket, rather than the last solution.

The $\alpha$-perceptron further utilised a preprocessing layer of fixed random weights, with thresholded output units. This enabled the perceptron to classify analogue patterns, by projecting them into a binary space. In fact, for a projection space of sufficiently high dimension, patterns can become linearly separable.

As an example, consider the case of having to classify data into two classes. Here is a small such data set, consisting of two points coming from two Gaussian distributions.

• 
  Two class gaussian data
• 
  A linear classifier operating on the original space
• 
  A linear classifier operating on a high-dimensional projection

A linear classifier can only separate things with a hyperplane, so it's not possible to classify all the examples perfectly. On the other hand, we may project the data into a large number of dimensions. In this case a random matrix was used to project the data linearly to a 1000-dimensional space; then each resulting data point was transformed through the hyperbolic tangent function. A linear classifier can then separate the data, as shown in the third figure. However the data may still not be completely separable in this space, in which the perceptron algorithm would not converge. In the example shown, stochastic steepest gradient descent was used to adapt the parameters.

Furthermore, by adding nonlinear layers between the input and output, one can separate all data and indeed, with enough training data, model any well-defined function to arbitrary precision. This model is a generalization known as a multilayer perceptron.

It should be kept in mind, however, that the best classifier is not necessarily that which classifies all the training data perfectly. Indeed, if we had the prior constraint that the data come from equi-variant Gaussian distributions, the linear separation in the input space is optimal.

Other training algorithms for linear classifiers are possible: see, e.g., support vector machine and logistic regression.

Example

A perceptron (X₁, X₂ input, X₀*W₀=b, TH=0.5) learns how to perform a NAND function:

		Input				Initial			Output							Final
Threshold	Learning Rate	Sensor values			Desired output	Weights			Calculated			Sum	Network	Error	Correction	Weights
TH	LR	X0	X1	X2	Z	w0	w1	w2	C0	C1	C2	S	N	E	R	W0	W1	W2
									X0 x w0	X1 x w1	X2 x w2	C0+C1+C2	IF(S>TH,1,0)	Z-N	LR x E
0.5	0.1	1	0	0	1	0	0	0	0	0	0	0	0	1	+0.1	0.1	0	0
0.5	0.1	1	0	1	1	0.1	0	0	0.1	0	0	0.1	0	1	+0.1	0.2	0	0.1
0.5	0.1	1	1	0	1	0.2	0	0.1	0.2	0	0	0.2	0	1	+0.1	0.3	0.1	0.1
0.5	0.1	1	1	1	0	0.3	0.1	0.1	0.3	0.1	0.1	0.5	0	0	0	0.3	0.1	0.1
0.5	0.1	1	0	0	1	0.3	0.1	0.1	0.3	0	0	0.3	0	1	+0.1	0.4	0.1	0.1
0.5	0.1	1	0	1	1	0.4	0.1	0.1	0.4	0	0.1	0.5	0	1	+0.1	0.5	0.1	0.2
0.5	0.1	1	1	0	1	0.5	0.1	0.2	0.5	0.1	0	0.6	1	0	0	0.5	0.1	0.2
0.5	0.1	1	1	1	0	0.5	0.1	0.2	0.5	0.1	0.2	0.8	1	-1	-0.1	0.4	0	0.1
0.5	0.1	1	0	0	1	0.4	0	0.1	0.4	0	0	0.4	0	1	+0.1	0.5	0	0.1
0.5	0.1	1	0	1	1	0.5	0	0.1	0.5	0	0.1	0.6	1	0	0	0.5	0	0.1
0.5	0.1	1	1	0	1	0.5	0	0.1	0.5	0	0	0.5	0	1	+0.1	0.6	0.1	0.1
0.5	0.1	1	1	1	0	0.6	0.1	0.1	0.6	0.1	0.1	0.8	1	-1	-0.1	0.5	0	0
0.5	0.1	1	0	0	1	0.5	0	0	0.5	0	0	0.5	0	1	+0.1	0.6	0	0
0.5	0.1	1	0	1	1	0.6	0	0	0.6	0	0	0.6	1	0	0	0.6	0	0
0.5	0.1	1	1	0	1	0.6	0	0	0.6	0	0	0.6	1	0	0	0.6	0	0
0.5	0.1	1	1	1	0	0.6	0	0	0.6	0	0	0.6	1	-1	-0.1	0.5	-0.1	-0.1
0.5	0.1	1	0	0	1	0.5	-0.1	-0.1	0.5	0	0	0.5	0	1	+0.1	0.6	-0.1	-0.1
0.5	0.1	1	0	1	1	0.6	-0.1	-0.1	0.6	0	-0.1	0.5	0	1	+0.1	0.7	-0.1	0
0.5	0.1	1	1	0	1	0.7	-0.1	0	0.7	-0.1	0	0.6	1	0	0	0.7	-0.1	0
0.5	0.1	1	1	1	0	0.7	-0.1	0	0.7	-0.1	0	0.6	1	-1	-0.1	0.6	-0.2	-0.1
0.5	0.1	1	0	0	1	0.6	-0.2	-0.1	0.6	0	0	0.6	1	0	0	0.6	-0.2	-0.1
0.5	0.1	1	0	1	1	0.6	-0.2	-0.1	0.6	0	-0.1	0.5	0	1	+0.1	0.7	-0.2	0
0.5	0.1	1	1	0	1	0.7	-0.2	0	0.7	-0.2	0	0.5	0	1	+0.1	0.8	-0.1	0
0.5	0.1	1	1	1	0	0.8	-0.1	0	0.8	-0.1	0	0.7	1	-1	-0.1	0.7	-0.2	-0.1
0.5	0.1	1	0	0	1	0.7	-0.2	-0.1	0.7	0	0	0.7	1	0	0	0.7	-0.2	-0.1
0.5	0.1	1	0	1	1	0.7	-0.2	-0.1	0.7	0	-0.1	0.6	1	0	0	0.7	-0.2	-0.1
0.5	0.1	1	1	0	1	0.7	-0.2	-0.1	0.7	-0.2	0	0.5	0	1	+0.1	0.8	-0.1	-0.1
0.5	0.1	1	1	1	0	0.8	-0.1	-0.1	0.8	-0.1	-0.1	0.6	1	-1	-0.1	0.7	-0.2	-0.2
0.5	0.1	1	0	0	1	0.7	-0.2	-0.2	0.7	0	0	0.7	1	0	0	0.7	-0.2	-0.2
0.5	0.1	1	0	1	1	0.7	-0.2	-0.2	0.7	0	-0.2	0.5	0	1	+0.1	0.8	-0.2	-0.1
0.5	0.1	1	1	0	1	0.8	-0.2	-0.1	0.8	-0.2	0	0.6	1	0	0	0.8	-0.2	-0.1
0.5	0.1	1	1	1	0	0.8	-0.2	-0.1	0.8	-0.2	-0.1	0.5	0	0	0	0.8	-0.2	-0.1
0.5	0.1	1	0	0	1	0.8	-0.2	-0.1	0.8	0	0	0.8	1	0	0	0.8	-0.2	-0.1
0.5	0.1	1	0	1	1	0.8	-0.2	-0.1	0.8	0	-0.1	0.7	1	0	0	0.8	-0.2	-0.1

Note: Initial weight equals final weight of previous iteration. A too high learning rate makes the perceptron periodically oscillate around the solution. A possible enhancement is to use $LR^{n}$ starting with n=1 and incrementing it by 1 when a loop in learning is found.

Multiclass perceptron

Like most other techniques for training linear classifiers, the perceptron generalizes naturally to multiclass classification. Here, the input $x$ and the output $y$ are drawn from arbitrary sets. A feature representation function $f(x,y)$ maps each possible input/output pair to a finite-dimensional real-valued feature vector. As before, the feature vector is multiplied by a weight vector $w$, but now the resulting score is used to choose among many possible outputs:

${\hat {y}}=\mathrm {argmax} _{y}f(x,y)\cdot w$

Learning again iterates over the examples, predicting an output for each, leaving the weights unchanged when the predicted output matches the target, and changing them when it does not. The update becomes:

$w_{t+1}=w_{t}+f(x,y)-f(x,{\hat {y}})$

This multiclass formulation reduces to the original perceptron when $x$ is a real-valued vector, $y$ is chosen from $\{0,1\}$, and $f(x,y)=yx$.

For certain problems, input/output representations and features can be chosen so that $\mathrm {argmax} _{y}f(x,y)\cdot w$ can be found efficiently even though $y$ is chosen from a very large or even infinite set.

In recent years, perceptron training has become popular in the field of natural language processing for such tasks as part-of-speech tagging and syntactic parsing (Collins, 2002).

History

See also: History of artificial intelligence, AI Winter and Frank Rosenblatt

Although the perceptron initially seemed promising, it was eventually 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 two or more layers (also called a multilayer perceptron) had far greater processing power than perceptrons with one layer (also called a single layer perceptron). Single layer perceptrons are only capable of learning linearly separable patterns; in 1969 a famous book 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. Three years later Stephen Grossberg published a series of papers introducing networks capable of modelling differential, contrast-enhancing and XOR functions. (The papers were published in 1972 and 1973, see e.g.: Grossberg, Contour enhancement, short-term memory, and constancies in reverberating neural networks. Studies in Applied Mathematics, 52 (1973), 213-257, online [1]). Nevertheless the often-cited Minsky/Papert text caused a significant decline in interest and funding of neural network research. It took ten more years until neural network research experienced a resurgence in the 1980s. This text was reprinted in 1987 as "Perceptrons - Expanded Edition" where some errors in the original text are shown and corrected.

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.

References

• 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. doi:10.1037/h0042519.
• Minsky M. L. and Papert S. A. 1969. Perceptrons. Cambridge, MA: MIT Press.
• 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.
• Freund, Y. and Schapire, R. E. 1999. Large margin classification using the perceptron algorithm. In Machine Learning 37(3):277-296, 1999.
• Gallant, S. I. (1990). Perceptron-based learning algorithms. IEEE Transactions on Neural Networks, vol. 1, no. 2, pp. 179-191.
• 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: Perceptron, Madaline, and Backpropagation," Proc. IEEE, vol 78, no 9, pp. 1415-1442, (1990).
• Collins, M. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with the perceptron algorithm in Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP '02)
• Yin, Hongfeng (1996), Perceptron-Based Algorithms and Analysis, Spectrum Library, Concordia University, Canada

External links

• SergeiAlderman-ANN.rtf
• Chapter 3 Weighted networks - the perceptron and chapter 4 Perceptron learning of Neural Networks - A Systematic Introduction by Raúl Rojas (ISBN 978-3540605058)
• Pithy explanation of the update rule by Charles Elkan
• C# implementation of a perceptron
• History of perceptrons
• Mathematics of perceptrons
• Perceptron demo applet and an introduction by examples