CS231n（2）：图像分类流程

| 研究学术  | CNN  计算机视觉  机器学习应用  最近邻算法  Python 

课程作业除了在自己电脑上，也可在 terminal.com 网站上完成。Python 入门可参考 Justin Johnson 的 Python Numpy Tutorial。

简介

图像分类是计算机视觉的核心任务，它根据已知的确定标签集，为输入图像分配一个标签（标签就是所谓的类别）。其它一些计算机视觉问题，比如目标提取、分割等，都可以被归结到图像分类。

RGB 图像通常用$[0,255]$之间的整数表示为三维数组。上图展示一个图像分类模型，其难点在于要从这堆数据中识别出猫。通过计算属于4个标签｛🐱，🐶，🎩，🍵｝的概率，为图像分配最大概率对应的标签。本例中宽248像素，高400像素的图像，用248×400×3的矩阵表示。矩阵的每个元素对应一个像素值，取值是0到255的整数。具体来说，图像分类的任务是通过这些像素值，利用计算机视觉算法，得到类别标签（本例输入图片的类别标签是🐱）。

形变与类内差异

图像分类面临的主要挑战

如上图所示，图像分类的挑战性在于：

  • 视角变化（Viewpoint Variation）；
  • 尺度变化（Scale Variation）；
  • 光照（Illumination）；
  • 形变（Deformation）；
  • 遮挡（Occlusion）；
  • 背景混杂（Background Clutter）；
  • 类内差异（Intraclass Variation）；
  • ……

同一图像分类问题还可能面临多重挑战，好的图像分类模型应当能应对这些挑战。图像分类器形如：

def predict(image):
    # ???
    return class_label

图像分类算法与传统的计算机算法（比如排序）开发不同。首先需要搜集图像训练集；然后开发学习算法从样本集中学习；最后通过预测结果评估算法性能。这种依赖已标注样本集的方法称为数据驱动的方法（data-driven approach）：

  1. 输入：输入包含$N$张图像，已经用K个标签之一标注了每张图像，这称为训练集（training set）。
  2. 学习（训练）：开发学习算法，通过训练集学习每类的样子，这称为训练分类器（training classifier）或学习模型（learning a model）。
  3. 评估（预测）：输入分类算法没有学习过的图片，通过算法预测标签，根据预测和真实结果的对比评估算法的效果。
def train(train_image, train_labels):
    # build a model for images -> labels ...
    return model

def predict(model, test_images):
    # predict test_labels using the model ...
    return test_labels

最近邻分类器

最近邻分类器（NNC，Nearest Neighbor Classifier）容易实现，本文通过它介绍图像分类的基本方法流程，但是在实际应用中很少使用该方法。对NNC，train训练阶段就是记住所有的图像及其标签，predict预测阶段就是输出最相似图像的标签。

［左］：CIFAR-10示例图像；［右］：与第1列最相邻的10张图片

图像数据集采用CIFAR-10，它包含尺寸32×32的60000张小图，每张图片已经被｛✈️，🚗，🐦，🐱，……｝等10个标签之一标注，如上图左所示。60000张图片被分割成50000张图片（每类5000张）的训练集和10000张图片（每类1000张）的测试集。

最近邻分类器训练分类器的方法，就是记住训练集即可。在预测的时候直接和训练集中的每张图片比较，得到输入图像与训练集中最相邻那张图片的标签，将该标签作为预测结果。上图右是最近邻分类器的结果，其中第8行，与第1列🐎最相邻的是🚗，🐎就会被误标记为🚗。

最近邻算法度量两张图片的相邻程度，通常采用像素值之间的$L_1$距离（Manhattan Distance）或$L_2$距离（Euclidean Distance）：

\[ d_1(\mathbf I_1,\mathbf I_2)=\sum_p\left\lvert\mathbf I_1^p-\mathbf I_2^p\right\rvert；\qquad d_2(\mathbf I_1,\mathbf I_2)=\sqrt{\sum_p\left(\mathbf I_1^p-\mathbf I_2^p\right)^2}。 \]

