CS231n assignment1 : SVM

이번에는 첫번째 과제(knn)에 이어서 svm 알고리즘을 작성하게 되었다.

과제를 완료하는데 굉장히 오랜 시간이 걸렸으며, 다른 블로그 코드와 chatgpt도 많이 참고했던 것 같다. 

다음 과제부터는 최대한 나 스스로(?) 많이 해결하고 싶다....

 

작성하게 될 코드 파일은 크게 세개이다.

svm.ipynb

linear_svm.py

linear_classifier.py

 

 

이번에도 마찬가지로 CIFAR-10 Data가 이용되며, data 분석에 이용될 train, test data의 사이즈는 다음과 같다.

 

 

 

코드의 아랫부분으로 더 내려가보면, train, validation, test data의 사이즈를 확인할 수 있다.

 

 

< preprocessing >

preprocessing 과정까지 skeleton code로 제공된다.

preprocessing은 크게 세가지 과정으로 나뉜다.

1. training data에 기반해 image mean 값을 계산한다.

2. train data와 test data에서 mean image 값을 뺀다.

3. bias trick

 

여기서 bias trick 이란?

흔히 bias를 행렬 곱을 계산한 뒤 나중에 추가로 더하는? 벡터 b 라고 생각하지만, bias trick에서는 벡터 b를 아예 W(weight)의 마지막 열에 붙여서 b를 추가적으로 더하지 않고 곱만 계산해도 되도록 변형한 형태를 의미한다. (아래 그림 참고)

 

 

 

여기서부터 본격적인 코딩이 시작된다...

 

< function svm_loss_naive >

먼저 linear_svm.py의 function svm_loss_naive을 채워넣어야한다.

 

 

 

 

코드를 작성하기에 앞서 먼저 loss function 개념을 이해해야한다.

 

SVM loss function은 아래 사진에 잘 정리되어있다.

우리가 이 코드에서 채워넣어야하는 부분은 엄밀히 따지면 loss function(첫번째 공식)보단 loss function의 gradient 이므로, 미분한 식(두번째, 세번째 공식)을 더 주의깊게 보면 좋겠다.

 

 

최종적으로 위에서 구한 L_i들의 평균을 구한 뒤, regularization loss를 더하면 된다.

 

loss function 최종 ver.

 

w_yi, w_j에 대해 편미분 하는 것인데... 편미분의 개념을 정확히 몰라도 느낌적으로 이게 어떤 식이겠구나~ 느낌만 받아도 코드를 작성하기엔 충분한 것 같다. 

 

여기서 yi는 정답 class, j는 잘못 예측한 class이다.

따라서, 정답 class yi 에 대해 편미분했을 땐 x_i를 빼주고 (두번째 공식)

잘못된 class j 에 대해 편미분했을 땐 x_i 값이 더해진다. (세번째 공식)

 

 

위 공식을 바탕으로 작성한 코드(function svm_loss_naive)는 아래와 같다.

기존에 있던 주석을 제거하지 않고 넣어서 코드가 길어보이지만, 실질적으로 채워넣은 길이는 짧다.

def svm_loss_naive(W, X, y, reg):
    """
    Structured SVM loss function, naive implementation (with loops).

    Inputs have dimension D, there are C classes, and we operate on minibatches
    of N examples.

    Inputs:
    - W: A numpy array of shape (D, C) containing weights.
    - X: A numpy array of shape (N, D) containing a minibatch of data.
    - y: A numpy array of shape (N,) containing training labels; y[i] = c means
      that X[i] has label c, where 0 <= c < C.
    - reg: (float) regularization strength

    Returns a tuple of:
    - loss as single float
    - gradient with respect to weights W; an array of same shape as W
    """
    dW = np.zeros(W.shape)  # initialize the gradient as zero

    # compute the loss and the gradient
    num_classes = W.shape[1]
    num_train = X.shape[0]
    loss = 0.0
    for i in range(num_train):
        scores = X[i].dot(W)
        correct_class_score = scores[y[i]]
        for j in range(num_classes):
            if j == y[i]:
                continue
            margin = scores[j] - correct_class_score + 1  # note delta = 1
            if margin > 0:
                loss += margin
                dW[:, y[i]] += -X[i] / num_train
                dW[:, j] += X[i] / num_train

    # Right now the loss is a sum over all training examples, but we want it
    # to be an average instead so we divide by num_train.
    loss /= num_train

    # Add regularization to the loss.
    loss += reg * np.sum(W * W)

    #############################################################################
    # TODO:                                                                     #
    # Compute the gradient of the loss function and store it dW.                #
    # Rather that first computing the loss and then computing the derivative,   #
    # it may be simpler to compute the derivative at the same time that the     #
    # loss is being computed. As a result you may need to modify some of the    #
    # code above to compute the gradient.                                       #
    #############################################################################
    # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

    dW += 2 * reg * W
    #print(dW)

    # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

    return loss, dW

 

