Boostcamp AI Tech/AI Mathematics
경사 하강법 (Gradient Descent)
떼닝
2022. 6. 15. 02:53
미분
- 미분(differentiation)은 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구
미분식 - 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))에서의 접선의 기울기를 구함
- 접선의 기울기를 이용함으로써 어느 방향으로 점을 움직여야 함수값이 증가하는지/감소하는지 알 수 있음.
- 미분값이 음수일 경우 x의 값을 왼쪽으로 이동할수록 함수값이 증가
- 미분값이 양수일 경우 x의 값을 오른쪽으로 이동할수록 함수값이 증가 - 미분값을 더하면 경사상승법(gradient ascent). 함수의 극대값의 위치 구할 때 사용
- 미분값을 빼면 경사하강법(gradient descent). 함수의 극소값의 위치를 구할 때 사용
- 경사상승법/경사하강법은 모두 극값에 도달하면 움직임을 멈춘다
- Pseudo-code
Input : gradient, init, lr, eps, Output : var
---------------------------------------------
# gradient : 미분을 계산하는 함수
# init : 시작점, lr : 학습률, eps : 알고리즘 종료조건
var = init
grad = gradient(var)
while ( abs(grad) > eps ):
var = var - lr * grad
grad = gradient(var)
- Python
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]))
gradient_descent(fun=func, init_point=np.random.uniform(-2, 2))
변수가 벡터일 경우
- 벡터가 input으로 주어지는 다변수함수의 경우, 편미분(partial differentiation)을 사용
편미분식 - sympy.diff로 계산 가능
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)
- 각 변수별로 편미분을 계산한 gradient 벡터 이용하여 경사하강법/경사상승법에 사용할 수 있음

- pseudo-code
Input : gradient, init, lr, eps, Output : var
---------------------------------------------
# gradient : 그래디언트 벡터를 계산하는 함수
# init : 시작점, lr : 학습률, eps : 알고리즘 종료조건
var = init
grad = gradient(var)
while ( norm(grad) > eps ) :
var = var - lr * grad
grad = gradient(var)
- 경사하강법 알고리즘은 그대로 적용되나, 벡터는 절대값 대신 norm을 계산해서 종료조건 설정
- Python
# Multivariate Gradient Descent
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(02, 2), np.random.uniform(-2, 2)]
gradient_descent(fun=func_multi, init_point=pt)
경사하강법으로 선형회귀 계수 구하기
- 무어-펜로즈는 선형일 때만 사용 가능 / 선형회귀모델은 비선형에서도 사용 가능
- 선형회귀의 목적식은 L2-norm(||y-Xβ||) 이고, 이를 최소화하는 β를 찾아야함.
- 계산의 편리 위해 L2-norm(||y-Xβ||)를 제곱한 값을 사용.
- 최종적으로 구해지는 β의 식은

경사하강법 기반 선형회귀 알고리즘
- Pseudo-code
Input : 선형 모델 X, 정답 y, 학습률 lr, 학습 횟수 T, Output : beta
------------------------------------------------------------------
# norm : L2-norm을 계산하는 함수
for t in range(T):
error = y - X @beta
grad = - transpose(X) @ error
beta = beta - lr * grad
- Moore-Penrose처럼 정확한 값에 도달할 때까지 진행하는 것이 아니기 때문에 적절한 학습률과 학습횟수를 선택할 경우에만 수렴 보장됨
- 비선형회귀 문제의 경우 목적식이 볼록하지 않을 수 있어 수렴이 항상 보장되지는 않음
- Python
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) : # T를 5000으로 둠
error = y - X_ @ beta_gd
# error = error / np.linalg.norm(error)
grad = -np.transpose(X_) @ error
beta_gd = beta_gd - 0.01 * grad
print(beta_gd)
- 이론적으로 경사하강법은 미분가능하고 볼록(convex)한 함수에 대해서는 적절한 학습률과 학습횟수를 선택했을 때 수렴이 보장되어 있음.
- 비선형회귀 문제의 경우 목적식이 볼록하지 않을 수 있으므로 경사하강법을 사용한다고 했을 때 수렴이 항상 보장되지 않음. 이를 해결하기 위해 확률적 경사하강법을 사용
확률적 경사하강법 (stochastic gradient descent)

- 모든 데이터를 사용하는 경사하강법과 달리, 확률적 경사하강법은 데이터 한개, 또는 데이터의 일부(mini-batch)를 활용하여 업데이트함
- non-convex 목적식은 SGD를 통해 최적화할 수 있음
- 데이터를 모두 사용하는 경사하강법과는 달리, 데이터의 일부를 가지고 parameter를 update하기 때문에 연산자원을 효율적으로 활용 가능
- 미니배치는 데이터를 확률적으로 선택하므로 매번 목적식의 모양이 바뀜
- 값은 다를 수 있으나, 방향은 같을 것으로 기대함
- 연산량이 b/n으로 감소
- 목적식의 gradient를 근사해서 계산
경사하강법 vs 확률적 경사하강법

- 경사하강법에 비해 확률적 경사하강법의 메모리 효율이 높고, 적은 시간에 결과를 찾아낼 수 있음