문제
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).
제약 조건
1 ≤ m ≤ 100, 1 ≤ n ≤ 10, 1 ≤ epochs ≤ 100
0 < learning_rate ≤ 1
-10 ≤ each feature ≤ 10
예시
입력:
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
예상 출력:
expected = [1.0, 1.0, 1.0]입력:
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;
예상 출력:
std::vector<double> expected = {1.0, 1.0, 1.0};입력:
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;
예상 출력:
double[] expected = new double[] {1.0, 1.0, 1.0};설명
[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].
입력:
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
예상 출력:
expected = [2.0, 1.0, -2.0]입력:
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;
예상 출력:
std::vector<double> expected = {2.0, 1.0, -2.0};입력:
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;
예상 출력:
double[] expected = new double[] {2.0, 1.0, -2.0};설명
After 10 epochs the perceptron has learned the AND gate: with weights [2, 1] and bias -2, only [1, 1] gives z > 0.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
Process samples in order for each epoch, because earlier updates affect later predictions.
힌트 2
Only update when the predicted class differs from the label, and adjust both weights and bias together.
힌트 3
The prediction rule uses a strict sign test, so a score of zero counts as class 0.
예상 복잡도
O(epochs × m × n) time, O(n) extra space
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.