Deep dive into Optimization: Second-order method - Updated

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

 

이번 포스팅 글부터는 2차 미분을 이용한 optimization algorithm에 대한 설명을 진행하고자 한다.

지난 시간까지는 (Stochastic) gradient descent로 1차 미분인 gradient를 활용한 파라미터 업데이트 방법들에 대해

살펴보았고, 오늘부턴 2차 미분을 활용한 딥러닝 학습 알고리즘에 대해 살펴보고자 한다.

 

 

* Hessian matrix (헤시안 행렬)

 

우선, 다변수 함수 $f : \mathbb{R}^n \rightarrow \mathbb{R}$ 의 2차 미분이 어떻게 나오는지 알아보도록 하자.

다변수 함수를 한 번 미분한 gradient는 vector이다. 

다변수 함수를 두 번 연속으로 미분한 것은 Hessian이라 하며, 이는 Matrix이다.

Hessian matrix

 

Hessian matrix는 위에서 볼 수 있듯이 기본적으로 $n \times n$ Symmetric matrix이다. 
(엄밀하게는 각각의 편미분들이 모두 연속이어야 하는데 대칭행렬인데 우리는 이것이 위배되는 상황은 무시할 것이다.)

 

그리고 각각의 성분들은 second-order partial derivative (편미분) 로 이뤄져 있음을 볼 수 있다.

어떤 함수를 1번 미분했을 때, 우리가 알 수 있는 정보는 그 지점에서의 '기울기' 즉, 순간변화율이다.

그리고 이 함수를 2번 미분했을 때, 알 수 있는 것은 곡률 (Curvature) 정보이다.

Curvature란 결국 기울기의 기울기, 즉, 기울기가 얼마나 빠르게 변화하는가를 나타내는 것이다. 

Curvature가 크면, 기울기가 빠르게 변화하므로 함숫값의 증가 속도 (또는 감소 속도)가 점점 증가할 것이고,

Curvature가 작으면, 기울기가 느리게 변화하므로 함숫값의 증가 속도 (또는 감소 속도)가 점점 감소할 것이다.

이를 그림으로 보면 다음과 같다.

 

위 그림에서 왼쪽 곡선은 curvature가 크고, 오른쪽 그림은 curvature가 작다. (sharp와 flat으로 볼 수도 있다.)

결국, Second-order optimizer를 사용한다 함은, 곡률이라는 Loss function의 (local) geometry property를 업데이트 방향에 반영한다고 볼 수 있다.

 

여기서 잠시 기본적인 개념들을 정리하고 넘어가자.
먼저, 지난 번 convex function의 정의부분에서 이야기했듯이, convex function $f$가 두 번 연속으로 미분이 가능하면, 그 Hessian matrix는 Positive (semi)-definite이다. 이는 헤시안 행렬의 모든 고윳값이 항상 0 이상인 것과 동치이다. 

점 $x \in \mathbb{R}^n$에서의 Hessian matrix가  Positive definite이면, 그 지점은 local minima이다. (또는 global minima)

반대로, Hessian matrix가 Negative definite이면, 그 지점은 local maxima이다. (또는 global maxima)

마지막으로 Hessian matrix가 Positive definite, Negative definite도 아니면, 그 지점은 saddle point 이다.

이러한 평가 방식을 second-derivative test라고 한다.

 

Hessian matrix가 Positive definite인지 아닌지의 여부는 그 행렬의 Eigenvalue를 보면 알 수 있는데 만약 Eigenvalue가 모두 양수이면 Positive definite, 모두 음수이면 Negative definite, 양수와 음수가 섞여 있으면 둘 다 아니게 된다.

즉,  Loss function에서 특정한 지점에서 Hessian의 eigenvalue를 계산하면 우리는 그 지점이 local minima인지 아닌지 판단할 수 있다. 

일반적으로 Neural network의 손실함수처럼 'non-convex'한 함수는 무수히 많은 local minima, global minima, saddle point를 가지고 있다. 이 경우에 $\nabla f(x) = 0$인 지점을 우리는 $f$의 critical point (or stationary point)라고 부른다.

이는 local minima, saddle point, global minima 를 모두 포함하는 용어이다.

그러면 그 지점에서 local minima인지 saddle point인지를 판단하기 위해서는 Hessian을 봐야 한다. 

하지만, 실제로는 그러한 판단법을 사용하지 않고 그냥 local minima에 잘 수렴했을 것이라고 믿고 간다. 

 

그렇다면 Second-order optimizer를 일반적으로 많이 쓰지 않는 이유는 무엇일까?

가장 큰 이유는 '계산량' (Computational cost)과 메모리 문제이다. Second-order optimizer를 사용하기 위해서는 매 step마다 2차 미분 행렬을 계산하고, 역행렬을 구한 다음에 그것을 메모리에 저장해야 하고 파라미터 업데이트를 진행하는 과정을 반복해야 하는데, 이는 파라미터의 개수가 많은 현재의 딥러닝에서는 상당한 계산량과 상당한 메모리 비용을 불러일으킨다.
다음은 Non-convex problem에서 Hessian을 사용할 경우 saddle point problem이 발생할 수 있다.

non-convex에서는 고윳값이 양수와 음수가 섞여 있고, 이는 결국 한 축으로는 함숫값이 증가하고, 다른 축으로는 함숫값이 감소하는 방향으로 업데이트가 진행될 수 있다.
(이에 대해서는 Newton's method에서 좀 더 이야기하겠다.)

그리고 First-order optimizer가 어떻게든 curvature의 정보를 조금이라도 활용하기 위해서 많은 발전을 거듭해왔기 때문에 First-order optimizer로도 충분히 좋은 성능을 내고 있어서 굳이 이를 사용할 필요를 느끼지 못하는 것이다.

 

하지만, 그럼에도 불구하고, Second-order optimizer의 장점은 무시할 수 없고 현재까지도 계속해서 연구가 진행되고 있다.

Second-order optimizer에서 우리가 사용하는 2차 미분 행렬은 대표적으로 Hessian matrix를 사용하는 Newton's method, Fisher information matrix를 사용하는 Natural gradient descent가 있는데 다음 글에서는 Hessian matrix를 사용하는 Newton's method를 살펴보고자 한다.