[cs231n 정리노트] 3. Loss Functions and Optimization (3) Optimization

단순하게 한번에 minima를 찾을 수 있으면 좋겠지만. loss function에 regluarizer까지 엄청 커지고 복잡해지고 거기에 neural networks까지 사용한다면 minima까지 직접적으로 접근해주는 명시적으로 계산할 수 있는 수학적 해를 찾아내기는 어려울 것입니다. 그래서 실제로는 iterative한 방법을 사용합니다. 

첫번째로 생각할만한 가장 멍청한 방법은 random search입니다.

bestloss = float("inf") #파이썬이 가능한 가장 큰 float value를 대입해줌
for num in xrange(1000):
	W = np.random.randn(10, 3073) * 0.0001
    loss = L(X_train, Y_train, W)
    if loss < bestloss:
    	bestloss = loss
        bestW = W
    print `in attempt %d the loss was %f, best %f` % (num, loss, bestloss)

 

보시다시피 굉장히 쓰레기 알고리즘이고 절대 사용하면 안됩니다.

 

두번째로 경사를 따라가는 방법입니다.

산에서 가장 낮은 지점을 찾아가려고 할때 내가 서있는 위치에서 낮은 경사쪽으로 가다보면 도달할 수 있을 것 같습니다. 이를 적용해보았을 때 상대적으로 간단한 알고리즘 같아보이지만 실제로 꽤 잘 작동합니다.

1차원에서의 미분은 꽤 자연스럽게 다변수함수에서도 일반화됨.
실제로 우리는 스칼라가아닌 벡터를 다룹니다. 따라서 저 공식을 일반화할 필요가 있습니다. 다변수 환경에서 미분의 일반화는 gradient입니다, gradient는 편미분들의 vector입니다, 따라서 gradient는 x와 같은 모양을 가집니다. 그리고 gradient의 각요소들은 그 좌표 방향으로 움직였을때 우리의 함수f들의 기울기가 무엇인지 말해줍니다. gradient의 장점은, gradient가 편미분들의 vector이지만 함수가 가장 크게 증가하는 방향을 가리키고, 이에 따라서 함수가 가장 크게 감소하는 방향은 음의 gradient를 보면 알 수 있습니다.그리고 더 일반적으로 만약 어떠한 방향에서는 내 landscape의 기울기를 알고 싶다면 그건 gradient와 unit vector의 dot product와 동일합니다. gradient는 현재 위치에서의 함수에 대한 선형 일차 근사값을 주기 때문에 gradient는 매우 중요합니다. 그래서 실제로 많은 딥러닝은 함수의 gradient를 계산하고 그 gradient를 사용해 계속해서 파라미터 벡터를 업데이트하는 것에 관한 것입니다.

---

컴퓨터에서 gradient를 naive하게 구하려면 유한차분을 사용하면 됩니다.

gradien dW를 계산해보겠습니다. 위 슬라이드에서 W의 첫번째 원소를 h라는 작은 값만큼 증가시키고 다시 loss 값을 계산합니다. 이제 극한 공식에 따라 첫번쨰 원소에 대한 gradient를 계산합니다. 이제 나머지 모든 원소들도 반복적으로 동일하게 계산하면 됩니다.

하지만 이런 방식은 매우 느리기 때문에 좋지 않습니다. 만약 엄청 큰 cnn모델이라고 생각한다면 이 함수 f를 계산하는 데에 오랜 시간이 걸리게됩니다. 그리고 파라미터 벡터 W는 위처럼 고작 10개의 원소만을 가지지 않고 천만 혹은 억 단위의 원소를 가질 것입니다.  유한차분 방식은 단 하나의 gradient를 얻기 위해 매우 오랜 시간을 기다려야하기 때문에 실제로는 사용하지 않습니다.

---

 

실제로는 W의 모든 차원을 돌기보다는 먼저 gradient에 대한 분석적인 표현(analytic gradient)를 찾고 W로부터 직접 dW 혹은 gradient를 계산합니다. 

위의 numeric gradient도 좋아보이긴 하지만 실제로는 analytic gradient를 거의 항상 사용합니다.

analytic expression이 맞는지 확인하고 싶으면 numeric gradient를 사용해 디버깅 해볼 수 있습니다.

