一研儒、前言
CS231n是斯坦福大學(xué)開設(shè)的一門深度學(xué)習(xí)與計算機(jī)視覺課程，是目前公認(rèn)的該領(lǐng)域內(nèi)最好的公開課看靠。目前，該課程的全部資料已經(jīng)被翻譯為中文液肌，非常適合自學(xué)挟炬。該課程和相關(guān)資料的地址如下：
- 在線視頻：網(wǎng)易云課堂
- 課程講義和資料：知乎專欄-智能單元
- 官方網(wǎng)站：http://cs231n.github.io/
課程不光有精彩的講解，還提供了非常精致的課后作業(yè)嗦哆。唯一的遺憾是作業(yè)沒有公布標(biāo)準(zhǔn)答案谤祖。因此我把自己的答案發(fā)出來與大家交流。
二老速、編程環(huán)境
官方建議使用Anaconda粥喜，它是Python的一個發(fā)布版，包含了最流行的科研橘券、數(shù)學(xué)额湘、工程和數(shù)據(jù)分析Python包卿吐。只需要安裝這一個東西就夠了，非常方便锋华。建議下載Python2.7版嗡官，因為課程給出的例程都是在Python2.7下測試通過的，而在Python3.x中可能會出錯毯焕。
從shell啟動jupyter notebook衍腥，就可以在瀏覽器中編程了，不需要本地IDE纳猫。
三婆咸、KNN分類器
用K-最近鄰（K Nearest Neighbor，KNN）分類器對圖像分類在實際中是不可行的续担，不過這里只是為了熟悉一些基本的操作擅耽，所以第一個作業(yè)從KNN開始活孩。
KNN的基本原理是物遇，給定一張測試圖片，拿它和所有的訓(xùn)練集圖片比較憾儒，找出最相近的K個（全部像素向量的歐氏距離越短越相近）询兴，由這K個圖片的標(biāo)簽投票決定（出現(xiàn)次數(shù)最多的標(biāo)簽勝出）測試圖片的標(biāo)簽。KNN方法不需要訓(xùn)練時間起趾，但在測試時需要做大量比對诗舰，因此測試性能極低。
下面給出Assignment1中的KNN分類器部分的作業(yè)答案训裆。
-
兩層循環(huán)計算距離
下面代碼中給出了兩種做法眶根，方案1是比較直觀的做法，兩張圖片相減平方再求和边琉。方案2用NumPy提供的norm方法属百，直接計算范數(shù)。
def compute_distances_two_loops(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using a nested loop over both the training data and the
test data.
Inputs:
- X: A numpy array of shape (num_test, D) containing test data.
Returns:
- dists: A numpy array of shape (num_test, num_train) where dists[i, j]
is the Euclidean distance between the ith test point and the jth training
point.
"""
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
for i in xrange(num_test):
for j in xrange(num_train):
#####################################################################
# TODO: #
# Compute the l2 distance between the ith test point and the jth #
# training point, and store the result in dists[i, j]. You should #
# not use a loop over dimension. #
#####################################################################
#方案1
#dists[i, j] = np.sqrt(np.sum((X[i] - self.X_train[j]) ** 2))
#方案2
dists[i, j] = np.linalg.norm(self.X_train[j,:]-X[i,:])
#####################################################################
# END OF YOUR CODE #
#####################################################################
return dists
-
一層循環(huán)計算距離
直接對整個訓(xùn)練集圖片操作变姨，此時self.X_train的大小為5000×3072族扰，而X[i]的大小為1×3072，兩者相減會自動對X[i]進(jìn)行廣播定欧，使其擴(kuò)展到與self.X_train相同的大小渔呵。如果不清楚廣播的用法，可以參考文檔砍鸠。此時執(zhí)行sum或者norm操作的話扩氢，還需要指定軸，令axis=1爷辱。NumPy中的軸是個很令人迷惑的概念类茂，根據(jù)我的理解耍属，不管多少維的矩陣，軸的序號總是從左向右計數(shù)巩检，被指定的軸的大小在操作后會被改變厚骗。例如，本例中兢哭，np.sum((X[i] - self.X_train) ** 2, axis=1)领舰，里面的運算X[i] - self.X_train的結(jié)果是個5000*3072的矩陣，對這個矩陣沿著1號軸求和迟螺，從左向右數(shù)冲秽，3072所在的維度就是1號軸（軸序號從0開始），因此矩父，該維度的大小將會改變锉桑，而其它維度保持不變。對于sum來說窍株，直接把這個維度的值全部加起來民轴，因此最后得到了長度為5000的一維矩陣。norm同理球订。
def compute_distances_one_loop(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using a single loop over the test data.
Input / Output: Same as compute_distances_two_loops
"""
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
for i in xrange(num_test):
#######################################################################
# TODO: #
# Compute the l2 distance between the ith test point and all training #
# points, and store the result in dists[i, :]. #
#######################################################################
#方案1
#dists[i, :] = np.sqrt(np.sum((X[i] - self.X_train) ** 2, axis=1))
#方案2
dists[i, :] = np.linalg.norm(self.X_train - X[i,:], axis = 1)
#######################################################################
# END OF YOUR CODE #
#######################################################################
return dists
-
無循環(huán)計算距離
這一步倒是很有難度后裸。題目中給出了提示——使用乘法和兩個廣播求和，可惜我并沒想明白怎么用冒滩。方案一是我的思路微驶，完全沿襲前面的做法，充分利用廣播使兩個矩陣擴(kuò)展到相同的維度开睡。具體來說因苹，原本X的大小是500×3072，現(xiàn)在我把它強(qiáng)行變成500×1×3072篇恒，與大小為5000×3072的self.X_train相減扶檐，按照廣播規(guī)則，結(jié)果將是500×5000×3072的矩陣婚度。再對2號軸（對應(yīng)3072的那一維）求和蘸秘、開根號，最后得到500×5000的矩陣蝗茁。
方案二則是按照提示的思路實現(xiàn)的（真不知道是怎么想到的）醋虏。把計算歐氏距離的式子差的平方展開，變成平方的和減去交叉項的2倍哮翘。的確是個很妙的方案颈嚼。
def compute_distances_no_loops(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using no explicit loops.
Input / Output: Same as compute_distances_two_loops
"""
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
#########################################################################
# TODO: #
# Compute the l2 distance between all test points and all training #
# points without using any explicit loops, and store the result in #
# dists. #
# #
# You should implement this function using only basic array operations; #
# in particular you should not use functions from scipy. #
# #
# HINT: Try to formulate the l2 distance using matrix multiplication #
# and two broadcast sums. #
#########################################################################
#方案1
#dists = np.sqrt(np.sum((X.reshape(num_test,1,X.shape[1]) - self.X_train) ** 2, axis=2))
#方案2
dists = np.multiply(np.dot(X,self.X_train.T),-2)
sq1 = np.sum(np.square(X),axis=1,keepdims = True)
sq2 = np.sum(np.square(self.X_train),axis=1)
dists = np.add(dists,sq1)
dists = np.add(dists,sq2)
dists = np.sqrt(dists)
#########################################################################
# END OF YOUR CODE #
#########################################################################
return dists
-
分類預(yù)測
這里用到了argsort函數(shù)靡馁，輸出的結(jié)果是從小到大排序后的下標(biāo)冯痢，也就是說茎辐，結(jié)果列表中的第一個值是最小的數(shù)的下標(biāo)旁趟，以此類推。
這句代碼closest_y = self.y_train[train_topK_index]用到了整型數(shù)組訪問語法限煞，即取出self.y_train中以train_topK_index中包含的值為下標(biāo)的內(nèi)容抹恳。
bincount用來計算列表中每個數(shù)出現(xiàn)的次數(shù)，任意數(shù)字n出現(xiàn)的次數(shù)保存在count[n]中署驻。
argmax找出列表中最大值的下標(biāo)奋献。
def predict_labels(self, dists, k=1):
"""
Given a matrix of distances between test points and training points,
predict a label for each test point.
Inputs:
- dists: A numpy array of shape (num_test, num_train) where dists[i, j]
gives the distance betwen the ith test point and the jth training point.
Returns:
- y: A numpy array of shape (num_test,) containing predicted labels for the
test data, where y[i] is the predicted label for the test point X[i].
"""
num_test = dists.shape[0]
y_pred = np.zeros(num_test)
for i in xrange(num_test):
# A list of length k storing the labels of the k nearest neighbors to
# the ith test point.
closest_y = []
#########################################################################
# TODO: #
# Use the distance matrix to find the k nearest neighbors of the ith #
# testing point, and use self.y_train to find the labels of these #
# neighbors. Store these labels in closest_y. #
# Hint: Look up the function numpy.argsort. #
#########################################################################
index_array = np.argsort(dists[i, :])
train_topK_index = index_array[:k]
closest_y = self.y_train[train_topK_index]
#########################################################################
# TODO: #
# Now that you have found the labels of the k nearest neighbors, you #
# need to find the most common label in the list closest_y of labels. #
# Store this label in y_pred[i]. Break ties by choosing the smaller #
# label. #
#########################################################################
count = np.bincount(closest_y)
y_pred[i] = np.argmax(count)
#########################################################################
# END OF YOUR CODE #
#########################################################################
return y_pred
-
交叉驗證
這部分代碼比較復(fù)雜。首先是把訓(xùn)練集分為5組旺上，使用array_split即可瓶蚂。但需要注意的是，分割結(jié)果是一個列表宣吱，而不是矩陣窃这。請務(wù)必注意列表和矩陣的區(qū)別：列表是Python的基本數(shù)據(jù)類型，而矩陣是NumPy中的數(shù)據(jù)類型征候。如果弄混了這一點杭攻，后面的程序?qū)浅ｋy以理解（我就弄混了，所以糾結(jié)了很久orz）倍奢。接下來朴上，很關(guān)鍵的一點是如何按照5折交叉驗證的要求組合訓(xùn)練集垒棋。
X_train_cv = np.vstack(X_train_folds[:i] + X_train_folds[i+1:])這句話是容易產(chǎn)生困擾的卒煞。vstack用于在0號軸上連接多個矩陣（請按照前面介紹的規(guī)則理解這句話。連接后叼架，0號軸的大小將發(fā)生變化畔裕，而其它軸的大小不變），函數(shù)的參數(shù)應(yīng)當(dāng)為待連接的矩陣組成的元組（tuple）乖订。而在這行代碼中扮饶，并沒有傳入元組，而是傳入了兩個列表相加的結(jié)果乍构。首先甜无，這里是列表相加而不是矩陣相加，Python的加號運算符用于列表時會直接把兩個列表連接起來哥遮。因此相加的結(jié)果是一個長度為4的列表岂丘，列表中每個元素都是1000×3072的矩陣。將列表傳入vstack后眠饮，會自動調(diào)用元組的構(gòu)造函數(shù)tuple(list)將其轉(zhuǎn)換為元組奥帘。之后，在0號軸上連接這4個矩陣仪召，得到一個4000×3072的矩陣寨蹋。相同的原理松蒜，使用hstack組合訓(xùn)練集標(biāo)簽，這次是在1號軸上連接矩陣已旧。這又是一個很容易出錯的地方秸苗，因為vstack和hstack會認(rèn)為輸入矩陣的維度至少為2，比如运褪，代碼中的y_train其實是一維矩陣难述，按理說它應(yīng)該在0號軸上連接。但是這兩個函數(shù)會把它當(dāng)做二維矩陣吐句，認(rèn)為它是1×1000的矩陣胁后，因此必須在1號軸上連接才能得到1×4000的矩陣。
上面這一段解釋建議多看幾遍嗦枢，就會對理解代碼有所幫助攀芯。num_folds = 5 k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100] X_train_folds = [] y_train_folds = [] ################################################################################ # TODO: # # Split up the training data into folds. After splitting, X_train_folds and # # y_train_folds should each be lists of length num_folds, where # # y_train_folds[i] is the label vector for the points in X_train_folds[i]. # # Hint: Look up the numpy array_split function. # ################################################################################ X_train_folds = np.array_split(X_train, num_folds) y_train_folds = np.array_split(y_train, num_folds) ################################################################################ # END OF YOUR CODE # ################################################################################ # A dictionary holding the accuracies for different values of k that we find # when running cross-validation. After running cross-validation, # k_to_accuracies[k] should be a list of length num_folds giving the different # accuracy values that we found when using that value of k. k_to_accuracies = {} ################################################################################ # TODO: # # Perform k-fold cross validation to find the best value of k. For each # # possible value of k, run the k-nearest-neighbor algorithm num_folds times, # # where in each case you use all but one of the folds as training data and the # # last fold as a validation set. Store the accuracies for all fold and all # # values of k in the k_to_accuracies dictionary. # ################################################################################ for k in k_choices: k_to_accuracies[k] = [] for i in range(num_folds): X_train_cv = np.vstack(X_train_folds[:i] + X_train_folds[i+1:]) y_train_cv = np.hstack(y_train_folds[:i] + y_train_folds[i+1:]) X_test_cv = X_train_folds[i] y_test_cv = y_train_folds[i] classifier = KNearestNeighbor() classifier.train(X_train_cv, y_train_cv) dists = classifier.compute_distances_one_loop(X_test_cv) y_test_pred = classifier.predict_labels(dists, k) num_correct = np.sum(y_test_pred == y_test_cv) accuracy = float(num_correct) / X_test_cv.shape[0] k_to_accuracies[k].append(accuracy) ################################################################################ # END OF YOUR CODE # ################################################################################ # Print out the computed accuracies for k in sorted(k_to_accuracies): for accuracy in k_to_accuracies[k]: print 'k = %d, accuracy = %f' % (k, accuracy)
交叉驗證的結(jié)果如下圖所示，總體趨勢是先上升再下降文虏，在k=10附近準(zhǔn)確度達(dá)到最大值侣诺。
四、總結(jié)
由于是第一次使用NumPy做矩陣運算氧秘，整個過程都感到非常吃力年鸳，不太適應(yīng)向量化計算的寫法。但同時也強(qiáng)烈感受到Python的強(qiáng)大丸相，語法相當(dāng)簡潔搔确，相信熟練了之后編碼效率會很高。
不過灭忠，在我電腦上膳算，向量化計算的用時卻比使用for循環(huán)長了近一倍，而且消耗的內(nèi)存也大了許多弛作，導(dǎo)致數(shù)據(jù)量大的時候出現(xiàn)Memory Error涕蜂。不知道這是什么問題，希望有經(jīng)驗的同學(xué)指點迷津映琳。
Jupyter Notebook也是個挺好用的工具机隙，不過目前還沒發(fā)現(xiàn)如何單步調(diào)試代碼。
最后萨西，包含答案的完整代碼可以從這里下載：
https://github.com/jingedawang/CS231n-Assignments
五有鹿、參考資料
斯坦福CS231n課程作業(yè)# 1簡介 知乎專欄-智能單元
CS231n課程筆記翻譯：圖像分類筆記（上） 知乎專欄-智能單元
CS231n課程筆記翻譯：圖像分類筆記（下） 知乎專欄-智能單元
CS231n課程筆記翻譯：Python Numpy教程 知乎專欄-智能單元
cs231n課程作業(yè)assignment1（KNN） 躺著中槍ing
NumPy v1.12 Manual SciPy.org
