경사하강법

중요개념

• 경사하강법 기반의 선형 회귀 알고리즘
• 확률적 경사하강법

목표

1. 행렬 부분에서 배웠던 무어-펜로즈 역행렬을 활용한 선형회귀분석과 비교하여, 선형 모델 외에도 적용 가능한 경사하강법-선형회귀분석 방법을 공부합시다. 이 때 나오는 경사하강법 알고리즘 수식을 정확히 이해하고 넘어갑시다.
2. 딥러닝에서 경사하강법이 가지는 한계를 알아보고, 이를 극복하기 위한 확률적 경사하강법을 공부합시다.

권고사항

확률적 경사하강법은 오늘날 딥러닝 학습에 널리 활용되는 방법이므로 충분히 공부하시고 넘어가야 합니다.
※ d-차원 벡터(베타)에 대한 그레디언트 벡터를 구하는 계산을 각자 직접 손으로 해보기 바랍니다!

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

$선형회귀의\ 목적식은\ ||y-X\beta||_2이고\ 이를\ 최소화하는\ \beta를\\ 찾아야\ 하므로\ 다음과\ 같은\ 그래디언트\ 벡터를\ 구해야한다.$

• 벡터의 각 요소의 전치기호 부분은 행렬 X의 k번째 열벡터를 전치시킨 것이다
• 목적식을 최소화하는 베타값을 구하는 경사하강법 알고리즘은 다음과 같이 표현할 수 있다.
  
• 목적식의 제곱을 최소화하는 식을 생각하면 더 간단해진다.
  

# norm : 미분을 계산하는 함수
# lr : 학습률 (learning rate)
# T : 학습 횟수 

for t in range(T):
    error = y - X@beta
    grad = - transpose(X)@error
    beta = beta - lr * grad

코드 해석

• 종료조건을 일정 학습횟수로 변경한 점만 빼고 앞에서 배운 경사하강법 알고리즘과 같다.
• 베타값을 지속적으로 업데이트한다.
• 경사하강법 알고리즘으로 역행렬을 이용하지 않고 회귀계수를 계산할 수 있다.
• 경사하강법 알고리즘에서 학습률과 학습횟수가 중요한 hyperparameter가 된다.

경사하강법은 만능인가?

• 이론적으로 경사하강법은 미분가능하고 볼록(convex)한 함수에 대해선 적절한 학습률과 학습횟수를 선택했을 때 수렴이 보장되어 있습니다.
  • 볼록한 함수는 그래디언트 벡터가 항상 최소점을 향한다.
• 선형회귀의 경우 목적식이 회귀계수에 대해 볼록함수이기 때문에 알고리즘을 충분히 돌리면 수렴이 보장됩니다.
• 비선형 회귀의 경우 목적식이 볼록하지 않을 수 있으므로 수렴이 항상 보장되지 않습니다.
  • 딥러닝을 사용하는 경우 목적식은 대부분 볼록함수이지 않습니다.

확률적 경사하강법

• 확률적 경사하강법(stochastic gradient descent)은 모든 데이터를 사용해서 업데이트 하는 대신 데이터 한 개 또는 일부 활용하여 업데이트 합니다.
• 볼록이 아닌(non-convex) 목적식은 SGD를 통해 최적화할 수 있습니다.
  • SGD가 만능은 아니지만 딥러닝의 경우 GD보다는 실증적으로 낫다고 검증되었습니다.

• SGD는 데이터의 일부를 가지고 파라미터를 업데이트하기 때문에 연산 자원을 좀 더 효율적으로 활용하는데 도움이 됩니다.
  - 전체 데이터를 쓰지 않고 미니배치를 써서 업데이트 하므로 연산량이 b/n으로 감소한다.
  

미니배치 연산

• 경사하강법은 전체데이터를 가지고 목적식의 그래디언트 벡터를 계산합니다.
• SGD는 미니배치를 가지고 그래디언트 벡터를 계산합니다.
  • 미니배치는 확률적으로 선택하므로 목적식 모양이 변하게 됩니다.
  • 미니배치는 볼록이 아닌 목적식에도 사용 가능하므로 경사하강법보다 머신러닝 학습에 더 효율적입니다.