[Lec2] KNN, Linear Classifier

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

 

lec1에서 image classification 기술에 대한 전반적인 설명을 진행하였고, lec2에서도 이에 대한 내용을 다루지만, 해당 내용은 생략하고 KNN과 Linear Classifier에 대해서만 다루었다.

 

<KNN>

K - Nearest Neighbor 알고리즘은 새로운 대이터가 주어졌을 때, 해당 데이터와 가장 유사한(L1 또는 L2 distance가 가까운) train data의 label로 예측하는 알고리즘이다. 

 

여기서 K는 가장 유사한 데이터를 몇 개 확인할지 결정하는 파라미터이다. 예를 들어, K = 3인 경우 가장 유사한 train data 3개를 찾고 과반수인 label로 예측한다.

 

● L1, L2 distance

앞서 가장 유사한 train 데이터의 label을 확인하는 방식으로 동작한다고 했는데, 여기서 유사성이란 L1 또는 L2 distance를 의미한다.

L1 distance

먼저 L1 distance를 이미지에 적용하면 위와 같이 계산할 수 있다. pixel별 차의 절대값의 합을 계산하면 된다.

 

L2 distance

L2 distance도 크게 어렵지 않다. 각 픽셀 별로 차의 제곱의 합을 계산하면 된다.

 

● Train

KNN 모델을 train하는 것은 매우 간단하다. 단순히 train 데이터를 모두 저장하면 된다.

 

● Prediction

prediction 또한 간단하다. 저장된 모든 train 데이터와 비교하여 가장 유사한 k개의 train 데이터를 찾으면 된다.

KNN의 단점

다만 위와 같은 동작때문에 KNN은 매우 비효율적인 알고리즘이다.

 

일반적으로 train이 오래 걸리는 것은 크게 문제가 안되지만, 새로운 데이터에 대해서는 빠르게 예측이 가능해야 한다. 그러나 KNN은 그 반대로, prediction 시간이 train data의 수에 따라 결정된다. 

 

● 시각화

KNN 시각화

KNN 알고리즘을 시각화한 자료이다.

각각의 포인트가 train 데이터이고, 포인트의 색이 label이다. 

색으로 칠해진 영역은 해당 영역에 데이터가 있다고 가정하면, 어떤 label로 분류되는지 나타낸다고 이해하면 된다.

(흰색은 동점인 경우라고 한다.)

 

● Hyperparemeter

KNN에서 Hyperparameters는 다음과 같다.

 K 값과 어떤 타입의 distance(L1 or L2)를 사용할지 결정해줘야 한다.

 

train/validation/test data set

Hyperparemeters의 경우 전체 데이터를 train, validation, test로 나눠서 결정한다.

이는 KNN 뿐만 아니라 모든 머신러닝, AI 모델에 대해 적용이 가능하다.

train데이터를 통해 학습하고, validation set에 대해 좋은 성능을 보이는 hyperparameter를 결정하면 된다.

test set은 최종 모델의 성능을 파악하는데 사용된다. 

 

Cross Validation

위와 같은 cross validation 기법도 있다. 

 

● Performace

결론적으로, KNN은 이미지 데이터에 대해서 사용되지 않는다.

KNN의 단점

그 이유는 다음과 같다.

1. very slow (test data의 수에 의해 결정)

2. pixel간의 distance 는 많은 정보를 포함하지 않음.

 

1번 이유의 경우 앞서 설명했고, 2번의 경우 슬라이드의 그림을 통해 이해할 수 있다.

original 이미지 우측 3개의 이미지가 모두 같은 distance를 갖는다. 

 

※ 일종의 noize가 끼었음에도 불구하고 하나로 인식하니까 좋은게 아니냐는 질문이 있었다.

-> answer : 위 그림은 하나의 예시로, 실제 전혀 다른 형상이더라도 distance가 같을 수 있다.

 

 

<Linear Classification>

● 동작

하나의 Weight(행렬)을 통해 prediction을 수행하는 방법이다.

즉, input과 Weight의 선형식으로 prediction을 수행한다.

Linear Classifier

하나의 이미지에 대해서 Linear Classification을 진행하는 예시이다. 

32x32x3 크기의 이미지가 주어지면 3072(32*32*7) 크기의 vector로 만들어서 W와 곱한다.

Weight의 크기는 (input data의 크기 x class의 수)이다.

 

Wx의 결과는 10x1 벡터가 되고, 값이 가장 큰 class를 선택하면 된다.

Linear Classifiaction 예시

위 예시를 확인하며 더 쉽게 이해할 수 있다.

 

● 의미

학습된 Weight 출력 결과

위 이미지는 CIFAR-10 데이터에 대해 학습시킨 Weight를 출력해본 결과이다. 

 

각 label과 유사한 흐릿한 이미지를 확인할 수 있는데, 이것이 Linear Classifer의 동작을 직관적으로 잘 나타낸다.

 

잘 train 된다면 각 Weight는 일종의 템플릿으로, 해당 label의 데이터들과 일반적으로 유사한 vector가 된다고 이해할 수 있겠다.

여기서 유사한 vector가 된다는 의미는 내적값이 크다는 것을 의미한다.

예를 들어, car class의 데이터가 주어지면 car에대한 template vector와 가장 유사하기 때문에 그 내적값이 가장 클 것이고, 해당 class로 선택이 될 것이다.

 

Linear Classifer의 classfication boundary

Linear Classifier는 그 이름대로, Linear한 boundary로 데이터를 classifiaction한다.

 

따라서 XOR과 같은 문제를 해결할 수 없는 한계가 잇다.

 

 

Linear Classifier의 loss function이나 optimization(train)에 대해서는 다음 장에서 다룬다.