โจทย์
เพอร์เซปตรอน (1958) คืออัลกอริทึมการเรียนรู้แรกสำหรับนิวรอนเทียม มันทำนายด้วยฟังก์ชันขั้นบันไดและเรียนรู้จากความผิดพลาด
เริ่มด้วยน้ำหนักและไบแอสทั้งหมดเป็น 0 ในแต่ละ epoch ให้ไล่ตัวอย่าง ตามลำดับ และสำหรับแต่ละตัวอย่าง x ที่มีป้ายกำกับ y (0 หรือ 1):
- การทำนาย = 1 ถ้า x · weights + bias > 0 ไม่เช่นนั้น 0
- error = y - การทำนาย (คือ -1, 0 หรือ 1)
- ถ้า error ≠ 0: weights[i] ← weights[i] + learning_rate × error × x[i] สำหรับทุก i และ bias ← bias + learning_rate × error
จงเขียน train_perceptron(samples, labels, learning_rate, epochs)
อินพุต
samples: ตัวอย่าง m ตัว แต่ละตัวมีฟีเจอร์ n ตัว
labels: ป้ายกำกับ m ค่า แต่ละค่าเป็น 0 หรือ 1
learning_rate, epochs: ขนาดก้าวและจำนวนรอบที่วนผ่านข้อมูล
เอาต์พุต
คืนค่าน้ำหนักสุดท้าย ตามด้วยไบแอส (n + 1 ค่า)
เงื่อนไข
1 ≤ m ≤ 100, 1 ≤ n ≤ 10, 1 ≤ epochs ≤ 100
0 < learning_rate ≤ 1
-10 ≤ แต่ละฟีเจอร์ ≤ 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 ทำนาย 0 ถูก [0, 1] และ [1, 0]: ทำนาย 0 เช่นกัน ถูก [1, 1]: ทำนาย 0 แต่ป้ายกำกับเป็น 1 จึงได้ error = 1: น้ำหนักกลายเป็น [1, 1] และไบแอสเป็น 1 ผลลัพธ์: [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};คำอธิบาย
หลังจาก 10 epoch เพอร์เซปตรอนเรียนรู้เกต AND ได้แล้ว: ด้วยน้ำหนัก [2, 1] และไบแอส -2 มีเพียง [1, 1] ที่ให้ z > 0
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ประมวลผล sample ตามลำดับในแต่ละ epoch เพราะการอัปเดตต้นๆ มีผลต่อการทำนายตัวถัดไป
คำใบ้ 2
อัปเดตเฉพาะเมื่อคลาสที่ทำนายต่างจาก label และปรับ weights กับ bias พร้อมกัน
คำใบ้ 3
กฎการทำนายใช้การทดสอบด้วย sign แบบเข้มงวด ดังนั้น score ที่เป็นศูนย์นับเป็น class 0
ความซับซ้อนที่คาดหวัง
เวลา O(epochs × m × n), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน