CS231n : Image Classification: Data-driven Approach, k-Nearest Neighbor, train/val/test splits (한국어 번역)

출처: http://ishuca.tistory.com/entry/Image-Classification-Datadriven-Approach-kNearest-Neighbor-trainvaltest-splits

CS231n Convolutional Neural Networks for Visual Recognition

http://cs231n.github.io/classification/ 의 번역인데, 발번역임. 

내 공부를 돕고자함. 

저작권 문제는 없는 듯하나 문제가 생길 경우 바로 삭제함

발번역이어도 내용은 제대로 이해하고 있으니 질문 있으면 댓글 남겨주세요

=======================================================================================Image Classification: Data-driven Approach, k-Nearest Neighbor, train/val/test splits

L1/L2 distances, hyperparameter search, cross-validation

이것은 이미지 분류 문제와 데이터에 기반한 접근법을 컴퓨터 비젼 외부 사람들에게 소개하기 위한 입문 강의임

이미지 분류(Image Classification)

동기(Motivation). 이 장에서 우리는 카테고리가 고정된 집합으로부터 하나의 라벨을 입력 이미지에 할당하는 작업인 이미지 분류 문제를 소개할 것임. 이것은 단순함에도 불구하고, 실제 응용의 많은 다양성을 가지고, 컴퓨터 비젼에서 주요 문제 중 하나임. 게다가 이 코스에서 후에 볼 것이지만, 많은 다른 겉보기에 달라보이는 컴퓨터 비젼 작업들(예를 들면, 물체 검출, 분할 등)은 이미지 분류로 축소할 수 있음

예(Example). 예를 들면, 아래 이미지에서 이미지 분류 모델은 하나의 이미지를 택해, 4개의 라벨 {cat, dog, hat, mug} 에 확률을 할당한다. 이미지에서 보여지는 것처럼, 컴퓨터에게 이미지는 매우큰 3차원 배열로써 표현된다. 이 예에서, 고양이 이미지는 너비 248 픽셀, 높이 400 픽셀이고, 3개의 색 채널 Red, Green, Blue ( 짧게 RGB)을 가지고 있다. 그러므로, 이미지는 248 x 400 x 3 의 숫자들이고, 이는 총 297,600  개의 숫자다. 각 숫자는 정부로 0(검은색) 으로부터 255(흰색)까지의 범위를 갖는다. 우리의 작업은 매우 큰 숫자를 하나의 라벨 "cat"으로 바꾸는 것이다.

이미지 분류에서 이 작업은 주어진 이미지에 대해 하나의 라벨(혹은 우리가 표시한 것처럼 라벨들의 분포를)을 예측하는 것이다. 이미지들은 0부터 255의 정수들인 3차원 배열로 너비 x 높이 x 3 의 크기를 갖는다. 이 3은 세개의 색 채널 Red, Green, Blue을 표현한다.

문제(Challenges). 시각적 개념 (e.g. 고양이 cat)을 인지하는 작업은 사람이 수행하기에는 상대적으로 쉽다. 컴퓨터 비젼 알고리즘의 관점에서 문제를 고려할 가치가 있다. 아래에 현재의 문제 목록이 있다. 이미지는 밝기의 3차원 배열로 표현되었다는 것을 명심해라

관점의 변화(Viewpoint variation). 한 객체의 개별 실체(single instance)는 카메라에 대하여 많은 방법으로 얻어질 수 있다.

규모의 변화(Scale variation). 시각적 클래스는 자주 그들의 크기에서 변화를 보인다(이미지 내에서 보이는 그들의 크기 뿐만 아니라 실제 세상에서의 크기)

변형(Deformation). 관심 있는 많은 객체는 일정한 형태가 아니고, 극단적으로 변형이 올 수도 있다.

안 보임?(Occlusion). 관심 있는 그 객체는 안 보일 수 있다. 때때로 어느 객체의 아주 작은 부분만이 관찰가능 할 수도 있다.

조명 조건(Illumination conditions). 조명의 효과는 픽셀 수준에서 극단적이다.

배경 어수선함(Background clutter). 관심 있는 그 객체는 그들의 환경 속에 섞여 있을 수 있고, 그들을 식별하기 어렵게 만든다. 

