深度学习从入门到放弃:cs231n(1)-K-NN分类器

图像分类

所谓图像分类问题，就是已有固定的分类标签集合，然后对于输入的图像，从分类标签集合中找出一个分类标签，最后把分类标签分配给该输入图像。这是计算机视觉的核心问题之一。

在基于内容的图像查询中, 存在一个底层特征和上层理解之间的差异.人是通过对语义的理解, 提取图片的信息, 判断两张图片的相似性, 而计算机”看”到却是由像素组成的巨大的数字阵列, 不能从中直接提取出语义信息.我们人对语义标签的理解和计算机存在差异, 这个问题叫语义鸿沟.

由于上面所说的语义鸿沟, 计算机在识别图像的时候就会存在以下困难.

可能图片表示的还是同一个物体, 但是由于各种条件发生变化, 将导致整个像素矩阵发生变化, 使得图片在计算机中的数据完全不同.

考虑到上面的问题, 人们想通过写一个规则来识别某一个物体就变得十分困难.基于此, 人们想出了数据驱动的方法, 不通过写一个确定的规则来分类图片, 而是通过几个步骤让计算机自己总结图片的核心要素.

KNN分类器存储大量的图片, 当你需要对一张新的图片分类时, 分类器将待测图片与所有图片比较,从数据集中选出1张或K张差异最小的图片, 在这些图片的标签中选择一个, 作为新图片的标签.

KNN分类器要选择差异最小的图片, 那么怎么计算图片之间的差异呢?
通过图片之间的距离运算.
首先将图片转化为两个向量, 选择一个适当的距离算法算出距离.

想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(City Block distance)。

$$
d_1(I_1, I_2)={\sum_{P} }|I^P_1-I^P_2|
$$

L1距离就是将每个像素比较, 求差值, 最后将差值的绝对值累加起来.

欧式距离是最易于理解的一种距离计算方法，也称欧几里得距离，源自欧式空间中两点的距离公式，是指在m维空间两点之间的真实距离，

$$
d_2(I_1, I_2)=\sqrt{ {\sum_{P} }(I^P_1-I^P_2)^2}
$$

L2距离也还是将每个像素比较, 求差值, 但是将差值平方后累加, 再开方.

L1距离更适用于特征向量, 向量的每个元素具有固定含义.
L2距离适用于空间中的通用向量, 每个元素没有或暂时不知道实际的含义.
而在面对差异时, L2比L1更不能接受差异, 所以L2的决策图像更为平滑.

每次都需要比对数据集中的所有图片, 速度慢.
分类器需要将所有的训练数据存储起来, 需要巨大的存储空间.
距离算法的缺点:
1. 将各个维度的单位当作相同的看待, 如(10,0),(0,10)到原点有相同的距离.
2. 没有考虑向量各个分量的分布是不同的.
维度灾难

在机器学习问题中，需要在高维特征空间（每个特征都能够取一系列可能值）的有限数据样本中学习一种“自然状态”（可能是无穷分布），要求有相当数量的训练数据含有一些样本组合。给定固定数量的训练样本，其预测能力随着维度的增加而减小。

也就是说, 数据集的必须密集地分布与空间中, 否则在测试时, 就会选择到相似度不那么高的数据, 降低预测的准确度. 但是在维度增加时, 要保证在空间的密集, 数据集规模的增加必须是指数倍的.

这些不能从训练中学到, 需要我们提前为算法做出选择的参数, 称为超参数.
例如, KNN可以设定K值, 选择最接近的K张图片, 也可以选择不同的距离函数, 这些都是之前设定好的超参数.

超参数的设置不是显而易见的, 我们使用训练集来训练算法, 使用测试集来评价准确率. 但要注意一点, 不能通过测试集的准确率反过来进行超参数的设置, 否则就会发生过拟合的现象.

过拟合
如果你使用测试集来调优，而且算法看起来效果不错，那么真正的危险在于：算法实际部署后，性能可能会远低于预期。这种情况，称之为算法对测试集过拟合。

但是超参数还是要调试的, 于是有了以下的步骤

在数据量较小时, 可以使用交叉验证.
和上面步骤不同的是, 交叉验证又将训练集分为n个部分, 每次使用1个部分作为验证集, 剩下的部分为训练集, 从n份验证的结果取平均值作为验证结果.