杨 斐，崔超远

（1.中国科学院合肥物质科学研究院智能机械研究所，安徽合肥 230031；2.中国科学技术大学，安徽合肥 230026）

布隆过滤器(Bloom Filter)是一种用于以时间空间高效方式解决集合存在性问题的概率数据结构。布隆过滤器广泛应用于垃圾邮件过滤、拼写检查、冗余项检测等。布隆过滤器以其优雅、空间高效、易于计算、容易实现的特点被广泛应用。数据库管理系统(Database Management System)经常使用布隆过滤器作为一种存在索引，Hadoop 中提供了布隆过滤器的实现[1]。

研究认为，索引也可以看作模型，文献[2]中训练了一个可以预测查询x是键或非键的模型f。给定一个键，学习型布隆过滤器(Learned Bloom Filter,LBF)将其输入列模型并计算结果，如果模型给出的结论是键不在其中，那么检查后备布隆过滤器(Backup Bloom Filter)来判断键是否在学习型布隆过滤器中；如果模型给出的结论是键在其中，那么学习型布隆过滤器返回肯定的结果。这项工作掀起了利用机器学习技术优化经典索引结构的浪潮[3-6]。尽管布隆过滤器是空间高效的，但学习型布隆过滤器可以在进一步降低占用空间的同时维持相同的假正例率。学习型布隆过滤器使用模型作为预过滤器来减少存储在后备布隆过滤器中键的数量。学习型布隆过滤器的另外一个特点是显著增加计算开销。

随着机器学习技术的发展，神经网络优化技术得到了不断的发展。用于提高神经网络推理速度的方法可以分为基于软件的方法与基于硬件的方法。基于硬件的方法指的是使用更适合并行处理的硬件，比如GPU（Graphics Processing Unit）。GPU可以将神经网络的执行速度提高10～100 倍，但是GPU 是昂贵且高能耗的。基于软件的方法指的是减少神经网络推理所需的操作数量。网络量化可以产生紧凑的模型，是一种有前途且快速的解决方案[7]。最极端的量化是二值化，二值化网络指的是权重和激活为二值的网络[8]。作为一种基于软件的方式，二值化网络在内存压缩、操作数减少、泛化能力提高等方面性能卓著[9]。

文中提出使用二值化网络来优化学习型布隆过滤器，可以称之为二值化学习型布隆过滤器(Binarized Learned Bloom Filter)。此外，二值化学习型布隆过滤器可以与其他学习型布隆过滤器优化技术相结合，比如三明治[10]。之前关于学习型布隆过滤器的研究只注重模型大小，忽略了计算开销的增加。文中研究了学习型布隆过滤器带来的总体空间大小和计算时间的改变，探讨了二值化学习型布隆过滤器就总体空间大小和推理时间方面的优化效果。

1 学习型布隆过滤器与布隆过滤器

1.1 布隆过滤器

布隆过滤器是一种用于解决集合存在性问题的概率数据结构。布隆过滤器的优势在于其卓越的时间和空间性能。布隆过滤器包含一个m位的位数组和k个相互独立的哈希函数。位数组的所有位用b(0),b(1),…,b(m-1)表示，全部初始化为0。k个哈希函数的输出分别使用h0(x),h1(x),…,hk-1(x)表示，范围为0～m-1。用S表示要存储到布隆过滤器中的键集合，要将元素x＇插入到布隆过滤器中，需将k个位b(h0(x＇)),b(h1(x＇)),…,b(hk-1(x＇)) 置为1。要判断一个元素x＇是否在布隆过滤器中，应检查k个位b(h0(x＇)),b(h1(x＇)),…,b(hk-1(x＇))是否全部为1。如果结果为真，则布隆过滤器给出键x＇可能在集合S中的结论，假正例率为ε；否则，布隆过滤器给出键x＇一定不在集合S中的结论。布隆过滤器的构造、插入和查询过程如图1 所示。

布隆过滤器的假正例率ε取决于存储的元素数量n和哈希函数数量k。p＇表示在向布隆过滤器中插入n个元素后一个位仍然为0 的概率。p＇与k、n、m的关系如式（1）所示：

用p表示e-kn/n，因此，假正例率ε与哈希函数数量k、元素数量n和位数组大小m之间的关系如式（2）所示：

对于给定的存储元素数量n，不同的m和k组合将会产生不同的假正例率。在哈希函数数量k和存储的元素数量n是固定的情况下，不难发现，m越大，假正例率ε越小。但是ε与k之间的关系并非如此，k越大，意味着发现不是1 的位的可能性越大；同时，意味着一个位被置为1 的可能性越大。

假正例率ε与k之间关系的变化趋势在不同的n和m组合下是相同的。在图2 中绘制了n=10 000,m=100 000 时假正例率ε随k变化的曲线。同时，假正例率ε与m之间关系的变化趋势在不同的n和k组合下也是相同的。在图2 中也绘制了n=10 000,k=7时ε随m变化的曲线。

