[CS231n] Assignment 1, Implement of vectorized lienar svm

Introduction

CS231n 과제 1번의 두번째가 Linear SVM을 구현하는 것입니다.

편의상 Delta=1로 두고 구현을 하고 있고, 이거 감안해서 봐주시면 감사하겠습니다.

Forward Pass와 Backpropagation을 구현하는 것이 핵심 토픽인데, 반복문 버전이랑 벡터화 버전이 있습니다.

반복문 버전은 뭐... 쉽게 할 수 있으니 넘어가고, 벡터화버전에 대해서 알아보도록 하겠습니다.

Forward Pass (Using iteration)

먼저, 반복문 버전의 코드부터 봅시다.

일단 loss는 Margin들의 합임을 알 수가 있고, margin을 계산하기 위해서는 정답의 값이 필요함을 알 수 있습니다.

코드를 보면, class 개수만큼 반복문을 돌면서 margin을 계산하는 것을 알 수가 있죠.

반대로 말하면, $i$(train)이 고정되어 있는 한 correct_class_score는 변하지 않음을 알 수 있습니다. 고정이 된다는 것이죠.

이걸 나중에 행렬곱으로 표현할 필요가 있습니다.

이렇게 loss들의 합을 구하고 나면, 마지막으로는 regularzation에 대한 것도 구해야합니다.

이건 앞의 Batch normalization backpropagation을 설명하며 사용한 방법을 재활용할 예정입니다.

$f(W)=W^2$, 이 때 $f$는 element-wise operation이라고 생각하면 $reg \times \sum_i \sum_j W_{ij}^2$은 $reg\times\sum_i\sum_j f(W)$로 쓸 수 있고, 모든 element를 다 더하는 것은 $\mathbf{1} f(W)\mathbf{1}$로 작성할 수 있습니다. 

결국 Loss도 Scalar로 반환되기 때문에, Trace-trick을 사용해도 문제가 없습니다.

Forward Pass (Using vectorization)

이제, 벡터화하여 최대한 행렬곱으로 표현할 시간입니다!

먼저, margin이 0보다 클 때만 loss를 더하는 이 부분부터 처리해보도록 하죠.

Activation function을 배우신 분들은 이 과정이 ReLU 함수를 통과하는 과정이랑 굉장히 유사함을 알 수 있습니다.

$ReLU(x)=\max(0,\,x)$로 표현 가능하므로, 우리도 마지막에 저 부분을 max operation을 통과함으로써 마무리 하면 되겠네요.

이러면 추후 Backpropagation할 때 ReLU를 미분해 줄 필요도 있는데, $x>0$이면 gradient를 1로, 그렇지 않으면 0으로 반환하는 방식으로 진행합니다. Python에서 boolean indexing을 진행하면 쉽게 할 수 있습니다.

다음 과정은 본격적으로 행렬 계산을 하는 부분입니다.

사실, score를 계산하는 과정은 굉장히 쉽습니다. 이건 그냥 Train set $X$와 Weight matrix $W$를 곱해주기만 하면 끝입니다. 따로 bias도 없기 때문에, 곱하기만 하면 됩니다.

하지만, 여기에서 정답 벡터만 추출하는 과정이 쉽지 않습니다. 앞의 Iteration 과정에서 말했듯이, $i$가 고정되어 있는 한 correct_class_score는 변하지 않으므로 정답 matrix는 $X$의 첫 번째 인덱스에만 의존적입니다. 이걸 구현할 수 있어야 합니다!

한 가지 묘수를 생각해봅시다.

우리는 현재 정답이 어디있는지를 알고 있습니다. 그러면, 정답을 표시하는 것 외에도 정답 인덱스에만 값을 할당하는 것이 가능합니다.

예를 들어, 정답을 표시한 $y$가 $y=\begin{bmatrix} 1&0&2\end{bmatrix}^T$라고 합시다.

