Unconstrained optimization, Gradient Descent

[읽기 전에.. ]

1. 용어정리

minimum, minimizer : 최소값, 최소점

2. 선수학습

Taylor series expansion 관련 내용이 종종 나오므로 간단한 개념을 알아야 잘 이해할 수 있다.

3. 관련 포스팅

예전 글에서 gradient descent 에 대해 정리한 적 있다. 그때 글은 gradient descent 를 한번에 이해할 수 있도록 돕기 위해 우리가 한번쯤 접해봤을 법 한 _선형회귀 함수를 fitting 하는 과정_을 gradient descent 를 이용해서 어떻게 하는지를 단적인 예시로 보여주었다면, 이번 글은 조금 더 큰 맥락에서의 설명이 될 것이다.

youngseokim.tistory.com/81?category=911369

Stochastic Gradient descent

---

 

Local minimizer, 지역 최소값 찾기

convex optimization 에서는 지역 최소값이 (local minimum) 전역 최소값 (global minimum) 라는 좋은 성질이 있었지만 non-convex optimization 에서는 그렇지 못하다. 따라서 종종 우리는 local minimum을 찾는 것에 집중한다.

 

Theorem: First order necessary condition

1차 미분 가능하며 미분해도 연속인 함수 f 가 x 에서 지역 최소값을 가지면 함수의 미분값은 0이다.

반대로 어떤 x 에서 함수의 미분 값이 0이라는 사실을 알면 (이런 지점을 stationary point 라 한다.) x 가 지역 최소값이라는 사실을 보장할 수 있을까? (위의 정리의 역에 해당한다.) 답은 No 이다. (함수가 convex 라는 조건이 있었을때는 이 답이 YES 였다는 사실을 잊지 말자.) 가장 대표적인 예시가 saddle point 로 알려진 말의 안장같은 모양의 hyperplane 상의 빨간 점이다. 모든 방향으로의 미분값이 0이지만 지역최소값은 아님을 눈으로 확인할 수 있다.

이미지 출처 위키피디아 https://en.wikipedia.org/wiki/Saddle_point

하지만 적어도 어떤 함수에서 미분값이 0이 아니면 x는 지역 최소값이 확실히 아니라는 사실은 알 수 있다. (위의 정리에 대우에 해당한다.)

 

Theorem: Second order necessary condition

만일 함수가 두번 미분해도 연속이며 x가 f의 지역최소값이라면, f의 Hessian matrix는 Positive semi-definite 이다.

이미지 출처 http://mlwiki.org/index.php/Positive-Definite_Matrices

어떤 함수의 헤시안 매트릭스가 definite, semidefinite, indefinite 중 무엇인지에 대한 정보는 그 함수가 기하학적으로 어떤 hyperplane 에 놓여있는지에 대한 정보를 준다. 함수가 semidefinite 이 아니면 (즉 indefinite)이면 지역 최소값을 가질 수 없다는 사실을 쉽게 눈으로 확인할 수 있다.

소결

앞선 두 정리를 종합하면 어떤 함수 f의 지역 최소값 x*는 항상 다음 조건을 만족해야한다.

따라서 어떤 함수의 지역 최소값을 찾는 알고리즘을 간단하게 구상해보면 첫번째로 미분값이 0인 지점을 모두 찾아서 헤시안 매트릭스가 PSD인지까지 확인하는 방식을 생각해볼 수 있다. 하지만 이렇게 찾은 점이 반드시 지역 최소값이라는 보장을 할 수 없음을 주의해야한다. 위의 수식을 만족하는 함수는 최대값도 있고 saddle point 도 있다. 항상 아래로 하강하는 값을 찾아 나가는 알고리즘을 통해 최대값도 있고 saddle point를 피하기를 꾀해볼 수 있다.

 

Gradient Descent Algorithm 경사 하강법 알고리즘

가장 간단한 형태의 Gradient Descent 알고리즘을 살펴보자. 

 

Step 1

초기값 정하기. 시작점을 찾는다. step size를 의미하는 alpha 값을 정한다. 수렴 조건 엡실론 값을 정한다. k=0 으로 설정한다.  

수렴조건

Step 2

현재 위치에서의 gradient 를 찾는다. 만약 수렴 조건을 만족하면 현재 지점을 반환한다.

만족하지 않으면, 현재 위치로부터 negative gradient (하강 경사) 에 step size alpha 만큼 이동하고 k에 1을 더한다.

특정 조건을 만족하는 모든 시작 지점에 대해 유한한 iteration 이후에 알고리즘이 stationary point (gradient 가 0인 지점)로 수렴하는 것이 보장된다. 이러한 성질을 두고 globally convergent 알고리즘이라 말한다. (global optimal solution으로 수렴한다는 의미가 아니니 주의하자. )