此笔记基于斯坦福cs231n课程。
作者：武秉文Jerry，bingwenwu@foxmail.com
转载请注明出处

目录

• 图像分类介绍，数据驱动(data-driven)方法，pipeline。
• 最近邻分类器
  • k-Nearest Neighbor
• Validation sets, 交叉验证, hyperparameter tuning（调整）
• 最近邻方法的优缺点
• 总结
• 总结：在实践中运用kNN
• 扩展阅读

图像分类

Motivation. 这部分我们会介绍图像分类问题，它的任务是从一个固定的标签目录中为输入的图片分配一个标签。这是计算机视觉的核心问题之一，尽管看似很简单，但有很大的应用领域。另外，很多其他看似不相干的计算机视觉问题（比如物体检测，分割）可以被简化为图像分类问题。
Example. 下图中，一个图像分类模型取一张图片并且分配可能性到4个类别。{cat, dog, hat, mug} 但像图中所示，记住对于电脑而言，一个图片由一个三维数组表示。这个例子中，猫图片248 pixels宽， 400
pixels长，有三种原色表示（RGB）。因此，这个图片包括248 * 400 * 3个数据，总共297,600个数字。每个数字是一个0 - 255范围内的整数。我们的任务是将这么多数字转为一个单独的标签，比如cat。

Image Classification

图像分类的任务就是对给定的图片预测一个标签（或者是标签概率的分布，如图中所示)。图像是一个三维数组表示，从0到255，尺寸是长乘宽。3表示三原色，Red,Green,Blue。
Challenges. 因为识别物体（比如“猫”）对于人类是很简单的，所以从计算机视觉算法的角度考虑挑战是有价值的。下面列出了很多挑战，注意图片的原始表示是三维数组。

• 视角变化。一个对象的实例可以从不同角度观察。
• 尺寸变化。对象的大小会不同。
• 畸变。可能图片中的对象发生变形。
• 不完整。图片中的对象不是完整的显现出来，可能部分被遮挡。
• 照明条件。光照影响在像素级上影响很大。
• 背景混乱。对象可能隐藏在背景中。
• 同类别变化。同一类对象可能有不同的样子，比如猫就很多种类，样子不同。

良好的图像分类模型必须对所有这些变量的交叉乘积保持不变，同时保持对类间变化的敏感性。

Variation

数据驱动方法（Data-driven approach)。我们如何写一个算法去将图片分到对应的类别？不同于写一个排序算法，写一个识别猫的图片的算法不是那么简单直接。不是直接在代码中指定每种感兴趣的类别，而是要为计算机提供每个类别的很多实例，然后构建学习算法，学习每一类图片。这个方法叫做你数据驱动方法。（data-drvien approach）。因为它首先依赖于一个有标签的训练集（training set）。这里是一个这样的数据集的示例：

Dataset

一个四类物体的训练集示例。实际中可能有几千个分类，每个类别下有几百张图片。

The Image classification pipeline. 完整的流程可以简化为如下三步：

• Input。我们的输入包括一个N张图片的集合，每张图片都有对应的标签。我们把这个集合叫做训练集（training set）。
• Learning。我们的任务是使用训练集去学习每个分类应该长什么样。我们把这一步叫做训练一个分类器（training a classifier），或者学习一个模型（learning a model）。
• Evaluation。最后，我们要评价分类器的性能，方式是对一组没有见过的图片进行分类。然后比较正确的标签和分类器分类后的标签。

最近邻分类器 Nearest Neighbor Classifier

作为我们的第一种方法，我们将先构建一种叫做最近邻分类器。这种分类器和CNN没有关系并且实际中很少使用，但它能让我们对图片分类问题的基本方法有一点了解。
Example Image classification dataset: CIFAR-10。一个很流行的图片分类数据库。这个数据库包括60,000图片，32 x 32像素。每一个图片都被10个标签中的一个标注了。这60,000图片被分为50,000的训练集和10,000的测试集。下面的图片能看到十个分类中随机的十个图片。

