[AI Math] 경사하강법 - 매운맛

경사하강법으로 선형회귀 계수 구하기

• 선형회귀 목적식 = $\lVert y - X\beta \rVert_2$
• 목적식을 최소화하는 $\beta$를 찾아야 하므로 목적식을 각각의 $\beta_k$로 미분한 다음과 같은 그레디언트 벡터를 구해야 한다.

\[\nabla_{\beta}\lVert y - X\beta \rVert_2 = (\partial_{\beta_1}\lVert y - X\beta \rVert_2,\ \cdots\ , \partial_{\beta_d}\lVert y - X\beta \rVert_2)\]

• 모든 $\beta$ 값에 대하여 미분을 해주어야 하기 때문에 임의의 $\beta_k$에 대해 미분하는 식을 간단히 하면 다음과 같은 과정을 거친다.

  1. L2-norm($\lVert y - X\beta \rVert_2$) 식을 전개 해주는데, $n$개의 데이터를 가지고 계산되는 L2-norm이기 때문에 다음과 같이 $i=1$부터 $n$까지 더해준 뒤 평균값을 구해준 뒤 제곱근을 계산해주게 된다.

     \[\lVert y - X\beta \rVert_2 = \left\{ \frac{1}{n} \sum^n_{i=1} \left( y_i - \sum^d_{j=1} X_{ij}\beta_j \right)^2 \right\}^{1/2}\]

  2. 제곱근 안에 있는 식을 $A$로, 제곱 안에 있는 식을 $B$로 먼저 치환하고, Chain-Rule을 이용하기위해 각각의 미분을 구해준다.

     \[\lVert y - X\beta \rVert_2 = A^{1/2}\] \[A = \frac{1}{n} \sum^n_{i=1} B^2\] \[B = y - \sum^d_{j=1} X_{j}\beta_j\] \[\frac{\partial}{\partial_{\beta_k}} = \frac{\partial}{\partial A} \cdot \frac{\partial A}{\partial B} \cdot \frac{\partial B}{\partial_{\beta_k}}\] \[\frac{\partial}{\partial A} = \frac{1}{2} \cdot A^{-1/2} = \frac{1}{2A^{1/2}}\] \[\frac{\partial A}{\partial B} = \partial B\ \frac{1}{n} \sum^n_{i=1} B^2 = \frac{1}{n} \sum^n_{i=1} \partial B \cdot B^2 = \frac{1}{n} \sum^n_{i=1} 2B = \frac{2}{n} \sum^n_{i=1} B\] \[\frac{\partial B}{\partial_{\beta_k}} = \partial_{\beta_k} \left( y_i - \sum^d_{j=1} X_{ij}\beta_j \right)\] \[= - \partial_{\beta_k} \sum^d_{j=1} X_j\beta_j = -\partial_{\beta_k} \left (X_{i1}\beta_1 +\ \cdots\ + X_{ik}\beta_k +\ \cdots\ + X_{id}\beta_d \right) = - X_{ik}\]

  3. 구해준 각각의 미분을 Chain Rule을 이용하여 곱해준다.

     \[\frac{\partial}{\partial_{\beta_k}} = \frac{\partial}{\partial A} \cdot \frac{\partial A}{\partial B} \cdot \frac{\partial B}{\partial_{\beta_k}}\] \[= \frac{1}{2A^{1/2}} \cdot \frac{2}{n} \sum^n_{i=1} B \cdot - X_{ik}\] \[= -\frac{\sum^n_{i=1}X_{ik} \left (y_i-\sum^d_{j=1} X_{ij}\beta_j \right )}{n\lVert y - X\beta \rVert_2}\]

  4. 3번의 결과값의 분모를 더 간단하게 하면 다음과 같다.

     \[\sum^n_{i=1} X_{ik} \left (y_i-\sum^d_{j=1} X_{ij}\beta_j \right )\] \[= \sum^n_{i=1} X_{ik} \cdot (y_i - X_{i \cdot}\beta)\] \[X_{i\ \cdot} = ith\ row\ vector\] \[= X_{1k} \cdot (y_1-X_1\beta) +\ \cdots\ + X_{nk} \cdot (y_n-X_n\beta)\] \[= X_{\cdot\ k}^T \cdot (y-X\beta)\] \[X_{\cdot\ k} = kth\ column\ vector\]

  5. 결과적으로 얻어지는 $\beta_k$에 대한 그레디언트는 다음과 같다.

     \[\frac{\partial}{\partial_{\beta_k}} = -\frac{X_{\cdot\ k}^T \cdot (y-X\beta)}{n\lVert y - X\beta \rVert_2}\]

  6. 이러한 그레디언트들을 모아둔 그레디언트 벡터를 구해야 되므로, 다음과 같이 결국 그레디언트 벡터는 $X\beta$를 계수 $\beta$에 대해 미분한 결과인 $X^T$만 곱해지게 된다.

     \[\nabla_{\beta}\lVert y - X\beta \rVert_2 = (\partial_{\beta_1}\lVert y - X\beta \rVert_2,\ \cdots\ , \partial_{\beta_d}\lVert y - X\beta \rVert_2)\] \[= (-\frac{X_{\cdot\ 1}^T \cdot (y-X\beta)}{n\lVert y - X\beta \rVert_2},\ \cdots\ , -\frac{X_{\cdot\ d}^T \cdot (y-X\beta)}{n\lVert y - X\beta \rVert_2})\] \[= -\frac{X^T (y-X\beta)}{n\lVert y - X\beta \rVert_2}\]

  7. 이제 목적식을 최소화하는 $\beta$를 구하는 경사하강법 알고리즘에 위에서 구한 그레디언트 벡터를 넣어주면 다음과 같다. ($\lambda$ = learning rate, $g$ = gradient vector)

     \[\beta^{(t+1)} \leftarrow \beta^{(t)} - \lambda \cdot g^{(t)}\] \[\beta^{(t+1)} \leftarrow \beta^{(t)} - \lambda \cdot -\frac{X^T (y-X\beta^{(t)})}{n\lVert y - X\beta^{(t)} \rVert_2}\] \[\beta^{(t+1)} \leftarrow \beta^{(t)} + \lambda \cdot \frac{X^T (y-X\beta^{(t)})}{n\lVert y - X\beta^{(t)} \rVert_2}\]

  8. $\lVert y - X\beta \rVert_2$ 대신 $\lVert y - X\beta \rVert^2_2$을 최소화하면 식이 좀 더 간단해진다.

     \[\nabla_{\beta}\lVert y - X\beta \rVert^2_2 = -\frac{2}{n}X^T(y-X\beta)\] \[\beta^{(t+1)} \leftarrow \beta^{(t)} + \frac{2\lambda}{n} X^T(y-X \beta^{(t)})\]

