경사하강법 간단정리

개념적 정리 

 

미분은 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구, 최적화에 가장 많이 사용되는 기법이다. 

 

미분은 함수 f 의 주어진 점 (x, f(x))에서의 접선의 기울기를 구한다. 

출처: 부스트 캠프 더 좋은 사진을 찾지 못해 사용 

순간 변화율을 알면, 해당 점에서 어느 방향으로 움직여야 함수값이 증가 혹은 감소하는지 알 수 있다.

미분 값을 더해서 함수를 점차 극대화 시키는 것을 경사 상승법 gradient ascent, 

미분 값을 더해서 함수를 점차 극소화 시키는 것을 경사 하강법 gradient descent라 한다. (목적 함수 최소화, 극소값으로 이동)

극 값에 도달하면 어차피 미분 값이 0이므로 더이상 움직이지 않게 된다. 

 

---

while(abs(grad) > eps):

    var = var - lr * grad

    gard = gradient(var)

---

변수가 벡터, 행렬인 경우에는 n 차원에서 계산이 되므로 이동을 할 때 굉장히 많은 방향으로 움직일 수 있다. 

이에 따라 단순히 음수 양수로 계산되기 어려워 특별한 미분 방식인 편미분을 사용한다. 

 

벡터가 입력인 다변수 함수의 경우, 특정 방향의 좌표쪽으로 움직이는 편미분을 사용하면 된다. 

각 변수 별로 편미분을 계산한 그라디언트 벡터를 이용하여 경사하강, 상승법에 사용할 수 있다. 

 

---

경사하강법의 필요성

 

무어패로즈 역행렬 VS 경사하강법 

선형 모델에서는 무어패로즈 역행렬을 사용할 수 있지만, 비선형 모델에서는 무어패로즈 역행렬 사용이 불가능하다. 

따라서 경사하강법의 중요성이 강조된다. 

 

적용 예시 

선형 회귀의 L2 norm 목적식 $||\textbf{y} - \textbf{X}\beta||_{2}$을 최소화 하는 $\beta$ 를 찾는 것이 목적이다. 

 

목적식을 beta로 미분을 한 다음에 (beta - 미분값) 경사하강법 알고리즘(상단 참고)으로 최소에 해당하는 점을 찾을 수 있다. 

 

*$\triangledown$은 그라이언트를 의미한다.

$\textrm{beta}_{k}$ 로 목적식을 편미분 

 

예찬 멘토님 제공

---

합성함수의 미분법

 

