Week 4.4. Gradient Method

Logistic function의 Θ를 최적화 하는 과정에서 CLosed form 형태가 나오지 않아 Θ를 Approximation 을 해야하는 과정이 필요하다. 그 중 한 방법인 gradient method 를 알아보자.

 

Taylor Expansion

 

위의 식을 ploating 해보면 빨간색은 원래 식 e^x이고 파란색이 n=2 , n=4일때의 ploating 이다. n이 무한대로 갈수록 원식에 가까워 진다는 것을 알수 있다. 

 

그러면 Tayler expansion 을 통해 Graident Method 알고리즘을 정의해 보자.

 

 

x를 이동시키는데 방향과 얼마만큼의 속력으로 이동하는지 알아야하는데 이것을 알아내는것이 gradient method 의 핵심이다. 여기서 방향을 알아내는것이 중요하다. 속력은 optimization 하는 사람이 제시하면 되고 ( 즉 내가 결정하면된다.) 방향은 gradient method가 제시해준다. 

 

위의 식에서 뒤(빨각색 네모 박스부분)의 무한대의 Term을 다 Summation 한값을 특정 constant 를 곱한것으로 제약시켜 무시 시킬수 있다. 이것을 Big-Oh Notation 이라 한다. 

 

Tayler expansion 은 특정 지점에서의 derivative를 알수 있어야한다. 여기서 특정한 지점을 a라 한다.

x=x1 + h u 인데 u의 방향으로 h의 속력으로 진행해간다는 의미이다.

여기서 u를 어떻게 잘정해야 할지가 중요하다. 위에서 x와 a를 정했기 때문에 이것을 Tayler expansion 에 대입해 보자.

 

h^2O(1) 의 항을 없애  버릴수 있다. 어떻게 가능할까? h를 매우작게 만들어 h^2O(1)를 무시해버리게 한다. 

즉 h의 진행하는 속도를 잘 조절해서 위의 2번째 식이 성립하도록 해야한다. (h^2O(1) 의 항을 없앨수 있도록..)

 

이동한값(f(x1 + hu)은 작고 기존의 값(f(x1)은 클때가 u값이 가장 optimizaion 된 경우 이다. 즉 위의식은 f 를 점점 줄여나가고자 할때 위의 식을 사용하게 된다. ( Gradient Descent )

즉 argmin 이 되기 위해서는 반대방향으로 이동시켜야 하고 , 내적의 경우 α가 π 일때가 최소값이 나온다.

즉 위의 식에 (-)를 붙여야 한다. 

 

우리가 최종적으로 구하는것은 Θ의 최대값이고 이것을 알기 위해서는 위에서 소개한 Gradient descent 가 아닌 Gradient Ascent를 이용해야한다.  Gradient Ascent 를 구하는것은 Gradient descent를 구하는 방법과 개념은 다 똑같고 아래의 식에서 제일 마지막의 마이너스 부호 대신 플러스 부호를 사용하면 된다.  ,