Linear classification – image classification

cs231n은 참 명강의이다. 처음 딥러닝을 이 강의로 접했다.

linear classification을 보면서 맨처음 접했던 Andrew Ng 교수님 초보 머신러닝 강의(코세라)와 개념 이어붙이느라 고생했다.

그 때 정리했던 노트를 올려본다.

cs231n module1 – Linear classification

Image Classification 

assigning a single label to an image

KNN classifier by comparing them to images from training set

(this causes space problem, and classifying a test image is very expensive)

-> linear regression 으로 정의해서 결국 Convolutional neural network 로 발전하도록 한다.

  • score function / loss fuction
1) Score function
maps the pixel values to confidence scores for each class(image class)

Linear classifier looks like this. :

  • image의 모든 pixel이 single column [D x 1]으로 펼쳐져 있다고 가정함.

  • W, b : parameters

  • cifar-10 데이터에서 xi는 i번째 이미지의 모든 pixel 정보를 하나의 [3072 x 1] column에 담고 있음.

  • 3072 개의 숫자(raw pixel value)가 function에 들어오고, 10 개의 숫자가 나온다.(class scores)

(cifar-10 데이터 자체가 10 seperate classifier in parallel (one for each class) 를 가지고 있기 때문)

  • (xi, yi)를 가지고 parameter를 도출해 낸다.

  • training 이 끝난 뒤 learned parameter만 남기고 training set은 날려버려도 괜찮다.

Interpreting a linear classifier

score : weighted sum of all pixel values across all 3 of its color channels

예를 들어, ship class의 classifier는 blue channel에 positive weight을 많이 가지고 있을 것이다.

이론적으로는 3072 차원에서 각 이미지는 한 점으로 존재한다.

이것을 굳이 2개의 차원으로 압축시켜서 의미를 해석해보자면 다음과 같은 그림이 될 것 이다.

W의 모든 row는 하나의 class를 위한 classifier가 될 것이다.

(참고로, b가 없으면 모든 line들이 원점을 지날 것이다.)

Interpretation of linear classifier as template matching.

W에 대한 해석은 W의 모든 row가 하나의 template(혹은 프로토타입)이 된다는 것이다.

이 경우 score는 이미지가 그 프로토타입과 얼마나 비슷한지에 대한 값이 될 것이다.

The linear classifier is too weak to properly account for different-colored cars, but as we will see later neural networks will allow us to perform this task. Looking ahead a bit, a neural network will be able to develop intermediate neurons in its hidden layers that could detect specific car types (e.g. green car facing left, blue car facing front, etc.), and neurons on the next layer could combine these into a more accurate car score through a weighted sum of the individual car detectors.

 

Linear classifier는 다양한 색의 자동차를 구분한다던지 하는 더 복잡한 문제를 해결하기엔 너무 약한다. Neural Network는 내부에 레이어를 추가함으로써 더 정확한 구분을 할 수 있게 되는 것이다. (단순히 생각해서는 추론의 단계가 추가되는 것으로도 볼 수 있다.)

Adding biases

Matrix의 맨 마지막에 bias column을 추가한다. CIFAR-10 데이터에 대한 모델링에서 따져보면 [3072 x 1] 행렬이 아니라 [3073 x 1] 행렬이 되는 것이다.

* data preprocessing 

 

또한가지 필요한 작업이 image data preprocessing 이다.

– input feature들의 값을 모두 normalization을 해주어야 한다. 

– 0 ~ 255의 값을 갖는 pixel data의 경우 center하기 위해서  -127~127로 바꾼 후, 이를 다시 -1 ~ 1로 스케일링 해주어야 한다. (gradient descent 를 위해서 필요)

 

 

2) Loss function

 

: Cost function, Objective

The loss will be high if we’re doing a poor job of classifying the training data. (low when we’re doing well)

 

 

Multiclass support vector machine(SVM) loss

– The SVM loss is set up so that the SVM “wants” the correct class for each image to a have a score higher than the incorrect classes by some fixed margin Δ.

– The SVM “wants” a certain outcome in the sense that the outcome would yield a lower loss (which is good).

 

The score for the j-th class (j-th element of output of score function) :

The multiclass SVM loss for the i-th example :

Example)

Suppose that we have three classes that receive the scores s=[13,−7,11]

and that the first class is the true class (i.e. yi=0).