对于给定的假正例率和存储的元素数量，最优的哈希函数数量和最小的位数组大小分别如式（3）和式（4）所示：

1.2 学习型布隆过滤器

学习型布隆过滤器将布隆过滤器看作一个二分类问题。在使用后备布隆过滤器检查之前，学习型布隆过滤器使用模型f来预测查询x存在与否[2]。使用数据集D={(xi,yi=1)|xi∈K}∪{(xi,yi=0)|xi∈U}来训练模型f。K指的是存储在布隆过滤器中的元素集合，U指的是不存在于布隆过滤器中的元素集合。模型经常有一个非零的假反例率，这使得模型不能完美替代布隆过滤器。因此，学习型布隆过滤器需要使用后备布隆过滤器来消除假反例。

学习型布隆过滤器的构造过程如下：首先，训练一个模型来区分键和非键。模型输出f(x) 越接近1，元素x是键的可能性就越大。之后在留出数据集H上调整阈值τ以实现目标假正例率。最后，将不满足f(x)≥τ的键插入后备布隆过滤器中。

学习型布隆过滤器的查询过程如下：给定一个查询x，计算f(x)。如果f(x)≥τ，则得出x是一个键的结论；如果f(x)＜τ，则基于后备布隆过滤器的输出给出结论。学习型布隆过滤器的构造和查询过程如图3 所示。

学习型布隆过滤器比布隆过滤器更空间高效是因为模型f的大小比布隆过滤器位数组小得多。学习型布隆过滤器的假正例来自模型f和后备布隆过滤器。分别使用符号FPRL、FPRM和FPRB表示学习型布隆过滤器的整体假正例率、模型的假正例率和后备布隆过滤器的假正例率，学习型布隆过滤器的假正例率由式（5）给出：

令FPRM=αp*且FPRB=βp*，则有：

如果α和β满足式（6）中的三个条件，则FPRL=p*(1-αβp*)＜p*。因此，如果要确保学习型布隆过滤器的假正例率不超过p*，只需要将模型的假正例率调整到小于αp*，并将后备布隆过滤器的假正例率调整到小于βp*。

2 二值化神经网络

神经网络模型在许多任务中都实现了先进的结果，比如目标检测[11]、机器翻译[12]等。更高性能的网络往往具有更深的层数及更多的参数量，一方面，深层网络性能指标更吸引人；另一方面，网络的计算开销巨大。GPU 可以将神经网络推理速度提升10～100 倍，但是GPU 昂贵且能耗高，尽管深层模型学习能力很强，但是这种能力可能没有被完全利用。

深度学习模型的大小和计算开销都远远超出了资源受限设备的能力。模型量化指的是将神经网络权重和激活的精度降低到16 位或8 位[13]。二值化网络代表了量化网络的极端情况，需要特殊的训练和优化策略[14]。二值化网络所占用空间为对应32位全精度网络的1/32。二值化网络在CPU 上的实际计算量可以减小为对应全精度网络的1/58[15]。

通常有两种二值化网络权重和激活函数的方法：确定性二值化和随机二值化。用于确定性二值化的函数如式（7）所示：

二值化网络层的定义如式（8）所示：

式中，δ代表激活函数。bkernel表示权值二值化使用的函数。binput表示层输入二值化使用的函数。f表示层操作（全连接或卷积）。用于将一个高精度的输入转换为量化输出的函数称为量化器。因此，bkernel和binput都是量化器。

网络二值化给网络训练带来了两个困难：①二值化函数的梯度几乎处处消失；②集合{-1,+1}中的权重无法吸收小的更新[13]。直通式估计器是这两个问题的解决方案。直通式估计器是常用的量化器，在前向传播过程中，可以用式（9）表示：

在反向传播中，直通式估计器忽略二值化，反向传播的梯度如式（10）所示：

通过使用量化器f(x)=x，二值化层也可以被转换为全精度层。在这种情况下，梯度处处为1。换句话说，全精度层对应着没有量化器的二值化层。

乘累加操作（Multiply And Accumulate，MAC）是深度神经网络推理中的主要操作。二值化网络将网络输入和权重量化为表示+1 或-1 的单个位。二值化网络使用逐位操作替换乘法。式（11）中枚举了权重激活乘积的可能组合。如果将式（11）中的-1 替换为0，则这个逻辑与同或的逻辑相同，可以将位打包为一个更大的数据类型以高效地执行逐位同或。

假定a和b均为包含8 个元素的数组，以数组a和b的逐元素乘加为例，计算数组a和b的逐元素乘累加需要8 次乘累加操作。假定数组a＇和b＇分别对应着数组a和b的二值化版本，将数组a＇和b＇中的-1替换为0，得到数组a″和b″。数组a＇和b＇的逐元素乘累加可以被替换为xnor 和popcnt，如式（12）所示：

