4. First Classifier: k Nearest Neighbor

2022. 3. 16. 17:17

kNN

첫 번째, Image Classification에 대한 시도는, Nearest Neighbor Classifier이다.

이 분류기는 real-world에서는 거의 쓰이지 않지만,

basic approach로서는 충분히 발전 가능한 아이디어를 제시하기에 중요하다.

def train(images, labels):
	# kNN
    # Memorize all data and labels
    return model

def predict(model, test_images):
	# Predict the label of the most similar training image
    return test_labels

본격적으로 kNN설명에 들어가기에 앞서, 사용할 data와 metric에 대해서 알아보자.

1. CIFAR-10

CIFAR-10은 10개의 class label에 대해서 image를 분류하는 task의 data를 제공한다.

2. Distance Metric

"How to compare two images and get its similar or not?"
"How semantically similar?"

Metric은 Image Classification에 대한 실질적 방법론을 말한다.

두 개의 Image가 있다면, 두 Image가 얼마나 유사한가?, 에 대한 수치적 답을 찾기 위한 방법으로 kNN은 Distance Metric을 사용한다.

위 식은 L1 distance metric이다. 두 개의 image에 대한 유사도를 pixel-wise(각 pixel별로)하게 뺀 값의 절댓값의 합을 구함으로써 계산한다. 이렇게 구한 두 image 간의 L1 거리가 작을수록 두 image는 유사하다고 할 수 있다.

하지만 결과는 아쉽게도 classification task를 잘 수행하지 못한다.

kNN Image Classification Result with CIFAR-10

단순 pixel value에 대한 거리를 계산하기 때문에, 전혀 다른 object class라도 색이나 모양이 유사하면, 두 image가 similar 하다고 classify 해버리는 문제가 발생하는 것이다.

하지만, kNN의 성능을 조금이라도 더 높이기 위한 tuning방법이 있다.

바로 hyper-parameter인 k값과 distance metrics(L1, L2)를 image data에 맞게 조정하여,

최적의 parameter를 찾는 방법이다!

Hyper-Parameter

Hyper-Parameter란, training data로부터 학습하는 parameter가 아니라, 개발자(사용자)가 model learning 시작 전 "본인의 선택"으로 setting 하는 parameter를 뜻한다. Hyper-Parameter는 problem-dependent(data의 특성과 매우 직결되어 있다)하고, 미리 알 수 없기 때문에 (generally) 모든 경우를 시도해 보는 방법밖에 없다.

최적의 Hyper-Parameter를 찾는 방법은 데이터를 세분화하는 것이다.

그리고 Idea #3의 효율성을 극대화 한 방법이 바로, Cross-Validation이다. 다만, 이는 small dataset에서만 사용되고 deep learning과 같이 방대한 data를 다루는 모델에는 잘 사용되지 않는다.

전체 데이터를 train/test로 나눈 후, test dataset에 대해서는 절대 학습이나 hyper-parameter tuning에 사용해서는 안된다. 이는 흔히 말하는 overfit을 유발하여, test dataset에만 맞춰진 parameter를 학습하게 되기 때문에 model을 real-world에 적용하여 완전히 새로운 dataset에 적용하였을 때, 성능이 떨어질 수밖에 없다.

Test dataset은 완전히 새로운 data에 대한 generalization에 대한 성능 지표를 제공하는 중요한 dataset이다. 따라서 우리는 train dataset을 다시, train과 valid dataset으로 나누고, validation set을 학습 도중 hyper-parameter tuning에 사용한다. 그렇다면, test dataset은 model이 전혀 보지 않은 data로 남겨놓을 수 있게 되며, 이를 통해 generalization 성능을 확인할 수 있는 것이다.

그렇다면 이제, kNN의 가장 중요한 Hyper-Parameter인 distance-metrics와 k값의 최적 경우를 구해보자.

1. Distance-Metric

vector들 간의 거리를 계산하는 metric은 여러 가지가 있다. 다만 대표적으로 쓰이는 것은 L1, L2 distance metric으로, 위에서 사용한 L1의 성능이 만족스럽지 않다면 L2를 사용해 보는 방법이 있다. L2는 euclidean distance로 두 vector사이의 거리를 geometric 하게 해석한다.

Different decision boundary is made by L1, L2 distance metirc&nbsp;

2. k-value for Nearest Neighbor

Different k-value of Nearest Neighbor model

NN모델의 또 다른 중요 Hyper-Parameter인 k-value는, 근처 몇 개의 neighbor를 보고 class label을 판단할 것인가를 결정하는 역할을 한다. 이에, k=1일 때는 outlier(이상치)에 영향을 많이 받아 deicison boundary가 매우 산만하게 나누어졌던 반면, k의 값을 크게 할수록 decision boundary는 smoothing 되고, outlier에 영향을 적게 받는 것을 볼 수 있다.

