문제
Adam은 가중치마다 기울기(m)와 기울기 제곱(v)의 두 가지 이동 평균을 유지하고, 이를 이용해 가중치마다 고유한 학습 보폭을 줍니다.
모든 가중치에 대해 m = 0, v = 0으로 시작합니다. 기울기 g를 가진 각 단계 t = 1, 2, 3, …에 대해:
- m ← beta1 × m + (1 - beta1) × g
- v ← beta2 × v + (1 - beta2) × g²
- m̂ = m / (1 - beta1ᵗ), v̂ = v / (1 - beta2ᵗ) (편향 보정)
- w ← w - learning_rate × m̂ / (√v̂ + epsilon)
adam_steps(gradients, weights, learning_rate, beta1, beta2, epsilon)를 구현하고, gradients의 각 행마다 한 번씩 순서대로 갱신하세요.
입력
gradients: 단계마다 한 행; 각 행은 가중치마다 하나의 기울기를 가집니다.
weights: 초기 가중치.
learning_rate, beta1, beta2, epsilon: Adam의 하이퍼파라미터 (보통 0.001, 0.9, 0.999, 0.00000001).
출력
모든 단계 후의 가중치를 반환하세요.
제약 조건
0 ≤ 단계 수 ≤ 1,000, 1 ≤ 가중치 수 ≤ 100
0 < learning_rate ≤ 1, 0 ≤ beta1, beta2 < 1, 0 < epsilon ≤ 0.001
-100 ≤ 각 값 ≤ 100
예시
입력:
beta1 = 0.9
beta2 = 0.999
epsilon = 1.0e-08
weights = [1.0]
gradients = [
[2.0]
]
learning_rate = 0.1
예상 출력:
expected = [0.9]입력:
double beta1 = 0.9;
double beta2 = 0.999;
double epsilon = 1.0e-08;
std::vector<double> weights = {1.0};
std::vector<std::vector<double>> gradients = {
{2.0}
};
double learning_rate = 0.1;
예상 출력:
std::vector<double> expected = {0.9};입력:
double beta1 = 0.9;
double beta2 = 0.999;
double epsilon = 1.0e-08;
double[] weights = new double[] {1.0};
double[][] gradients = new double[][] {
new double[] {2.0}
};
double learning_rate = 0.1;
예상 출력:
double[] expected = new double[] {0.9};설명
m = 0.1 × 2 = 0.2, v = 0.001 × 4 = 0.004. 편향 보정으로 m̂ = 0.2 / 0.1 = 2, v̂ = 0.004 / 0.001 = 4가 되어 보폭은 0.1 × 2 / √4 = 0.1입니다: w = 0.9. 첫 단계에서 Adam은 기울기 크기와 관계없이 각 가중치를 학습률만큼 움직입니다.
입력:
beta1 = 0.9
beta2 = 0.999
epsilon = 1.0e-08
weights = [0.0, 0.0]
gradients = [
[100.0, 0.01]
]
learning_rate = 0.01
예상 출력:
expected = [-0.01, -0.01]입력:
double beta1 = 0.9;
double beta2 = 0.999;
double epsilon = 1.0e-08;
std::vector<double> weights = {0.0, 0.0};
std::vector<std::vector<double>> gradients = {
{100.0, 0.01}
};
double learning_rate = 0.01;
예상 출력:
std::vector<double> expected = {-0.01, -0.01};입력:
double beta1 = 0.9;
double beta2 = 0.999;
double epsilon = 1.0e-08;
double[] weights = new double[] {0.0, 0.0};
double[][] gradients = new double[][] {
new double[] {100.0, 0.01}
};
double learning_rate = 0.01;
예상 출력:
double[] expected = new double[] {-0.01, -0.01};설명
두 기울기는 10,000배 차이가 나지만 두 가중치 모두 약 0.01씩 움직여 [-0.01, -0.01]이 됩니다: Adam은 각 단계를 해당 기울기 자신의 크기로 조정합니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
각 weight마다 gradient 방향과 제곱 크기를 나타내는 두 개의 moving average를 추적하세요.
힌트 2
분모의 square root term으로 나누기 전에, 현재 step number를 써서 bias correction을 적용하세요.
힌트 3
분모의 epsilon을 주의하세요. division by zero를 막고 최종 update도 조금 바꿉니다.
예상 복잡도
시간 O(s × w), 추가 공간 O(w)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.