[AI Math] 경사하강법

네이버 부스트코스에서 제공하는 임성빈 님의 강의를 참고하여 작성된 포스팅입니다.

---

미분이란?

• 미분 : 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구
  • 함수 f의 주어진 점 (x, f(x)) 에서의 접선 기울기
  • 미분을 계산하려면 함수 모양이 매끄러워야 한다 = 함수가 연속적이어야 한다
  • in numpy
  • import sympy as sym from sympy.abc import x sym.diff(sym.poly(x**2 + 2*x + 3), x)

 

경사상승법 / 경사하강법

접선의 기울기를 알면 어느 방향으로 점을 움직여야 함수값이 증가/감소하는지 알 수 있음 (특히 고차원일 때!!!)

• 함수 값이 증가하는 경우 (미분값 더하기) = 경사상승법
• 함수의 극대값 위치를 구할 때 = 목적함수를 최대화할 때 사용한다

• 함수 값이 감소하는 경우 (미분값 빼기) = 경사하강법
• 함수의 극소값 위치를 구할 때 = 목적함수를 최소화할 때 사용한다

극값에 도달하면 미분값이 0이 되므로 최적화 과정이 끝난다.

→ 단, 컴퓨터로 계산하면 미분이 정확히 0이 되지 않으므로 eps(threshold)보다 작을 때 종료

 

경사하강법 알고리즘 (일변수)

'''
Input : gradient, init (시작점), lr (학습률), eps : 알고리즘 종료조건
Output : var
'''

var = init
grad = gradient(var)
while(abs(grad) > eps):
    var = var - lr*grad # x - lambda (f'(x)) 를 계산 : 미분을 통해 업데이트 하는 속도 조절
    grad = gradient(var) # 미분값 업데이트

# 파이썬 구현코드
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_point, lr_rate=1e-2, epsilon=1e-1):
    cnt = 0; val = init_point
    diff, _ = func_gradient(fun, init_point)
    while np.abs(diff) > epsilon:
        val = val = lr_rate * diff
        diff, _ = func_gradient(fun, val)
        cnt += 1
    print(f"함수 : {fun(val)[1]}, 연산 횟수 : {cnt}, 최소점 : {val}, {fun(val)[0]}")

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

벡터가 입력인 다변수 함수는 편미분을 사용

• 예시
  
• import sympy as sym from sympy.abc import x, y sym.diff(sym.poly(x**2 + 2*x*y + 3) + sym.cos(x+2*y), x)

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

 

그래디언트 벡터가 뭐예요?

각 점 (x,y,z) 공간에서 f(x,y) 표면을 따라 $-\nabla f$ 벡터를 그리면 아래와 같이 그려짐

→ 극소점으로 향하는 화살표들의 움직임!

그래디언트 벡터 $\nabla f(x,y)$ 는 각 점 (x, y)에서 가장 빨리 증가하는 방향으로 흐름

여기에 마이너스 부호를 붙인 $-\nabla f(x,y)$ 는 각 점에서 가장 빨리 감소하게 되는 방향으로 흐름

 

경사하강법 알고리즘 (다변수)

'''
Input : gradient, init (시작점), lr (학습률), eps : 알고리즘 종료조건
Output : var
'''

var = init
grad = gradient(var)
while(norm(grad) > eps): # 절대값 대신 노름을 계산해 종료조건을 설정한다는 것만 다름
    var = var - lr*grad # x - lambda (f'(x)) 를 계산 : 미분을 통해 업데이트 하는 속도 조절
    grad = gradient(var) # 미분값 업데이트

# 파이썬 구현코드
import sympy as sym
from sympy.abc import x, y
import numpy as np

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):
    fun = sym.poly(x**2 + 2*x + 3)
    return fun.subs(x,val), fun

def func_multi(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_point, lr_rate=1e-2, epsilon=1e-1):
    cnt = 0; val = init_point
    diff, _ = func_gradient(fun, init_point)
    while np.linalg.norm(diff) > epsilon:
        val = val = lr_rate * 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_multi, init_point=pt)

 

