[EECS 498] Assignment 2. Linear Classifier...(1)

본 포스팅은 Michigan Univ.의 EECS 498 강의를 수강하면서 공부한 내용을 정리하는 포스팅입니다.

---

https://jinwoo-jung.tistory.com/123

[EECS 498] Assignment 1. k-NN...(2)

---

Introduction

본 과제는 CIFAR-10 Dataset을 기반으로 Linear Classifier를 구현하고 테스트하는 과제이다.

 

지난 k-NN에서 사용한 동일한 데이터지만, 본 과제에서는 Bias Trick을 사용해 Bias를 Weight Matrix에 포함하여 다루기 위해, Input Data의 가장 마지막에 상수 1을 추가하고, Weight Matrix 마지막에는 Bias를 추가한다. 이를 통해 Bias Vector를 추가적으로 다루지 않아도 된다.

 

# Invoke the above function to get our data. 
import eecs598

eecs598.reset_seed(0)
data_dict = eecs598.data.preprocess_cifar10(bias_trick=True, cuda=True, dtype=torch.float64)
print('Train data shape: ', data_dict['X_train'].shape)
print('Train labels shape: ', data_dict['y_train'].shape)
print('Validation data shape: ', data_dict['X_val'].shape)
print('Validation labels shape: ', data_dict['y_val'].shape)
print('Test data shape: ', data_dict['X_test'].shape)
print('Test labels shape: ', data_dict['y_test'].shape)
print('Last Data of Input: ', data_dict['X_train'][0][-1])

 

데이터를 Dictionary 형태로 가져온다. 

 

각 클래스에 대한 Input Data를 확인 해 보면 다음과 같다. 실제로 32x32x3의 Shape를 가지는 Input 영상이 Flatten 된 형태로 저장되어 있으며, 마지막 값은 상수 1임을 확인할 수 있다.

 

SVM Classifier

 먼저 SVM Loss에 대해서 간단히 복습 해 보면 다음과 같이 정의할 수 있다.

$$ L_i = \sum_{j \neq y_i} max \left ( 0, s_j - s_{y_i} + 1 \right )$$

이때, $s_j = X[i]W[:,j], s_(y_i) = X[i]W[:,y_i]$이다. 따라서 Loss에 대한 Gradient는 다음과 같다.

$$\frac{\partial  L}{\partial W[:j]} = \frac{\partial  s_j}{\partial W[:j]}  \frac{\partial  L}{\partial s_j} = X[i]$$

$$\frac{\partial  L}{\partial W[:y_i]} = \frac{\partial s_{y_i}}{\partial W[:y_i]} \frac{\partial L}{\partial s_{y_i}} = -X[i]$$

 

• Naive SVM Loss

def svm_loss_naive(
    W: torch.Tensor, X: torch.Tensor, y: torch.Tensor, reg: float
):

    dW = torch.zeros_like(W)  # 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 = W.t().mv(X[i])
        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
            
            # 정답 클래스의 점수와 정답이 아닌 클래스 점수와의 차이가 margin보다 큰 경우
            if margin > 0:
                loss += margin

                # Gradient of SVM Loss
                dW[:,j] += X[i]
                dW[:,y[i]] -= X[i]

    # Average Loss
    loss /= num_train
    # Regularization Term
    loss += reg * torch.sum(W * W)

    # Average Gradient
    dW /= num_train
    # Regularization Term
    dW += 2*reg*W

    return loss, dW

 

Naive 방법은 Loop를 돌면서 Margin $s_(y_i) > s_j+1$인 경우를 찾아 Loss와 Gradient를 계산한다.

 

이때, Score는 Input X와 Weight Matrix의 Matrix Vector Multiply를 통해 계산할 수 있다. $s_(y_i) > s_j+1$인 경우에만 Loss가 0이 아니므로, 누적 Loss를 계산하기 위해 $s_(y_i) > s_j+1$(코드 상 margin)을 더해주며, 그때의 Gradient를 계산하게 된다. 앞서 계산한 수식에 근거하여 각각의 Gradient를 dW에 누적 합 한다.

 