Dot Point: train dataset으로, 각 color마다 class label이 다르다
Back-Ground: train dataset으로 결정된 class label의 영역으로, X-point의 test data가 특정 back-ground color 안에 놓이면 label이 assign 된다.
Decision Boundary: black line으로 각 class label 영역을 구분 짓는 boundary를 뜻한다.

k-value를 1보다 높이면, kNN모델의 deicison boundary에도 변화가 일어난다.

Majority Vote: k closest point로부터 voting을 하여 test의 class label을 결정한다.
Decision-Boundary가 smoothing 되면서, outlier의 영향을 덜 받게 된다.
흰 부분으로 생기는, tie region(두 영역의 확률이 1:1)이 존재하게 된다.
train data에 대해서는 error(틀린 영역)가 증가할 수 있으나, test data에 대한 generalization(일반화 능력)은 향상한다.

Evaluation Metric
흔히, Image Classificatoin에 대한 성능 평가 지표로 accuracy를 많이 사용한다.
이는 우리가 이미 알고 있는 ground truth의 정답 label과 model이 predict 한 예측 label이 얼마나 일치하는가에 대한 정확도를 나타낸다.
* Accuracy = (model이 정확히 예측한 label의 개수: ground truth == predict label) / 전체 label 개수

Code Implementation

이제 본격적으로 kNN에 대한 Code Implementation을 해보도록 하겠다.

(본 code는 EECS498 강좌의 Assignment1-2의 kNN.ipynb source이다.)

1. L2 Distance Metric

def compute_distance_two_loops(x_train, x_test):
    num_train = x_train.shape[0]
    num_test = x_test.shape[0]
    dists = x_train.new_zeros(num_train, num_test)
    
    for i in range(num_test):
    	for j in range(num_train):
        	dists[i, j] = torch.sum(torch.square(torch.subtract(x_train[j], x_test[i])))**(1/2)
    
    return dists

L2 distance metric을 2 for-loop을 사용하여 구현한 것이다.

for-loop을 두 번이나 돌기 때문에, num_test, num_train의 값이 커질 경우, 계산 시간 또한 급격히 증가할 것이고, 그만큼 모델의 효율성도 떨어질 것이다.

def compute_distances_one_loop(x_train, x_test):
    num_train = x_train.shape[0]
    num_test = x_test.shape[0]
    dists = x_train.new_zeros(num_train, num_test)
    
    for i in range(num_train):
    	dists[i,:] = torch.sum(torch.square(torch.sub(x_test,x_train[i])), dim=(1,2,3))**(1/2) 
    
    return dists

보다 효율적인 1 for-loop으로 구현한 코드이다.

아예 for-loop을 없앨 수는 없을까?

def compute_distances_no_loops(x_train, x_test):
    num_train = x_train.shape[0]
    num_test = x_test.shape[0]
    dists = x_train.new_zeros(num_train, num_test)
    
    A = x_train.reshape(num_train,-1)
    B = x_test.reshape(num_test,-1)
    AB2 = A.mm(B.T)*2
    dists = ((A**2).sum(dim = 1).reshape(-1,1) - AB2 + (B**2).sum(dim = 1).reshape(1,-1))**(1/2)
    
    return dists

시간적 효율성을 test 해보자.

import time

def timeit(f, *args):
    tic = time.time()
    f(*args) 
    toc = time.time()
    return toc - tic

torch.manual_seed(0)
x_train_rand = torch.randn(500, 3, 32, 32)
x_test_rand = torch.randn(500, 3, 32, 32)

two_loop_time = timeit(compute_distances_two_loops, x_train_rand, x_test_rand)
print('Two loop version took %.2f seconds' % two_loop_time)

one_loop_time = timeit(compute_distances_one_loop, x_train_rand, x_test_rand)
speedup = two_loop_time / one_loop_time
print('One loop version took %.2f seconds (%.1fX speedup)'
      % (one_loop_time, speedup))

no_loop_time = timeit(compute_distances_no_loops, x_train_rand, x_test_rand)
speedup = two_loop_time / no_loop_time
print('No loop version took %.2f seconds (%.1fX speedup)'
      % (no_loop_time, speedup))

효율성이 for-loop이 없을 때, 기하급수적으로 증가하였다.

2. Predict labels

def predict_labels(dists, y_train, k=1):
    num_train, num_test = dists.shape
    y_pred = torch.zeros(num_test, dtype=torch.int64)
  
    values, indices = torch.topk(dists, k, dim=0, largest=False)
    for i in range(indices.shape[1]):
        _, idx = torch.max(y_train[indices[:,i]].bincount(), dim = 0)
        y_pred[i] = idx
    
  return y_pred

pytorch의 topk를 이용하여, k개의 smallest top과 그 index를 뽑는다.

그리고 majority voting을 위해 for-loop을 돌면서, y_train label의 개수를 counting(bincount)하여 max index=label을 return 한다.

그래서 최종 모델은 아래와 같다.

