[Assignment1 - Q2] SVM

 

※ 본 내용은 stanford에서 제공하는 cs231n 강의, 강의자료를 바탕으로 작성하였습니다.

 

Q2에서는 SVM loss의 계산과 미분 그리고 SGD를 통한 optimization에 대해 다루고 있다.

 

 

<SVM>

- setup

 

X_train, X_val, X_test, X_dev 의 shape는 위와 같다. 

 

- Naive하게 svm loss와 dW 계산하기

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)*****
    #pass
    dW += W*2*reg

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

    return loss, dW

2중 for문을 이용해서 loss와 미분(dW)를 계산하는 코드이다.

 

loss의 경우 2중 for문을 통한 구현은 직관적이고 어렵지 않기 때문에 생략한다.

 

미분의 경우 loss 의 식을 천천히 살펴보면 된다. 

 

loss에 값이 추가되는 경우는 margin > 0인 경우이고, 그때 더해지는 값, margin은 다음과 같다. 

$ loss += (x^{(n)}W^{(j)} - x^{(n)}W^{(y_i)} + 1) $

(j : 잘못 예측한 class, $ y_i$ : 정답 class)

따라서 $ W^{(j)}$에 대한 미분값으로는 $ +x^{(n)}$, $ W^{(y_i)}$에 대한 미분값으로는 $ -x^{(n)}$이 더해질 것이다.  

 

(어차피 선형수식으로 계산이 되기 때문에 각 연산마다 개별적으로 dW += ~ 를 연산해도 된다.)

 

마지막으로 data의 수로 나눠주고, 마지막에 regularization에 대한 미분을 더해주면 된다.

 

 

- fully vectorize하여 loss와 미분(dW) 계산하기

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)*****

    mul = np.dot(X, W) #500x10
    S_correct = mul[np.arange(X.shape[0]), y].reshape(-1, 1) # 500x1, 맞는 label 들의 score

    S_gap = (mul - (S_correct - 1)).clip(0)
    S_gap[np.arange(X.shape[0]), y ] =0
    loss = (np.sum(S_gap) / X.shape[0]) + 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)*****

    #pass
    Z = np.where(S_gap > 0, 1, 0)
    Z[np.arange(X.shape[0]), y] = -np.sum(Z, axis = 1) # 정답보다 score가 높은 lable의 수
    dW += np.dot(X.T, Z) / X.shape[0]
    dW += (2*reg*W)




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

    return loss, dW​

● loss

  1. $ XW $의 결과로 score가 계산되고(code상으로는 mul이라고 표시) 

  2. 맞는 label의 score와 margin을 고려해서 각 행에 빼준다.

  3. clip을 통해 0 이하의 값은 0으로 바꾸고, 맞는 label의 값도 0으로 바꿔준다.

위 3과정만 거치면 margin값만 남게되고, np.sum()을 통해 margin을 전부 더해주면 loss가 계산된다. 

 

● 미분(dW)

미분을 fully vectorize하는 것은 꽤 복잡하다.

처음엔 구현을 하지 못했고, 코드를 참고한 후 이해하는 방향으로 학습했다.

덕분에 다음 과제인 softmax classifier에서 비슷한 내용은 스스로 구현할 수 있었다.

(https://github.com/hohyun312/cs231n-stanford 의 코드를 사용하였습니다.)

 

먼저 기본적으로 계산 원리는 naive하게 구현한 원리를 그대로 이용한다. 

 

$ dW^{(i)}$ = ($ W^{(i)}$와 곱해져 margin > 0이 된 $ x^{(n)}$들의 합)

                  - ( ($ i$-th label이 정답이고, 그 외 class에 대한 margin > 0 인 label의 수 x $ x^{(n)}$) 의 합 )

 

naive 방식에서 하나의 데이터마다 더하거나 뺐던 값을 모든 데이터에 대해 정리하면 위와 같이 나타낼 수 있다. 

위식을 vectorize하는 것이 문제였는데, 각 $ x^{(n)}$에 대한 합을 for문을 사용하지 않고 구현하는 방법이 떠오르지 않았다.

결과적으로, 행렬곱의 연산 중 다음과 같은 특징을 이용하면 됐다.

보통 행과 열의 내적에만 집중을 하지만, column간의 연산에도 위와 같은 관계가 있다.

 

이제 다시 코드를 미분을 계산하는 코드를 살펴보면 먼저 Z에는 margin > 0 인 score에만 1이 masking되고,

(Z.shape = (n_data, class의 수))

 

다음 줄에서는 정답 label의 score가 자리에는 정답 label이 아닌데 margin > 0 인 label의 수를 구한다.

(이 경우 뺴야하기 때문에 음수로)

 

이제 X의 전치행렬과 Z를 곱하기만 하면 dW가 계산된다. (물론 regularization의 미분도 더해줘야  한다.)

 

다소 이해가 안갈수 있어 위 특징을 미분의 연산에 그대로 적용한 예시를 한 번 더 살펴보면 다음과 같다. 

데이터의 수를 4개로 간소화한 예시이다.

Z에서 1인 경우는 $ W^{(0)}$와 곱해져서 margin > 0이 된 경우이고, Z의 4행 1열의 -3은 그 외 3개의 class가 모두 margin > 0이라는 것을 의미한다. 

 

$ dW^{(i)}$ = ($ W^{(i)}$와 곱해져 margin > 0이 된 $ x^{(n)}$들의 합)

                  - ( ($ i$-th label이 정답이고, 그 외 class 중 margin > 0 인 label의 수 x $ x^{(n)}$) 의 합 )

위 설명과 일치되도록 계산이 되는 것을 확인할 수 있다. 

 

<SGD>

SGD의 경우 구현의 문제로 크게 어렵진 않기 때문에 자세한 내용은 생략한다.

 

hyperparameter를 조정하여 validation accuracy를 높이는 실험이 포함되었는데, 다음과 같은 결정과정을 따랐다.

 

1. loss가 계속하여 감소되지 않으면 learning rate를 줄인다.

2. loss는 줄었으나 validation accuracy는 감소하면 regulization parameter를 증가시킨다. 

 

문제에서 hyperparameter를 잘 조정하면 0.39이상의 validation accuracy가 가능하다는 hint가 있어서,

해당 수치가 나올 때 까지 위 과정을 반복하여 hyperparameter를 조정할 수 있었다.