小结：经典的VC维学习理论，假设的前提是数据可学习的情况下，算法拟合效果的优劣。论文做了比较有意思的实验。 把标签随机化，也就是把可学习的任务变成不可学习的任务。但实验结论表明，训练误差仍然可以为0，那么随机标签后，任务还是可学习的，这个VC理论不同。
论文的核心结论是：DNN模型能够有效记住样本。

一、问题与现状

尽快DNN模型有大量参数，但有效的DNN模型在训练集、测试集上误差差异较小。
论文通过一些列实验发现：传统方法难以解释大型的神经网络在实际应用中泛化性能的优异性。

论文贡献：

随机化测试（randomization test）
把原始数据集的label替换成随机的label，并做了多组实验。得到主要的发现是：DNN可以很容易的拟合随机标签。可以总结出如下观点：
1、NN的模型容量足够大，能记住整个数据集。
2、即使在随机标签数据集上的训练模型也容易。事实上，其收敛时间只真实标签增加常数量级。
3、随机标签可以看成是一个独立的数据转换任务。使得学习任务的其他性质并没有改变。

论文还进行label上添加噪声的实验，发现CNN可以训练到训练误差为0。进一步的，尝试不同程度的加噪声实验（纯label到纯噪声的实验），实验发现，噪声越多泛化误差越大，这表明DNN能有效地捕获数据中残留的有效信号，同时暴力地拟合噪声部分。

上述实验观察到的现象，VC维理论是无法解释的。

显示正则化的地位
论文实验了权重衰减、dropout、数据增强等正则化方法，发现都不能准确地解释神经网络的泛化误差。得到如下结论：显示的正则化或许能提高模型的泛化能力，但是也非必要操作。

和经典地 经验风险误差（empirical risk minimization）对比来看，显示的正则化对模型的泛化性有很大影响。

有限样本的表达性（Finite sample expressivity）
一般地大型神经网络可以表达训练数据中的任何标签。

There exists a two-layer neural network with ReLU activations and 2n+d weights that can represent any function on a sample of size n in d dimensions

隐式正则化的地位
论文认为SGD 是一种隐式的正则化。

二、实验

随机化测试的出发点是：VC假设地是数据可以学习，论文直接把标签随机化了，也就是数据是不可学习的，那么训练误差应该很大，但实验表明，训练误差可以是0，且训练迭代次数没有增加很多（常数量级），那么这显然和传统的泛化理论有所不同了。
image.png
true label：真实的label
partially corrupted label：以概率P决定是否Label是否改变成随机Label
random labels：全是随机label
shuffled pixels：样本间重排列
random pixels：样本内重排列
guassion：使用一个高斯分布生成随机的特征。


三、结论

本文做了一些实验用来理解、定义神经网络模型的有效容量。这些实验表明了比较成功的一些神经网络模型的容量足够大以至于能记住混乱的训练数据，这和传统的机器学习理论相悖论。此外，论文发现即使模型的结果不够泛化，但是优化依然很容易（即：训练误差为0）。