说明：

1. 本系列文章翻译斯坦福大学的课程：Convolutional Neural Networks for Visual Recognition的课程讲义 原文地址：http://cs231n.github.io/。 最好有Python基础（但不是必要的），Python的介绍见该课程的module0。

2. 本节的code见地址：
   https://github.com/anthony123/cs231n/tree/master/module1-1

3. 如果在code中发现bug或者有什么不清楚的地方，可以及时给我留言，因为code没有经过很严格的测试。

这节课的目的在于向来自计算机视觉背景之外的人介绍图像分类问题和数据驱动方法。这节课的主要内容为:

• 介绍图像分类，数据驱动方法和流程
• 最近邻分类法：K最近邻
• 验证集，交叉验证，超参数调节
• 最近邻方法的优点和缺点
• 总结

图像分类

动机

在这一小节中， 我们将会介绍图像分类问题，即给一个输入图片赋一个标签，这个标签来自于一个固定的标签集。这是计算机视觉的一个核心的问题，尽管很简单，却有很大的实践应用价值。而且，随着课程的深入，你会发现，很多看起来非常不一样的计算机视觉任务（比如物体检测，分割）都可以化简为图像分类问题。

例子

如下图所示，一个图像分类的分类器接收一张图片的输入，并给四个标签（猫，狗，帽子，杯子）分别赋一个概率值，对于电脑来说，一张图片就是一个大的三维数组。在这个例子中，猫的图片大小是248个像素宽，400个像素长，有三个颜色通道：红，绿，蓝（简称RGB）。因此，这张图片由248x400x3个数字，共计297,600个数字组成。每个数字都是一个从0（黑色）到255（白色）的任意整数。我们的任务就是把这一百万个数字转变为一个标签，比如：猫。

图一 图像分类的任务是对一张给定的图片，预测它的标签（或者对一系列标签，给出概率分布图）图像是三维的整型数组，每个元素的值从0~255，三个维度分别为宽x高x3。其中3代表颜色三通道：红，绿和蓝

挑战

既然视觉的识别任务（比如猫）对人类来说比较简单，那么有必要从计算机视觉的角度来考虑下其中的挑战。我下面列出一系列的挑战（不是一个完整的清单），请时刻记住图像的原始表现就是一个三维数组，每个元素代表一个光照强度。

• 视角变化： 对于观察者（人或相机）来说，我们可以从不同的角度去观察一个物体
• 尺度变化： 一个类别的物体通常可以表现出不同的大小（不仅仅是它们在图像中表现的大小，还可能是它们真实大小的差异）
• 形变：很多物体都不是坚硬的，在极端的情况下可能发生形变。
• 遮挡： 物体可能会被遮挡，只有一部分是可见的。
• 光照条件： 光照会对像素值起到非常大的影响。
• 背景影响： 物体可能会融合到环境当中，使得它们难以辨别
• 类别内的差异： 一个类别内的物体可能形状各异，比如椅子。有很多类型的椅子，每种椅子都有它们独特的外形。

一个好的图像分类器应该对以上这些变化都不敏感，而对不同类之间的变化敏感。

数据驱动方法

我们该如何写出一个算法，将图片分到不同的类中呢？和写一个排序算法不一样，写一个图像识别算法（比如猫）可不是那么容易。写一个图像识别算法，不是直接在代码中写出每一种猫的形状，而是使用一种类似于带小孩的方法：我们提供分类器每一类中的许多例子，然后开发一种学习算法，让它观看这些例子，学习每一类的视觉形象。这种方法被称之为数据驱动算法。因为它依赖于首先累计一个带有标记的训练集。下面是一个这种数据集的例子：

一个包含四个种类的训练例子。在实践中，我们可能有上千个种类，每个种类有成百上千张图片

图像分类流程

我们已经知道图像分类的任务是输入一个表示图片的像素数组，我们给这张图片赋一个标签。我们完整的流程可以表示为如下的形式：
1）输入： 我们的输入是包含N张图片的集合，每张图片都被标记为K类中的一种，我们把这个集合称之为训练集
2）学习： 我们的任务是利用这个训练集，来学习一个种类中每个个体长什么样。我们把这一步称之为训练分类器，或者学习一个模型。
3）评价： 最后，我们通过测试一个新的数据集及其标签，来评价这个分类器的质量。我们希望预测能最大程度上和正确答案一致（ground truth）。

最近邻分类器

作为我们的第一种方法，我们将开发最近邻分类器。这种分类器和卷积神经网络没有任何关系，而且它很少用于实践当中，但是它能够帮助我们了解图片分类问题的基本的流程。

