[cs231n] Note 3: Optimization (Optimization)

Optimization의 목적은 loss function을 최소화하는 $W$를 찾는 것이다. 

 

loss function을 최적화하는 optimization 방법을 소개하고자 하며, svm loss를 예시로 세가지 방법에 대하여 설명한다. 

 

1) Random Search

2) Random Local Search

3) Gradient

 

Random Search

첫 번째로 random search 방법이다. 

 

이 방법은 랜덤한 값의 $W$로 여러번 시행한 후 loss가 가장 작은 최적의 $W$를 선택하는 방법이기 때문에 가장 간단하지만 좋지 않은 방법이다. 

 

여러 번의 시행 중 최적의 $W$를 찾는다고 하더라도 이는 실행 횟수에 국한되어 있는 한계가 있으며 그 중 추출된 최적의 $W$가 모든 경우의 수에 대한 최적의 $W$라고 정의하기 어렵다. 

 

하지만 한번의 랜덤한 $W$를 실행하여 loss를 계산하는 것보다는 여러번의 반복 시행을 통해 개선된 loss를 구할 수 있다는 데에서 장점이 있다. 

 

즉, random search의 전략은 랜덤한 가중치 $W$에서 시작하여 여러번 학습을 통해 보다 개선된 $W$를 찾는것이다. 

 

다만 이 방법은 loss가 떨어지는 경우만을 고려하기 때문에 일시적인 최적의 값만으로 나타낸다. 

 

예를 들어, 울퉁불퉁한 산이 있을 때

 

첫 번째 고개를 넘어갈 때 내리막길로 내려갈 수는 있지만 그 다음 고개로 넘어가지 못하고 첫 번째 고개에 머무르게 되는 한계가 있다.

 

Random Local Search

두 번째로 random local search 방법이다.

 

앞의 random search는 특정 방향으로 내려가기만 할 뿐, 이후에 나타날 더 큰 내리막을 예상하지 못하고 올라가는 방향을 향하지 않는다. 

 

이러한 문제를 보완하는 방법으로 random local search가 소개되었다.

 

random local search의 시작은 random search와 동일하다.

 

우선적으로 랜덤한 초기화 파라미터 $W$로 시작한다. 

 

그리고 여러번의 loss계산을 통해 $W$를 업데이트하는 random search와는 달리, 

 

random local search는 $\delta W$를 생성한다. 

 

즉, 여러번의 loss 계산에서 $(W+\delta W)$에서의 loss가 낮아질 경우 $W$를 업데이트한다. 

 

여기에서 $\delta$를 step size라고 볼 수 있으며 특정 step size만큼 $W$를 이동시켜 local minima에 빠져 다음 고개로 향하지 못하는 문제를 해결하는데에 효과적이다. 

 

하지만 이 방법 역시 random search와 동일하게 여러번의 시행으로 loss를 최소화하는 $W$를 찾아야하기 때문에 연산량이 많은 단점이 있다. 

 

Gradient

마지막으로 gradient를 사용하는 방법이다. 

 

이전의 random search, random local search 방법은 랜덤하게 $W$를 초기화하여 최적의 loss를 위한 $W$를 구하였지만 gradient의 경우 계산을 통해 최적의 $W$를 찾기 위한 방향을 얻는다. 

 

즉, random search와 random local search는 랜덤한 계산을 통해 최적의 방향을 찾았지만 gradient 방법은 수학적 접근 방법으로 최적의 방향을 구하여 $W$를 업데이트한다. 

 

수학적 접근을 통해 최적의 방향을 찾는 방법은 loss function의 gradient를 사용한다. 

 

이는 기울기를 통해 가장 가파른 방향을 찾아 내려가는 것을 의미한다. 

 

1차원에서는 함수의 변화율을 의미하는데, 이 때 기울기(gradient)는 단순한 기울기가 아닌 벡터를 취하는 함수의 기울기라고 할 수 있다. 

 

즉, 도함수를 통해 함수의 기울기를 얻을 수 있고 이는 다음과 같다. 

 

$$\frac{df(x)}{dx} = lim_{h \to 0} \frac{f(x+h) - f(x)}{h}$$

 

