📌(AI Math 3강) 경사하강법 - 순한맛

✍미분이 뭔가요?

• 미분(differentiation)은 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구

• 최적화에서 제일 많이 사용하는 기법

  • 미분은 변화율의 극한(limit) 으로 정의합니다.
  • $f^{'}(x) = \lim_{h \to 0} \frac{f(x+h)-f(x)}{h}$

• 파이썬을 사용해서 계산하려면 sympy.diff 로 계산할 수 있습니다.

☛ 입력

import sympy as sym
from sympy.abc import x

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

☛ 출력

Poly(2*x + 2, x, domain='zz')

• 미분은 함수 $f$ 의 주어진 점 $(x,f(x))$ 에서의 접선의 기울기를 구합니다.

• 한 점에서 접선의 기울기를 알면 어느 방향으로 점을 움직여야 함수값이 증가하는지 감소하는지 알 수 있습니다.

  • 함수값을 증가시키고 싶다면 미분값을 더하고, 감소시키고 싶다면 미분값을 뺍니다.
    

• 미분값을 빼면 경사하강법(gradient descent) 이라 하며 함수의 극소값의 위치를 구할 때 사용합니다. 즉, 목적함수를 최소화할 때 사용합니다.

  • 극값에서 미분값은 0 이므로 목적함수 최적화는 자동으로 끝난다.

✍경사하강법 : 알고리즘

1  Input: gradient, init, lr, eps,   Output: var
2  ---------------------------------------------
3  # gradient : 미분을 계산하는 함수
4  # init : 시작점,  lr : 학습률,  eps: 알고리즘 종료조건
5  
6  var = init
7  grad = gradient(var)
8  while(abs(grad) > eps):  # 컴퓨터로 계산할 때 미분이 정확히 0이 되는 것은 불가능하므로 `eps` 보다 작을 때 종료하는 조건이 필요.
9  	var = var - lr * grad  # 이 부분이 x-lr*f(x)을 계산하는 부분. lr은 학습률로 업데이트 속도를 조절
10	grad = gradient(var)  # 종료조건이 성립하기 전까지 미분값을 계속 업데이트

아래 그림은 함수가 $f(x)=x^2+2x+3$

• def func

  • sym.poly 함수는 함수식을 정의해줍니다.
  • sym.subs 함수는 변수를 다른변수로 치환하거나 값을 대입해줍니다.

• func_gradient

  • sym.diff 함수는 도함수를 구해줍니다.
  • func 함수를 사용하여 미분값과 함수를 return하는 코드를 짜야합니다.

• gradient_descent

  • init_point는 경사하강법의 시작점을 의미합니다.
  • lr_rate는 learning rate로 step의 크기를 정해줍니다.
  • epsilon은 gradient 크기의 lower bound입니다.
    
    

✍변수가 벡터이면요?

• 벡터가 입력인 다변수 함수의 경우 편미분(partial differentiation)을 사용합니다.

  • 벡터 $x$ 의 $i$ 번째 값을 편미분 하면 -> $\partial_{x_i}f(x)=\lim_{h \to 0} \frac{f(x+he_i)-f(x)}{h}$

  • $e_i$

• 각 변수 별로 편미분을 계산한 그레디언트(gradient) 벡터를 이용하여 경사하강/경사상승법에 사용할 수 있습니다. 아래 그림은 함수 $f$ 를 벡터 $x$ 에 대해 편미분한 것이며, 앞서 사용한 미분값인 $f^{'}(x)$

✍그레디언트 벡터가 뭐에요?

그레디언트를 이해하기 위해 함수 $f(x,y)$ 의 등고선(contour) 을 보면서 해석해보겠습니다.
먼저 각 점 $(x,y,z)$

✍경사하강법(그레디언트 벡터): 알고리즘

1  Input: gradient, init, lr, eps,   Output: var
2  ---------------------------------------------
3  # gradient : 그레디언트 벡터를 계산하는 함수
4  # init : 시작점,  lr : 학습률,  eps: 알고리즘 종료조건
5  
6  var = init
7  grad = gradient(var)
8  while(norm(grad) > eps):  
9  	var = var - lr * grad
10 	grad = gradient(var)

경사하강법 알고리즘은 그대로 적용됩니다. 하지만 벡터는 절대값 대신 노름(norm)을 계산해서 종료조건을 설정합니다.

• def eval_

  • sym.subs 함수는 변수를 다른변수로 치환하거나 값을 대입해줍니다.

• def func_multi

  • 다변수함수를 정의하는 함수입니다.
  • sym.poly 함수는 함수식을 정의해줍니다.

• func_gradient

  • sym.diff 함수는 도함수를 구해줍니다.
  • func 함수를 사용하여 미분값과 함수를 return하는 코드를 짜야합니다.

• gradient_descent

  • init_point는 경사하강법의 시작점을 의미합니다.
  • lr_rate는 learning rate로 step의 크기를 정해줍니다.
  • epsilon은 gradient 크기의 lower bound입니다.
  • 종료조건을 노름(norm)으로 계산하여 설정합니다.

📌(AI Math 4강) 경사하강법 - 매운맛

✍선형회귀분석 복습

• np.linalg.pinv를 이용하면 데이터를 선형모델(linear model)로 해석하는 선형회귀식을 찾을 수 있습니다.
  
  하지만 이번 시간에서는 역행렬을 이용하지 않고 경사하강법을 이용해 적절한 선형모델을 찾는 방법에 대해서 알아보겠습니다.

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

• 선형회귀의 목적함수는 $||y-X\beta||_2$

• 아래 그림은 목적함수 $||y-X\beta||_2$

• 위 식이 좀 복잡하시면, $||y-X\beta||_2$

  위 그림의 식은 $-\frac{2}{n}X^T(y-X\beta)$

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

1  Input: X, y, lr, T,   Output: beta
2  ---------------------------------------------
3  # norm: L2-노름을 계산하는 함수
4  # lr : 학습률,  T: 학습횟수
5  
6  for t in range(T):
7  	error = y - X @ beta
8  	grad = - transpose(X) @ error
9  	beta = beta - lr * grad

• line 6 : 종료조건을 일정 학습횟수로 변경한 점만 빼고 앞에서 배운 경사하강법 알고리즘과 같다.

• line 7 ~ 9 : $\nabla_{\beta} ||y-X\beta||_{2}^{2}$

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

• 이론적으로 경사하강법은 미분가능하고 볼록(convex)한 함수에 대해선 적절한 학습률과 학습횟수를 선택했을 때 수렴이 보장되어 있습니다.

• 특히 선형회귀의 경우 목적함수 $||y-X\beta||_{2}$

• 하지만 비선형회귀 문제의 경우 목적함수가 볼록하지 않을 수 있으므로 수렴이 항상 보장되지는 않습니다.
  

✍ 확률적 경사하강법

• 확률적 경사하강법(stochastic gradient descent)은 모든 데이터를 사용해서 업데이터하는 대신 데이터 한개 혹은 일부를 활용하여 업데이트 합니다.

• non-convex한 목적함수는 SGD를 통해 최적화할 수 있습니다.

• SGD는 데이터의 일부를 가지고 파라미터를 업데이트하기 때문에 연산자원을 좀 더 효율적으로 활용하는데 도움이 됩니다.
  
  

정규방정식이 이해하기 어려워서 다음 블로그를 참고하시면 좋을 것 같습니다.
[머신러닝 reboot] 단순 선형 회귀 분석 - 정규방정식 도출하기