class KnnClassifier:
    def __init__(self, x_train, y_train):
        self.x_train = x_train.contiguous()
        self.y_train = y_train.contiguous()
  
    def predict(self, x_test, k=1):
        dists = compute_distances_no_loops(self.x_train, x_test.contiguous())
        y_test_pred = predict_labels(dists, self.y_train, k=k)
        
        return y_test_pred
  
    def check_accuracy(self, x_test, y_test, k=1, quiet=False):
        y_test_pred = self.predict(x_test, k=k)
        num_samples = x_test.shape[0]
        num_correct = (y_test == y_test_pred).sum().item()
        accuracy = 100.0 * num_correct / num_samples
        msg = (f'Got {num_correct} / {num_samples} correct; '
               f'accuracy is {accuracy:.2f}%')
        if not quiet:
            print(msg)
            
        return accuracy

그렇다면, 이제 최적의 k값을 찾기 위한 cross validation을 구현해보자.

def knn_cross_validate(x_train, y_train, num_folds=5, k_choices=None):
    if k_choices is None:
        # Use default values
        k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]

    x_train_folds = []
    y_train_folds = []
    
    x_train_folds = torch.chunk(x_train, num_folds, dim=0)
    y_train_folds = torch.chunk(y_train, num_folds, dim=0)

    k_to_accuracies = {}

    for k in k_choices:
        list_of_acc = []
        
        for num_fold in range(num_folds):
            x_train_folds_local = [x for x in x_train_folds]
            y_train_folds_local = [x for x in y_train_folds]
            
            x_test = x_train_folds_local[num_fold]
            y_test = y_train_folds_local[num_fold]
            
            del x_train_folds_local[num_fold]
            del y_train_folds_local[num_fold]
            
            x_train = torch.cat(x_train_folds_local, dim=0)
            y_train = torch.cat(y_train_folds_local, dim=0)
            
            classifier = KnnClassifier(x_train, y_train)
            list_of_acc.append(classifier.check_accuracy(x_test, y_test,k))
            
        k_to_accuracies[k] = list_of_acc
        
    return k_to_accuracies

먼저, k_choices를 통해 k값으로 적절할 만한 값들을 list로 만들어 준다.

다음으로 torch.chunk를 사용하여 data를 fold 개수로 나누어 준다.

그 후, k_choices의 개수만큼의 큰 for-loop 안에서, fold 개수만큼의 작은 for-loop으로 cross-validation이 이루어진다.

train dataset에서 validation fold를 빼는 방법은,

전체 fold들을 list형태로 만들어 준 뒤 이를 train set으로 우선 정의한다.

다음으로 test fold를 따로 선언하고, 이 test fold를 train set에서 delete 해준 다음 torch.cat으로 이어 붙여 주는 것이다.

최종적으로 우리는 best k value를 얻을 수 있다.

kNN은 Universal Approximation이다.
training sample이 infinity로 증가할수록, NN모델은 any(*) function representation이 가능하다!
kNN Function Approximation via training sample increasing

(*) Subject to mathematical conditon. Only continuous functions on a compact domain; need to make assumption about spacing of training points

Curse of Dimensionality
Uniform coverage of space를 위해서는, 필요한 training point의 수가 기하급수적으로 늘어난다.
Needed training sample increase exponentially

장단점

마지막으로 kNN의 장단점을 정리하면서 마치도록 하자.

[장점]

Implementation과 이해가 매우 쉽다.
Training에 시간이 걸리지 않는다 (단순히, 데이터 전부를 memory에 assign 하여 기억하기 때문).

[단점]

Test Prediction에 시간이 오래 걸린다 (기억하고 있는 모든 train data와 similarity를 비교해야 하기 때문).
- 보통, train에 걸리는 시간보다는, test에 걸리는 시간이 실전에서는 더욱 비효율적이기 때문에 이는 치명적 단점이다.
- 그래서 앞으로 배울 deep learning은 이에 대한 trade-off가 일어나, training에 오랜 시간이 걸리지만, test에는 거의 시간이 걸리지 않는다.
Practical Image Classification에서는 사용할 수가 없다.
- L2 distance가 raw pixel value의 similarity를 아래 사진 모두 같은 값으로 내뱉기 때문에 semantic 한 구분이 되지 않는다.

L2 distance가 image 내의 object에 대한 semantic class differnece보다는 background에 영향을 많이 받는다.
- 아래의 t-SNE (image embedding) 결과를 보면, L2 distance로 유사하다고 보는(서로 인접해 있는) 이미지가 배경 색이 비슷한 경우가 많다.

kNN은 Image Classification의 아주 기초적인 idea이기 때문에 장단점이 극명하나,

분명한 점은 Image Classification을 pixel-wise로 distance metric을 통해 similarity를 구하려 했다는 idea는 훌륭하다고 볼 수 있다.

'Image > Basic' 카테고리의 다른 글

3. Image Classification - Introduction (0)	2022.03.16
2. Deep Learning for Computer Vision & it's History (0)	2022.03.15
1. What is Computer Vision? (0)	2022.03.13

인공지능 브로커