k-Nearest Neighbors (k-최근접 이웃)
일반적인 순서
- 데이터셋 구성
- training dataset
- ${(x_i,y_i)}^{N}_{i=1}$, $x_i \in R^{D}$, $y_i \in {1, \dotsc, C}$
- validation dataset
- ${(x_i,y_i)}^{M}_{i=N+1}$
- test Dataset
- ${(x_i,y_i)}^{L}_{i=M+1}$
- 방법
- f 를 만들어 준다.
- f 에 new $x$ 를 집어 넣는다. $\hat{y} := f(x)$
- $\hat{y}$와 $y$ 비교($i=M+1, \dotsc, L$)
k-NN 에서 $f$ 를 만드는 방법 (training 방법)
- training set ${(x_i,y_i)}^{N}_{i=1}$ 을 전부 기억한다.
- new $x$가 들어오면,
- $x$ 와 $x_1, x_2, \dotsc, x_N$ 까지의 거리들을 전부 계산 : calculate $d(x, x_1), d(x, x_2), \dotsc, d(x, x_N)$
- 가장 가까운 ($d(x,x_i) (i=1 \dotsc N)$가 가장 작은) k 개의 index 들에 대하여. $y_i$ 의 majority vote 를 예측값으로 리턴함 ex) $f(x) = 3$
* 단, “거리” $d(x, z)$는 “잘 정의된 거리”
* ex) $x, z \in R^D$ 이면, 다음 거리들 고려 가능
- L2 거리 : $d(x, z) = {| x-z |}2 = \sqrt{\sum{j=1}^{D} (x_j - z_j)^2}$
- L1 거리 : $d(x, z) = {| x-z |}1 = \sum{j=1}^{D} \mid x_j - z_j \mid$
- 일반적으로 $d(x, z)$ 는 다음 조건들을 만족해야 한다. (“metric”)
- 모든 $x, z$에 대하여 $d(x, z) = d(z, x)$
- 모든 $x$ 에 대하여 $d(x, x) = 0$
- 모든 $x, z$에 대하여 $d(x, z) \geq 0$ (if $x \neq z$, $d(x, z) > 0$)
- (삼각 부등식) 임의의 $x, z, w$ 에 대하여 $d(x, w) \leq d(x, z) + d(z, w)$
- time complexity
- training : $O(1)$
- testing : $O(N*(L-M))$
- slow training
- Nearest Neighbor Decision Boundaries (결정경계) : $f$ 가 정해지면 결정됨
Hyperparameters
Hyperparameters 란?
Distance Metric
, Hyperparameter k
를 적절히 선택해야하는 문제
- 학습 데이터로부터 배울 수 있는 것이 아니다.
- 최적의 $k$ 와 $d$ 는 없다. 주어진 데이터셋에 의존해서 언제나 바뀐다.
- hyperparameter 에 따라서 $\hat{y}$ 를 건설하는 rule 이 달라진다.
Setting Hyperparameters
- 학습 데이터로 그대로 평가해서 hyperparameter를 고른다면?
- $k=1$ 은 학습 데이터에 대해서 항상 완벽한 결과(자신의 라벨)를 낸다.
- train 과 test 로 나눈다면?
- 나중에 서비스할 때 어떻게 잘 작동할지 알 수 가 없다. (Wild 환경을 재현해줄 데이터가 남지 않는다.)
- train 과 validation 과 test 로 나눈다면?
- train 으로 $f_1, f_2, \dotsb$ 등을 만든다.
- validation 으로 $f_1, f_2, \dotsb$ 등의 성능을 잰다.
- test 로 실제 프로덕션 때 어느 정도의 성능을 낼지 예측
- Cross-Validation
- test 는 그대로 두고, train 부분을 fold 로 나눈 다음에 각각 validation 부분을 바꿔서 학습 & 측정 한다.
- 각 $f_1, f_2, \dotsb$ 의 평균 성능이 가장 좋은 것을 고른다.
Validation set 의 역할
- 데이터셋 구성
- training dataset : ${(x_i,y_i)}^{N}_{i=1}$
validation dataset
: ${(x_i,y_i)}^{M}_{i=N+1}$
- 여러 방법론의 hyperparameter 비교
- test dateset : ${(x_i,y_i)}^{L}_{i=M+1}$
- 하나의 $f$ 성능을 평가하는 방법 (분류 문제)
- validation set : ${(x_i,y_i)}^{M}_{i=1}$ (training set 이랑 독립적인 데이터셋)
- true label : $y_i$, predicted label : $\hat{y_i} (= f(x_i))$
- classification accuracy (정분류율) $= \frac{맞은 i의 수}{M} = \frac{\sum_{i=1}^{M}I(y_i=\hat{y_i})}{M}$
- miss classification rate (오분류율) $= \frac{틀린 i의 수}{M} = \frac{\sum_{i=1}^{M}I(y_i \neq \hat{y_i})}{M}$
결론
k-NN은 좋은 분류기인가?
- 이론적으로는 그렇다.
- Universal Approximation : training size가 무한대(dimension을 채우는 빽빽한 점들)면, 어떤 true function 이던지 가까워질 수 있다.
이미지 데이터에 적용할 때의 이론적인 한계점
- Curse of Dimensionality (차원의 저주) : dimension(D) 이 커지면 dimension을 비슷한 거리의 점들로 꽉채우기 위한 점들이 기하급수적으로 많이 필요해진다.
- Very slow at test time
- Distance metrics on pixels are not informative
- 픽셀 데이터에 대한 거리 계산이 실제로 무엇을 의미하는가에 대한 의문점이 있을 수 있다.
- ConvNet features 을 뽑아서 거리를 계산하면 의미가 있을 수 있다. Nearest Neighbor 자체가 이상한 개념은 아님!