Deep High-Resolution Representation Learning for Visual Recognition
-> 고해상도의 표현을 학습하는 모델인가보다..
1. Abstract
위치가 중요한 휴먼 pose estimation이나 semantic segmentation, object detection과 같은 시각적 문제에는 고해상도 표현이 필수적이다.
현존하는 sota 구조들은 인풋 이미지를 저해상도로 인코딩하고, 다시 고해상도로 회복시킨다.
우리의 모델(HRNet)은 모든 과정에서 고해상도를 유지한다. 여기에는 두가지 특징이 있다.
1) high-to-low resolution convolution이 평행으로 연결된다는 것이다.
2) 반복적으로 정보를 교환한다.
이로 인한 장점은, 결과적인 표현이 시맨틱하게 더 풍부하고 정확하다는 것이다.
우리의 모델은 human pose estimation, semantic segmentation, and object detection과 같은 다양한 application에서
우월성을 보여주었다.
2. Conclusion
이 논문을 통해, 우리는 시각 인식 문제를 위한 고해상도 네트워크를 발표하였다.
여기에는 기존 모델들과 다른 세 가지 근본적인 차이가 있다.
1) 고해상도와 저해상도의 컨볼루션을 평행하게 연결하였다는 것. (일렬로가 아니라)
2) 전체과정에서 고해상도를 유지하였다는 것
3) position sensitivity를 가지고 multi-resolution representation을 반복적으로 녹였다는 것
가장 우수한 결과는 HRNet이 컴퓨터 비전 문제의 백본으로서 강력하다는 것이다.
우리의 연구는 특정 비전 문제에 대한 네트워크 아키텍처를 구축하기 위한 연구도 장려하였다.
Discussion
여기에는 잘못된 이해가 있다: 해상도가 높을수록 HRNet의 메모리 비용이 많이 들 것이다. 라는
사실, HRNet을 세가지 application(pose estim, object detect, semantic seg)에 적용한 메모리 비용은 이전 SOTA와 유사하다.
게다가, 우리는 파이토치 1.0에서 runtime cost 비교를 요약했다
1) segmentation HRNet에서의 inference time은 훨씬 적다.
2) pose estimation HRNet에서의 training time은 조금 많이 든다.
우리는 semantic segmentation the inference cost 가 PSPNet and DeepLabv3 보다 상당히 적다는 것이다.
Future and Followup works
semantic segmentation and instance segmentation를 위한 HRNet의 combination을 연구할 것이다.
현재로써는, mIOU의 결과가 있지만, OCR과 결합함으로써 더 해상도를 증가시켜볼 것이다.
Introduction
DCNN(Deep Convolution Neural Network)은 많은 컴퓨터비전 태스크에서 state-of-the-art한 결과를 내었다.
DCNN의 강점은 더 풍부한 표현을 할 수 있다는 것이다. (더 고해상도)
가장 최근에 개발된 classification network(AlexNet, VGGNet, etc)은 LeNet-5의 디자인 규칙을 따른다.
Fig. 1. The structure of recovering high resolution from low resolution. (a) A low-resolution representation learning subnetwork (such as VGGNet [126], ResNet [54]), which is formed by connecting high-to-low convolutions in series. (b) A high-resolution representation recovering subnetwork, which is formed by connecting low-to-high convolutions in series. Representative examples include SegNet [3], DeconvNet [107], U-Net [119] and Hourglass [105], encoder-decoder [112], and SimpleBaseline [152].
(a)는 점진적으로 feature map의 공간적 크기를 줄이고, 고해상도에서 저해상도로 일렬로 연결한다. 그리고 저해상도로 귀결한다.(b)는
High-resolution representations는 위치가 중요한 태스크들에 필요하다.
그래서 이전의 SOTA 모델들은 resolution을 올리기 위해
(b) classification에 의해 나온 low-resolution 결과에 high-resolution recovery process를 거쳤다.
게다가, 확장된 컨볼루션은 downsample된 layer를 줄이는 데 사용되고
이에 따라 medium-resolution representation을 얻게 된다.
우리는 새로운 아키텍처를 제안한다. 이름하여 HRNet High-Resolution Representations.
이는 전체 과정에서 고해상도를 유지할 수 있다.
우리는 고해상도 컨폴루션 stream으로 시작해서, 점진적으로 high-to-low resolution convolution stream을 one by one으로 추가하고, multi-resolution streams을 평행으로 연결한다.
Fig. 2. An example of a high-resolution network. Only the main body is illustrated, and the stem (two stride-2 3 × 3 convolutions) is not included. There are four stages. The 1st stage consists of high-resolution convolutions. The 2nd (3rd, 4th) stage repeats two-resolution (three-resolution, four-resolution) blocks. The detail is given in Section 3
HRNet은 semantically 강한 것 뿐만 아니라, 공간적으로도 정밀하다.
1) 우리의 모델 개념은 high-to-low resolution convolution stream을 직선이 아닌,평행으로 연결하기 때문이다.
따라서, 고해상도를 유지할 수 있다. 저해상도에서 고해상도로 회복시킨 것이 아니기 때문에 공간적으로도 정밀할 수 있다.
Attention to Scale: Scale-aware Semantic Image Segmentation
-> 어텐션에서 스케일로.. 스케일을 아는 시맨틱 이미지 세그먼테이션
이 논문의 핵심은 어텐션 매커니즘과 스케일로 예측된다.
1. Abstract
FCN(Fully Convolutional Network)에 multi-scale feature을 적용한 것은
시맨틱 세그먼테이션에서 SOTA 성능을 달성하는데 핵심이 되었다.
multi-scale feature를 뽑는 데 일반적으로 사용되는 방법은
공유되는 deep network에 다수의 resize된 이미지를 먹이는 것이다.
그리고 나온 결과를 픽셀 단위로 합치는 것이다.
우리는 어텐션 매커니즘을 제안한다.
이는 각 픽셀 위치에서 다중 스케일 기능에 부드럽게 가중치를 부여하는 방법을 학습하는 메커니즘이다.
우리는 state-of-the-art segmentation model을 채택하였고, 여기에 우리의 어텐션 모델과 multi-scale input image를 학습하였다.
어텐션 모델은 average pooling 과 max pooling 의 성능을 능가할 뿐만 아니라,
다양한 위치와 스케일에서의 feature의 중요성을 진단적으로 시각화할 수 있게 하였다.
게다가, multi-scale features를 병합할 때 좋은 성과를 내려면
각 스케일의 output에 대한 추가적인 감독이 필요함을 보여준다.
우리의 모델의 효과성을 PASCAL-Person-Part, PASCAL VOC 2012 and a subset of MS-COCO 2014에서
입증하였다.
2. Conclusion
이 논문에서는 multi-scale input을 활용하기 위해 DeepLab-LargeFOV 모델을 사용하였다.
세가지 데이터셋에 실험해봄으로써 우리가 알아낸 것이다.
1) multi-scale inputs가 single-scale inputs 보다 더 좋은 성능을 냄
2) 어텐션 모델에 multi-scale features를 적용한 것은 average pooling과 max pooling보다 뛰어날 뿐만 아니라,
다른 위치와 스케일에 따른 features의 중요성을 진단적으로 시각화할 수 있다.
3) 각각의 스케일에 마지막 결과에 추가적인 감독이 있다면 훌륭한 결과가 있을 것이다.
Figure 8. Qualitative segmentation results on PASCAL-Person-Part validation set.
3. Introduction
Semantic image segmentation는 각각의 모든 픽셀에 semantic label을 할당하는 태스크이다.
최근에는 FCN 을 기반으로 한 다양한 방식들이 놀라운 성과를 내었다.
성공적인 Semantic image segmentation의 요소 중 한가지는 "multi-scale features"의 사용이다.
FCN에는 multi-scale features를 활용하는 두 가지 타입의 네트워크 구조가 있다.
. Different network structures for extracting multi-scale features:
첫 번째는 skip-net이다.
아주 큰 receptive field sizes 때문에 skip-net의 feature는 본질적으로 multi-scale이다.
학습 시간동안 skip-net은 두 가지 프로세스를 거치는데,
딥러닝 백본을 학습하고, multi-scale feature extraction 과정에서 fine tuning하는 것이다.
이 전략의 문제점은 학습과 feature extraction 과정이 분리되어 있기 때문에 학습 과정이 이상적이지 못 하다는 것이다.
두 번째는 share-net이다.
인풋 이미지를 여러 사이즈로 리사이즈하고, 공유된 딥 뉴럴 네트워크로 통과하는 것이다.
그런 다음 다중 스케일 피쳐들을 기반으로 최종 예측값을 계산한다.
최근, attention model은 컴퓨터 비전과 자연어 처리에서 엄청난 성공을 하였다.
전체 이미지와 시퀀스들을 압축하는 것이 아니라,어텐션은 가장 유용하고 관련있는 피쳐에 집중한다.
이전의 2D 대상으로한 어텐션 모델들과 다르게, 우리는 scale dimension에서의 효과를 입증해보고자 한다.
우리는 sota 모델에 share-net를 적용하였고,
average pooling과 max pooling을 generalize하기 위해 soft attention model을 적용하였다.
attention model illustration
어텐션 모델은 이미지에 나타나 있는 물체의 크기에 따라
multi-scale feature들에 가중치를 부여하는 방법을 학습힌다.
(예를 들어, 모델은 거칠고 큰 물체에는 큰 가중치를 부여한다.)
각각의 스케일에서, 어텐션 모델은 weight map을 뱉어내는데, 이것은 픽셀 바이 픽셀로 가중치를 구한 것이다.
그리고 FCN에서 생성한 score map의 가중치 합을 뱉어낸다.
각각의 스케일마다 추가적인 감독을 소개한다. 성능 개선에 필수적인
우리는 어텐션 모델과 멀티스케일 네트워크를 공동으로 학습시킨다.
어텐션 컴포넌트는 average pooling과 max pooling에 비해 상당한 개선을 제공한다.
게다가 diagnostic visualization이 가능하다. 모든 이미지 포지션에서 각각의 스케일의 각각의 피쳐들의 중요성을 시각화함으로써 블랙박스를 벗겨내었다.
4. Model
1) Review of DeepLab
FCN이 semantic segmentation에서 성공적인 효과를 거두었으므로
FCN의 변형인 DeepLab 모델을 리뷰해보고자 한다.
DeepLab은 VGG를 참고하여 16개의 레이어 구조를 채택하였다.
해당 네트워크에 dense feature map을 가져다주는 fully convolution으로 주입하였다.
자세하게는, 마지막 VGG의 fully connected layer가 fully convolutional layer로 변경되었다. (마지막 레이어는 커널 사이즈 1x1)
원래의 VGG-16의 spatial decimation은 32이다. 5개의 stride 2를 가진 max pooling을 사용하였기 때문이다.
DeepLab은 atrous 알고리즘을 사용하여 이를 8로 줄였다.
또한 linear interpolation을 사용하여 최종 레이어의 스코어 맵을 원본 이미지 해상도에 매핑한다.
우리는 DeepLab의 여러가지 변형 중, DeepLab-LargeFOV에 초점을 맞춘다.
2) Attention model for scales
(a) Merging score maps (i.e., last layer output before SoftMax) for two scales. (b) Our proposed attention model makes use of features from FCNs and produces weight maps, reflecting how to do a weighted merge of the FCN-produced score maps at different scales and at different positions.
어텐션 모델은 각각의 다른 스케일과 position으로 부터 FCN이 생성한 스코어맵의
가중 합을 어떻게 할지를 반영하는 weight map을 만든다.
즉, multi-scale features를 가중치를 어떻게 할지 학습한다.
share-net을 기반으로, 인풋 이미지는 여러 스케일로 리사이즈 된다.
각각의 스케일은 DeepLab을 통과하며 score map을 만든다. (fully convolutional layer)
score map은 bilinear interpolation을 통해 동일한 해상도를 갖도록 리사이즈된다.
f : score map
w : importance of feature at position i and scale s
g : weighted sum of score map
w를 시각화하면 스케일별로 어텐션을 시각화할 수 있다.
5. Result
Table 1. Results on PASCAL-Person-Part validation set. E-Supv: extra supervisionTable 2. Per-part results on PASCAL-Person-Part validation set with our attention model.
Table 3. Results on PASCAL VOC 2012 validation set, pretrained with ImageNet. E-Supv: extra supervisionTable 4. Labeling IOU on the PASCAL VOC 2012 test set.
Table 5. Results on PASCAL VOC 2012 validation set, pretrained with MS-COCO. E-Supv: extra supervision.
W를 계산해낸 이 loss function은 score 를 보고 W가 얼마나 양적으로 나쁜지 알려주는 척도이다.
이 강의에서 여러가지 loss function을 소개할 것이다.
가장 적게 나쁜 W를 찾아가는 과정이 "최적화" 과정이다.
Loss function : multi-label SVM
image classification 에서 많이 쓰는 것 -> multi-label SVM
sj = 틀린 함수값, syi = 맞는 합수값
만약 맞는 클래스의 score가 틀린 클래스의 score보다 월등히 크다면, Loss는 0으로 설정한다.
그렇지 않다면, 맞는 클래스의 score에서 틀린 클래스의 score을 빼는 방식으로 Loss를 계산한다.
Hinge Loss 라고도 부른다. x축은 맞는 클래스의 score이고, y축은 loss이다.
맞는 클래스 score이 높아지면, loss는 감소한다.
loss가 0이 되면 잘 분류한 것으로 보면 된다.
from builtins import range
import numpy as np
from random import shuffle
from past.builtins import xrange
def svm_loss_naive(W, X, y, reg):
"""
Structured SVM loss function, naive implementation (with loops).
Inputs have dimension D, there are C classes, and we operate on minibatches
of N examples.
Inputs:
- W: A numpy array of shape (D, C) containing weights.
- X: A numpy array of shape (N, D) containing a minibatch of data.
- y: A numpy array of shape (N,) containing training labels; y[i] = c means
that X[i] has label c, where 0 <= c < C.
- reg: (float) regularization strength
Returns a tuple of:
- loss as single float
- gradient with respect to weights W; an array of same shape as W
"""
dW = np.zeros(W.shape) # initialize the gradient as zero
# compute the loss and the gradient
num_classes = W.shape[1]
num_train = X.shape[0]
loss = 0.0
for i in xrange(num_train):
scores = X[i].dot(W)
correct_class_score = scores[y[i]]
loss_contributors_count = 0
for j in xrange(num_classes):
if j == y[i]:
continue
margin = scores[j] - correct_class_score + 1
if margin > 0:
loss += margin
dW[:, j] += X[i] # [GD] 틀린 애
loss_contributors_count += 1
dW[:, y[i]] += (-1) * loss_contributors_count * X[i] # [GD] 맞는 애
loss /= num_train
dW /= num_train
# [Regularization]
loss += reg * np.sum(W * W)
dW += 2 * reg * W
#############################################################################
# TODO: #
# Compute the gradient of the loss function and store it dW. #
# Rather that first computing the loss and then computing the derivative, #
# it may be simpler to compute the derivative at the same time that the #
# loss is being computed. As a result you may need to modify some of the #
# code above to compute the gradient. #
#############################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return loss, dW
def svm_loss_vectorized(W, X, y, reg):
"""
Structured SVM loss function, vectorized implementation.
Inputs and outputs are the same as svm_loss_naive.
"""
loss = 0.0
dW = np.zeros(W.shape) # initialize the gradient as zero
#############################################################################
# TODO: #
# Implement a vectorized version of the structured SVM loss, storing the #
# result in loss. #
#############################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
num_train = X.shape[0]
s = X.dot(W)
correct_score = s[list(range(num_train)), y]
correct_score = correct_score.reshape(num_train, -1)
s += 1 - correct_score
s[list(range(num_train)), y] = 0
loss = np.sum(np.fmax(s, 0)) / num_train
loss += reg * np.sum(W * W)
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
#############################################################################
# TODO: #
# Implement a vectorized version of the gradient for the structured SVM #
# loss, storing the result in dW. #
# #
# Hint: Instead of computing the gradient from scratch, it may be easier #
# to reuse some of the intermediate values that you used to compute the #
# loss. #
#############################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
X_mask = np.zeros(s.shape)
X_mask[s > 0] = 1
X_mask[np.arange(num_train), y] = -np.sum(X_mask, axis=1)
dW = X.T.dot(X_mask)
dW /= num_train
dW += 2 * reg * W
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return loss, dW
ex)
Q. 어떻게 +1을 정한거죠?
score의 절대적인 값이 아니라 score들 간의 상대적인 차이가 의미가 있는 것이고,
correct score이 incorrect score보다 상당히 높아야 하기 때문에 +1을 한 것이다.
1이라는 숫자는 미분 계산을 통해 씻겨 나가기 때문에 영향이 거의 없어서 괜찮다.
loss값은 상대적인 값임.
Q. 만약 car의 score가 조금 바뀐다면, loss 값도 변할까?
A. No, 이미 다른 틀린 score보다 1이상 크기 때문에 score가 조금 바뀌어도 loss에는 영향이 없다.
Q. multiclass SVM loss의 최소, 최대값은?
A. 최소 : 0, 최대 : 무한대
Q. correct score과 incorrect score의 차이가 거의 없다면 multiclass SVM loss는 어떻게 될까?
A. (class의 개수) - 1
=> 좋은 디버깅 툴임.
Q. multiclass SVM loss에서 max를 mean으로 변경하면?
A. 차이가 없다. loss값의 상대적인 차이가 의미가 있는 것이므로 max든 mean으로 하든간에 차이가 없다.
Q.multiclass SVM loss에서 제곱을 추가한다면?
A. 차이가 있다. 차이가 큰 값의 차이를 더 키우는 것이기 때문에 다른 의미가 된다.
Q. L = 0으로 만드는 W가 있다면, 이 값 하나 뿐일까?
A. 아니다.
Loss function은 어떤 타입의 에러를 더 고려하느냐를 결정하는 것.
loss가 0인 W가 두배가 된다고 하더라도 loss는 still 0
모델과 loss function은 training이아니라 test dataset에서 잘 작동해야한다.
training set에만 너무 fit하지 않고 제너럴한 모델을 만들기 위해서
우리는 regularization이라는 방법을 사용한다.
람다는 하이퍼파라미터인데, 굉장히 중요한 요소이다.
Regularization
L2 regularization은 w2를 선호할 것이다. norm 이 더 작기 때문에. L2는 값이 골고루 spread 되어 있는 것이 덜 복잡하다고 판단한다.
L1 regularization은 w1를 선호할 것이다. 값은 같지만, L1은 직관적으로 sparse solution(대부분이 0이고 소수만 non-zero인)을 선호하기 때문이다. L1의 complexity 측정 방식은 non-zero값의 개수일 것이다.
L2 Loss 는 직관적으로 오차의 제곱을 더하기 때문에 Outlier 에 더 큰 영향을 받는다.
L1 Loss 가 L2 Loss 에 비해 Outlier 에 대하여 더 Robust(덜 민감 혹은 둔감) 하다.
정답 확률을 모든 확률의 합으로 나눈 것에 -Log를 취한다. (KL divergence)
만약, 정답 확률이 높아서 거의 1에 가깝다면, loss는 정답 확률에 negative log를 취한 것이 될 것이다.
즉, 정답 확률이 높을수록 loss는 감소한다.
def softmax_loss_naive(W, X, y, reg):
"""
Softmax loss function, naive implementation (with loops)
Inputs have dimension D, there are C classes, and we operate on minibatches
of N examples.
Inputs:
- W: A numpy array of shape (D, C) containing weights.
- X: A numpy array of shape (N, D) containing a minibatch of data.
- y: A numpy array of shape (N,) containing training labels; y[i] = c means
that X[i] has label c, where 0 <= c < C.
- reg: (float) regularization strength
Returns a tuple of:
- loss as single float
- gradient with respect to weights W; an array of same shape as W
"""
# Initialize the loss and gradient to zero.
loss = 0.0
dW = np.zeros_like(W)
#############################################################################
# TODO: Compute the softmax loss and its gradient using explicit loops. #
# Store the loss in loss and the gradient in dW. If you are not careful #
# here, it is easy to run into numeric instability. Don't forget the #
# regularization! #
#############################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
num_classes = W.shape[1]
num_train = X.shape[0]
for i in xrange(num_train):
scores = X[i].dot(W)
scores -= scores.max()
scores_expsum = np.sum(np.exp(scores))
cor_ex = np.exp(scores[y[i]])
loss += - np.log( cor_ex / scores_expsum)
dW[:, y[i]] += (-1) * (scores_expsum - cor_ex) / scores_expsum * X[i] # [gd] 맞은 애
for j in xrange(num_classes):
if j == y[i]:
continue
dW[:, j] += np.exp(scores[j]) / scores_expsum * X[i] # [gd] 틀린 애
loss /= num_train
dW /= num_train
# [regulation]
loss += reg * np.sum(W * W)
dW += 2 * reg * W
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return loss, dW
Q. softmax의 최소, 최대값은?
A. 최소값 : 0, 최대값 : 무한대(정답 확률이 마이너스 무한대일 때)
Q. 모든 s가 거의 0에 가까울 때 loss는?
A. -log(1/C) = logC
=> senity check? => 좋은 디버깅 툴임.
correct label의 score과 incorrect label의 score의 값이 매우 차이가 나면,
SVM은 correct score가 조금 바뀌어도 loss 값에 영향이 없지만,
softmax loss값은 바뀐다.
loss function은 GT보다 얼마나 다른지 알려주는 지표가 된다.
loss를 최소화하는 W를 선택한다. -> 딥러닝 학습 과정
어떻게 W를 변경하며 최적 값을 찾을까?
optimization function
optimization function #1 random search
bad idea
optimization function #2 follow the slope
work well
slope -> derivative of a function 미분값
gradient -> the vector of partial derivative along each dimension
h만큼의 어떤 방향으로든 이동한다고 가정하면 기울기를 반환한다.
[ numeric gradient ]
모든 W값의 값의 미분값을 구한다. -> 매우 시간이 많이 걸림.
하지만, 다행히도 이 과정을 할 필요가 없다.
loss가 그 자체로 W의 함수이기 때문에, loss function에 w로 편미분을 하면 된다.
[ analytic gradient ]
Gradient Descent
W를 랜덤으로 초기화하고
weight를 계속 gradient의 반대 방향으로 업데이트한다.
gradient는 높은 지점을 향해서 가기 때문에, 반대 방향으로 마이너스를 붙여서 업데이트 한다.
Classification 태스크는 input을 넣으면 어떤 물체인지의 category를 예측한다.
사람에게는 쉽지만, 기계에게는 굉장히 어려운 일이다.
Problem : Semantic Gap
이미지는 예를 들어 800(w) x 600(h) x 3(RGB)개의0부터 255의 값으로 이루어진픽셀로 이루어져 있다.
이 이미지 정보는 semantic label을 제공하는 것 -> 하지만, 하나하나의 픽셀로 고양이 시맨틱 이미지를 인식하기는 매우 어렵다.
Challenge : 카메라의 각도가 달라짐 / 빛이 어두워지거나 / 고양이가 다른 포즈를 하거나 / 다른 물체에 숨겨져 있으면 더 어려워진다.
모든 상황을 고려하여 이미지를 분류하여야 하므로 기계에게는 매우 어려운 일이다.
여러가지 시도들
1) 모든 엣지와 코너를 찾아서 그린다.
-> not worked, 다루기 힘들고 고양이가 아닌 다른 물체는 인식 못한다.
2) Data-driven approach
- 이미지와 카테고리를 가진 데이터를 수집한다.
- 분류기를 학습하기 위해 머신러닝을 이용한다.
- 새로운 이미지에 분류기를 평가한다.
train & predict 두 과정으로 나뉜다.
-> 데이터 드리븐 방식이 딥러닝보다는 좀 더 일반적이고, 간단한 분류기를 사용할 수 있다는 점에서 좋다.
2) - a) First classifier : Nearest classifier
Nearest classifier : 학습된 데이터에서 가장 비슷한 이미지를 찾아 예측하는 알고리즘
성능이 아주 좋지는 않다.
CIFAR10 으로 테스트 해볼 것이다. 10 classes, 50000 training images, 10000 testing images
테스트 예시)
비슷한 이미지인지 아닌지는 어떤 기준으로 계산할까?
Distance Function 1 : L1 distance
학습 시에는 x와 y를 지정해주기만 하면 된다.
예측 시에는 모든 학습 이미지를 살펴 보면서 테스트 이미지와 가장 L1 or L2 distance가 작은 학습 이미지를 찾아서
그 학습 이미지의 레이블을 반환한다.
Q. how fast are training and prediction?
A. train : O(1), predict : O(N)
-> this is bad, 학습이 느리고 예측 과정은 빨라야 실제로 사용할 수 있기 때문에
결과는 어떻게 보일까?
-> 초록색 안에 노란색이 들어가 있거나
-> 초록색 영역이 파란색 영역에 침입한 것은 노이즈임
2) - b)Second classifier : K - Nearest classifier
K - Nearest classifier : top K 중에 가장 많은 투표를 받은 레이블로 선택하는 알고리즘
* X.shape = (500, 3072)
* self.X_train.shape = (5000, 3072)
# Test your implementation:
dists = classifier.compute_distances_two_loops(X_test)
print(dists.shape)
def compute_distances_two_loops(self, X):
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
for i in range(num_test):
for j in range(num_train):
#####################################################################
# TODO: #
# Compute the l2 distance between the ith test point and the jth #
# training point, and store the result in dists[i, j]. You should #
# not use a loop over dimension, nor use np.linalg.norm(). #
#####################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
dists[i][j] = math.sqrt(sum((X[i] - self.X_train[j]) ** 2))
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return dists
def compute_distances_one_loop(self, X):
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
for i in range(num_test):
#######################################################################
# TODO: #
# Compute the l2 distance between the ith test point and all training #
# points, and store the result in dists[i, :]. #
# Do not use np.linalg.norm(). #
#######################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
sum_matrix = (self.X_train - X[i]) ** 2
dists[i, :] = np.sqrt(sum_matrix.sum(axis=1)).T
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return dists
def compute_distances_no_loops(self, X):
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
#########################################################################
# TODO: #
# Compute the l2 distance between all test points and all training #
# points without using any explicit loops, and store the result in #
# dists. #
# #
# You should implement this function using only basic array operations; #
# in particular you should not use functions from scipy, #
# nor use np.linalg.norm(). #
# #
# HINT: Try to formulate the l2 distance using matrix multiplication #
# and two broadcast sums. #
#########################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
sx = np.sum(X**2, axis=1, keepdims=True)
sy = np.sum(self.X_train**2, axis=1, keepdims=True)
dists = np.sqrt(-2 * X.dot(self.X_train.T) + sx + sy.T)
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return dists
Distance Function 2 : L2 distance (=유클리디안 거리)
L1 distance는 좌표계에 따르고,
L2 distance는 좌표계에 상관없는 숫자가 되기 때문데 좀 더 매끄러운 라인을 그리는 것을 알 수 있다.
distance function을 변경함으로써 원하는 방식으로 데이터들간의 차이를 정의할 수 있다.
어떤 타입의 데이터든 일반적으로 적용할 수 있기 때문에 처음에 다가가기에 적합한 개념이다.
Hyperparameter
모델에 의해 계산되는 값이 아니라, 사람이 직접 설정해줘야 하는 파라미터
ex) K, distance function
How to set hyperparameter?
Idea #1) 가장 좋은 성능을 가져다주는 하이퍼파라미터 선택 -> Bad Idea
Idea #2) split into train and test data, test 데이터에서 성능이 좋은 하이퍼파라미터 선택 -> Bad Idea -> 새로운 데이터는 어떤게 올지 모르기 때문에
Idea #3) train, val, test 데이터로 나누기 -> Good Idea -> 새로운 데이터에도 적용될 수 있어서
* training set에는 Label을 알려주고 학습하는 거지만, validation set은 label 없고 예측하는 것임
Idae #4) cross-validation -> small dataset일 때 많이씀, deep learning x
num_folds = 5
k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]
X_train_folds = []
y_train_folds = []
################################################################################
# TODO: #
# Split up the training data into folds. After splitting, X_train_folds and #
# y_train_folds should each be lists of length num_folds, where #
# y_train_folds[i] is the label vector for the points in X_train_folds[i]. #
# Hint: Look up the numpy array_split function. #
################################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
X_train_folds = np.array_split(X_train, num_folds)
y_train_folds = np.array_split(y_train, num_folds)
X_train_cv = np.concatenate([X_train_folds[0], X_train_folds[1]])
# *****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 = {}
################################################################################
# TODO: #
# Perform k-fold cross validation to find the best value of k. For each #
# possible value of k, run the k-nearest-neighbor algorithm num_folds times, #
# where in each case you use all but one of the folds as training data and the #
# last fold as a validation set. Store the accuracies for all fold and all #
# values of k in the k_to_accuracies dictionary. #
################################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
num_valid = len(X_train) / num_folds
for kSelected in k_choices:
accuracies = []
for validIdx in range(num_folds):
X_train_cv = []
y_train_cv = []
for idx in range(num_folds):
if idx == validIdx:
X_valid_cv = X_train_folds[idx]
y_valid_cv = y_train_folds[idx]
else:
if len(X_train_cv) == 0:
X_train_cv = X_train_folds[idx]
else:
X_train_cv = np.concatenate([X_train_cv, X_train_folds[idx]])
if len(y_train_cv) == 0:
y_train_cv = y_train_folds[idx]
else:
y_train_cv = np.concatenate([y_train_cv, y_train_folds[idx]])
classifier.train(X_train_cv, y_train_cv)
dists_valid = classifier.compute_distances_no_loops(X_valid_cv)
y_valid_pred = classifier.predict_labels(dists_valid, k=kSelected)
num_correct = np.sum(y_valid_pred == y_valid_cv)
accuracy = float(num_correct) / num_valid
accuracies.append(accuracy)
k_to_accuracies[kSelected] = accuracies
# *****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))
- K-nearest classifier on images는 사용되지 않는다.
1) test time 너무 오래걸림
2) distance metrics는 이미지 데이터에 적합하지 않음
3) dimensionality 문제
Linear Classification : score function f(x, W) = Wx + b
deep learning은 레고 같은 것이고, linear classification은 가장 기본 뼈대 블럭같은 것이다.
3) Paramatic Approach
input(x), W(weight)
K-nearest는 테스트할 때 전체 이미지를 사용하지만,
Paramatic approach에서는 input 이미지를 요약하여 W라는 파라미터에 저장하고 요약본을 사용하여 테스트한다.
함수 f는 어떻게 설정할 것인가? : Linear classifier
f(x, W) = Wx
10 x 1 = (10 x 3072) x (3072 x 1)
W 사이즈의 의미는 10 categories와 3072 input pixels가 있다는 것이다.
