SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning
SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning
复制标题
DOI：
--
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Yuege Xie;Bobby Shi;Hayden Schaeffer;Rachel A. Ward
中科院分区：
文献类型：
--
作者：
Yuege Xie;Bobby Shi;Hayden Schaeffer;Rachel A. Ward
稀疏收缩加性模型和稀疏随机特征模型已经被分别开发作为学习低阶函数的方法，其中变量之间的相互作用很少，但都没有提供计算效率。另一方面，基于$\ell_2 $的收缩加性模型是有效的，但不提供特征选择，因为得到的系数向量是密集的。受迭代幅度修剪技术在神经网络彩票发现中的成功启发，我们提出了一种新的方法-通过IMP的稀疏随机特征模型（ShRIMP）-以有效地拟合具有稀疏变量依赖形式的固有低维结构的高维数据。我们的方法可以被看作是一个组合的过程来构造和找到稀疏彩票的两层密集网络。我们解释了观察到的好处SHRIMP通过细化分析的泛化误差阈值基追踪和由此产生的特征值的界限。从合成数据和真实世界的基准数据集上的函数近似实验，我们表明，SHRIMP获得更好的或有竞争力的测试精度相比，最先进的稀疏特征和添加剂的方法，如SRFE-S，SSAM和SALSA。同时，SHRIMP进行特征选择，具有较低的计算复杂度和鲁棒性的修剪率，表明所获得的子网络的结构的鲁棒性。我们通过SHRIMP了解彩票假说，注意到我们的模型和权重/神经元子网络之间的对应关系。
Sparse shrunk additive models and sparse random feature models have been developed separately as methods to learn low-order functions, where there are few interactions between variables, but neither offers computational efficiency. On the other hand, $\ell_2$-based shrunk additive models are efficient but do not offer feature selection as the resulting coefficient vectors are dense. Inspired by the success of the iterative magnitude pruning technique in finding lottery tickets of neural networks, we propose a new method -- Sparser Random Feature Models via IMP (ShRIMP) -- to efficiently fit high-dimensional data with inherent low-dimensional structure in the form of sparse variable dependencies. Our method can be viewed as a combined process to construct and find sparse lottery tickets for two-layer dense networks. We explain the observed benefit of SHRIMP through a refined analysis on the generalization error for thresholded Basis Pursuit and resulting bounds on eigenvalues. From function approximation experiments on both synthetic data and real-world benchmark datasets, we show that SHRIMP obtains better than or competitive test accuracy compared to state-of-art sparse feature and additive methods such as SRFE-S, SSAM, and SALSA. Meanwhile, SHRIMP performs feature selection with low computational complexity and is robust to the pruning rate, indicating a robustness in the structure of the obtained subnetworks. We gain insight into the lottery ticket hypothesis through SHRIMP by noting a correspondence between our model and weight/neuron subnetworks.