線性分類

在上一節(jié)我們介紹了圖像分類和KNN但是他有很多缺點：分類器必須記住所有的訓(xùn)練數(shù)據(jù)并且存儲下來以備未來的比較萤彩，這一塊是非常低效的并且容易造成內(nèi)存爆炸粪滤，計算效率低。
現(xiàn)在我們用一種更加有力的方式來做圖像分類雀扶，然后我們將進(jìn)一步展開神經(jīng)網(wǎng)絡(luò)和卷積神經(jīng)網(wǎng)絡(luò)的介紹杖小，在這個部分我們有兩個地方值得介紹，一個score function 一個loss function愚墓。我們將用score function的參數(shù)來最優(yōu)化loss function 并以此來解決最優(yōu)化問題予权。

從圖像到標(biāo)簽分?jǐn)?shù)的參數(shù)化映射

該方法的第一個組成部分是定義將圖像的像素值映射到每個類的置信度得分的分?jǐn)?shù)函數(shù)。我們將以具體的例子開發(fā)這種方法转绷。像以前一樣伟件，我們假設(shè)一個圖像xi∈RDxi∈RD的訓(xùn)練數(shù)據(jù)集，每個都與標(biāo)簽yiyi相關(guān)聯(lián)议经。這里i = 1 ... Ni = 1 ... N和yi∈1...Kyi∈1... K斧账。也就是說谴返，我們有N個例子（每個都有維度D）和K個不同的類別。例如咧织，在CIFAR-10中嗓袱，我們有一組訓(xùn)練集N = 50,000圖像，每個D = 32 x 32 x 3 = 3072像素习绢，K = 10渠抹，因為有10個不同的類（狗，貓闪萄，汽車等） ）梧却。我們現(xiàn)在將定義分?jǐn)?shù)函數(shù)f：RD?RKf：RD?RK，將原始圖像像素映射到類分?jǐn)?shù)败去。
線性分類器放航，在這塊我們將用最簡單的函數(shù)來做：
$f(x_i,W,b)=Wx_i+b$
在上述等式中，我們假設(shè)圖像$x_i$將其所有像素平坦化為單個[Vx]形列列向量圆裕。矩陣W（尺寸[K×D]）和向量b（尺寸[K×1]）是函數(shù)的參數(shù)广鳍。在CIFAR-10中，$x_i$將第i個圖像中的所有像素均勻化為單個[3072×1]列吓妆，W為[10 x 3072]赊时，b為[10 x 1]，因此3072個數(shù)字進(jìn)入該函數(shù)原始像素值）和10個數(shù)字（類分?jǐn)?shù)）行拢。 W中的參數(shù)通常稱為權(quán)重祖秒，b稱為偏置向量，因為它影響輸出分?jǐn)?shù)剂陡，但不與實際數(shù)據(jù)$x_i$進(jìn)行交互狈涮。但是，您經(jīng)常會聽到人們可以互換使用術(shù)語權(quán)重和參數(shù)鸭栖。
首先$Wx_i$可以有效的評估十個類別的得分歌馍，每個都是W的一行；其次輸入的數(shù)據(jù)是固定的晕鹊，我們必須控制參數(shù)松却；在學(xué)習(xí)的時候我們需要用到train的set但是學(xué)完了之后就可以把訓(xùn)練集丟掉了；最后分類牽扯到矩陣的相乘和相加溅话；

將圖像映射到類分?jǐn)?shù)的示例晓锻。為了可視化，我們假設(shè)圖像只有4個像素（4個單色像素飞几，我們在這個例子中不考慮色彩通道砚哆，以簡潔），我們有3個類（紅色（貓）屑墨，綠色（狗）躁锁，藍(lán)色（船）班）纷铣。 （說明：這里的顏色特別簡單地表示3個類，與RGB通道無關(guān)战转。）我們將圖像像素拉伸成一列搜立，并執(zhí)行矩陣乘法以得到每個類的分?jǐn)?shù)。請注意槐秧，這個特定的一組權(quán)重W不是很好：權(quán)重分配我們的貓圖像是一個非常低的貓分?jǐn)?shù)啄踊。特別是，這套重量似乎相信它正在看著一只狗刁标。
圖像類似于高維點颠通。由于圖像被拉伸成高維列向量，我們可以將每個圖像解釋為該空間中的單個點（例如命雀，CIFAR-10中的每個圖像是32×32×3像素的3072維空間中的點）蒜哀。類似地，整個數(shù)據(jù)集是一個（標(biāo)記）的點集合吏砂。

