โจทย์
Momentum makes gradient descent behave like a ball rolling downhill: each step keeps part of the previous one.
Start with a velocity of 0 for every weight. For each step t, with gradient vector g (one value per weight):
- v ← beta × v + g
- w ← w - learning_rate × v
Implement momentum_steps(gradients, weights, learning_rate, beta), applying one update per row of gradients, in order.
Input
gradients: One row per step; each row has one gradient per weight.
weights: The starting weights.
learning_rate: The step size.
beta: The momentum coefficient (0 means plain gradient descent).
Output
Return the weights after all steps.
เงื่อนไข
0 ≤ steps ≤ 1,000, 1 ≤ weights ≤ 100
0 < learning_rate ≤ 1, 0 ≤ beta < 1
-100 ≤ each value ≤ 100
ตัวอย่าง
อินพุต:
beta = 0.9
weights = [0.0]
gradients = [
[1.0],
[1.0],
[1.0]
]
learning_rate = 0.1
ผลลัพธ์ที่คาดหวัง:
expected = [-0.561]อินพุต:
double beta = 0.9;
std::vector<double> weights = {0.0};
std::vector<std::vector<double>> gradients = {
{1.0},
{1.0},
{1.0}
};
double learning_rate = 0.1;
ผลลัพธ์ที่คาดหวัง:
std::vector<double> expected = {-0.561};อินพุต:
double beta = 0.9;
double[] weights = new double[] {0.0};
double[][] gradients = new double[][] {
new double[] {1.0},
new double[] {1.0},
new double[] {1.0}
};
double learning_rate = 0.1;
ผลลัพธ์ที่คาดหวัง:
double[] expected = new double[] {-0.561};คำอธิบาย
The velocity grows 1 → 1.9 → 2.71 because the gradient keeps pointing the same way, so the steps are 0.1, 0.19 and 0.271: w = -0.561.
อินพุต:
beta = 0.0
weights = [1.0, 1.0]
gradients = [
[2.0, -4.0]
]
learning_rate = 0.5
ผลลัพธ์ที่คาดหวัง:
expected = [0.0, 3.0]อินพุต:
double beta = 0.0;
std::vector<double> weights = {1.0, 1.0};
std::vector<std::vector<double>> gradients = {
{2.0, -4.0}
};
double learning_rate = 0.5;
ผลลัพธ์ที่คาดหวัง:
std::vector<double> expected = {0.0, 3.0};อินพุต:
double beta = 0.0;
double[] weights = new double[] {1.0, 1.0};
double[][] gradients = new double[][] {
new double[] {2.0, -4.0}
};
double learning_rate = 0.5;
ผลลัพธ์ที่คาดหวัง:
double[] expected = new double[] {0.0, 3.0};คำอธิบาย
With beta = 0 this is plain gradient descent: w = [1 - 0.5 × 2, 1 - 0.5 × (-4)] = [0, 3].
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
Keep a velocity vector that accumulates part of the previous step and the current gradient.
คำใบ้ 2
Update the velocity before adjusting the weights, and reuse the same velocity across all steps.
คำใบ้ 3
If beta is zero, the method should reduce to ordinary gradient descent, so check that behavior carefully.
ความซับซ้อนที่คาดหวัง
O(s × w) time, O(w) extra space
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน