CS231n SVM vs Softmax for Classification

by allenlu2007

 

Stanford CS231n Convolutional Neural Network for Visual Recognition

是非常用心的 lecture notes.  由淺入深的引導,類似 Cioffi 的 digital communication class.

唯一可惜是沒有 video lecture!

 

先介紹 Supervised learning classification (就是有 training dataset) 的整體 framework:

Image classification 是其中一個應用,其他應用包含 spam classification, disease diagnose, etc.

注意 regression 問題可視為 discrete classification 擴展到 continuous classification (roughly), 請自行 generalize.  

 

Classification Framework:

1. 定義一個 Parameterized score function

可以 map input data (raw image pixels) to class scores.  (e.g.  linear mapping, logistic mapping, neural network, deep neural net)

parameter (space) 就是 W, weight vectors, 或是 filter, etc.  

如果 parameter space dimension >> training dataset dimension  –>  小心 overfit (太多 W 可以滿足), 加上 regulation, or reduce dimension (share weight, pooling, PCA/ICA, etc.)

如果 training dataset dimension >>  parameter space dimension –>  小心 underfit (W 的 dimension 不夠), expand W dimension.

最簡單的 parameterized score function 是 linear function: 

NewImage

 

2. 定義 Loss function

Loss function measures the “loss” based on scores agree with golden labels of the training data.   有很多 loss function 定義。本文比較兩種常見的 loss function for classification, i.e. Softmax and SVM.  

比較之下, regression 的 loss function 一般比較直覺,例如  L1 norm or L2 norm, 或是再加上 regulation.  

SVM 的 hinge loss function 如下。

NewImage

Softmax 的 cross entropy loss function (one dataset) 如下。這部份後面會再 elaborate.

NewImage

 

3.  最後一步就是 optimization 算法

對於 convex loss function (w.r.t. W) 已有現成的解法。例如一般的 L1 or L2 norm plus linear score function.  但是 neural network 的 score function 是 nonlinear function.  即使 loss function 是 convex function, 整體 loss function w.r.t W 非 convex function.  因此需要不同的算法。最常見的算法是 gradient descent and derivative (GD, SGD, SGD with momentum, conjugate GD).      

 

 

Loss Function

 

For binary –> logistic and SVM difference?

For classification ->  how to count correct and error ‘s loss in softmax and SVM. 

compare with regression.   Regression is simple,  loss = ( predict – truth )’s L1 or L2 norm

For classification, how to count loss? 

1.  Correct :  loss = 0;   Error:  loss = fixed value  ==>  Hinge loss:  loss=0;  Error: within margin linear loss, out of margin fixed loss?

2. Probability distribution, 引入新的 pdf (or pmf), 以機率角度來算 loss (entropy loss!!).  有趣的是 regulation 可視為 Gaussian prior distribution!  (MLE and MAP,  無 regulation -> MLE;  有 regulation -> MAP)

3. discrete to continuous? easy or not that easy?

 

 

Softmax classifier 先從 Logistic regression 開始

Softmax 其實是 logistic regression 的 generalization.  先從 logistic regression/classifier 開始。

Logistic regression 的 input variable 是 continuous, 但 outcome 是 binary 0 或 1.  這和 linear regression 有顯著不同。

因些產生兩個問題:  (1) 如何解釋 regression coefficient (and outcome)?   (2) 如何計算 golden dataset 的 loss/error (for regression)?

關於 (1), 可以參考本文如下。

“傳統線性迴歸的迴歸係數(regression coefficient)的解釋為「當自變項增加一個單位,依變項則會增加多少單位」,但是在Logistic regression的迴歸係數解釋為「當自變項增加一個單位,依變項1相對依變項0的機率會增加幾倍」,也就是說「自變項增加一個單位,依變項有發生狀況(習慣稱為Event)相對於沒有發生狀況(non-event)的比值」,這個比值就是勝算比(Odds ratio, OR)。我們可以這樣說,除了迴歸係數的解釋方法不太相同之外,基本上可說傳統線性迴歸跟Logistic regression是一樣的分析。”

Linear regression coefficient 基本上就是 linear function 的斜率。對於 logistic regression 需要引入機率的觀念。也就是 odd ratio.  不過似乎要加上 log function 才會得到斜率。換言之是 log likelihood (log 似然率).  如下推導。

pi(x|x=1) = exp(ax) / (1+ exp(ax))    pi(x=0) = 1 – pi(x) = 1 / (1+exp(ax))     odd ratio = exp(ax)   log(odd ratio) = ax

 

關於 (2), 可以參考本文如下。

如何計算 loss/error function?  為什麼要算 loss/error function?  因為這是 regression 是 optimization 問題,需要 minimize error/loss function.

Linear regression 一般解釋是 least square error minimization, 沒有機率概念在其中。

但也可以用機率角度是,  Y = a x + b + E,  X, E 是 random variable with Gaussian pdf,  a and b 是 maximum likelihood estimation 的結果。和非機率結果一樣。MLE 的 loss function 

回到 logistic regression,  Y = f(a x + b + E)   Y 只有 0 or 1, Bernoulli variable.  E 是 Logistic distribution.  所以如何找到 a and b. 

其實是用和 linear regression 同樣的 trick.  就是 maximum likelihood estimation 的結果。或是用 loss function 如下,解題重點就是 arg max (w) to maximize probability or reduce loss function.

Assuming yi = +1/-1, loss function 如下:

NewImage

Assuming yi = +1/0, loss function 如下:

NewImage 

 

如何算 Softmax?  

明顯計算 log (odds ratio) 並不適用在 multiple discrete outcome 的情況。要如何求解?

其實可以 generalize by minimizing loss function.  先定義 loss function ( = -1 * log(probability) ), minimize loss = maximize probability (MLE)

NewImage

Logistic function (CDF) = prob(X>x) = 1/(1+exp(-(ax+b)))

f(xi; W) = W xi = ax + b

normalize probability

exp(ax)/ (exp(ax) + exp(b)) = 1 / (1 + exp(ax+b)

 

Softmax

f(xi, W ) = W xi

assuming 

x                -4  -3  -2  -1   0   1   2  3  4  

outcome    0     0   1   0   1   0   1  1  1

-4      -3        -2          -1       0         1         2         3            4

log0  log0  log1/5  log1/5  log2/5  log2/5 log3/5 log4/5    log5/5 

 

 

Total loss L0 + L1 = -fo + log(exp(0) + exp(1)) – f1 + log(exp(0) + exp(1))

 

 

Advertisements