图片分类数据集例子： CIFAR-10. 一个著名的小型图像分类算法数据集是CIFAR-10数据集（下载地址为 https://pan.baidu.com/s/1dFaCKFn, 密码为wt7m）。这个数据集包括60,000张小图片，每张图片32像素宽和32像素高。每张图片都被标记为10类中的某一类（比如：飞机，电动车，鸟等）。这60,000张图片被分成50，000张训练集和10,000张测试集。下图你可以看到这10类中随机的10个例子照片。

左边： CIFAR-10中的例子照片。右边：第一列是一些测试照片，随后是和它最近邻的照片

假设我们现在有CIFAR-10测试集中50,000张图片（包括它们的标记），我们希望标记剩下的10,000张图片。最近邻分类器将接收一张测试图片，把它与测试集中的每一张照片比较，然后用最相似照片的标记作为该照片的标记。在上面的图片右边我们可以看出这种方法的10张测试图。我们可以看出，在10张照片中，只有3张和最左边是同一类，其余的七张不是。比如，在第八行中，马头的最近邻图片是一辆红色的车，可能是因为很强的黑色背景。结果导致这匹马被误标记为车。

你可能已经发现，我们还没有讲出如何比较这两幅图的具体的公式，在这个例子中，即如何比较两个32x32x3的矩阵。一个最简单的方法是比较两幅图像的每一个像素，然后将所有的差异加起来。也就是说，给了两张照片，给我两张照片，把它们表示为I1 和I2
, 一个很简单的比较方法便是L1距离

其中，这个总和包括了所有的像素差异，下面以图表的方式表达：

一个用L1距离比较两幅图片的像素差异（例子中只显示了一个颜色通道）。先计算两幅图片的每个像素的差异，然后求所有的差异的和。如果两幅图片一样，那么差异为零。但是如果两幅图片差异很大，那么结果会很大。

让我们看一下如何在代码中实现这个分类器。首先我们下载CIFAR-10的数据，把它以四个数组的形式载入内存：训练数据，训练标签，测试数据和测试标签。在下面的代码中， Xtr（大小为50,000x32x32x3）为训练图片的数据，对应的以为数组Ytr（长度为50,000）为训练的标签（从0到9）：

Xtr, Ytr, Xte, Yte = load_CIFAR10('data/cifar10') #a magic function

#flatten out all images to be one-dimensional
Xtr_rows = Xtr.reshape(Xtr.shape[0], 32*32*3)
Xte_rows = Xte.reshaoe(Xte.reshape[0], 32*32*3)

现在我们将所有的图片都延展到一行中，下面是我们训练和检验分类器的方法：

nn = NearestNeighbor() #create a Nearest Neighbor classifier classifier
nn.train(Xtr_rows, Ytr) #train the classifier on the training images
Yte_predict = nn.predict(Xte_rows) #predict labels on the test images

#and now print the classification accuracy, which is the average num
#of examples that are correctly predicted(i.e. label matches)
print 'accuracy: %f' %(np.mean(Yte_predict == Yte))

通常我们使用准确率（预测准确的比例）作为评价的标准，我们建立的所有分类器满足一个共有的API： 它们有一个train函数，以数据和标签作为学习的素材。在内部， 这个方法应该能够建立某种关于标签及如何预测数据的模型。然后，有一个predict函数，它接收一个新的数据，然后预测它的标签。当然，我们至今还没谈到最重要的部分，即分类器本身。下面是一个简单的基于L1距离的最近邻分类器的一个实现

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 
    # 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        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的准确率只能达到38.6%。这比随机猜的准确率更高（随机猜的准确率略为10%），但是还是比人类（人类的准确度可以达到94%）或者卷积神经网络（可以达到95%）的表现差很多。

距离的选择

还有很多其他的方法来计算向量之间的距离，另外一个经常使用的选择是L2距离 从几何的角度，可以将其解释为计算两个向量的欧式距离（euclidean distance）。 公式如下：

也就是说，我们像以前一样，还是计算像素之间的差异，但是这一次，我们都求差异的平方，然后把它们相加，最后求开方。使用Python的numpy模块，使用上面的代码，我们只需要替换上面一行代码，也就是计算距离的那段代码：

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

我们可以看到我使用了np.sqrt函数，但是在实践中，我们可能不使用开方操作，因为开方函数是一个单调函数，即它只缩小了距离的大小，同时它保持了它们之间的顺序。所有有没有开方操作都一样。如果你使用L2距离在CIFAR-10上运行这个程序，那么你的准确度可以达到35.4%（比L1距离稍低）。

L1 vs. L2

