Gradient descent 2. (심화)

 

 

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

 

 

오늘부턴 다음과 같은 관점에 대해 이야기해볼 것이다.

 

"gradient descent"를 continuous-time approximation을 하는 것.

즉, continuous-time (gradient) flow의 dynamical system으로 보는 것.

사실 우리가 discrete-time algorithm인 Gradient descent를 continuous-time으로 바꿔서 보는 것도 결국 이를 위함이다..

 

gradient flow란 vector field의 일종인 gradient field에서 하나의 점이 시간의 흐름에 따라 어떻게 연속적으로 이동하는지를 나타낸다. 그때 이동하는 방향은 함수 $f$의 gradient 방향이다.

이 과정을 수식으로 표현하는 것에 있어서 필연적으로 ODE가 등장한다. 

 

자, 다음과 같은 과정을 생각해보자.

 

$x_{n+1} = x_n - \eta_n \nabla f(x_n)$

이를 다음과 같이 보자.

$x_{n+1} - x_n = - \eta_n \nabla f(x_n)$

 

우리는 이 알고리즘의 파라미터 수열을 즉, $\{ x_n \}_{n \in \mathbb{N}}$, 이제 continuous-time으로 approximation을 할 것이다. ($\{ X(t)\}_{t \in \mathbb{R}^+}$) 

여기서 '$\eta$'는 step-size로서 양의 실수 수열이다. 즉, $\{ \eta_n \}_{n \in \mathbb{N}}$ 는 항상 양의 실수이다.

일반적으론, step-size는 내가 현재 지점에서 얼마만큼 이동할지, 즉 보폭의 크기를 결정하는 값으로 볼 수 있다.

만약 이 step size를 $0$에 가깝게 보내버리면 어떻게 될까?

위 등식의 LHS는 "n번째 time step에서 n+1번째 time step으로 바뀔 때, $x$가 얼마만큼 이동했는가?" 를 나타낸다. 

이 discrete-time을 우리는 continuous-time으로 바꾸고 싶다. 즉, $n$과 $n+1$ 사이의 빈 틈을 채우고 싶고, $x_n$과 $x_{n+1}$ 사이의 변화의 경로를 채워넣고 싶다. (이를 interpolation의 과정으로 볼 수 있다.)

 

그러면 어떻게 하면 될까? $\eta$를 $0$으로 보내면 된다. 왜? 이것이 무슨 의미일까?

이는 $n$과 $n+1$ 사이의 시간 간격을 $\eta$로 보겠다는 것이다.

그러면 $x_n$이 $X(t)$에 대응된다면, $x_{n+1}$은 $X(t+\eta)$에 대응되는 것이다.

그러면 $t$는 $n \eta $에 대응된다. 

$x_0$ ($X(0)$) 와 $x_1$의 시간 간격이 $\eta$이고, $x_1$과 $x_2$의 시간 간격이 $\eta$이고, 이러한 식으로 계속 확장해나가면 $x_{n}$는 $X(n \eta) = X(t)$에 대응된다.

 

자, 그러면 $\eta$를 0에 가깝게 놓는다는 것은,  $t \in \mathbb{R}^{+}$인 연속적인 시간 축에서 $x_n$과 $x_{n+1}$사이의 간격을 아주 작게 잡겠다는 것이고, 이는 discrete-time을 continuous-time으로 interpolation을 해나가는 과정에 대응된다.

 

다시 위의 식으로 돌아가보자.

 

$x_{n+1} - x_n = - \eta_n \nabla f(x_n)$

양변을 $\eta$로 나누면,

 

$ \frac{x_{n+1} - x_n}{\eta} = - \nabla f(x_n)$

여기서 $\eta \rightarrow 0$으로 극한을 취해주면,

 

$\frac{dX(t)}{dt} = - \nabla f(X(t))$이다. 이 방정식은 아무 시점 $t$에서 점의 이동 속도 (위치의 변화량)은 negative gradient라는 것을 나타낸다. 

 

이 식이 gradient descent를 continuous-time으로 approximation을 한 것이다.

여기서 ODE의 형태를 취해주면 다음과 같다.

 

$\dot{X(t)} = - \nabla f(X(t))$ 이것이 ODE의 형태이다.

그리고 이 방정식은 $f$의 gradient flow를 나타내는 식이며, 함수의 최솟값을 향하는 continuous-time의 trajectory를 나타내준다.

 

더 나아가서 이 방정식의 해를 구한다는 것은 $X(0) = x_0$에서 시작하여, 연속적으로 점이 이동해나가는 과정을 보여주며, 함수 $f$의 minimum을 향해 어떻게 이동하는지, 연속적인 시간 속에서 보여준다.

 

오늘의 글에서 우리는 gradient descent와 gradient flow를 연결지어 해석했다. 

물론, gradient flow의 운동을 나타내는 위 ODE의 해를 구한다고 하여, 그것을 바로 gradient descent에 연결지을 수는 없다. 다시, discretization 하는 과정을 거쳐야 하는데 이때도 역시 step-size가 충분히 작다 (0으로 간다) 등의 조건이 필요하다. 이에 대해서는 추후 알아보자.