클래스 내 변화(intra-class variation). 관심 있는 클래스들은 자주 상대적으로 넓어질 수 있다. 의자 같은것처럼. 이들은 이들 그들 자신의 외모와 함께 각 객체의 많은 다른 타입이 있다. 

좋은 이미지 분류 모델은 클래스간 변동에는 예민함을 유지하면서 이 모든 변화에 불변해야한다. 

자료에 따른 접근법(data-driven approach). 어떻게 우리가 이미지를 개별 카테고리에 분류할 수 있는 알고리즘을 작성할 수 있을까? 예를 들어, 숫자의 리스트를 정렬하는 것과 같은 알고리즘을 작성하는 것과 달리, 이미지에서 고양이를 식별하기 위한 알고리즘을 작성하는 방법은 명확하지 않다. 그러므로, 코드에서 직접적으로 관심있는 대상의 카테고리가 무엇인지 특정지으려는 시도 대신에, 어린아이와 같은 방법을 취하는 접근법이다. 우리는 컴퓨터에게 각 클래스의 많은 예제를 제공하고, 각 클래스의 시각적 특성에 대해 배우는 알고리즘을 개발한다. 이 접근법은 자료에 따른 접근법(data-driven approach)과 관련이 있다. 이것은 첫재로 이름 붙여진(labeled) 이미지의 학습 자료집합을 누적할 필요가 있다. 이것은 다음과 같은 데이터집합의 예제이다.

4개의 시각적 카테고리에 대한 학습 집합의 예제이다. 실제는 우리는 수 천개의 카테고리와 각 카테고리에 대한 수십만의 이미지를 가지고 있다.

이미지 분류 파이프라인(The image classification pipeline). 우리는 이미지분류에서 이 작업이 하나의 이미지를 픽셀의 배열로 표현하고, 거기에 라벨을 할당하는 것을 보았다. 우리의 완벽한 파이프라인은 다음과 같이 공식화될 수 있다.

입력(Input): 우리의 인풋은  K개의 다른 클래스 중 하나로 라벨된  N개의 이미지의 집합으로 구성된다. 우리는 이 데이터를 학습 집합(training set)이라고 부른다.

학습(Learning): 우리의 작업은 학습 집합을 사용해서 그 클래스의 모든 것이 무엇으로 보이는지 학습하는 것이다. 우리는 분류기(classifier)를 학습하는 것(혹은 모형을 배우는 것)으로 이 단계를 나타낸다. 

평가(Evaluation): 결국, 우리는 이전에 보지 못했던 이미지의 새로운 집합에 대한 예측 라벨을 물어봄으로써 분류기의 질을 평가한다. 우리는 분류기에 의해 예측된 것과 이들 이미지에 실제 라벨ㅇ을 비교한다. 직관적으로 우리는 실제 답(우리는 이를 ground truth라 부른다)과 맞는 예측이 많기를 바란다.

최근접 이웃 분류기(Nearest Neighbor Classifier)

우리의 첫번째 접근법으로써, 우리는 우리가 최근접 이웃 분류기라 부르는 것을 개발할 것이다. 이 분류기는 Convolutional Neural Networks 콘볼루션 신경망과 관련 없고, 실제로 쓰이는 일이 매우 드믈다. 그러나 이것은 이미지 분류 문제에 대한 기본적인 접근법에 대한 아이디를 얻을 수 있도록 한다.

예제 이미지 분류 집합:CIFAR-10 (Example image classification dataset: CIFAR-10). 유명한 모형 이미지 분류 집합은  CIFAR-10 dataset이다. 이 데이터셋은 높이와 너비가 32 픽셀인 6만 개의 작은 이미지들로 구성되어있다. 각 이미지는 10개의 클래스의 하나로 이름 붙여져있다 (예를 들면, "비행기, 자동차, 새, 기타 등등"). 이들 6만개의 이미지들은 5만 개의 학습 이미지와 1만 개의 테스트 이미지 집합으로 나뉘어져있다. 아래 이미지에서 10개 클래스에서 랜덤한 10개의 예제를 볼 수 있다.

왼쪽: CIFAR-10 데이터셋으로부터 예제 이미지. 오른쪽: 첫 열은 테스트 이미지이고, 다음은 학습데이터셋에서 픽셀별 차이에 해당하는 10개의 최근접 이웃을 보여준다.