경사하강법: 알고리즘

# lr: 학습률, T: 학습횟수

for t in range(T): # 종료조건을 학습횟수로 변경
	error = y - X @ beta
	grad = - transpose(X) @ error
    beta = beta - lr * grad

• 학습률과 학습횟수가 중요한 hyperparameter가 된다
  • 학습률을 너무 작게 설정할 경우, 수렴을 너무 늦게하게 되고, 너무 크게 설정하면 알고리즘이 불안정하게 움직이게 된다.
  • 학습횟수를 너무 적게 설정하면 수렴이 잘 안되고 마무리 될 수도 있으니, 적절하게 학습횟수를 선택해주어야 한다.

경사하강법은 만능일까?

• 미분 가능하고, 볼록(convex)한 함수에 대해, 적절한 학습률과 학습횟수를 선택했다면 수렴이 보장
  • 볼록한 함수는 그레디언트 벡터가 항상 최소점을 향하기 때문
• 선형회귀의 목적식 $\lVert y - X\beta \rVert_2$은 회귀계수 $\beta$에 대해 볼록함수이기 때문에 수렴성 보장
• 비선형회귀 문제의 경우 목적식이 볼록하지 않을 수 있으므로(non-convex) 수렴성이 항상 보장되지 X
  • 찾고자 하는 global minimum이 아닌 local minimum에서 수렴될 수도 있다는 뜻
  • 특히 딥러닝을 사용하는 경우 목적식은 대부분 볼록함수가 X

확률적 경사하강법 (SGD, stochastic gradient descent)

• 모든 데이터를 사용하지 않고, 데이터 한 개, 또는 일부 활용하여 업데이트하는 방식
• non-convex 목적식은 SGD를 통해 최적화 가능
• SGD라고 해서 만능은 아니지만 경사하강법보다 더 낫다.
• 데이터의 일부를 가지고 parameter를 업데이트하기 때문에 연산자원을 더 효율적으로 활용 가능

확률적 경사하강법의 원리: 미니배치 연산

• 확률적으로 선택한 데이터만으로 그레디언트 벡터를 계산하기 때문에, 매번 다른 미니배치를 사용할 때마다 목적식이 변화하게 된다.
• 목적식이 변화하지만 방향은 비슷하게 이동하기 때문에 minimum을 찾아줄 수 있다.
• local에 빠지려고 할 때 확률적으로 local에서 벗어날 수 있는 gradient가 주어지게 되면 local에서 벗어나기도 하기 때문에 찾고자 하는 global minimum을 찾아줄 수 있게 된다.

확률적 경사하강법의 원리: 하드웨어

• 수백만 개의 이미지 데이터를 이용하여 딥러닝 학습을 할 때, 일반적인 경사하강법처럼 모든 데이터를 업로드 하면 메모리가 부족하여 Out-of-memory가 발생
• 미니배치로 쪼갠 데이터를 가지고 SGD를 진행할 경우, 빠르게 연산이 가능하고 하드웨어적인 한계도 극복하면서, 병렬연산을 통해 딥러닝 학습이 가능