AdaGrad(Adaptive Gradient의 약자)는 머신러닝 및 딥러닝에서 각 파라미터에 대해 학습률을 개별적으로 적응시키는 최적화 알고리즘이다. 모든 파라미터에 단일 학습률을 적용하는 표준 확률적 경사 하강법과 달리, AdaGrad는 각 파라미터의 과거 제곱 기울기를 기반으로 해당 파라미터의 업데이트를 조정한다. 이러한 파라미터별 적응을 통해 알고리즘은 드물게 나타나는 파라미터에는 더 큰 업데이트를, 자주 나타나는 파라미터에는 더 작은 업데이트를 수행할 수 있으며, 이는 희소 데이터 환경에서 특히 유용하다. AdaGrad는 2011년 John Duchi, Elad Hazan, Yoram Singer가 도입했으며, 이후 RMSProp 및 Adam과 같은 적응형 최적화 기법 개발의 기초가 되었다.
AdaGrad의 핵심 아이디어는 각 파라미터에 대해 과거 기울기의 제곱 합을 유지하는 것이다. 각 반복에서 파라미터의 학습률은 이 누적 합의 제곱근으로 나뉜다. 이는 과거 기울기가 큰 파라미터는 더 작은 유효 학습률을 받고, 기울기가 작거나 드문 파라미터는 더 큰 유효 학습률을 받는다는 것을 의미한다. 제곱 기울기의 누적은 단조 증가하므로 유효 학습률은 시간이 지남에 따라 감소한다. 이러한 특성은 볼록 설정에서 수렴에 유리할 수 있지만, 비볼록 문제에서는 과도하게 급격한 감소를 초래할 수 있으며, 이는 이후 알고리즘 개발의 동기가 되었다.
배경
머신러닝의 최적화는 종종 각 예제별 손실 함수의 합인 목적 함수를 최소화하는 것을 포함한다. n개의 예제로 구성된 훈련 세트의 경우, 경험적 위험은 Q(w) = (1/n) Σ Q_i(w)로 주어지며, 여기서 w는 파라미터 벡터이고 Q_i는 i번째 예제의 손실이다. 표준 경사 하강법은 각 단계에서 전체 합의 기울기를 계산하므로 n이 클 때 계산 비용이 많이 들 수 있다. 확률적 경사 하강법(SGD)은 대신 단일 샘플 또는 미니 배치를 사용하여 기울기를 근사하므로 반복당 계산 비용을 줄이지만 노이즈를 도입한다. 1950년대의 Robbins-Monro 알고리즘은 확률적 근사의 기초를 마련했으며, SGD는 대규모 데이터셋에서의 효율성 덕분에 머신러닝의 핵심 기법이 되었다.
SGD에서 업데이트 규칙은 w := w - η ∇Q_i(w)이며, 여기서 η는 학습률이다. 고정 학습률을 선택하는 것은 종종 최적이 아니다. 너무 큰 학습률은 발산을 유발할 수 있고, 너무 작은 학습률은 수렴을 느리게 한다. AdaGrad와 같은 적응형 방법은 최적화 지형의 기하학적 구조에 따라 학습률을 조정하여 이 문제를 해결하고자 한다. AdaGrad의 동기는 특히 일부 파라미터가 드물게 업데이트되는 희소 특성 문제에서 서로 다른 파라미터가 서로 다른 단계 크기를 요구할 수 있다는 관찰에서 비롯되었다.
알고리즘
AdaGrad는 SGD 업데이트를 수정하여 대각 행렬 G_t를 유지하며, 여기서 각 대각 요소는 해당 파라미터의 과거 제곱 기울기의 합이다. 시간 단계 t에서 파라미터 w_i의 업데이트는 다음과 같다:
w_i := w_i - (η / sqrt(G_{t,ii} + ε)) ∇Q_i(w_i),
여기서 ε는 0으로 나누는 것을 방지하기 위한 작은 상수(예: 1e-8)이다. 누적된 기울기 제곱 G_{t,ii} = Σ_{τ=1}^{t} (∇Q_i(w_τ))^2이다. 이는 벡터 형태로 다음과 같이 쓸 수 있다:
w := w - η * diag(G_t + εI)^{-1/2} ∇Q(w).
실제로 이 알고리즘은 종종 미니 배치에 적용되며, 여기서 기울기는 훈련 예제의 부분 집합에 대해 계산된다. 따라서 파라미터별 학습률은 η_t,i = η / sqrt(G_{t,ii} + ε)이다. G_t가 시간이 지남에 따라 증가하므로 유효 학습률은 감소하여 알고리즘이 진행됨에 따라 더 작은 단계를 수행한다. 이는 일관된 방향으로 가속하기 위해 기울기를 누적하는 모멘텀을 사용하는 SGD와 대조적이다.
수학적 특성
AdaGrad는 원래 볼록 최적화 맥락에서 분석되었다. 저자들은 볼록 함수에 대해 AdaGrad가 온라인 학습에서 점근적으로 최적의 후회(regret) 한계를 달성함을 보여주었다. 구체적으로, 알고리즘의 손실과 사후 최적 고정 파라미터 간의 누적 차이를 측정하는 후회는 AdaGrad에서 O(√T)로 증가하며, 이는 온라인 볼록 최적화의 하한과 일치한다. 이는 학습률 스케줄의 세심한 조정이 필요할 수 있는 고정 학습률을 사용하는 표준 SGD보다 개선된 것이다.
핵심 통찰은 AdaGrad가 특성 공간의 기하학적 구조에 자동으로 적응한다는 것이다. 희소 설정에서 많은 특성이 대부분의 예제에서 0인 경우 해당 특성의 누적 기울기는 작게 유지되므로, 해당 특성이 나타날 때 더 큰 업데이트가 가능하다. 이는 AdaGrad를 자연어 처리 및 고차원 희소 입력이 있는 다른 영역에서 특히 효과적으로 만든다.
그러나 제곱 기울기의 누적은 단조 증가하므로 학습률은 시간이 지남에 따라 0으로 감소한다. 깊은 신경망 훈련과 같은 비볼록 문제에서는 이로 인해 알고리즘이 조기에 학습을 중단할 수 있다. 이러한 한계는 제곱 기울기의 합 대신 이동 평균을 사용하는 RMSProp과 적응형 학습률과 모멘텀을 결합한 Adam과 같은 변형의 개발로 이어졌다.
응용
AdaGrad는 특히 희소 데이터를 포함하는 다양한 머신러닝 작업에 적용되었다. 자연어 처리에서는 각 문서가 단어 빈도의 희소 벡터로 표현되는 bag-of-words 특성에 대한 모델 훈련에 사용되었다. 파라미터별 적응을 통해 희귀 단어가 더 큰 업데이트를 받을 수 있어 드물지만 정보가 풍부한 특성에서 학습하는 모델의 능력이 향상된다.
추천 시스템에서 AdaGrad는 희소 상호작용 데이터를 기반으로 사용자 및 항목 임베딩이 업데이트되는 행렬 분해 모델을 최적화하는 데 사용되었다. 사용자-항목 쌍의 다양한 빈도를 처리하는 알고리즘의 능력은 이러한 설정에 적합하다. 또한 AdaGrad는 데이터가 순차적으로 도착하고 모델이 빠르게 적응해야 하는 온라인 학습 시나리오에서도 사용되었다.
많은 딥러닝 응용에서 더 고급 최적화 기법으로 대체되었음에도 불구하고, AdaGrad는 비교를 위한 벤치마크로 남아 있으며 그 특성이 유리한 일부 영역에서 여전히 사용된다. 그 영향은 파라미터별 학습률 아이디어를 기반으로 하는 이후 적응형 방법의 설계에서 분명하게 나타난다.
한계 및 확장
AdaGrad의 주요 한계는 단조 감소하는 학습률이다. 손실 지형이 비볼록인 딥러닝에서는 이로 인해 수렴이 느려지거나 좋지 않은 지역 최소값에 갇힐 수 있다. 이를 해결하기 위해 연구자들은 여러 확장을 제안했다:
- RMSProp: Geoffrey Hinton의 강의 노트에서 소개된 RMSProp은 제곱 기울기의 지수 감쇠 이동 평균을 사용하여 학습률이 더 유연하게 적응할 수 있게 한다.
- Adam: 2014년 Diederik Kingma와 Jimmy Ba가 제안한 Adam은 RMSProp의 이동 평균과 모멘텀을 결합하여 적응형 학습률과 모멘텀을 모두 제공한다.
- AdaDelta: Matthew Zeiler가 개발한 AdaDelta는 과거 기울기의 창을 사용하여 학습률 하이퍼파라미터의 필요성을 제거한다.
이러한 알고리즘은 깊은 신경망 훈련의 기본 선택이 되었지만, 모두 AdaGrad가 도입한 적응형 기울기 개념에 뿌리를 두고 있다.
영향 및 유산
AdaGrad는 머신러닝 최적화 분야에 지속적인 영향을 미쳤다. 파라미터별 학습률을 사용한 최초의 널리 채택된 알고리즘 중 하나로, 적응형 최적화 기법 계열의 길을 열었다. 볼록 설정에서의 이론적 보장은 적응형 방법을 이해하는 데 견고한 기초를 제공했다. 이 알고리즘은 교과서와 연구 논문에서 최적화 역사의 핵심 발전으로 자주 인용된다.
실제로 AdaGrad는 오늘날 대규모 딥러닝 모델 훈련에는 덜 일반적으로 사용되며, Adam 및 그 변형이 더 나은 성능을 보이는 경향이 있다. 그러나 희소 특성이 있는 문제와 같은 특정 문제에는 여전히 유용한 도구로 남아 있으며, 머신러닝 과정에서 중요한 개념적 단계로 여전히 가르쳐진다.