우리는 이제 CIFAR-10 학습 5만개의 학습 집합(모든 라벨 별로 5천개의 이미지)이 주어졌다고 가정하고, 우리는 남은 1만 개를 이름 붙이고  싶다. 이 최근접 이웃 분류기는 하나의 테스트 이미지를 택해, 학습 이미지의 모든 개별 이미지와 비교하고, 가장 가까운 학습 이미지의 라벨을 예측한다. 위에 이미지에서 오른쪽에 10개의 테스트 이미지에 대한 이런 과정의 결과의 예를 볼 수 있다. 10개의 예제 중 약 3개만이 동일 클래스로 검색되고, 나머지 7개의 예제는 다른 사례이다. 예를 들어, 8번째 행의 말에 대한 최근접 학습 이미지는 빨간 차이다. 아마 강한 검은 배경 때문일 것이다. 그 결과, 말의 이미지는 차로 잘못 분류된다.

너는 우리가 32 x 32 x 3의 두 블록 인 두개의이미지를 비교하는 정확한 방법의 자세한 설명을 언급하지 않고 남겨둔 것을 눈치 챘을 수도 있다. 가장 단순한 가능중 하나는 픽셀별로 이미지를 비교하고 이 모든 차이를 더하는 것이다. 즉, 두개의 이미지가 주어지고, I1, I2 벡터로써 그들을 표현하면, 그들을 비교하기 위한 합리적인 선택은 L1 거리일 수 있다. 

이 과정을 시각화하면 다음과 같다.

L1 거리(이 예제에서는 하나의 색 채널에 대한)와 함께 두개의 이미지를 비교하기 위해 픽셀별 차이를 사용한 예제. 두개의 이미지들은 요소별로 빼지고, 모든 차이는 하나의 숫자로 더해졌다. 만약 두 이미지가 동일하다면 그 결과는 0이 될 것이다. 하지만 이미지가 많이 다르다면, 그 결과는 매우 클 것이다.

코드에서 우리가 어떻게 이 분류기를 구현할 수 있는지 살펴보자. 머넞, CIFAR-10 데이터를 메모리에 4개의 배열로 불러오자: 학습 데이터/ 학습 라벨 데이터와 테스트 데이터/ 데스트 라벨 데이터. 아래에 코드에서 Xtr(50,000 x 32 x 32 x 3의 크기)는 학습 집합에서 모든 이미지를 가지고 있고, Ytr( 50,000의 길이) 1차원 배열은 해당하는 학습 라벨 (0부터 9까지)를 가지고 있다.

Xtr, Ytr, Xte, Yte = load_CIFAR10('data/cifar10/') # 우리가 제공하는 마법의 함수
# 모든 이미지들을 1차원으로 만든다
Xtr_rows = Xtr.reshape(Xtr.shape[0], 32 * 32 * 3) # Xtr_rows 는 50000 x 3072 shape가 된다.
Xte_rows = Xte.reshape(Xte.shape[0], 32 * 32 * 3) # Xte_rows 는 10000 x 3072 shape가 된다.

이제 우리는 행으로 만든 모든 이미지들이 있다. 여기에 우리가 분류기를 학습하고 평가할 방법이 있다.

nn = NearestNeighbor() # 최근접 이웃 분류기 클래스를 생성한다.
nn.train(Xtr_rows, Ytr) # 학습 이미지와 라벨에 대해 분류기를 학습한다.
Yte_predict = nn.predict(Xte_rows) # 테스트 이미지에 대해 라벨을 예측한다.
# 올바르게 예측한 예제의 평균 숫자로 분류기의 정확도를 나타낸다.

print 'accuracy: %f' % ( np.mean(Yte_predict == Yte) )

평가기준으로써 정확도(accuracy)가 일반적으로 쓰인다. 이것은 올바르게 예측한 비율로 측정된다. 모든 분류기는 우리가 공통된 API를 만족시키게 만들 것이다. 그들이 가진 train(X,y) 함수는 데이터와 라벨로부터 배운다. 내부적으로, 그 클래스는 라벨의 모형의 몇가지 종류와 그들이 데이터로부터 예측할 수 있는 방법을 만든다. 그래서 predict(X) 함수는 새로운 데이터를 취해서 라벨을 예측한다. 여기에 L1 거리로 단순한 최근접 이웃 분류기의 구현이 있다.

import numpy as np