Also assume that Δ(a hyperparameter we will go into more detail about soon) is 10.

The expression above sums over all incorrect classes (j≠yi),

so we get two terms:

max(0, −7−13+10) + max(0, 11−13+10)

여기서 첫번째 term은max(0, -10)이라서 0이 되고,

두번째 term은 max(0, 8)이라서 8이 된다.

Loss function의 의미는 맞게 추측한 클래스에 대한 score와 잘못 추측한 클래스에 대한 score의 차이가 delta 이상이어야만 loss가 아니라고 판단하는 것이다.

여기서도 Regularization을 할 필요가 있다.

(W의 여러배수(1이상의 수를 곱한)도 모두 loss function을 만족할 수 있기 때문에)

식으로 풀어쓰면,   (N : training example의 갯수)

python 코드로 작성하면 다음과 같다.


def L_i(x, y, W):

"""

unvectorized version. Compute the multiclass svm loss for a single example (x,y)

- x is a column vector representing an image (e.g. 3073 x 1 in CIFAR-10)

with an appended bias dimension in the 3073-rd position (i.e. bias trick)

- y is an integer giving index of correct class (e.g. between 0 and 9 in CIFAR-10)

- W is the weight matrix (e.g. 10 x 3073 in CIFAR-10)

"""

delta = 1.0 # see notes about delta later in this section

scores = W.dot(x) # scores becomes of size 10 x 1, the scores for each class

correct_class_score = scores[y]

D = W.shape[0] # number of classes, e.g. 10

loss_i = 0.0

for j in xrange(D): # iterate over all wrong classes

if j == y:

# skip for the true class to only loop over incorrect classes

continue

# accumulate loss for the i-th example

loss_i += max(0, scores[j] - correct_class_score + delta)

return loss_idef L_i_vectorized(x, y, W):

"""

A faster half-vectorized implementation. half-vectorized

refers to the fact that for a single example the implementation contains

no for loops, but there is still one loop over the examples (outside this function)

"""

delta = 1.0

scores = W.dot(x)

# compute the margins for all classes in one vector operation

margins = np.maximum(0, scores - scores[y] + delta)

# on y-th position scores[y] - scores[y] canceled and gave delta. We want

# to ignore the y-th position and only consider margin on max wrong class

margins[y] = 0

loss_i = np.sum(margins)

return loss_i

def L(X, y, W):

"""

fully-vectorized implementation :

- X holds all the training examples as columns (e.g. 3073 x 50,000 in CIFAR-10)

- y is array of integers specifying correct class (e.g. 50,000-D array)

- W are weights (e.g. 10 x 3073)

"""

# evaluate loss over all examples in X without using any for loops

# left as exercise to reader in the assignment

 

 

Practical Considerations

  • Delta 세팅

hyperparameter 두가지 Δ and λ를 어떻게 세팅할 것이냐.

이 때, data loss와 regularization loss 두가지는 상충되며 tradeoff가 발생한다.

W의 크기는 score에 직접적인 영향을 준다.

W안의 모든 값들을 압축할 수록 score의 차이는 줄어들 것이다. (반대로도 마찬가지)

그러므로, score들 간의 정확한 margin은 사실상 의미가 없다. weight로 하여금 그 차이를 임의로 늘리거나 줄어들게 할 수 있기 때문이다. 그러므로 사실상 의미 있는 tradeoff 는 regularization strength λ를 통해서 weight이 얼마 커지도록 하는지 이다.

  • Binary Support Vector Machine과의 관계

Binary SVM에서 loss는 다음과 같다.:

이는 우리가 도출한 수식에서 class가 두개인 경우라고 볼 수도 있는 것이다.

Softmax classifier

SVM 이외에 가장 많이 사용되는 classfier.

당신이 binary logistic regression을 공부해봤다면, Softmax classifier는 그것을 multiple class에 대해서 일반화 한 것이다.

SVM은 f(x, W)를 각 클래스에 대한 score로 사용하지만, Softmax는 normailized class probability로 활용한다. (각 클래스에 대한 정규화된 확률)

먼저 unnormalized된 log 확률을 계산해서 hinge loss(SVM에서의)를 대체한다. 이것이 Cross-entropy loss 이다.

  • Cross-entropy loss 수식 :

(여기 fj는 score 벡터 f의 j번째 element이다.)

