Image Classification Pipeline

Data-Driven Approach

Collect a dataset of images and labels
Use Machine Learning to train a classifier
Evaluate the classifier on new images

数据驱动方法：分为train和predict两个步骤，前者输入images和labels输出一个模型，后者输入模型和测试数据预测标签。

Example Dataset

CIFAR10可以为深度学习提供数据集。

CIFAR-10 and CIFAR-100 datasets

Measure Distance

如何衡量两张图片的差异度？

图片一般储存为数字矩阵（RGB三通道），可以尝试使用L1 distance或L2 distance。

L1 distance(Manhattan distance)即

$d_1(I_1, I_2) = \sum_{p}|I^p_1 - I^p_2|$

L2 distance(Euclidean distance)即

$d_2(I_1, I_2) = \sqrt{\sum_{p}(I^p_1 - I^p_2)^2}$

KNN

K-Nearest Neighbors Classifier（KNN，K近邻分类器）根据最近的K个数据点决定测试数据的分类。

对于一个输入数据，在训练数据中寻找出与之距离最近的$k$个数据点，由这$k$个数据点所属的标签进行投票，$k$个中出现次数最多的标签就认为是输入数据的分类结果。

KNN的train函数只是将训练数据储存下来，predict函数对测试数据进行归类。

当$k=1$时，KNN变为Nearest Neighbor Classifier，最近邻分类器。不难发现最近邻分类器极容易受到噪声的干扰，这也是KNN更优的一个理由。

当然，KNN在实际中绝不会用于图像识别，首先测试的巨大时间开销显然不合理，其次这一种图片的距离衡量方式并不能很好地体现图片所包含的信息。

另一个重要的问题就是维度灾难（Curse of Dimensionality），当维数越来越高时，为了使样本空间能够保持稠密性，需要的数据量呈指数增长。

Hyperparameters

类似KNN中的$k$值和distance计算方式（L1 / L2 / ……）的一类参数被称为hyperparameters（超参数），它们是不能从机器学习中所习得的内容，与问题的实际情况高度相关，需要手动指定。

因此我们需要通过数据测试来确定最佳的超参数。

一般的做法是将所有数据分为三组：train、validation和test。

train部分数据用于训练模型，validation部分数据用于测试模型的正确率。我们通过调整超参数，使得训练出的模型在validation数据中能够获得最好的准确率。最后用test数据检测这个算法的真正准确率（写到paper上的准确率）。

另一种做法是Cross-Validation，交叉验证。

将数据分为若干folds，第一次以fold 1、fold 2、……、fold 4作为train，fold 5作为validation；第二次以fold 1、fold 2、……、fold 3、fold 5作为train，fold 4作为validation；……

最后取五次的平均值作为此次训练的准确率。

这种方法一般只会在小数据集中使用，并不会经常在机器学习中使用。

Linear Classification

$\text{Image x} \longrightarrow f(x, W) \longrightarrow \text{10 numbers giving class score} \\ W:\text{parameters or weights}$

Loss Function

损失函数用于定量地判断参数矩阵$W$的优劣。

$L = \frac{1}{N} \sum_{i}L_i(f(x_i, W), y_i)$

整个数据集的Loss定义为每个数据Loss的均值。

Multiclass SVM Loss

对于数据$(x_i, y_i)$，$s = f(x_i, W)$，

$L_i = \sum_{j \neq y_i} max(0, (s_j + 1) - s_{y_i})$

$1$为Safety margin，即要求正确项的得分应比错误项的得分高出一个安全边距。

这种函数的图像像一个合页，因此也被称为hinge loss（合页损失函数）。

Regularization

仅对训练数据拟合容易出现过拟合的情况，典型例子就是将直线上的散点完美拟合到高次曲线上。

因此一般会对Loss function添加Regularization正则化，选出“最简单”的模型。

$L(W) = \underbrace{\frac{1}{N} \sum_{i=1}^{N}L_i(f(x_i, W), y_i)}_{\textbf{Data loss}\text{: Model predictions} \\ \text{should match training data}} + \underbrace{\lambda R(W)}_{\textbf{Regularization}\text{: Model} \\ \text{should be “simple”, so it} \\ \text{works on test data}}$

超参数regularization strength$\lambda$用于权衡公式中两者的占比。

常见的正则化：

L2 Regularization $R(W) = \sum{k}\sum{l}W^2_{k, l}$，即L2范数
L1 Regularization $R(W) = \sum{k}\sum{l}|W_{k, l}|$，即L1范数
Elastic net Regularization 弹性网络正则化 $R(W) = \sum{k}\sum{l}\beta W{k, l}^2 + |W{k, l}|$，即L1与L2的结合
Max norm regularization
Dropout
……

Softmax Classifier (Multinomial Logistic Regression)

对scores做归一化指数处理，得到概率形式的结果（使用$e$指数的目的是得到正值）：

$P(Y=k|X=x_i) = \frac{e^{s_k}}{\sum_{j}e^{s_j}} \\ L_i = -\lg {P(Y=y_i|X=x_i)}$

即：

$L_i = -\lg({\frac{e^{s_{y_i}}}{\sum_{j}e^{s_j}}})$

在正确分类项的得分超过一个阈值时，SVM倾向于不再管它。

但Softmax倾向于不断地增大正确分类项的对应分值，并不断减小错误分类项的对应分值。

Optimization

梯度下降法（Gradient Descent）是常用的最优化方法。

我们可以通过计算有限差分来获得数值梯度，但这种方法非常慢，且结果并不尽如人意。

更合理的方式是使用分析性质计算解析梯度。

# Vanilla Gradient Descent

while True:
    weights_grad = evaluate_gradient(loss_fun, data, weights)
    weights += -step_size * weight_grad # perform parameter update

Stochastic Gradient Descent

数据量较大时，每次都对所有数据计算Loss function并求平均值会是一笔很大的开销。使用Stochastic Gradient Descent（随机梯度下降），每次从数据集中随机抽取一部分数据（称为minibatch）用于计算梯度，可以加快速度。

Image Feature

直接将图像的原始数据作为分类器的输入数据可能并不是一个很好的选择，以图像的某些特征作为数据参数可能使数据更线性可分。

一些想法是使用颜色直方图Color Histogram、有向梯度直方图Histogram of Oriented Gradients或Bag of Words等方式提取图像特征。

然而，卷积神经网络等神经网络能够直接从数据中提取并学习特征。