Gradient descent 3. (심화)

 

 

모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다.

 

지난 번 글에서 우리는 gradient descent를 continuous-time approximation algorithm으로 바라보았다.

그리고 다음과 같은 형태의 미분방정식을 보이면서 글을 마무리했다.

 

$\dot{X}(t) = - \nabla f(X(t))$

 

여기서 시간을 나타내는 $t$는 양의 실수이다. 즉, $t \in \mathbb{R}_{+}$이다.

자 그러면 위 식이 나타내는 의미는 무엇일까?

 

우선, 위 방정식은 기본적으로 (continuous) flow를 나타낸다.

좌변은 시간에 대한 $X(t)$의 미분을 나타내므로 속도를 나타낸다.

속도는 기본적으로 방향과 크기를 갖고 있는 벡터이고, 위 식에서는 어떤 방향으로 얼마만큼의 크기로 시스템의 상태가 변화하는지를 나타내는 식이다.

우변은 그 속도가 (negative) gradient임을 나타내는 것이다. negative gradient는 가장 가파른 하강 방향을 나타낸다.
결국, 위 식은 함수 $f$를 최소화해나가면서 시스템의 '계' (the state of the system, $X(t)$)가 Negative gradient 방향으로 변화해나감을 나타내는 방정식이다. 그러면 $f$가 가장 낮은 값을 갖는 그러한 (안정적인) 상태로 수렴해나갈 것이다.

 

수학에서 우리는 위와 같은 방정식을 '(first-order homogeneous) Ordinary differential equation'이라고 부른다.

 

우선, differential equation은 말 그대로 방정식에 Derivative term이 포함되어져 있는 방정식이다.

그리고 우리는 지금 시간 $t$에 대한 미분을 보고 있고, 여기서 $t$는 양의 실수이기 때문에 위 방정식은 'ordinary' 방정식이다. 만약 Multi-variable 에 대한 derivative term이 방정식에 들어간다면 , Partial derivative term이 포함되어질 것이고, 우리는 이를 Partial differential equation이라고 부른다.

그리고 위 식에서는 first-order term만 포함되어져 있으므로 first-order ODE이다.

 

마지막으로 Homogeneous는 무엇을 의미할까?

이는 $f(x)$라는 potential function이 time variable $t$에 의존하는 함수가 아니기 때문에 이 방정식은 'homogeneous in time'이다. 이 말은 결국 위 시스템을 지배하는 어떤 rule이 시간에 따라 변화하지 않음을 나타낸다.
(즉, 시스템 자체는 시간에 따라 변화하더라도 그 변화 안에는 시간이 흘러도 불변하는 규칙 / 질서가 존재함을 의미한다.)

 

우리는 방정식이 주어져 있으면 이 방정식의 해를 구해야 한다. 

즉, 구체적으로 '등호관계'가 성립하게 하는 함수 $X(t)$를 찾아야 한다.

우선, 미분방정식은 시간에 따라 변화하는 어떤 system의 변화 방식을 수학적으로 모델링하는 것이다.

즉 미분방정식을 푼다, 즉 다른 말로 해를 구한다는 행위의 의미는 방정식의 등호관계를 만족시키는 함수 (또는 함수의 집합)를 찾는 것을 의미하고 그 함수가 시간에 따라 어떻게 변화하는지 그 변화율을 우리는 알 수 있기 때문에

결국 우리가 원래 보고자 했던 (dynamical) system을 알게 되는 것이나 다름없다.

 

그런데 여기서 문제점은 미분방정식의 '일반해' (general solution) 는 찾을 수 있는 경우가 매우 드물다는 것이다.

이들은 일반적으로 무수히 많은 해를 가질 수 있고, 결국 우리가 특수한 해 (Particular solution) 를 결정짓기 위해서는 추가적인 조건이 더 있어야만 한다는 점을 시사한다.

그 조건이 바로 '초기조건' (initial condition) 이다.

ODE 자체는 많은 해의 쌍들을 가지고 있고, 이 해 중 구체적으로 하나를 결정하기 위해서는 방정식 뿐만이 아니라 초기 조건도 우리에게 주어져야 한다. 여기서 초기조건이라 함은 결국 $X(0)$일 때 어떤 함수 (또는 어떤 값)이냐 일 것이다.

 

그러면 초기조건이 주어지면 우리는 어떤 미분방정식의 해이든 다 구할 수 있을까?

아쉽게도 그렇지 못한 경우가 훨씬 많다.

극소수의 드문 상황을 제시하고는 우리는 정확한 해 (exact solution)를 구할 수 없는 경우가 훨씬 더 많이 있다.

이러한 경우에 그럼 우리는 어떻게 해야 할까?

어떤 수치 연산의 알고리즘을 활용해 최소한의 오차를 갖는 최선의 해 (approximate solution)를 찾아내거나 실제로 해를 찾아내지 못하더라도 Solution들의 dynamical behavior를 알 수 있는 방법을 활용해야 할 것이다.

 

후자의 방법부터 살펴보자. (수학에서 이를 'Qualitative theory of differential equations' 이라고 한다.)

Solution의 'dynamical behavior'를 보겠다는 것은 주로 local behavior, long-term behavior를 보겠다는 것이다.

여기서 등장하는 개념이 'equilibrium solutions'이다.

 

Equilibrium solution은 안정된 상태 (state) $X^{\star}$, 즉 더 이상 시스템의 변화가 일어나지 않는, $\dot{X}(t) = 0$인 상태를 의미한다. 우리가 관심을 갖는 ODE에서 이는 $- \nabla f(X(t))  = 0$인 $X^{\star}$를 나타낸다.

이 해의 'stability'는 다음을 의미한다.

 

약간의 perturbation을 가했을 때, 동일한 상태가 반환된다면, 그 지점은 'stable'하다.

즉, 엄밀하게 이는 임의의 $\epsilon > 0$에 대하여 $|X(0) - X^{\star}| < \delta$이면 $|X(t) - X^{\star}| < \epsilon$인 $\delta$가 존재할 때 stable하다고 정의한다.

이는 위의 ODE에서는 함수 $f$의 local minima에 수렴한 경우이다.

반대로 만약 함수 $f$의 local maxima나 saddle point에 수렴한다면 이때는 'unstable' equilibrium이다.

 

local maximum에서 perturbation을 더하는 경우, 즉 약간의 $X^{\star}$에서 $X^{\star} + \delta$로의 이동은 함수 $f(X)$를 감소시킨다.

이는 $-\nabla f(X)$가 다시 system을 $X^{\star}$에서 멀리 이동하게 하는 결과를 가져온다.

saddle point에서 약간의 $X^{\star}$에서의 이동은, 함수 $f(X)$를 증가시키거나 감소시키는 결과를 가져온다.

이는 $-\nabla f(X)$가 system을 $X^{\star}$에서 멀리 이동하게 하는 결과를 가져온다.

 

그렇기 때문에 local maxima나 saddle point에서의 perturbation은 $X^{\star}$에서 멀리 떨어지게 만들어버리고 이를 우리는 'instability'라고 정의한다.

반대로 local minima에서 perturbation을 더하는 경우 이는 함수 $f(X)$를 증가시키고, 다시 원래의 상태 $X^{\star}$로 돌아오게 만든다.

이를 우리는 'stability of the equilibrium'이라고 정의한다.