class NearestNeighbor(object):
  def __init__(self):
    pass

  def train(self, X, y):
    """ X는 각 행이 예제인 N x D 크기의 행렬이다. Y는 N 크기의 1차원이다. """
    # 이 최근접 이웃 분류기는 단순히 모든 학습 데이터를 기억한다.
    self.Xtr = X
    self.ytr = y

  def predict(self, X):
    """ X 는 우리가 예측하고 싶어하는 각 행이 예제인 N x D 행렬이다. """
    num_test = X.shape[0]
    # 입력 형과 출력형이 같도록 만든다.
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)

    # 모든 테스트 데이터 행들에 걸쳐 반복을 한다.
    for i in xrange(num_test):
      # i번째 테스트 이미지에 대해 가장 가까운 학습 이미지를 찾는다 
      # 절대값 차이의 합인 L1 거리를 사용해서
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
      min_index = np.argmin(distances) # 가장 작은 거리를 갖는 인덱스를 얻는다
      Ypred[i] = self.ytr[min_index] # 가장 가까운 예제의 라벨로 예측한다

    return Ypred

이 코드를 실행해봤다면, 너는 CIFAR-10 에 대해 이 분류기가 38.6%만 성취한 것을 보았을 것이다. 이것은 더 랜덤(10개 클레스에 대해 10% 정확도를 기대하는)으로 예측하는 것보다는 더 낫지만, 최신 기술인 콘볼루션 신경망이 달성한 약 95%나 사람수준의 성능(약 94% 정도로 측정된다)에는 근처에도 못 간다.

거리의 선택(The choice of distance). 벡터 간의 거리를 계산하는 다른 많은 방법이 있다. 또다른 일반적인 선택은 두 벡터간의 유클리디안 거리를 계산하는 기하학적 해석인 L2 거리를 대신 사용할 수 있다. 이 거리는 다음의 형태를 갖는다.

즉 우리는 이전처럼 픽셀 별 차이를 계산하는데, 동시에 모든 것들에 대해 제곱을 하고, 전부 더하고 마지막으로 제곱근을 취한다. numpy에서 위의 코드는 한줄이면 된다. 

distances = np.sqrt(np.sum(np.square(self.Xtr - X[i,:]), axis = 1))

나는 위에서 np.sprt를 불렀다. 그러나 실제 최근접 이웃에서는 생략할 수 잇다. 왜냐면 제곱 근은 보이는 것만 바꾸기 때문이다. 즉, 이것은 거리의 절대적 크기를 바꾸지, 순서를 바꾸지는 않는다. 그래서 최근접이웃은 이걸 넣으나 빼나 동일하다. 만약 이 거리로 최근접와 함께 CIFAR-10에 대해 최근접 이웃 분류기를 실행하면, 35.4% 정확도를 얻는다(우리의 L1 거리 결과보다 약간 더 낮다)

L1 vs. L2. 이것은 두 지표 간의 차이를 고려할때 흥미롭다. 특히, L2 거리는 두 벡터간의 차이를 얻을 때 L1 거리보다 관대하다. 즉, L2 거리는 하나의 큰 것보다 많은 중간 불일치는 선호한다. L1과 L2 거리는 가장 일반적으로 사용되는 p-norm의 특별한 경우이다.

k개 최근접 이웃 분류기(k - Nearest Neighbor Classifier)

우리가 예측을 만들때 가장 가까운 이미지의 라벨만을 사용하는 것을 이상하게 여겼을 수도 있다. 이것은 항상 k 최근접 이웃 분류기라 불리는 것을 사용해 더 나아질 수 있다. 이 아이디어는 단순하다 학습 데이터 셋에서 가장 가까운 하나의 이미지만을 찾는 것 대신의 k 개의 가까운 이미지를 찾고, 테스트 이미지의 라벨에 대한 투표를 하는 것이다. 특히 , k가 1 일때, 우리는 최근접 이웃 분류기라 한다. 직관적으로 k의 큰 수는 이상치에 대해 더 강건한 분류기를 만드는 스무딩 효과를 갖는다.