在 CIFAR-10 数据集上，用$L_1$距离得到的分类正确率大约是38.6%，$L_2$距离得到的分类正确率大约是35.4%，高于随机猜想10%的精度，目前最先进的卷积神经网络（CNN，convolutional neural networks）正确率在95%以上1。NNC 的训练时间短，但是测试时耗很长。通常实际应用中，测试时耗更重要，CNN 就是训练耗时但测试高效。

在度量两个向量差异时，$L_2$的效果比$L_1$糟糕（That is, the $L_2$ distance prefers many medium disagreements to one big one. ）。$L_1$和$L_2$是常用的两个p范数特例。

k最近邻分类器

k最近邻分类器（k-NN，k-nearest neighbor classifier）是对最近邻分类器的简单扩展：从训练集中选出与输入图像最相邻的k张图像的类别标签，通过这k个标签对输入图像的类别标签进行投票。k=1时，k最近邻分类器和最近邻分类器等价。直观上理解，k最近邻分类器取大的k值，对判别边界有平滑作用，能更好的抗击噪声干扰。

k最近邻分类器的分类效果2

上图的k最近邻分类器采用的是$L_2$距离。上图中可以看到，蓝色区域中的小块绿色孤岛是由于噪声点干扰导致的，这将导致预测错误；上图右的5-NN不受这些异常值的干扰，能在测试集上取得跟好的泛化（generalization）效果。上图右的灰色表示有争议的区域，在这些区域至少2个类别标签都得到了最高票。

交叉验证

在实际应用中，如何选择kNN的参数k呢？除k之外，还有度量距离的$L_1$和$L_2$等其它参数需要调节。这些候选参数称为超参数（hyperparameters）。在基于数据驱动的机器学习算法中，参数选择非常普遍。

在实际应用中，不能采用测试集选择参数。如果采用测试集调整参数，分类器就可能对测试集过拟合（overfit），当最终发布到应用环境，分类器的性能可能大打折扣。用测试集调整参数，相当于把测试集当训练集使用。测试集只应该在最终测试分类器泛化性能时，被使用1次。

合适的做法是从训练集分割出一个较小的子集，作为验证集（validation set）。对CIFAR-10数据，可以用49,000个图像作为训练集，利用剩下了1,000个图像作为验证集进行参数调节。在选择参数k的时候，在验证集上测试每个k模型的性能，从中选择使性能达到最好的k。选定k之后，在测试集上仅进行一次性能评估。

当训练集合测试集较小的时候，可以采用更聪明的交叉验证（cross-validation）进行参数选择。通过评估不同验证集上的平均性能，选择合适的参数。以5-fold的交叉验证为例：

  1. 将训练集分割为5等份；
  2. 选择1份作为验证集，剩余的4份组成训练集，在验证集上评估参数的性能；
  3. 轮流将5份作为训练集，将5次性能的平均作为最终评估结果。

5-fold交叉验证选择参数k的正确率曲线

上图展示了5-fold交叉验证的效果，k=7是个不错的参数。若分割的等份大于5，上图的曲线将变得更加光滑。

在实际应用中，由于交叉验证计算量很大，因而会选择采用单一验证集而避免采用交叉验证。通常用50%到90%的数据作为训练集，剩下的作为验证集，候选超参数集越大，验证集越大。当验证集很小时（比如仅仅几百个数据），采用交叉验证是比较保险的方法，它能减少参数选择时的噪声干扰，常用的有3-fole、5-fold、10-fold交叉验证。

另一个需要考虑的问题是，在通过验证集确定了最佳参数后，是否需要利用整个训练集和最佳参数重新学习。由于放回了验证集，整个训练集上的表现必然有所不同。实际上，最终发布的分类器不需要验证集的参与。

最近邻算法探讨

k最近邻算法的主要优点是容易理解和实现，并且训练不时耗；主要缺点是测试（预测）时耗高。在实际应用中，主要关注的是测试（预测）时耗。深度神经网络（DNN，Deep Neural Networks）相反，训练耗时但预测高效，在实际中更适用。

最近邻算法也是一个活跃的研究领域。近似最近邻算法（ANN，approximate nearest neighbor）通过对精度和速度（空间）耗费的折中提高效率，比如FLANN。这些算法通常需要通过kd树或k均值算法预处理或建立索引。

