달고나 36. 최적화 알고리즘
Overview of Optimization for ML
누군가 '인생은 속도보다 방향이 중요하다'라고 말하면 이과생이 등장해서 '속도는 벡터로 이미 방향을 포함한 값이므로 속도가 아니라 속력이다'라고 정정할 거다. 정의상 속도는 힘의 방향과 크기가 결합된 벡터, 즉 '속도 = 방향 + 속력'이다. 늦게라도 언젠가는 원하는 목표를 이룬 사람들을 보면 인생에서 방향이 더 중요한 듯하다가도 빠르고 민첩하면 더 이르게 성공하거나 (비록) 실패하더라도 아직 젊으니 새로운 도전을 할 수 있어 속력이 더 중요한 듯하기도 하다. 사람마다 가치관과 방식에 따라 방향이든 속력이든 각자 사정에 맞게 잘 조절하면 된다. 어쨌든 인생에서 방향과 속력이 모두 중요하듯이 최적화도 방향과 속력이 중요하다.
머신러닝 모델을 최적화하는 방법은 이 논문 (An Overview of Gradient Descent Optimization Algorithms)을 참조하면 현재 많이 사용하는 대부분의 알고리즘과 발전 과정을 알 수 있다. 이 글은 논문을 좀 더 쉽게 이해하도록 최적화 방식을 개념적으로 설명한다. Gradient Descent를 설명한 아래 그림은 이미 익숙할 테니 자세한 설명은 생략한다.
Online Gradient Descent그림에 있는 수식에서 중요한 부분은 '- Eta * Gradient'인데, 방향은 '마이너스 그래디언트'이고 속력은 '에타'다. 즉, 글로벌 옵티멈 (W*)를 빠르게 찾기 위해서 중요한 방향은 loss 함수의 미분 값의 역방향이고, 속력은 learning rate인 에타인 조절한다. Loss 함수를 미분하고 적당한 러닝 레이트만 구하면 최적의 모델 파라미터를 찾을 수 있다는 거다. 정확하고 빠르게 최적 값을 찾기 위해서 논문에 소개된 다양한 최적화 알고리즘들이 제안됐다.
방향은 쉽다. 그냥 미분 값을 구해서 역방향(-)으로 설정하면 된다. Loss 함수가 복잡하거나 불연속 또는 미분 불가여서 미분이 쉽지 않을 수는 있으나 일단 미분이 가능하면 방향은 쉽게 찾을 수 있다. 위 그림에서 붉은 화살표처럼 '위'로 향하기 때문에 음의 방향 (현재 값의 왼쪽)에 Wt+1이 위치한다. 현재 값 Wt가 그림의 왼쪽에 있었다면 화살표는 아래로 향했을 테고, 그래서 Wt+1이 현재보다 오른쪽인 양의 방향에 위치한다. 그런데 이걸 3차원에서 보면 양상이 조금 달라진다. Gradient 방식에서 Steepest Descent라는 용어를 들어봤을 텐데, 가장 경사가 심한 (steepest) 방향을 선택한다는 거다. 말로 설명하긴 조금 까다롭지만 이 steepest 방향이 2D 그림에서와는 달리 글로벌 옵티멈이 있는 방향을 정확히 가리키지 않는다. 산에서 물이 흐르는 골짜기를 따라서 쭉 내려오면 가장 낮은 지점 (글로벌 옵티멈)에 도달할 수 있다.(물론 산에서 길을 잃었을 때는 위로 올라가야 한다.) 그런데 현재 산등성에 있다면 가장 가파른 방향은 전체에서 가장 낮은 지점이 아니라 가까운 골짜기 쪽이다. 논문에서 Momentum을 설명하는 그림을 보면 도움 될 텐데, 글로벌 옵티멈과는 다소 차이가 있는 방향으로 계속 oscillate 하는 걸 볼 수 있다. 모멘텀은 미분의 (역) 방향에 글로벌 옵티멈 방향을 보정해서 더 빨리 최적 값으로 찾아가도록 유도한다.
논문에 소개된 알고리즘의 관계/개념도 (틀렸을 수 있음)방향이 정해지면 이제 learning rate (에타)를 정하면 된다. 그냥 한 스텝만으로 글로벌 옵티멈에 이르면 좋겠지만 시작점 (random initialization)이 모두 다르고 복잡한 목적식에서 어디가 옵티멈인지 모르니 가능한 빠르고 정확하게 수렵하도록 하는 알고리즘들이 제안됐다. 이론상으론 quasi-Newton Method를 사용하면 가장 빠르게 최적 지점을 찾아가지만, 이차 편미분으로 구성된 Hessian 행열의 역행열을 계산하는 것이 쉽지 않다. 특히 피쳐/변수가 많을 경우 역행열 계산이 사실상 불가능하다. (참고. 매번 역행열을 계산하는 대신 애초에 역행열을 업데이트하는 방식도 있다.) 그래서 다양한 휴리스틱으로 러닝 레이트를 정하는 알고리즘들이 등장했다.
먼저 러닝 레이트가 상수로 고정된 것을 생각해보자. 힘 조절을 할 수 없어서 매번 일정한 거리만큼만 공을 던지는 두 사람이 있다고 하자. 한 명은 무조건 0.1m만 던질 수 있고 (A), 다른 이는 10m만 던질 수 있다 (B). 만약 '73.6m' 지점에 공을 갖다 놔야 한다면 어떻게 될까? A는 736번을 던저서 목표 지점에 도착한다. B는 7번만 던져도 목표 지점 근처에 도달하지만 목표 지점에 정확히 공을 갖다 놓을 수 없다. 러닝 레이트가 일정할 때, 에타 값이 너무 작으면 목표 지점까지 수렴하는데 시간이 오래 걸리고, 에타 값이 너무 크면 목표 지점을 정확히 맞추지 못하고 왔다 갔다 한다. 그래서 등장한 방식이 처음에는 에타 값을 크게 하고, 차츰 회수/시간이 증가함에 따라서 에타 값을 줄이는 전략을 취했다. 즉, 목적지에 가까워질수록 속력을 차츰 줄이는 거다. 그래서 '에타 / t' 또는 '에타 / sqrt(t)' 방식이 최근까지 주로 사용됐다.
1/t 또는 1/sqrt(t)가 너무 기계적이고 데이터에 따라서 성능도 썩 마음에 들지 않는다. 하지만 이런 시간 (회수)에 따라서 러닝 레이트를 조절하는 아이디어는 여전히 유효하다. 시작부터 현재까지 구했던 그래디언트 값을 활용하자는 아이디어로 제안된 방식이 AdaGrad다. 그런데 AdaGrad는 이제까지의 모든 그래디언트를 저장해서 계산해야 하는 귀찮음이 있어서 그냥 최근 그래디언트만 사용하거나 이전 단계에서 구한 값과 마지막 그래디언트의 가중 평균을 취하는 AdaDelta (또는 RMSProp) 방식이 뒤이어 등장했다. 여기에 모멘텀의 개념을 결합해서 -- 현재 가장 늘리 이용하는 -- Adam이 됐고, 다시 AdaMax가 제안됐다.
이전의 알고리즘들의 장점을 모두 흡수한 가장 나중에 나온 알고리즘이 일반적으로 좋은 특징을 많이 가졌겠지만 모든 문제, 데이터에서 가장 좋다고는 말할 수 없다. 장점을 합쳤다고 해서, 많은 요소를 고려했다고 해서 그저 좋아지는 건 아니다. 때론 그냥 오버스펙일 뿐이다. 수식이 복잡해지면 계산량만 늘어나고 예기치 못한 곳에서 버그가 발생할 수도 있다. 그냥 심플한 convex 문제라면 바닐라 버전인 SGD만으로 충분하다. 그 외의 일상에서 접하는 많은 데이터들도 SGD로 대부분 해결된다. 모로 가도 서울만 가면 된다고 했듯이 로컬 옴티마나 새들 포인트에 빠지지 않고 글로벌 옵티멈을 잘 찾아가면 최선이다. 사람들이 많이 사용하는 일반적인 방법이니 또는 가장 최근에 나온 방법이니 이걸 사용하자가 아니라 내 문제와 데이터에 가장 적합한가에 따라서 알고리즘을 취하면 된다.
자세한 수식은 링크된 논문을 참조하기 바란다. 어쨌든 최적화 알고리즘의 발전은 글로벌 옵티멈을 향한 좀 더 정확한 방향을 찾는 방법과 조금 더 빠르면서도 정밀하게 속력을 조정하는 방법, 두 축으로 발전하고 있다.
