9. 경사하강법

미분

• 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구
• 최적화에서 제일 많이 사용하는 기법

$$ f' (x) =  \lim_{h \rightarrow 0} \frac{f(x+h)-f(x)}{h}  $$

• 미분은 함수 f의 주어진 점 $ (x, f(x)) $ 에서의 접선의 기울기를 구할 수 있다.
• 접선의 기울기를 통해 고차원 공간에서도 어느 방향으로 점을 움직여야 함수값이 증가/감소하는지 알 수 있다.
  $ f'(x) > 0 $ 일 때, x 값이 양수로 간다면 y값이 커진다.
  $ f'(x) < 0 $ 일 때, x 값이 음수로 간다면 y값이 커진다.
• 즉, $ x - f'(x) $를 하면 함수값이 감소하는 방향으로 이동한다.
  → 함수의 극소값의 위치를 구할 수 있다. → 경사하강법(gradient descent)
   

import sympy as sym 
from sympy.abc import x
import numpy as np

def func(val):
    fun = sym.poly(x**2 + 2*x + 3)
    return fun.subs(x, val), fun

def func_gradient(fun, val):
    _, function = fun(val)
    diff = sym.diff(function, x)
    return diff.subs(x, val), diff

def gradient_descent(fun, init, lr=1e-3, epsilon=1e-5):
    cnt = 0
    val = init
    diff, _ = func_gradient(fun, init)
    
    # 컴퓨터 계산시, 미분이 정확히 0이 되는 것은 불가능하므로 epsilon보다 작을 때 종료하는 조건
    while np.abs(diff) > epsilon:
    	val = val - lr*diff
        diff, _ = func_gradient(fun, val)
        cnt += 1
        
    print(f"함수: {fun(val)[1]}, 연산 횟수: {cnt}, 최소점: ({val:.3f}, {fun(val)[0]:.3f})")

gradient_descent(fun=func, init=np.random.uniform(-2, 2))

# 함수: Poly(x**2 + 2*x + 3, x, domain='ZZ'), 연산 횟수: 6551, 최소점: (-1.000, 2.000)

 

 

변수가 벡터인 경우

• 벡터가 입력인 다변수 함수의 경우에는 편미분을 사용한다.

$$ f(x, y) = x^2 + 2xy + 3 + cos(x+2y) $$

$$ {\partial}_{x}f(x,y) = 2x + 2y - sin(x+2y) $$

 

• 각 변수 별로 편미분을 계산한 gradient 벡터를 $ f'(x) $ 대신 사용하여 경사하강법에 이용할 수 있다.

$$ \nabla f = ({\partial}_{x_{1}}f, {\partial}_{x_{2}}f,    \ldots , {\partial}_{x_{n}}f)  $$

 

• 다차원벡터의 경사하강법

def eval_(fun, val):
    val_x, val_y = val
    fun_eval = fun.subs(x, val_x).subs(y, val_y)
    return fun_eval

def func(val):
    x_, y_ = val
    func = sym.poly(x**2 + 2*y**2)
    return eval_(func, [x_, y_]), func

def func_gradient(fun, val):
    x_, y_ = val
    _, function = fun(val)
    
    diff_x = sym.diff(function, x)
    diff_y = sym.diff(function, y)
    grad_vec = np.array([eval_(diff_x, [x_,y_]), eval_(diff_y, [x_,y_])], dtype=float)
    return grad_vec, [diff_x, diff_y]

def gradient_descent(fun, init, lr=1e-2, epsilon=1e-5):
    cnt = 0
    val = init
    diff, _ = func_gradient(fun, val)
    
    while np.linalg.norm(diff) > epsilon:
        val = val - lr*diff
        diff, _ = func_gradient(fun, val)
        cnt += 1
    
    print(f"함수: {fun(val)[1]}, 연산횟수: {cnt}, 최소점: ({val}, {fun(val)[0]}) ")

pt = [np.random.uniform(-2,2), np.random.uniform(-2,2)]
gradient_descent(fun=func, init=pt)

# 함수: Poly(x**2 + 2*y**2, x, y, domain='ZZ'), 연산횟수: 619, 최소점: ([4.98934498e-06 6.65714066e-12], 2.48935633679920E-11)

 

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

• 선형모델의 경우 유사역행렬을 이용하여 선형회귀식을 구할 수 있지만, 경사하강법을 이용하면 선형모델이 아닌 다른 모델도 다룰 수 있다.
  → 일반적인 기계학습 모형에서 최적화를 할 때 사용하는 방법론이다.

