前言：

以斯坦福cs231n課程的python編程任務(wù)為主線，展開對(duì)該課程主要內(nèi)容的理解和部分?jǐn)?shù)學(xué)推導(dǎo)。
該課程相關(guān)筆記參考自知乎-CS231n官方筆記授權(quán)翻譯總集篇發(fā)布
課程材料和事例參考自-cs231n

SVM分類器簡(jiǎn)介：

SVM-支持向量機(jī)(Support Vector Machine)，是一個(gè)有監(jiān)督的線性分類器
線性分類器：在本模型中，我們從最簡(jiǎn)單的函數(shù)開始，一個(gè)線性映射：

這個(gè)公式就是平時(shí)最常見到的線性函數(shù)，常為一維線性函數(shù)（即 W 為一維的）。當(dāng)這種函數(shù)擴(kuò)展到多維度的情況下時(shí)就是我們SVM要面臨的情況。首先我們要做的處理是將每個(gè)圖像數(shù)據(jù)都拉長(zhǎng)為一個(gè)長(zhǎng)度為D的列向量，大小為 [D * 1] 。其中大小為 [K * D] 的矩陣W和大小為 [K 1] 列向量 b 為該函數(shù)的參數(shù)。以CIFAR-10為例,CIFAR-10中一個(gè)圖像的大小等于 [32323] ,含了該圖像的所有像素信息，這些信息被拉成為一個(gè) [3072 * 1] 的列向量， W 大小為 [103072] ， b 的大小為 [10*1] 。因此，3072個(gè)數(shù)字（素?cái)?shù)值）輸入函數(shù)，函數(shù)輸出10個(gè)數(shù)字（不同分類得到的評(píng)分）。參數(shù) W 被稱為權(quán)重（weights）。 b 被稱為偏差向量（bias vector）。

理解線性分類器

線性分類器計(jì)算圖像中3個(gè)顏色通道中所有像素的值與權(quán)重的矩陣乘，從而得到分類分值。根據(jù)我們對(duì)權(quán)重設(shè)置的值，對(duì)于圖像中的某些位置的某些顏色，函數(shù)表現(xiàn)出的得分即對(duì)該點(diǎn)的接受程度。例如對(duì)于飛機(jī)來說，飛機(jī)圖片中包含有大量的藍(lán)色天空，白色的云彩以及白色的飛機(jī)，那么這個(gè)飛機(jī)分類器就會(huì)在藍(lán)色通道上的權(quán)重比較多，而在其他通道上的權(quán)重就較少,正如筆記中指出的：

一個(gè)將圖像映射到分類分值的例子。為了便于可視化，假設(shè)圖像只有4個(gè)像素（都是黑白像素，這里不考慮RGB通道），有3個(gè)分類（紅色代表貓，綠色代表狗，藍(lán)色代表船，注意，這里的紅、綠和藍(lán)3種顏色僅代表分類，和RGB通道沒有關(guān)系）。首先將圖像像素拉伸為一個(gè)列向量，與W進(jìn)行矩陣乘，然后得到各個(gè)分類的分值。需要注意的是，這個(gè)W一點(diǎn)也不好：貓分類的分值非常低。從上圖來看，算法倒是覺得這個(gè)圖像是一只狗。

現(xiàn)在考慮高維度情況：還是以CIFAR-10為例，CIFAR-10中的圖片轉(zhuǎn)化成一個(gè)向量（3072維）后，就是一個(gè)高維度問題，而一個(gè)向量（3色通道轉(zhuǎn)化而來）可以看作是3072維空間中的一個(gè)點(diǎn)，而線性分類器就是在高維度空間中的一個(gè)超平面，將各個(gè)空間點(diǎn)分開。如圖所示：

圖像空間的示意圖。其中每個(gè)圖像是一個(gè)點(diǎn)，有3個(gè)分類器。以紅色的汽車分類器為例，紅線表示空間中汽車分類分?jǐn)?shù)為0的點(diǎn)的集合，紅色的箭頭表示分值上升的方向。所有紅線右邊的點(diǎn)的分?jǐn)?shù)值均為正，且線性升高。紅線左邊的點(diǎn)分值為負(fù)，且線性降低。

目標(biāo)：而我們要做的就是尋找一個(gè)W和一個(gè)b,使得這個(gè)超平面能很好的區(qū)分各個(gè)類。尋找方法就是不停的改變w和b的值，即不停的旋轉(zhuǎn)平移，直到它使分類的偏差較小。

SVM的組成：

