[boostcamp-ai-tech][AI-Math] 3, 4. 경사하강법(순한맛, 매운맛)

whatSup CheatSheet·2022년 1월 18일

ai math

AI-Math

목록 보기

3/9

3. 경사하강법(순한맛)

목차
- 미분이란?
- 경사하강법, 경사상승법
- 편미분

미분이란?

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

미분 = 변화율의 극한(limit) !!

$f(x)$ = $x^2 + 2x + 3$ 을 미분해보자.
- h를 0으로 보내는 극한을 취해주면,
  $f{\prime}$ (x) = $2x + 2$
- 구현 : sympy.diff
```
import sympy as sym
from sympy.abc import x

sys.diff(sym.poly(x**2 + 2*x + 3), x)

>>>> Poly(2*x _ 2, x, domain = 'zz')
```

경사하강법, 경사상승법

미분은 함수 $f$ 의 주어진 점 $(x, f(x))$ 에서의 접선의 기울기를 구하는 것.
한 점에서 접선의 기울기를 알면 어느 방향으로 점을 움직여야 함수값이 증가하는지/감소하는지 알 수 있음.
- 미분값을 더하면 경사상승법(gradient ascent)이라 하며 함수의 극대값의 위치를 구할 때 사용한다(목적함수를 최대화할 때)
- 미분값을 빼면 경사하강법(gradient descent)이라 하며 함수의 극소값의 위치를 구할 때 사용한다(목적함수를 최소화할 때)
  -> 극값에 도달하면(미분값이 0이 되면) 움직임을 멈춘다.(목적함수 최적화 종료)
경사하강법 : 알고리즘
- 컴퓨터로 계산할 땐 미분이 정확히 0이 되지 않으므로, 종료 조건이 따로 필요함

var = init  # 시작점
grad = gradient(var)  # 미분값을 계산해주는 함수 
while(abs(grad) > eps):  # 미분값이 종료조건(eps)보다 작아지면 종료
    var = var - lr * grad  # 정해놓은 학습률로 미분 업데이트 속도를 조절
    grad = gradient(var)  # 업데이트

변수가 벡터라면? 편미분 !

벡터가 입력인 다변수 함수의 경우 편미분(partial differentiation)을 사용한다.
- 편미분 : 특정방향의 좌표축으로 이동하는 방식으로 미분하는 것.
- 편미분은 주어진 함수의 변수의 개수만큼 계산을 해볼 수 있음

벡터 e의 i번째( $e_i$ )에만 변화를 주는 단위벡터(벡터 e의 i번째 변화율만 계산할 수 있음.

ex)

x에 대한 편미분 -> y를 상수취급하고 미분을 함(x방향의 움직임만 보는 것)

위 식에 대한 편미분 구현 : sympy.diff

import sympy as sym
from sympy.abc import x, y

sys.diff(sym.poly(x**2 + 2*x*y + 3) + sym.cos(x + 2*y), x)

>>>> 2*x + 2*y - sin(x + 2*y)

각 변수별로 편미분을 계산한 그레디언트(gradient) 벡터를 이용하여 경사하강/경사상승법에 사용할 수 있음

미분 값(한 개) 대신 벡터 $\nabla f$ ( $\nabla$ == nabla !!)를 사용하여 변수 $x=(x_1, ..., x_d)$ 을 동시에 업데이트 !!
경사하강법(그레디언트 벡터) : 알고리즘
- 경사하강법 알고리즘은 그대로 적용됨. 하지만 벡터는 절대값 대신 노름(norm)을 계산해서 종료조건을 설정해야 함.

var = init  # 시작점
grad = gradient(var)  # 미분값을 계산해주는 함수 
while(norm(grad) > eps):  # 미분값이 종료조건(eps)보다 작아지면 종료
    var = var - lr * grad  # 정해놓은 학습률로 미분 업데이트 속도를 조절
    grad = gradient(var)  # 업데이트

4. 경사하강법(매운맛)

목차
- 선형회귀분석 복습(유사역행렬)
- 경사하강법으로 선형회귀 계수 구하기
- 확률적 경사하강법(SGD)

선형회귀분석 복습

유사역행렬을 이용하면 데이터를 선형모델(limear model)로 해석하는 선형회귀식을 찾을 수 있다
- $X$ $\beta$ = $\hat{y}$ $\approx$ $y$ -> 😁
  -> $\beta$ = $X^+y$
  -> $\beta$ = $(X^TX)^{-1}X^Ty$
  - 이처럼, Moore-Penrose 역행렬을 이용하면 y에 근접하는 $\hat{y}$ 을 찾을 수 있음( $L_2$ -노름을 최소화하는 계수 $\beta$ )

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

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

목적식을 $\beta$ 로 미분 한 다음, 주어진 $\beta$ 에서 미분값을 빼주면 최소점을 구할 수 있음
학습률 $\lambda$ 를 베타에 대한 편미분인 그레디언트 벡터를 곱한 값을 $\beta^{(t)}$ 에서 빼주면 됨.

복잡해보이지만, 사실 $X\beta$ 를 계수 $\beta$ 에 대해 미분한 결과인 $X^T$ 만 곱해지는 것임.

경사하강법 기반 선형회귀 : 알고리즘
- 종료조건을 일정 학습횟수로 변경한 점만 빼고 앞에서 배운 경사하강법 알고리즘과 같음

for t in range(T):  # 정해진 횟수가 종료조건
    error = y - X @ beta  # @ -> 행렬곱(numpy)
    grad = - transpose(X) @ error  # 그레디언트 벡터
    beta = beta - lr * grad

$\nabla_\beta||y-X\beta||^2_2$ 항을 계산(grad)해서 $\beta$ 를 업데이트.

** 경사하강법 알고리즘에선 학습률(lr)과 학습횟수가 중요한 하이퍼파라미터가 됨.

** 특히 선형회귀의 경우 목적식 $||y-X\beta||_2$ 은 회귀계수 $\beta$ 에 대해 볼록함수이기 때문에 알고리즘을 충분히 돌리면 수렴이 보장되지만, 비선형회귀 문제의 경우 목적식이 볼록하지 않을 수 있으므로 수렵이 항상 보장되지는 않음(특히 딥러닝의 경우🥲).

확률적 경사하강법(SGD)

확률적 경사하강법(Stochastic Gradient Descent)은 모든 데이터를 사용해서 업데이트하는 대신 데이터 한 개 또는 일부 활용하여 업데이트 하는 것.
- 일부 활용 : 미니배치. 미니배치는 확률적으로 선택하므로 목적식 모양이 배뀌게 됨(매번 대른 미니배치를 사용하기 때문).
- SGD가 만능은 아니지만 딥러닝의 경우 SGD가 경사하강법보다 실증적으로 더 낫다고 검증됨.
볼록하지 않은 목적식은 SGD를 통해 최적화 할 수 있다.
SGD는 데이터 일부를 가지고 파라미터를 업데이트하기 때문에 연산자원을 좀 더 효율적으로 활용하는 데 도움이 됨.