AdaGrad

• Deep Learning 책 참고 299page
• An overview of gradient descent optimization algorithms

Stochastic Gradient Descent (SGD)는 convex 또는 non-convex function의 optimization에 일반적으로 사용되는 알고리즘입니다.
SGD의 한가지 문제점은 learning rate에 매우 민감합니다. 특히 데이터가 sparse이며 features가 서로다른 frequencies (빈도수)를 갖고 있다면, 단 하나의 learning rate가 모든 weight update에 영향을 주는것은 문제가 될 수 있습니다.

이전의 Momentum update에서는 다음과 같은 공식을 사용했습니다.

v=γvt−1+η∇θJ(θ;x(i),y(i))θ=θ−vv=γvt−1+η∇θJ(θ;x(i),y(i))θ=θ−v

즉 모든 weights θθ에 대해서 동일한 learning rate ηη 를 사용하여 update를 하였습니다.

AgaGrad는 각각의 데이터에 dynamically adapt함으로서 궁극적으로 각각의 feature들마다 서로다른 learning rate로 연산을 합니다.

gt,i=∇θJ(θi)gt,i=∇θJ(θi)

이렇게 해주기 위해서는.. 실제로는 sum을 제거해야 합니다.
2N∑y−^y2N∑y−y^
이게 아니고 2Ny−^y2Ny−y^ 
즉 weight값의 gradient값을 구하는게 아니라, 각각 weight element θiθi 들의 gradient gt,igt,i 값을 구해야 합니다.

쉽게 이야기해서, 빈도수가 낮은 데이터에는 높은 learning rate를 적용하고, 빈도수가 높은 데이터에는 낮은 learning rate를 자동으로 적용합니다. 
따라서 sparse한 데이터에 적합하며, 대표적인 예가 구글 X lab에서 16000대의 cores를 사용하여 유튜브 동영상안의 고양이를 detection하는 모델에 Adagrad를 사용한것입니다.

• Global Learning Rate ηη 가 필요합니다.
• weights θθ에 대한 초기화가 필요합니다.
• small constant ϵϵ 값을 설정합니다. (numerical stability를 위해서 약 10−810−8로 설정, 즉 분모에 들어가게 되는데 0이 안되도록 매우 작은 수를 넣음)
• gradient accumulation variable GG값은 weight와 동일한 shape인 0으로 초기화합니다.

먼저 gradient를 구한뒤 sqaured gradient (gradient의 제곱)을 r에 accumulation해줍니다.

gt=∇θJ(θ;x(i),y(i))Gt=Gt+gt⊙gtgt=∇θJ(θ;x(i),y(i))Gt=Gt+gt⊙gt

update를 계산합니다.

Δθt=ηϵ+√Gt⊙gtΔθt=ηϵ+Gt⊙gt

update를 적용합니다.

θt+1=θt−Δθtθt+1=θt−Δθt

⊙⊙ 기호는 element wise multiplication 입니다

AdaGrad의 장점은 보통 다른 optimizers의 경우에는 learning rate를 일반적으로 0.01로 놓고 변경되지 않지만, Adagram같은 경우는 자동으로 learning rate를 계산해준다는 것입니다. 반면 약점은 denominator부분의 accumulation of the squared gradients의 값이 지속적으로 쌓여서 계속 늘어난다는 단점이 있습니다. 결국 learning rate는 점점 작아진다는 약점을 갖고있습니다. 이러한 약점은 극복한 것이 Adadelta입니다.

 

출처 - http://incredible.ai/artificial-intelligence/2017/04/09/Optimizer-Adagrad/