1. 경사 하강법의 정의
경사 하강법(傾斜下降法, Gradient descent)은 1차 근삿값 발견용 최적화 알고리즘이다. 기본 개념은 함수의 기울기(경사)를 구하고 경사의 반대 방향으로 계속 이동시켜 극값에 이를 때까지 반복시키는 것이다.
-위키백과-
만약 본인이 한 치 앞도 보이지 않는 상황에서 산을 내려가야 하거나, 올라가야 한다면 어떻게 해야할까요?
시각적으로 멀리 있는 산 꼭대기가 보이지 않기 때문에 단순히 근처의 지형을 가지고 판단을 내려야 합니다.
그러므로 현재 위치에서 가장 경사가 높은 곳, 그 곳으로 계속해서 움직이면 '보통' 산의 정상에 도달 할 수 있습니다.이는 경사 상승법이라고 하며, 정 반대의 방법으로 계속해서 가장 낮은 곳으로 이동하는 것이 경사 하강법이라고 할 수 있습니다.
2. 그렇다면 왜 경사 하강법을 사용할까?
일반적으로 인공지능은 손실 함수를 통하여 자신의 파라미터를 검증합니다.
손실 함수는 인공지능의 파라미터를 통하여 나온 예측 값과 실제 값의 차이라고 볼 수 있으며,
특정 파라미터를 통하여 나온 손실 함수 값이 가장 낮은 곳이 바로 최적의 파라미터라고 할 수 있습니다.
그러면 그냥 손실함수를 미분하여 최소, 최대 값을 찾으면 되지 않을까요?
하지만 미분을 이용하지 않고, 경사 하강법을 이용하여 최소의 근삿값을 찾는 이유가 있습니다.
- 실제 우리가 마주치는 함수들은 간단한 함수가 아니라 복잡하고, 비선형적인 함수가 대부분입니다. 따라서 미분을 통하여 그 값을 계산하기 어려운 경우가 많습니다.
- 미분을 구현하는 과정보다 경사 하강법을 구현하여 최솟값을 찾는 것이 실질적으로 더 효율적입니다.
따라서 우리는 함수를 미분하는 대신 경사 하강법을 이용하여 함수의 최소, 최댓값을 찾습니다.
3. 경사 하강법으로 근사값을 찾는 과정
- 만약 현재 위치의 기울기가 음수라면 파라미터를 증가시키면 최솟값을 찾을 수 있습니다.
- 반대로 기울기가 양수라면 파라미터를 감소시키면 최솟값을 찾을 수 있습니다.
따라서 해당 파라미터에서 학습률 * 기울기를 빼면 최솟값이 되는 장소를 찾을 수 있습니다.
수식은 \(w \leftarrow w - \eta * \frac{\partial L}{\partial w}\)와 같습니다.
이때 \(\leftarrow\)는 업데이트가 된다는 뜻입니다.
\(\eta\)는 학습률이고, \(\frac{\partial L}{\partial w}\)는 손실 함수 위에서의 해당 가중치의 기울기입니다.
근데 사실은 정말로 기울기가 가리키는 곳에 최솟값이 있을지, 그쪽이 정말 나아갈 방향인지 보장할 수 없습니다.
하지만 그 방향으로 가야 함수의 값을 줄일 수 있는 것은 확정적이므로, 최솟값이 되는 장소를 찾기 위해서는 기울기 정보를 단서로 나아갈 방향을 찾아야 합니다.
4. 경사 하강법의 문제점
이런 경사 하강법도 몇 가지 문제점을 가지고 있습니다.
대표적으로
- 적절한 학습률(learning rate)
- local minimum
이 있습니다.
통상적으로 학습률과 기울기 정보를 혼합하여 내가 나아갈 방향과 거리를 결정합니다.
따라서 학습률이 높으면 높을수록 더욱더 많이 나아갑니다.
그러므로 학습률이 높으면 한 번에 이동하는 거리가 커지므로 최적값에 빨리 수렴할 수 있다는 장점이 있습니다.
하지만 너무 크게 설정하면 최적값에 수렴하지 못하고 다른 곳으로 발산하는 현상이 나타날 수 있습니다.
정 반대로 학습률이 낮으면 발산하지 않는 대신 최적값에 수렴하는 시간이 오래 걸릴 수 있습니다.
따라서 학습률을 적절히 조정하는 것이 매우 중요합니다
두 번째로 지역 최솟값에 안착해버릴 수 있습니다.
실제로 우리는 전역 최솟값을 찾고 싶지만, 어떤 이유로 인해 지역 최솟값에 빠지는 경우 탈출하지 못하고 거기로 수렴해버릴 수 있습니다.
운이 안 좋다면 local minimum에 빠져 탈출하지 못할 가능성이 있습니다.
5. 해결법
이를 위하여 다양한 경사 하강법들이 나왔습니다.
학습 도중에 학습률을 지속적으로 바꾸는 Adaptive Gradient Descent가 있고,
local minimum에 빠지는 경우를 방지하기 위해 관성력을 추가한 Momentum GD가 있습니다.
다른 다양한 경사 하강법은 추후에 추가하도록 하겠습니다.
감사합니다.
[References]
1. 이상구 with 이재화, [빅북] 인공지능을 위한 기초수학(Basic Mathematics for Artificial Intelligence), 교보문고 POD, 2019.
//matrix.skku.ac.kr/math4ai/
[Key point]
Gradient Descent Algorithm 은 어떤 모델에 대한 비용 (Cost) 을 최소화 시키는 알고리즘으로써,
머신러닝 및 딥러닝 모델에서 사용되는 가중치의 최적해를 구할 때 널리 쓰이는 알고리즘이다.
기본 개념은 함수의 기울기(경사)를 구하여 기울기가 낮은 쪽으로 계속 이동시켜서 극값에
이를 때까지 반복시키는 것이다.
최적화 문제의 수치적인 방법(Numerical Method for Optimization -- Line Search Type)
• 먼저 제약조건이 없는 최적화 (unconstrained optimization) 문제
$\min_{{\bf x} \in \mathbb{R}^n} f({\bf x}) $
를 푸는 수치적인 방법 (numerical method) 에 대하여 살펴보자.
[Fermat의 임계점 정리]에 의해 위 문제의 최적해 (optimal solution) ${\bf x}^*$ 는 다음을 만족한다.
$\nabla f({\bf x}^*) = {\bf 0}$
따라서 2.4절에서 배운 바와 같이 방정식 $\nabla f({\bf x}) = {\bf 0}$ 을 풀어서 나온 해들이 최적해가 되는지
판단하면 된다.
• 그러나, 함수 $f$ 가 비선형인 경우는 방정식을 풀어서 임계점을 구하는 것조차도 쉽지 않다.
이런 경우에는 수치적인 방법으로 임계점을 구한다. 최적화 문제를 푸는 계산 방법은 대개
반복법 (iterative method) 으로, 초기 근사해 ${\bf x}_1$ 으로 부터 시작하여 특정한 반복단계를 거쳐
이전보다 나은 근사해 ${\bf x}_2$, ${\bf x}_3$, ... 를 생성한다. 목표는 $k$번째 근사해 ${\bf x}_k$ 또는 극한값 $({\bf x}_k \rightarrow ) \,{\bf x}^*$
에서 $\nabla f({\bf x}) = {\bf 0}$ 을 만족하도록 하는 것이다.
• $k$번째 반복단계는 보통 다음과 같은 (직선의 벡터방정식) 형식으로 구성된다.
${\bf x}_{k+1} = {\bf x}_k + \alpha_k {\bf d}_k$
여기서 ${\bf d}_k$ 는 탐색방향(search direction), $\alpha_k$ 는 step-size (머신러닝에서는 이를 learning rate)
라 한다. 즉 ${\bf x}_k$ 상에서 ${\bf d}_k$ 방향으로 $\alpha_k$ 만큼 이동하여 ${\bf x}_{k+1}$ 을 생성한다.
• 보통 ${\bf d}_k$ 는 함숫값이 감소하는 방향으로 정한다. 즉 다음을 만족한다.
$D_{{\bf d}_k} f({\bf x}_k ) = \nabla f({\bf x}_k ) \cdot {\bf d}_k = {\bf d}_k ^T \nabla f({\bf x}_k ) <0 $
이러한 ${\bf d}_k$ 는 특히 하강방향 (descent direction) 이라고도 한다. ${\bf d}_k$ 방향을 따라 움직이면, 함수
$f$ 가 감소한다는 보장이 있으므로 step-size $\alpha_k >0$ 는 $f({\bf x}_k ) > f({\bf x}_{k+1} )$ 이 만족되도록 정한다.
• step-size $\alpha_k$ 를 택하는 방법은 대개 다음 두 가지로 나눌 수 있다.
① 반직선 ${\bf x} = {\bf x}_k + \alpha {\bf d}_k$ $(\alpha \ge 0)$ 상에서 함수 $f$ 의 값이 가장 작게 되는 $\alpha_k$ 를 찾는다.
$f({\bf x}_k + \alpha_k {\bf d}_k ) = \min _{\alpha > 0} f({\bf x}_k + \alpha {\bf d}_k )$
이 방법을 exact line search 라 하고, 이때의 $\alpha_k$ 를 optimal step-size 라 한다. 대개는
cost 가 많이 들어서 잘 사용하지 않는다.
② 만일 $\min _{\alpha > 0} f({\bf x}_k + \alpha {\bf d}_k )$ 을 정확하게 풀지는 않지만 "함숫값이 충분히 감소한다"는 것을
보장하는 $\alpha_k$ 를 선택하는 방법이 있다면, exact line search 를 피하여 cost 를 상당히 줄일 수 있다.
이를 inexact line search 라 한다. 즉, 다음 조건을 만족하는 $\alpha_k$ 를 찾는다.
$f({\bf x}_k + \alpha {\bf d}_k ) \le f({\bf x}_k ) + c_1 \alpha {\bf d}_k ^T \nabla f({\bf x}_k )$
${\bf d}_k ^T \nabla f({\bf x}_k + \alpha {\bf d}_k ) \ge c_2 {\bf d}_k ^T \nabla f({\bf x}_k )$
여기서 $0<c_1 < c_2 < 1$ 이다. 이를 그림으로 표현하면 다음과 같다.
따라서 위의 두 부등식을 만족하는 $\alpha_k$ 는 폐구간 $[a, \,b]$ 에서 택하면 된다.
[참고] $\alpha_k$ 가 만족해야 하는 조건은 여러가지가 있으나, 위의 두 부등식이 주로 쓰인다.
이를 Wolfe condition 이라 하고, 그 중 첫번째 부등식을 Armijo condition 이라 한다.
그리고 위의 조건을 만족하는 $\alpha_k$ 를 실제로 찾아내는 알고리즘은 Backtracking line search 등
이 있으나 자세한 내용은 본 웹 페이지 맨 아래의 최적화(Optimization) 관련 도서를 참고하라.
경사하강법 (Gradient Descent Algorithm)
• 경사하강법은 탐색방향을 ${\bf d}_k = -\nabla f({\bf x}_k )$ 로 택하는 경우이다. 앞서 살펴본 바와 같이 음의
그래디언트 $-\nabla f({\bf x}_k )$ 방향이 점 ${\bf x}_k$ 에서 $f$ 가 가장 가파르게 하강하는 방향이므로, 경사하강법
의 아이디어가 쉽게 이해된다. (스키장에서 가장 빠르게 하강하는 길을 찾는 알고리즘의 아이디어
와 일치한다.) 다음은 경사하강법의 알고리즘이다.
[경사하강법]
[단계 1] 초기 근사해 ${\bf x}_1 \in \mathbb{R}^n$ 와 허용오차(tolerance) $0\le \epsilon \ll 1$ 을 준다. $k:=1$ 이라 한다.
[단계 2] ${\bf d}_k = -\nabla f({\bf x}_k )$ 를 계산한다. 만일 $\| {\bf d}_k \| \le \epsilon$ 이면, 알고리즘을 멈춘다.
[단계 3] line search 를 수행하여 적절한 step-size $\alpha_k > 0$ 를 구한다.
[단계 4] ${\bf x}_{k+1} = {\bf x}_k + \alpha_k {\bf d}_k $, $k:=k+1$ 라 두고 [단계 2]로 이동한다.
• 다음은 주어진 함수에 경사하강법을 적용한 예시이다. 허용오차는 $\epsilon = 10^{-8}$ 으로 주었다.
[출처] J. BARZILAI and J. M. BORWEIN, Two-Point Step Size Gradient Methods, IMA J. Numer. Anal. (1988) 8 (1): 141-148.
$\min_{{\bf x} \in \mathbb{R}^4} f({\bf x} )=\frac{1}{2} {\bf x}^T A {\bf x} - {\bf b}^T {\bf x} $, $A=\textrm{diag}(20, 10, 2, 1)$, ${\bf b}=(1, 1, 1, 1)$.
여기서 $\nabla f({\bf x} ) = A{\bf x} - {\bf b}$ 이고, $f({\bf x})$ 는 Hessian $A$ 가 양의 정부호 (positive definite) 인
이차함수이므로 exact line search 를 수행하면, $\alpha_k$ 는 다음과 같이 closed-form 으로 나온다.
$\alpha_k = \frac{\nabla f({\bf x}_k )^T \nabla f({\bf x}_k )}{\nabla f({\bf x}_k )^T A \nabla f({\bf x}_k )}$
Copyright @ 2020 SKKU Matrix Lab. All rights reserved.
Made by Manager: Prof. Sang-Gu Lee and Dr. Jae Hwa Lee
*This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF)
funded by the Ministry of Education (2017R1D1A1B03035865).