- KNN 실습 및 정리를 코랩으로 수행
- Cross-validation 에 대해 이론 및 코드
- 코드 리뷰 및 이론 정리
KNN 이론
이미지에서 어떤식으로 분류되는지 과정 설명
여기서 New Insatnce 는 새로운 Test Dataset 을 뜻하고 이건 이미지 하나를 2차원 평면위에 투입시켜놓은것
이제 여기서 우리는 Training Data 와 Test Data 에 대해 L1 Dist or L2 Dist 를 활용하여 최다 투표를 수행해야함
- L1 Dist & L2 Dist 정의
여기서 P는 이미지의 픽셀간의 값의 차이를 뜻함, 두사이의 거리는 결국 모든 이미지의 픽셀 사이의거리를 합하여 더한것
KNN 실습
- 데이터셋 : CIPAR 10
- Train 5000, Test 500
- 환경 : Colab
Inline Question 1
![[Pasted image 20240203135959.png]]
Notice the structured patterns in the distance matrix, where some rows or columns are visibly brighter. (Note that with the default color scheme black indicates low distances while white indicates high distances.)
- What in the data is the cause behind the distinctly bright rows?
- What causes the columns?
첫번째 질문에 대해서는 bright rows 는 테스트 이미지 한장 이 학습 이미지 전체와의 거리 를 모아 놓은 row이다. 그래서 모든 부분이 밝다는것은 훈련 모델과의 유사성이 별로 없다는걸 뜻함.
두번째 질문에 대해서는 columns 은 어떤 훈련 이미지 한장과의 유사도를 뜻하는것이다. 그렇기에 임의의 훈련 이미지와
얼마만큼 가깝냐 머냐
를 알 수있는 지표이다.
- 코드 복사시 엔터 쳐지는 현상 -> Ctrl + shift + V 를 하면 해결
Two Loop code
def compute_distances_two_loops(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using a nested loop over both the training data and the
test data.
Inputs:
- X: A numpy array of shape (num_test, D) containing test data.
Returns:
- dists: A numpy array of shape (num_test, num_train) where dists[i, j]
is the Euclidean distance between the ith test point and the jth training
point.
"""
# 500, 5000
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train)) # (500,5000) shape
for i in range(num_test):
for j in range(num_train):
# the difference between each images -> one test image pixed
X_sub = X[i] - self.X_train[j]
l2 = np.sqrt(np.sum(X_sub**2))
#l2_r = np.linalg.norm(X_sub,2)
dists[i][j] = l2
pass
return dists
Inline Question 2
We can also use other distance metrics such as L1 distance.
For pixel values $p_{ij}^{(k)}$ at location $(i,j)$ of some image $I_k$,
the mean $\mu$ across all pixels over all images is $$\mu=\frac{1}{nhw}\sum_{k=1}^n\sum_{i=1}^{h}\sum_{j=1}^{w}p_{ij}^{(k)}$$
And the pixel-wise mean $\mu_{ij}$ across all images is
$$\mu_{ij}=\frac{1}{n}\sum_{k=1}^np_{ij}^{(k)}.$$
The general standard deviation $\sigma$ and pixel-wise standard deviation $\sigma_{ij}$ is defined similarly.
Which of the following preprocessing steps will not change the performance of a Nearest Neighbor classifier that uses L1 distance? Select all that apply. To clarify, both training and test examples are preprocessed in the same way.
- Subtracting the mean $\mu$ ($\tilde{p}{ij}^{(k)}=p{ij}^{(k)}-\mu$.)
- Subtracting the per pixel mean $\mu_{ij}$ ($\tilde{p}{ij}^{(k)}=p{ij}^{(k)}-\mu_{ij}$.)
- Subtracting the mean $\mu$ and dividing by the standard deviation $\sigma$.
- Subtracting the pixel-wise mean $\mu_{ij}$ and dividing by the pixel-wise standard deviation $\sigma_{ij}$.
- Rotating the coordinate axes of the data, which means rotating all the images by the same angle. Empty regions in the image caused by rotation are padded with a same pixel value and no interpolation is performed.
1,3 번이 정답이고 픽셀 하나하나의 평균은 n개의 배치개에서 무조건 다르다. 또한 전체 평균을 빼주는건 영향을 주지 않음 나누는것도 마찬가지
One Loop code
def compute_distances_one_loop(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using a single loop over the test data.
Input / Output: Same as compute_distances_two_loops
"""
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
# using the brodacasting
for i in range(num_test):
dists[i] = np.sqrt(np.sum(np.power(self.X_train - X[i], 2),axis=1))
pass
return dists- np.power 는 제곱 합수
- broad casting 을 이용하여 (5000,3072) Train image 와 (n번째,3072) test 이미지를 연산함
-
broad casting 조건
- 차원에서 axis(축) 하나가 무조건 1이여야함 (5000,3072) 와 (500,3072) 는 broad casting이 수행될 수 없음 이유는 5000 과 500 둘중에 하나가 1이 아님
- 차원에서 축이 같아야함 (500,3072) (1,300) 은 500,1 은 broad casting 이 수행되지만 3072와 300은 브로드 캐스팅이 안되기 때문에 위와 같은 데이터는 조건에서 위배됨
No Loop code
내가짠 코드 (3.47s)
def compute_distances_no_loops(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using no explicit loops.
Input / Output: Same as compute_distances_two_loops
"""
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
X_square = np.reshape(np.diag(np.dot(X,X.T)),(-1,1))
X_train_square = np.reshape(np.diag(np.dot(self.X_train,self.X_train.T)),(1,-1))
dists = np.sqrt(X_train_square + X_square - 2*np.dot(X,self.X_train.T))
return dists코드 설명
우선 위의 그림1을 보게되면 Train_image 와 Test_image 간의 연산을 위해 L2 dists를 이용한것을 확인할 수 있음 여기서 핵심 알고리즘은 image를 vector 로 보고 루트 안에 제곱값을 풀어서 연산해주는게 핵심 그렇게하여 모든 성분에 대해 계산이 가능해짐 diag()는 대각성분의 값들만 뽑아 내기위해 취해준것이고 여기선 X**2 제곱을 행렬곱후 대각성분으로 뽑으면 어떨까 하는 아이디어 에서 코드를 작성하였음 그러나 sum(A,axis=1) 을 이용한 element 곱이 더 좋은 성능을 보여줌
위 그림2는 sum 을 이용한 np.diag 성분을 뽑아내는 과정을 나타냄 위방법이 더 효율적이다.
인터넷 코드 (0.87s)
def compute_distances_no_loops(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using no explicit loops.
Input / Output: Same as compute_distances_two_loops
"""
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
X_square = np.sum(X**2,axis=1)
X_train_square = np.sum(self.X_train**2,axis=1)
dists = np.sqrt(X_train_square+X_square.reshape(-1,1)-2*np.dot(X,self.X_train.T))
return distsCross-validation 이론
위의 그림을 보며 설명하겠다. 우선 각 데이터 셋에 대해 5가지로 fold를 나눠줌 즉 여러개의 모델의 평균값을 이용하여 정확도를 계산하는 원리 overfitting을 막기위해 사용되는 방법중 하나 이다.
num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]
X_train_folds = []
y_train_folds = []
X_train_folds = np.array_split(X_train,num_folds)
y_train_folds = np.array_split(y_train,num_folds)
pass
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
# A dictionary holding the accuracies for different values of k that we find
# when running cross-validation. After running cross-validation,
# k_to_accuracies[k] should be a list of length num_folds giving the different
# accuracy values that we found when using that value of k.
k_to_accuracies = {}
for i in range(num_folds):
# train / validation split (80% 20%)
X_train_batch = np.concatenate(X_train_folds[1:num_folds])
y_train_batch = np.concatenate(y_train_folds[1:num_folds])
X_valid_batch = X_train_folds[0]
y_valid_batch = y_train_folds[0]
# swap data (for next iteration)
if i < num_folds - 1:
tmp = X_train_folds[0]
X_train_folds[0] = X_train_folds[i+1]
X_train_folds[i+1] = tmp
tmp = y_train_folds[0]
y_train_folds[0] = y_train_folds[i+1]
y_train_folds[i+1] = tmp
# train model
model = KNearestNeighbor()
model.train(X_train_batch, y_train_batch)
dists = model.compute_distances_no_loops(X_valid_batch)
# compute accuracy for each k
for k in k_choices:
y_valid_pred = model.predict_labels(dists, k=k)
# compute validation accuracy
num_correct = np.sum(y_valid_pred == y_valid_batch)
accuracy = float(num_correct) / y_valid_batch.shape[0]
# accumulate accuracy into dictionary
if i == 0:
k_to_accuracies[k] = []
k_to_accuracies[k].append(accuracy)
pass
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
# Print out the computed accuracies
for k in sorted(k_to_accuracies):
for accuracy in k_to_accuracies[k]:
print('k = %d, accuracy = %f' % (k, accuracy))