考虑两个矩阵之间的差异是个很有趣的问题。具体来说，当测量两个矩阵之间的差异，相比于L1距离，L2距离的容忍性更低。也就是说，L2距离更喜欢很多中等程度的差异，而不是一个非常大的差异。L1距离和L2距离（一对图片差异的L1/L2范式）是P范式中最经常使用的两个特例。

K-近邻分类器

你可能已经注意到当我们做预测时，只使用最近邻图片的标记是非常奇怪的。确实，当我们使用k近邻分类器时，往往能够得到更好的结果。这个想法很简单： 不是在测试集中寻找最接近的那张图片，我们会寻找最近邻的k张图片，然后从这k张照片中找出最适合的标记。当k=1时，就变成最近邻分类器。K的值越高，会使得分类器对异常值（outliers）更有抵抗力。

最近邻和5-最近邻区别的一个例子，使用二维点和三个类（红，蓝，绿）。有颜色的区域是L2距离的分类器的决策边界。白色区域表示点无法被分类（这个点至少在两个类的投票中处于平局）。我们可以观察到，在NN分类器情况下，异常点（比如在蓝色点群中的绿色点）会创建小的不正确的区域，而5-NN分类器能够正确的处理这种情况。同时可以发现，在5-NN中有一些灰色区域，这些灰色区域是由在最近邻投票相等而导致的。

在实践中，你几乎总是需要使用k近邻。但是我们应该如何决定k的值呢？我们下面来关注这个问题。

用于超参数微调（Hyperparameter tuning）的验证集（validation sets）

k近邻分类器需要设定k值。那么设置哪个数字效果更好呢？除此之外，我们看到有很多距离函数可以使用: L1范式 和L2范式，但是也还有很多其他选择我们没有考虑（比如：点积）。这些选择称之为超参数，在设计机器学习算法中它们经常出现，通常它们的值都不是非常容易确定。
我们可能会被建议尝试许多值，然后在其中选择最好的。这是个好方法，也是我们接下来使用的方法，但是我们必须要非常谨慎。特别是，我们不能使用测试集来微调超参数 当你设计机器学习算法时，你都应该将测试集视为一种珍贵的资源，只有到最后面才能使用。否则，你可能调试你的超参数，使得它们在测试集上有很好的表现，但是当你发布你的模型时，你可能发现你的模型效果会大大降低。在实践中，我们会将这种现象称之为过拟合（overfit）。另外一个看待这个问题的方式是如果你基于测试集调整了你的参数，那么你就把测试集当成了训练集。那么你就会对你模型的效果过度乐观。如果你只在最后使用测试集，那么它就能很好的测量你分类器的可扩展性（generalization）（在接下来的课程中你会看到对可扩展性更过的讨论）

    只能在最后评估你的测试集一次

幸运的是，有一种正确的方法来调整超参数而且不会使用到测试集。这个想法是将测试集一分为二：一个稍微小的测试集，我们称之为验证集，其余部分作为真正的训练集。使用CIFAR-10 为例子，我们使用49,000的测试图片作为训练集，1,000作为验证集。验证集可以作为一个伪测试集，来调整超参数。

在CIFAR-10中，可能会是这样：

# 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  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))

在这个过程的结尾，我们可以画一张图，表明k取哪个值才是最好的。之后会使用这个值，并在真正的测试集中评估一次。

把你的测试集分成测试集和验证集。使用验证集来调整所有的超参数。最后，在测试集中测试，并报告结果。

交叉验证

在训练集很小的情况下， 人们通常会使用一个更成熟的技术来调节超参数，这种技术称之为交叉验证。 以我们之前的例子为例，不是取前1000个点作为验证集，剩下的作为训练集，而是使用一种更好的，噪音更少的评估K的方式，这种方式通过遍历不同的验证集，然后去这些验证集的平均值。比如：在5重交叉验证（5-fold cross-validation）中，我们将测试集分成五等分，使用其中的四份作为测试集，1份作为验证集。我们分别将其中一份作为验证集，评估其效果，然后使用平均值作为最终的结果。

五重交叉验证决定k的一个例子。对于k的每个值，我们训练四份数据，并用第五份数据进行评估。所以，对于每个k我们可以在验证集上得到5个准确度。（准确度是y轴，每个结果是一个点）趋势线（the trend line）是通过对于每个k，平均每个结果得到，误差线（error bar）表示标准差。在这个情况下，交叉验证的结果表明k=7的效果最好（根据最高点的值）。如果我们使用多于5重，那我们可以预期一个更平滑（更少噪声）的曲线.

实践