Computing the gradient

 

앞서 랜덤한 값으로 최적의 $W$를 구하는 방법보다 수학적 접근 방법인 gradient를 이용한 방법이 더 효율적이라는 것을 설명하였다. 

 

기본적으로 도함수의 개념에서 시작된 gradient를 구하는 방법에 대하여 구체적으로 설명하고자 한다. 

 

gradient를 구하는 방법으로는 간단하지만 대략적인 numerical gradient와 정확하지만 에러를 찾기 위해 연산이 필요한 analytic gradient가 있다. 

 

1) numerical gradient

 

수학적으로 gradient를 계산하기 위해 벡터 $x$에 대한 함수 $f$의 연산이 이루어진다. 

 

이는 위의 Gradient에서 작성한 수식과 같다. 

 

$$grad_{x_i} = \lim_{h \to 0} \frac{f(x+h) - f(x)}{h}$$

 

위의 수식에 따라 각 차원에서 $h$가 변하는 정도를 도함수를 통해 얻게 된다.

 

#. 수식에서 $h$는 0에 가까이 수렴하도록 하지만 0이 아닌 매우 작은 값 (ex. 1e-5)으로 설정하는 것으로도 충분하다.

 

gradient는 loss를 낮게 만들기 위해 사용되기 때문에 gradient가 음의 방향으로 가도록 하여 $W$를 업데이트한다. 

 

즉, $W$를 최적화하기 위해 loss function을 계산하는데 loss function을 감소시키기 위해 gradient가 음의 방향으로 가도록 업데이트한다. 

 

다만, numerical gradient는 $lim$를 통해 근사한 값을 사용하여 계산하기 때문에 간단한 방법이지만 변수의 수가 선형적으로 복잡하고 단순한 근사치에 머문다는 단점이 있다. 

---

# learning rate

 

gradient는 가파른 기울기가 있는 방향을 알려줄 뿐, 그 방향으로 얼마나 가야하는 지에 대한 값을 알려주지는 않는다.

 

그래서 얼만큼 앞으로 갈 것인가 step을 결정하는 hyperparameter로 learning rate가 있다. 

 

가파른 언덕을 가정했을 때, 

 

learning rate가 클 경우, 빠른 속도로 내려갈 수 있지만 중간에 더 가파른 gradient가 있더라도 이를 놓치고 넘어가는 문제가 발생할 수 있다. 

 

반면, learning rate가 작을 경우, 느린 속도로 내려가지만 더 가파른 gradient를 놓치는 일을 방지할 수 있기 때문에 대부분 learning rate를 낮게 설정한다. 

---

2) analytic gradient

 

analytic gradient는 근사값을 사용하는 numerical gradient와 달리 미적분 연산을 통해 분석적으로 계산하는 방법이다. 

 

이는 numerical gradient보다 복잡하지만 근사치가 아닌 보다 빠르고 정확한 값으로 계산된다는 장점이 있다.

 

아래와 같이 SVM의 loss function 수식으로 보면,

 

$$L_i = \sum_{j \neq  y_i}[max(0, w_{j}^{T}x_{i} - w_{y_i}^{T}x_{i} + \Delta)]$$

 

위의 식에서 $W_{y_i}$를 기준으로 기울기를 구하면 다음과 같으며,

 

해당 식은 $j = y_i$로 실제 라벨에 속하는 $W$의 벡터 값에 대한 gradient이다. 

 

$$\nabla_{w_{y_i}}L_{i} = -(\sum_{j \neq y_i} 1(w_{j}^{T}x_{i} - w_{y_i}^{T}x_{i} + \Delta > 0))x_{i}$$

 

반대로 $j \neq y_i$과 같이 실제 라벨과 다른 라벨의 $W$ 벡터 값에 대한 gradient는 다음과 같다.  

 

$$\nabla_{w_j}L_{i} = 1(w_{j}^{T}x_{i} - w_{y_i}^{T}x_i + \Delta > 0)x_{i}$$

 

참고) https://cs231n.github.io/optimization-1/#optimization

CS231n Convolutional Neural Networks for Visual Recognition