Problème
The perceptron (1958) is the first learning algorithm for an artificial neuron. It predicts with a step function and learns from its mistakes.
Start with all weights and the bias at 0. For each epoch, go through the samples in order, and for each sample x with label y (0 or 1):
- prediction = 1 if x · weights + bias > 0, otherwise 0
- error = y - prediction (so -1, 0 or 1)
- If error ≠ 0: weights[i] ← weights[i] + learning_rate × error × x[i] for every i, and bias ← bias + learning_rate × error
Implement train_perceptron(samples, labels, learning_rate, epochs).
Input
samples: m samples with n features each.
labels: The m labels, each 0 or 1.
learning_rate, epochs: The step size and the number of passes over the data.
Output
Return the final weights followed by the bias (n + 1 numbers).
Contraintes
1 ≤ m ≤ 100, 1 ≤ n ≤ 10, 1 ≤ epochs ≤ 100
0 < learning_rate ≤ 1
-10 ≤ each feature ≤ 10
Exemples
Entrée :
epochs = 1
labels = [0, 0, 0, 1]
samples = [
[0.0, 0.0],
[0.0, 1.0],
[1.0, 0.0],
[1.0, 1.0]
]
learning_rate = 1.0
Sortie attendue :
expected = [1.0, 1.0, 1.0]Entrée :
long long epochs = 1;
std::vector<long long> labels = {0, 0, 0, 1};
std::vector<std::vector<double>> samples = {
{0.0, 0.0},
{0.0, 1.0},
{1.0, 0.0},
{1.0, 1.0}
};
double learning_rate = 1.0;
Sortie attendue :
std::vector<double> expected = {1.0, 1.0, 1.0};Entrée :
long epochs = 1;
long[] labels = new long[] {0, 0, 0, 1};
double[][] samples = new double[][] {
new double[] {0.0, 0.0},
new double[] {0.0, 1.0},
new double[] {1.0, 0.0},
new double[] {1.0, 1.0}
};
double learning_rate = 1.0;
Sortie attendue :
double[] expected = new double[] {1.0, 1.0, 1.0};Explication
[0, 0]: z = 0, predicts 0, correct. [0, 1] and [1, 0]: also predict 0, correct. [1, 1]: predicts 0 but the label is 1, so error = 1: weights become [1, 1] and the bias becomes 1. Result: [1, 1, 1].
Entrée :
epochs = 10
labels = [0, 0, 0, 1]
samples = [
[0.0, 0.0],
[0.0, 1.0],
[1.0, 0.0],
[1.0, 1.0]
]
learning_rate = 1.0
Sortie attendue :
expected = [2.0, 1.0, -2.0]Entrée :
long long epochs = 10;
std::vector<long long> labels = {0, 0, 0, 1};
std::vector<std::vector<double>> samples = {
{0.0, 0.0},
{0.0, 1.0},
{1.0, 0.0},
{1.0, 1.0}
};
double learning_rate = 1.0;
Sortie attendue :
std::vector<double> expected = {2.0, 1.0, -2.0};Entrée :
long epochs = 10;
long[] labels = new long[] {0, 0, 0, 1};
double[][] samples = new double[][] {
new double[] {0.0, 0.0},
new double[] {0.0, 1.0},
new double[] {1.0, 0.0},
new double[] {1.0, 1.0}
};
double learning_rate = 1.0;
Sortie attendue :
double[] expected = new double[] {2.0, 1.0, -2.0};Explication
After 10 epochs the perceptron has learned the AND gate: with weights [2, 1] and bias -2, only [1, 1] gives z > 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Process samples in order for each epoch, because earlier updates affect later predictions.
Indice 2
Only update when the predicted class differs from the label, and adjust both weights and bias together.
Indice 3
The prediction rule uses a strict sign test, so a score of zero counts as class 0.
Complexité attendue
O(epochs × m × n) time, O(n) extra space
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.