cifar-10
左侧：CIFAR-10中的图片。右侧：第一列显示一些测试图片，后面显示的是训练集中根据像素相似度差异计算后最接近的10个邻居。

假定现在我们给定了CIFAR-10中的50,000张训练集图片（每个标签5000张），然后我们希望去标注剩下的10,000张。最近邻分类器会去一张测试图片，拿他和每一张训练图片对比，然后取相似度最高的训练集图片标签作为该测试图片的标签。上图中右侧的图片就是10张测试图片的结果。注意10张图片中只有3张测试正确，其他7张出现了错误。比如第8行与马头最接近的图片是红色汽车，似乎是因为背景的原因，所以被错误标注成了一辆车。

你可能已经注意到我们没有具体说如何比较两张图片。在这个例子中，是两个32x32x3的数组。最简单的方式是每个像素进行比较，然后每个像素的差异求和。换句话说，给定两张图片并且将他们表示为两个向量I_1和I_2，比较他们的一个合理的方法是L1 distance：

\begin{equation}
d_1 (I_1, I_2) = \sum_{p} \left| I^p_1 - I^p_2 \right|
\end{equation}

这里有一个可视化的过程：

L1 distance

可以看出如果两张图片完全一样的话，结果为0。两张图片差别越大，结果也就越大。

现在看一下如何用代码实现分类器。首先我们要载入CIFAR-10数据到内存中。形式是4个数组：训练数据、训练数据标签、测试数据、测试数据标签。在下面的代码中，Xtr（50000 x 32 x 32 x 3）保存训练集中所有的图片信息，Ytr（50000 x 1）对应测试集的标签（0-9）：

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

注意作为评价的标准，常常使用accuracy，意思预测正确的百分比。注意我们构建的所有分类器满足一个通用的API：他们有一个train(X,y)函数，输入训练数据和对应的标签。内部看，这个类会构建某种模型用于预测标签。并且还有一个predict(X)函数，输入新的数据然后输出预测的标签。下面是一个简单的使用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 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

如果你跑这段代码，你会发现这个分类器在CIFAR-10上只有38.6%的准确率。虽然比随机猜一个的准确率高不少，但离人类的水平（大约94%）和最先进的CNN（95%）还差了很多。

The choice of distance。有很多种方法计算两个向量之间的距离。另一个常用的选择是使用L2 Distance，它是计算两个向量之间欧式距离的几何解释。形式如下：

\begin{equation}
d_2 (I_1, I_2) = \sqrt{\sum_{p} \left( I^p_1 - I^p_2 \right)^2}
\end{equation}

换句话说，我们还和之前一样计算像素之间的差距，但是这一次我们将它平方，再求和，之后在开方。在numpy中，用下面的代码我们只需要替换一行代码即可。计算距离的那一行代码：

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

注意我们包括了np.sqrt的调用，但是在实际的最近邻应用中我们丢掉了开方操作因为开方是一个单调函数。只是距离大小值发生了变化，但还是保留了排序，所以对于最近邻而言，有没有开方都是一样的。如果这时在CIFAR-10上面测试，准确率为35.4%。（比L1还要低一点点）。

L1 vs. L2。讨论两种测量方法的不同是很有意思的。特别是，当涉及到两个向量的不同时L2更加不可饶恕。也就是说，L2更偏向于大的不同。L1 and L2 distance (or equivalently the L1/L2 norms of the differences between a pair of images) are the most commonly used special cases of a p-norm。

k-Nearest Neighbor Classifier（k阶最近邻分类器）

你可能已经发现单单只看距离最近的图片的标签是很奇怪的。确实，几乎任何情况下，用k-Nearest Neighbor Classifier的效果都更好。原理很简单：不只找训练集中差别最小的一幅图片，我们找差距最小的k张图片，然后这k张图片投票产生测试图片的标签。实际中，当k=1，就是最近邻分类器。较高的k值对类别之间的边界起到了光滑作用。

