Stanford CS231n(2017版）-- Lecture 2 笔记

Lecture 2 主要讲的是 image classification 的一些基础知识 (核心概念会用英语原味表达）

从最经典的例子入手：给你一张猫的图片，如何从一堆标签中正确地 pick 猫这个标签呢？

一言以蔽之，需要解决的是： Semantic gap between “cat” and pixels ，也就是从计算机读取的一个个像素里的数字 --> “猫” 这个概念。而且猫的图片变化多样，要考虑以下几个挑战：

illumination (光照）：
deformation (形变）：猫毕竟是一种流体...
occlusion (遮挡）：猫猫藏起来勒
background clutter：和背景融为一体
intraclass variation: 不同的猫外貌不同

用数组排序一样的 hard code (硬编码）方法肯定不行，于是我们考虑用 data-driven approach, 用带标签数据集来训练一个 classifier 选取数据集：CIFAR10， 10 种标签，50000 大小 training set, 10000 大小 testing set

Nearest Neighbor (近邻）#

思路：在 training set 中遍历，寻找和当前测试的图片最 “相似” 的图片 a，用这个图片 a 的标签作为测试图片的标签

那么 “相似” 该如何用数学语言表示？ 我们用 L1 Distance , 即计算 pixel-wise distance 并相加，如下图示例

import numpy as np

class NearestNeighbor:
  def __init__(self):
    pass

  def train(self, X, y):
    self.Xtr = X
    self.ytr = y

  def predict(self, X):
    num_test = X.shape[0]
    Ypred = np.zeros(num_test, dtype = self.ytr.dtype)
  
    for i in xrange(num_test):
    distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
    min_index = np.argmin(distances)
    Ypred[i] = self.ytr[min_index]

  return Ypred

假设 num_test = 10，图片分成 4*4 = 16 个像素块，X 的维度是 [10, 16]，distances 的维度是 [10, 1], ytr 的维度是 [50000, 1](假设我们用的是 CIFAR 整个数据集的 50000 张图训练，每张图对应一个标签）。

这个方法看起来简单又好，为什么不采用呢？接下来要提到 “时间复杂度”，训练的时间复杂度是 O (1), 预测的时间复杂度是 O (N), 因为预测一张图片需要把整个（比如这个例子中的 50000）张都遍历一遍，一个一个做 L1 distance。一旦扩大数据集，预测会非常非常慢。我们可以接受训练慢一些，因为这是幕后工作，但推理很慢是无法接受的。所以这个方法实操起来不可行。

K-Nearest Neighbors#

上一个部分提到的 “Nearest Neighbor” 方法，实质做的是 copy 训练集某张图片的 label。且不说时间复杂度的问题，这个 copy 的策略本身也会导致问题：

受到噪声的干扰，导致划分区域出现了不规则或尖锐的边界
对噪声或异常值无法做到正确的处理（如下图在绿色区域中的那个黄色点）

为了升级 Nearest Neighbor 方法，我们做出了改动:

这句话是什么意思呢？我们首先确定我们使用的 distance function，L1 和 L2 都可以，然后选定一个 K 参数。假设我们选了 L1，并选了 K=5，那么我们就去计算当前测试的这张图片与所有训练集中的图片的 L1 distance（运算 50000 次），然后选择 L1 distance 最小的 5 张训练图。如果这 5 个邻居里，两个邻居的标签是 cat, 一个是 dog，一个是 car, 一个是 shit, 那么很直观的，我们就可以认为测试图的 label 是 cat。除了 majority voting，我还得提一下另一种课程中没提到的 weighted voting 情况:

majority voting (课程中提到的）：从 K 个中寻找标签次数最多的
weighted voting: 假设 K=3，三个邻居的 L1 距离分别为 1、2、3，标签分别为 A、B、A，则权重计算为：标签 A：1/1 + 1/3 ≈ 1.333，标签 B：1/2 = 0.5，因此我们认为测试图片的 label 是 A，因为其权重和更高。
说白了就是对 majority voting 稍微加强了一下，能够处理标签数量相同的情况，这个思路贯穿整个机器学习。

这个 K 值得选取也很有说法，较大的 K 值通过 “多数投票” 或 “加权平均” 综合更多邻居的信息，能够减少模型对训练数据中异常点或噪声的过度拟合，使模型泛化能力更强。具体可见 Stanford 做的交互可视化网页，非常有助于理解。当然，散点的表现形式和我们实际图像之间的像素值作差是不完全一致的，散点之间的 L1 distance 是曼哈顿距离，L2 distance 是点到点线段长度，散点是在抽象整个分类问题，这里需要慢慢琢磨。
http://vision.stanford.edu/teaching/cs231n-demos/knn/
图上的点全都是训练集，一个颜色表示一个 label，假设红色区域表示 cat，那一团红点就对应了我们图像分类任务中一些受 illumination, deformation, occlusion...... 影响的猫图，他们有差异但是有相似的 “模式”，所以不会完全重叠但离彼此不远。
把玩这个交互页面时候，你会发现，K=1 → 3 →5 有明显的变化，使分类边界变得平滑。

如何选取超参数#

Hyperparameters 这个词大家应该都不陌生，上面问题中，如何选取 K 值，如何选取 distance funcion，都会直接影响到模型的预测结果。这种我们要设置而不是让模型来学习的参数，我们叫它 “超参数”。在测试我们的超参数好不好的过程中，我们要遵循以下原则

为了保证尽量不要太早碰 test dataset, 比较好的做法是专门取出一定比例的数据集作为 validation set.
老师给出的建议是：他会在论文截止前的一周再碰 test dataset。
cross-validation 也是一种可行的办法，但由于在大型数据集中训练成本太高，所以只在小型数据集中使用。

总结#

事实上， K 近邻的方法从未在 image 上使用，如课件所示，有很大的问题。像素之间的 L2 距离包含的有效信息不够，具体来说，右下三张图片和左边原图的 L2 距离相同，但很显然这 3 张图很不一样。

于是乎我们要引出 Linear Classification 的方法。我宣布：这节课白忙活😀！
课程中 lecture 2 的末尾讲了一点线性分类的内容，我打算将其放到 lecture 3 笔记中完整地介绍。