kNN 与距离函数

图像分类问题的输入是一组带标签图片，输出是从固定类别集合中选出的一个标签。它几乎不需要训练：训练阶段只是记住所有样本，预测阶段再拿测试图片和训练集逐一比较。这个方法不适合实际大规模视觉任务，但它能把“数据驱动分类”“距离度量”“验证集选超参”这几件事讲得非常清楚。

k 最近邻分类器

kNN（k-Nearest Neighbor）分类器，就是对于每一张测试集中的图片，找到与它最接近的 k 张图片，从这 k 张图片中选出最多的一个种类作为它的种类。

当 k=1k=1 时，分类边界会非常依赖单个训练样本，容易被噪声点带偏；当 kk 较大时，预测会变得更平滑，但也可能把局部细节抹掉。这里的“最近”并不是一个固定概念，而是由距离函数决定的，因此 kNN 的效果同时取决于 kk 的大小、距离度量以及数据预处理方式。

放到这张图上来说就是将训练集抽象成不同颜色（代表不同种类）的数据点，整个空间就是可能出现的数据点的集合，kNN 分类器使用训练集中的数据点来划分这个空间，测试集中的点落在哪一个区域内就归为哪一类。图中的灰色区域则是出现“平票”的区域。

距离函数

对比两张图片之间的距离时，将 W*H 的图片（每个像素为一个 3 维向量）拉伸成 W*H*3 的向量，然后计算这两个向量之间的距离。有以下两种计算距离的函数：

L1 距离：向量各个维度上差的绝对值之和，对单个大差异的惩罚是线性的，因此更不容易被单个异常值主导。

L2 距离：向量各个维度上差的平方和开根号，平方项会放大大差异的影响。当把图像看作像素向量时，若两张图像在少数像素上有巨大差异（例如一个噪点或遮挡），L2 会把这类差异放大，导致距离很大；而 L1 会把这些差异按绝对值线性累加，对整体相似性影响较小。

直接在像素空间里比较距离有明显局限：两张语义上相同的图片，只要发生平移、光照变化或背景变化，像素向量距离就可能很大；反过来，两张语义不同但颜色分布相似的图片也可能距离很近。因此 kNN 更像一个基线方法，它说明了“用数据定义分类规则”的思想，但也暴露了原始像素距离不够表达视觉语义的问题。

交叉验证

将模型用于测试集之前需要选取一些参数（如 k 值，距离函数等），这些参数不能直接从训练数据中得到，称为超参数（Hyperparameters）。可以将训练数据分为训练集和验证集（Validation sets），针对不同的超参数进行训练与评估，作为超参数选择的依据。这个过程可以避免将测试集直接当作调参的对象，减少过拟合测试集的风险。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np

# 假设已经有 Xtr_rows, Ytr, Xte_rows, Yte。
# CIFAR-10 中，Xtr_rows 形状通常是 (50000, 3072)，每一行是一张被拉平的图片。
Xval_rows = Xtr_rows[:1000, :]  # 前1000张作为验证集
Yval = Ytr[:1000]               # 验证集标签
Xtr_rows = Xtr_rows[1000:, :]   # 剩余49000张作为训练集
Ytr = Ytr[1000:]                # 训练集标签

# 在验证集上搜索表现最好的超参数k。
validation_accuracies = []
for k in [1, 3, 5, 10, 20, 50, 100]:

  # 对每一个候选k值，重新训练/记录训练集，并在验证集上预测。
  nn = NearestNeighbor()
  nn.train(Xtr_rows, Ytr)
  # 这里假设 predict 支持传入 k；若使用原始版本，需要把 k 写进 predict 的参数。
  Yval_predict = nn.predict(Xval_rows, k = k)
  acc = np.mean(Yval_predict == Yval)  # 验证集准确率
  print("k = %d, accuracy: %f" % (k, acc))

  # 保存每个k的验证集表现，后面选准确率最高的k。
  validation_accuracies.append((k, acc))

在 CIFAR-10 这个例子中，在不同的 k 值下，将前 1000 个数据作为验证集，后 49000 个作为训练集进行训练和验证，得到最终的准确度。这段代码可以给出用于测试集最合适的超参数 k。

为了减小训练和验证过程中的噪声,可以使用不同的训练集和验证集划分来得到更加稳定的性能估计，即交叉验证。比较常用的方法是 k 折交叉验证：将训练集分成 k 份，每次选取 1 份作为验证集，其余 k-1 份作为训练集，最后计算 k 次准确值的平均值用于评估准确性。

线性分类器

线性分类器开始从“记住训练集”转向“学习参数”。训练结束后，模型只保留权重矩阵 WW 和偏置 bb，不再需要把每一张训练图片都拿来和测试图片比较。因此预测一张新图片时只需一次矩阵乘法，速度远快于 kNN。这是从 kNN 过渡到线性分类器的核心动机。

将每一张图片当作一个向量 xix_i，其维度 D=3WHD = 3WH。再给定 KK 个分类，我们的问题就变成了将一个 DD 维的向量映射到 KK 维的分类向量上。使用一个矩阵运算就可以达到这种效果：

f(xi,W,b)=Wxi+bf(x_i,W,b)=Wx_i+b

其中 WW 为 K×DK\times D 矩阵，xix_i 为 D×1D\times 1 向量，bb 为 K×1K\times 1 向量。计算出来的向量代表一张图片在各个分类上的评分，如下图所示：

可以把 WW 的每一行理解为某一类的“模板”。输入图片 xix_i 与第 jj 行权重做点积，得到它和第 jj 类模板的匹配分数；偏置 bjb_j 则表示该类别的整体倾向。线性分类器的限制也在这里：每一类只能用一个线性模板描述，所以它很难处理同一类别内部姿态、背景、视角差异很大的情况。

WW 的每一个行向量将 xix_i 的每一个维度线性组合得到一个分数，用这个分数来衡量图片更接近哪一个类别。对 xix_i 各个维度的线性组合，在二维空间中是一条线，在三维空间中则是一个平面，将这个线性变换放到一个二维空间上可以更加直观地理解线性分类器的工作方式：

在二维空间中每一个 w1x+w2y=0w_1x+w_2y=0 都是一条直线，K 个这样的直线将空间分割成若干区域，可以根据图像（在这里是数据点）相对于每条直线的位置判断其种类。

还有一个把 ff 变成一次矩阵乘的 Trick：

f(xi,W,b)=Wxi+b=[Wb][xi1]f(x_i,W,b)=Wx_i+b= \begin{bmatrix} W & b \end{bmatrix} \begin{bmatrix} x_i \\ 1 \end{bmatrix}

前面的示例中都使用原始像素值，实际操作中还需要进行数据的预处理：将每个特征减去平均值来做归一化处理，放在图像中就是将数据从 [0,255] 平移到 [-127,127]，然后再缩放到 [-1,1] 范围内。