CS231n-2017 Lecture3線性分類器、最優化筆記

圖片向量與標簽得分向量：

上節講到，圖片可以被展開成一個向量，對于這個向量，假設它有D維，那么它就是D維空間的一個點，又假設我們的標簽集合總共有K種，我們可以定義一個K維標簽得分向量，每一個維度對應著其相應標簽的得分。那么我們就可以想辦法建立一個線性映射，將一個圖片向量映射成一個標簽向量，將其中得分最高的維度所對應的標簽作為這張圖片的標簽，這就是線性分類器的本質

即：

設訓練集 $X$ ?有N個元素,其中 $x_i\in R^D$ , 每個 $x_i$ ?有其對應的標簽向量? $y_i \in R^K$

線性分類器：

對于上述的向量對應關系

則我們可以建立一個線性分類器：

$f(x,W) = Wx+b$

其中W是一個 $K \times D$ 的矩陣，被稱為權重（權重是提前設定好的，這里我們假設模型已經找到最優權重），b是一個K維向量，被稱為偏差向量（這個向量也已經找到了最優）

這個函數會輸出對于x映射出來的標簽得分預測向量，然后我們可以根據該預測向量的最高得分維度來預測x所對應的圖片的標簽

偏差與權重的合并技巧：

我們可以將圖片向量增加至D+1維，將W也增加至 $K\times (D+1)$ ，將其第D+1列作為原本的b，則可以將函數簡化為

$f(x,W) = Wx$

線性分類器的直觀理解：

第一種理解：

對于W的第i行，其每一列的元素分別就是D維圖片向量對應像素對第i行對應標簽的貢獻權重，當權重為正時，就說明該位置（包含了長、寬、顏色三個信息）的像素值對該標簽分類是正貢獻，且越高越好，權重為負時相反

同時，我們可以將第i行這一行向量映射回圖片三維數組，從而得到該標簽所對應的圖片模版，可以直觀地觀察到其分類喜好

第二種理解：

對于第i個標簽，如果我們將所有令 $f(x,W)$ ?的第i個分量為0的所有x向量組成一個平面，那么這個平面就是第i個標簽的分界面，雖然高維空間不好想象，但我們可以將D維空間當做二維平面來理解，此時分界面必有一邊會使得第i個分量的值>0（則這個區域就是第i個標簽所屬的區域），而另一面會使得第i個分量的值<0（第i個標簽所不屬于的區域）。那么對于K個標簽來說，就會有K個分界面，將D維空間線性劃分為K個標簽所屬的區域，因此我們只需要判斷輸入圖像向量落入哪個區間，即可預測其標簽

Loss Function（損失函數）：

對于不同的權重矩陣W，我們需要對其給出的預測向量評分，從而評價其預測結果的好壞，這里，我們使用Loss Function作為評分標準，Loss越大時，預測結果越差，Loss越小時，預測結果越好

Multiclass Support Vector Machine Loss(多類支持向量機損失):

這是眾多形式Loss中的一種，被稱為折葉損失(hinge loss)，具體定義式為：

$L_i = \sum_{j \ne y_i}{max{(0,s_j-s_{y_i}+\Delta)}}$

$L=\frac{1}{N}\sum_{i=1}^{N}{L_i}$

其中 $L_i$ ?是對第i個圖片向量預測的損失， $L$ ?是總損失， $y_i$ ?是 $x_i$ 所對應的標簽所對應的維度， $j$ 是遍歷維度， $s_j$ 是預測向量在j維度所對應的預測值， $s_{y_i}$ 是預測向量在 $y_i$ 維度所對應的預測值， $\Delta$ 是自定義超參數

$max{(0,s_i-s_{y_i}+\Delta)}$ ?的含義就是，我們遍歷預測向量的每一維度（除了正確標簽所對應的維度），即遍歷的都是錯誤標簽所對應的維度，若正確標簽得分減去該錯誤標簽得分的差少于 $\Delta$ ?，則說明預測得分的差距不夠大，對Loss作出了一定貢獻，否則對Loss的貢獻為0

由此可見， $\Delta$ 是我們所預期的正確維度與錯誤維度所需要拉開的差距

正則化(Regularization):

上面的損失函數會有一個問題，使得分類器能夠正確分類數據集內每個數據的W并不唯一，我們希望能向W中某些特定的權重添加一些偏好，對其他權重則不添加，從而來更好地區分每個滿足分類Loss為0的W，即向損失函數增加一個正則化懲罰 $R(W)$ ?部分

通常采用L2范式，即：

$R(W) = \sum_k\sum_lW_{k,l}^2$

即對W中所有元素平方后求和作為正則化懲罰，它不是數據的函數，僅僅是權重的函數

至此，我們可以給出完整的多類SVM損失函數，由數據損失和正則化損失組成，即

$L = \frac{1}{N}\sum_i{L_i}+\lambda R(W)$

其中 $\lambda$ 也是超參數，需要具體確定正則化懲罰的的權重

L2正則化最好的性質就是能對大數值權重進行懲罰，進而提升模型的泛化能力，因為平方項對大數值的懲罰更為嚴厲，導致沒有哪個維度能獨自于整體有過大的影響，鼓勵分類器將所有維度的特征都用上，最后體現出來就是訓練出來的模型的權重參數更小更分散

