Paper HashingTricks

Abstract

深度网络在移有链接动设备上应用越来越多，一个 dilemma 变得越来越明显：深度学习的趋势是开发能够吸收更大数据集的模型，然而移动设备的存储空间有限，不能存储过大的模型，这里提出了一种 HashedNets，通过减少神经网络的内部固有冗余来实现模型尺寸的减少。HashedNets 利用一个低开销的哈希函数来将连接权重随机分组进不同的哈希桶，而同一个哈希桶里面的所有连接都使用同一个参数值，这些参数在标准的反向传播过程中被进行调整。这个哈希过程不会引入额外的内存开销。在不同的 benchmark 数据集上性能说明 HashedNets 可以在保留泛化性能的基础上明显减少存储需要。

1.Introduction

近十年里，深度神经网络在很多应用领域里都设立了新的性能标准，这些领域包括：物体分类，语音识别，图像字幕生成和域适应。随着数据的增加，为了获取更多参数信息，神经网络中的参数数量也在增加。并且在工业集群和高性能 GPU 上进行训练，这是发展的一个趋势。而另外一个趋势在于机器学习开始向移动设备和嵌入式设备上进行迁移，这些设备具有比较低的能耗，并且关键在于他们只有比较小的工作内存。

这两个趋势之间的分离导致了 state-of-the-art 的网络应用在移动设备上的 dilemma。在工业集群上训练好的最高效的模型可能也会超过移动设备的运行内存。语音识别领域的一个解决办法就是把经过处理的语音传到计算中心然后在服务器端进行计算。然而这样需要有比较高的带宽，另外一个办法就是为移动设备上的应用训练小型网络，但是这样会损失精度（从 2018 年来看的话这种方法还是可行的，一方面移动设备计算能力增长很快，另一方面 ShuffleNet 等轻量化网络在精度上也很不错）。

这样的 dilemma 促进了网络压缩的发展，研究表明神经网络当中有大量的冗余，作者表明其中只有一小部分是有用的，并且使用了权重矩阵的低秩分解对其进行了开发。另外有研究表明深层网络压缩成一层浅网络，通过利用完全训练好的网络的输出来训练小网络来实现（从 2018 的角度来看就是 ditillation，应该也是 2015 年 Hinton 第一次提出这个名词，不过 06 年就有相关的想法出现）。还有利用 reduced bit precision 来实现的，还有 1989 年 lecun 提出去除神经网络中不重要的权重。总而言之，神经网络中很多权重参数都是没用的。

通过很多 benchmark 证明 HashedNets 能够在少量影响精度的情况下大幅减少模型尺寸。在同样的内存限制下，Hashing 的方法要比 low-rank 分解具有更多可调节的参数。同样发现在有限的参数集下，重复使用参数，对神经网络进行扩张也是很有好处的，另外 HashedNets 的网络再扩张之后也不对其他的网络结构设计造成影响（dropout 正则化之类的）。

2.Feature Hashing

3.Notation

这一节主要介绍了向量，矩阵等符号表示，以及公式当中的符号所代表的含义等。

4.HashedNets

这一章节主要介绍了 HashedNets，一种模型尺寸和内存要求都大幅减少的神经网络的变种，之后最先介绍了在网络连接之间进行随机权重共享的方法实现，然后描述了如何利用 hashing trick 对其进行改善，从而避免更多内存开销。

4.1.Random weight sharing

全连接的网络层有很多参数，如果对于每一层都有内存限制，如果超过了内存限制，需要减小每一层所占内存，通常有两个办法：1.减少连接的节点数。2.减少权重矩阵中的位精度。然而如果内存限制已经很小了，那么这两种方法将会降低网络的泛化能力。这里提出了一种新的方法：利用一个虚拟的权重矩阵，通过权值共享减小其有效内存消耗。具体结构如图所示：

4.2.Hashed Neural Nets (HashedNets)

随机权值共享的一个简单的实现就是用第二个矩阵来包含每个连接的分组情况，然而这样过于详细的表示方法在节省内存这方面上表现并不好。这里打算利用哈希的方式来实现权值共享，利用$w^{l}_i$来存储第$l$层的第$i$个有效权重，$V^l_{i,j}$代表虚拟权重，然后利用哈希函数$h^l(i,j)$来将虚拟权重上的下标映射到有效权重上，即$V^{l}_{ij}=w^{l}_{h^l(i,j)}$，这里利用开源的 xxHash 来实现这一功能

4.3.Feature hashing versus weight sharing

HashedNets 的单层计算公式为$z_i=\sum^{m}_{j=1}V_{ij}a_j=\sum^{m}_{j=1}w_{h(i,j)}a_j$，同样可以通过特征哈希的方式来对 HashedNets 进行阐释，即将输入的 m 维特征通过哈希的方式映射到 k 维中，可以得到与权值共享同样的结果，可以看作对 HashedNets 的另一种解释。

在特征哈希中，哈希函数表示为

$$[\phi_{i}(a)]_{k}=\sum_{j:h(i,j)=k}a_j$$

其中$i$表示权值矩阵当中的第$i$行，$[\phi_{i}(a)]_{k}$表示在映射之后的 k 维的特征空间中的第$k$个元素，可以将$z_i$写成以下形式：

