Problema
O momentum faz a descida de gradiente rolar como uma bola ladeira abaixo: cada passo mantém parte do anterior.
Comece com velocidade 0 para cada peso. Para cada passo t com vetor de gradiente g (um valor por peso):
- v ← beta × v + g
- w ← w - learning_rate × v
Implemente momentum_steps(gradients, weights, learning_rate, beta) aplicando uma atualização por linha de gradients, em ordem.
Entrada
gradients: Uma linha por passo; cada linha tem um gradiente por peso.
weights: Os pesos iniciais.
learning_rate: O tamanho do passo.
beta: O coeficiente de momentum (0 dá a descida de gradiente simples).
Saída
Retorne os pesos após todos os passos.
Restrições
0 ≤ passos ≤ 1.000, 1 ≤ pesos ≤ 100
0 < learning_rate ≤ 1, 0 ≤ beta < 1
-100 ≤ cada valor ≤ 100
Exemplos
Entrada:
beta = 0.9
weights = [0.0]
gradients = [
[1.0],
[1.0],
[1.0]
]
learning_rate = 0.1
Saída esperada:
expected = [-0.561]Entrada:
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;
Saída esperada:
std::vector<double> expected = {-0.561};Entrada:
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;
Saída esperada:
double[] expected = new double[] {-0.561};Explicação
A velocidade cresce 1 → 1.9 → 2.71 porque o gradiente continua apontando na mesma direção, então os passos são 0.1, 0.19 e 0.271: w = -0.561.
Entrada:
beta = 0.0
weights = [1.0, 1.0]
gradients = [
[2.0, -4.0]
]
learning_rate = 0.5
Saída esperada:
expected = [0.0, 3.0]Entrada:
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;
Saída esperada:
std::vector<double> expected = {0.0, 3.0};Entrada:
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;
Saída esperada:
double[] expected = new double[] {0.0, 3.0};Explicação
Com beta = 0 é a descida de gradiente simples: w = [1 - 0.5 × 2, 1 - 0.5 × (-4)] = [0, 3].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Mantenha um vetor de velocity que acumula parte do passo anterior e o gradiente atual.
Dica 2
Atualize a velocity antes de ajustar os pesos e reutilize a mesma velocity em todos os passos.
Dica 3
Se beta for zero, o método deve virar gradient descent comum, então verifique esse comportamento com cuidado.
Complexidade esperada
tempo O(s × w), espaço extra O(w)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.