必須先開始學(xué)cs231n了，前一段時間匆匆看了一遍視頻舔示，感覺不行碟婆，只能再來一遍記一記筆記了，哎惕稻，越學(xué)越感覺自己啥都不會啊竖共。筆記參考：https://zhuanlan.zhihu.com/p/20894041?refer=intelligentunit，隨后會加入一些自己的理解
非原創(chuàng)俺祠，禁止轉(zhuǎn)載本文

• 1. 圖像分類公给、數(shù)據(jù)驅(qū)動方法和流程
  • 1.1 圖像分類
  • 1.2 數(shù)據(jù)驅(qū)動方法
  • 1.3 流程
• 2. Nearest Neighbor分類器
  • 2.1 Nearest Neighbor分類器
  • 2.2 k-Nearest Neighbor
• 3. 驗證集、交叉驗證集和超參數(shù)調(diào)優(yōu)
  • 3.1 驗證集
  • 3.2 交叉驗證集
  • 3.3 實際應(yīng)用
  • 3.4 Nearest Neighbor的優(yōu)劣
• 4. 小結(jié)
• 5. 小結(jié)：應(yīng)用kNN實踐
• 6. 拓展閱讀

1.圖像分類蜘渣、數(shù)據(jù)驅(qū)動方法和流程

1.1 圖像分類

目標：所謂圖像分類問題淌铐，就是已有固定的分類標簽集合，然后對于輸入的圖像蔫缸，從分類標簽集合中找出一個分類標簽腿准，最后把分類標簽分配給該輸入圖像。
困難和挑戰(zhàn)：視角變化（Viewpoint variation）拾碌、大小變化（Scale variation）吐葱、形變（Deformation）、遮擋（Occlusion）校翔、光照條件（Illumination conditions）弟跑、背景干擾（Background clutter）、類內(nèi)差異（Intra-class variation）

1.2 數(shù)據(jù)驅(qū)動方法

給計算機很多數(shù)據(jù)防症，然后實現(xiàn)學(xué)習(xí)算法孟辑，讓計算機學(xué)習(xí)到每個類的外形。這種方法告希，就是數(shù)據(jù)驅(qū)動方法扑浸。

1.3 圖像分類流程

• 輸入：輸入是包含N個圖像的集合，每個圖像的標簽是K種分類標簽中的一種燕偶。這個集合稱為訓(xùn)練集喝噪。
• 學(xué)習(xí)：這一步的任務(wù)是使用訓(xùn)練集來學(xué)習(xí)每個類到底長什么樣。一般該步驟叫做訓(xùn)練分類器或者學(xué)習(xí)一個模型指么。
• 評價：讓分類器來預(yù)測它未曾見過的圖像的分類標簽酝惧，并以此來評價分類器的質(zhì)量榴鼎。我們會把分類器預(yù)測的標簽和圖像真正的分類標簽對比。毫無疑問晚唇，分類器預(yù)測的分類標簽和圖像真正的分類標簽如果一致巫财，那就是好事，這樣的情況越多越好哩陕。

2. Nearest Neighbor分類器

2.1 Nearest Neighbor分類器

這個分類器和卷積神經(jīng)網(wǎng)絡(luò)沒有任何關(guān)系平项，實際中也極少使用，但通過實現(xiàn)它悍及，可以讓讀者對于解決圖像分類問題的方法有個基本的認識闽瓢。
那么具體如何比較兩張圖片呢？最簡單的方法就是逐個像素比較心赶，最后將差異值全部加起來扣讼。換句話說横浑，就是將兩張圖片先轉(zhuǎn)化為兩個向量秋秤，然后計算他們的
L1距離：

Xtr, Ytr, Xte, Yte = load_CIFAR10('data/cifar10/') # a magic function we provide
# flatten out all images to be one-dimensional
Xtr_rows = Xtr.reshape(Xtr.shape[0], 32 * 32 * 3) # Xtr_rows becomes 50000 x 3072
Xte_rows = Xte.reshape(Xte.shape[0], 32 * 32 * 3) # Xte_rows becomes 10000 x 3072

現(xiàn)在我們得到所有的圖像數(shù)據(jù)，并且把他們拉長成為行向量了征讲。接下來展示如何訓(xùn)練并評價一個分類器：

nn = NearestNeighbor() # create a Nearest Neighbor classifier class
nn.train(Xtr_rows, Ytr) # train the classifier on the training images and labels
Yte_predict = nn.predict(Xte_rows) # predict labels on the test images
# and now print the classification accuracy, which is the average number
# of examples that are correctly predicted (i.e. label matches)
print 'accuracy: %f' % ( np.mean(Yte_predict == Yte) )

