미분과 경사하강법(Gradient Descent)

 

 

미분 (Differentiation)

 

미분의 정의

 

[출처] https://commons.wikimedia.org/wiki/File:Derivative1.png, Koantum

미분은 다음과 같이 정의할 수 있다.

 

• 변수의 변화에 따른 함수값의 변화량
• 함수 위의 주어진 점에서의 접선의 기울기
• 변화율의 극한

 

함수 내에서 미분을 사용하면 변수의 특정 값에서의 기울기를 구할 수 있다. 한 점에서 기울기를 알면 어느 방향으로 점을 움직여야 함수값이 증가 또는 감소하는지를 알 수 있다.

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

$$f(x) = x^2 + 2x + 3$$

$$f'(x) = 2x + 2$$

$f(x) = x^2 + 2x + 3$의 미분은 $f'(x) = 2x + 2$이다. $x$의 값에 따라 기울기는 양수가 될 수도, 음수가 될 수도 있다

 

python에서는 sympy 모듈을 통해 미분을 수행할 수 있다.

import sympy as sym
from sympy.abc import x

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

 

 

 

미분과 함숫값

 

미분을 통해 구한 값인 기울기는 변수의 증감에 따른 함수값의 증감을 알려준다. 이때, 어떤 경우이든 $x$에 $f'(x)$값을 더하면 $f(x)$는 증가하고, 빼면 감소한다.

 

• 미분값이 양수이면
  • 미분값을 더하면 함수값이 증가한다.
  • 미분값을 빼면 함수값이 감소한다.
• 미분값이 음수이면
  • 미분값을 더하면 함수값이 증가한다.
  • 미분값을 빼면 함수값이 감소한다.

즉, $f'(x)$의 값이 양수이든 음수이든 어떤 경우에도 $x$에 $f'(x)$값을 더하면 $f(x)$는 증가하고, $f'(x)$값을 빼면 감소한다.

 

 

경사하강법(Gradient Descent)

 

경사상승법과 경사하강법

 

• 경사상승법(Gradient Ascent)  
  • 미분값 $f'(x)$을 더하여 함수의 극댓값의 위치를 구한다.

 

• 경사하강법(Gradient Descent)
  • 미분값 $f'(x)$을 빼서 함수의 극솟값의 위치를 구한다.

 

경사상승법 또는 경사하강법을 통해 $f'(x) = 0$에 근사해지면 극값에 수렴한다.

머신러닝에서는 손실함수의 극솟값을 찾는 것을 목표로 하므로 경사하강법을 사용하며, epsilon 값이 일정 수치 이하일 때 경사하강법 수행을 종료하는 등 종료 조건을 정하여 미분값 $f'(x)$의 절댓값 크기가 일정 수치 이하가 되었는지를 판단할 때까지 진행한다.
이는 컴퓨터에서 미분값이 0이 되는 것은 매우 어렵기 때문이다.

극대, 극소가 함수의 최대, 최소를 의미하지는 않는다.
그래서 미분을 통해 최대, 최소가 아닌 극대 또는 극소에서 수렴하지 않도록 위치가 변하는 속도를 조절하기 위해 learning rate를 사용한다.

아래 예시 코드는 $x^2 + 2x + 3$ 함수에 경사하강법을 적용해 극솟값과 $x$값을 찾는 것이다.

 

def func(val):
  fun = sym.poly(x**2 + 2 * x + 3)
  # subs()로 식의 변수에 특정 값을 대입한 결과를 구할 수 있다.
  return fun.subs(x, val, fun)

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

def gradient_descent(fun, init_point, lr_rate=1e-2, epsilon = 1e-5):
  cnt = 0
  val = init_point
  diff, _ = func_gradient(fun, val)
  while np.abs(diff) > epsilon:
    val = val - lr_rate * diff
    diff, _ = func_gradient(fun, val)
    cnt += 1
    
# 사용 예시
gradient_descent(fun = func, init_point = np.random.uniform(-2, 2))

 

 

Gradient Vector

 

미분에서 변수가 벡터이면 편미분(Partial Differentiation)을 사용한다.
즉, 다변수 함수이면 편미분을 사용한다.

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

$x$에 대한 편미분: $\delta_xf(x,y) = 2x + 2y - sin(x+2y)$
$y$에 대한 편미분: $\delta_yf(x,y) = 2x - sin(x+2y)$

벡터의 각 변수별로 편미분을 계산한 것이 그라디언트 벡터(gradient vector)이다. 이는 $n$차원의 공간에서의 변화량을 구하여 극소, 극대값을 찾을 수 있도록 한다. 즉, 변수가 둘 이상인 경우에는 편미분을 통해 그라디언트 벡터를 이용하여 경사하강법을 진행한다.
각 변수에 대한 편미분 값을 요소로 갖는 벡터가 Gradient Vector이며, 공간 상에서 특정 위치에서의 기울기가 된다.

