(cs231n) Assignment 1

첫번째 과제는 KNN을 구현하는 것이다.

 

KNN은 train과 test 두가지로 구분할 수 있다.

train 과정에서는 단순히 모든 이미지들을 기억한다.

이후 test 단계에서는 새로들어온 이미지를 기억한 모든 이미지들을 비교하가면서 distance(픽셀간 거리차)가 가장 작은 

이미지를 출력하는 방식으로 동작한다.

허나, 이 방식은 매우 비효율적이므로 쓰이지 않는다.

단순해서 구현하기 쉽지만 훈련이 오래걸리고 인퍼런스는 짧아야하는데 그 반대이며, 예측 성능도 별로여서 쓰이지 않는다.

 

우선 과제에서 제시하는 train이 어떻게 동작하는지 살펴본다.

 

train

    def train(self, X, y):
        """
        Train the classifier. For k-nearest neighbors this is just
        memorizing the training data.

        Inputs:
        - X: A numpy array of shape (num_train, D) containing the training data
          consisting of num_train samples each of dimension D.
        - y: A numpy array of shape (N,) containing the training labels, where
             y[i] is the label for X[i].
        """
        self.X_train = X
        self.y_train = y

X는 이미지의 전체 픽셀 값, y는 정답 레이블로 구성된 numpy 배열 형식의 파라미터가 들어온다.

x 값은 각 이미지 별 픽셀 정보가 담겨 있다. 2차원 배열이며, x = [[233,123,5,234...], [123,123,52,...]]... 이런식으로 배열이 구성되어 있으며 각 원소는 n번째 이미지를 의미한다. 

self.X_train, y_train에 해당 값을 저장한다.

즉 train은 그냥 간단하게 값을 복사하는 것에 불과한 것이다.

 

이제 compute_distances_two_loops함수를 구현한다.

def compute_distances_two_loops(self, X):
        """
        Compute the distance between each test point in X and each training point
        in self.X_train using a nested loop over both the training data and the
        test data.

        Inputs:
        - X: A numpy array of shape (num_test, D) containing test data.

        Returns:
        - dists: A numpy array of shape (num_test, num_train) where dists[i, j]
          is the Euclidean distance between the ith test point and the jth training
          point.
        """
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))
        for i in range(num_test):
            for j in range(num_train):
                #####################################################################
                # TODO:                                                             #
                # Compute the l2 distance between the ith test point and the jth    #
                # training point, and store the result in dists[i, j]. You should   #
                # not use a loop over dimension, nor use np.linalg.norm().          #
                #####################################################################
                # *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
                diff = X[i] - self.X_train[j]
                distance = np.sqrt(np.sum(diff**2))
                dists[i,j] = distance
                # *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
        return dists

L2 거리는 (x1-y1)^2 + (x2-y2)^2 ... 즉 차이의 제곱 형태로 구할 수 있으며 그렇게 구한 각 픽셀값들을 전부 더한 것이 L2 거리이다.

 

해당 함수를 잘 구현하면 밑의 코드 블럭에서 거리를 시각화해서 볼 수 있다. y축은 test 이미지를 x축은 train 이미지를 의미하며 색상이 흰색일수록 거리가 가깝다 (즉 이미지가 유사하다)를 알 수 있다.

 

이어서 k 값에 따른 레이블 예측 코드 구현은 다음과 같다.

    def predict_labels(self, dists, k=1):
        num_test = dists.shape[0]
        y_pred = np.zeros(num_test)
        for i in range(num_test):
            closest_y = []
            indices = np.argsort(dists[i])
            closest_y = self.y_train[indices[:k]]
            y_pred[i] = np.argmax(np.bincount(closest_y))

        return y_pred

distance가 2차원 배열이고 각 배열은 test 이미지의 순서대로 들어있기 때문에

반복문을 사용하여 distance와 k 값에 따라 예측할 label을 구한다.

우선 구한 distance을 오름차순 순서대로 정렬하고 k개의 이웃만큼 indices에 저장한다.

이후 해당 indices의 정답  label을 구한후 y_pred[i]에서 np.bincount 즉 가장 많이 등장한 레이블을 

정답 레이블로 지정한다.

 

이후 테스트 이미지의 숫자 만큼 반복하여 모든 예측 레이블을 구한후 y_pred를 리턴한다

 

compute_distance_oneloop 구현

이 부분은 distance을 구할떄 이전처럼 twoloop을 사용하지 않고 하나의 반복문으로만 구현하면 된다.

이는 numpy의 broadcast로 구현할 수 있다.

braodcast는 배열들을 계산할때 하나가 아닌 전체 배열에 값이 적용되는 것을 의미한다.

    def compute_distances_one_loop(self, X):
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))
        
        for i in range(num_test):
            squared_diff = (X[i, :] - self.X_train) ** 2  # (N, D)
            dists[i, :] = np.sqrt(np.sum(squared_diff, axis=1))
            
        return dists

 

compute_distance_noloop 구현

반복문 없이 거리를 구하는 코드이다.

L2 공식을 전개 (x-y)^2를 전개후 브로드 캐스트 방식으로 구하면 된다.

   def compute_distances_no_loops(self, X):
        num_test = X.shape[0]
        num_train = self.X_train.shape[0]
        dists = np.zeros((num_test, num_train))

        test_square = np.sum(X**2, axis=1).reshape(-1,1)
        train_square = np.sum(self.X_train**2, axis=1)
        cross_term = -2 * np.dot(X, self.X_train.T) 
        dists = np.sqrt(cross_term + test_square + train_square)

        return dists

 

cross validation의 구현

num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]

X_train_folds = []
y_train_folds = []
X_train_folds = np.array_split(X_train, num_folds)
y_train_folds = np.array_split(y_train, num_folds)



k_to_accuracies = {}
for k in k_choices:
    k_to_accuracies[k] = []  # k에 대한 accuracy 리스트 초기화
    
    # 각 fold를 한 번씩 validation set으로 사용
    for fold in range(num_folds):
        # validation fold를 제외한 모든 fold를 training data로 사용
        X_train_cv = np.concatenate(X_train_folds[:fold] + X_train_folds[fold+1:])
        y_train_cv = np.concatenate(y_train_folds[:fold] + y_train_folds[fold+1:])
        
        # 현재 fold를 validation data로 사용
        X_valid = X_train_folds[fold]
        y_valid = y_train_folds[fold]
        
        # KNN 분류기 학습 및 예측
        classifier = KNearestNeighbor()
        classifier.train(X_train_cv, y_train_cv)
        y_pred = classifier.predict(X_valid, k=k)
        
        # 정확도 계산 및 저장
        num_correct = np.sum(y_pred == y_valid)
        accuracy = float(num_correct) / len(y_valid)
        k_to_accuracies[k].append(accuracy)


# Print out the computed accuracies
for k in sorted(k_to_accuracies):
    for accuracy in k_to_accuracies[k]:
        print('k = %d, accuracy = %f' % (k, accuracy))

교차 검증은 훈련 데이터 셋을 나누어서 교차로 검증하는 것을 의미한다.

즉 훈련 데이터셋을 5개로 나누었다면

[1,2,3,4] 데이터를 훈련하고 5번째 데이터는 검증 데이터로 활용한다.

이후 반복문에서는

[1.2.3,5]를 훈련데이터로 활용하고 4번째 데이터는 검증 데이터로 활용하게 된다.

이렇게 5번 반복한후 평균을 내어 전체적인 성능을 검증하는 것이 교차 검증이다.