그러면, 우리는 순수하게 $y$를 사용하는 것이 아니라, $$\hat{y}=\begin{bmatrix} 0&1&0\\1&0&0\\0&0&1\end{bmatrix}$$를 만들어서 사용하자는 것입니다.

이렇게 되면, 총 $N$개의 Train set에 대해 표시할 수 있는 Class의 개수가 $C$개 있으므로 총 $N\times C$ 크기의 Matrix를 가지게 됩니다. 이렇게 만들어진 행렬을 편의상 $\hat{y}$라고 하겠습니다.

이제, 우리가 들고 있는 score 행렬에 이 $\hat{y}$를 Hadamard product를 하게 되면 정답만이 남아있게 되고, 그렇지 않은 것들은 전부 $0$으로 바뀌게 됩니다.

하지만, 우리가 최종적으로 원하는 꼴은 이게 아니죠. 결국은 우리는 행렬의 각 행이 전부 정답으로만 도배가 되어 있어야 합니다.

예를 좀 들면, 현재 상황은 $$\begin{bmatrix} 0&3&0\\-0.7&0&0\\0&0&0.4\end{bmatrix}$$뭐 이런 상황인 것이구요, 우리가 필요한 행렬은 $$\begin{bmatrix} 3&3&3\\-0.7&-0.7&-0.7\\0.4&0.4&0.4\end{bmatrix}$$ 이것입니다.

이걸 만들기 위해서, $N\times 1$의 벡터로 만들고 이걸 다시 $N\times C$로 확장한다는 느낌으로 갑시다.

이때, $N\times 1$을 만들 땐 각 행의 합이 필요합니다. 이건 앞에서도 많이 사용했다시피 모든 항의 값이 $1$인 벡터를 사용하면 가능합니다. 이런게 가로로 $C$개 있으면, $N\times C$의 행렬을 만들 수 있겠죠.

즉, 우리는 $\hat{y}$에 모든 항이 $1$인 $N\times C$ 크기의 행렬을 우측에 곱해주면 됩니다.

이후, $\delta$ 값을 더하고, 정답 라벨의 Score을 $0$으로 만든 후, max operation을 거쳐주면 되는 것이죠.

이걸 코드로 구현한 것은 다음과 같습니다.

Implement of Forward Pass (Using vectorization)

