CS231n笔记系列（一）
数据驱动的图像分类方式——K近邻与线性分类器（上）
1.Image Classification：a core task in Computer Vision
为什么图像分类问题在计算机里很困难？语义鸿沟问题。图像在计算机里是一个巨大的表单，可以由长*宽*（R，G，B）表示。难点在于如何处理这些表单里的数字。摄像机的摄影方式可以不同，使图片样式不同，但是被摄对象不变。还有其它问题例如光线问题、被摄对象的形态不同、遮蔽、同类演变等。对于这些问题，我们的解决方法应有鲁棒性。
2.Nearest Neighbor Classifier
图像分类器是怎样的呢？构建一个三维空间，x轴为种类标签值，但没有一种显式分类器能实现这个过程。传统方法曾尝试勾勒出边界，按边界形状和连结方式进行分类，以此监测物体的某些结构特征。这是不可扩展的学习方法。所以我们现在采用数据驱动的学习方法。我们可以根据被分类对象的数据训练相应的模型，它是和这个对象对应的类，之后可以对你的测试数据基于模式匹配和统计等进行分类。
分类过程是怎样的呢？假设我们有若干个从CIFAR-10数据集里抽取的例子，我们要从训练集中找一个与这些图像中每个独立图像最相近的近似。我们如何度量“相似”？第一种方法是曼哈顿距离，又称L1距离。我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标（x1, y1）的i点与坐标（x2, y2）的j点的曼哈顿距离为：
在图像中，我们将逐元素比较所有的像素值，计算同一空间位置下的像素值之差，差值全部相加，就得到了相似性。但是这种分类器随着数据规模的扩大分类速度线性减慢。在训练方法和测试方法中我们需要权衡，这种分类器尽管花了大量时间在测试上，但是训练速度很快。无论训练集有多大，我们对每一张测试实例进行分类的计算量是恒定的。（ps：如何使近邻算法分类器加速？近似近邻算法&FLANN实例库？）Nearest Neighbor分类器易于理解，实现简单。其次，算法的训练不需要花时间，因为其训练过程只是将训练集数据存储起来。然而测试要花费大量时间计算，因为每个测试图像需要和所有存储的训练图像进行比较，这显然是一个缺点。在实际应用中，我们关注测试效率远远高于训练效率。其实，我们后续要学习的卷积神经网络在这个权衡上走到了另一个极端：虽然训练花费很多时间，但是一旦训练完成，对新的测试数据进行分类非常快。这样的模式就符合实际使用需求。
常用的距离是欧几里得距离又称L2距离，计算图像间差值的平方和：
那么这一选择到底要如何进行距离的计算呢？一个进行控制的离散选择，我们这个距离的选择我们称为超参数。另一个超参，将近邻推广为最近邻规则分类器KNN，在最近邻规则分类器中检索每张测试图像。一个好的近邻算法要做的事是：在训练集中检索到若干张最相似的图像，然后对他们的标签进行多数表决。
3.k-Nearest Neighbor Classifier
当k=1的时候，k-Nearest Neighbor分类器就是Nearest Neighbor分类器，从直观感受上就可以看到，更高的k值可以让分类的效果更平滑，使得分类器对于异常值更有抵抗力。需要注意的是，在NN分类器中，异常的数据点（比如：在蓝色区域中的绿点）制造出一个不正确预测的孤岛。5-NN分类器将这些不规则都平滑了，使得它针对测试数据的泛化（generalization）能力更好（例子中未展示）。注意，5-NN中也存在一些灰色区域，这些区域是因为近邻标签的最高票数相同导致的（比如：2个邻居是红色，2个邻居是蓝色，还有1个是绿色）。
4. How Do We Set the Hyperparameters?
如何调优超参？可以尝试不同的值，看哪个表现好就选哪个，但是要特别细心。特别注意：不要用测试集调优。会对测试集过拟合，实际效果可能不好；也等于把测试集并入训练集，不能很好的测试所设计的分类器的泛化性能。
从训练集中取出一部分数据用来调优，我们称之为验证集，其实就是作为假的测试集来调优。有时候，训练集数量较小（因此验证集的数量更小），人们会使用一种被称为交叉验证的方法，在实际情况下，人们不是很喜欢用交叉验证，主要是因为它会耗费较多的计算资源。一般直接把训练集按照50%-90%的比例分成训练集和验证集。
引用：知乎-智能单元-杜客
