Image Classification

Motivation

输入一些图片，并且算法实现知道一组预定的类别或标签，算法的任务是区分图片的种类并为它分配这些固定类别的标签之一。

图像分类可以说是计算机视觉中的核心任务之一，物体检测和分割等任务都可以通过在此图像分类的基础上进行细节上的改动来实现，所以学习图像分类可以说是很有用的。

Challenges

对于计算机来说，图片是以3维数组来表示的。例如下面的例子中，图片是由800*600个像素组成，而每个像素由三个数字(RGB)组成。因此对于计算机很难从这些数中为图片分类。这个问题被称为语义鸿沟(Semantic Gap)。

所以存在以下一些问题：

视角变化（Viewpoint variation）：同一个物体，拍摄的角度距离不同，每一个像素都会不同。
光照条件（Illumination conditions）：拍摄时光照条件不同，或者物体本身的深浅，对图片影响非常大。
形变（Deformation）：相同物体的形状并非完全一样，会有不同的形态。
遮挡（Occlusion）：目标物体可能被遮挡，有时候物体只可见一部分。
背景干扰（Background clutter）：检测物体融入背景，难以辨识。
类内差异（Intra-class variation）：同一类物体的个体差异大，比如椅子。这一类物体有许多不同的对象，每个都有自己的外形。

所以对于图像分类来说是没有像排序算法一样的显示算法存在的。但是对于好的分类器来说，需要能够处理以上的变化，正确的识别出物体来。

对于这个问题来说已经有过很多尝试，比如说检测物体的边缘，按照edges形状来进行分类，比如猫耳朵。但是这个方法不容易扩展，对于新的物体需要新的特征。而我们需要更scalable的方法。

Data-driven Approach

收集大量的图片及标记，比如说google图片搜索
用机器学习方法训练一个分类器
应用分类器到新的图片上进行预测

Pipline

Nearnest Neighbor Classifier

训练：只是记住所有的训练数据
预测：输入新的图像，尝试在训练数据中找出最相似的图像，然后根据最相似的图像的标签来预测新图片的标签。

Example

CIFAR-10数据集：训练集为50000张，测试集10000张，10种分类标签，每张图像为32X32的小图像。下图是使用Nearest Neighbor算法，根据像素差异，从训练集中选出的10张最类似的图片，可见其中有不少错误。

Distance Metric

因为需要找出最相似的图像，我们就需要对图片的距离进行计算。所谓距离就是图片的每一个像素之间的差异，相当于将图片的3维数组转化向量计算向量之间的距离。距离的计算有很多方法。

L1距离，也叫曼哈顿距离，计算每个像素的差值并求和，如下图如果旋转了坐标轴，L1距离会变化，但是L2距离不会。

L2距离，也叫欧式距离。

向量有很多距离函数，怎么选择就成了一个问题。

KNN Classifier

找最相似的k个图片的标签，然后让针对测试图片进行投票，最后把票数最高的标签作为对测试图片的预测。当k=1的时候，就是Nearest Neighbor分类器。从下图中我们可以看出，k=3时绿色部分中间的一些零散的黄色就不会被单独区分出来，同时边界也变得很平滑，泛化能力更好。

如何确定最佳k值就是另外一个问题。

Hyperparamenter

由前面所讲，需要选择不同的距离函数以及K的大小，这些被称为超参数。

对于机器学习来说，超参数很常见，具体怎么设置和取值则是根据具体的问题来分析。需要不停的尝试不同的数值并在测试集上进行测试来找出最合适的参数。但这这也不是一个好的方法，因为这个测试集只是算法泛化能力的一个代表，不能确定在其他新数据上的表现。

使用验证集是一种更普遍的方法，我们将数据集分为三份。在训练集上训练算法，用不同的超参数在验证集上验证，再用最优的超参数在测设集上预测。通常测试集将会在最后时刻才会用到。

Cross-validation

交叉验证是另外一种策略，将除了测试集以外的数据分成多个fold，循环选择其中一个作为测试集，另外几个作为训练集来评估性能。但是对于deep learning来说，数据集非常大，计算量很大，比较少采取这个方法。下图是一个5-fold的对于k的交叉验证结果，每一个点是不同的输出，纵坐标是准确率，图中的竖线代表标准差。

Drawbacks

实际上knn方法基本上不会用于图像分类问题

