C: training a perceptron until it makes no mistakes
Use integer weights and the perceptron rule to learn the AND function.
#include <stdio.h>
int main(void) {
int inputs[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
int targets[4] = {0, 0, 0, 1};
int w1 = 0, w2 = 0, bias = 0;
int epochs = 0;
int mistakes = 1;
while (mistakes > 0) {
mistakes = 0;
for (int i = 0; i < 4; i++) {
int sum = w1 * inputs[i][0] + w2 * inputs[i][1] + bias;
int output = sum > 0 ? 1 : 0;
int error = targets[i] - output;
if (error != 0) {
w1 += error * inputs[i][0];
w2 += error * inputs[i][1];
bias += error;
mistakes++;
}
}
epochs++;
}
printf("epochs: %d\n", epochs);
printf("weights: w1=%d w2=%d bias=%d\n", w1, w2, bias);
for (int i = 0; i < 4; i++) {
int sum = w1 * inputs[i][0] + w2 * inputs[i][1] + bias;
printf("%d AND %d = %d\n", inputs[i][0], inputs[i][1], sum > 0 ? 1 : 0);
}
return 0;
}epochs: 6 weights: w1=2 w2=1 bias=-2 0 AND 0 = 0 0 AND 1 = 0 1 AND 0 = 0 1 AND 1 = 1
Explanation
A perceptron outputs 1 if the weighted sum of its inputs plus a bias is greater than zero, otherwise 0. The learning rule changes the weights only when the output is wrong: each weight changes by the error times its input, and the bias by the error. With integer weights and a learning rate of 1, every number in the run is exact.
AND is linearly separable, so the perceptron convergence theorem promises that a mistake-free pass happens after finitely many updates. The program counts the epochs until a complete pass makes no mistakes, and then prints the weights and the learned truth table. A function that is not linearly separable, such as XOR, would never reach a clean pass.
Explore the dry run
#include <stdio.h> int main(void) { int inputs[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}}; int targets[4] = {0, 0, 0, 1}; int w1 = 0, w2 = 0, bias = 0; int epochs = 0; int mistakes = 1; while (mistakes > 0) { mistakes = 0; for (int i = 0; i < 4; i++) { int sum = w1 * inputs[i][0] + w2 * inputs[i][1] + bias; int output = sum > 0 ? 1 : 0; int error = targets[i] - output; if (error != 0) { w1 += error * inputs[i][0]; w2 += error * inputs[i][1]; bias += error; mistakes++; } } epochs++; } printf("epochs: %d\n", epochs); printf("weights: w1=%d w2=%d bias=%d\n", w1, w2, bias); for (int i = 0; i < 4; i++) { int sum = w1 * inputs[i][0] + w2 * inputs[i][1] + bias; printf("%d AND %d = %d\n", inputs[i][0], inputs[i][1], sum > 0 ? 1 : 0); } return 0;}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| All weights start at zero. | w1 = 0, w2 = 0, bias = 0 | — | |
| 0 if the output is right, +1 if the neuron should have fired, −1 if it should not have. | w1 = 0, w2 = 0, bias = 0 | — | |
| Only inputs that were active change their weights. | w1 = 0, w2 = 0, bias = 0 | — | |
| Repeat full passes until one pass makes no mistakes. | w1 = 0, w2 = 0, bias = 0 | — | |
| The last pass made no mistakes; the sixth pass was the clean one. | w1 = 0, w2 = 0, bias = 0 | epochs: 6 | |
| The weights the learning rule settled on: input (1, 1) gives 2 + 1 − 2 = 1 > 0, while (1, 0) gives 0, which is not above 0. | w1 = 0, w2 = 0, bias = 0 | epochs: 6 weights: w1=2 w2=1 bias=-2 | |
| The learned truth table matches AND. | w1 = 0, w2 = 0, bias = 0 | epochs: 6 weights: w1=2 w2=1 bias=-2 0 AND 0 = 0 0 AND 1 = 0 1 AND 0 = 0 1 AND 1 = 1 |
Cost and common mistakes
O(epochs · n) for n training examples.
- On data that is not linearly separable the loop never ends. Real code limits the number of epochs.
- The condition sum > 0 treats a sum of exactly 0 as output 0. A different convention changes the weights that are learned.
Try it yourself
What happens if you change the targets to {0, 1, 1, 0}?
Reveal answer and reasoning
The loop never terminates, because no weights can separate the XOR cases with a single line.