[CS231n] lecture 1. KNN 과제(Assignment)
포스팅을 시작하기에 앞서 수준 높은 강의와 강의 자료를 무료로 배포해주신 Stanford University CS231n 교수진께 감사의 말씀을 드립니다.
label(y_test, y_train)의 경우 'plane', 'car', 'bird'와 같이 string 타입으로 적혀있을 줄 알았는데 숫자로 적혀있네요. 아마 관리하기 편하기 때문에 숫자로 적은 것이 아닐까 추측해 봅니다.
온라인 강의: https://www.youtube.com/watch?v=vT1JzLTH4G4&list=PLC1qU-LWwrF64f4QKQT-Vg5Wr4qEE1Zxk
강의 자료: https://cs231n.github.io
참고) 위의 강의 자료 사이트(github)를 통해 들어가면 Assignment #1에서 과제 다운로드 및 drive mount에 관한 짧은 영상을 볼 수 있습니다.
* 블로그 작성자 github 주소: https://github.com/withAnewWorld/JamesHanamura
Assignment 구조
작성되어 있는 부분(파란색), 과제로 주어진 부분(빨간색)
- 데이터 전처리
- KNN 함수 작성
- train()
- compute_distance()
- predict_label(k)
- KNN의 성능(예측도)을 확인할 수 있는 부분
- distance의 loop에 따른 시간복잡도 측정
- Cross-validation
- k에 따른 성능 비교(시각화)
데이터 전처리
training image(X_train)은 총 5,000개의 이미지로 이루어져 있고 Test Image(X_test)는 총 500개의 이미지로 이루어진 것을 확인할 수 있습니다.
KNN 함수 작성
이제 본격적으로 과제가 시작되는 부분입니다. 시작하기에 앞서 과제로 주어진 데이터로 알고리즘을 테스트하기 보다 임의의 데이터를 만들어 문제를 해결하고자 합니다. 그 이유로는
1. 데이터의 용량이 크다.
- 시간을 많이 잡아 먹음
- 디버깅 어려움
2. 데이터 훼손의 가능성(?) 등.
먼저 임의의 데이터를 만들어봅시다.
직접 타이핑을 쳐서 데이터를 만들 수도 있지만 시간이 많이 걸리기 때문에random함수를 통해 임의의 수를 받아 왔습니다. 여기서 X_train과 X의 열의 개수는 똑같이 해주시되 행의 개수는 차이가 나게 설정해주시는 것이 좋습니다. 그 이유는 나중에 compute_distances_no_loops()함수를 작성할 때 언급하겠습니다. Compute_distances_two_loops(self, X)
코드를 간단하게 그림으로 나타내 봤습니다. 우리의 목적은 dists 행렬의 (i, j) 원소에 X_train의 i번째 행 원소 - X의 j번째 행 원소를 계산하여 L2 distance를 적용해야 합니다.
힌트에는 matrix multiplication 즉, 행렬의 곱셈을 이용하고 two broadcast sums을 이용하라고 합니다. 일단 곱셈이라고 하니 L2 distance를 곱셈을 이용하여 나타내야 할 것 같습니다.
첫번째 방법의 경우 X와 X_train의 행의 개수가 다르기 때문에 뺄셈자체가 불가능 합니다. 그러면 두번째 산술식을 이용해 접근해보도록 하겠습니다.
행렬곱을 하기 위해서는 첫번째 행렬의 열의 개수와 두번째 행렬의 행의 개수가 같아야하므로 하나의 행렬을 Transpose를 통해 이를 맞춰줍니다. 여기서 주의할 점은 dists[i, j]에서 i가 X(Test Image)의 i번째 행을 뜻하므로 X_train행렬을 transpose하여 곱해야 합니다.
loop에 따라 시간이 얼마나 차이가 나는지 확인해보시면 loop의 수가 줄어들수록 시간이 줄어들고 no loop은 1초도 안걸리는 걸 확인할 수 있습니다. 주석(NOTE)을 확인해보시면 two loop이 때에 따라서는 one loop보다 시간이 더 걸릴 수도 있다고 합니다. 
확실히 k=1일 때보다 더 성능이 좋은 것을 확인하실 수 있습니다.
그 후 함수 호출을 통해 각각의 결과를 list에 저장하여 k_to_accuracies에 저장하면 마지막 코드가 끝납니다.
이는 각각 num_test와 num_train을 range로 가지는 이중 for문을 통해 쉽게 작성할 수 있습니다. 주의해야할 점은 L2 distance 함수는 각각의 차이를 제곱한 후에 더하는 것으로 np.square 함수가 np.sum보다 앞에 나와야 합니다.
cf) 그림에는 L1 distance가 나와있습니다. 참고해주세요.
Compute_distances_one_loop(self, X)
눈썰미가 좋으신 분들이라면 one_loop의 경우 강의 노트에 답안이 나와있는 걸 알아채셨을 겁니다.
one_loop은 numpy의 sum함수의 특징을 이용하는 것으로 axis를 통해 행을 더할 것인지, 열을 더할 것인지, 혹은 모든 원소를 더할 것인지 나뉘어 집니다.
저희는 행으로 image 데이터를 나열했기 때문에 axis=1을 변수로 계산을 하면 됩니다.
Compute_distances_no_loops(self, X)
첫번째 난관입니다. 위의 코드들을 보면 반복문을 사용하지 않고 dists를 도출하는 것이 가능할지 의문이 듭니다. 다행히 힌트가 있으므로 먼저 힌트를 살펴봅시다.
힌트에는 matrix multiplication 즉, 행렬의 곱셈을 이용하고 two broadcast sums을 이용하라고 합니다. 일단 곱셈이라고 하니 L2 distance를 곱셈을 이용하여 나타내야 할 것 같습니다.
(X-X_train)^2 = (X-X_train)(X-X_train) = X^2+X_train^2-2X(X_train)
행렬곱의 결과 num_test*num_train의 행렬이 만들어 졌고 X.dot(X_train.T)(i, j)의 원소는 X의 i번째 행과 X_train의 j번째 행의 sum product의 결과입니다. 반면 X^2과 X_train^2은 각각의 이미지 데이터를 제곱한 것으로 X^2의 i번째 행은 np.sum(X^2, axis= 1)의 결과가, X_train^2의 j번째 열에 np.sum(X_train^2, axis=1)의 결과가 담겨 산술식에 맞게 작성해야 합니다.
이제 제곱한 결과를 각각의 sqaure_X의 i번째 행에는 X의 i번째 행의 제곱합을, sqaure_X_train의 j번째 열에는 X_train의 j번째 행 제곱합을 나타내야 합니다.
cf) np.tile(array, (row, col))은 row의 수만큼 행을 복사하고 col의 수 만큼 열을 복사하는 함수입니다. 예를 들어 array가 2*3 행렬일 때 np.tile(array, (1, 2))의 경우 array의 행은 1번만 복사하고 array의 column은 2번 복사하여 2*6행렬이 만들어집니다.NN성능 확인
k=1일 때 nearest neighbor의 성능은 약 27%를 보입니다. 다음 코드는 loop에 따라 dists의 결과값이 차이를 보이는지 확인하는 디버깅 코드로 따로 다루지는 않겠습니다.
비록 no loop의 코드 작성이 어렵지만 프로그램의 성능을 위해서는 no loop 함수로 작성해야 하는 것을 몸소 체감할 수 있었습니다.
다음은 위의 도출된 dists를 변수로 k개의 후보군을 뽑아 가장 많은 개수를 가지는 label을 결과값으로 도출하는 predict_label 함수 작성입니다. 가장 먼저 해야할 사항으로는 closest_y 리스트에 k개의 label을 오름차순으로 저장하는 코드입니다. hint를 보면 numpy.argsort 함수를 살펴보라고 하네요.
5개의 후보군을 선택하여 이를 오름차순으로 label을 선택하면 0번째 test image의 경우 y_train[2]=1, y_train[1]=0, y_train[4]=4, y_train[3]=4, y_train[0]=4으로 선택된 것을 볼 수 있습니다. 여기서 비록 label 4가 label 1과 label 0보다 더 큰 L2 distance를 보이지만 KNN에 따라 label 4가 결과값으로 도출되겠군요.
predict_labels(self, dists, k=k)
다음은 위의 도출된 dists를 변수로 k개의 후보군을 뽑아 가장 많은 개수를 가지는 label을 결과값으로 도출하는 predict_label 함수 작성입니다. 가장 먼저 해야할 사항으로는 closest_y 리스트에 k개의 label을 오름차순으로 저장하는 코드입니다. hint를 보면 numpy.argsort 함수를 살펴보라고 하네요.
도출된 dists에 np.argsort()를 적용하면 다음과 같이 결과가 나옵니다. 각각의 행에 따라 오름차순으로 index를 나열한 것을 볼 수 있습니다. (cf. index는 0부터 시작) 먼저 0번째 행을 보면 (2, 1, 4, 3, 0)으로 dists[0][2] = 5.91607978부터 시작하여 dists[0][0]=11.44552314까지 정렬이 된 것을 확인할 수 있습니다. 그렇다면 이를 통해 간단히 코드를 작성할 수 있을 것 같습니다.
코드를 작성할 때 주의점은 dists의 [i]번째 행을 불러온 후 np.argsort()를 할 것이냐 혹은 dist의 모든 행렬을 np.argsort()를 한 후 리스트에 저장을 할 것이냐에 따라 엄청난 속도 차이를 보입니다. 당연히 필요한 부분만 그 때 그 때 불러오는 것이 메모리나 시간 관리 면에서 우수하게 작동을 합니다.
다음으로는 후보 k개 중에서 가장 많이 뽑힌 label을 반환하는 알고리즘을 작성해야 합니다. 만약 개수가 똑같을 때에는 더 적은 점수 차이를 보인 label을 반환하도록 설계를 해야합니다. 개수를 세는 알고리즘은 count()함수가 떠오를 것이고 더 적은 점수 차이를 보이는 것은 np.argsort()에 의해 오름차순으로 정렬이 되었으므로 index가 더 낮은 label을 저장하면 될 것 같습니다.
다음으로는 후보 k개 중에서 가장 많이 뽑힌 label을 반환하는 알고리즘을 작성해야 합니다. 만약 개수가 똑같을 때에는 더 적은 점수 차이를 보인 label을 반환하도록 설계를 해야합니다. 개수를 세는 알고리즘은 count()함수가 떠오를 것이고 더 적은 점수 차이를 보이는 것은 np.argsort()에 의해 오름차순으로 정렬이 되었으므로 index가 더 낮은 label을 저장하면 될 것 같습니다.
cf) k의 수가 커질수록 closest_y에는 여러 label이 중첩으로 저장되어 있을텐데 특정 label의 index함수를 적용할 경우 어떤 index를 반환할까요?
답: 다행히도 가장 먼저 있는 index를 반환합니다. 여기서는 차이가 가장 적은 index를 반환하므로 크게 신경쓰지 않아도 될 것 같군요.
이제 closest_y에 들어있는 원소를 반복문으로 체크를 하며 가장 많은 개수를 가지는 label을 리스트에 저장하면 될 것 같습니다. 여기서 반복문을 수행할 때 closest_y에 들어있는 원소를 0부터 k까지 확인하기보다 각각의 원소만 확인하고 싶습니다. 이럴 때에 필요한 자료형은 무엇이 있을까요? 정답은 중복을 허락하지 않는 집합 자료형이 있습니다.
저 같은 경우는 y_train을 통해 label의 개수를 확인해 closest_y에 들어있지 않은 label인지 확인하는 코드가 추가로 들어갔지만 여러분은 set(closest_y)를 통해 반복문을 수행하면 더 간결하고 빠른 코드를 작성할 수 있으실 것입니다.
Cross-validation
이제 과제의 마지막입니다. 각각의 training image를 n개로 나눈 후 validation set과 train set으로 나누어 어떠한 k가 가장 좋은 성능을 보이는지 확인하시면 됩니다.
먼저 각각의 train_folds에 train data를 num_folds로 나누어 저장을 해야 합니다. 이를 위해 numpy array_split 함수를 살펴보라고 합니다. 
그 전에 가상 데이터의 개수가 cross-validation을 하기에 부족한 느낌이 들어 10개의 data로 확장을 하겠습니다;;
np.array_split(array, n)은 array를 n개의 sub array로 나누는 함수입니다. np.split()함수와 다른 특징은 array의 개수가 n으로 나누어지지 않을 시에도 작동한다는 점입니다.
다음으로는 key값으로 k를 설정하고 value 값으로 각각의 validation set을 설정하여 knn을 적용하는 코드입니다. 여기서 num_folds=5 이므로 k=k_choices에서 X_train_folds[0]부터 X_train_folds[4]까지 validation set을 설정해야 합니다.
주의해야할 점은 np.array_split()을 적용한 후에는 np.array가 아닌 list를 반환합니다.
또한 list로 X_train data를 각각 감싸기 때문에 하나의 차원이 추가된 것을 확인할 수 있습니다. 이를 위해서는 concatenate함수를 통해 데이터를 통합시켜야 하는데 validation set의 경우 하나의 fold만 가져오기 때문에 concatenate함수를 적용시키면 안됩니다.
마지막 코드는 여러분이 생각하기에 가장 좋은 성능을 보이는 k를 위의 그래프를 통해 추측해본 후 결과를 확인하는 방법입니다.
결론
KNN의 단점으로는 낮은 정확도도 있지만 더 치명적으로는 예측을 하는데에 소요되는 시간이 지나치게 길다는 점입니다. Training에 소요되는 시간은 많이 걸려도 사용자가 사용하기에 큰 불편함을 못 느끼게 만들 수 있지만 결과를 예측할 때에 매번 많은 시간이 걸릴 경우 실시간으로 작동해야 하는 프로그램에서는 이를 사용하기에 부적절합니다. 따라서 이를 해결하기 위해 input을 통해 곧바로 output을 도출해내는 linear classifier가 다음 lecture의 주제입니다.