선형회귀의 목적식 : $ \parallel y - {X}\beta \parallel_{2} $  → 이를 최소화하는 $ \beta $를 찾는 것이 목적

$$ \nabla_{\beta} \parallel y-{X}\beta \parallel_{2} = ( \partial_{\beta_{1}}\parallel y-{X}\beta \parallel_{2},  \cdots , \partial_{\beta_{d}}\parallel y-{X}\beta \parallel_{2} ) $$

 

아래 식은 주어진 $\beta$ 벡터 내에서 k번째 계수에 해당하는 $ \beta_{k} $ 를 사용하여 목적식을 편미분한 것이다.

 

 

$$ \nabla_{\beta} \parallel y-{X}\beta \parallel_{2} = (- \frac{X^{T}_{.1}(y-{X}\beta)}{n \parallel y - {X}\beta \parallel_{2}} , ... , - \frac{X^{T}_{.d}(y-{X}\beta)}{n \parallel y - {X}\beta \parallel_{2}} ) = - \frac{X^{T}(y-{X}\beta)}{n \parallel y - {X}\beta \parallel_{2}} $$

 

위의 목적식을 최소화하는 $ \beta $ 를 구하는 경사하강법 알고리즘은 아래와 같다.

$$ \beta^{t+1}  \leftarrow \beta^{t} -  \lambda  \nabla_{\beta} \parallel y - {X}\beta^{t} \parallel $$

 

+ L2-norm의 최솟값이나 L2-norm의 제곱값의 최솟값이나 찾는 작업 방향은 같기 때문에 계산의 편의성을 위해 L2-norm의 제곱을 계산해주어도 된다. L2-norm의 제곱으로 구한 목적식을 최소화하나는 $ \beta $를 구하는 경사하강법 알고리즘은 아래과 같다.

$$ \beta^{t+1}  \leftarrow \beta^{t} -  \frac{2\lambda}{n} {X}^{T}(y-{X}\beta^{t}) $$

 

 

경사하강법은 만능은 아니다!

• 경사하강법은 역행렬을 사용하지 않고도 최적화를 시킬 수 있기때문에 매우 편리한 최적화 알고리즘이다.
  이론적으로 경사하강법은 미분가능하고 볼록(convex)한 함수에 대해선 적절한 학습률과 학습횟수를 선택했을 때 수렴이 보장되어 있다.
• 하지만 비선형의 경우 목적식이 볼록하지 않을 수 있으므로 수렴이 항상 보장되지는 않는다. 특히 딥러닝의 경우 목적식이 대부분 볼록함수가 아니다.

 

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

• 확률적 경사하강법은 모든 데이터를 사용해서 업데이트하는 대신 데이터의 한개 또는 mini-batch를 활용하여 업데이트한다.
• non-convex 목적식은 SGD를 통해 최적화할 수 있다.
  
• 전체데이터를 쓰지않고 미니배치를 써서 업데이트하므로 연산량이 $ \frac{b}{n} $으로 감소하기 때문에 효율적이다.

 

아래와 같이 미니배치를 이용하게 되면 미니배치는 확률적으로 선택되기 때문에 목적식 모양이 바뀌지만 방향은 유사하다.

→ 목적식의 모양이 바뀐다 == 기울기가 바뀐다 → 이전  gradient vector가 0이라고 하더라도 목적식이 바뀐 상태에서 graident vector를 계산하면 값이 0이 아니기 때문에 극소점에서 탈출이 가능하다.

→ 극소,극대점에서의 gradient vector가 0 벡터가 되더라도, 실제로는 함수 전체의 극소/극대점이 아닐 수 있는 local minima 문제를 해결 가능하다.

→ 즉, 극값이면서 최솟값이 아닐 때도 탈출할 수 있기 때문에 convex한 함수가 아니더라도 최소점을 찾을 수 있다.

 

 

경사하강법은 모든 데이터를 가지고 계산하지만, 확률적 경사하강법은 미니배치를 가지고 gradient vector를 계산하기 때문에 각각의 화살표를 계산할 때 연산속도가 더 빠르다. 

+ 너무 작은 미니배치는 일반 경사하강법보다 느린 수렴을 일으킨다.
   →  SGD는 학습률, 학습횟수, 미니배치 사이즈의 고려가 필요하다!

 

 

---

부스트캠프 AI Tech 교육 자료를 참고하였습니다.