Stochastic Parallel Gradient Descent method

SPGD알고리즘은 함수 최적화를 할 때 사용하는 알고리즘이다. 기존의 Steepest descent method라든가 Conjugate Gradient method같은 경우, 특정 방향에 대해서 최적해를 찾고 그 위치에서 그 다음으로 진행할 방향을 선택해서 더이상 움직이지 않을 때 까지 반복하는 알고리즘이다. 두 방법의 차이는 그 다음 방향을 결정하는데 좀 더 개선된 방법이냐 아니냐의 차이가 있을 뿐이다.

SPGD알고리즘은 통계적으로 접근하는데, 덕분에 빠른 최적화가 가능하다. 수학적, 통계학적인 이야기는 다 빼고 알고리즘만 설명하도록 한다. 자세한 것은 구글에 검색하면 다 나올 것이다.

어떤 함수 V(x)가 주어져 있다. V(x)는 하나의 실수값을 갖고, x는 N차원에서의 벡터이다. g는 0이 아닌 어떤 실수인 상수인데, 이따가 설명하도록 하겠다.

1. x에 대해서 어떤 임의의 벡터 a를 선택한다.

2. P=V(x+a), Q=V(x-a)를 계산한다.

3. P-Q=R을 얻을 수 있을 것이다.

4. x를 x+g*R*a로 교체하고 1번으로 돌아가서 반복한다.

5. 더이상 움직이지 않을 때 까지(==V(x)와 V(x+g*R*a)가 별로 차이가 없을 때 까지) 반복한다.

이 알고리즘이 작동하는 이유는 R=P-Q이기 때문이다. g>0인 경우에 만약 P가 더 크다면 R>0이므로 벡터가 x+a방향으로 움직이게 된다. 만약 Q가 더 크다면 R<0이므로 벡터가 x-a방향으로 움직이게 된다. 여기서 g>0이면 V가 커지는 방향으로 최적화가 이루어지고, g<0이면 V가 작아지는 방향으로 최적화가 이루어진다.

a자체는 임의로 고르지만 대체로 난수 함수가 0~1사이에서 하나를 고르게 되어 있으므로 a의 최대 크기는 제한적일 것이다. 만약 V가 엄청 큰 공간에서 최적화 해야 하는 경우라면, 이것은 너무 느릴 수 있을 것이다. 따라서 g가 충분히 큰 숫자가 되어야 한번에 멀리 갈 것이다. 내가 봤던 논문에서는 최대화 하는 경우 g를 한 스텝 지나갈 때 마다 g/V로 교체하고, 최소화 하는 경우 g를 한 스텝 지나갈 때 마다 g*V로 교체하는 것을 보았다.

실제로 계산에 적용해보면 g/V나 g*V를 그냥 두면 스텝 수가 너무 많아지는 경우 g값이 무한대로 발산하거나, 무한소로 수렴한다. 무한대가 되는 경우 컴퓨터 계산 범위를 넘어가므로 오류가 발생하고, 무한소가 되는 경우 0이 되어 버리므로 아예 움직이지 않게 된다. 따라서 이런 경우를 방지하기 위해 알고리즘을 구현하는 과정에서 적절한 수준에서 크기를 재조절 해주어야 한다.

이렇게 했어도 결국 최적화 지점 근처에서 한번에 너무 멀리 가버리면 망하는데, 그래서 a에 R을 곱해주는 것이다. R의 부호는 최적화 방향을 결정하고, R의 크기는 한 스텝의 크기를 조절한다. R은 최적화 지점에 가까워질 수록 그 크기가 작아지므로 최적화 지점 근처에서 천천히 움직이게 해 준다. 또한, 실수로 너무 멀리갔을 경우 다시 무작위로 크게 움직이도록 하므로 최적화 속도를 빠르게 할 수 있다.

이 알고리즘의 수렴성은 통계적으로 보장된다. 즉, 무한히 오래 돌리면 반드시 최적점에 수렴한다. 하지만 이것은 반대로 문제가 되는 부분이기도 한데, R의 크기가 계속해서 작아지므로 수렴 속도가 점점 느려진다. 그래서 최적점 근처에서 "운이 좋아서" 최적점에 매우 가까운 점으로 뛰어들지 않는다면 계속해서 최적점 근처에서 헤메고 다닐 수 있다.