贪婪算法研究论文

加速卷积神经网络的方法主要可以分三个方面：1. 针对卷积操作优化，例如使用FFT实现卷积操作；2. 量化操作，例如网络的二值化（BinaryNet）；3. 在结构上简化，使模型变小。在结构上简化模型也可以分三类：张量分解、连接稀疏化，基于通道的裁枝。首先张量分解是将张量分解成多个小张量，但是输出的通道数并没有变化，因此对于1*1的卷积层很难通过张量分解的方法做压缩，而当前很多模型结构都用到了大量的1*1卷积（例如ResNet，GoogleNet，Xception等）。其次连接稀疏化是将两层之间的连接变稀疏，但是这种稀疏化处理通常是没有固定模式规律的，所以尽管理论上有很高的加速效果，但是实际实现很复杂，因为通过稀疏化处理，数据无法再通过原来的张量存储，需要使用稀疏矩阵/稀疏张量来存储，那么卷积操作也变成稀疏卷积。最后相比于前两种方法，基于通道的裁枝既可以减少通道数，又不会改变数据的存储方式，因此其对于CPU和GPU都有很好的加速效果，同时也不需要实现特殊的卷积操作。 模型压缩的典型工作： Low-rank Decomposition 低秩分解 ： 使用SVD等技术来近似于权重矩阵（它具有低秩矩阵）。 在全连接层上工作很好，但CNN的计算量主要在卷积层。 Weight Quantization 量化权值 ： 如HashNet量化网络权值（采用共享权重和哈希索引大大节省存储空间） 但不能节省运行时间（因为权重还需要恢复从而进行网络推理inference） 二值化是个很好的方法（或用三值化{-1,0,1}）。 Weight Pruning/Sparsifying 权重修剪或稀疏 ： 有论文将训练好的网络里的小权值修剪掉（即设为0），这样也可以用稀疏格式储存权值。 但是需要专用的稀疏矩阵运算库或特殊硬件来加速，且运行内存也没有减少。 Structured Pruning/Sparsifying 结构修剪或稀疏化： 有提出在训练好的网络中，修剪那些较小权值连接的Channel，再微调网络恢复精度方法的论文 有提出在训练前随机停用channel从而引入稀疏，有提出neuron-level的稀疏方法从而修剪神经元获得紧凑网络，也有提出结构化稀疏学习（SSL）的方法，去稀疏CNN不同层级的结构（filters、channels、layers）。 Neural Architecture Learning （NAS）神经结构学习： 有关于自动学习网络结构的方法，如谷歌通过强化学习来搜寻最佳网络结构，或者其他的给定巨大网络结构，从中学习出最佳子图网络。 但是资源消耗太大，时间太长。 传统的模型剪枝思路：训练一个冗余模型+剪枝+微调，剪枝的意义在于保留重要的权重，裁剪冗余的权重，以此尽可能保证准确率。实际上，对于所有STOA的模型结构剪枝算法，微调一个剪枝后的模型相比于从头训练一个剪枝候的模型，结果不会更好，甚至更差。意思就是说，剪枝之后保留的权重相比于剪枝之后网络模型的结构，并不那么重要，或者说， Network Pruning更多地是在进行网络结构的搜索 。根据实验观察，本文发现：1、训练一个大的参数冗余的模型并不是必要的；2、保留对于大网络重要的权重对于小模型而言并不那么重要；3、剪枝之后的网络结构本身而非保留的权重对于最后模型的有效性更为重要。 传统剪枝的两点共识： 1、训练一个效果优良的大模型很重要，以此保证高准确率； 2、剪枝之后的模型结构和保留的权重都很重要，因此是fine-tuning而非train from scratch 本文认为在进行结构剪枝（structured pruning method）（在卷积通道上进行剪枝）上述两个共识可能并不是必须的。 两个观察： 1、对于预先定义（predefined）目标模型的结构剪枝，直接从头训练剪枝模型不比微调剪枝之后的模型效果差，甚至更好； 2、对于事先不知道（auto-discover）目标模型的结构剪枝，从头训练也不比微调的结果差，甚至更好。 意思是说结构比参数重要，模型剪枝可能本质就在做网络结构的搜索。此外，从参数冗余的大模型继承权重参数似乎并不是那么好，可能让剪枝之后的模型陷入局部优化。 对于非结构化的网络剪枝（unstructured，weight level），在小数据集上从头训练往往与微调剪枝模型效果相当，但是在大数据集上不是如此。 从头训练有两种方式： 剪枝模型与大模型训练同样的轮数显然不公平，因为剪枝模型一轮训练的计算量明显远低于大模型。 因此，一种方法是使得训练大模型和训练小模型的总体计算量是相同的（FLOPs），换言之，剪枝降低了几倍的计算量，训练轮数就是训练大模型的几倍，称之为Scratch-B。另外一种的使得训练剪枝模型的轮数跟训练大模型一样，称之为Scratch-E。 Predefined Structured Pruning L1-norm based Filter Pruning 以往一些剪枝的操作主要是 减少了全连接层的参数 ，全连接层的参数量占比最多（比如VGG-16中全连接层操作参数占了90%，但计算量只占了不到1%）, 但是主要的计算量集中在卷层操作。意即对权重矩阵进行稀疏化并不能充分减少计算量。论文提出 对卷积层进行剪枝操作 ，然后进行retrain，不会造成 稀疏连接 （稀疏矩阵操作需要特殊的库等来处理），全连接层可以使用 平均池化层 来代替以减少参数量。 pruning filters and feature maps 第 层卷积层的输入特征图为 ，卷积核维度为 ，单个卷积核记为 ，输出特征图维度为 ，总计算量为 ，去除一个卷积核，将减少的计算量为 ，因此，如果去除 个卷积核，将减少的计算量倍数为 。 在单层中确定去除那些卷积核： 衡量每层中单个卷积核的相对重要性：绝对值的和（矩阵L1范数和） 具有较小权重的卷积核可以认为倾向于产生较小激活的特征图（相比于同层内的其他卷积核） 选择前m个最小的绝对值，删除对应的卷积核和特征图，相比于随机选择相同数量的filters和选择最大值filters的结果比较，效果更好 。 算法： 对于每一个filter matrix按列绝对值求和 对求和结果排序 裁剪掉m个绝对值最小的filters，以及对应的输出，它又是下一层的输入，所以也得去掉下一层卷积核的对应通道 剩余的kernel weights保留 决定每层对剪枝的敏感性： 每一卷积层进行单独剪枝，查看在validation set上准确度的变化，对于VGG-16，一些卷积层的卷积核数量是一样的，所以对于敏感度差不多的卷积层，使用相同的比例进行剪枝，而对于敏感度比较大的层，选择最小的比例进行剪枝或者不进行剪枝。 跨越多层的剪枝： 之前的一些剪枝策略是逐层剪枝，然后进行retraining，但是这样是非常耗时的。 两种策略  独立剪枝：就是每一层是独立的，当剪枝层的输入特征图通道减少，决定该去掉哪些卷积核时，范数的计算还是应该考虑原始卷积的所有通道，然后进行剪枝 贪心剪枝：就是考虑到上一层被剪掉的情况，当剪枝层的输入特征图通道减少，决定该去掉哪些卷积核时，范数的计算要去掉对应输入特征图减少的通道，然后进行剪枝 Retraining 剪枝之后，应该retraining（类似fine-tune）  一次性剪枝然后retrain 逐层剪枝进行retrain 第二种策略结果可能会更好，但是需要更多的epochsThiNet 作者主页 prune以filter（卷积核）为单位，根据该层filter的输出来判断该filter是否对结果有贡献，如果没有贡献或贡献很小，则直接把这个filter去掉，关键在于filter的选择方式，依据则是如果可以用某一层的输入的一个子集代替原来的输入得到尽可能类似原来的输出的话，那么子集以外的输入就可以去掉，则其对应的前面一层的卷积核也就可以去掉。如下图。 以去掉冗余卷积核做prune的研究还有很多，关键在于选择方式，比如计算filter的绝对值和，认为如果一个filter的绝对值和比较小，说明该卷积核并不重要，这种算法暂且叫Weight sum；还有计算激活层输出的feature map的值的稀疏程度，如果feature map的值很稀疏，也就是大部分值是0，那么该feature map对应的filter也是冗余的，可以去掉，这种算法暂且叫APoZ（Average Percentage of Zeros）。 Filter selection： 不同于一些方法：用第 层的数据来指导剪枝第 层的卷积核，本文使用第 层来确定第 层的剪枝，如前所述： 如果能用第 层的输入的某一子集来估计该层的输出，那么输入中的其他通道就可以被去掉，而第 层的输入来源于第 层的输出，那么对应第 层的卷积核就可以去掉。 Pruning： 同时去掉第 层输入的weak channel，和与其对应的第 层的卷积核，网络结构不变，只是变瘦了。 Finetuning： 当对每一层做prune后，都fine-tune1到2个epoch，然后等所有层都prune后，再fine-tune多个epoch。 因此整体上就是上述三步迭代应用到每一层上，依次对每一层做prune。 Data-drive channel election： 将一个卷积操作定义为： ， 表示输入特征图，维度为 ， 表示卷积核，维度为 目标是移除一些不太重要的卷积核 ，而由于第 层的卷积核数量没变，因此第 层的输出的维度是不变的，意即第 层的输入 不变，根据这样的想法，就可以移除第 层中对 影响很小的那些卷积核，这样对整个网络的性能影响也很小。换句话说，就是最小化 的重构损失。 Collecting training examples 从 上任意取一位置分量 ，有： 意即可以寻找一个子集 ，使得： 贪心算法：给定输入 ，优化： m是图像数量和位置数量的乘积。 由于 包含channel较多，因此求解速度会很慢，因此定义另一个集合 ，集合 所包含的channel要少于 ，满足： 则优化下式： 对于ResNet这样的网络，在每一个stage的每一个block中一般有三层卷积，其中最后一层卷积的结果需要和skip connection的结果做element-wise product，这样的话就得保证该block的最后一层卷积的输出channel个数和skip connection的输出channel个数一样。因此在文中采用只对一个block的前两层卷积做prune，而不动最后一个卷积层，如下图Figure3。另外对于VGG-16网络，由于前面10层卷积占据了90%的计算量，而全连接层又占据了86%的参数，因此作者采用对前面10层卷积层进行prune，达到加速目的，另外将所有全连接层用一个global average pooling层代替。Regression based Feature Reconstruction Channel Pruning for Accelerating Very Deep Neural Networks 对于一个训练好的模型，本文方法通过一个2步迭代的算法逐层裁枝，优化函数是LASSO回归和最小二乘法重建误差。 与ThiNet类似，本文不去考虑单个参数的重要性，而是直接最小化输出特征图的重建误差，逐层地做裁枝，为了降低特征图B的通道，通过最小化特征图C的重构误差得到。 第一步是选择通道，第二步是特征图重建，目的是最小化重建误差，本文提出两步迭代的算法：首先选取最具代表性的通道，即裁剪B层到C层的卷积；其次重建特征图，调整B层到C层的参数W，使C层特征图重建误差最小。迭代交替进行以上两步。通过基于LASSO回归的方法来找到最具代表性的通道。 假设特征图B到特征图C的卷积表示为 ，特征图B ，特征图C ， 表示batch_size，将特征图B的通道由 降为 表示非零项数， 是向量 的分量，为0就表示对应通道被去掉， ， 都表示单通道的特征图/卷积核。但由于上式中的约束条件是0-范数，属于 优化问题，求解为NP难问题，因此进一步将0-范数放宽到1-范数，得优化函数为： 选择通道： 固定参数 不变，求解 ，则上述优化问题可以进一步转化为LASSO回归问题： ，上式可以通过SGD方法找到最优解，是比较常见的优化问题。 重构特征图： 固定 不变，上式可以转化为最小二乘估计问题： 最小二乘估计问题同样为常见的优化问题，也可以利用SGD的方法得到最优解，最后做出调整，保证范数为1： 对多分支网络进行剪枝： 在裁剪第一个卷积时，并不删掉其输入特征图的通道，而是新加一层采样层（其用处就是对输入特征图按 来进行采样，同时保留了原本的输入特征图作为shortcut的输入），对于残差块的第一个卷积层的输入进行通道采样，估计 的重构误差。 Automatic Structured Pruning Network Slimming 利用batch normalization中的缩放因子 作为重要性因子，即 越小，所对应的channel就不太重要，就可以裁剪（pruning） 对BN层中的scale factor 进行L1正则化，使其变得稀疏。BN：直接用 来评估channel的重要程度。 的数越小，说明该channel的信息越不重要，也就可以删减掉该Channel。 为什么不用 作为重要性因子？ feature map的信息量是来源于方差而非均值。方差越大则该feature map内的特征就越明显。 服从分布 ，因此方差越小，信息量就越少，就越不重要 某些通道特征图的方差越小，意即对下一层特征图的所有单元的贡献值越平均，将其去掉，仅仅只是做了特征评议，不影响相对差异 因此对BN的缩放因子添加smooth L1正则化（不是Fast R-CNN中的smooth L1 Loss），损失函数定义为：训练方法为： 第一步：初始化网络； 第二步：加入Channel稀疏惩罚项，训练网络； 第三步：通过固定阈值来删减channel，如删减70%的channel； 第四步：Fine-tune。由于删减channel后精度会下降，故再训练去微调网络； 第五步：可以再跳到第二步，实现多次精简网络； 第六步：得到精简后的网络。

