Perceptron

For alternate meanings see Perceptron (disambiguation).

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 kind of binary classifier that maps its input ${\displaystyle x}$ (a binary vector) to an output value ${\displaystyle f(x)}$ (a single binary value) calculated as

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

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

The value of ${\displaystyle f(x)}$ (0 or 1) is used to classify ${\displaystyle x}$ as either a positive or a negative instance, in the case of a binary classification problem. The bias can be thought of as offsetting the activation function, or giving the output neuron a "base" level of activity. If ${\displaystyle b}$ is negative, then the weighted combination of inputs must produce a positive value greater than ${\displaystyle -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.

Since the inputs are fed directly to the output unit via the weighted connections, the perceptron can be 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:

• ${\displaystyle x(j)}$ denotes the j-th item in the input vector
• ${\displaystyle w(j)}$ denotes the j-th item in the weight vector
• ${\displaystyle y}$ denotes the output from the neuron
• ${\displaystyle \delta }$ denotes the expected output
• ${\displaystyle \alpha }$ is a constant and ${\displaystyle 0<\alpha <1}$
File:Perceptron.gif
the appropriate weights are applied to the inputs that passed to a function which produces the output y

The weights are updated after each input according to the update rule below:

${\displaystyle w(j)'=w(j)+\alpha (\delta -y)x(j)\,}$

Therefore, learning is modeled as the weight vector being updated after one iteration, which will only take place if the output ${\displaystyle y}$ is different from the desired output ${\displaystyle \delta }$. Still considering a single neuron but trying to incorporate multiple iterations, let us first define some more variables:

• ${\displaystyle x_{i}}$ denotes the input vector for the i-th iteration
• ${\displaystyle w_{i}}$ denotes the weight vector for the i-th iteration
• ${\displaystyle y_{i}}$ denotes the output for the i-th iteration
• ${\displaystyle D_{m}=\{(x_{1},y_{1}),\dots ,(x_{m},y_{m})\}}$ denotes a training set of ${\displaystyle m}$ iterations

Each iteration the weight vector is updated as follows

• For each ${\displaystyle (x,y)}$ pair in ${\displaystyle D_{m}=\{(x_{1},y_{1}),\dots ,(x_{m},y_{m})\}}$
• Pass ${\displaystyle (x_{i},y_{i},w_{i})}$ to the update rule ${\displaystyle w(j)'=w(j)+\alpha (\delta -y)x(j)}$

The training set ${\displaystyle D_{m}}$ is said to be linearly separable if there exists a positive constant ${\displaystyle \gamma }$ and a weight vector ${\displaystyle w}$ such that ${\displaystyle y_{i}\cdot \left(\langle w,x_{i}\rangle +b\right)>\gamma }$ for all ${\displaystyle i}$. Novikoff (1962) proved that the perceptron algorithm converges after a finite number of iterations if the data set is linearly separable and the number of mistakes is bounded by ${\displaystyle \left({\frac {2R}{\gamma }}\right)^{2}}$.

However, if the training set is not linearly separable, the above online algorithm is not guaranteed to converge.

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 ${\displaystyle \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.

A linear classifier can only separate things with a hyperplane, so it's not possible to perfectly classify all the examples. 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.

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.

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

Note: Initial weight equals final weight of previous iteration.