경사하강법

출처: 네이버 부스트코스 인공지능(AI) 기초 다지기 3. 기초 수학 첫걸음

<목차>
1. 미분
2. 경사하강법
3. 편미분
 - 변수가 벡터일때
4. Gradient vector

 

 

 

미분(differentiation)  sym.diff

• 변수의 움직임에 따른 함수 값의 변화를 측정하기 위한 도구

import sympy as sym
from sympy.abc import x
sym.diff(sym.poly(x**2+2*x+3), x)
#Poly(2𝑥+2,𝑥,𝑑𝑜𝑚𝑎𝑖𝑛=ℤ)

 

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

h를 0으로 보내면 (x, f(x))에서 접선의 기울기로 수렴

 

• 한 점에서 접선의 기울기를 알면 어느 방향으로 점을 움직여야 함수값이 증가하는지/ 감소하는 지 알 수 있음
• 미분 값을 더하면 경사상승법(gradient ascent)라고 하며, 함수의 극대값의 위치를 구할 때 사용한다
• 미분 값을 빼면 경사하강법(gradient descent)라고 하며, 함수의 극소값의 위치를 구할 때 사용한다
• 두 방법은 극값에 도달하면 움직임을 멈춘다(극값에선 미분값이 0이므로 더 이상 업데이트가 안되고 목적함수 최적화가 자동으로 끝남)

---

경사하강법 알고리즘

경사하강법을 사용하여 구한 함수의 극소값의 위치는 해당 함수의 최소값의 위치가 아닐 수 있다.

'''
Input: gradient(미분을 계산하는 함수), init(시작점), lr(학습률), eps(알고리즘 종료조건)
Output: var
'''
var = init
grad = gradient(var)
while(abs(grad) > eps): #컴퓨터로 계산할 때 미분이 정확히 0이 되는 건 불가능하므로 eps보다 작을 때 종료하도록 함
 var = var - lr * grad #x − λf′(x)를 계산하는 부분. lr은 미분을 통해 업데이트하는 속도를 조절함
 grad = gradient(var) #종료조건 성립전까지 미분값 업데이트

import numpy as np
import sympy as sym
from sympy.abc import x

def func(val):
    fun = sym.poly(x**2 + 2*x +3)
    return fun.subs(x, val), fun # subs(x, val) x에 val 값을 대입해라

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("function: {}, cnt: {}. 최소점: ({}, {})".format( fun(val)[1], cnt, val, fun(val)[0] ) )
    
gradient_descent(fun= func, init_point=np.random.uniform(-2,2))    
#function: Poly(x**2 + 2*x + 3, x, domain='ZZ'), cnt: 613. 최소점: (-0.999995024012154, 2.00000000002476)

---

변수가 벡터일 경우

• 벡터가 입력인 다변수 함수는 편미분(partial differentiation)을 이용한다

e^i는 i번째 방향에서만 변화율 계산가능

 

y는 무시하고 x 방향만 계산 (y방향만 계산도 가능)

 

• 각 변수 별로 편미분을 계산한 그레디언트(gradient) 벡터를 이용해 경사하강/상승법에 사용할 수 있음

미분이 변수가 한 개인 함수에 대한 기울기를 구하는 것이라면 Gradient는 다변수 함수에 대한 기울기를 구하는 것

 

 

다변수를 입력으로 받는 함수의 gradient 벡터는 nabla를 사용해 표시

 

---

Gradient vector

 

- gradient vector 의 방향으로 따라가면 무조건 최소점에 도달

 

• ∇f(x,y)는 각 점(x,y)에서 가장 빨리 증가하는 방향으로 흐르게 됨
• -∇f는 ∇(-f)와 같고 이는 각 점에서 가장 빨리 감소하게 되는 방향과 같음

접선의 기울기를 이용해서 함수의 최솟값으로 점을 이동시키는 원리

변수가 벡터인 경우, 편미분을 통해서 구한 Gradient vector를 통해 d-차원으로 경사하강법을 확장할 수 있다

 

'''
Input: gradient(gradient vector을 계산하는 함수), init(시작점), lr(학습률), eps(알고리즘 종료조건)
Output: var
'''
var = init
grad = gradient(var)
while(norm(grad) > eps): #벡터는 절대값 대신 norm을 계산해서 종료 조건 설정
 var = var - lr * grad 
 grad = gradient(var)

import numpy as np
import sympy as sym
from sympy.abc import x
from sympy.abc import y

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("function: {}, cnt: {}. 최소점: ({}, {})".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)    
#function: Poly(x**2 + 2*y**2, x, y, domain='ZZ'), cnt: 549. 최소점: ([-4.91756234e-06 -1.11559624e-10], 2.41824194218619E-11)