스켈레톤 코드에서 추가로 작성한 부분은 크게 두가지로 나눌 수 있다.

 

첫번째 파트

if margin > 0:
                loss += margin
                dW[:, y[i]] += -X[i] / num_train
                dW[:, j] += X[i] / num_train

 

앞서 공식에 대해 설명할 때,

y[i] 에서는 X[i]의 값을 빼주고, j에서는 X[i]의 값을 더해준다고 언급했다.

요걸 그대로 식으로 옮긴 느낌.

(모르겠으면 공식을 보고 이해해보자... 이부분이 젤 이해하기에 빡세다)

 

왜 num_train으로 나눴는지도 최종 loss function 공식을 보면 이해될 것이다. (공식에서 N으로 나눠주는 맥락이랑 동일)

 

 

두번째 파트

dW += 2 * reg * W

 

요건 공식에서 regularization loss 부분을 미분했을 때 나오는 식이다!

미분하기 전 형태가 reg * np.sum(W * W) 이었으니까 미분하면 2 * reg * W가 된다.

 

 

코드를 다 작성했다면 아래 보이는 코드처럼 numerical과 analytic의 값이 일치하는지 비교해보자.

 

 

 

 

< function svm_loss_vectorized >

앞서 작성했던 함수보다 훨씬 어려우니... 포기하지 말자...

갑자기 vectorized 하라는게 뭔 소린가 싶을 수도 있을텐데... 쉽게 설명하면 위에서 이중 for문을 사용해서 구현했던 코드를 for문 없이 구현해보란 소리다. (cs231n 과제는 대체로 이와 비슷한 맥락의 과제가 많은 것 같다...)

 

작성한 코드는 아래와 같다. 

 

def svm_loss_vectorized(W, X, y, reg):
    """
    Structured SVM loss function, vectorized implementation.

    Inputs and outputs are the same as svm_loss_naive.
    """
    loss = 0.0
    dW = np.zeros(W.shape)  # initialize the gradient as zero

    #############################################################################
    # TODO:                                                                     #
    # Implement a vectorized version of the structured SVM loss, storing the    #
    # result in loss.                                                           #
    #############################################################################
    # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

    num_train = X.shape[0]
    score = X @ W
    correct_score = score[np.arange(num_train),y].reshape(-1, 1)
    margin = np.maximum(0, score - correct_score +1)
    margin[np.arange(num_train),y ] = 0
    
    loss = np.sum(margin) / num_train
    loss += reg * np.sum(W * W)


    # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

    #############################################################################
    # TODO:                                                                     #
    # Implement a vectorized version of the gradient for the structured SVM     #
    # loss, storing the result in dW.                                           #
    #                                                                           #
    # Hint: Instead of computing the gradient from scratch, it may be easier    #
    # to reuse some of the intermediate values that you used to compute the     #
    # loss.                                                                     #
    #############################################################################
    # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

    margin[margin > 0] = 1
    count = margin.sum(axis = 1)
    margin[np.arange(num_train), y] -= count
    dW = (X.T).dot(margin) / num_train
    dW += 2* reg * W

    # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

    return loss, dW

 

 

이번에도 크게 두가지 파트로 나눠서 설명할 수 있겠다.

 

첫번째 파트

loss function 작성에 관한 파트인만큼, 아래의 loss funcion 식과 비교하면서 이해하면 쉽다.

 

num_train = X.shape[0]
score = X @ W
correct_score = score[np.arange(num_train),y].reshape(-1, 1)
margin = np.maximum(0, score - correct_score +1)
margin[np.arange(num_train),y ] = 0
    
