一、前言
CS231n是斯坦福大学开设的一门深度学习与计算机视觉课程，是目前公认的该领域内最好的公开课。目前，该课程的全部资料已经被翻译为中文，非常适合自学。该课程和相关资料的地址如下：
- 在线视频：网易云课堂
- 课程讲义和资料：知乎专栏-智能单元
- 官方网站：http://cs231n.github.io/
课程不光有精彩的讲解，还提供了非常精致的课后作业。唯一的遗憾是作业没有公布标准答案。因此我把自己的答案发出来与大家交流。
二、编程环境
官方建议使用Anaconda，它是Python的一个发布版，包含了最流行的科研、数学、工程和数据分析Python包。只需要安装这一个东西就够了，非常方便。建议下载Python2.7版，因为课程给出的例程都是在Python2.7下测试通过的，而在Python3.x中可能会出错。
从shell启动jupyter notebook，就可以在浏览器中编程了，不需要本地IDE。
三、KNN分类器
用K-最近邻（K Nearest Neighbor，KNN）分类器对图像分类在实际中是不可行的，不过这里只是为了熟悉一些基本的操作，所以第一个作业从KNN开始。
KNN的基本原理是，给定一张测试图片，拿它和所有的训练集图片比较，找出最相近的K个（全部像素向量的欧氏距离越短越相近），由这K个图片的标签投票决定（出现次数最多的标签胜出）测试图片的标签。KNN方法不需要训练时间，但在测试时需要做大量比对，因此测试性能极低。
下面给出Assignment1中的KNN分类器部分的作业答案。
-
两层循环计算距离
下面代码中给出了两种做法，方案1是比较直观的做法，两张图片相减平方再求和。方案2用NumPy提供的norm方法，直接计算范数。
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
-
一层循环计算距离
直接对整个训练集图片操作，此时self.X_train的大小为5000×3072，而X[i]的大小为1×3072，两者相减会自动对X[i]进行广播，使其扩展到与self.X_train相同的大小。如果不清楚广播的用法，可以参考文档。此时执行sum或者norm操作的话，还需要指定轴，令axis=1。NumPy中的轴是个很令人迷惑的概念，根据我的理解，不管多少维的矩阵，轴的序号总是从左向右计数，被指定的轴的大小在操作后会被改变。例如，本例中，np.sum((X[i] - self.X_train) ** 2, axis=1)，里面的运算X[i] - self.X_train的结果是个5000*3072的矩阵，对这个矩阵沿着1号轴求和，从左向右数，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
-
无循环计算距离
这一步倒是很有难度。题目中给出了提示——使用乘法和两个广播求和，可惜我并没想明白怎么用。方案一是我的思路，完全沿袭前面的做法，充分利用广播使两个矩阵扩展到相同的维度。具体来说，原本X的大小是500×3072，现在我把它强行变成500×1×3072，与大小为5000×3072的self.X_train相减，按照广播规则，结果将是500×5000×3072的矩阵。再对2号轴（对应3072的那一维）求和、开根号，最后得到500×5000的矩阵。
方案二则是按照提示的思路实现的（真不知道是怎么想到的）。把计算欧氏距离的式子差的平方展开，变成平方的和减去交叉项的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
-
分类预测
这里用到了argsort函数，输出的结果是从小到大排序后的下标，也就是说，结果列表中的第一个值是最小的数的下标，以此类推。
这句代码closest_y = self.y_train[train_topK_index]用到了整型数组访问语法，即取出self.y_train中以train_topK_index中包含的值为下标的内容。
bincount用来计算列表中每个数出现的次数，任意数字n出现的次数保存在count[n]中。
argmax找出列表中最大值的下标。
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
-
交叉验证
这部分代码比较复杂。首先是把训练集分为5组，使用array_split即可。但需要注意的是，分割结果是一个列表，而不是矩阵。请务必注意列表和矩阵的区别：列表是Python的基本数据类型，而矩阵是NumPy中的数据类型。如果弄混了这一点，后面的程序将会非常难以理解（我就弄混了，所以纠结了很久orz）。接下来，很关键的一点是如何按照5折交叉验证的要求组合训练集。
X_train_cv = np.vstack(X_train_folds[:i] + X_train_folds[i+1:])这句话是容易产生困扰的。vstack用于在0号轴上连接多个矩阵（请按照前面介绍的规则理解这句话。连接后，0号轴的大小将发生变化，而其它轴的大小不变），函数的参数应当为待连接的矩阵组成的元组（tuple）。而在这行代码中，并没有传入元组，而是传入了两个列表相加的结果。首先，这里是列表相加而不是矩阵相加，Python的加号运算符用于列表时会直接把两个列表连接起来。因此相加的结果是一个长度为4的列表，列表中每个元素都是1000×3072的矩阵。将列表传入vstack后，会自动调用元组的构造函数tuple(list)将其转换为元组。之后，在0号轴上连接这4个矩阵，得到一个4000×3072的矩阵。相同的原理，使用hstack组合训练集标签，这次是在1号轴上连接矩阵。这又是一个很容易出错的地方，因为vstack和hstack会认为输入矩阵的维度至少为2，比如，代码中的y_train其实是一维矩阵，按理说它应该在0号轴上连接。但是这两个函数会把它当做二维矩阵，认为它是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)
交叉验证的结果如下图所示，总体趋势是先上升再下降，在k=10附近准确度达到最大值。
四、总结
由于是第一次使用NumPy做矩阵运算，整个过程都感到非常吃力，不太适应向量化计算的写法。但同时也强烈感受到Python的强大，语法相当简洁，相信熟练了之后编码效率会很高。
不过，在我电脑上，向量化计算的用时却比使用for循环长了近一倍，而且消耗的内存也大了许多，导致数据量大的时候出现Memory Error。不知道这是什么问题，希望有经验的同学指点迷津。
Jupyter Notebook也是个挺好用的工具，不过目前还没发现如何单步调试代码。
最后，包含答案的完整代码可以从这里下载：
https://github.com/jingedawang/CS231n-Assignments
五、参考资料
斯坦福CS231n课程作业# 1简介 知乎专栏-智能单元
CS231n课程笔记翻译：图像分类笔记（上） 知乎专栏-智能单元
CS231n课程笔记翻译：图像分类笔记（下） 知乎专栏-智能单元
CS231n课程笔记翻译：Python Numpy教程 知乎专栏-智能单元
cs231n课程作业assignment1（KNN） 躺着中枪ing
NumPy v1.12 Manual SciPy.org
