Deep dive into Optimization : Second-order method (4) - Updated

 

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

 

 

오늘과 다음 글 두 번에 걸쳐 Natural gradient descent에 대해 이야기하고자 한다.

Natural gradient descent는 Fisher information matrix를 활용한 optimization method로서, Fisher information matrix에 대해서는 이전 글을 참고하기 바란다.

https://kyteris0624.tistory.com/39

Deep-dive into Optimization : Second-order method (3)

 

이 글과 다음 글은 아래 2개의 논문을 참조하여 작성되었다.

* Razvan Pascanu, Yoshua Bengio, "Revisiting natural gradient for deep networks", arXIv 2014

* James Martens, "New insights and perspectives on the Natural Gradient Method", JMLR 2020

 

--- Riemannian geometry, Information geometry에 대한 background를 상정하지 않고 본 글을 작성하였다.

Riemannian geometry에 대한 background가 있다면 Natural gradient algorithm은 Fisher information metric이 정의된 Riemannian manifold 상에서의 gradient descent 알고리즘으로 볼 수 있다.

 

우선, Natural gradient descent는 다음과 같은 'natural gradient'를 사용하여 Neural networks의 parameter를 업데이트한다.

 

Natural gradient descent

 

여기서 $w_{t+1}$은 $t+1$ 번째 iteration을 의미하며, $\eta_t$는 step-size, $F^{-1}$은 $w_t$에서의 Fisher information matrix의 inverse, $\nabla \mathcal{L}(w_t)$는 $w_t$에서의 Loss function의 gradient를 나타낸다.

 

앞서 Gradient descent에서도 이야기하였듯이, Negative gradient $- \nabla \mathcal{L}(w_t)$는 "국소적으로" 가장 가파른 방향으로 Loss function을 감소하게 한다. 

이때, 파라미터 공간을 Euclidean geometry로 정의하면, 파라미터 사이의 거리는 Euclidean distance로 표현된다.

그리고 이는 inner product를 dot product로 정의한 것을 바탕으로 한다.

 

이 지점에서 Natural gradient descent의 Motivation이 등장한다.

 

Neural network는 (probability) distribution을 모델링한 것으로 볼 수 있고, 때문에 $w_t$에서의 distribution과 $w_t + \epsilon$과의 distribution의 차이를 단순히 $L2-norm$으로 측정하면 거리의 왜곡이 발생할 수 있다.

Natural gradient descent는 이 parameter space에서 파라미터들 사이의 거리를 $L2-norm$이 아닌 확률분포들의 공간, "Statistical manifold"의 관점에서 측정해야 한다는 점에서 Motivation이 있다.

 

구체적으로 Neural network의 파라미터인 $w$로 parameterized되는 distribution을 다음과 같이 표현해보자.

$P_{x, y}(w)$

 

그러면 $w_t$에서 $w_{t+1}$로 파라미터가 업데이트될때, 이동할 때 어떠한 방향이 가장 가파른 감소 방향인지를 측정하기 위해서는 확률 분포 사이의 거리 / 차이를 측정하는 지표가 필요하고 이때 등장하는 것이 KL-divergence이다.

 

KL-divergence의 정의는 다음과 같다.

KL-divergence

 

이 때 $P, Q$는 distribution을 의미한다.

 

그렇다면 $P_{x, y}(w)$와 $P_{x, y}(w + \epsilon)$ 사이의 KL-divergence는 다음과 같이 Fisher information matirx를 이용해 표현할 수 있다. ($\epsilon$이 충분히 작을 때)

 

위 성질은 Taylor expansion을 사용해 KL-divergence에 대입하면 쉽게 확인 가능하다.

(이전 글에서도 언급했으므로 넘어가자)

 

즉, $F$, Fisher information matrix는 KL-divergence의 'local quadratic approximation'으로 표현되며, 파라미터가 $w$에서 $w + \epsilon$으로 변환된 분포 사이의 차이/거리를 측정할 수 있는 지표가 된다.

 

