Perceptron
Section of Neural units, part of Statistical learning
Perceptron
| Type | Section |
| Taught in | Neural units |
| Part | Statistical learning |
A family of hyperplanes can separate the same labelled sample, and a threshold unit does not come with normal equations. The threshold is constant on each open half-space, so there is no linear system whose solution is “the” weight vector. Suitable weights are built by correction. The perceptron rule changes the weights only on a misclassified pattern, and it moves them along that pattern so the score on the pattern increases when the label was 1 and decreases when the label was 0.
Definition 1 (Perceptron learning rule) Let the training pairs be (x_i,y_i) with y_i\in\{0,1\} and with each x_i augmented by x_{i0}=1. Start from any weights w, including the bias. Repeat until no pattern is misclassified. For each pattern i compute o_i=f(w^\top x_i) and set
w\leftarrow w+(y_i-o_i)\,x_i.
If the unit is right, y_i-o_i=0 and nothing changes. If it outputs 0 for a pattern whose label is 1, the pattern is added to the weights, which increases w^\top x_i by \lVert x_i\rVert^2. If it outputs 1 for a label 0, the pattern is subtracted, and the score decreases by \lVert x_i\rVert^2. The added term is (y_i-o_i)x_i, so the score changes by (y_i-o_i)\lVert x_i\rVert^2.
Rosenblatt’s perceptron convergence theorem says that if the classes are linearly separable the rule reaches a separating set of weights in a finite number of corrections. If they are not, it never stops. Linear separability is the assumption that does the work. The rule returns a separator, when one exists, and it has no further criterion: any separating line ends the algorithm. The support vector machine adds a margin, which is the preference this rule lacks.
Example 1 (Watching a perceptron learn) A unit with two inputs starts at w=(2,1)^\top and bias -1. Class 1 (“+”) sits at (1,1), (0,0.5) and (-0.5,-0.5). Class 0 (“\circ”) sits at (1,0) and (0.5,-1).
Question. Apply one correction (y-o)x at a time, and record the weights until the rule has a separating line.
Solution. At each step one misclassified point is corrected.
| Step | Misclassified point | y | o | Update | New (w_1,w_2), w_0 |
|---|---|---|---|---|---|
| 0 | (2,1), -1 | ||||
| 1 | (0,0.5) | 1 | 0 | add (0,0.5), w_0+1 | (2,1.5), 0 |
| 2 | (1,0) | 0 | 1 | subtract (1,0), w_0-1 | (1,1.5), -1 |
| 3 | (0,0.5) | 1 | 0 | add (0,0.5), w_0+1 | (1,2), 0 |
| 4 | (1,0) | 0 | 1 | subtract (1,0), w_0-1 | (0,2), -1 |
| 5 | (-0.5,-0.5) | 1 | 0 | add (-0.5,-0.5), w_0+1 | (-0.5,1.5), 0 |
| 6 | (-0.5,-0.5) | 1 | 0 | add (-0.5,-0.5), w_0+1 | (-1,1), 1 |
For step 1, \mathrm{net}=-1+0\cdot 2+0.5\cdot 1=-0.5<0, so o=0\neq 1. After step 6, (1,0) has net input exactly 0 and is still classified as class 1 under the convention f(0)=1. Continuing the same rule, cycling through the five points in the order listed, converges after three further corrections to w=(-2,2)^\top, w_0=0, the boundary x_1=x_2. The points (1,1) and (-0.5,-0.5) lie on it (net input 0, classified as 1). The rule stops as soon as every point is on the correct side. It returns a separating line, and it has no notion of a margin.
Used in
- Taught in Neural units
- Also used in Support vector machines
- All 7 questions on Neural units
See also
Artificial neuron · Sigmoid function · Activation function · Perceptron learning rule · A single threshold unit cannot compute XOR · One hidden layer approximates continuous functions · History of the neural unit · Neural unit