2차원 점과 3개의 클래스(red,blue,green)을 사용한 최근접 이웃과 5 최근접 이웃 분류기 사이의 차이에 대한 예제이다. 색칠된 지역은 L2 거리로 분류기에 의한 결정경계(decision boundaries)를 보여준다.하얀 지역은 적어도 두개의 클래스가 같은 수의 클래스 투표를 받은 애매모호한 분류 점을 나타낸다. 최근접 분류기의 경우에, 이상치 데이터(파란 점 가운데에 초록색 점)는 올바르지 않은 예측의 작은 섬을 만든다. 반면 5 최근접 이웃 분류기는 이러한 비정규성을 극복하고, 테스트 데이터(보이지는 않은)에 대해 더 일반적일 것으로 예상할 수 있다. 5 NN 이미지에서 회색 지역은 최근접 이웃 사이에서 투표에 동일 표 때문에 발생했다.

실제에서, 너는 대게 항상 k 최근접 이웃을 사용하길 원할 것이다. 그러나 k의 어떤 값을 사용할 것인가? 다음에서 이 문제로 넘어간다

하이퍼 파라미터 조정을 위한 검증 집합(Validation sets for hyperparameter tuning)

k 최근접 이웃 분류기는 k의 설정이 필요하다. 그러나 어떤 숫자가 가장 좋은지 알 수 있을까? 게다가, 우리는 L1, L2 거리나 내적(dot product)과 같은 수 많은 거리 함수 선택이 있다. 이들 선택을 하이퍼파라미터라고 한다. 자료로부터 학습하는 기계학습 알고리즘의 설계에서 자주 나온다. 값이나 설정을 어떻게 설정해야할지 명확하지 않기 때문이다.

가장 좋은 값을 찾기 위해 수많은 다른 값을 시도할 수 있다. 좋은 아이디어다 그러나 실제로 우리가 할 것이다. 그러나 매우 조심해서 해야만 한다. 특히, 우리는 하이퍼파라미터들을 조정할 목적으로 테스트 집합을 사용할 수 없다. 너가 기계학습 알고리즘을 설계할때 마다, 테스트 집합은 끝날때까지 절대로 건드리지 말아야할 귀중한 것으로 생각해야만 한다. 그렇지 않으면, 진짜 위험은 너의 하이퍼파라미터 조정이 테스트 집합에서 잘 작동할 수 있다는 것이다. 그러나 만약 너가 모델을 구축한다면 성능이 유의미하게 감소하는 것을 볼 수 있을 것이다(테스트 집합을 사용해서 하이퍼파라미터를 만들면 이렇다는 것임). 우리는 이것을 너가 테스트 집합에 과대적합했다고 말한다.  테스트집합에 대해 하이퍼파라미터를 조정한다면, 테스트 집합을 학습 집합처럼 사용하는 것이고, 그래서 너의 모델을 구축할 때, 아주 낙관적인 결과를 얻을 수 있다. 그러나 네가 마지막에만 테스트 집합을 사용한다면, 너의 분류기의 일반적 능력을 측정하는 아주 좋은 대리변수가 될 것이다(우리는 이 클래스에서 후에 일반화를 둘러싼 많은 논의를 살펴볼 것이다)

테스트 집합에 대한 평가는 가장 마지막에 단 한번만 해라

운좋게도, 테스트 집합은 전혀 건들지 않고 하이퍼파라미터를 조정하는 올바른 방법이 있다. 이것은 학습 집합을 두개로 나누는 것이다.  학습 집합보다 조금 더 작고, 우리는 이것을 검증 집합(validation set)이라 부를 것이다. 예제처럼 CIFAR-10을 사용할 때, 우리는 4만 9천개를 학습집합으로 사용하고, 1천개를 검증을 위해 남겨둔다. 이 검증 집합은 하이퍼파라미터를 조정하기 위한 가짜 테스트 집합 처럼 사용한다.

# 이전과 같이 Xtr_rows, Ytr, Xte_rows, Yte 를 가정한다
#  Xtr_rows 는 50000x 3072(32x32x3) 행렬이다
Xval_rows = Xtr_rows[:1000, :] # 검증을 위해 처음 1천개를 고른다
Yval = Ytr[:1000]
Xtr_rows = Xtr_rows[1000:, :] # 학습에는 49,000개만 사용한다
Ytr = Ytr[1000:]