预测效率低：训练步骤过于简单，只是记住所有图片，时间复杂度为O(1)，但是预测时对每一个图片都要遍历所有训练集中的图片并且计算，这个复杂度会根据训练集的大小线性增长。但对于我们来说测试时间应该要更重要，训练的时间可以很长，但测试的时间需要很快，所以这个方法比较backward。
距离函数不太有效：比如下图中右边3个图与第一个图的L2距离是相同的

维数灾难：维数增多主要会带来的高维空间数据稀疏化问题，所以需要数据密度更高，但是这就意味着时间复杂度的指数增长，这是非常糟糕的。这里有一个链接很形象的讲述了这个问题。

Summary

图像分类问题。由被标注了分类标签的图像组成的训练集，训练算法，并在测试集上预测标签，并根据准确率进行评价。
最近邻分类器(K-Nearest Neighbor classifier)通过最相近的训练样本预测标签。
距离类型和K是超参数(Hyperparameters)。
使用交叉验证集(Cross-validation set)来选择超参数，或者只是通过测试集找到最好的参数。

Linear Classification

Motivation

线性分类器是一种很简单的算法，但是它很重要并会帮助我们建立对整个神经网络和CNN的理解。神经网络很像是乐高玩具，有很多不同类型的组件然后把这些组件拼在一起组成一个大的神经网络，而其中一个重要的组件就是线性分类器，它在不同的deep learning应用中都发挥了很大的作用。

instructor的实验室有一个项目，他们要输入一张图片，然后输出一句描述性的语句来描述这幅图像。原理就是有一个更适用于CV的CNN来观察图像，一个更适用于sequences的RNN来生成描述，然后把两块像乐高一样拼在一起来实现的。

Parametric Approach

回到CIRAR-10上，我们的训练集有50000个32 32 3的图像，1000个种类，测试集有10000个图像。线性分类器就是构造一个有W参数函数，输入是一个图像，输出对应每一个种类的数值/分数，正确的种类数值/分数较大。如下图所示（假设有十个分类）：

在这里，我们的函数中有两个组件，我们要做的就是让函数输出对应10个种类的分数。其中x是不可变的输入值（图中所示猫的图片，即为3072个数字），W就是参数或者权重，是可变的，这就是parametric approach。线性分类是最简单的parametric approach，KNN就是non-parametric approach。在这里我们的测试步骤中，与KNN不同的是，我们就不需要记住所有的数据，只需要知道参数W，这样的模型更有效率。

最简单的我们可以让W与x相乘，所以我们要把x展开成一个3072元素的列向量，而W(weights)就是一个10 3072的矩阵，它们相乘输出就是一个10元素向量，向量的每一个数对应一个种类。通常情况下我们还需要有一个10个元素的*偏移向量(bias vector)，来平衡不平衡的数据集的情况。比如数据集中猫的数量比其他的多，则猫的偏移量更大，代表默认情况下分类器会更多的预测出猫。

总结的说，线性分类器是从图片空间映射到标签空间的函数，我们要找的最佳的W和b。

Interpreting

下图是一个简单的计算例子：

从这个图中可以理解线性分类器类似于一种模板匹配的方法，W每一行相当于图像的一些模板，与图片的每一个像素计算内积再加上偏移量得到一个分数。下图是每一类解出来的模板图像：

我们可以看到第一个模板图像是飞机，所以比较偏重于蓝色，因为飞机大部分在天上被蓝色所包围，所以这个模板在蓝色通道上有很多正权重。后面那个马的种类，可以隐约看到马是双头的，因为数据集中的马可能朝不同的方向，所以模板平均了这些变化。这也是线性分类器的一种局限性，因为图片是变化的，但它通过一个单独的模板来识别每个类别。神经网络没有这个问题，因为它不再限制每一个类别只有一个模板。

下图是对线性分类器的另一种理解：

想象每一个图片是3072维空间上的一个点，分类器就是再为这些点画decision boundary，而得到的分数就是取样空间中箭头指向正方向的梯度。训练就是直线（在高维空间里是超平面）的移动，直到把所有的类分开。

Hard cases

但是对于线性分类器来说，有几种情况是难以区分开的，如下图：

线性分类器还有一个问题就是如果数据集中图片尺寸不同就不容易处理。这个是分类器的通病，实际操作中会将不同尺寸的图片进行压缩，压缩成相同形状，目前最前沿的水平图片都是正方形的。所以对于全景图片的分类是很糟糕的。

最后为了能定量的测量每一个W在数据集上的表现并选择更好的W，我们需要引入loss function以及optimizaition，这是下一节的内容。