$(x_1, x_2, ..., x_d)$의 Gradient Vector

$\nabla{f} = (\delta_{x_1}f, \delta_{x_2}f, \cdots , \delta_{x_d}f)$

벡터이기 때문에 단순히 앞에서 미분값의 절댓값 크기로 종료 조건을 정한 것과는 다르게 norm을 계산하여 종료조건을 정한다.
Gradient Vector를 가지고 경사하강법을 적용한 식을 일반화하여 정리하면 다음과 같다.

$$\mathbf{x}^{(t+1)} \leftarrow \mathbf{x}^{(t)}-\nabla{f}$$

아래 예시 코드는 $x^2 + 2y^2$ 함수에 경사하강법을 적용한 것이다.

 

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_multi(val):
  x_, y_ = val
  fun = sym.poly(x**2 + 2 * y ** 2)
  return eval_(fun, [x_, y_]), func

def func_gradient(fun, val):
  x_, y_ = val
  __, function = func_multi(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-5):
  cnt = 0
  val = init_point
  diff, _ = func_gradient(fun, val)
  while np.linalg.norm(diff) > epsilon:
    val = val - lr_rate * diff
    diff, _ = func_gradient(fun, val)
    cnt += 1
    
# 사용 예시
pt = [np.random.uniform(-2, 2), np.random.uniform(-2, 2)]
gradient_descent(fun = func, init_point = pt)

 

선형회귀분석과 경사하강법

 

선형회귀분석에서의 목적함수

행렬 $\mathbf{X}$에 $m$개의 변수와 $n$개의 샘플이 있고, 각 샘플에 대한 결과값인 $\mathbf{y}$가 있는 상태를 가정하자 이때, $\mathbf{X}\beta = \hat{\mathbf{y}} \approx \mathbf{y}$를 만족하는 $\beta$를 찾고자 하는 것이 선형회귀분석이다.
하지만 어떤 $\beta$으로도 $\mathbf{X}\beta = \mathbf{y}$를 만족시키는 건 거의 불가능하므로 목적함수를 설정하는데, 이는 $\mathbf{y} - \hat{\mathbf{y}} $의 $L_2$ Norm을 최소화하는 것으로 한다.
$min_\beta||\mathbf{y} - \hat{\mathbf{y}}||_2$
즉, $||\mathbf{y} - \hat{\mathbf{y}}||_2$를 최소화하는 $\beta$를 구하는 것이 목표이다.

 

 

$\nabla_{\beta}$를 통한 경사하강법

위의 목적함수에 따라 $\beta$를 업데이트 하기 위해선 $\beta$에 대한 gradient vector를 구해야 한다.

$$\beta = (\beta_1, \beta_2, \cdots, \beta_d)$$

$$\nabla_{\beta}||\mathbf{y} - \mathbf{X}\beta||_2=(\delta_{\beta_1}||\mathbf{y} - \mathbf{X}\beta||_2, \cdots, \delta_{\beta_d}||\mathbf{y} - \mathbf{X}\beta||_2)$$

$k$번째 $\beta$에 대한 미분값을 확인하면 다음과 같다.

 

$$ \begin{aligned} δ_{β_{k}}||\mathbf{y}−\mathbf{X}β||_2&=δ_{β_k}\{\frac{1}{n}∑^n_{i=1}(y_i−∑^d_{j=1}X_{ij}β_j)^2\}^\frac{1}{2}\\&=-\frac{\mathbf{X}_{k}^{T}(\mathbf{y} - \mathbf{X}\beta)}{n||\mathbf{y} - \mathbf{X}\beta||_2} \end{aligned} $$

 

한 개의 점에 대한 $L_2$ Norm이 아니라 $n$개의 데이터에 대한 $L_2$ Norm을 계산하는 것이므로 1에서 $n$까지의 값을 모두 더해준 후 $n$으로 나누어 평균값을 사용한다.
목적함수의 값을 최소화하기 위해 $\beta$를 업데이트하는 식을 정리하면 다음과 같다.

 

$$ \begin{aligned} \beta^{(t+1)} &\leftarrow \beta^{(t)} - \lambda\nabla_{\beta}||\mathbf{y} - \mathbf{X}\beta^{(t)}||_2\\&=\beta^{(t)}-\frac{\lambda\mathbf{X}_{k}^{T}(\mathbf{y} - \mathbf{X}\beta^{(t)})}{n||\mathbf{y} - \mathbf{X}\beta^{(t)}||_2} \end{aligned} $$

 