# 검증 집합에 가장 잘 작동하는 하이퍼파라미터를 찾는다
validation_accuracies = []
for k in [1, 3, 5, 10, 20, 50, 100]:

  # 특정 k의 숫자를 사용해서, 검증 자료에 대해 평가한다
  nn = NearestNeighbor()
  nn.train(Xtr_rows, Ytr)
  # 여기서 우리는 최근접이웃 클래스가 k를 입력값처럼 사용하도록 수정했다.
  Yval_predict = nn.predict(Xval_rows, k = k)
  acc = np.mean(Yval_predict == Yval)
  print 'accuracy: %f' % (acc,)

  # 검증 집합에 대해작동하는 것을 저장한다
  validation_accuracies.append((k, acc))

이 과정의 끝에서, 우리는 k의 값에 대한 그래프를 그릴 수도 있다. 우리는 이 값으로  고정시키고, 실제 테스트 집합에 대해 한번만 평가한다.

너의 학습 집합을 학습 집합과 검증 집합으로 나눠라. 모든 하이퍼파라미터를 조정하기 위해 검증 집합을 사용해라. 마지막에 테스트 집합에 대해 한번만 하고, 성능을 보고해라

교차검증(Cross-validation). 너의 학습 집합의 크기가 작아서 검증 집합도 작을 경우에 하이퍼파라미터 조정을 위한 더 정교한 기법을 사용한다. 이를 교차검증(Cross-validation)이라 부른다. 이전 예제에서, 이 아이디어는 애매하게 뽑은 첫 1천 개를 검증집합으로 나누고 나머지를 학습 집합으로 두는 대신에, 다른 검증 집합 들에 걸쳐 반복적으로 특정 k에 대해 측정하고 이들 성과를 평균하는 방법으로 노이즈가 적고, 더 나은 추정을 할 수 있다. 예를 들면, 5겹 교차검증(5-fold cross-validation)에서, 우리는 학습 집합을 5개의 동등한 그룹으로 나누고, 이중 4개를 학습에 사용하고, 나머지 한개를 검증에 사용한다. 우리는 이걸 모든 검증 집합에 대해 반복하고, 성능을 평가하고, 성능을 평균낸다.

파라미터 k 에 대한 5겹 교차검증의 예. 각 k의 값에 대해 4개의 그룹으로 학습시키고, 5번째로 평가한다. 그런 이유로, 각 k는 검증 그룹에 대해 5개의 정확도가 나온다. 추세선은 각 k에 대한 결과의 평균선이고, 오차 막대는 표준편차를 나타낸다. 이 특정 사례에서, 교차 검증은 k를 약 7이 가장 좋다고 한다. 만약 너가 5겹보다 더 한다면, 더 부드러운 곡선을 기대할 수 있을 것이다.

실제는 교차검증은 계산적 비용이 매우 크기 때문에 사람들은 교차검증을 선호하지 않고, 한번 검증 집합을 나누는 것을 선호한다. 사람들은 주로 학습 집합의 50%-90%를 학습 집합으로 사용하고, 나머지를 검증으로 한다. 그러나 이것은 다양한 요인에 달려있다. 예를 들어 하이퍼파라미터의 수가 크다면 너는 아마 검증  집합을 나누는걸 크게하는 것을 선호할 수도 있다. 만약 검증집합의 예제의 수가 적다면(단지 수백정도라면,) 교차검증을 사용하는 것이 더 안전할 수 있다. 몇 겹을 할지는 너에게 달려있지만, 실제로는 3겹, 5겹 10겹의 교차검증을 주로 사용한다.

일반적인 데이터 나누기. 학습 집합과 테스트 집합은 주어진다. 학습집합은 예제에서 5개의 그룹으로 나눠진다. 1-4개의 그룹은 학습 집합이고, 노란색으로 되어있는 5번째 그룹은 검증 집합이 되어 하이퍼파라미터를 조정하는데 사요된다. 교차검증은 검증 집합을 바꿔가며 1-5까지 반복적으로 수행된다. 이것이 5겹 교차검증이라 부르는 이유다. 가장 좋은 하이퍼파라미터가 결정된면, 그 모델을 테스트 자료(빨강)에 평가된다.

최근접 이웃 분류기의 찬반양론(Pros and cons of Nearest Neighbor classifier)

