Nearest Neighbor Classifier
L1 vs. L2. It is interesting to consider differences between the two metrics. In particular, the L2 distance is much more unforgiving than the L1 distance when it comes to differences between two vectors. That is, the L2 distance prefers many medium disagreements to one big one. L1 and L2 distances (or equivalently the L1/L2 norms of the differences between a pair of images) are the most commonly used special cases of a p-norm.
L1和L2的比较：L2对差异的容忍度更低。也就是说，相对于一个巨大的差异，L2更倾向于接受多个中等程度的差异。L1和L2都是最常见的p-norm的一种特殊形式。
K-Nearest Neighbor Classifier
we cannot use the test set for the purpose of tweaking hyperparameters.
Hyperparameters的选择：在实际中，我们不能用测试集（test set）作为参数的调整。
Evaluate on the test set only a single time, at the very end.
Validation sets for Hyperparameter tuning
可以使用验证集（validation set）的方法来调整hyperparameters
Using CIFAR-10 as an example, we could for example use 49,000 of the training images for training, and leave 1,000 aside for validation. This validation set is essentially used as a fake test set to tune the hyper-parameters.
Split your training set into training set and a validation set. Use validation set to tune all hyperparameters. At the end run a single time on the test set and report performance.
Cross-validation
实际中，人们避免使用交叉验证，因为交叉验证计算量很大。人们一般把50%-90%的数据作为训练数据，其余的作为验证数据。然而，这还取决于其他因素，例如：如果超参数量很大，你希望使用更大的验证集。如果验证集的数量很少（只有几百），那么你就应该使用交叉验证的方法。在实践中，你一般看到的是3-fold，5-fold或者10-fold交叉验证。
Pros and Cons of Nearest Neighbor classifier
优点
- 易实现、易理解
- 分类器的训练不需要花费时间
缺点：
- 测试时间很长
- 分类器必须记住所有的训练数据，为了以后和测试数据进行比较
The Nearest Neighbor Classifier在某些特定情况下是一个不错的选择（特别当数据是低维的），但是在实际的图像分类工作中，很少被使用。
在实际中使用kNN
- 预处理你的数据。对你数据中的特征进行归一化，即零平均值（zero mean）和单位方差（unit variance）。
- 如果你的数据维度很高，考虑使用一种降维的方法。例：PCA (wiki ref, CS229ref, blog ref) or even Random Projections.
- 将你的数据随机分为train/val集。一般规律是：70-90%的数据为训练集。这个比例由超参数的数量和这些超参数对于算法的预期影响来决定。如果超参数的数量很多，那么应该使用更大的验证集来估计。如果担心验证集的数量不够多，那么最好使用交叉验证的方法。如果计算资源足够多，那么最好使用交叉验证（fold的个数越多越好，但是计算量也就大）。
- 在验证集（Validation data）上调优。选择k、和距离类型（L1 和L2）
- 如果kNN分类器所需的计算时间过长，考虑使用 Approximate Nearest Neighbor library (e.g. FLANN)缺点是准确率降低。
- 记录最优的超参数。记录最优参数后，是否应该让使用最优参数的算法在完整的训练集上运行并再次训练呢？因为如果把验证集重新放回到训练集中（自然训练集的数据量就又变大了），有可能最优参数又会有所变化。在实践中，不要这样做。不要在最终的分类器中使用验证集数据，这样做会破坏对于最优参数的估计。直接使用测试集来测试用最优参数设置好的最优模型，得到测试集数据的分类准确率，并以此作为你的kNN分类器在该数据上的性能表现。