수식 상 최종적인 Loss는 다음과 같다.

 

따라서 loss를 num_train으로 나눠주고, Regularization Term을 더해줌으로써 최종적은 Loss를 계산할 수 있다. 또한, dW 계산 시 $\frac{1}{N}$을 고려하지 않았기에 num_train으로 나눈 뒤, Regularization Term의 미분($2\lambda W$)를 더해준다.

참고로 현재 Regularizatoin은 L2 Regularizatoin이다.

 

실제로 구현한 Gradient 계산 과정이 정확한지 확인하기 위해 Numerical Gradient Check(수치적 그래디언트 검사)를 수행한다.

import eecs598
from linear_classifier import svm_loss_naive

eecs598.reset_seed(0)
W = 0.0001 * torch.randn(3073, 10, dtype=data_dict['X_val'].dtype, device=data_dict['X_val'].device)
batch_size = 64
X_batch = data_dict['X_val'][:batch_size]
y_batch = data_dict['y_val'][:batch_size]

_, grad = svm_loss_naive(W, X_batch, y_batch, reg=0.0)

f = lambda w: svm_loss_naive(w, X_batch, y_batch, reg=0.0)[0]
grad_numerical = eecs598.grad.grad_check_sparse(f, W, grad)

 

Weght Matrix W를 아주 작은 난수 값으로 초기화 한 뒤, Mini Batch에 대하여 reg = 0.0으로 하여 Gradient를 계산한다. 이는 Regularization Term의 영향을 없앰으로써 데이터에 대한 Loss에 의한 Gradient 계산을 확인할 수 있다.

 

이후 Lamda Function $f$를 정의하는데, 이는 Loss 값 만 받아온다. 이후 grad_check_sparse Method를 통해 유한 차분 방법을 이용하여 Gradient를 계산하고, 이를 svm_loss_naive를 통해 계산한 grad와 비교하여 Error를 계산한다. 이때, 유한 차분 방법은 미분을 아래와 같이 근사한 방법이다.

 

현재 Error는 1e-5보다 작은 매우 작은 값이기에, Analytic Gradient 계산이 잘 진행됨을 확인할 수 있다.

 

 

• Vectorized SVM Loss

Naive와 동일한 Input, Output을 가지지만, 명시적인 Loop 없이 SVM Loss를 계산 해 보자.

 

def svm_loss_vectorized(
    W: torch.Tensor, X: torch.Tensor, y: torch.Tensor, reg: float
):

    loss = 0.0
    dW = torch.zeros_like(W)  # initialize the gradient as zero

    scores = X.mm(W)  # NxC   : Input_i의 Class_j에 대한 Score
    
    idx0 = torch.arange(0,X.shape[0])
    correct_scores = scores[idx0, y].view(-1,1)   # Cx1 : 정답 클래스에 해당되는 Score

    margin = scores - correct_scores + 1

    margin[idx0, y] = 0   # j==y_i인 경우는 고려 x

    mask = (margin > 0)
    loss = margin[mask].sum()

    # N으로 나눠주고 Regularization Term 고려
    loss = loss.sum() / X.shape[0] + reg * torch.sum(W*W)  
    
    # 정답 cls에 대한 Weight의 경우 margin>0일 때 계속 X[i]를 빼줘야함 => 누적
    mask_correct_cls = torch.zeros_like(scores, dtype = torch.bool)
    mask_correct_cls[idx0, y] = True  

    margin[margin>0] = 1
    margin[margin<0] = 0

    margin[mask_correct_cls] = torch.sum(margin, axis = 1)*-1

    dW = margin.T.mm(X).T

    # N으로 나눠주고 Regularization Term 고려
    dW = dW / X.shape[0] + 2*reg*W

    return loss, dW

 

Broadcasting 및 Vectorization을 위해 많이 생각하고 그려봐야 한다.

 

