Problema
Il momentum fa rotolare la discesa del gradiente come una palla in discesa: ogni passo conserva parte del precedente.
Parti da una velocità 0 per ogni peso. Per ogni passo t con vettore gradiente g (un valore per peso):
- v ← beta × v + g
- w ← w - learning_rate × v
Implementa momentum_steps(gradients, weights, learning_rate, beta) applicando un aggiornamento per riga di gradients, in ordine.
Input
gradients: Una riga per passo; ogni riga ha un gradiente per peso.
weights: I pesi iniziali.
learning_rate: La dimensione del passo.
beta: Il coefficiente di momentum (0 dà la discesa del gradiente semplice).
Output
Restituisci i pesi dopo tutti i passi.
Vincoli
0 ≤ passi ≤ 1.000, 1 ≤ pesi ≤ 100
0 < learning_rate ≤ 1, 0 ≤ beta < 1
-100 ≤ ogni valore ≤ 100
Esempi
Input:
beta = 0.9
weights = [0.0]
gradients = [
[1.0],
[1.0],
[1.0]
]
learning_rate = 0.1
Output atteso:
expected = [-0.561]Input:
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;
Output atteso:
std::vector<double> expected = {-0.561};Input:
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;
Output atteso:
double[] expected = new double[] {-0.561};Spiegazione
La velocità cresce 1 → 1.9 → 2.71 perché il gradiente punta sempre nella stessa direzione, quindi i passi sono 0.1, 0.19 e 0.271: w = -0.561.
Input:
beta = 0.0
weights = [1.0, 1.0]
gradients = [
[2.0, -4.0]
]
learning_rate = 0.5
Output atteso:
expected = [0.0, 3.0]Input:
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;
Output atteso:
std::vector<double> expected = {0.0, 3.0};Input:
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;
Output atteso:
double[] expected = new double[] {0.0, 3.0};Spiegazione
Con beta = 0 è la discesa del gradiente semplice: w = [1 - 0.5 × 2, 1 - 0.5 × (-4)] = [0, 3].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Mantieni un vettore di velocità che accumula una parte del passo precedente e del gradiente corrente.
Suggerimento 2
Aggiorna la velocità prima di modificare i pesi, e riusa la stessa velocità in tutti i passi.
Suggerimento 3
Se beta è zero, il metodo deve ridursi alla gradient descent standard, quindi controlla bene quel comportamento.
Complessità attesa
tempo O(s × w), spazio aggiuntivo O(w)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.