---

Gradient Descent

while True:
    weights_grad = evaluate_gradient(loss_fun, data, weights)
    weights += - step_size * weights_grad

 

step_size는 hyperparameter입니다. gradient를 계산할때 그 방향으로 얼마나 멀리 갈지 정해줍니다, 가끔 learning_rate라고도 부릅니다. 가장 중요한 hyper parameter로 항상 첫번째로 체크해야할 하이퍼파라미터입니다. model size나 regularization strength는 나중에 체크하고 learning rate를 올바르게 하는 것이 첫번째입니다. 

 

 

2차원의 간단한 예시를 살펴보겠습니다. 이 bowl은 우리의 loss function을 보여줍니다. 빨간 영역은 우리가 원하는 낮은 loss 값 영역, 파란색 초록색으로 갈 수록 우리가 피해야하는 높은 loss 영역입니다. W를 랜덤한 영역에서 시작해보겠습니다. 우선 negative gradient direction을 계산할거임, 그리고 그렇게 계산한게 결국 minima로 방향을 가리키길 기대하며 이걸 계속 반복하다보면 실제 minima에 도달하게됩니다.

---

SGD

 

 

우리는 loss가 우리의 classifier가 각각의 single training example에 대해 얼마나 나쁘게 동작하는지 계산하는 것이라고 정의했고 전체 loss는 전체 training set의 loss 값의 평균이라고 얘기했습니다. 하지만 실제로 N은 매우매우 큽니다. 만약 ImageNet dataset을 예로 들면 N은 130만입니다. 그래서 이런 loss를 계산하는 것은 비용이 매우 크고 이 함수에 대해 수백만번의 계산을 요구할것입니다. 따라서 gradient를 계산하는 건 전체 training set을 iterate해야하기 때문에 매우매우 오래 걸립니다. 그래서 W의 update를 매우매우 오래 기다려야합니다. 그래서 실제로는 stochastic gradient descent라고 불리는 걸 사용합니다. 전체 training set의 loss와 gradient를 계산하기보다는 각각의 iteration에서 우리는 training set의 작은 set을 sample하고 이를 minibatch라고 부릅니다. 보통 배치사이즈는 2의 제곱 (32/64/128/...)로 정합니다. 그리고 우리는 이 작은 minibatch를 전체 합의 추정값과 실제 gradient의 추정값을 계산하기 위해 사용합니다. 이게 왜 stochastic이냐면 실제 값의 기대치에 대한 monte carlo 추정으로 볼 수 있기 때문입니다.

while True:
    data_batch = sample_training_data(data, 256)
    weights_grad = evaluate_gradient(loss_fun, data_batch, weights)
    weights += - step_size * weight_grad

 

아까 알고리즘보다 더 좋아진 것 같은데 아직도 4줄밖에 안됩니다.
minibatch에 대한 loss를 계산하고 이 loss와 gradient의 추정치에 기반해서 파라미터 W를 업데이트합니다.

---

 

http://vision.stanford.edu/teaching/cs231n-demos/linear-classify/

Multiclass SVM optimization demo

위 사이트에서 하이퍼파라미터를 바꿔가며 시각적으로 모델의 학습과정을 확인할 수 있습니다.

---

Image Feature

지금까지 linear classifier에 대해 얘기해보았는데, 지금까지는 단순히 raw image pixel을 가지고 그 이미지 픽셀 자체를 linear classifier에 넣었습니다. 하지만 이건 multi-modality 같은 것들 때문에 별로 좋지 않습니다. 실제로 raw pixel 값을 linear classifier에게 주는(feeding) 건 잘 동작하지 않습니다. deep neural networks 지배 이전에는 꽤 흔했던 두 단계의 approcch가 있었습니다. 이미지를 가져와서 우선 다양한 feature representations을 계산합니다.(아마도 다양한 종류의 appearance에 관한 quantity들입니다.) 그리고 각각의 feature vector들을 이어붙입니다.(concatenate) 그리고 그 이미지의 feature representation을 linear classifier에게 줍니다.

