Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Perceptron Learning Algorithm

Train the original perceptron, which updates its weights only when it makes a mistake.

Bạn sẽ học được gì

  • Update weights only on mistakes
  • Train over several epochs
  • Learn how the first neural model worked

Đề bài

Xem bản dịch

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):

  1. prediction = 1 if x · weights + bias > 0, otherwise 0
  2. error = y - prediction (so -1, 0 or 1)
  3. 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).

Ràng buộc

1 ≤ m ≤ 100, 1 ≤ n ≤ 10, 1 ≤ epochs ≤ 100

0 < learning_rate ≤ 1

-10 ≤ each feature ≤ 10

Ví dụ

Ví dụ 1
Đầu vào:
samples = [
    [0.0, 0.0],
    [0.0, 1.0],
    [1.0, 0.0],
    [1.0, 1.0]
]
labels = [0, 0, 0, 1]
learning_rate = 1.0
epochs = 1

Kết quả mong đợi:
expected = [1.0, 1.0, 1.0]
Đầu vào:
std::vector<std::vector<double>> samples = {
    {0.0, 0.0},
    {0.0, 1.0},
    {1.0, 0.0},
    {1.0, 1.0}
};
std::vector<long long> labels = {0, 0, 0, 1};
double learning_rate = 1.0;
long long epochs = 1;

Kết quả mong đợi:
std::vector<double> expected = {1.0, 1.0, 1.0};
Đầu vào:
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}
};
long[] labels = new long[] {0, 0, 0, 1};
double learning_rate = 1.0;
long epochs = 1;

Kết quả mong đợi:
double[] expected = new double[] {1.0, 1.0, 1.0};

Giải thích

[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].

Ví dụ 2
Đầu vào:
samples = [
    [0.0, 0.0],
    [0.0, 1.0],
    [1.0, 0.0],
    [1.0, 1.0]
]
labels = [0, 0, 0, 1]
learning_rate = 1.0
epochs = 10

Kết quả mong đợi:
expected = [2.0, 1.0, -2.0]
Đầu vào:
std::vector<std::vector<double>> samples = {
    {0.0, 0.0},
    {0.0, 1.0},
    {1.0, 0.0},
    {1.0, 1.0}
};
std::vector<long long> labels = {0, 0, 0, 1};
double learning_rate = 1.0;
long long epochs = 10;

Kết quả mong đợi:
std::vector<double> expected = {2.0, 1.0, -2.0};
Đầu vào:
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}
};
long[] labels = new long[] {0, 0, 0, 1};
double learning_rate = 1.0;
long epochs = 10;

Kết quả mong đợi:
double[] expected = new double[] {2.0, 1.0, -2.0};

Giải thích

After 10 epochs the perceptron has learned the AND gate: with weights [2, 1] and bias -2, only [1, 1] gives z > 0.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Process samples in order for each epoch, because earlier updates affect later predictions.

Gợi ý 2

Only update when the predicted class differs from the label, and adjust both weights and bias together.

Gợi ý 3

The prediction rule uses a strict sign test, so a score of zero counts as class 0.

Độ phức tạp mong đợi

O(epochs × m × n) time, O(n) extra space

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.