CS231n : Lecture 2

15 Mar 2018 1 minute read

K-Nearest Neighbor vs Linear Classifiers

K-Nearest Neighbor는 non-parametric classifier인 반면, Linear classifier(SVM, Softmax)는 parametric classifier이다.
Linear classifier는 training data의 내용을 요약해 담고 있는 W, weight들이 곧 모형(model)이 된다. 반면 K-Nearest Neighbor는 그런게 없다. Data가 곧 모델이기 때문이다.
이 점에 주목해 이러한 모형을 ‘data model’이라고도 한다. K-NN을 비롯한 data model의 장점은 data에 adaptive 하다는 것이다. 데이터에 대해 어떠한 가정도 하지 않기 때문에 k-NN은 true distribution의 형태가 어떻든 어느 정도 괜찮은 예측력을 보인다.
반면 linear classifier는, 모형의 분산이 상대적으로 작고 robust하다는 강점은 있지만, 그만큼 데이터의 true distribution이 선형이 아닐 때, 예측력이 크게 떨어진다는 단점이 있다.

Curse of Dimensionality (차원의 저주)
K-Nearest Neighbor classifier를 train 하는데에 걸리는 시간은 O(1)이지만, predict 하는 데에 걸리는 시간은 O(N)이다. Train 하는 데에 오래 걸리는 알고리즘은 괜찮지만, test 하는데에 시간이 오래 걸리는 알고리즘은 좋은 방법이 아니다. We want classifiers that are fast at prediction; slow for training is ok.
특히 이미지 데이터는 더더욱 안 쓰인다!
L1 / L2 distance와 같은 거리 척도가 이미지 사이의 거리를 재는데에 좋은 방법이 아니기 때문이다. 강의에서는 같은 L2 distance를 가지는 세개의 서로 다른 이미지를 보여주었다. 우리가 봤을 때는 확연하게 나타나는 차이를 K-NN의 distance metric은 capture하지 못한다.

L1 Distance는 원점으로부터 거리가 동일한 점들을 연결했을 때, 각 변수가 가지는 값이 다를 수 있다. 따라서 L1 Distance는 변수들이 가지는 의미가 서로 다를 때 더 적합하다. (when individual elements have more meaning)
L2 Distance는 반대로 변수들이 가지는 의미가 크게 차이가 없을 때에 더 적합하다.
L1 Distance를 사용하는 K-NN classifier를 fit하면, decision boundary는 축에 평행하는 듯한 모습을 보인다. L2 Distance를 사용하는 K-NN classifier는 형태가 더 자유롭다.

Linear classifier을 통해 학습된 W (weight matrix)의 각 행은 각 카테고리에 대응되는 일종의 template이다.
이 때, 각 class마다 template을 하나만 학습하는 것이 예측력을 떨어뜨리는 원인들 중 하나이다. 나중에는 이 제약이 사라진, 좀 더 복잡한 모델들을 배우게 될 것.

가장 먼저 찾아두면 좋은 hyperparameter : step size
Stochastic Gradient Descent의 minibatch size는 주로 전체 데이터의 크기를 $2^n$으로 나눈 숫자
Linear classifier 의 W를 조정하는 것은 선형 decision boundary의 기울기를 수정하는 것이고, bias term b를 조정하는 것은 boundary를 평행이동하는 과정이다.