[WEEK 1] AI Math - 경사하강법

▶ 미분

• $f'(x) = \lim_{h\to 0}{{f(x+h)-f(x)}\over h}$
• 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구이다.
• 최적화에서 제일 많이 사용하는 기법이다.
• 기울기 = 변화율
• 변화율의 극한 = 미분

import sympy as sym
from sympy.abc import x

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

# sym.diff : 미분 구하는 함수
# Poly(2𝑥+2,𝑥,𝑑𝑜𝑚𝑎𝑖𝑛=ℤ)

• 미분 : 주어진 점 $(x, f(x))$ 에서의 접선의 기울기를 계산하는 것이다.
• 한 점에서 접선의 기울기를 알면 어느 방향으로 움직여야 함수값이 증가/감소 하는지 알 수 있다.

• 양수 / 음수 미분값 상관없이
  • 함수를 증가시키고 싶으면 미분값을 더한다.
    • 경사상승법 (gradient ascent)
    • 함수의 극대값의 위치를 구할 때 사용한다.
    • 목적 함수를 최대화할 때 사용한다.
  • 함수를 감소시키고 싶으면 미분값을 뺀다.
    • 경사하강법 (gradient descent)
    • 함수의 극소값의 위치를 구할 때 사용한다.
    • 목적 함수를 최소화할 때 사용한다.
• 극값에 도달하게 되면 미분값이 0이므로 움직임을 멈춘다. 

 

▶ 경사하강법 : 알고리즘

# gradient : 미분을 계산하는 함수
# init : 시작점, lr : 학습률, eps : 종료조건

var = init
grad = gradient(var)

while(abs(grad) > eps):
		var = var - lr * grad
		grad = gradient(var)

• 컴퓨터의 경우 미분값이 정확히 0이 될 수 없으므로 eps 보다 작을 때 종료하게 된다.

 

▶ 변수가 벡터일 때

• $\partial_{x_i}f(x)=\lim_{h\to 0}{f(x+he_i)-f(x)\over h}$
• $e_i$ : i번째 값만 1이고 나머지는 0인 단위 벡터
• 벡터가 입력인 다변수 함수의 경우에는 편미분을 사용한다.
• 편미분 : 다변수 함수의 특정 변수를 제외한 나머지 변수를 상수로 간주하고 미분하는 것이다.
• 편미분을 이용하면 i번째 방향에서의 변화율을 알 수 있다.
• 각 변수 별 편미분을 계산한 그래디언트 벡터를 이용하여 경사하강/경사상승법에 사용할 수 있다.

 

▶ 그레디언트 벡터

• $\nabla f=(\partial_{x_1}f, \partial_{x_2}f, \cdots, \partial_{x_d}f)$
• $\nabla f$는 각 점에서 가장 빨리 증가하는 방향으로 흐른다. → 주어진 함수의 극소점으로 향하는 방향 알 수 있음
• -$\nabla f$ 는 각 점에서 가장 빨리 감소하는 방향으로 흐른다. → 주어진 함수의 극대점으로 향하는 방향 알 수 있음

# gradient : 미분을 계산하는 함수
# init : 시작점, lr : 학습률, eps : 종료조건

var = init
grad = gradient(var)

while (norm(grad) > eps) : 
		var = var - lr * grad
		grad = gradient(var)

• 벡터는 절대값 대신 노름 계산해서 종료조건 설정한다.

 

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

• 선형모델의 경우 무어-펜로즈 역행렬을 이용해서 가능하지만, 선형모델이 아닌 경우 무어-펜로즈를 사용하지 못하게 되며 경사하강법을 일반적으로 사용하므로 경사하강법을 통한 선형모델을 알아야한다.
• 선형회귀의 목적식 : $||\mathbf y- \mathbf X\beta||_2$ ($y$ : 정답, $X\beta$ : 선형모델)
• 목적식을 최소화하는 $\beta$를 찾아야 하기 때문에 아래와 같은 그래디언트 벡터를 구해야 한다.
• $\nabla_\beta||y-X\beta||_2=(\partial_{\beta_1}||y-X\beta||_2,  \cdots , \partial_{\beta_d}||y- X\beta||_2)$
• $\delta_{\beta_k}||y-X_\beta||2=\delta{\beta_k} \left\{ {1\over n }\sum_{i=1}^n(y_i -\sum_{j=1}^d X_{ij}\beta_j)^2\right\}^{1/2} = -{ {X_{\cdot k}^T(y-X\beta)}\over{n||y-X\beta||_2}}$
• 복잡한 계산이지만 사실 $X\beta$를 계수 $\beta$에 대해 미분한 결과인 $X^T$만 곱해지는 것
• 최소화하는 $\beta$를 찾으려면 목적식을 $\beta$로 미분한 뒤 주어진 $\beta$에서 미분값을 빼주면서 최소값을 구할 수 있다.
• $\beta^{(t+1)} \leftarrow \beta^{(t)} - \lambda \nabla_\beta||y-X\beta^{(t)}||$ 
• 위에서 구한 그레디언트 벡터를 대입하면 뒤의 값의 부호가 +로 바뀐다.
• L2-노름의 제곱을 이용해 그레이언트 벡터 구하면 계산을 좀 더 간단해진다.

# norm : L2-노름을 계산하는 함수
# lr : 학습률, T : 학습 횟수

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

 

▶ 경사하강법은 만능일까?

• 이론적으로 경사하강법은 미분 가능하고 볼록한 함수에 대해선 적절한 학습률과 학습횟수를 선택했을 때 수렴이 보장되어 있다.
• 특히 선형회귀의 경우 목적식 $||\mathbf y-\mathbf X\beta||_2$은 회귀계수 $\beta$에 대해 볼록함수이므로 수렴이 보장된다.
• 비선형회귀 문제의 경우 목적식이 볼록하지 않을 수 있으므로 수렴이 항상 보장되지는 않는다.

 

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

• 확률적 경사하강법은 모든 데이터를 사용해서 업데이트하는 대신 데이터 한개 또는 일부 (mini batch) 활용하여 업데이트한다.
• 볼록이 아닌(non-convex) 목적식은 SGD를 통해 최적화할 수 있다.
• SGD는 데이터의 일부를 가지고 파라미터를 업데이트하기 때문에 GD에 비해 연산량이 감소한다.
• 미니배치를 써서 업데이트 하므로 연산량이 b/n으로 감소한다.

 

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

• 경사하강법은 전체데이터 $\mathcal D =(\mathbf X, \mathbf y)$를 가지고 목적식의 그래디언트 벡터인 $\nabla_\theta L(\mathcal D, \theta)$ 계산한다.
• SGD는 미니배치 $\mathcal D_{(b)}=(\mathbf X_{(b)}, \mathbf y_{(b)} ) \subset \mathcal D$를 가지고 그래디언트 벡터를 계산한다.
• 매번 다른 미니배치를 사용하기 때문에 목적식 모양이 점점 바뀌게 된다.
• 경사하강법으로 local minimum에 수렴했더라도 SGD를 사용하게 되면 벗어날 수 있다..

 

※ 모든 시각 자료는 부스트 캠프 AI Tech 교육 자료를 참고했습니다.