\[ \frac{dy}{dx} =   \frac{dy}{du}  \frac{du}{dx} \textrm{또는}  \{f(g(x))\}^{'} = f^{'}g(x))g^{'}(x) \]

---

목적식을 최소화 하는 $\beta$ 를 구하는 경사하강법 알고리즘은 다음과 같다.

 

---

이제 위에서 간단하게 제시했던 경사하강법 알고리즘을 좀 더 구체적으로 작성할 수 있다. 

input: X, y, lr, T, output: beta

 

for t in range(T):

    error = y - X @ beta

    grad = -transpose(X) @ error

    beta = beta - lr * grad

 

*$\triangledown_{\beta}||\textbf{y}- \textbf{X}\beta||^{2}_{2}$

 

학습률과 학습 횟수를 적절하게 조정해야한다. 

 학습 횟수가 너무 작으면 목표로 하는 값까지 도달하지 못할 수 있다. 

학습률이 너무 작으면 수렴이 오래걸리고, 너무 크면 알고리즘이 불안정하게 움직인다. 

---

경사하강법은 만능일까?

이론적으로 경사하강법은 미분가능하고 볼록한 함수에 대해선 적절한 학습률과 학습횟수를 선택했을 때 수렴이 보장되어있다. 

 

*볼록한 함수는 그레디언트 벡터가 항상 최소점을 향한다.

 

 선형회귀의 경우 목적식 $||\textbf{y} - \textbf{X}\beta||_{2}는 회귀계수 \beta에 대해 볼록함수이기 때문에 알고리즘을 충분히 돌리면 수렴이 보장된다.$

 

그러나 비선형회귀 문제의 경우 목적식이 볼록하지 않을 수 있고, 수렴이 항상 보장되지 않는다. 

 

특히 딥러닝의 경우, 목적식이 다음과 같이 볼록한 구간이 여러 곳이기도 하다. 

 

non-convex 예시

이럴 때는 변형된 경사하강법 알고리즘이 필요하다. 

 

확률적 경사하강법

확률적 경사하강법(Stochastic Gradient Descent: SGD)은 모든 데이터를 사용해서 업데이트하는 대신 데이터 한개 또는 일부(mini-batch) 활용하여 업데이트한다. 

 

볼록이 아닌(non-convex) 목적식은 SGD를 통해 최적화할 수 있다. 

\[ \theta^{(t+1)} \leftarrow \theta^{(t)} - \triangledown_{\theta}\mathcal{L}(\theta^{(t)}) \\ \textrm{E}[\triangledown_{\theta}\mathcal{L}] \approx \triangledown_{\theta}\mathcal{L} \]

 

SGD는 데이터의 일부를 가지고 parameter를 업데이트 하기 때문에 연산자원을 더 효율적으로 활용하는데 도움이 된다. 

기댓값의 관점에서 원 GD와 유사하게 사용할 수 있다. 

 

원리

경사하강법은 전체데이터 $ \mathcal{D} = (\textbf{X}, \textbf{y})$ 를 가지고 목적식의 그라디언트 벡터 $\triangledown_{\theta}\mathcal{L}(\mathcal{D}, \theta)$ 를 계산한다.

*$\triangledown$은 nabla 라고 읽는다.

 

SGD은 전체데이터 $ \mathcal{D}_{b} = (\textbf{X}_{b}, \textbf{y}_{b}) \subset \mathcal{D} $ 를 가지고 그라디언트 벡터를 계산한다.

 

미니배치 $\mathcal{D}_{b}$를 가지고 목적식의 그라디언트를 근사해서 계산 (위 figure의 그라디언트 형태와 경사하강법 figure 그라디언트 형태가 다르다.)

 

값이 달라도, 원 경사하강법과 SGD의 방향이 유사할것이라 기대한다. 

경사하강법을 순차적으로 적용하며 여러 다른 미니배치를 사용해서 그라디언트 벡터를 계산하기 때문에 목적식의 모양이 하나로 고정되지 않고 매번 목적식 모양이 바뀐다. 즉 곡선의 형태가 계속해서 바뀐다. 이에 따라 로컬 극소점 즉 미분값이 0 이되는 구간에서 0이 되지 않고 탈출하는 것이 가능해진다. 

 

SGD는 목적식에서도 사용 가능하므로 경사하강법보다 머신러닝 학습에 더 효율적이다. 

다만, 경사하강법처럼 극소점을 향해서 올바르게 나아가지는 못할 수 있다. 그러나 데이터를 향해서 움직이는 것은 같기에 결국에는 같이 극소점을 향해서 나아간다. 

 

경사하강법 vs 미니배치 SGD 

 

 

오늘날 딥러닝 사용 데이터는 워낙 크기에, SGD 는 필수이다. 

ex) 256 $\times$ 256 $\times$ 3 $\times$ 1,000,000 $\approx 2^{37}$ bytes 

만약 일반적인 경사하강법처럼 모든 데이터를 업로드하면 메모리가 부족하여 Out-of-memory가 발생한다. 

 

이를 미니배치로 쪼개면, 

ex) 256 $\times$ 256 $\times$ 3 $\times |\mathcal{B}| \leq  2^{18} \cdot |\mathcal{B}|$ bytes 

병렬 연산을 통해 좀 더 빠르게 연산 가능