由于我們將每個類的分?jǐn)?shù)定義為所有圖像像素的加權(quán)和，所以每個類得分是該空間的線性函數(shù)乘客。我們無法可視化3072維的空間狐血，但是如果我們想像將所有這些維度壓縮到只有兩個維度，那么我們可以嘗試可視化分類器可能在做什么

損失函數(shù)

在上一節(jié)中易核，我們定義了從像素值到類得分的函數(shù)匈织，由一組權(quán)重WW參數(shù)化。此外牡直，我們看到我們無法控制數(shù)據(jù)（$x_i$缀匕，$y_i$）（$x_i$，$y_i$）（它是固定的和給定的）碰逸，但是我們確實控制了這些權(quán)重乡小，我們想設(shè)置它們，使得預(yù)測課程分?jǐn)?shù)與訓(xùn)練數(shù)據(jù)中的實地標(biāo)簽一致饵史。
例如满钟，回到貓的示例圖像及其分類“貓”，“狗”和“船”的分?jǐn)?shù)胳喷，我們看到這個例子中的特定權(quán)重集不是很好：我們喂在描繪一只貓的像素中湃番，與其他類別（狗得分437.9和船分?jǐn)?shù)61.95）相比，貓分?jǐn)?shù)非常低（-96.8）吭露。我們將用失敗函數(shù)（有時也被稱為成本函數(shù)或目標(biāo)）來衡量我們對于不幸的結(jié)果吠撮。直觀地說，如果我們在對培訓(xùn)數(shù)據(jù)進(jìn)行分類工作方面做得不好讲竿，那么損失將會很高，如果我們做得很好侵浸，這將會很低范咨。

## 多類支持向量機損失

這里寫圖片描述

我們應(yīng)該選擇更小的權(quán)重這樣使得過擬合的現(xiàn)象更加不明顯侯勉，另一點很重要的是我們永遠(yuǎn)無法達(dá)到0損失鹦筹，一般我們會給w加正則項而不會給b加。

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_i

def 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

實際應(yīng)用

Delta的設(shè)定：Δ=1.0 實際上在任何情況下都是安全的設(shè)定址貌，Δ與$\lambda$ 是兩個不同的參數(shù)但是他們都控制同樣的tradeoff铐拐，（正則損失和準(zhǔn)確率的損失）。理解他的要點是W的量級對于score的效果有著直接的影響练对，當(dāng)我們縮小W的時候遍蟋，score也會降低，因此score的絕對值不重要螟凭，重要的是相對值虚青。因此應(yīng)該做差。

二元支持向量機赂摆，有以下的表達(dá)方法：
$L_i = C \max(0, 1 - y_i w^Tx_i) + R(W),y_i \in { -1,1 }$
此時有：$C \propto \frac{1}{\lambda}$

原始優(yōu)化挟憔。如果你以前知道SVM來到這個課程，你可能還聽說過內(nèi)核烟号，雙重绊谭，SMO算法等。（和Neural Networks的情況一樣）汪拥，我們將一直與優(yōu)化目標(biāo)在其無約束的原始形式达传。這些目標(biāo)中的許多在技術(shù)上是不可區(qū)分的（例如，max（x，y）函數(shù)不是因為當(dāng)x = y時具有扭結(jié)）宪赶，但實際上這不是問題宗弯，并且常見的是使用子梯形圖。

多分類的支持向量機搂妻。值得提到的是本文提到的方式只是構(gòu)造多分類的svm的一種方法蒙保，除此之外 one-vs-all也是一種常用方法，他是獨立對各個類構(gòu)造SVM欲主。我們的構(gòu)造遵循Weston和Watkins 1999版本邓厕，這是一個比OVA更強大的版本（在這個意義上，您可以構(gòu)建多版本的數(shù)據(jù)集扁瓢，其中該版本可以實現(xiàn)零數(shù)據(jù)丟失详恼，但是OVA不能）。您可能會看到最后一個表達(dá)式是一個結(jié)構(gòu)化SVM引几，它可以最大限度地提高正確類的得分和最高評分不正確的亞軍類的得分昧互。了解這些配方之間的差異超出了課堂的范圍。這些說明中提供的版本是在實踐中使用的一個安全的賭注伟桅，但可以說是最簡單的OVA策略也可能會起作用（Rikin等人2004年“一維全部分類防御”

