논문요약 - Identifying and attacking the saddle point problem in high-dimensional non-convex optimization[14.05]

(Dauphin, Y.N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., Bengio, Y)

사실 이 paper는 거의 동일한 저자분들이 2014년 5월에 내셨던

[2014.05] On the saddle point problem for non-convex optimization

(Razvan Pascanu, Yann N. Dauphin, Surya Ganguli, Yoshua Bengio)

 

 

에서 몇 가지 실험결과가 더 추가되어 나온 업그레이드 된 paper이다.

이 논문을 간단히 요약하자면

1. 우리가 결국 관심있는 딥러닝 문제들은 고차원(차원이 높다는건 hidden layer가 많다는건가??) 문제들이고 따라서 우리는 고차원 문제들에서의 성질들이 궁금하다

2. 기존의 physics, random-matrix관련된 논문들에서 알려진 사실에 의하면 critical point들 중 문제가되는 local-minimum이나 saddle-point들과 관련하여, 차원이 높아지면 결국 문제가 되는건 local-minimum이 아니라 saddle-point이다

3. 따라서 고차원에서 saddle-point들을 피할 수 있는 saddle-free-newton-method라는 세로운 알고리즘을 제안하였고 실험결과상 기존 다른 방법들 보다 좋은 결과를 보였다.

라고 할 수 있겠다.

전체적인 내용을 다시 이야기 해보자면(스토리 텔링 형식으로)

먼저 딥러닝에서는 뉴럴네트워크를 이용하여 input data에 대하여 output data를 가장 잘 표현 할 수 있는 함수를 찾는게 목표인데 layer사이에 weight를 주어서 그 weight를 업데이트 시키는 방식으로 error function을 최소화 시키는 알고리즘을 이용한다(optimization). 이 업데이트는 편미분을 이용하는 backpropagation 방법을 이용하여 하는데 그 방법은 일반적으로 gradient descent 알고리즘을 사용한다. 그래디언트 방향의 반대편으로 조금씩 이동시켜가며 iteration을 돌려 조금씩 error-function을 최소화 하는 방식이다. 이  gradien-descent(이하gd) 알고리즘은 convex-function에 대해서는 이미 수렴성과 여러가지 좋은것들이 보장되어 있다는 사실이 알려져있다.

하지만 문제는 딥러닝에서의 error-function optimization은 보통 non-convex 형태이기 때문에 gd에 대한 수렴성이나 수렴을 한다해도 우리가 원하는 global-minimum으로 수렴을 하는지도 잘 모르거나 수렴속도가 느련 경우도 많다.

따라서 속도나 방향, 수렴성 등을 위해 다양한 시도들과 관련된 paper들이 나오고 있는 추세이다. 여러가지 시도들 중 몇 가지를 요약해 보자면

1. 다음에 정리할 paper가 이 내용에 속하는데, 최근 dynamical system을 이용하여 optimization을 해결하려는 시도가 있다. 간단히 말하자면 매 번 돌아가는 iteration을 무한히 작은 시간의 연속으로 보아서 기존에 우리가 알고있는 differential-equation(미분방정식)에서의 이론들을 가져와서 해결하려는 것이다. dynamical-system과 control-theory와 관련된 이론들을 가져와서 이를 바탕으로 하는 알고리즘을 이용하니 딥러닝에서의 optimization에 더 좋은 성능을 가져왔다는 것이다.

2. topology와 geometry의 성질을 이용하여 error function이나 그 surface를 분류하려는 시도도 있다. 자세히는 잘 몰라 생략...

3. 이 paper가 여기에 속하는데  기존의 critical point들을 분석하고 어떻게 하면 올바른 방향으로 수렴을 보장하고 global-minimum이나 saddle-point에 묶여있지 않을 수 있나에 대하여 기존의 gd를 수정하여 새로운 알고리즘을 제안하는 시도가 있다. 자주 들어봤고 실제로 내장함수로 이미 자주 쓰이고 있는 Stochastic Gradient Descent, Nesterov accelerated gradient, Adagrad, Adadelta, RMSprop, Adam등도 그 예시이다. critical point들을 분석한 최신 논문들 중에는 몇 가지를 대강 소개하면

•[2014.06]Identifying and attacking the saddle point problem in high-dimensional non-convex

•[2015.01]The Loss Surfaces of Multilayer Networks

•[2016.12]Deep Learning without Poor Local Minima

•[2017.06]Are Saddles Good Enough for Deep Learning?

•[2017.10]First-order Methods Almost Always Avoid Saddle Points

1번째 paper는 뒤에서 소개할 paper

2번째 논문은 물리에서 spin glass관련된 성질들을 이용하여 hidden layer가 많아질수록 local-minima들이 global-minimum근처 적당한 밴드안에 모여서 존재한다는 사실을 보임.

3번째 논문은 local-minima들 중에 별로 안좋은 poor-local-minima들을 정의하고 deep leaning 에서 optimization을 할 때에 nonconvex라는 문제점은 있지만 poor-local-minima로 수렴하지는 않아 그렇게 어렵지는 않다는 사실을 보임.

4번째 논문은 보통의 논문들은 degeneracy인 경우를 무시하는데 실제로는 dnn은 사실 높은 degeneracy를 가지는 saddle-point에 수렴하게 된다는 사실을 보임.

그렇담 얘기하려는 논문은 어떤 내용인지

 

기존의 물리학계의 논문

Bray, A. J. and Dean, D. S. (2007). Statistics of critical points of gaussian fields on large-dimensional

spaces. Physics Review Letter,

에서

α := fraction of negative eigenvalues of the Hessian at the critical point

ε := error attained at the critical point

에 대하여 높은 dim에 대해서는 이 알파와 입실론이 비례한다는 사실을 보였다

우리의 논문에서는 이 사실을 neural-network에 실제로 적용하여 이 사실이 맞는지를 보였다. 이 사실이 말해주는건 알파가 작다는 의미는 eigenvalue가 거의 대부분 양수라는 것이고 즉 local-minima인 critical-point들 이라는 의미이다. 즉 local-minima(알파값이 작은 점)들은 에러가 작다는 의미이며 결국 높은 dim에서는 local-minima들이 문제가 아니라 saddle-point들을 조심해야 한다는 의미이다.

이에 맞추어 논문에서는 기존의 trust region method를 일반화하여 saddle-point들을 피할 수 있도록 하는 알고리즘=saddle free newton method을 제안하였고 이 방법이 다른 방법보다 이터레이션 대비 더 먼저 error를 줄이는 결과를 보여주었다.