基于二值化網絡的學習型布隆過濾器優化研究

楊 斐，崔超遠

（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%，這主要是由于二值化網絡性能的下降。二值化學習型布隆過濾器使學習型布隆過濾器更實用。隨著二值化網絡優化技術的不斷發展，二值化學習型布隆過濾器的優勢將會越來越突出。