kNN

上图说明了NN和k-NN之间的区别。不同颜色区域表示分类器用L2距离的分类边界。白色区域是无法分类的点（即至少两个类别的投票结果相同）。注意NN中在蓝色点之间的一个绿色点，这个点生成了一小片可能错误预测的区域。但是在5-NN中消失了，所以分类器更加一般化。

实际中，k-NN总是你的选择，但是k值应该用多少呢？我们下面讨论。

Validation sets for Hyperparameter tuning

用于调整超参数的验证集合

k-NN分类器需要给定一个k值。但是多少最合适呢？另外，我们看到有很多计算距离的方法，比如L1和L2。这些选择叫做hyperparameter（超参数），他们在设计机器学习算法中常常出现，而且通常很难直观的知道应该选择哪一个。

你可能会想到我们把不同值都试一下，看哪个表现最好。这是个好想法并且也确实是我们要做的，但要非常谨慎的去做。特别是，我们不能用测试集去调整超参数。在设计机器学习算法的任何时候，你都应将测试集当做很珍贵的资源，直到最后才能使用。否则，很可能你的超参数在测试集上性能很好，但真正部署以后，性能会大大下降。实际上，我们将这样的情况称作overfit（过拟合）测试集。从另一个角度看，如果在测试集上调整超参数，你实际上将测试集也当做了训练集。但如果你最后只用了一次测试集，它能够保证分类器良好的generalization（一般性）。

只在最后用测试集进行一次性能评估。

幸运的是，有一种方法可以在不碰测试集的情况下调整超参数。这个想法是将训练集分为两部分：一个相对较小的训练集，我们叫做validation set（验证集）。用CIFAR-10当例子，我们可以用49000当做训练集，剩下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))

这个过程的最后，我们能够画出一张图，显示出哪个k值效果最好。然后我们可以固定这个值去在测试集上进行评估。

将训练集分为一个训练集和一个验证集。使用验证集去调整超参数。最后在测试集上评估效果。

Cross-validation（交叉验证）。如果你的训练集相对较小，人们有时使用更复杂的一种方法用于调整超参数，叫做cross-validation（交叉验证）。使用之前的例子，想法不是简单的随机选出1000个图片当做验证集，剩下的当训练集。你可以通过对不同的验证集进行迭代并对这些性能进行平均，您可以得到一个更好且较少噪声的估计k的某个值的工作情况。比如5折交叉验证，我们将训练集平均分为5个部分，其中4个用于训练，1个用于验证。然后我们迭代5次，让每一个部分都能当一次验证集，评估分类器的性能，最后在不同折上取平均性能。

---

Cross-validation on k

一个例子，针对k值的5折交叉验证。对于每一个k值我们在4折上训练然后在第5折上验证。因此，对于每一个k值我们有5个准确率结果。（准确率在图中为y轴，每一个结果是一个点。趋势线是每个k值5个结果的平均值连接而成，上下边界表示标准差。注意在这个例子中，交叉验证显示k=7时分类器效果最好。（对应图片中趋势线的峰值）。如果我们使用更多折的交叉验证，我们会看到更加平滑的曲线。

---

In practice。实际过程中，人们一般更偏向于避免使用交叉验证，而是分出一个独一无二的验证集，因为交叉验证的计算成本比较高。一般使用训练集的50%-90%用于训练，剩下的数据用于验证。然而分割训练集数据依赖于很多条件：比如如果超参数的数量比较多那么你应该使用更大的验证集。如果验证集中的样本数量较少（可能只有几百个），最好使用交叉验证。典型的选择是3折，5折，10折交叉验证。

---

splits

一般的数据分割。一个训练集和一个测试集是给定的。训练集被分为若干折（这里是5折）。1-4折成为训练集。一折（这里黄色的fold 5）作为验证集用于调整超参数。交叉验证的下一步就是迭代，让每一折都做一次验证集，这就是5折交叉验证。最后一旦模型训练完成并且所有最优超参数都已经被确定，就可以用测试集（红色部分）评估性能了。