모든 training example들의 Li의 평균이 dataset의 full loss이다.

<참고>

기존에 Neural Network 강의에서 살펴본 cross-entropy function은 다음과 같았다.

(a는 sigmoid를 사용)

필요성 : 기존 quadratic cost function으로 learning 할 경우, sigmoid function의 양쪽 끝에서 이동할 경우 learning 이 매우 느리다는 단점을 보완하기 위해서 정의한 cost function이었음.

여기서 사용하는 건 살짝 다른 듯 하다.

이 부분을 softmax function이라고 부른다.
이 부분은 임의의 score값의 벡터를 취해서 0 ~ 1 사이의 확률값으로 만든다. (이 값들의 총합이 1이 된다.)

(총합에서 나누는 것은 1보다 작은 확률값으로 normalize하기 위함.)

  • Information theory view

True distribution p 와 estimated distribution q 사이의 cross-entropy는 다음과 같이 정의된다. :

(뉴럴넷 강의에서 본 식과 같음)

class 추정 확률 :

따라서 Softmax classifier는 추정 확률과 실제 분포 사이의 cross-entropy를 최소화하게 된다.

여기서 실제(true) 분포는 모든 확률 값이 정확하게 분포 되어 있는 벡터이다.

p = [0,0,…,1,…0] 이런 식으로 맞는 클래스에만 1로 되어 있는 벡터.

cross-entropy 는 entropy와 Kullback-Leibler divergence로 표현될 수도 있다.

여기서, delta function p의 entropy는 0이기 때문에, 결국 두 분포의 KL divergence를 최소화 하는 것이 cross-entropy를 최소화하는 것이나 마찬가지다.

다시 말하면, cross-entropy의 목적은 추정 확률분포가 모든 값을 correct answer부분에만 갖도록 하고 싶어 한다는 것이다.

  • Probabilistic interpretation : 확률론적 접근으로의 해석

이 수식은 image xi에 대해 W를 이용해서 올바른 label yi 가 매겨질 확률(normalized된 확률)이다.

위에서 살펴본 것처럼,

Sofmax classifier는

output 벡터 f안의 score들을

정규화가 아직 안된(unnormalized) log 확률로 여긴다.

이 값들을 Exponentiating 함으로써 probability를 얻을 수 있고, (아직 unnormalized)

이를 총합으로 나눔으로써 normalized 하게 되는 것이다.

이를 해석하자면,

올바른 class에 대한 negative log likelihood을 최소화하게 되는 것이다.

: Maximum Likelihood Estimation (MLE)

이런 관점이 좋은 이유는, regularization에 대한 해석이 가능하다는 것인데,

full loss function에서의 R(W)는,
a Gaussian prior over the weight matrix W (MLE 대신 Maximum a posteriori estimation을 실행할 경우의) 이라고 할 수 있다.

Practical issues : numeric stability

실제 softmax function을 코딩하게 되면

이 두가지 요소의 숫자 크기가 매우 클 가능성이 있고, 그로 인해 계산이 불안정할 수 있다.

그래서 약간의 normalization trick을 쓰는 것이 좋다.

C를 분모, 분자에 곱해서 숫자의 크기를 줄여주는데 이 식을 전개하면 다음과 같음.

C의 값은 마음대로 정해도 되고, 결과에 변화를 주지 않는다.

C의 값을 정하는데 주로 이용되는 방법은

로 정하는 것이다.

(이렇게 대입하면 벡터 f내의 가장 큰 값을 0으로 만들어버리게 된다.)


f = np.array([123, 456, 789]) # example with 3 classes and each having large scores

p = np.exp(f) / np.sum(np.exp(f)) # Bad: Numeric problem, potential blowup# instead: first shift the values of f so that the highest number is 0:

f -= np.max(f) # f becomes [-666, -333, 0]

p = np.exp(f) / np.sum(np.exp(f)) # safe to do, gives the correct answer

 

  •  Naming convention에서 헷깔릴 수 있는 부분

SVM 에서는 hinge loss를 사용한다. (max-margin loss라고도 함.)

Softmax 는 cross-entropy loss를 사용한다.

정확하게 따지만 ‘softmax loss’라는 단어는 없다. (softmax는  normalization으로 줄여주는 함수일 뿐) 다만, 줄여서 그런 용어를 사용하기도 함.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s