왼쪽과 같은 training data set이 있다고 해보겠습니다. 빨간색 점들과 파란색 점들을 구분할 수 있는 선형 결정 경계(linear decision boundary)를 그리는 방법이 존재하지 않습니다. 하지만 극좌표계로 바꾸는 feature transform을 한 이후에는 이 복잡한 데이터셋이 실제로 선형적을 구분가능하게되었습니다. 그리고 linear classifier에 의해 정확하게 classify될 수 있게 됐습니다. 가장 중요한 요령은 관심 있는 문제에 대한 올바른 quantity를 계산하는 올바른 feature transform이 뭔지 알아내는 것입니다. 예를 들어 이미지에서 각 픽셀을 극좌표계로 변환하는 건 말이 안되지만 말이될것같은 이미지의 feature representation들을 적어내는 건 가능합니다.

 

이런 feature representation 중의 한 예시로는 color histogram이 있습니다.

---

Color Histogram

큰 색깔 스펙트럼을 가지고 각각의 bucket을 나눠서 각 픽셀들을 해당하는 색깔 bucket중 하나로 mapping합니다. 그리고 얼마나 많은 pixel들이 각각의 버켓에 들어갔는지 셉니다. 이것은 전반적으로 이미지 안에 어떤 색깔들이 있는지 알려줍니다.

 

 

Histogram of Oriented Gradients (HoG)

neural networks 이전에 볼 수 있는 또다른 흔한 종류의 feature vector는 HoG (Histogram of Oriented Gradients)입니다.

예전 강의에서 hubbel과 Wiesel이 oriented edge들이 사람의 시각 시스템에서 중요하다는 것을 발견해냈다고 하였습니다. 그리고 HoG feature representations은 같은 방법을 capture하려고 했고 이미지에서 edge의 local orientation 측정하려고했습니다. 이미지를 작은 8x8 픽셀 크기의 작은 영역으로 나눈 뒤, 각각의 영역에서 지배적인 edge의 방향을 계산하고 이를 bucket으로 양자화하였습니다. 각각의 픽셀 영역에서 다양한 edge orientation으로 히스토그램을 계산합니다. 이렇게 계산된 모든 8 x 8 영역의 히스토그램을 결합하면 이미지 전체에 대한 full-feature vecotr가 됩니다. 예를 들어 나뭇잎은 지배적으로 대각선 방향의 edge를 많이 포함하고 있습니다. 따라서 나뭇잎 이미지의 oriented gradient features 히스토그램을 시각화하면 다양한 대각선 edge 패턴이 두드러지게 나타납니다. 꽤 최근까지도(2017년 기준) object recognition에서 많이 사용된 기법 중 하나입니다.

 

 

Bag of Words

또 다른 아이디어는 Bag of Words입니다.

 

 

이 방법은 자연어 처리에서 영향을 받았습니다. 문장을 feature vector로 표현하는 한가지 방법은 문장 속 단어들의 출현빈도를 세는 것입니다. 이러한 아이디어를 이미지 데이터에도 적용하고 싶었지만, 단순히 동일한 방식으로는 구현하기 어려웠습니다. 따라서, 우리만의 visual words vocabulary를 정의할 필요가 있었습니다. 이를 위해 주요한 두 가지 단계가 있습니다.

 

1. 대규모 이미지 데이터셋을 수집하고, 매우 작은 크기의 랜덤 패치를 대량으로 샘플링합니다.

2, 이 샘플들을 K-means와 같은 군집화 기법을 사용하여 여러 개의 클러스터로 그룹화합니다.

 

오른쪽 샘플들을 보면 클러스터링 이후, visual words가 다양한 색깔(red, blue, yellow...)과 다양한 종류의 oriented edges를 효과적으로 포착하고있음을 확인할 수 있습니다. 

 

흥미로운 점은, 이렇게 하면 oriented edges를 완전히 data-driven 방식으로 학습할 수 있다는 것입니다. 즉, 사람이 직접 정의하는 것이 아니라 데이터로부터 시각적 특징을 자동으로 추출할 수 있습니다.

 

이제 visual words의 집합(code book)을 얻은 후에는, 이미지 내에서 각 visual word가 얼마나 자주 등장하는지를 기반으로 이미지를 인코딩할 수 있습니다. 이를 통해, 이미지의 visual appearance에 대한 새로운 정보를 효과적으로 제공할 수 있습니다.

---

다음 시간에는 neural network와 backpropagation을 배워봅시다.!