作為評價標準据某，我們常常使用準確率，它描述了我們預(yù)測正確的得分诗箍。請注意以后我們實現(xiàn)的所有分類器都需要有這個API：train(X, y)函數(shù)癣籽。該函數(shù)使用訓(xùn)練集的數(shù)據(jù)和標簽來進行訓(xùn)練。從其內(nèi)部來看滤祖，類應(yīng)該實現(xiàn)一些關(guān)于標簽和標簽如何被預(yù)測的模型筷狼。這里還有個predict(X)函數(shù)，它的作用是預(yù)測輸入的新數(shù)據(jù)的分類標簽〗惩現(xiàn)在還沒介紹分類器的實現(xiàn)埂材，下面就是使用L1距離的Nearest Neighbor分類器的實現(xiàn)套路：

import numpy as np

class NearestNeighbor(object):
  def __init__(self):
    pass

  def train(self, X, y):
    """ X is N x D where each row is an example. Y is 1-dimension of size N """
    # the nearest neighbor classifier simply remembers all the training data
    self.Xtr = X
    self.ytr = y

  def predict(self, X):
    """ X is N x D where each row is an example we wish to predict label for """
    num_test = X.shape[0]
    # lets make sure that the output type matches the input type
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)

    # loop over all test rows
    for i in xrange(num_test):
      # find the nearest training image to the i'th test image
      # using the L1 distance (sum of absolute value differences)
      distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
      min_index = np.argmin(distances) # get the index with smallest distance
      Ypred[i] = self.ytr[min_index] # predict the label of the nearest example

    return Ypred

如果你用這段代碼跑CIFAR-10，你會發(fā)現(xiàn)準確率能達到38.6%汤求。這比隨機猜測的10%要好俏险，但是比人類識別的水平（據(jù)研究推測是94%）和卷積神經(jīng)網(wǎng)絡(luò)能達到的95%還是差多了严拒。

L2距離：從幾何學(xué)的角度，可以理解為它在計算兩個向量間的歐式距離竖独。L2距離的公式如下：

distances = np.sqrt(np.sum(np.square(self.Xtr - X[i,:]), axis = 1))

注意在這里使用了np.sqrt裤唠，但是在實際中可能不用。因為求平方根函數(shù)是一個單調(diào)函數(shù)莹痢，它對不同距離的絕對值求平方根雖然改變了數(shù)值大小种蘸，但依然保持了不同距離大小的順序。所以用不用它竞膳，都能夠?qū)ο袼夭町惖拇笮∵M行正確比較劈彪。如果你在CIFAR-10上面跑這個模型，正確率是35.4%顶猜，比剛才還低了沧奴！。

L1和L2比較长窄。比較這兩個度量方式是挺有意思的滔吠。在面對兩個向量之間的差異時，L2比L1更加不能容忍這些差異挠日。也就是說疮绷，相對于1個巨大的差異，L2距離更傾向于接受多個中等程度的差異嚣潜。L1和L2都是在p-norm常用的特殊形式冬骚。

2.2 k-Nearest Neighbor分類器

KNN思想：與其只找最相近的那1個圖片的標簽，我們找最相似的k個圖片的標簽懂算，然后讓他們針對測試圖片進行投票只冻，最后把票數(shù)最高的標簽作為對測試圖片的預(yù)測。所以當(dāng)k=1的時候计技，k-Nearest Neighbor分類器就是Nearest Neighbor分類器喜德。從直觀感受上就可以看到，更高的k值可以讓分類的效果更平滑垮媒，使得分類器對于異常值更有抵抗力舍悯。

如何選擇k值呢金矛？

3. 驗證集、交叉驗證集和超參數(shù)調(diào)優(yōu)

3.1 驗證集（validation set）

k-NN分類器需要設(shè)定k值勺届，那么選擇哪個k值最合適的呢驶俊？我們可以選擇不同的距離函數(shù)，比如L1范數(shù)和L2范數(shù)等免姿，那么選哪個好饼酿？還有不少選擇我們甚至連考慮都沒有考慮到（比如：點積）。所有這些選擇胚膊，被稱為超參數(shù)（hyperparameter）故俐。

絕對不能使用測試集調(diào)優(yōu)！Ｎ赏瘛药版！（這一點應(yīng)該沒問題，稍有ML常識的小伙伴都清楚）
所以一般的方法是：從訓(xùn)練集中取出一部分數(shù)據(jù)用來調(diào)優(yōu)喻犁，我們稱之為驗證集（validation set）槽片。以CIFAR-10為例，我們可以用49000個圖像作為訓(xùn)練集肢础，用1000個圖像作為驗證集还栓。驗證集其實就是作為假的測試集來調(diào)優(yōu)。下面就是代碼：