优化的分布式梯度提升算法，end-to-end 不需要特征抽取。输入原始数据，就能输出目标结果。 整篇论文技术实现分两个部分显而易见，xgboost是非线性(Tree)的加法模型如果是回归问题则可能是：                                                                                    而分类问题则应该是交叉熵, 此处 ： 二分类问题： 多分类问题： 这里review一下，对于多分类及二分类，交叉熵及soft公式，二分类均是多分类的特例 : ： 原文描述：Default direction, 按我的理解应该是：每轮迭代，每颗树对待一个特征缺失的方向处理应该是一致的，但是不同特征的缺失方向是随机的；不同的迭代子树，策略也是随机的在建树的过程中，最耗时是找最优的切分点，而这个过程中，最耗时的部分是 将数据排序 。为了减少排序的时间，Xgboost采用 Block结构 存储数据(Data in each block is stored in the compressed column (CSC) format, with each column sorted by the corresponding feature value) 对于approximate算法来说，Xgboost使用了多个Block，存在多个机器上或者磁盘中。每个Block对应原来数据的子集。不同的Block可以在不同的机器上计算。该方法对Local策略尤其有效，因为Local策略每次分支都重新生成候选切分点。使用Block结构的一个缺点是取梯度的时候，是通过索引来获取的，而这些梯度的获取顺序是按照特征的大小顺序的。这将导致非连续的内存访问，可能使得CPU cache缓存命中率低，从而影响算法效率在非近似的贪心算法中， 使用 缓存预取（cache-aware prefetching） 。具体来说，对每个线程分配一个连续的buffer，读取梯度信息并存入Buffer中（这样就实现了非连续到连续的转化），然后再统计梯度信息 在近似 算法中，对Block的大小进行了合理的设置。 定义Block的大小为Block中最多的样本数 。设置合适的大小是很重要的，设置过大则容易导致命中率低，过小则容易导致并行化效率不高。经过实验，发现2^16比较好当数据量太大不能全部放入主内存的时候，为了使得out-of-core计算称为可能，将数据划分为多个Block并存放在磁盘上。计算的时候，使用独立的线程预先将Block放入主内存，因此可以在计算的同时读取磁盘。但是由于磁盘IO速度太慢，通常更不上计算的速度。因此，需要提升磁盘IO的销量。Xgboost采用了2个策略： Block压缩（Block Compression）：将Block按列压缩（LZ4压缩算法？），读取的时候用另外的线程解压。对于行索引，只保存第一个索引值，然后只保存该数据与第一个索引值之差(offset)，一共用16个bits来保存 offset，因此，一个block一般有2的16次方个样本。 Block拆分（Block Sharding）：将数据划分到不同磁盘上，为每个磁盘分配一个预取（pre-fetcher）线程，并将数据提取到内存缓冲区中。然后，训练线程交替地从每个缓冲区读取数据。这有助于在多个磁盘可用时增加磁盘读取的吞吐量。[1]  R. Bekkerman. The present and the future of the kdd cup competition: an outsider’s perspective. (xgboost应用) [2]  R. Bekkerman, M. Bilenko, and J. Langford. Scaling Up Machine Learning: Parallel and Distributed Approaches. Cambridge University Press, New York, NY, USA, 2011.(并行分布式设计) [3]  J. Bennett and S. Lanning. The netflix prize. In Proceedings of the KDD Cup Workshop 2007, pages 3–6, New York, Aug. 2007.(xgboost应用) [4]  L. Breiman. Random forests. Maching Learning, 45(1):5–32, Oct. 2001.(Breiman随机森林论文) [5]  C. Burges. From ranknet to lambdarank to lambdamart: An overview. Learning, 11:23–581, 2010. [6]  O. Chapelle and Y. Chang. Yahoo! Learning to Rank Challenge Overview. Journal of Machine Learning Research - W & CP, 14:1–24, 2011.(xgboost应用) [7]  T. Chen, H. Li, Q. Yang, and Y. Yu. General functional matrix factorization using gradient boosting. In Proceeding of 30th International Conference on Machine Learning(通过梯度提升的方法来实现general的矩阵分解) (ICML’13), volume 1, pages 436–444, 2013. [8] T. Chen, S. Singh, B. Taskar, and C. Guestrin. Efficient second-order gradient boosting for conditional random fields. In Proceeding of 18th Artificial Intelligence and Statistics Conference (AISTATS’15), volume 1, 2015.(二阶导boost实现的条件随机场) [9] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification. Journal of Machine Learning Research, 9:1871–1874, 2008.(xgboost应用) [10] J. Friedman. Greedy function approximation: a gradient boosting machine. Annals of Statistics, 29(5):1189–1232, 2001.(gbm的贪心算法实现) [11] J. Friedman. Stochastic gradient boosting. Computational Statistics & Data Analysis, 38(4):367–378, 2002. (随机梯度下降) [12] J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: a statistical view of boosting. Annals of Statistics, 28(2):337–407, 2000.(叠加式的逻辑回归方式) [13] J. H. Friedman and B. E. Popescu. Importance sampled learning ensembles, 2003.(采样学习) [14] M. Greenwald and S. Khanna. Space-efficient online computation of quantile summaries. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, pages 58–66, 2001. [15] X. He, J. Pan, O. Jin, T. Xu, B. Liu, T. Xu, Y. Shi, A. Atallah, R. Herbrich, S. Bowers, and J. Q. n. Candela. Practical lessons from predicting clicks on ads at facebook. In  Proceedings of the Eighth International Workshop on Data Mining for Online Advertising, ADKDD’14, 2014.(xgboost应用) [16] P. Li. Robust Logitboost and adaptive base class (ABC) Logitboost. In Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI’10), pages 302–311, 2010.(logitboost) [17] P. Li, Q. Wu, and C. J. Burges. Mcrank: Learning to rank using multiple classification and gradient boosting. In Advances in Neural Information Processing Systems 20, pages 897–904. 2008.(多分类应用) [18] X. Meng, J. Bradley, B. Yavuz, E. Sparks, S. Venkataraman, D. Liu, J. Freeman, D. Tsai, M. Amde, S. Owen, D. Xin, R. Xin, M. J. Franklin, R. Zadeh, M. Zaharia, and A. Talwalkar. MLlib: Machine learning in apache spark.  Journal of Machine Learning Research, 17(34):1–7, 2016.(分布式机器学习设计) [19] B. Panda, J. S. Herbach, S. Basu, and R. J. Bayardo. Planet: Massively parallel learning of tree ensembles with mapreduce. Proceeding of VLDB Endowment, 2(2):1426–1437, Aug. 2009.(分布式机器学习设计) [20] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.(sklearn) [21] G. Ridgeway. Generalized Boosted Models: A guide to the gbm package. [22] S. Tyree, K. Weinberger, K. Agrawal, and J. Paykin. Parallel boosted regression trees for web search ranking. In Proceedings of the 20th international conference on World wide web, pages 387–396. ACM, 2011. [23] J. Ye, J.-H. Chow, J. Chen, and Z. Zheng. Stochastic gradient boosted distributed decision trees. In Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM ’09. [24] Q. Zhang and W. Wang. A fast algorithm for approximate quantiles in high speed data streams. In Proceedings of the 19th International Conference on Scientific and Statistical Database Management, 2007.(数据处理加速计算) [25] T. Zhang and R. Johnson. Learning nonlinear functions using regularized greedy forest. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(5), 2014.