scores = X.mm(W)  # NxC   : Input_i의 Class_j에 대한 Score

idx0 = torch.arange(0,X.shape[0])
correct_scores = scores[idx0, y].view(-1,1)   # Cx1 : 정답 클래스에 해당되는 Score

margin = scores - correct_scores + 1

margin[idx0, y] = 0   # j==y_i인 경우는 고려 x

mask = (margin > 0)
loss = margin[mask].sum()

# N으로 나눠주고 Regularization Term 고려
loss = loss.sum() / X.shape[0] + reg * torch.sum(W*W)

 

Loss를 계산하는 경우 $Input_i$의 $Class_j$에 대한 Score를 먼저 계산한다. 결국 SVM Loss를 위해서는 $s_(y_i) > s_j + 1$인 경우를 찾아 0으로 만들어야 하므로, Broadcasting을 위해 각 Input의 정답 Class에 대한 score를 correct_scores로 가져온다.

 

현재 Margin이 1이므로, scores에서 정답 클래스의 점수(correct_scores)를 빼고 margin(1)을 더한 margin을 계산한다. SVM Loss의 경우 $j \neq y_i$ 즉, 정답 클래스에 대한 경우는 제외하기 때문에 각 Input Data의 정답 클래스의 경우 margin을 0으로 설정한다.

 

margin이 0보다 큰 경우에만 Average Loss, Average Gradient를 계산하면 되기 때문에, mask를 생성하여 Loss가 0보다 큰 경우의 Loss만 골라 평균을 계산한 뒤, Regularization Term을 고려하였다. 

 

# 정답 cls에 대한 Weight의 경우 margin>0일 때 계속 X[i]를 빼줘야함 => 누적
mask_correct_cls = torch.zeros_like(scores, dtype = torch.bool)
mask_correct_cls[idx0, y] = True  

margin[margin>0] = 1
margin[margin<0] = 0

margin[mask_correct_cls] = torch.sum(margin, axis = 1)*-1

dW = margin.T.mm(X).T

# N으로 나눠주고 Regularization Term 고려
dW = dW / X.shape[0] + 2*reg*W

 

Gradient의 경우 앞서 계산한 margin이 양수인 경우에 대해서 $W[:j]$는 $X[i]$를 더해주고, $W[:y_i]$는 $X[i]$를 빼 줘야 한다. 우선 margin이 0보다 큰 경우 $W[:y_i]$의 Gradient를 위한 mask_correct_cls를 생성한다. 앞선 과정에서 정답 클래스에 대한 margin은 모두 0으로 만들어 놨기에, mask를 통해 해당 Index를 True로 생성한다. 

 

margin이 0보다 큰 경우 해당 인덱스 $j$에 대해선 $X[i]$를 더해야 하므로, 횟수를 Count 하기 위해 margin[margin>0]인 경우 1로 작으면 0으로 설정하였다. 이때, 정답 mask의 경우 margin이 0보다 클 때 마다 $W[:y_j]$에 대한 Grdient는 누적되기 때문에 torch.sum()을 통해 더해준다. 

 

이후 torch.mm을 통해 Input X와 margin의 Matrix Multiply를 진행하고, 평균을 구하고 Regularization Term을 고려한다.

 

• Train Linear Classifier