<li>圖像數(shù)據(jù)預(yù)處理：在上面的例子中，所有圖像都是使用的原始像素值（從0到255）。在機(jī)器學(xué)習(xí)中，對(duì)于輸入的特征做歸一化（normalization）是必然的。在圖像處理中，每個(gè)像素點(diǎn)可以看作是一個(gè)簡(jiǎn)單的特征,在一般使用過程中，我們都先將特征“集中”，即訓(xùn)練集中所有的圖像計(jì)算出一個(gè)平均圖像值，然后每個(gè)圖像都減去這個(gè)平均值，這樣圖像的像素值就大約分布在[-127, 127]之間了，下一個(gè)常見步驟是，讓所有數(shù)值分布的區(qū)間變?yōu)閇-1, 1]。

<li>損失函數(shù)（loss function）：如何評(píng)判分類器的偏差就是當(dāng)前的問題，解決這問題的方法就是損失函數(shù):

這個(gè)函數(shù)得到的就是當(dāng)前分類的偏差值。

舉例：用一個(gè)例子演示公式是如何計(jì)算的。假設(shè)有3個(gè)分類，并且得到了分值s=[13,-7,11]。其中第一個(gè)類別是正確類別，即$y_i=0$。同時(shí)假設(shè)$\Delta$是10。上面的公式是將所有不正確分類加起來，所以得到兩個(gè)部分：
$$Li=max(0,-7-13+10)+max(0,11-13+10)$$
可以看到第一個(gè)部分結(jié)果是0，這是因?yàn)閇-7-13+10]得到的是負(fù)數(shù)，經(jīng)過函數(shù)處理后得到0。這一對(duì)類別分?jǐn)?shù)和標(biāo)簽的損失值是0，這是因?yàn)檎_分類的得分13與錯(cuò)誤分類的得分-7的差為20，高于邊界值10。而SVM只關(guān)心差距至少要大于10，更大的差值還是算作損失值為0。第二個(gè)部分計(jì)算[11-13+10]得到8。雖然正確分類的得分比不正確分類的得分要高（13>11），但是比10的邊界值還是小了，分差只有2，這就是為什么損失值等于8。簡(jiǎn)而言之，SVM的損失函數(shù)想要正確分類類別的分?jǐn)?shù)比不正確類別分?jǐn)?shù)高，而且至少要高。如果不滿足這點(diǎn)，就開始計(jì)算損失值。
那么在這次的模型中，我們面對(duì)的是線性評(píng)分函數(shù)（f(x_i,W)=Wx_i），所以我們可以將損失函數(shù)的公式稍微改寫一下：

其中w_j是權(quán)重W的第j行，被變形為列向量。然而，一旦開始考慮更復(fù)雜的評(píng)分函數(shù)f公式，這樣做就不是必須的了。

<li>正則化(Regularization):上面損失函數(shù)有一個(gè)問題。假設(shè)有一個(gè)數(shù)據(jù)集和一個(gè)權(quán)重集W能夠正確地分類每個(gè)數(shù)據(jù)（即所有的邊界都滿足，對(duì)于所有的i都有）。問題在于這個(gè)W并不唯一：可能有很多相似的W都能正確地分類所有的數(shù)據(jù)。

一個(gè)簡(jiǎn)單的例子：如果W能夠正確分類所有數(shù)據(jù)，即對(duì)于每個(gè)數(shù)據(jù)，損失值都是0。那么當(dāng)時(shí)，任何數(shù)乘都能使得損失值為0，因?yàn)檫@個(gè)變化將所有分值的大小都均等地?cái)U(kuò)大了，所以它們之間的絕對(duì)差值也擴(kuò)大了。舉個(gè)例子，如果一個(gè)正確分類的分值和舉例它最近的錯(cuò)誤分類的分值的差距是15，對(duì)W乘以2將使得差距變成30。

當(dāng)然,在沒有這種模糊性的情況下我們能很好的控制偏差。而減少這種模糊性的方法是向損失函數(shù)增加一個(gè)正則化懲罰（regularization penalty）部分。最常用的正則化懲罰是L2范式，L2范式通過對(duì)所有參數(shù)進(jìn)行逐元素的平方懲罰來抑制大數(shù)值的權(quán)重,將其展開完整公式是:

其中，N是訓(xùn)練集的數(shù)據(jù)量?，F(xiàn)在正則化懲罰添加到了損失函數(shù)里面，并用超參數(shù)來計(jì)算其權(quán)重。該超參數(shù)無法簡(jiǎn)單確定，需要通過交叉驗(yàn)證來獲取,引入了L2懲罰后，SVM們就有了最大邊界這一良好性質(zhì)。（如果感興趣，可以查看CS229課程）。

SVM實(shí)現(xiàn)：

<li>linear_svm.py

