Not All Samples Are Created Equa

Katharopoulos A, Fleuret F. Not All Samples Are Created Equal: Deep Learning with Importance Sampling[J]. arXiv: Learning, 2018.

@article{katharopoulos2018not,
title={Not All Samples Are Created Equal: Deep Learning with Importance Sampling},
author={Katharopoulos, Angelos and Fleuret, F},
journal={arXiv: Learning},
year={2018}}

概

本文提出一种删选合适样本的方法, 这种方法基于收敛速度的一个上界, 而并非完全基于gradient norm的方法, 使得计算比较简单, 容易实现.

主要内容

设为输入输出对, 代表网络, 为损失函数, 目标为

其中是总的样本个数.

假设在第个epoch的时候, 样本(被选中)的概率分布为, 以及梯度权重为, 那么且

在一般SGD训练中.

定义为SGD的收敛速度为:

如果我们令 则

在这里插入图片描述
定义
在这里插入图片描述
我们自然希望能够越大越好, 此时即负项越小越好.

定义, 既然

在这里插入图片描述
(7)式我有点困惑，我觉得(7)式右端和最小化(6)式的负项()是等价的.

于是有

在这里插入图片描述

最小化右端(通过拉格朗日乘子法)可得, 所以现在我们只要找到一个即可.

这个部分需要引入神经网络的反向梯度的公式, 之前有讲过，只是论文的符号不同, 这里不多赘诉了.

在这里插入图片描述 在这里插入图片描述

注意的计算是比较复杂的, 但是, 所以我们只需要计算部分, 设此分布为.

另外, 在最开始的时候, 神经网络没有得到很好的训练, 权重大小相差无几, 这个时候是近似正态分布的, 所以作者考虑设计一个指标，来判断是否需要根据样本分布来挑选样本. 作者首先衡量

在这里插入图片描述
显然当这部分足够大的时候我们可以采用分布而非正态分布, 但是这个指标不易判断, 作者进步除以. 在这里插入图片描述
显然越大越好, 我们自然可以人为设置一个. 算法如下
在这里插入图片描述

最后, 个人认为这个算法能减少计算量主要是因为样本少了, 少在一开始用正态分布抽取了一部分, 所以...