Gradient Descent

Gradient Descent

• 1차 근삿값 발견용 최적화 알고리즘
• 함수의 기울기(경사)를 구하고 경사의 절대값이 낮은 쪽으로 계속 이동시켜 극값에 이를 때 까지 반복시키는 것

최적화할 함수 ${\displaystyle f(\mathbf {x} )}$에 대하여, 먼저 시작점 $\mathbf {x} _{0}$를 정한다. 현재 가 주어졌을 때, 그 다음으로 이동할 점인 ${\mathbf {x}}{i}$은 다음과 같이 계산된다.

${\displaystyle \mathbf {x} _{i+1}=\mathbf {x} _{i}-\gamma _{i}\nabla f(\mathbf {x} _{i})}$

이때 $\gamma _{i}$는 이동할 거리를 조절하는 매개변수이다.이 알고리즘의 수렴 여부는 $f$의 성질과 $\gamma _{i}$ 의 선택에 따라 달라진다. 또한, 이 알고리즘은 지역 최적해(극값)로 수렴한다.따라서 구한 값이 전역적인 최적해라는 것을 보장하지 않으며 시작점 $\mathbf {x}_{0}$ 의 선택에 따라서 달라진다.

이에 따라 다양한 시작점에 대해 하강법을 적용하여 그 중 가장 좋은 결과를 선택할 수도 있다.

Cost Function

• 예측값과 기댓값의 차이를 정량화 하고 하나의 실수 형태로 표현한다.
• $Hypothesis : H_{\theta} = \theta_0 + \theta_1x$
• $Parameters : \theta_0, \theta_1$
• $Cost Function : J(\theta_0, \theta_1) = \frac 1 {2m} \sum^m_{i=1}(h_{\theta}(x^{(i)})-y^{(i)})^2$
• $Goal : \underset{\theta_0,\theta_1}{minimize}\ J(\theta_0, \theta_1)$

• 단계
  • gradient(해당 점에서의 1차 미분계수) 계산,
  • 해당 점에서 gradient의 alpha배 만큼 경사가 증가하는 반대 방향으로 나아간다.

Gradient Desent Algorithm

repeat\ until\ convergence\ \{
\theta_j := \theta_j - \alpha \frac{\partial}{\partial \theta_j}J(\theta_0,\theta_1)
(for\ j=1\ and\ j=0) \}

alpha : learning rate, 최적화 과정에서의 tuning parameter, step의 길이를 결정

• a) 최적 alpha, 최솟값으로 수렴
• b) 너무 작음, 수렴하는데 너무 오래 걸림
• c) 너무 크다, 수렴하지만, overshoot
• d) 너무 크다, overshoot & 발산, 최적점에서 멀어진다
• 너무 작으면 오래걸림, 너무 크면 진동하거나 발산

local minima

• 근방에서의 최소점

평가 및 장단점

장점

- 모든 차원과 모든 공간에서의 적용 가능(무한 차원도 가능)

단점

- 정확성을 위해 극값으로 이동 시 매우 많은 단계를 거침
- 함수의 곡률에 따라 같은 위치에서 시작해도 다른 결과가 나올 수 있음
- 해에 근접할 수록 $$\|\nabla$| \to 0 $$ : 수렴속도 느려짐
- global minimum이 아닌 local minimum에 빠질 수 있음

• input : gradient, init, lr, eps
• output : var
• Gradient Descent Pseudo Code

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

• Gradient Descent Pseudo Code in Vector

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

• Gradient Descent Python Code in Vector

import numpy as np

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(f"function: {fun(val)[1]}, cal_count: {cnt}, min_point: ({val}, {fun(val)[0]}))

Reference

https://www.analyticsvidhya.com/blog/2020/10/how-does-the-gradient-descent-algorithm-work-in-machine-learning/
https://ruder.io/optimizing-gradient-descent/https://ruder.io/optimizing-gradient-descent/
https://ko.wikipedia.org/wiki/%EA%B2%BD%EC%82%AC_%ED%95%98%EA%B0%95%EB%B2%95