$$z_i=\sum_{k=1}^{K}w_{k}[\phi_{i}(a)]_{k}=\sum_{k=1}^{K}w_{k}\sum_{j:h(i,j)=k}a_j$$

另外继续通过变换可以得到：

$$z_{i}=\sum^{m}_{j=1}\sum_{k=1}^{K}w_{k}a_{j}\delta_{[h(i,j)=k]}=\sum^{m}_{j=1}w_{h(i,j)a_{j}}$$

这个表达式与权值共享得到的表达式是一样的，因此二者其实是等价的。

Sign factor：出于权值随机共享和特征哈希之间的等价性，HashedNets 继承了一些特征哈希的优点，比如在特征哈希中可以通过引入$\xi(i,j)$，以此消除由于冲突而引起的的内积偏差。

Sparsity：以前的研究表明，在稀疏特征向量的时候应用特征哈希是最有用的，因为此时的冲突比较小。在隐藏层里面使用稀疏诱导的激活函数可以进一步促进该现象，比如 ReLU。在这里全部使用了 ReLU 激活函数因为稀疏诱导性和很强的泛化性能。

Alternative neural network architectures：这里主要研究的是全连接的前向传播网络，HashedNets 也能应用在其他网络上，比如 RNN 等，同样也可以与其他网络压缩方法相融合，比如使用 Low-bit 存储，移除某些边，或者通过其他大型网络的输出来训练 HashedNets 等。

4.4.Training HashedNets

这里分为三个部分来介绍：1.在前向传播阶段计算一个哈希层的输出。2.从输出层向输入层传播梯度。3.在反向传播的过程中计算对权重$W^l$的梯度

前向传播的公式：

$$a_i^{l+1}=f(\sum^{n^l}_{j}w^{l}_{h^{l}(i,j)}\xi^{l}(i,j)a_{j}^l)$$

误差项：

$$\delta_{j}^{l}=(\sum_{i=1}^{n^{l+1}}\xi^{l}(i,j)w^{l}_{h^{l}(i,j)}\delta_{i}^{l+1})f'(z_{j}^l )$$

损失函数对于参数的梯度：

$$\frac{\partial L}{\partial V_{ij}^{l}}=a^{l}_{j}\delta_{i}^{l+1}\\ \frac{\partial V_{ij}^l}{\partial w_{k}^{l}}=\xi^{l}(i,j)\delta_{h^{l}(i,j)=k}$$

上面公式中第一个是损失函数对虚拟权重的微分，后一个是虚拟权重对真实权重的微分，利用链式法则将二者结合起来则得到：

$$\frac{\partial L}{\partial w_{k}^{l}}=\sum_{i,j}\frac{\partial L}{\partial V_{ij}^l}\frac{\partial V_{ij}^{l}}{\partial w_{k}^{l}}=\sum_{i=1}^{n^{l+1}}\sum_{j}a_{j}^{l}\delta_{i}^{l+1}\xi^{l}(i,j)\delta_{h^{l}(i,j)=k}$$

5.Related Work

深度神经网络在很多真实世界应用中都取得了巨大的进展，包括图像分类，目标检测，图像检索，语音识别和文字表达等。现在已经有了很多尝试去在各种语境下减少神经网络的复杂度，最流行的方法就是卷积神经网络，在每一个感知野里面都用了同样的滤波器，既能够减小模型尺寸也能改善泛化性能。另外与池化相结合能够减少层之间的连接，只展示输入特征的一部分。自编码器则在编码器与解码器之间使用同样的权值。

其他有一些方法可以减少网络中自由参数的数量，但是并不一定能减少内存开销。有一种用于正则化的软权值共享的方法，将权值建模成一个混合高斯模型：对权值进行聚类，使得同一个组的权重有同样的值。因为权值在训练之前并不清楚，所以在训练过程中对权重进行聚类。这个方法与 HashedNets 不同，需要大量的参数来记录每个权重值所对应的组成员。

还有一种方法是直接去掉不重要的权重，但是这种方法同样需要大量的参数来存储稀疏的权重值。另外有方法在实验中表明随机去掉网络中的连接将导致很好的经验性能，这点与 HashedNets 的想法类似。

有的方法利用减少数值表示精度的方法来减少模型的尺寸，比如 16 位的定点表示相比双精度浮点表示减少为 1/4 的存储量，然而在性能上只有少量降低，这个方法可以拿来与其他方法相耦合。

最近的研究表明通过直接学习每一层的低秩分解发现神经网络参数中有大量的冗余，直接从低秩分解恢复来的网络只是轻微的降低了性能，相比所有权重值都作为自由参数的情况下。后续的工作用了类似的技术来加速 CNN 的测试速度，而不是在减少存储空间和内存开销。HashedNets 与这项工作是互补的，两种方法可以组合在一起。

另一种方法就是蒸馏，作者表明蒸馏出来的模型相比只在标签上进行训练有更好的泛化性能。还有一种 nested dropout 方法，可以对隐藏节点的重要性进行排序，在训练完成之后去掉这些节点。

一种方法是第一次提出对于移动和嵌入式设备进行 NLP 模型的优化，提出了随机特征混合基于哈希函数来对特征进行分组，能够显著减少特征数量和参数数量，在特征哈希的帮助下，Vowpal Wabbit 大规模学习系统能够对数据集进行缩放。