Linuxeden开源社区阿里巴巴ICLR Poster论文：基于交替方向法的循环神经网络多比特量化
(Alternating Multi-bit Quantization for Recurrent Neural Networks, in ICLR 18)
许晨，姚建强，林宙辰，欧文武，曹元斌，王志荣，查红彬
北京大学 阿里巴巴
*该工作在阿里巴巴搜索算法组实习期间完成
论文原文地址：https://arxiv.org/abs/1802.00150
介绍
循环神经网络(RNN)在语言模型、机器翻译、语音识别、生成图像标题等很多应用上都取得了非常好的效果。然而，这些模型常常是建立在高维的嵌入(embedding)或者多层的循环单元中，包含了大量的参数，使得无法在资源有限的移动端部署。此外，RNN的计算依赖于与当前的隐状态，只能被顺序执行，因此在执行推断时会造成比较大的延时。在拥有大规模并发请求的服务器端，比如语音识别或者机器翻译等应用，为了满足线上苛刻的响应时间要求，需要部署大量的机器。在这项工作中，我们考虑通过量化参数到二值{-1,+1}上来解决上述问题。考虑将模型的权重量化成1比特，相对于全精度，直接带来32倍的内存压缩。而对1比特参数的矩阵乘法，如果不考虑具体实现，相对于全精度乘法，理论上也会带来32倍的加速。然而，如果把模型的权重和激活都量化成1比特，在循环神经网络中，会带来很大的精度损失。因此，很自然的折中方案就是采用多比特量化（如图1所示）。
Figure 1多比特量化乘法示意
现有的多比特量化方法
1)均匀(Uniform)量化采用下列的k比特量化方案:
这样基于规则的量化方法非常容易实现,但是对于非均匀数据的量化效果很差，而非均匀分布数据在深度神经网络却更为常见。
2)均衡(Balanced)量化通过数据预处理来解决均匀量化的弊端。该方法首先产生2k个间隔，每个间隔大致包含等量的数据。然后该方法将每个间隔的中心线性映射到对应的量化编码中。尽管看起来更有效，但是该方法还是基于规则，而这种规则并不能保证对所有的数据分布都起效果。
3)贪婪法(Greedy)近似通过去解下面的带离散约束的分解问题来实现量化:
对于k=1, 上述问题存在闭式解。贪婪近似通过逐步量化余量(residue)并将其推广到k比特(k>1)的情形：
每个子步都有最优解
贪婪法非常高效，尽管不能得到一个高精度的解，但是将量化问题建模成一个优化问题的形式还是非常具有启发性的。
4)改进版(Refined)贪婪近似进一步拓展贪婪法以降低量化误差。在上述第j步最小化问题中，该方法加上额外一步最小二乘来修正系数
在原文量化卷积神经网络权重的实验中，修正版贪婪法被证实比原始的贪婪法更有效。然而，正如我们下面要讲的，修正版的贪婪法在量化精度方面仍然不能令人满意。
除了上述通用的多比特量化方案以外，还有文章还提出了三值量化，与1比特的二值量化相比，三值量化多了可行状态0。三值量化通过解如下问题
来实现编码。然而，原文并未提出一种高效的解法，相反，作者通过经验，将小于0.7/n|(|w|)| 1 0.7/n|(|w|)|1 的元素设成0, 并对剩余元素采用如上所述的二值量化。三值量化其实本质上等价于此处的2比特量化，唯一不同的地方在于多了一个α 1 =α 2 α1=α2 的约束。当二值编码被固定以后，最优系数α 1 α1 (或者α 2 α2 )类似地可以通过最小二乘得到。
基于交替方向法的多比特量化方案
接下来将介绍本文提出的量化方法，同样我们也是通过解上述的优化问题来实现量化。为了简单起见，首先考虑k = 2的情形，如果α 1 α1 和α 2 α2 已知且满足α 1 ≥α 2 α1≥α2 ，那么可行编码即被限制为以下四种情况v={−α 1 −α 2 ,−α 1 +α 2 ,α 1 −α 2 ,α 1 +α 2 } v={−α1−α2,−α1+α2,α1−α2,α1+α2} 。对于w中的任意元素w, 其编码都是通过最小二乘来确定。我们相应地可以将整个坐标轴分成四份，落在某个区间上的w分别对应其中一个量化编码。由最近邻条件可得区间的边界即为量化编码的中间值，也就是-α 1 α1 、0以及α 1 α1 。下图给出一个示意。
Figure 2当实系数固定时，最优2比特编码示意
对于任意k比特量化问题，假设{α i } k i=1 {αi}i=1k 已知，我们可以类似地将整个坐标轴分成2 k 2k 个区间，其边界同样通过相邻可行编码的中点来划分。如果直接将待量化的实数w与所有区间边界进行比较以确定对应编码，总共需要2 k 2k 次，当k比较大，这种操作非常不经济。事实上，我们可以利用可行编码全集v v 中元素单调递增的性质，将v v 均匀分成两个子集: v (1:m/2) v(1:m/2) 和v (m/2+1:m) v(m/2+1:m) , 其中m表示v的长度。如果w<(v m/2 +v m/2+1 )/2 w<(vm/2+vm/2+1)/2 ,其可行编码即被限制在子集v (1:m/2) v(1:m/2) 上。相反如果w≥(v m/2 +v m/2+1 )/2 w≥(vm/2+vm/2+1)/2 , 其可行编码即被限制在子集v (m/2+1:m) v(m/2+1:m) 上。通过递归地将可行编码子集均匀划分，我们只需要k次比较就可以得到最优编码。该过程可以看成是一个二叉搜索树，我们在下图中给出了一个k=2时的简单示意。一旦得到量化编码，即可将其一一映射到对应的二值向量{b i } k i=1 {bi}i=1k 。
Figure 3二叉搜索树将2k 次比较降为k次比较
基于上面的发现，我们重新来考虑上一节中介绍的改进版贪婪近似。经过最小二乘修正实系数之后，二值编码{b i } k i=1 {bi}i=1k 不再是最优，而该方法却仍将其固定。为了进一步改进，交替最小化实系数和二值编码变成了一个很自然的选择。一旦用二叉搜索树得到最优的{b i } k i=1 {bi}i=1k , 可以将其固定，并采用最小二乘更新{a i } k i=1 {ai}i=1k 。在真实实验中，以贪婪法得到的解作初始化，我们发现只需要两步交替迭代就足以得到高精度的解。
实验结果
我们在语言模型上进行量化实验，分别测试了LSTM和GRU两种架构。因为
Table 1 不同方法近似PTB数据集上训练好的LSTM的权重。其中FP表示全精度
Table 2不同方法近似PTB数据集上训练好的GRU的权重
实验是去预测下一个单词，其效果采用单字复杂度来衡量(perplexity per word, 简写成PPW)。为了检验所有的算法量化精度，我们首先对训练好的全精度权重做近似(没有量化激活或者重训练)，结果如表1和表2所示。注意到均匀量化和均衡量化是基于规则的，其目标并不在于最小化误差，因此这两种方法会得到差很多的结果。我们还在其他数据集上重复了上述实验，对于两种循环神经网络结构LSTM和GRU，结果都与此处相似。
Table 3 PTB数据集上多比特量化LSTM和GRU的测试PPW，其中均匀量化和均衡量化为现有论文中的结果，改进版贪婪法为我们自己实现的结果。
Table 4 WikiText-2数据集上多比特量化LSTM和GRU的测试PPW。
Table 5 Text-8数据集上多比特量化LSTM和GRU的测试PPW
我们还进行了权重和激活同时量化的实验，结果如表3、4和5所示。从中可以看到，本文提出的交替方向法明显好过现有其他量化方法。即使与表现最好的改进版贪婪法相比，交替方向法实现类似的精度大概可以少用一个比特。
我们还在CPU中实现了矩阵向量的二值乘法，其结果如表6所示。
Table 6 CPU中二值乘法与全精度乘法的时间比较
小节
在这个工作中，我们主要考虑神经网络的多比特量化压缩加速问题。我们发现，如果编码的实系数固定，那么离散的二值编码{-1,+1}可以通过二叉搜索树高效的求解。基于这个发现，我们相应地提出交替方向法。我们将该方法用于量化语言模型中的LSTM和GRU结构，与全精度模型相比，通过2比特量化，我们可以减少约16倍的内存消耗，以及在CPU上实现约6倍的真实推断加速，而只产生少量的准确率损失。通过3比特量化，该方法在准确率上可以实现几乎没有损失甚至超过原始模型，并减少约10.5倍的内存消耗，以及在CPU上实现约3倍的真实推断加速。这些结果都远远优于现有量化方法的结果。
如果您也有论文被国际会议录用或者对论文编译整理工作感兴趣，欢迎关注AI前线（ai-front），在后台留下联系方式，我们将与您联系，并进行更多交流！
