斯坦福 CS231n（2017版）-- 讲座 2 笔记

Lecture 2 主要講的是 image classification 的一些基礎知識 (核心概念會用英語原味表達）

從最經典的例子入手：給你一張貓的圖片，如何從一堆標籤中正確地 pick 貓這個標籤呢？

一言以蔽之，需要解決的是： Semantic gap between “cat” and pixels ，也就是從計算機讀取的一個個像素裡的數字 --> “貓” 這個概念。而且貓的圖片變化多樣，要考慮以下幾個挑戰：

illumination (光照）：
deformation (形變）：貓畢竟是一種流體...
occlusion (遮擋）：貓貓藏起來勒
background clutter：和背景融為一體
intraclass variation: 不同的貓外貌不同

用數組排序一樣的 hard code (硬編碼）方法肯定不行，於是我們考慮用 data-driven approach, 用帶標籤數據集來訓練一個 classifier 選取數據集：CIFAR10， 10 種標籤，50000 大小 training set, 10000 大小 testing set

Nearest Neighbor (近鄰）#

思路：在 training set 中遍歷，尋找和當前測試的圖片最 “相似” 的圖片 a，用這個圖片 a 的標籤作為測試圖片的標籤

那麼 “相似” 該如何用數學語言表示？ 我們用 L1 Distance , 即計算 pixel-wise distance 並相加，如下圖示例

import numpy as np

class NearestNeighbor:
  def __init__(self):
    pass

  def train(self, X, y):
    self.Xtr = X
    self.ytr = y

  def predict(self, X):
    num_test = X.shape[0]
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)
  
    for i in xrange(num_test):
    distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
    min_index = np.argmin(distances)
    Ypred[i] = self.ytr[min_index]

  return Ypred

假設 num_test = 10，圖片分成 4*4 = 16 個像素塊，X 的維度是 [10, 16]，distances 的維度是 [10, 1], ytr 的維度是 [50000, 1](假設我們用的是 CIFAR 整個數據集的 50000 張圖訓練，每張圖對應一個標籤）。

這個方法看起來簡單又好，為什麼不採用呢？接下來要提到 “時間複雜度”，訓練的時間複雜度是 O (1), 預測的時間複雜度是 O (N), 因為預測一張圖片需要把整個（比如這個例子中的 50000）張都遍歷一遍，一個一個做 L1 distance。一旦擴大數據集，預測會非常非常慢。我們可以接受訓練慢一些，因為這是幕後工作，但推理很慢是無法接受的。所以這個方法實操起來不可行。

K-Nearest Neighbors#

上個部分提到的 “Nearest Neighbor” 方法，實質做的是 copy 訓練集某張圖片的 label。且不說時間複雜度的問題，這個 copy 的策略本身也會導致問題：

受到噪聲的干擾，導致劃分區域出現了不規則或尖銳的邊界
對噪聲或異常值無法做到正確的處理（如下圖在綠色區域中的那個黃色點）

為了升級 Nearest Neighbor 方法，我們做出了改動:

這句話是什麼意思呢？我們首先確定我們使用的 distance function，L1 和 L2 都可以，然後選定一個 K 參數。假設我們選了 L1，並選了 K=5，那麼我們就去計算當前測試的這張圖片與所有訓練集中的圖片的 L1 distance（運算 50000 次），然後選擇 L1 distance 最小的 5 張訓練圖。如果這 5 個鄰居裡，兩個鄰居的標籤是 cat, 一個是 dog，一個是 car, 一個是 shit, 那麼很直觀的，我們就可以認為測試圖的 label 是 cat。除了 majority voting，我還得提一下另一種課程中沒提到的 weighted voting 情況:

majority voting (課程中提到的）：從 K 個中尋找標籤次數最多的
weighted voting: 假設 K=3，三個鄰居的 L1 距離分別為 1、2、3，標籤分別為 A、B、A，則權重計算為：標籤 A：1/1 + 1/3 ≈ 1.333，標籤 B：1/2 = 0.5，因此我們認為測試圖片的 label 是 A，因為其權重和更高。
說白了就是對 majority voting 稍微加強了一下，能夠處理標籤數量相同的情況，這個思路貫穿整個機器學習。

這個 K 值得選取也很有說法，較大的 K 值通過 “多數投票” 或 “加權平均” 綜合更多鄰居的信息，能夠減少模型對訓練數據中異常點或噪聲的過度擬合，使模型泛化能力更強。具體可見 Stanford 做的交互可視化網頁，非常有助於理解。當然，散點的表現形式和我們實際圖像之間的像素值作差是不完全一致的，散點之間的 L1 distance 是曼哈頓距離，L2 distance 是點到點線段長度，散點是在抽象整個分類問題，這裡需要慢慢琢磨。
http://vision.stanford.edu/teaching/cs231n-demos/knn/
圖上的點全都是訓練集，一個顏色表示一個 label，假設紅色區域表示 cat，那一團紅點就對應了我們圖像分類任務中一些受 illumination, deformation, occlusion...... 影響的貓圖，他們有差異但是有相似的 “模式”，所以不會完全重疊但離彼此不遠。
把玩這個交互頁面的時候，你會發現，K=1 → 3 →5 有明顯的變化，使分類邊界變得平滑。

如何選取超參數#

Hyperparameters 這個詞大家應該都不陌生，上面問題中，如何選取 K 值，如何選取 distance funcion，都会直接影響到模型的預測結果。這種我們要設置而不是讓模型來學習的參數，我們叫它 “超參數”。在測試我們的超參數好不好的過程中，我們要遵循以下原則

為了保證盡量不要太早碰 test dataset, 比較好的做法是專門取出一定比例的數據集作為 validation set.
老師給出的建議是：他會在論文截止前的一周再碰 test dataset。
cross-validation 也是一種可行的辦法，但由於在大型數據集中訓練成本太高，所以只在小型數據集中使用。

總結#

事實上， K 近鄰的方法從未在 image 上使用，如課件所示，有很大的問題。像素之間的 L2 距離包含的有效信息不夠，具體來說，右下三張圖片和左邊原圖的 L2 距離相同，但很顯然這 3 張圖很不一樣。

於是乎我們要引出 Linear Classification 的方法。我宣布：這節課白忙活😀！
課程中 lecture 2 的末尾講了一點線性分類的內容，我打算將其放到 lecture 3 筆記中完整地介紹。