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

Thuật toán học perceptron

Huấn luyện perceptron nguyên bản, chỉ cập nhật trọng số khi dự đoán sai.

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

  • Chỉ cập nhật trọng số khi sai
  • Huấn luyện qua nhiều epoch
  • Biết mô hình nơ-ron đầu tiên hoạt động ra sao

Đề bài

Xem bản gốc (English)

Perceptron (1958) là thuật toán học đầu tiên cho một nơ-ron nhân tạo. Nó dự đoán bằng hàm bậc thang và học từ những lần sai.

Bắt đầu với mọi trọng số và bias bằng 0. Ở mỗi epoch, duyệt các mẫu theo thứ tự, và với mỗi mẫu x có nhãn y (0 hoặc 1):

  1. dự đoán = 1 nếu x · weights + bias > 0, ngược lại 0
  2. error = y - dự đoán (tức là -1, 0 hoặc 1)
  3. Nếu error ≠ 0: weights[i] ← weights[i] + learning_rate × error × x[i] với mọi i, và bias ← bias + learning_rate × error

Hãy cài đặt train_perceptron(samples, labels, learning_rate, epochs).

Đầu vào

samples: m mẫu, mỗi mẫu n đặc trưng.

labels: m nhãn, mỗi nhãn là 0 hoặc 1.

learning_rate, epochs: Bước nhảy và số lượt duyệt qua dữ liệu.

Đầu ra

Trả về các trọng số cuối cùng, tiếp theo là bias (n + 1 số).

Ràng buộc

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

0 < learning_rate ≤ 1

-10 ≤ mỗi đặc trưng ≤ 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, dự đoán 0, đúng. [0, 1] và [1, 0]: cũng dự đoán 0, đúng. [1, 1]: dự đoán 0 nhưng nhãn là 1, nên error = 1: trọng số thành [1, 1] và bias thành 1. Kết quả: [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

Sau 10 epoch, perceptron đã học được cổng AND: với trọng số [2, 1] và bias -2, chỉ [1, 1] cho 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

Xử lý các mẫu theo thứ tự ở mỗi epoch, vì cập nhật sớm sẽ ảnh hưởng đến dự đoán sau.

Gợi ý 2

Chỉ cập nhật khi lớp dự đoán khác nhãn, và điều chỉnh cả weights lẫn bias cùng lúc.

Gợi ý 3

Quy tắc dự đoán dùng phép kiểm tra dấu chặt, nên score bằng 0 được tính là class 0.

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

thời gian O(epochs × m × n), bộ nhớ phụ O(n)

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.