최근접 이웃 분류기의 장점과 단점을 알아보자. 명확하게, 장점은 구현하고 이해하기 매우 단순하다는 것이다. 게다가, 이 분류기는 학습에 시간이 안 든다. 학습 자료를 색인하고 저장하기만 하면 된다. 그러나 우리는 매우 테스트 집합에 대해 매우 큰 계산 비용을 지불한다. 하나의 테스트 예제를 분류하기 위해 모든 학습 예제와 비교해야만 한다. 이것은 단점이다, 실제에서 우리는 자주 학습 시간을 효율적이게 하는 것보다 테스트 시간을 최적하는데 신경써야한다. 사실, 우리가 후에 개발할 딥러닝은 이 문제에 극단적으로 다른 면이다. 그들은 학습에 매우 큰 비용이 들고, 한번 학습을 완료하면, 새로운 테스트 예제를 분류하기 위해서는 매우 쉽게 된다. 이러한 작동 방식이 실제에서는 더 바람직하다.

최근접 이웃 분류기의 계산적 복잡함은 연구가 활발히 진행되고 있고, 몇가가 근사 최근접 이웃(approximate Nearest Neighbor ,ANN) 알고리즘과 라이브러리들이 존재해서 자료집합에서 최근접 이웃을 가속해서 찾을 수 있다. (e.g. FLANN) 이들 알고리즘은 검색 동안의 공간/시간적 복합도와 최근접 이웃의 정확성 사이의 상충관계에서 대게, k-means 알고리즘이나 kdtree 등과 같은 전처리와 인덱싱 단계에 의존한다.

최근접 이웃 분류기는 몇가지 문제에서는 좋은 선택이 될 수 있을 것이다(특히 자료가 저차원이라면), 그러나 이것은 실제 이미지 분류 설정에서는 매우 드믈게 사용된다. 한가지 문제는 이미지는 매우 고차원의 객체(그들은 매우 많은 픽셀을 갖는다)이고, 고차원의 공간에서의 거리는 매우 직관에 반대일 수 있다. 아래 이미지는 우리가 위에서 개발한 픽셀 기반의 L2 유사성이 인지적 유사성으로부터 매우 다른 것을 보여준다.

고차원 자료(특히 이미지들)에서 픽셀 기반 거리는 직관적이지 않을 수 있다. 원본 이미지(좌측) 과 3개의 다른 이미지들은 L2 픽셀 거리에서는 동등하게 떨어져 있지만, 명확하게 픽셀별 거리는 인지적이나 의미론적 유사성에 해당하지는 않는다.

여기에 픽셀 차이를 이용해 이미지를 비교하는 것이 불충한지 쉽게 보여주는 시각화가 있다. 우리는 이 시각화 기술을 t-SNE 라 부른다. 이것은 CIFAR-10 이미지들을 가지고 그들의 쌍별 거리를 잘 보전하는 2차원 공간에 임베드 시키는 것이다. 이 시각화에서 가까운 이미지들은 우리가 위에서 개발한 L2 픽셀별 거리에 따라 매우 가까운 이미지들로 생각한다.

CIFAR-10 이미지들을 t-SNE와 함께 2차원 공간에 임베드 시킴. 이 이미지에서 가까운 이미지들은 L2 픽셀 거리 기반으로 가까운 거로 생각한다. 배경의 강한 효과는 의미적 클래스 차이보다 더 크게 나타난다.  here 에 이 시각화의 더 큰 버젼이 있다.

각자에게 가까운 이미지들은 그들의 의미론적 식별보다 배경의 형태나 이미지들의 일반적 색 분포에 더 영향을 받는다. 예를 들어, 개는 흰색 배경이어서 개구리와 매우 가깝게 보인다. 이상적으로 우리는 변화나 개별특성(배경같은)에 관련 없이 그들의 클래스를 잘 나타내어 같은 클래스는 가까이 나타나게 하고 싶다. 그러나 우리가 이러한 특성읃기 위해서는 픽셀 기반을 넘어서야한다.

요약(summary)

우리는 이미지 분류의 문제를 소개했다.하나의 카테고리가 이름 붙여진 이미지 집합이 주어지고, 우리는 테스트 이미 집합에 대해 이들 카테고리를 예측하고, 예측 정확도를 측정한다.

우리는 최근접 이웃 분류기라 불리는 단순한 분류기를 소개했다. 우리는 다양한 하이퍼파라미터(k의 값이나 예제를 비교하는데 사용하는 거리의 유형)가 이 분류기와 관련있고, 이들을 선택하는 명확한 방법이 없음을 보였다.