def train_linear_classifier(
    loss_func: Callable,
    W: torch.Tensor,
    X: torch.Tensor,
    y: torch.Tensor,
    learning_rate: float = 1e-3,
    reg: float = 1e-5,
    num_iters: int = 100,
    batch_size: int = 200,
    verbose: bool = False,
):
    """
    Train this linear classifier using stochastic gradient descent.

    Inputs:
    - loss_func: loss function to use when training. It should take W, X, y
      and reg as input, and output a tuple of (loss, dW)
    - W: A PyTorch tensor of shape (D, C) giving the initial weights of the
      classifier. If W is None then it will be initialized here.
    - X: A PyTorch tensor of shape (N, D) containing training data; there are N
      training samples each of dimension D.
    - y: A PyTorch tensor 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.

    Returns: A tuple of:
    - W: The final value of the weight matrix and the end of optimization
    - loss_history: A list of Python scalars giving the values of the loss at each
      training iteration.
    """
    # assume y takes values 0...K-1 where K is number of classes
    num_train, dim = X.shape
    if W is None:
        # lazily initialize W
        num_classes = torch.max(y) + 1
        W = 0.000001 * torch.randn(
            dim, num_classes, device=X.device, dtype=X.dtype
        )
    else:
        num_classes = W.shape[1]

    # Run stochastic gradient descent to optimize W
    loss_history = []
    for it in range(num_iters):
        # TODO: implement sample_batch function
        X_batch, y_batch = sample_batch(X, y, num_train, batch_size)

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

        # perform parameter update
        #########################################################################
        # TODO:                                                                 #
        # Update the weights using the gradient and the learning rate.          #
        #########################################################################
        W -= learning_rate * grad
        #########################################################################
        #                       END OF YOUR CODE                                #
        #########################################################################

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

    return W, loss_history

 

이제 Linear Classifier를 학습시켜 보자. 먼저 Weight Matrix를 작은 난수로 초기화 시킨 뒤, num_iters만큼 반복하면서 학습을 진행한다. SGD를 위해 입력받은 batch_size만큼의 batch를 무작위로 생성한다. 이렇게 생성된 X_batch는 (batch_size, X.shape[1])의 크기를 가진다. 이후 loss_func을 이용해 Loss와 Gradient를 계산한 뒤, Gradient Descent로 Weight Matrix를 Update 한다.

 

def sample_batch(
    X: torch.Tensor, y: torch.Tensor, num_train: int, batch_size: int
):
    """
    Sample batch_size elements from the training data and their
    corresponding labels to use in this round of gradient descent.
    """
    X_batch = None
    y_batch = None
    #########################################################################
    # TODO: 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 torch.randint to generate indices.                          #
    #########################################################################
   
    batch_idx = torch.randint(0, num_train, (batch_size,))  # batch idx 생성
    X_batch = X[batch_idx]
    y_batch = y[batch_idx]
    #########################################################################
    #                       END OF YOUR CODE                                #
    #########################################################################
    return X_batch, y_batch

 

SGD를 위한 Batch는 sample_batch를 통해 생성된다. torch.randint를 통해 0~num_train 범위 중 batch_size 개의 Random Index를 생성하여, 원본 학습 데이터 및 정답 레이블 중 일부를 X_batch, y_batch로 할당한다.

 

 

• Predict Class

def predict_linear_classifier(W: torch.Tensor, X: torch.Tensor):
    """
    Use the trained weights of this linear classifier to predict labels for
    data points.

    Inputs:
    - W: A PyTorch tensor of shape (D, C), containing weights of a model
    - X: A PyTorch tensor of shape (N, D) containing training data; there are N
      training samples each of dimension D.

    Returns:
    - y_pred: PyTorch int64 tensor of shape (N,) giving predicted labels for each
      elemment of X. Each element of y_pred should be between 0 and C - 1.
    """
    y_pred = torch.zeros(X.shape[0], dtype=torch.int64)
    ###########################################################################
    # TODO:                                                                   #
    # Implement this method. Store the predicted labels in y_pred.            #
    ###########################################################################
    scores = X.mm(W)
    y_pred = scores.argmax(axis = 1)
    ###########################################################################
    #                           END OF YOUR CODE                              #
    ###########################################################################
    return y_pred

 

Input X와 학습된 Weight Matrix W의 Matrix Multiply를 통해 Score를 계산하고, 각 행에 대하여 최댓값을 가지는 Index를 torch.argmax를 통해 구하면 Class를 예측할 수 있다.

 

 

실제로 정답 Class와 비교 해 보면 생각보다 Accuraacy가 낮음을 확인할 수 있다.