Lec10: Mathematics for Artificial Intelligence_Gradient Descent

01_Differentiation

1) Differentiation?

• Differentiation : 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구, Optimization에서 제일 많이 사용하는 기법, 변화율의 극한으로 정의한다.
  

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')

• 한 점에서 접선의 기울기를 알면 어느 방향이 함수의 증가이고 감소인지 알 수 있다.
  
• 미분값을 더하면 경사상승법(=Gradient Ascent)이라 하며, 함수의 극대값 위치를 구할 때 사용.
  
• 미분값을 빼면 경사하강법(=Gradient Descent)이라 하며, 함수의 극소값 위치를 구할 때 사용.
  
• Gradient Ascent/Descent는 극값에 도달하면 움직임을 멈춘다.
  

2) Gradient Descent : Algorithm

컴퓨터로 계산할 때 미분이 정확히 0이 되는 것은 불가능하므로 eps보다 작을 때 종료하는 조건이 필요.

• Input : gradient, init, lr, eps
• Output : var

  • gradient : 미분을 계산하는 함수
  • init : 시작점
  • lr : Learning Rate, 미분을 통해 업데이트하는 속도를 조절
  • eps : Epsilon, Algorithm 종료 조건

var = init
grad = gradient(var)
while(abs(grad) > eps):
	var = var - lr * grad # 변수 - 학습률 * 접선의 기울기
    grad = gradient(var) # 종료 조건이 성립하기 전까지 미분값을 계속 업데이트

• 함수가 x*2 + 2x + 3일 때 Gradient Descent로 최소점을 찾는 코드

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-5):
	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("함수: {}, 연산횟수: {}, 최소점: ({}, {})".format(fun(val)[1], cnt, val, fun(val)[0]))
# 함수: Poly(x**2 + 2*x + 3, x, domain='ZZ'), 연산횟수: 636, 최소점: (-0.999995047967832, 2.00000000002452)

3) If Variable = Vector?

• Vector가 Input인 다변수 함수의 경우 Partial Differentiation을 사용.
  

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)
# 2*x + 2*y - sin(x + 2*y)

• 각 변수 별로 편미분을 계산한 Gradient Vector를 이용하여 Gradient Ascent/Descent에 사용 가능.
  

4) Grandient Vector?

5) Gradient Descent : Algorithm#2

• Gradient Descent Algorithm은 그대로 적용, 그러나 Vector는 abs 대신 norm을 계산해서 eps를 설정.

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

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
    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-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

	print("함수: {}, 연산횟수: {}, 최소점: ({}, {})".format(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)
# 함수: Poly(x**2 + 2*y**2, x, y, domain='ZZ'), 연산횟수: 606, 최소점: ([4.95901570e-06 2.88641061e-11], 2.45918366929856E-11)