---

最近邻分类器的优缺点
显然，一个优点就是很容易理解和实现。另外这种分类器不需要时间去训练，因为它需要的只是存储记忆训练集数据。然而在测试阶段我们需要花费不少算力，因为给一个测试用例分类需要和每一个训练样本比较。这就是它的缺点，因为实际中我们更关注的是测试时的分类效率，而不是训练时的效率。实际上，之后我们学习的深度神经网络将这种权衡提升到了另外一个极端：训练时需要很大的算力，但是一但训练结束，分类时效率极高。这是实际中我们所期待的。

另外一方面，最近邻分类器的计算复杂度是很活跃的一个研究领域，一些近似最近邻算法（Approximate Nearest Neighbor)(ANN)和存在的库文件可以加速最近邻在数据集中的查找速度(e.g. FLANN，这些算法允许在检索期间将最近邻居检索的正确性与空间/时间复杂度进行权衡，并且通常依赖于涉及构建kdtree或运行k-means算法的预处理/索引阶段。

最近邻分类器有时在某些设定下是一个很好的选择（尤其是当数据是低维度的时候），但是实际中很少使用它去进行图片分类。一个问题是图片都是高维度的对象（即图片一般包含很多像素），计算高维度空间的距离是很不直观。下面的图片说明了我们之前构建的基于像素之间L2相似度的想法和感知相似度是不同的：

---

high-demensional

在高维度基于像素的距离可以是很不直观的。一张原始图片（左侧）和三张其他图片的L2距离是完全相同的。显然，像素间距离不能对应所有的感知或者语义的相似程度。

---

这里有一个更加可视化的例子证明使用像素差异去比较图片是不合适的。我们可以使用一个可视化工具叫做t-SNE，使用CIFAR-10图片，将它们嵌入到两个维度之中，以便保持它们（局部）距离。在此可视化的基础上，根据我们构建的L2距离，附近的图片被认为是非常接近的：

---

t-SNE
使用t-SNE将CIFAR-10图片嵌入到二维空间中。基于L2距离，彼此靠近的图片被认为是很相似的。注意图片背景相比于图片中真正的对象锁带来的更大影响。点击这里看更完整的可视化结果。

---

注意彼此靠近的图片更多是因为他们颜色的分布大致相同，或者是背景类型大致相同，而不是图片中的对象相同。比如，一只狗可以被看做很接近一只狐狸因为两张图片的背景都是白色。理想情况下，我们希望所有10个类的图像都能形成自己的簇，以便相同类的图像彼此靠近，而不管无关的特征和变化（如背景）。 但是，要获得此属性，我们必须跨越原始像素。

总结

• 我们引入了图像分类的问题，我们给定一组图片，这些图片都标注一个类别。然后我们想预测这些类别的一组新的测试图片，并且测量预测的准确性。
• 我们引入了一个简单的分类器。称为最近邻分类器。我们看到有多个超参数（比如k的值，或者用于比较图片差异的距离类型）与此分类器有关，并且没有直接明显的选择方式。
• 我们看到设置超参数的正确方法收益将训练集数据分为两部分：训练集和验证集。我们尝试不同的超参数值，并且保留能让验证集效果最好的超参数值。
• 如果缺乏训练集数据，我们引入交叉验证的方法，它可以帮助减少估计哪些超参数效果最好的噪声。
• 一旦找到好的超参数，我们就用实际的测试集去执行单一评估。
• 我们看到，最近邻在CIFAR-10上可以取得接近40%的准确率。实施起来很简单，但是需要存储整个训练集，并且测试时的计算成本非常高。
• 最后，我们看到在原始像素上使用L1或者L2距离是不够的，因为距离与图像的背景和颜色分布相比与其语义内容相关性更强。