Softmax分類器

事實證明敞掘，SVM是兩個常見的分類器之一。另一個受歡迎的選擇是Softmax分類器贿讹，它具有不同的損耗函數(shù)渐逃。如果您以前聽說過二進(jìn)制邏輯回歸分類器，那么Softmax分類器就是將它推廣到多個類民褂。不想SVM，softmax給了一些更加直觀的輸出液給了概率的輸出疯潭。$f(x_i; W) = W x_i$是保持不變的赊堪，但是我們現(xiàn)在用了非標(biāo)準(zhǔn)化的log概率形式代替了之前的cross-entropy 的損失：
$L_i = -\log\left(\frac{e^{f_{y_i}}}{ \sum_j e^{f_j} }\right) \hspace{0.5in} \text{or equivalently} \hspace{0.5in} L_i = -f_{y_i} + \log\sum_j e^{f_j}$
從信息論的角度，熵表示真實的分布和估計分布：$H(p,q) = - \sum_x p(x) \log q(x)$而softmax就是最小化熵增竖哩，也就是最小化真實分布與估計分布哭廉。
從穩(wěn)定性來看，由于加了一個指數(shù)分布相叁，分子和分母都會非常大遵绰，所以這個相除就會很不穩(wěn)定，因此要用標(biāo)準(zhǔn)化的技巧增淹，所以我們就在上面乘上一個常數(shù)C并且把它加進(jìn)去椿访，我們可以自由的決定C的大小，所以我們可以用C來控制函數(shù)的穩(wěn)定性虑润。
$\frac{e^{f_{y_i}}}{\sum_j e^{f_j}}
= \frac{Ce^{f_{y_i}}}{C\sum_j e^{f_j}}
= \frac{e^{f_{y_i} + \log C}}{\sum_j e^{f_j + \log C}}$
在代碼中:

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

確切地說成玫，SVM分類器使用鉸鏈損失，有時也稱為最大余量損失。 Softmax分類器使用交叉熵?fù)p失哭当。 Softmax分類器從softmax函數(shù)獲取其名稱猪腕，該函數(shù)用于將原始分?jǐn)?shù)壓縮為歸一化的正值，總和為1钦勘，從而可以應(yīng)用交叉熵?fù)p失陋葡。特別要注意的是，從技術(shù)上來說彻采，談?wù)摗皊oftmax loss”是沒有意義的腐缤，因為softmax只是壓縮函數(shù)，但它是一個比較常用的簡寫颊亮。

二者不同

這里寫圖片描述

Softmax分類器為每個類提供“概率”柴梆。與計算未校準(zhǔn)并且不容易解釋所有類的分?jǐn)?shù)的SVM不同，Softmax分類器允許我們計算所有標(biāo)簽的“概率”终惑。例如绍在，給定一個圖像，SVM分類器可能給你的類“cat”雹有，“dog”和“ship”的分?jǐn)?shù)[12.5偿渡，0.6，-23.0]霸奕。 softmax分類器可以將三個標(biāo)簽的概率計算為[0.9,0.09,0.01]溜宽，這使您能夠解釋其對每個類的信心。然而质帅，我們將“概率”一詞引入引號的原因是适揉，這些概率的高峰或擴散性將直接取決于您作為系統(tǒng)輸入的正則化強度λ。
SVM和softmax的差異一般很小煤惩，所以是可以做比較的嫉嘀。相比于softmax，SVM有一個更加local的目標(biāo)函數(shù)魄揉，這是一個bug也是一個特點剪侮。

總結(jié)

• 定義了一個score function，從pixel到scores
• 不像knn洛退，這種參數(shù)的方式是一丹我們學(xué)習(xí)了參數(shù)我們就可以丟棄掉訓(xùn)練數(shù)據(jù)
• 介紹了bias 的trick
• 我們定義了一個損失函數(shù)（我們?yōu)榫€性分類器引入了兩個常用的損失：SVM和Softmax）瓣俯，它們測量給定參數(shù)集合與訓(xùn)練數(shù)據(jù)集中的地面真值標(biāo)簽的兼容性。我們還看到兵怯，損失函數(shù)的定義是對訓(xùn)練數(shù)據(jù)做出很好的預(yù)測彩匕，相當(dāng)于損失小。