loss = np.sum(margin) / num_train
loss += reg * np.sum(W * W)

 

loss function 식, 위 코드에서는 margin으로 이해하는게 쉬울 것이다.

 

위 코드에서 맨 끝 두줄..... 에 해당하는 부분

 

두번째 파트

loss function에 이어 gradient에 관한 파트이다.

margin이 0이상인 부분을 masking 한 뒤, 그 개수를 counting해서 뺀다.

 

맨 아래 두줄은 앞서 작성한 코드와 같은 맥락이다.

margin[margin > 0] = 1
count = margin.sum(axis = 1)
margin[np.arange(num_train), y] -= count
dW = (X.T).dot(margin) / num_train
dW += 2* reg * W

 

 

코드를 다 작성하였다면, diffrence가 0으로 나타나는지 확인해본다. 0이 아닌 값이 나온다면... 코드를 잘못 작성하였을 확률이 높다...

 

 

 

< SGD >

SGD에 관한 개념은 생략하도록 하며... 작성한 코드만 첨부하였다.

linear_classifier.py의 LinearClassifier.train()을 수정하면 된다.

 

핵심은 np.random.choice를 사용해 mini batch를 random하게 선정해야한다는 것!

def train(
        self,
        X,
        y,
        learning_rate=1e-3,
        reg=1e-5,
        num_iters=100,
        batch_size=200,
        verbose=False,
    ):
        """
        Train this linear classifier using stochastic gradient descent.

        Inputs:
        - X: A numpy array of shape (N, D) containing training data; there are N
          training samples each of dimension D.
        - y: A numpy array of shape (N,) containing training labels; y[i] = c
          means that X[i] has label 0 <= c < C for C classes.
        - learning_rate: (float) learning rate for optimization.
        - reg: (float) regularization strength.
        - num_iters: (integer) number of steps to take when optimizing
        - batch_size: (integer) number of training examples to use at each step.
        - verbose: (boolean) If true, print progress during optimization.

        Outputs:
        A list containing the value of the loss function at each training iteration.
        """
        num_train, dim = X.shape
        num_classes = (
            np.max(y) + 1
        )  # assume y takes values 0...K-1 where K is number of classes
        if self.W is None:
            # lazily initialize W
            self.W = 0.001 * np.random.randn(dim, num_classes)

        # Run stochastic gradient descent to optimize W
        loss_history = []
        for it in range(num_iters):
            X_batch = None
            y_batch = None

            #########################################################################
            # TODO:                                                                 #
            # Sample batch_size elements from the training data and their           #
            # corresponding labels to use in this round of gradient descent.        #
            # Store the data in X_batch and their corresponding labels in           #
            # y_batch; after sampling X_batch should have shape (batch_size, dim)   #
            # and y_batch should have shape (batch_size,)                           #
            #                                                                       #
            # Hint: Use np.random.choice to generate indices. Sampling with         #
            # replacement is faster than sampling without replacement.              #
            #########################################################################
            # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

            #choice를 랜덤하게 만들어야하므로
            choices = np.random.choice(num_train, size = batch_size, replace = True)
            X_batch = X[choices]
            y_batch = y[choices]

            # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

            # evaluate loss and gradient
            loss, grad = self.loss(X_batch, y_batch, reg)
            loss_history.append(loss)

            # perform parameter update
            #########################################################################
            # TODO:                                                                 #
            # Update the weights using the gradient and the learning rate.          #
            #########################################################################
            # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

            self.W -= learning_rate * grad

            # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

            if verbose and it % 100 == 0:
                print("iteration %d / %d: loss %f" % (it, num_iters, loss))

        return loss_history

 

 

 

이어서 predict function도 스켈레톤 코드의 빈칸에 아래와 같이 채워넣어준다.

scores = X.dot(self.W)
y_pred = scores.argmax(axis = 1)

 

이때의 정확도는 아래와 같이 계산된다.

대략 36~37%의 정확도를 보인다.

 

 

 

< hyperparameter tuning >

드디어 과제의 마지막 부분이다!

최적의 learning rate와 regularization_strengths를 찾는 것이 목적이다.

 

기존에 적혀있던 아래의 값 외에도, 새로운 값을 추가해서 코드를 돌려봐도 된다.

learning_rates = [1e-7, 5e-5]