因此，8 次乘累加操作可以减少到5 个指令（累加、乘、popcnt、异或、非）。即使数组a＇和b＇的长度扩展到32 位或64 位，5 条指令仍然可以完成它们的逐元素乘加。

3 实验数据

为了测试提出方法的性能，选择了恶意URL 识别任务，使用来自kaggle 的恶意和良性URL 数据集，这个数据集包含了450 176个不同的URL。数据集中有104 438个恶意URL，占总数的23.2%；其他345 738个URL 是良性的，占总数的76.8%。使用128×800=102 400 个良性URL 和89 600 个恶意URL 作为训练集D。训练集D中的12 800个良性URL用于留出数据集H。训练集D中的恶意URL 是要存储到学习型布隆过滤器和二值化学习型布隆过滤器中的元素，称为键集S。键集S和另外128×400=51 200 个良性URL 用作查询集Q。使用查询集Q测试二值化学习型布隆过滤器和学习型布隆过滤器的查询速度。

4 实验过程与结果

二值化网络结构和常规神经网络模型结构如图4 所示，其中二值化网络中二值化层的背景用灰色突出显示。

构造二值化学习型布隆过滤器和基准学习型布隆过滤器之前，首先训练二值化神经网络模型B 和常规神经网络模型R，嵌入矩阵包含91 个向量。有效的字符如下："abcdefghijklmnopqrstuvwxyzABCDEF GHIJKLMNOPQRSTUVWXYZ0123456789,;.!?:/_@#$%&*～+-=＜＞()[]{}"。字符首先被转化为其在有效字符组成的字符串中的位置。如果字符不在有效字符组成的字符串中，则将其置为＜NF＞。如果输出长度小于150，则使用＜PAD＞将其填充到长度为150。之后，使用这两个模型构造二值化学习型布隆过滤器和学习型布隆过滤器。使用C++实现二值化学习型布隆过滤器和学习型布隆过滤器，使用larq compute engine 完成神经网络模型的推理[16]。使用二值化神经网络模型和常规神经网络模型在留出数据集H和键集合S上进行预测，预测值的直方图如图5-8所示。

二值化神经网络模型B 的大小为8 624 字节，常规神经网络模型R 大小为26 964 字节，二值化网络模型比传统神经网络模型占用空间更少。在两个不同架构的平台上测试了不同假正例率下二值化学习型布隆过滤器和学习型布隆过滤器的平均查询时间和总体空间占用。两个不同平台分别为x86_64 桌面PC 和树莓派3B。x86_64 桌面PC 的CPU 是Intel Core i7 7700，内存规格为40 GB ddr4-2400，运行的操作系统为Ubuntu 20.04。树莓派3B 运行的操作系统为Manjaro 20.10，CPU 为BCM2837，内存规格为1 GB LPDDR2。测试过程中，Intel 处理器的超线程、睿频等功能被关闭，所有的数据都是连续三次运行后取的平均值。

不同假正例率下的二值化学习型布隆过滤器的总大小和查询时间如表1 所示。

表1 二值化学习型布隆过滤器的查询时间

与之相对应的不同假正例率下，学习型布隆过滤器的总大小和查询时间如表2 所示，查询时间同样在x86_64 PC 和树莓派上测量。

表2 学习型布隆过滤器的查询时间

5 讨论

对比表1 和表2 可以发现二值化学习型布隆过滤器和学习型布隆过滤器在总体空间占用、x86_64 PC 和树莓派上的查询时间等方面的差异。总空间占用大小指的是模型大小与后备布隆过滤器的位数组大小之和。

尽管二值化模型的大小比常规神经网络模型小的多，但是二值化学习型布隆过滤器的后备布隆过滤器比学习型布隆过滤器的后备布隆过滤器占用空间大的多，因此二值化学习型布隆过滤器总体空间占用有所增大。得益于二值化网络的计算高效性，二值化学习型布隆过滤器[17-18]的查询速度得到了较大的改善。与学习型布隆过滤器相比，二值化学习型布隆过滤器将总体空间占用增加了20%左右，将查询速度提高了1.5～2 倍。

6 结论

文中提出了一种优化学习型布隆过滤器的新方法。通过使用二值化网络作为预过滤器，二值化学习型布隆过滤器的计算开销显著降低。在不同的假正例率下，与学习型布隆过滤器相比，二值化学习型布隆过滤器增加了空间占用，但是显著减低了查询时间，不论是在x86_64 平台上还是在Arm64 平台上，二值化学习型布隆过滤器查询速度是学习型布隆过滤器的1.5～2 倍。但是，二值化学习型布隆过滤器占用的空间比学习型布隆过滤器多20%，这主要是由于二值化网络性能的下降。二值化学习型布隆过滤器使学习型布隆过滤器更实用。随着二值化网络优化技术的不断发展，二值化学习型布隆过滤器的优势将会越来越突出。