# assume we have Xtr_rows, Ytr, Xte_rows, Yte as before
# recall Xtr_rows is 50,000 x 3072 matrix
Xval_rows = Xtr_rows[:1000, :] # take first 1000 for validation
Yval = Ytr[:1000]
Xtr_rows = Xtr_rows[1000:, :] # keep last 49,000 for train
Ytr = Ytr[1000:]

# find hyperparameters that work best on the validation set
validation_accuracies = []
for k in [1, 3, 5, 10, 20, 50, 100]:

  # use a particular value of k and evaluation on validation data
  nn = NearestNeighbor()
  nn.train(Xtr_rows, Ytr)
  # here we assume a modified NearestNeighbor class that can take a k as input
  Yval_predict = nn.predict(Xval_rows, k = k)
  acc = np.mean(Yval_predict == Yval)
  print 'accuracy: %f' % (acc,)

  # keep track of what works on the validation set
  validation_accuracies.append((k, acc))

注意一下這個 acc = np.mean(Yval_predict == Yval)

程序結(jié)束后乔妈，我們會作圖分析出哪個k值表現(xiàn)最好蝙云，然后用這個k值來跑真正的測試集氓皱，并作出對算法的評價路召。
把訓(xùn)練集分成訓(xùn)練集和驗證集。使用驗證集來對所有超參數(shù)調(diào)優(yōu)波材。最后只在測試集上跑一次并報告結(jié)果股淡。

3.2 交叉驗證

原因：訓(xùn)練集數(shù)量較小（因此驗證集的數(shù)量更型⑶）
方法：還是用剛才的例子唯灵，如果是交叉驗證集，我們就不是取1000個圖像隙轻，而是將訓(xùn)練集平均分成5份埠帕，其中4份用來訓(xùn)練垢揩，1份用來驗證。然后我們循環(huán)著取其中4份來訓(xùn)練敛瓷，其中1份來驗證叁巨，最后取所有5次驗證結(jié)果的平均值作為算法驗證結(jié)果。

3.3 實際應(yīng)用

在實際情況下奏瞬，人們不是很喜歡用交叉驗證布近，主要是因為它會耗費較多的計算資源。一般直接把訓(xùn)練集按照50%-90%的比例分成訓(xùn)練集和驗證集丝格。但這也是根據(jù)具體情況來定的：如果超參數(shù)數(shù)量多撑瞧，你可能就想用更大的驗證集，而驗證集的數(shù)量不夠显蝌，那么最好還是用交叉驗證吧预伺。至于分成幾份比較好，一般都是分成3曼尊、5和10份酬诀。

常用的數(shù)據(jù)分割模式。給出訓(xùn)練集和測試集后骆撇，訓(xùn)練集一般會被均分瞒御。這里是分成5份。前面4份用來訓(xùn)練神郊，黃色那份用作驗證集調(diào)優(yōu)肴裙。如果采取交叉驗證，那就各份輪流作為驗證集涌乳。最后模型訓(xùn)練完畢蜻懦，超參數(shù)都定好了，讓模型跑一次（而且只跑一次）測試集夕晓，以此測試結(jié)果評價算法宛乃。

3.4 Nearest Neighbor分類器的優(yōu)劣

優(yōu)點：易于理解，實現(xiàn)簡單 ; 算法的訓(xùn)練不需要花時間，因為其訓(xùn)練過程只是將訓(xùn)練集數(shù)據(jù)存儲起來
缺點：測試要花費大量時間計算征炼，因為每個測試圖像需要和所有存儲的訓(xùn)練圖像進行比較

在實際應(yīng)用中析既，我們關(guān)注測試效率遠遠高于訓(xùn)練效率。其實谆奥，我們后續(xù)要學(xué)習(xí)的卷積神經(jīng)網(wǎng)絡(luò)在這個權(quán)衡上走到了另一個極端：雖然訓(xùn)練花費很多時間渡贾，但是一旦訓(xùn)練完成，對新的測試數(shù)據(jù)進行分類非承塾遥快空骚。
Nearest Neighbor分類器在某些特定情況（比如數(shù)據(jù)維度較低）下，可能是不錯的選擇擂仍。但是在實際的圖像分類工作中囤屹，很少使用。

圖片的排布更像是一種顏色分布函數(shù)逢渔，或者說是基于背景的肋坚，而不是圖片的語義主體。我們更希望希望同類的圖片能夠聚集在一起肃廓，而不被背景或其他不相關(guān)因素干擾智厌。

4. 小結(jié)