def ForwardPass(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
    """
    loss = 0.0
 
    #############################################################################
    # 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)*****
 
    N = X.shape[0]
    C = W.shape[1]
    ones = np.ones((C, C))
    tp = np.arange(N)
    score = X@W
    ans = np.zeros_like(score)
    ans[tp, y] = 1
    score = score - (score * ans)@ones + 1
    score[tp, y] = 0
    score[score <= 0] = 0
    loss += np.sum(score) / N
    loss += reg * np.sum(W * W)
 
    return loss

Backpropagation (Using vectorization)

자, Forward Pass를 깔끔하게 마무리했으므로 Backpropagation도 생각보다 쉽게 할 수 있습니다!

현재, Loss가 계산되는 과정을 좀 적어보자면 $$\mathcal{L}=\dfrac{1}{N}\sum_i\sum_j \max(0,\,score)_{ij} + \lambda \Vert W\Vert _2^2$$

입니다. $score$ 행렬은 $XW-(XW\odot \hat{y})\cdot \mathbf{1}_{(C,\,C)}+1$로, $N\times C$의 크기를 가지고 있습니다.

앞에서도 말했다시피 $\sum_i \sum_j \max(0,\,score)_{ij}$는 $\mathbf{1} \max(0,\,score) \mathbf{1}$로 적을 수 있고, Trace trick을 활용하여 넘겨주면 모든 항이 $1/N$인 $N\times C$ 행렬이 필요한 것 뿐입니다.

다음은 $\max$를 처리해야합니다. 이때, max operation이 element-wise하게 이루어지므로 앞의 Matrix differentation rule에 의해 $d\sigma(X)=\sigma'(X)\odot dX$가 성립하게 됩니다. 이때, $\max$의 Gradient(혹은 derivation)은 $0$보다 크면 $1$, 그렇지 않으면 $0$을 뿜어내므로 우리는 값을 들고 있는 행렬이 필요합니다.

정말 다행히도 이 행렬은 score 행렬이 됩니다. 즉, 우리는 score 행렬을 보면서 $0$보다 큰 값을 가지고 있는 애들은 $1$을, 그렇지 않으면 $0$을 나타내게 행렬의 값을 바꿀 것입니다. 이 부분에서 Boolean indexing이 들어가게 됩니다.

이 행렬을 $grad_{max}$라고 칭하겠습니다.

그러면, 현재 상황을 Trace trick을 통해 나타내면 $$d\mathcal{L}=\langle grad_{max},\,d(score)\rangle$$입니다.

OK, 여기까지 왔으면 거의 끝났습니다.

score에 대한 Total derivate를 계산할 때 상수는 의미없으므로 날리고, 빼기로 연결되어 있으므로 각각 따로 계산합시다.

먼저, $\langle grad_{max}, \,d(XW)\rangle$ 부터 하죠. 굉장히 쉽게 계산이 됩니다. $X$와 $W$는 independent하므로, $d(XW)=XdW$입니다. 따라서, $\langle grad_{max},\,d(XW)\rangle=\langle X^T\cdot grad_{max},dW\rangle$입니다.

이제 뒷쪽을 처리하도록 하죠. $\langle grad_{max},\,d\left\{(XW\odot\hat{y})\cdot \mathbf{1}_{(C,\,C)}\right\}\rangle$에서 뒷쪽의 $C\times C$ 크기의 $\mathbf{1}$ 행렬을 먼저 곱한 후, element-wise operation을 좌측으로 옮깁시다. 마지막으로 직전에 했던 과정을 똑같이 거칩시다.

그러면, $$\begin{aligned}\langle grad_{max},\,d\left\{(XW\odot\hat{y})\cdot\mathbf{1}_{(C,\,C)}\right\}\rangle&=\langle grad_{max}\cdot\mathbf{1}_{(C,\,C)},\,d(XW\odot\hat{y})\rangle\\&=\langle (grad_{max}\cdot\mathbf{1}_{(C,\,C)})\odot \hat{y},\,d(XW)\rangle\\&=\langle X^T\cdot ((grad_{max}\cdot\mathbf{1}_{(C,\,C)})\odot\hat{y}),\,dW\rangle\end{aligned}$$

입니다.

마지막으로, Regularization에 대한 Term만 고려해줍시다. 동일하게 $\mathbf{1} f(W)\mathbf{1}$이므로, $N\times D$ 크기의 모든 항이 $reg$인 행렬을 만든 후, $f'(W)=2W$이므로 이걸 Hadamard product 진행해주면 끝입니다.

즉, Regularization에 대한 gradient는 $2\times reg\odot W$가 되고, $reg$는 $N\times D$의 행렬입니다.

앞의 내용을 코드로 나타내면 다음과 같습니다.

def Backprop(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
 
    #############################################################################
    # 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)*****
    score_grad = np.copy(score)
    score_grad[score_grad > 0] = 1
    grad_max = score_grad / N
    dW = X.T @ grad_max - X.T @ ((grad_max@ones)*ans)
    dW += 2 * reg * W
 
    # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
 
    return dW

Outroduction

사실 선형대수 배워봤자 쓰잘데기 없다고 생각했는데, Trace trick 하나 알아두니까 Backprop 계산이 진짜 편하네요

행렬곱 같은것도 표현 좋고

기회될 때 선형대수 관련해서 업로드 좀 하겠습니다.

이번학기에 선형대수 들었는데, 사실 귀찮아서 안올리고 있었는데 배운 내용 함 정리할게요