k最近邻算法有时是不错的选择，尤其是数据维数较低的时候，但在图像分类中几乎很少使用：

  • 图像是高维数据，高维空间的距离度量有些反直觉（counter-intuitive）;
  • 测试时耗太高。

右边的三张图片和最左的一张的$L_2$距离均相同

利用$L_2$距离度量上图中小图的相似性，结果违反直觉。其它图都是最左图变换得到的，人眼观察这些图比较相似，但是基于$L_2$的度量表明其它图和原图差异很大。实际山，像素级别的距离度量无法判断基于直觉和语义的相似性。

利用t-SNE展示CIFAR-10图像

上图用t-SNE展示CIFAR-10的图像，在像素级的$L_2$距离度量下，相似的图像相邻排列。结果表明并所非所期望的那样，同类别的相邻排列。实际上，这种度量严重受背景和颜色分布的影响，并非真正度量图像内容的相似性。

k最近邻算法在实际使用中的建议：

  1. 数据预处理：特征向量均值归0化、方差单位化3；
  2. 对高维数据用PCA或随机投影（random projections）等算法降维处理；
  3. 根据前文建议采用验证（50%到90%数据作为训练集）或交叉验证，通常fold数越多，效果越好，但也越耗时；
  4. 通过验证集选择k（候选k越多越好）和距离度量方式；
  5. 如果算法太耗时，尝试采用ANN加速。

示例代码

下文中代码所需要的函数和数据在这里获取。

__author__ = 'jiyeqian'

import numpy as np
from cs231n.data_utils import load_CIFAR10

# a magic function we provide
Xtr, Ytr, Xte, Yte = load_CIFAR10('cs231n/datasets/cifar-10-batches-py')
# Subsample the data for more efficient code execution
num_training = 5000
mask = range(num_training)
Xtr, Ytr = Xtr[mask], Ytr[mask]
num_test = 500
mask = range(num_test)
Xte, Yte = Xte[mask], Yte[mask]

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

class NearestNeighbor:
    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, self.ytr = X, y

    def predict(self, X, k):
        """ 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)
            # L2 distance
            # distances = np.linalg.norm(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
            fre_idx, fre_num = np.unique(self.ytr[distances.argsort()[0:k]], \
                                         return_counts=True)
            Ypred[i] = fre_idx[fre_num == fre_num.max()].min()

        return Ypred


# Part 1: kNN prediction

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


# Part 2: validation for choosing k

# assume we have Xtr_rows, Ytr, Xte_rows, Yte as before
# recall Xtr_rows is 5,000 x 3072 matrix
Xval_rows, Yval = Xtr_rows[:1000, :], Ytr[:1000]# take first 1000 for validation
Xtr_rows, Ytr = Xtr_rows[1000:, :], Ytr[1000:] # keep last 4,000 for train

# 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最近邻算法预测阶段计算复杂度非常高，为了加快计算速度，上述代码只抽取了10%的数据，得到的结果如下：

# Part 1:
accuracy: 0.290000
# Part 2:
accuracy: 0.291000
accuracy: 0.269000
accuracy: 0.275000
accuracy: 0.289000
accuracy: 0.287000
accuracy: 0.285000
accuracy: 0.283000

线性分类器

图像标注系统（CNN 与 RNN 的结合）

与最近邻方法不同，线性分类器是一种参数化方法（Parametric Approach）。

线性分类器计算过程

输入图像属于得分最高的类别，从上图可以看出，🐱的得分为负，显然会被错分类，分类器的参数并不合适4。

参考文献

    1. kaggle排名的得分（score）是如何计算的？ ↩

    2. NN 和 kNN （采用$L_1$或$L_2$距离）在训练集上测试的精度是多少呢？ ↩

    3. We will cover this in more detail in later sections, and chose not to cover data normalization in this section because pixels in images are usually homogeneous and do not exhibit widely different distributions, alleviating the need for data normalization. ↩

    4. 不平衡数据集对线性分类器的性能有何影响？ ↩

    打赏作者

    上一篇：CS231n（1）：计算机视觉简介     下一篇：CS231n（3）：损失函数与最优化