regularization_strengths = [2.5e4, 5e4]

 

작성한 코드는 아래와 같다.

# Use the validation set to tune hyperparameters (regularization strength and
# learning rate). You should experiment with different ranges for the learning
# rates and regularization strengths; if you are careful you should be able to
# get a classification accuracy of about 0.39 (> 0.385) on the validation set.

# Note: you may see runtime/overflow warnings during hyper-parameter search.
# This may be caused by extreme values, and is not a bug.

# results is dictionary mapping tuples of the form
# (learning_rate, regularization_strength) to tuples of the form
# (training_accuracy, validation_accuracy). The accuracy is simply the fraction
# of data points that are correctly classified.
results = {}
best_val = -1   # The highest validation accuracy that we have seen so far.
best_svm = None # The LinearSVM object that achieved the highest validation rate.

################################################################################
# TODO:                                                                        #
# Write code that chooses the best hyperparameters by tuning on the validation #
# set. For each combination of hyperparameters, train a linear SVM on the      #
# training set, compute its accuracy on the training and validation sets, and  #
# store these numbers in the results dictionary. In addition, store the best   #
# validation accuracy in best_val and the LinearSVM object that achieves this  #
# accuracy in best_svm.                                                        #
#                                                                              #
# Hint: You should use a small value for num_iters as you develop your         #
# validation code so that the SVMs don't take much time to train; once you are #
# confident that your validation code works, you should rerun the validation   #
# code with a larger value for num_iters.                                      #
################################################################################

# Provided as a reference. You may or may not want to change these hyperparameters
learning_rates = [1e-7, 5e-5]
regularization_strengths = [2.5e4, 5e4]

# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

for lr in learning_rates:
  for reg in regularization_strengths:
    svm = LinearSVM()
    svm.train(X_train, y_train, learning_rate= lr, reg = reg, num_iters = 500)

    y_train_pred = svm.predict(X_train)
    y_val_pred = svm.predict(X_val)

    train_accuracy = np.mean(y_train_pred == y_train)
    val_accuracy = np.mean(y_val_pred == y_val)

    results[(lr, reg)] = (train_accuracy, val_accuracy)

    if(val_accuracy > best_val):
      best_val = val_accuracy
      best_svm = svm
    

# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****

# Print out results.
for lr, reg in sorted(results):
    train_accuracy, val_accuracy = results[(lr, reg)]
    print('lr %e reg %e train accuracy: %f val accuracy: %f' % (
                lr, reg, train_accuracy, val_accuracy))

print('best validation accuracy achieved during cross-validation: %f' % best_val)

 

 

이때의 출력값을 아래와 같다.

이번에도 마찬가지로 대략 36~37%의 정확도를 보인다.

 

 

 

test set을 대상으로 best_svm에 대한 accuracy를 구했을 땐, 37.4%보다 약간 낮은 값인 36.7% 정도의 정확도를 보였다. (그래도 이전에 knn에 비하면 많이 나아진 것 같..기도?)

 

 

 

마지막 문제에서는 위에서 구한 svm 모델을 바탕으로 하여 각 클래스의 이미지를 시각화하였다. 대충 뭉개진 형태긴 하지만 꽤 그럴싸(?) 하다는 것을 발견할 수 있다. 특히 plane과 ship의 경우 하늘 혹은 바다가 배경일 가능성이 높기 때문에 대체적으로 rgb 색상 중에서도 전반적으로 파란색을 띈다는 점을 확인할 수 있다.

car에서는 보라색 창문과 차의 몸체처럼 보이는 빨간색 파트로 구분된다. frog의 경우에도 개구리가 초록색이다 보니 전반적으로 초록빛을 띄며, horse는 중앙의 갈색 물체에 다리와 유사한 형태의 무언가가 달려있는 것 같은 형상이 나타난다.

 

 

 

이번 과제는 정말... 내가 전산이 맞는가? 라는 의문이 들정도로 꽤나 어려웠고 (내가 너무 만만하게 봤던 것도 있다)

내가 분명 기계학습 수업을 잘 들었음에도 불구하고 코드로 작성하는게 너무 어려워서... ㅠㅠ 코딩의 중요성을 다시 한번 느꼈다... (개념을 안다고 다 아는게 아니야...) 남은과제도 화이팅 :)