本系列文章是http://cs231n.stanford.edu/syllabus.html 系列课程笔记
Image Classification 图像分类
在这个部分介绍了图像识别的问题，如何将一个单label的图像做一系列的分类，在计算机视觉上有很重要的应用，进一步的，很多其他看上去棉线的机器视觉的任务也能够被简化为图像分类，如下面的图片要将他分成四类，猫狗帽子或者杯子，在图片中，我们看到这个图片被表示成一个三维的数字，248pi宽，400pi高并且有三种颜色，进一步来看，这个图像有2484003的数字，每一个数字都从0-255。我们的任务就是如何从这个数字预测出这个图片的标签比如猫。
挑战。由于识别视觉概念（例如猫）的任务对于人类来说相对来讲是微不足道的，但是从计算机的角度来看是很难的。
- 视点的不同，同样的物体不同的角度看不同的相机拍效果都不一样
- 尺度变化，尺寸可能也会不同
- 形变，有时候会发生物体的形变
- 有时候可能会被遮挡
- 背景比较混乱也会造成识别困难
- 同种类别比如猫之间也会有很大的差异
我们已经看到，图像分类中的任务是使用一个像素数组来代表一个图像，并为其分配一个标签。我们的pipeline可以正式化如下：
输入：我们的输入由一组N个图像组成，每一个都标有K个不同的类别。我们将这些数据称为训练集。
学习：我们的任务是使用训练集来了解每一个班级的样子。我们将此步骤称为训练分类器，或者学习模型。
评估：最后，我们通过要求它预测一组从未见过的新图像的标签来评估分类器的质量。然后，我们将这些图像的真实标签与分类器预测的图像进行比较。直观地，我们希望很多预测与真实答案（我们称之为真相）相匹配。
最近邻算法
假设我们现在又CIFAR-10的5万张已经有标签的数据现在要对剩下的一万打标签，这时候最近邻方法是拿一个测试的图片，然后将它跟其他训练的数据进行比对，选择最相似的。您可能已经注意到，我们未详细说明我们如何比较两个图像的细节，这两个图像在这种情况下只是32 x 32 x 3的两个块。最简单的可能性之一是逐个比较图像，并将所有图像相加差异。换句话说，给定两个图像并将其表示为向量I1，I2，比较它们的合理选择可能是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
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) )
关于最近邻最简单的实现：
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
这种最简单的算法也能达到36.8%的准确率，比起盲投肯定是高的
当我们换成L2距离的方法的时候，这考虑到了两个向量之间的几何距离
换句话说，我们将像以前一样计算像素差异，但是这次我们将它们全部平方，加起来，最后取平方根。在numpy中，使用上面的代码，我们只需要替换一行代码。计算距离的线：
distances = np.sqrt(np.sum(np.square(self.Xtr - X[i,:]), axis = 1))
请注意，我包括上面的np.sqrt调用，但在实际的最近邻应用程序中，我们可以省略平方根操作，因为平方根是一个单调函数。也就是说，它缩放距离的绝对大小，但它保留了排序，因此与或不相邻的最近邻居是相同的。如果您使用该距离在CIFAR-10上运行最近邻分类器，则可以获得35.4％的精度（略低于我们的L1距离结果）。
L1与L2。考虑两个指标之间的差异是有趣的。特别地，当涉及两个向量之间的差异时，L2距离比L1距离容忍度低，也就是说，L2距离更倾向于一个大的中等的分歧。 L1和L2距离（或等效地，一对图像之间的差异的L1 / L2范数）是p范数最常用的特殊情况。
KNN
您可能已经注意到，当我们想进行预测时，只能使用最近图像的标签是奇怪的。事实上，通过使用所谓的最近邻分类器，人们可以做得更好。这个想法很简单：不是在训练集中找到单个最接近的图像，而是找到最上面的k个最接近的图像，并将它们投影在测试图像的标签上。特别地，当k = 1时，我们恢复最近邻分类器。直观地，较高的k值具有平滑效果，使分类器更能抵抗离群值：
k最近邻分类器需要k的设置。但什么数字最有效？另外，我们看到我们可以使用许多不同的距离函数：L1 norm，L2 norm，还有许多其他选择，我们甚至没有考虑（例如点产品）。这些选择被称为超参数，并且它们经常在设计许多机器学习算法的过程中学习数据。通常不清楚什么值/设置应该选择。
你可能会试图建议我们尝试许多不同的方法，看看哪些效果最好。这是一个好主意，这确实是我们将要做的，但这必须非常仔细地进行。特别是，我们不能使用测试集来调整超参数。每当您设计机器学习算法时，您应该将测试集视为一个非常宝贵的资源，理想情况下，只能用一次。否则，真正的危险是，您可以调整您的超参数在测试集上运行良好，但如果要部署模型，则可以看到性能显着降低。在实践中，我们会说你过分考虑了测试集。另一种观察方式是，如果您在测试集上调整超参数，则您有效地使用测试集作为训练集，因此您实现的性能对于您实际观察到的效果将是过于乐观部署模型时。但是，如果最终只使用测试集，那么它仍然是测量分类器泛化的一个很好的代理（我们将在课后稍后再看到关于泛化的更多讨论）。
幸运的是，有一个调整超参数的正确方法，它根本没有接触测试集。这个想法是将我们的训练集分为两部分：稍微小一点的训练集，我们称之为验证集。以CIFAR-10为例，我们可以使用49,000个训练图像进行训练，并留下1000个进行验证。该验证集基本上用作假测试集来调整超参数。
# 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))
交叉验证。在您的训练数据（因此也是验证数据）的大小可能很小的情况下，人们有时会使用更为复杂的超参数调优技术，称为交叉验证。使用我们前面的例子，这个想法是，而不是任意选择前1000个数据点作为验证集和休息训练集，您可以通过迭代不同的方式获得更好，更低噪声的k值的确定值的良好估计验证集合并对其进行平均。例如，在5倍的交叉验证中，我们将训练数据分成5个相等的折叠，其中4个用于训练，1个用于验证。然后，我们将迭代哪个折叠是验证折叠，评估性能，最后平均不同折叠的性能。不过这个计算的代价很大所以一般不用。
最近邻分类器的优缺点 显然，一个优点是实现和理解非常简单。另外，分类器没有时间进行训练，因为所需要的是存储和可能地对训练数据进行索引。然而，我们在测试时间支付计算成本，因为分类测试示例需要与每个训练示例进行比较。这是倒退的，因为在实践中，我们经常关心测试时间效率远远超过训练时间的效率。事实上，我们将在这个班级稍后发展的深层神经网络将这种权衡转移到另一个极端：培训费用非常高，但一旦培训完成，对新的测试实例进行分类就非常便宜。这种操作模式在实践中更为理想。
除此之外，最近邻分类器的计算复杂度是一个有效的研究领域，并且存在可以加速数据集（例如FLANN）中的最近邻查找的几个近似最近邻（ANN）算法和库。这些算法允许在检索期间以其空间/时间复杂度来折衷最近相邻检索的正确性，并且通常依赖于涉及构建kdtree或运行k均值算法的预处理/索引阶段。
在某些设置中，最近邻分类器有时可能是一个很好的选择（特别是如果数据是低维数据），但很少适用于实际的图像分类设置。一个问题是图像是高维度对象（即它们通常包含许多像素），并且高维空间上的距离可以是非常直观的。下面的图像说明了我们上面开发的基于像素的L2相似度与感知相似性的区别。
总结一下：如果要在实际中应用knn需要注意以下问题：首先你应该将你的数据标准化，因为图像数据往往是同源的而且一般不会表现出不同的分布。其次，如果你的数据是高维的那么你应该考虑先降低维度使用PCA或者RP。另外应该做样本的训练集和测试集的划分，如果参数比较多，你应该保持更大的测试集，所以最好是用较差验证，当然只要计算能力能承受都最好做个交叉验证。如果你的knn运行时间过长，可以用FLANN来加速。