선형회귀분석 복습

역행렬 대신 경사하강법으로 선형 모델 찾기!

• 선형 회귀의 목적식 : $||y - X\beta||_2$

→ 이를 최소화하는 beta 값을 찾기!

 

경사하강법 기반 선형회귀 알고리즘

'''
Input : X, y, lr, T(학습 횟수)
Output : beta
'''

for t in range(T): # 종료 조건을 일정 학습횟수로 변경한 점만 빼고는 앞의 경사하강법 알고리즘과 같음
    # error term^2을 계산해서 beta 업데이트
    error = y - X @ beta # X의 전치 행렬을 행렬곱으로 곱해준 다음 - 붙여주면 그래디언트 벡터 -> beta 업데이트
    grad = -transpose(X) @ error
    beta = beta - lr * grad

import numpy as np

X = np.array([[1,1], [1,2], [2,2], [2,3]])
y = np.dot(X, np.array([1,2])) + 3 # 계수 1, 2, 절편 3 -> [1,2,3] 찾아야 함

beta_gd = [10.1,15.1,-6.5] # 초기값
X_ = np.array([np.append(x, [1]) for x in X]) # intercept 항 추가
for t in range(5000):
    error = y - X_ @ beta_gd
    # error = error / np.linalg.norm(error)
    grad = - np.transpose(X_) @ error
    beta_gd = beta_gd - 0.01 * grad

print(beta_gd)

💡 학습률(lambda), 학습횟수(T) 는 매우 중요한 파라미터!

 

 

경사하강법의 한계

이론적으로 경사하강법은 미분가능하고 볼록 (convex) 한 함수에 대해서는 수렴 보장

→ 그레디언트 벡터가 항상 최소점을 향하기 때문

• 선형회귀는 회귀 계수 beta에 대해 볼록함수이므로 수렴이 보장됨
• 비선형회귀는 목적식이 볼록하지 않을 수 있으므로 수렴이 항상 보장되지 않음
  • 특히 딥러닝을 사용할 경우 대부분 목적식이 볼록함수가 아님

 

 

확률적 경사하강법 (SGD)

• 모든 데이터 대신 데이터 1개, 또는 일부를 활용해 업데이트
• 볼록이 아닌 (=non-convex) 목적식은 SGD를 통해 최적화 가능
• SGD에서는 모든 데이터를 사용하지 않고 데이터의 일부를 사용해 계산
  → 전체 그래디언트 벡터와 유사하긴 하지만 같지 않음
• 딥러닝의 경우 SGD가 경사하강법보다 실증적으로 더 낫다고 검증됨
• 현재는 미니배치 방식을 주로 쓰므로 SGD라는 용어가 나오면 minibatch SGD로 통용됨
• SGD는 데이터의 일부만으로 파러미터 업데이트 → 연산자원을 좀 더 효율적으로 활용 가능

 

 

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

경사하강법과의 차이

• 경사하강법은 전체 데이터 D = (X,y)를 가지고 목적식의 그래디언트 벡터인 $\nabla _{\theta} L(D, \theta)$를 계산함
• 그래디언트 벡터는 현재 주어진 파라미터 theta 에서 주어진 목적식의 최소점으로 향하는 방향 제시
• SGD는 미니배치 $D_{(b)} = (X_{(b)}, y_{(b)}) \in D$ 를 통해 그래디언트 벡터 계산
• 미니배치는 확률적으로 선택하므로 목적식 모양은 계속 바뀌지만, 방향은 유사할 것으로 기대됨

또한 볼록이 아닌 목적식에서도 사용 가능하므로 경사하강법보다 학습이 효율적

 

다양한 최적화 알고리즘

SGD 이후에도 많은 발전을 거쳐, 현재에는 개량된 Gradient descent 알고리즘들이 쓰이고 있다.

https://ll2ll.tistory.com/29

[논문 Review] 04. Overview of Gradient Descent algorithms

 

이 포스팅을 참고하면 Optimizer의 발전 방향을 살펴볼 수 있을 것이다.