需要注意的是，偏差b沒有這樣的效果，因為它并不影響輸入向量的維度所造成的得分影響，因此通常只對權重W進行正則化，而不正則化b

由于正則化懲罰的存在，導致Loss通常不為0，因為當且僅當W=0時Loss才為0

Softmax分類器

Softmax分類器的損失函數與SVM不同，本質上是邏輯回歸分類器在面對多個分類時的拓展，其Loss稱為交叉熵損失(cross-entropy loss)，公示如下：

$L_i = -log(\frac{e^{f_{y_i}}}{\sum_j{e^{f_j}}})$ ?, 又等價于? $L_i = -f_{y_i} + log(\sum_j{e^{f_j}})$

其中 $f_j$ 為標簽得分向量的第j維分量

softmax函數：

$f_j(z) = \frac{e^{z_j}}{\sum_k{e^{z_k}}}$

簡單理解為函數對第j個維度進行壓縮，輸出一個在 $[0,1]$ ?的值，可以把它看作分類到該標簽的概率

cross-entropy Loss的合理性解釋：

信息論解釋：

定義在“真實”分布p與估計分布q之間的交叉熵如下：

$H(p,q) = -\sum_xp(x)logq(x)$

顯然，當估計分布q越接近真實分布p時，H越小

而我們的Loss函數公式恰好對應的就是真實概率分布p(假設是標簽j，那么就是第j維為1，其余維度全為0的向量)，與估計分類概率分布q，即預測出來的標簽得分向量通過指數歸一化處理的映射出來的概率分布，又由于p(x)只在x=j時為1，其余為0，因此H的求和只保留了x=j的項，即q(x)所對應的就是 $\frac{e^{f_{y_i}}}{\sum_je^{f_j}}$

所以我們最小化Loss時，就是在使得q分布逐漸逼近p分布

有，交叉熵可以寫成KL散度(KL divergence)的形式，即

$H(p,q) = H(p) + D_{KL}(p||q)$

又 $H(p) = -\sum{p(x)log{p(x)}} = 0$

所以本質上就是對分布p與分布q的KL散度做最小化，而KL散度正是用來判斷兩個分布在信息上的的相似程度的

概率論解釋：

給出公式，在給定 $x_i,W$ 的條件下，我們預測出 $y_i$ 的概率為

$P(y_i|x_i,W) = \frac{e^{f_{y_i}}}{\sum_j{e^{f_j}}}$

而我們的Loss可以看作是歸一化處理后，正確標簽的負對數概率，我們在最小化這個值，就是在最大化正確標簽的概率，從而去求出其對應的W參數，即可以看作是在對W參數進行最大似然估計(MLE)

實際計算時的注意事項：

對于sofmax函數來說，存在指數即有可能存在大數值，而對大數值進行除法會導致數值計算的不穩定，因此我們需要對公式進行等價變形：

$\frac{e^{f_{y_i}}}{\sum_j{e^{f_j}}} = \frac{Ce^{f_{y_i{}}}}{C\sum_je^{f_j}} = \frac{e^{f_{y_i}+logC}}{\sum_j{e^{f_j+logC}}}$

這里，我們選定 $logC = -max_jf_j$ ，將所有分量的元素平移，使得最大值為0，從而避免了單個大數值的出現

SVM與Softmax的比較：

兩種分類器都是接受輸入圖片向量，然后輸出對應的評分向量f

但SVM輸出的f中的元素值被看作是分類評分，它的損失函數鼓勵正確標簽的得分至少要比錯誤標簽的得分高出 $\Delta$

而Softmax輸出的f中的元素值被看作是該標簽對應的未進行歸一化的對數概率，鼓勵正確標簽的概率變高，而錯誤標簽的概率變低

因此，SVM的計算是沒有標定的，無法對各個維度的評分值給出直觀地解釋，而softmax的輸出可以簡單地理解為該維度標簽所對應的“概率”

在softmax中，輸出的概率的分布的集中/離散程度是會由正則化參數 $\lambda$ ?直接決定的

當 $\lambda$ 越大，權重W被懲罰的越多，數值越小，這樣算出來的各個分量的分數也會更小，則導致各個標簽的概率更為接近，也就是概率的分布更為分散了。隨著 $\lambda$ 的增大，最后輸出的概率會接近于均勻分布

最優化問題

有了上述的前提，我們現在所需要做的就是，在給定超參數的前提下，如何去找到使得Loss最小的W參數

梯度下降法：

在給定數據集輸入的前提下，我們可以將W矩陣中的所有參數看作Loss函數的變量，假設有 $n=K\times (D+1)$ 個變量，那么Loss函數就是一個n維函數，最小化Loss問題其實就是一個函數優化問題，實際這個函數可能非常復雜，因此我們無法通過求駐點的方法求出極小值，則需要使用梯度下降法

我們求出Loss函數在給定 $x_i$ 這一點關于n個變量的偏導數，這n個導數組成的向量稱為梯度，梯度向量所指向的方向就是在該點處函數圖像上升最陡峭的地方，如果我們向著這個方向的反方向前進一小步（這里稱作步長，又學習率，是一個重要超參數），那么就會以最快的速度下降，然后再重復迭代，直到落入局部極小值

即有公式：

$W_t = W_{t-1} - \alpha\nabla_W L(x_i,y_i,W_{t-1})$