네이버 부스트캠프 AI Tech 질문 게시판에 올라온 다른 캠퍼분의 답변을 참고하여 위 식의 도출과정을 정리해봤다.

$||\mathbf{y}−\mathbf{X}β||_2$ 대신 $||\mathbf{y}−\mathbf{X}β||_2^2$를 최소화하면 식이 좀 더 간결해진다.

 

$$ \begin{aligned} \nabla_{\beta}||\mathbf{y} - \mathbf{X}\beta||_2^2&=(\delta_{\beta_1}||\mathbf{y} - \mathbf{X}\beta||_2^2, \cdots, \delta_{\beta_d}||\mathbf{y} - \mathbf{X}\beta||_2^2)\\&=-\frac{2}{n}X^T(\mathbf{y}-\mathbf{X}\beta) \end{aligned} $$

 

$$ \begin{aligned} \beta^{(t+1)} &\leftarrow \beta^{(t)} - \lambda\nabla_{\beta}||\mathbf{y} - \mathbf{X}\beta^{(t)}||_2\\&=\beta^{(t)}-\frac{2\lambda}{n}\mathbf{X}_{k}^{T}(\mathbf{y} - \mathbf{X}\beta^{(t)}) \end{aligned} $$

 

 

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

학습 종료 조건을 Gradient Vector의 Norm 값으로 정할 수도 있지만, 학습 횟수와 같은 종료 조건을 사용하기도 한다.

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

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

아래는 $\beta$의 참값이 1, 2, 3인 선형회귀 문제에 경사하강법을 적용하는 예시 코드이다.

X = np.array([[1, 1], [1, 2], [2, 2], [2, 3]])
y = np.dot(X, np.array([1, 2])) + 3

beta_gd = [10.1, 15.1, -6.5] # [1, 2, 3]이 정답
X_ = np.array([np.append(x, [1]) for x in X]) # intercept 항 추가

for t in range(5000):
	error = y - X_ @ beta_gd
	grad = - np.transpose(X_) @ error
	beta_gd = beta_gd - 0.01 * grad
  

 

 

경사하강법의 한계

 

위의 알고리즘은 다음과 같은 이유로 모든 상황에서 작동하지는 않는다.

• 이론적으로 경사하강법을 사용하려면 목적함수가 모든 지점에서 미분 가능해야하며, 볼록한(convex) 형태를 가져야 한다.
• 선형회귀의 경우 목적식 $\|\mathbf{y} - \mathbf{X}\beta\|_2$은 회귀계수 $\beta$에 대해 볼록함수이므로 알고리즘을 충분히 돌리면 수렴이 보장된다.
• 하지만 비선형회귀 문제의 경우 목적식이 볼록하지 않을 수 있으므로 수렴이 항상 보장되지 않는다.
• Learning Rate 값이 너무 작거나 커서 지역적인 극소 위치로 수렴할 경우 전체 목적식에 대한 최솟값을 보장하지 못한다.

 

 

확률적 경사하강법(Stochastic Gradient Descent)

 

확률적 경사하강법은 매 업데이트마다 Gradient Vector를 계산할 때 전체 데이터 셋을 이용하는 것이 아닌 추출된 데이터 중 일부의 데이터만 사용하는 기법이다.

이는 기존의 경사하강법의 한계를 보완할 수 있으며, 볼록이 아닌(non-convex) 목적식은 SGD를 통해 최적화할 수 있다.

 

• SGD: 한 개의 데이터만 활용해서 gradient를 계산하는 것이다.
• Mini-Batch SGD: Mini-Batch 크기만큼 데이터 일부만 활용해서 gradient를 계산하는 것이다.

 

다음과 같은 장점으로 인해 ML과 DL에서는 SGD가 경사하강법보다 더 나은 것으로 알려져 있다.

 

• 모든 데이터를 사용하는 경사하강법은 컴퓨텅 자원(특히 메모리)이 많이 필요하지만, 일부 데이터로 Gradient를 구하는 SGD도 전체 데이터를 사용하는 것에 근접한 성능을 보인다.
• 데이터의 일부(Mini Batch)는 확률적으로 선택해서 매번 바뀌므로 목적식도 일부 바뀐다. 이를 통해 국소적인 최소, 최대(Locally Optimized Point)인 위치에 와도 탈출이 가능하다.
• 연산이 효율적이어서 훨씬 빠르게 최소점을 찾는다.
• Gradient Vector를 업데이트 동안 데이터 전처리 및 계산 준비를 할 수 있어서 병렬 처리가 가능하다.