경사 하강법
제목은 경사하강법이지만 사실 경사 상승법이 편해서 경사상승법 형식으로 다룹니다.
GD(Gradient Descent) 경사하강법이 최적해(global optimal)를 보장하는지와 그리고 과연 진짜 수렴하는지에 대해서 수식적으로 알아 보겠습니다. 서적이나 강의를 바탕으로 한게 아니라 제가 혼자 수식을 끄적이고 공부한 내용을 정리하다 보니 아마 틀린 내용이 많습니다.
sgd와 gd의 차이는 (mini-batch)sgd는 데이터 셋에서 mini-batch만큼 샘플링을 하여 추출하여 경사하강법을 하여 매개변수를 업데이트 합니다. gd는 전체 데이터 셋에 대하여 업데이트를 합니다. 이때 sgd에서 추출하는 mini-batch간의 관계가 i.i.d로 정의 된다면 기울기의 기댓값이 전체 데이터셋의 기울기와 같아져 gd에서 사용하는 기울기에 대해 수렴한다면 sgd또한 수렴하게 됩니다.
사실 경사하강법 자체의 아이디어는 직관적이고 쉬운 내용입니다.
그래도 한번 조금 더 뜯어 볼 필요가 있다고 생각합니다.
최적화를 위해서는 손실함수 혹은 목적함수가 필요합니다. 이 함수는 반드시 스칼라 값을 가져야합니다.
스칼라가 아니면 어떤 것이 더 최적인지 구분이 불가하기 때문입니다.
우선 최적화 할 함수를 아래처럼 설정 하겠습니다.
$\mathbb{maximize} \, J(x,y,\theta) $
주어진 데이터가 있을 때 x,y는 변하지 않습니다.
주어진 x,y에 대해 J를 가장 최대화(혹은 최소화)하는 $\theta$를 찾는 것이 우리의 목표입니다.
i번째 스텝의 매개변수를 $\theta_{i}$이라고 하겠습니다. 그 다음 스텝의 매개변수를 $\theta_{i+1}$이라고 하겠습니다.
반복적인 방법을 이용해 최적의 매개변수를 탐색하고자 합니다. 그러기 위해 꽤 괜찮은 가정은 적어도 현재의 매개변수보다 나은 매개변수가 되도록 다음 매개변수를 지정하는 것입니다.
이를 부등식으로 표현하면 다음과 같습니다.
$J(x,y,\theta_{i+1})\ge J(x,y,\theta_{i})$
i 번째 과정에서 찾아야 하는 것은 다음 매개변수 $\theta_{i+1}$입니다. 부등식에서 좌변은 우리가 아직 알지 못하는 값입니다.
그렇기에 이를 우리가 아는 값인 $\theta_i$와의 관계를 찾아 표현해야 합니다. 가장 쉬운 방법은 테일러 전개입니다. 하지만 n-차 테일러 전개에 대해 나타내는 것은 무리가 있어 1차 테일러 전개로 나타내도록 합니다.
테일러 전개를 통해 부등식을 다시 표현하면 아래와 같습니다. (기울기 벡터는 열벡터이지만 전치는 생략하겠습니다)
$J(x,y,\theta_{i+1}) \approx J(x,y,\theta_{i}) + \nabla_\theta J(x,y,\theta_i)\cdot (\theta_{i+1}-\theta_i)\ge J(x,y,\theta_i)$
(1차 테일러 전개에서 $z=J_{i+1}$에 대해 표현하면 접평면의 방정식이 됩니다.)
최적화 문제를 테일러 1차 근사에 대해 다시 정의한다면 다음과 같이 바꿀수 있습니다.
$\theta_i$에서 J는 주어진 값이므로 이를 제외한다면 내적의 값을 최대화 하는 문제로 바뀌게 됩니다.
$\mathbb{maximize} \nabla_\theta J(x,y,\theta_i)\cdot (\theta_{i+1}-\theta_i)$
이제 목적 식은 두 벡터의 내적을 최대화 하는 것이 됩니다. 여기서 찾아야 하는 것은 위 식을 가장 크게하는 $\theta_{i+1}$입니다. 한 점에서 자신이 아닌 다른 점과 연결하는 것은 하나의 직선을 만드는 것과 동일합니다.
한 점에서 선을 만들기 위해서는 방향과 길이가 필요합니다.
어떤 벡터에 대해 내적이 최대가 되기 위해서는 벡터와 비례하는 벡터일때 가장 큰 값을 갖게 됩니다. 방향을 얻게 되었습니다.
따라서 $\theta_{i+1}-\theta_i \propto \nabla_\theta J(x,y,\theta_i)$ 입니다.
이 비례식을 등호로 만들어주기 위해, 길이를 정하기 위해 약간 휴리스틱하지만 다음과 같은 제약 조건을 추가합니다.
(아마도 정석은 아래에 부등식 조건을 걸고 라그랑주 방법으로 풀어내는 것 아닐까 생각됩니다.)
$\mathbb{such\, that}\lVert \theta_{i+1}-\theta_i \rVert^2 = \epsilon $
위 조건식을 만족하면서 기울기 벡터에 비례하는 $\theta_{i+1}-\theta_i$는 아래와 같습니다.
$\theta_{i+1}-\theta_i =\sqrt{\epsilon / \lVert \nabla_\theta J(x,y,\theta_i)\rVert^2} \nabla_\theta J(x,y,\theta_i)$
위 식에서 복잡한 루트 식을 학습률 $\eta$로 대체하겠습니다.
$\theta_{i+1}-\theta_i = \eta \nabla_\theta J(x,y,\theta_i),\, \eta > 0$
실제로 학습시에는 두 점 사이의 L2 norm을 제한하는게 아니라 $\eta$를 고정하면서 기울기 벡터의 크기에 따라 L2 norm을 설정합니다.
기울기 벡터의 크기가 작아진다면 현재 점 주변을, 기울기 벡터의 크기가 커지면 현재 점과 멀리 떨어진 점을 탐색합니다.
만약 여기서 $\epsilon$을 고정하게 되면 학습률이 기울기 벡터의 크기에 따라 매번 바뀌게 됩니다.
좌변의 i번째 매개변수를 오른쪽으로 넘겨 점화식 형태로 만들어준다면 아래와 같습니다.
$\theta_{i+1} = \theta_i + \eta \nabla_\theta J(x,y,\theta_i)$
테일러 전개를 통해 구했던 부등식에 $\theta_{i+1}-\theta_i$를 대입한다면 아래와 같아집니다.
$\eta \lVert \nabla_\theta J(x,y,\theta_i)\rVert^2\ge 0$
기울기 벡터는 실수 벡터이기 때문에 항상 0보다 큰 값을 갖게 되므로 기울기를 따라 매개변수 업데이트를 진행한다면 적어도 현재의 값보다 좋은 매개 변수를 얻게 됩니다. 이것이 기울기 기반 업데이트의 수렴하는 방식입니다.
위에서 i+1의 매개변수에 대한 비용 함수를 1차 테일러 전개를 통해 근사를 하였습니다.
1차 테일러 전개로 함수를 근사한다는 것은 함수의 한 점 위에서 접선으로 함수를 근사하는 것입니다. (3차원 이상부터는 접평면)
1차 테일러의 근사의 오차는 나머지 n차 미분들의 합으로 $\Delta \theta^2$에 대한 오차를 갖게 됩니다. 기울기를 구한 점에서 너무 멀어지게 된다면 근사의 오차가 늘어나게 됩니다. (그렇기에 유클리드 거리의 제약조건이 등장하는 것은 자연스러운 조건입니다.)
2차 테일러로 근사한다면 함수의 곡률 정보를 포함하는(헤시안 행렬) 항이 더해져 조금 더 정확한 근사가 가능합니다.
다만 2차 미분에 사용되는 hessian의 경우 계산 비용이 많이 들어 잘 사용되지는 않습니다. 1차만으로 꽤나 잘 근사하기 때문입니다.
이 오차를 줄이기 위해서는 $\Delta \theta$에 대한 규제가 있어야 하지만 학습률을 고정하는 것은 L2 norm에 대한 규제가 아니게 됩니다.
$\eta = \sqrt{\epsilon / \lVert \nabla_\theta J(x,y,\theta_i)\rVert^2 }$
기울기가 커지게 된다면 다음 점은 더 먼 곳을 탐색하고, 기울기가 작아진다면 가까운 점을 탐색합니다. 이때 학습률이 커져 기울기가 너무 커지게 되면 계속해서 발산을 하는 문제가 있으며, 너무 작으면 수렴속도가 느려지는 문제점이 있습니다.
또 다른 문제점은 1차 테일러 전개에 대해서도 전역 최적값이 아니라 국소 최적값에도 수렴한다는 점입니다.
처음으로 돌이켜 생각해보면 적어도 현재의 매개 변수보다 좋은 매개변수를 탐색하고자 하였지 전체 매개변수 공간에서 최적의 값을 탐색하는 방향으로 gd를 설계하지 않았습니다.(제 생각에 딥러닝에서 초기화가 중요한 이유입니다.)
이런 문제점을 피하기 위해서 다양한 옵티마이저, warmup start cosine restart 같은 learning rate scheduler들이 만들어졌습니다.
딥러닝에서는 sgd를 옵티마이저로 쓰는게 일반적으로 가장 좋은 성능을 갖는다고 합니다.
또 다른 문제는 안장점 문제(saddle point)가 있는데 이는 극대점과 극소점이 동시에 나타나는 경우를 말합니다.
경사하강법의 제약 조건을 유클리드 노름이라고 설명하였습니다.
하지만 매개변수 간의 유클리드 거리가 대부분의 경우 우리가 추정하는 분포의 차이를 설명하지는 못합니다.
$d: distancs \, function$
$\Delta \theta \neq d(P(y|x ;\theta_{i+1}), P(y|x;\theta_{i+1}))$
여기서 d는 거리함수, 세미콜론은 theta에 의해 매개변수화 되었다는 의미입니다.
여기서 다른 제약 조건을 사용하는 대표적인 예시로는 natural gradient 방법이 있습니다.
매개변수에 대해 유클리드 거리의 제약조건이 아니라 확률 분포 공간 상에서 거리(KL-divergence,엄밀한 의미에서 거리는 아님)에 대한 제약 조건으로 바꿔주는 방법입니다.
natural gradient에 대해서는 저도 아직 공부가 많이 필요해 소개만하고 넘어가겠습니다.
사실 gd라는 현상이 있고 이를 분석하는 감이 있습니다. 쉬운것도 괜히 어렵게 쓰려고 노력한거 같기도하고,, gd가 현재의 매개변수보다 나은 매개변수를 찾고자 한다는 동기도 사실 저의 추측입니다. 다만 흐름상 받아 들이기에 자연스럽다고 느껴져 그냥 넘어 갔습니다.