NumericalComputation for ML

 

 

#Underflow/Overflow

#Poor Conditioning

#Gradient Based Optimization

#Jacobian and Hessian Matrix

 

@2017.01

 

1. Underflow / Overflow

• Underflow : 0에 가까운 매우 작은 숫자가 0으로 반올림되어 취급
• Overflow : 매우 큰 숫자가 무한으로 취급.
• ex ) softmax - Underflow 또는 Overflow로 부터 반드시 안정화 필요
   

  

   
• 모든 x(i)가 상수 c와 같다고 가정했을 때, output = 1/n으로 동일
• exp 함수 그래프에 따라 x(i) 가 매우 클 때 Overflow, 매우 작을 때 Underflow 발생
• 해결 : softmax(z) wherez=x − max(i)x(i)
  exp의 최대 인수가 1로 제한 -> 오버플로우 방지
  분모의 항은 적어도 1의 값을 가짐 -> 언더플로우 방지
• 분자 항에서의 Underflow 발생 가능성
• 해결 : log softmax. 분자안의 항은 0이 될 수 없음

  

2. Poor Conditioning

• Conditioning : 입력 값의 작은 변화에 대하여 변화율을 나타낸다.
• 컴퓨터 계산의 반올림과 같은 작은 연산도 영향을 미칠 수 있다.
• f(x) = A^-1x, A = N*N Matrix 일 때, conditioning number은

  

• 벡터의 가장 큰 고유값과 가장 작은 고유값의 비율로 나타남.
• 값이 클 수록 변화에 민감하고, 작을수록 변화에 둔감하다.

3. Gradient Based Optimization

Gradient 기반 최적화 기법. 목적함수 f(x)를 최소화 또는 최대화. 최대화의 경우 -f(x)를 최소화한다.

 

최소화 표현 : x^* = arg min f(x)

• f(x) 의 미분 값 : f(x) 의 기울기 제공 --> 출력의 변화에 대한 입력 스케일링 방법 제공
• f(x)가 이웃 점들의 값 보다 작을 때 : local minimum
• f(x)가 이웃 점들의 값 보다 클 때 : local maximun
• f(x)가 한 쪽 보다는 작고 한 쪽 보다는 클 때 : Saddle point

  

• global minimum : 절대값의 크기가 가장 큰 local minimum
• directional derivative : 방향성 미분(벡터 연산)

기본으로 알아두어야 할 식

목적함수 f(x)의 단위벡터 u에 의존하는 f(x+au)에 대하여 목적함수를 최소화 할 때 u와 f(x)의 내적에 의하여 다음과 같은 식을 최소화 시킨다.

 

( u와 x에 대한 f(x)의 기울기의 곱)

(theta는 두 벡터사이 각도를 뜻한다)

u 에 대하여 minimize를 진행하므로 단위벡터 연산, 상수항을 정리하면 u에 대하여 min cos(theta) 로 정리된다.

 

목적함수에 대하여 minimize 를 위한 식을 만들고 음의 기울기 방향으로 이동하여 값을 줄일 수 있다. 이러한 방법을 Gradient Descent(경사강하법) 이라고 한다.

-->기울기의 음의 방향으로 이동 시 local minimun으로 수렴 가능

Gradient Descent의 다음 입력 값은 다음과 같이 수정된다.

(Epsilon=learning rate)

특정 함수를 선형근사한 것에 대한 극점을 찾거나, 벡터의 크기, 증가 밑 감소 확인이 가능하다.

 

반복적인 작업 이외에 행렬 연산을 통하여 한번에 근을 찾는 방법 또한 존재한다.

4. Jacobian and Hessian Matrix

3 에서는 특정 방향에 대한 Gradient Descent를 진행하였지만 모든 벡터에 대한 Gradient Descent를 진행하여야 하는 경우도 생긴다.

 

 

Jacobian Matrix

m차원의 input이 n차원의 ouput을 가질 때 Jacobian Matrix는 nxm 차원이 되며 1차 미분 값을 가진다.

Hessian Matrix

x_i, x_j에 대하여 2차 미분 값을 가진다.

Hessian 행렬은 대칭행렬이며 따라서 고유값, 고유벡터로 분해 가능하다.

특정 방향에 대한 이차 미분 값은 (d^T)Hd 의 d로 표현되며, H의 상응하는 이차 미분값에 따라 계산된다.

 

Hessian Matrix는 테일러 급수에 따라 다음과 같이 정리된다.

이차 미분 값은 일차 미분 값에 대한 도함수를 표현한다. 다른 말로 일차 미분 그래프의 곡률 정도 를 표현한다. 다차원 공간에서는 특정 방향벡터에 대하여 local minimum으로 수렴하여도 다른 방향 벡터에 대하여는 minimum이 아닐 수 있다. Hessian Matrix는 local minimun에서 각각의 방향벡터들 간의 관계를 파악하는데, 이를 이용하여 local maximum, local minimum 밑 saddle point 를 확인할 수 있다.

또한 곡률 값을 바탕으로 학습의 진행에 대하여 어느 정도 성능이 나올 지 확인 이 가능하다.

위의 gradient descent 는 first-order optimization algorithms 로 불리며, 여기서는 정리하지 않은 Newton's method를 이용한 방법(minimize로 한번에 근사하는 방법)은 second-order optimization algorithms로 불린다.

 

 

머신러닝 학습에 있어서 정확한 성능이 보증되기 어려운 알고리즘 및 수학 이론이 많이 사용되며 가끔 보증되는 어떠한 머신러닝 알고리즘이 있기도하다. Lipschitz continuous 는 stepsize의 변화에 대하여 output을 짐작할 수 있게 해준다.

step size가 너무 클 경우 알고리즘이 diverge하게 되는 경우가 발생 하며 global minimun이 존재한다는 가정 하에 step size <= 2/L 값을 가질 때, stationary point로 반드시 수렴한다는 것이 증명된다.

 

 

@너무나 옛날에 하였던 것.. 파일 정리하다가 발견해서 올리기

@참고 [Deeplearningbook]