[References]
1. 이상구 with 이재화, [빅북] 인공지능을 위한 기초수학(Basic Mathematics for Artificial Intelligence), 교보문고 POD, 2019.
http://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 )}$