#coding:utf-8
import numpy as np
from random import shuffle

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]]
    for j in xrange(num_classes):
      if j == y[i]:
        continue
      margin = scores[j] - correct_class_score + 1 # note delta = 1
      if margin > 0:
        loss += margin
        dW[:, y[i]] += -X[i, :]    
        dW[:, j] += X[i, :]         

  # Right now the loss is a sum over all training examples, but we want it
  # to be an average instead so we divide by num_train.
  loss /= num_train
  dW /= num_train
  # Add regularization to the loss.
  loss +=  reg * np.sum(W * W)
  dW += reg * W
  
  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
  scores = X.dot(W)        
  num_classes = W.shape[1]
  num_train = X.shape[0]

  scores_correct = scores[np.arange(num_train), y]   # 1 by N
  scores_correct = np.reshape(scores_correct, (num_train, -1))  # N by 1
  margins = scores - scores_correct + 1    # N by C
  margins = np.maximum(0,margins)
  margins[np.arange(num_train), y] = 0
  loss += np.sum(margins) / num_train
  loss += 0.5 * reg * np.sum(W * W)

  # compute the gradient
  margins[margins > 0] = 1
  row_sum = np.sum(margins, axis=1)                  # 1 by N
  margins[np.arange(num_train), y] = -row_sum        
  dW += np.dot(X.T, margins)/num_train + reg * W     # D by C

  return loss, dW

<li>linear_classifier.py

#coding:utf-8
import numpy as np
from classifiers.linear_svm import *
from classifiers.softmax import *

class LinearClassifier(object):

  def __init__(self,w=None):
    self.W = w

  def train(self, X, y, learning_rate=1e-3, reg=1e-5, num_iters=100,
            batch_size=200, verbose=False):
    """
    Train this linear classifier using stochastic gradient descent.

    Inputs:
    - X: A numpy array of shape (N, D) containing training data; there are N
      training samples each of dimension D.
    - y: A numpy array of shape (N,) containing training labels; y[i] = c
      means that X[i] has label 0 <= c < C for C classes.
    - learning_rate: (float) learning rate for optimization.
    - reg: (float) regularization strength.
    - num_iters: (integer) number of steps to take when optimizing
    - batch_size: (integer) number of training examples to use at each step.
    - verbose: (boolean) If true, print progress during optimization.

    Outputs:
    A list containing the value of the loss function at each training iteration.
    """
    num_train, dim = X.shape
    num_classes = np.max(y) + 1 # assume y takes values 0...K-1 where K is number of classes
    if self.W is None:
      # lazily initialize W
      self.W = 0.001 * np.random.randn(dim, num_classes)

    # Run stochastic gradient descent to optimize W
    loss_history = []
    for it in xrange(num_iters):
      X_batch = None
      y_batch = None

      sample_index = np.random.choice(num_train, batch_size, replace=False)
      X_batch = X[sample_index, :]   # select the batch sample
      y_batch = y[sample_index]      # select the batch label
     
      # evaluate loss and gradient
      loss, grad = self.loss(X_batch, y_batch, reg)
      loss_history.append(loss)

      # perform parameter update
      self.W += -learning_rate * grad

      if verbose and it % 100 == 0:
        print 'iteration %d / %d: loss %f' % (it, num_iters, loss)

    return loss_history

  def predict(self, X):
    """
    Use the trained weights of this linear classifier to predict labels for
    data points.

    Inputs:
    - X: D x N array of training data. Each column is a D-dimensional point.

    Returns:
    - y_pred: Predicted labels for the data in X. y_pred is a 1-dimensional
      array of length N, and each element is an integer giving the predicted
      class.
    """
    y_pred = np.zeros(X.shape[1])
    score = X.dot(self.W)
    y_pred = np.argmax(score,axis=1)
    return y_pred
  
  def loss(self, X_batch, y_batch, reg):
    """
    Compute the loss function and its derivative. 
    Subclasses will override this.

    Inputs:
    - X_batch: A numpy array of shape (N, D) containing a minibatch of N
      data points; each point has dimension D.
    - y_batch: A numpy array of shape (N,) containing labels for the minibatch.
    - reg: (float) regularization strength.

    Returns: A tuple containing:
    - loss as a single float
    - gradient with respect to self.W; an array of the same shape as W
    """
    pass


class LinearSVM(LinearClassifier):
  """ A subclass that uses the Multiclass SVM loss function """

  def loss(self, X_batch, y_batch, reg):
    return svm_loss_vectorized(self.W, X_batch, y_batch, reg)


class Softmax(LinearClassifier):
  """ A subclass that uses the Softmax + Cross-entropy loss function """

  def loss(self, X_batch, y_batch, reg):
    return softmax_loss_vectorized(self.W, X_batch, y_batch, reg)

測(cè)試：

不同參數(shù)下SVM10類分類的準(zhǔn)確率如下：

總結(jié)：

SVM在分類少以及線性的情況下有非常好的分類效果（尤其是二類），在配合PCA的情況下會(huì)有更好的結(jié)果。