그렇다면, 우리의 Loss function의 가장 가파른 감소 방향을 정의할 때도 다음과 같이 유도할 수 있다.

 

복잡해보이지만 자세하게 살펴보면 쉽게 이해될 수 있다.

우리는 Loss function $\mathcal{L}(w + \epsilon)$을 최소화하는 $\epsilon$을 찾고 싶다.

$\epsilon$은 두 distribution ($P(w + \epsilon)$, $P(w)$) 사이의 거리 (KL-divergence)를 나타내며, 그 값은 $d^2$으로 constraint돼 있는데, 이때 $d$는 0으로 가는 아주 작은 값이다. 이는 우리가 'Taylor approximation'을 사용하기 때문에 $\epsilon$이 한없이 커지면, 그 근사의 오차가 커지기 때문에 $\epsilon$을 작게 유지하기 위한 장치라고 이해할 수 있다.

 

위 수식에서의 $\epsilon$이 바로 Natural gradient인 $- F^{-1}\nabla \mathcal{L}(w)$ (실수배 항은 무시함)가 되는 것이다.

즉, Negative natural gradient는 parameter space를 distribution space로 바라보았을 때 (Statistical manifold 라고 한다), distance를 KL-divergence를 활용해 측정할 수 있고, 이때  조그마한 local neighborhood에서 가장 낮은 함숫값, (구체적으로는 "local quadratic approximation") 그곳의 방향을 가리키는 vector이다. 

 

Hessian matrix를 사용하는 Newton's method는 parameter space를 Euclidean 관점에서 바라봤을 때 distance를 L2 distance로 측정하였고, 그 때 조그마한 local neighborhood에서 가장 낮은 함숫값 (구체적으로는 "local quadratic approximation"), 그곳의 방향을 가리키는 vector로 $H^{-1} \nabla \mathcal{L}(w)$가 유도된다. 

(Second-order approximation을 사용했었다 / 이전 글 참조)

https://kyteris0624.tistory.com/36

Deep dive into Optimization : Second-order method (2)

 

 

그렇다면 이론적으로 좋은 background를 가지고 있는 이 알고리즘을 practical한 측면에서 잘 쓰지 않는 이유는 무엇일까?

여태까지 이 시리즈의 글을 잘 읽어왔다면 알겠지만 결국 계산 비용 문제 (시간과 메모리) 이다.

파라미터의 개수가 매우 많은 (심지어 training dataset 크기보다 훨씬 큰) overparameterized neural network에서 현재 파라미터인 $w_t$에서 Hessian, Fisher등의 matrix를 연산해서 이를 메모리에 일시적으로 저장하는데는 상당히 큰 비용이 소모된다. 

또한 우리가 파라미터를 update할 때는 이들의 inverse matrix, 즉 $F^{-1}$, $H^{-1}$을 계산하여야 하는데, 'overparameterized' neural network에서는 이들이 Full-rank matrix가 아닌 경우가 많기 때문에 역행렬이 존재하지 않는 경우가 더 많다.

그래서 실제로는 $F$, $F^{-1}$을 정확히 계산하는 것이 아닌 이들을 approximate하여서 근사행렬을 활용하는데, 이 과정에서 원치 않는 bias/error 들이 들어갈 수 있다.

이 문제에 대해서는 현재도 활발하게 연구가 진행되고 있고, 계속해서 적지 않은 논문들이 나오고 있다.

이에 대한 자세한 언급은 '기초/입문'이 이 시리즈의 범위를 넘어서기 때문에 다루지는 않겠다.

 

다만, 관심이 있다면 다음의 논문을 참조할 수 있을 것이다.

"Frederik Kunstner et al. "Limitations of the Empirical Fisher Approximation for Natural gradient descent", Neurips 2019"

가장 유명한 논문 중 하나이다.

 

다음 글에서는 Natural gradient descent에 대한 추가적인 설명과 함께 Second-order method를 마무리하겠다.