在实践中，人们倾向于避免交叉验证，而喜欢一次验证分割，因为交叉验证计算量很大。人们一般使用训练集的50%~90%作为真正的训练集，剩下的作为验证集。然而，这也取决于多个因素：比如如果超参数的数量很多，你可能倾向于使用更大的验证集。如果验证集的数目太少（只有几百个），那么使用交叉验证比较安全。通常的交叉验证为3重，5重，10重交叉验证。

数据分割。训练集和测试集已经给出。训练集被分为几份（比如5份）。其中1-4成为训练集。一份（比如黄色的那一份）作为验证集，用来调节超参数。交叉验证做的比这些更多，遍历所有可能的验证集的选择，这被称之为五重交叉验证。最后，当模型已经训练完后，所有的超参数已经决定好，模型就可以在测试集（红色）上测试（只能使用一次）了。

最近邻分类器的优点和缺点

现在来考虑下最近邻分类器的优点和缺点。很显然，一个优点是它非常简单而且很容易理解。除此之外，这个分类器不需要训练，我们需要做的就是存储和索引训练数据。所以。我们计算的花费主要在测试时间上，因为分类一个测试集需要将其与每一个训练集进行比较。这是不符合常理的（backwards），因为在实践中，相比于训练时间，我们经常更关心的是测试的时间效率。实际上，我们接下来开发的深度神经网络会交换这个计算成本分配，即它们训练的成本非常高，但是一旦训练完成，就很容易测试。这种模式在实践中更可行。
除此之外，最近邻分类器的计算复杂度也是一个活跃的研究领域。一些近似最近邻算法（Approximate Nearest Neighbor ANN）可以加速在数据集中对最近邻的查找（比如：FLANN）。这些算法可以在最近邻的正确性和空间/时间复杂度上做出一个权衡，通常依赖于一个预处理/索引阶段 即建立一个kdtree或运行k-means算法。

最近邻分类器有时候是一个好的选择（特别是当数据是低维数据的时候），但是它很少适合运用在图像分类情境中。其中一个很重要的原因为图像是高维物体（比如，它一般包含很多像素），高维空间的距离可能是违反直觉的。下面的图片表明这个观点： 逐像素L2相似和直觉的相似非常不同：

高维度数据的基于像素距离可以是违反直觉的。原图（左边）和旁边三个其他的图像和原图的距离是一样的。显然，逐像素距离和感知或者语义相似并不一一对应。

下面以更可视化的形式向你展示 仅仅使用像素差异比较图像是远远不够的。我们使用了一个可视化技术（t-SNE）来接收一个CIFAR-10的图片，并把它们排列在二维空间中以便它们的距离能够最好的保持。在下图中，近邻的图片是在L2距离非常相近

使用t-SNE 将CIFAR图像放入两个维度当中。在上面图片中，相邻的图片的L2距离比较近。可以看出背景而不是语义的强大作用。

特别的，临近的图片更多的是因为图像的整体颜色分布，或者背景的类似而不是它们的语义相同。比如，一条狗可能被认为和一只青蛙很相似，因为它们都是在白色背景中。我们希望所有10个类的图像能够形成它们各自的聚类，同一个类的物体能够在各自的附近，而不受不重要的特征或变量的影响（比如背景）。然而，为了获得这种特质，我们需要做的往往比仅仅比较像素值更多。

总结：

• 我们引出了图像分类的问题，即给出一序列的图片，每张图片都有一个标记，我们需要预测一个新的测试集中图片的标记，然后测量预测的准确性。

• 我们介绍了一个简单的分类器，最近邻分类器。我们发现这种分类器有多个超参数（比如k的值，或者距离函数的类型），并且没有一个简单的方法决定它们的值

• 我们发现最简单的设置这些超参数方式是将测试数据一分为二，一个作为真正的测试数据，一个作为伪测试数据，称之为验证数据。我们尝试不同的超参数，并在验证集里保持有最好效果的值。

• 如果训练数据量不是很多，我们讨论了一种方法叫做交叉校验，它可以在估计超参数的时候帮助减少噪音。

• 一旦最好的超参数找到了，我们最后在真正的测试集上测试。

• 我们发现最近邻可以在CIFAR-10得到得到大约40%的准确度。它很容易实现，但是需要我们存储整个训练集，而且在测试阶段花销很大。

• 最后，我们看到在图像的像素值上使用L1或L2距离是不够的，因为距离与背景，图像的颜色分布更相关，而不是和语义内容。

在下一节课中，我们开始解决这些挑战，并最终达到约90%的准确度，并允许在我们训练完成后，可以完全抛弃测试集，并使得我们能够在少于1毫秒的时间内评价一张测试图片。