Perceptron
Perceptrons are the basis of neural networks. They exist to perform classifications like that shown below. Each dot represents the test scores and grades for set of students applying to a university. Blue dots indicate the student was accepted to the university. Red indicates they were denied.
In the case of the dot in yellow, above, we would assume they were accepted given that they are above the black dividing line.
The formula for the black line is given by:
$$2 x_1 + x_2  18 = 0$$
Algorithmically, we could assign each applying student a score based on the following formula:
$$Score = 2(Test) + Grades  18$$
 If score > 0, the student is Accepted.
 If score < 0, the student is Denied.
In the example student above (Test = 7, Grades = 6), their score comes out to 2, which means they would be Accepted.
General Form for 2 Dimensions
The more general equation for a 2dimensional boundary line is the following.
$$w_1 x_1 + w_2 x_2 + b = 0$$
This can also be expressed as
$$ Wx + b = 0,\ where\ W = (w_1, w_2),\ x = (x_1, x_2)$$
$$\hat{y} = 1,\ if Wx + b \geq 0$$ $$\hat{y} = 0,\ Wx + b < 0$$
The goal of the algorithm is to have $y$ the same as $\hat{y}$ as often as possible.
More General Case
The more general case exists in $n$dimensional space where each point ($x_1, x_2, …, x_n$) is either above or below an n1 dimensional hyperplane. The equation of the hyperplane is still $Wx+b=0$.
To satisfy this equation, the weights, $W$, will be a $(1 \times n)$ vector, the input features, $x$, will be $(n \times 1)$, and the bias, $b$, will be $(1 \times 1)$.
Perceptron
A perceptron is an encoding of our equation above into a small graph. The perceptron receives the points as inputs, like in the image below, and returns $1$ if the point is in the positive area, and a $0$ otherwise.
The bias can be thought of as another input with magnitude 1 and edge weight equal to the bias term, as show below.
In the case of the example above:
$$Score = 2 \times 7 + 1 \times 6  18 \times 1 = 2$$
Since $2 \geq 0$, the perceptron would output $1$.
The more general case of a perceptron with $n$ inputs is shown below.
During the linear function part of the node above, the node calculates $Wx + b = \sum^n_{i=1} W_i X_i + b$. The output of that linear function is run through a step function during which the continuous output of the linear function is categorized into a binary $1$ or $0$.
Perceptrons as Logical Operators
By setting the weights and bias strategically, perceptrons can be made to function as logical operators. The perceptron below functions as an AND
operator.
This one functions as an OR
.
A perceptron that models NOT
can also be constructed. Combinations of AND
, OR
, and NOT
perceptrons can be used to create more complicated logical operators such as NAND
and XOR
.
Perceptron Trick
The perceptron trick involves moving the line progressively closer to any misclassified points. For example, in the following image the point $(4,5)$ is misclassified on the wrong side of the boundary line $3x_1 + 4x_2  10 = 0$.
To adjust the location of the line, it is adjusted by a small ratelimiting factor (“learning rate”) times the location of the point, with a 1 added as the bias. The line $3x_1 + 4x_2  10 = 0$ could be denoted by the tuple $(3, 4, 10)$ and the point denoted by $(4, 5, 1)$. For a learning rate of $0.1$, the adjusted equation of the line would be:
$$(3, 4, 10)  0.1(4, 5, 1) = (2.6, 3.5, 10.1)$$
Thus, the new equation for the line is $2.6x_1 + 3.5x_2  10.1 = 0$.
Perceptron Algorithm

Start with random weights: $w_1, …, w_n, b$

For every misclassified point $(x_1, …, x_n)$:
2.1. If prediction = 0:
 For i = 1 … n:
 Change $w_i \rightarrow w_i + \alpha x_i$
 Change $b \rightarrow b + \alpha$
2.2 If prediction = 1:
 For i = 1 … n:
 Change $w_i = w_i  \alpha x_i$
 Change $b \rightarrow b  \alpha$
 For i = 1 … n: