图像分类
图像分类问题，就是对已有的固定的分类标签集合，对于输入的图像，从分类标签集合中找到一个分类标签，最后把分类标签分配给该输入图像。虽然看起来很简单，但是是计算机视觉领域的核心问题之一，并且有着广泛的应用。
例如，以下图为例，图像分类模型读取该多，并生成该图片属于{cat,dog,hat,mug}中各个标签的概率。人类可以直接看到这个图像，但对于计算机来说，看到的确是由数字组成的巨大的3维数组。在此例中，图片的大小为248*400，有3个颜色通道，分别是红、绿和蓝。如此，图像就包含了248*400*3=297600个数字，每个数字都在0-255之间，图像分类的任务就是从这些数字中学习到知识，把该图像分类到“猫”。
困难和挑战：对于人类来说，从图片中识别“猫”非常简单，但是对于计算机而言却不是这么简单了。计算机视觉算法在图像识别方面遇到的一些困难：
- 视角变化（Viewpoint variation）
- 大小变化（Scale variation）
- 形变（Deformation)
- 遮挡（Occlusion)
- 光照条件（Illumination conditions)
- 背景干扰（Background clutter）
- 类内差异（Intra-class variation）
数据驱动方法（Data-driven approach）
数据驱动方法类似和教小孩看图识物类似：给计算机很多数据，让计算机进行学习，从而进行分类。该方法的流程如下：
- 输入：输入包含N个图像的集合，每个图像的标签是k种分类标签中的一种。这个集合称为训练集。
- 学习：使用训练集来学习每个类到底长什么样。一般称为训练分类器或学习一个模型。
- 评价：让分类器来预测它未见过的图像的分类标签，以此评价分类器的好坏。分类正确的图像数量越多，则分类器的性能越好。
Nearest Neighbor分类器
图像分类数据集：CIFAR-10，包含60000张32*32的小图像，数据集包含10中类别，60000张图片被分为包含50000张图片的训练集和包含10000张图片的测试集。下图就是10类的10张随机图片。
上图的左边是训练样本集，右边：第一列是测试图像，然后第一列的每个图像的右边是使用Nearest Neighbor算法，根据像素的差异，从训练样本集中选出的10张最类似的图片。
Nearest Neighbor算法，假设我们拿到包含50000张图片的训练集，对于一个要预测的图片，Nearest Neighbor算法会拿这张测试的图片和训练集中的每个图片去比较，然后将它认为最相似的那个训练集图片的标签赋给这张测试图片。至于判断两张图片是否相似，以及最相似，在本例中，就是比较32*32*3的像素块。最简单的方法就是逐个像素比较，最后将差异值全部加起来。也就是说，将两张图片先转化为向量$I_1$和$I_2$，然后计算$L_1$距离：$$
d_1(I_1,I_2)=\sum_p |I_1^p-I_2^p|
$$
以图片中的一个颜色通道为例来进行说明，两张图片使用$L_1$距离来进行比较。逐个像素求差值，然后将所有差值加起来得到一个数值。如果两张图片一模一样，那么$L_1$距离为0，但是如何两张图片很是不同，那么$L_1$值将会非常大。
距离选择：计算向量间的距离方法有很多种，另一个常用的方法为$L_2$距离，从几何的角度看，可以理解为计算两个向量间的欧式距离。
$L_1$和$L_2$比$L_2$的比较：在面对两个向量之间的差异时，$L_2$比$L_1$更不能容忍差异。也就是说，相对于一个巨大的差异，$L_2$距离更倾向于接受多个中等程度的差异。$L_1$和$L_2$都是在p-norm常用的特殊形式。
k-Nearest Neighbor分类器
Nearest Neighbor算法使用最相似的1张图片作为最终的预测结果。k-Nearest Neighbor算法则是找到最相似的k张图片，然后让它们针对测试图片进行投票，最后把票数最高的标签作为对测试图片的标签。当k=1时，K-Nearest Neighbor就变为Nearest Neighbor。从直观上可以看到，更高的k值可以让效果更平滑，使得分类器对于异常值更有抵抗力。
上图显示了Nearest Neighbor分类器和5-Nearest Neighbor分类器的区别。图中使用了2维的点来表示，分成3类。不同的颜色区域代表使用$L_2$距离的分类器的决策边界。白色的区域是分类模糊的例子（即图像与两个以上的分类标签绑定）。需要注意的是，在NN分类器中，异常的数据制造出一个不正确预测的孤岛。5—NN分类器将这些不规则都平滑了，使得针对测试数据的泛化能力更好。
用于超参数调优的验证集
k-NN分类器需要设定k值，选择哪个k值最合适呢?同样也距离函数也是可选择的，那么选哪个好？这些选择，被称为超参数（hyperparameter)。在基于数据进行学习的机器学习算法设计中，朝参数时非常常见的，但是如何选择这些超参数？
我们可能会尝试不同的值，看哪个值表现最好就选哪个。但这样做的时候要非常小心，特别注意：决不能使用测试集来进行调优。在训练机器学习模型时，应该把测试集看做非常宝贵的资源，不到最后一步，绝不使用它。如果使用测试集进行调优，而且算法看起来效果不错，但算法实际部署后，性能可能会远低于预期。这种情况，称之为过拟合。从另一个角度来说，如果使用测试集来调优，实际上就是把测试集当做训练集，由测试集训练出来的算法再跑测试集，自然性能看起来会很好。这其实是过于乐观了，实际部署起来效果就会差很多。所以，最终测试的时候再使用测试集，可以很好地近似度量你所设计的分类器的泛化性能。
测试集只能使用一次，即在训练完成后评价最终的模型时使用。
实际在进行参数调优的过程中，是从训练集中抽取一部分数据用来调优，称之为验证集（validation set）。以CIFAP-10数据集为例，我们可以用49000个图像作为训练集，用1000个图像作为验证集。验证集其实就是作为假的测试集来调优。
把训练集分为训练集和验证集，使用验证集来对超参数进行调优，最后只在测试集上对模型进行评价。
交叉验证，有时候训练集较小，就会导致验证集的数量更小，人们会使用一种称为交叉验证的方法。这种方法把训练集评价分为K份，用其中的k-1份来训练，另1份来验证。然后循环着取其中的k-1份来训练，其中1份来验证。最后取所有k次验证的结果的平均值作为算法验证结果。在实际的应用中，一般会直接把训练集按照50%-90%的比例分为训练集和验证集。但这也是根据具体情况来定的：如果超参数数量较多，可能就想用更大的验证集，而验证集的数量不够，最好还是使用交叉验证。
Nearest Neighbor分类器的优劣
- 易于理解，实现简单；
- 算法的训练不需要花时间，其训练只需要和所有存储的训练图像进行比较（缺点）；
- 虽然训练花费很多时间，但是一旦训练完成，对新的测试数据进行分类非常快。
Nearset Neighbor分类器在某些特定的情况下，可能是不错的选择。但是在实际的图像分类工作中，很少使用。
实际应用K-NN的流程
- 预处理数据：对数据中的特征进行归一化，让其具有0均值和单位方差（unit variance)。
- 如果数据是高维数据，考虑使用降维方法。
- 将数据随机分为训练集和测试集。
- 在验证机上进行调优，尝试足够多的k值，尝试$L_1$和$L_2$两种距离。
- 如果分类器跑得太慢，尝试使用Approximate Nearest Neighbor库（比如FLANN）来加速这个过程，其代价是降低一些准确率。
- 对最优的超参数做记录。记录最优参数后，是否应该让使用最优参数的算法在完整的训练集上运行并再次训练呢？因为如果把验证集重新放回到训练集中（自然训练集的数据量就又变大了），有可能最优参数又会有所变化。在实践中，不要这样做。千万不要在最终的分类器中使用验证集数据，这样做会破坏对于最优参数的估计。直接使用测试集来测试用最优参数设置好的最优模型，得到测试集数据的分类准确率，并以此作为你的kNN分类器在该数据上的性能表现。
小结
- 介绍了图像分类问题。在该问题中，给出一个由被标注了分类标签的图像组成的集合，要求算法能预测没有标签的图像的分类标签，并根据算法预测准确率进行评价。
- Nearest Neighbor分类器，分类器中存在不同的超参数(比如k值或距离类型的选取)，要想选取好的超参数不是一件轻而易举的事。
- 选取超参数的正确方法是：将原始训练集分为训练集和验证集，我们在验证集上尝试不同的超参数，最后保留表现最好那个。
- 如果训练数据量不够，使用交叉验证方法，它能帮助我们在选取最优超参数的时候减少噪音。
一旦找到最优的超参数，就让算法以该参数在测试集跑且只跑一次，并根据测试结果评价算法。 - 最后，我们知道了仅仅使用L1和L2范数来进行像素比较是不够的，图像更多的是按照背景和颜色被分类，而不是语义主体分身。
—end—