우리는 학습 데이터를 둘(학습 집합과 검증집합이라 부르는 가짜 테스트 집합)로 나눠서 하이퍼 파라미터를 설정하는 올바른 방법을 보였다. 우리는 다른 하이퍼파라미터 값을 시도하고 검증 집합에 대해 가장 좋은 성능을 내는 값을 택한다.

만약 학습 데이터가 부족하다면, 우리는 교차검증이라 불리는 방법을 사용한다. 이것은 가장 좋은 하이퍼파라미터를 추정하는데에 있어서 노이즈를 줄여줄 것이다.

하이퍼 파라미터들을 찾으면, 우리는 그것을 고정시키고, 실제 테스트 집합에 대해 평가를 수행한다.

우리는 최근접 이웃이 CIFAR-10에 대해 약 40%의 정확도를 갖는 것을 보았다. 이것은 전체 학습 집합을 저장하기만 하면 되는 매우 단순한 구현이지만 테스트 이미지를 평가할 때 매우 큰 비용이 든다.

마지막으로, 우리는 픽셀값에 대한 L1이나 L2 거리를 사용하는 것이 불충분함을 보였다. 왜냐하면 거리는 그들의 의미적 맥락보다는 이미지의 색분포나 배경과 더 강하게 관련되어 있기 때문이다.

다음 강의에서 우리는 이들 문제를 해결하기 위해 90% 정확도를 갖고, 한번 학습이 학습 집합에 대해 완료되면, 테스트 이미지를 평가하는데 1000분의 1초보다도 더 작은 시간이 걸리는 모형을 개발할 것이다.

요약: 실제로 k NN 적용하기 (Summary: Applying kNN in practice)

만약 실제로 kNN을 적용하고 싶다면 다음의 과정을 따르라.

1. 자료를 전처리해라: 자료에서 특성들을 평균이 0이고 분산이 1로 정규화해라. 우리는 나중 장에서 이에 대해 논의할 것이고, 이장에서 자료의 정규화에 대해 얘기 안한 것은 이미지들에서 픽셀은 대게 동질적이고, 넓고 다른 분포가 아니기 때문이다.

2. 만약 너의 자료가 매우 고차원이라면, PCA(wiki ref, CS229ref, blog ref)나 Random Projections. 같은 차원축소 기법을 고려해라.

3. 너의 학습 자료를 랜덤하게 학습과 검증 집합으로 나누어라. 보통 70%-90% 정도는 학습으로 나눈다. 이 설정은 너가 가진 하이퍼파라미터의 수와 그들이 갖는 영향을 얼마나  볼 것인지에 달려있다. 만약 추정하고 싶은 하이퍼파라미터가 매우 많다면, 그들을 효율적으로 추정하기 위해 매우 큰 검증 집합을 선택하는 쪽이 낫다. 만약 너의 검증 자료의 수를 고려한다면, 학습 자료를 그룹으로 나누고 교차 검증을 수행하는 것이 최선일 것이다. 만약 너가 계산 비용을 감당할 수 있다면, 항상 교차 검증을 택하는 쪽이 안정하다(더 많은 겹은 더 좋지만, 더 많은 비용이 든다)

4. k의 많은 선택과 거리 지표에 대해 검증 자료로 kNN 분류를 학습하고 평가한다. 

5. 만약 너의 kNN 분류기가 너무 오래 돈다면, 근사 최근접 이웃 라이브러리를 사용해, 검색을 가속할 수 있다(정확도에 손실이 있긴함).

6. 가장 좋은 결과를 주는 하이퍼파라미터에 주의해라. 매우 큰 학습 자료 때문에 너의 학습 자료에 검증 데이터가 있었다면, 최적 하이퍼파라미터는 변할 수 있기 때문에 최적 파라미터를 전체 학습 자료에 사용할 것인지 하는 문제가 있다.  테스트 집합에 대해 최적 모형을 평가하고, 테스트 집합 정확도와 성능을 보고해라

더 읽을 것(Further Reading)

더 읽고 싶다면 관심있을 만한 거들이 있다.

A Few Useful Things to Know about Machine Learning, 특히 6장이 관련되어 있고, 전체 논문을 읽는 걸 추천한다

Recognizing and Learning Object Categories, ICCV 2005에서 객체 분류의 짧은 코스