• 介紹了圖像分類問題。在該問題中盲赊，給出一個由被標注了分類標簽的圖像組成的集合铣鹏，要求算法能預(yù)測沒有標簽的圖像的分類標簽，并根據(jù)算法預(yù)測準確率進行評價哀蘑。
• 介紹了一個簡單的圖像分類器：最近鄰分類器(Nearest Neighbor classifier)诚卸。分類器中存在不同的超參數(shù)(比如k值或距離類型的選取)，要想選取好的超參數(shù)不是一件輕而易舉的事绘迁。
• 選取超參數(shù)的正確方法是：將原始訓(xùn)練集分為訓(xùn)練集和驗證集合溺，我們在驗證集上嘗試不同的超參數(shù)，最后保留表現(xiàn)最好那個缀台。
• 如果訓(xùn)練數(shù)據(jù)量不夠棠赛，使用交叉驗證方法，它能幫助我們在選取最優(yōu)超參數(shù)的時候減少噪音膛腐。
• 一旦找到最優(yōu)的超參數(shù)睛约，就讓算法以該參數(shù)在測試集跑且只跑一次，并根據(jù)測試結(jié)果評價算法依疼。
• 最近鄰分類器能夠在CIFAR-10上得到將近40%的準確率痰腮。該算法簡單易實現(xiàn)，但需要存儲所有訓(xùn)練數(shù)據(jù)律罢，并且在測試的時候過于耗費計算能力。
• 最后，我們知道了僅僅使用L1和L2范數(shù)來進行像素比較是不夠的误辑，圖像更多的是按照背景和顏色被分類沧踏，而不是語義主體分身。

5. 小結(jié)：實際應(yīng)用k-NN

如果你希望將k-NN分類器用到實處（最好別用到圖像上巾钉，若是僅僅作為練手還可以接受）翘狱，那么可以按照以下流程：

1. 預(yù)處理你的數(shù)據(jù)：對你數(shù)據(jù)中的特征進行歸一化（normalize），讓其具有零平均值（zero mean）和單位方差（unit variance）砰苍。在后面的小節(jié)我們會討論這些細節(jié)潦匈。本小節(jié)不討論，是因為圖像中的像素都是同質(zhì)的赚导，不會表現(xiàn)出較大的差異分布茬缩，也就不需要標準化處理了。
2. 如果數(shù)據(jù)是高維數(shù)據(jù)吼旧，考慮使用降維方法凰锡，比如PCA(wiki ref, CS229ref, blog ref)或隨機投影。
3. 將數(shù)據(jù)隨機分入訓(xùn)練集和驗證集圈暗。按照一般規(guī)律掂为，70%-90% 數(shù)據(jù)作為訓(xùn)練集。這個比例根據(jù)算法中有多少超參數(shù)员串，以及這些超參數(shù)對于算法的預(yù)期影響來決定勇哗。如果需要預(yù)測的超參數(shù)很多，那么就應(yīng)該使用更大的驗證集來有效地估計它們寸齐。如果擔(dān)心驗證集數(shù)量不夠智绸，那么就嘗試交叉驗證方法。如果計算資源足夠访忿，使用交叉驗證總是更加安全的（份數(shù)越多瞧栗，效果越好，也更耗費計算資源）海铆。
4. 在驗證集上調(diào)優(yōu)迹恐，嘗試足夠多的k值，嘗試L1和L2兩種范數(shù)計算方式卧斟。
5. 如果分類器跑得太慢殴边，嘗試使用Approximate Nearest Neighbor庫（比如FLANN）來加速這個過程，其代價是降低一些準確率珍语。
6. 對最優(yōu)的超參數(shù)做記錄锤岸。記錄最優(yōu)參數(shù)后，是否應(yīng)該讓使用最優(yōu)參數(shù)的算法在完整的訓(xùn)練集上運行并再次訓(xùn)練呢板乙？因為如果把驗證集重新放回到訓(xùn)練集中（自然訓(xùn)練集的數(shù)據(jù)量就又變大了）是偷，有可能最優(yōu)參數(shù)又會有所變化拳氢。在實踐中，不要這樣做蛋铆。千萬不要在最終的分類器中使用驗證集數(shù)據(jù)馋评，這樣做會破壞對于最優(yōu)參數(shù)的估計。直接使用測試集來測試用最優(yōu)參數(shù)設(shè)置好的最優(yōu)模型刺啦，得到測試集數(shù)據(jù)的分類準確率留特，并以此作為你的kNN分類器在該數(shù)據(jù)上的性能表現(xiàn)。

6. 拓展閱讀

下面是一些你可能感興趣的拓展閱讀鏈接：

• A Few Useful Things to Know about Machine Learning玛瘸，文中第6節(jié)與本節(jié)相關(guān)蜕青，但是整篇文章都強烈推薦。

• Recognizing and Learning Object Categories糊渊，ICCV 2005上的一節(jié)關(guān)于物體分類的課程右核。

再次感謝原作者的翻譯！再来！