1. 背景
2018年，谷歌AI部門在SIGMOD會議（資料庫領域的頂會）上發表的一篇exploratory research paper，論文名為《The Case for Learned Index Structures》，值得一提的是谷歌AI部門主要負責人Jeffrey Dean挂名其中，使得論文引起學術界和工業界的廣泛關注。
“AI 與計算機系統架構”
Jeff Dean 等人從 2018 年 3 月開始發起 SysML 會議，聚焦于機器學習 / 深度學習相關的硬體基礎設施和計算機系統。那麼 AI 到底能夠給計算機系統架構帶來哪些新的機會？“阿裡計算平台掌門人”賈揚清認為可以從以下兩個方面來看。
Jeff Dean 在提到 SysML 的時候，其實提過這樣一個概念，就是 Machine Learning for Systems and Systems for Machine Learning。今天我們做的更多的是 System for Machine Learning，指的是當機器學習有這樣一個需求的時候，我們怎麼去建構一個系統來滿足它的需求。另一方面，在計算機系統建構的過程中，我們還可以考慮怎麼通過機器學習的方法跟資料驅動的方法來優化和設計系統，解決原來系統設計對人的經驗的依賴問題，這是 Machine Learning for System 可以解決的事情，不過目前這方面還處于相對比較早期的探索階段，也是人工智能接下來還需要突破的瓶頸之一。
好了，言歸正傳。Learned Index的論文主要講的是利用Machine Learning優化資料索引結構的性能，如空間性能、時間性能等，即Machine Learning for System 。而本文主要講的是論文中優化Bloom filter的這部分（想閱讀更多的内容見參考文獻），利用Machine Learning 降低Bloom filter的空間開銷。
2. Motivation
上一篇博文我已經介紹了Bloom filter作為一種空間高效的資料索引結構，經常被資料庫用于測試元素是否是某集合的成員。通常用于測試某些cold storage(例如disk)中是否存在某個元素。雖然布盧姆過濾器具有很高的空間效率，但它仍然占用大量記憶體。例如，對于10億條記錄，大約需要1.76Gigabytes的記憶體；對于0.01%的FPR(false positive rate，誤判率)，我們大約需要2.23 Gigabytes的記憶體。是以，進一步降低Bloom filter的空間開銷顯得尤為重要。
3. 單一模型
Bloom filter視作二進制分類問題：Bloom filter本身是用來判斷某個元素是否屬于某集合，可以将這個過程視作一個二進制機率分類任務。也就是說，可以學習一個模型f(x)，它可以預測待查詢的元素是“屬于集合”還是“不屬于集合”。例如，對于字元串，我們可以訓練遞歸神經網絡(RNN)或卷積神經網絡(CNN)。但是，對于RNN或者CNN來說，其預測結果必定存在誤差，即fpr(false positive rate)
0且fnr(false negative rate)
0。如此，直接把Bloom filter當作一個二進制分類任務進行處理，顯然不具有任何意義，因為Bloom filter存在的意義就是fnr=0，使得“不屬于”的判定結果為真。
顯然，單一模型并不能解決問題！！！
4. 複合模型
Bloom filter與二進制分類相結合：為了確定學習化的Bloom filter與标準的Bloom filter具有一樣的特性，即①fnr=0；②可設定預期的fpr大小，進而保證Bloom filter索引的品質。是以，文章提出通過設定門檻值的方法來保證fnr=0，并且使用者可以自定義預期的fpr。
（1）fnr=0的保證：如下圖所示，Model為一個RNN或者CNN模型f(x)，f(x)為模型預測的結果值（f(x)
[0,1]）。通過設定門檻值
，當f(x)
時，我們可以認為目前元素key在集合中（允許fpr
0）；當f(x)
時，我們可以認為目前元素key不在集合中（fnr
0，但不被允許），此時我們得到一個元素均滿足f(x)
的集合K，将集合K映射為一個Bloom filter，我們稱之為overflow Bloom filter，當再次查詢元素key的f(x)
時，我們通過overflow Bloom filter來判定key是否屬于集合（如下圖右半部分所示，通過overflow Bloom filter判定的結果沒有false negative，即fnr=0）。這樣的複合模型設計使得fnr=0得到的保證，複合模型命名為Learned Bloom filter。
（2）可設定預期的fpr大小：集合
表示Learned Bloom filter訓練前的“不屬于目前集合”的元素的整體，則我們可以在訓練完Model（上圖中左半部分）并确定門檻值
之後計算Model的FPR
大小，如下所示：
overflow Bloom filter的預期誤判率設定為FPRb，則整體的複合模型的預期誤判率設定為FPRp，則必須滿足：
為了簡化結果（右邊取等号是為了最小化空間開銷），我們取：
則我們可以通過設定門檻值
來決定整體的預期誤判率FPRp（同時也包括決定複合模型的FPR
，FPRb）。
5. 實驗結果
從實驗結果我們可以看出，Learned Bloom filter在fpr允許的大範圍内節省了原有Bloom filter占據的記憶體空間開銷（圖中的W和E是RNN的參數）。
Learned Bloom filter占用的記憶體空間 = RNN模型的參數記憶體大小 + overflow Bloom filter的記憶體大小；
6. 總結
我們通過以上分析可以看出，Machine Learning現階段還很難取代傳統的資料索引結構，取而代之的是複合型的模型。但是，Bloom filter的一大特點就是性能快，而Learned Bloom filter的查找時間顯然要比傳統的Bloom filter大上兩三個數量級（本人實驗已驗證），是以文章裡也提及了Learned Bloom filter的适用場景，即在使用者通路某些例如磁盤時，允許較大的延時。以下為二者之間的性能對比：
參考文獻：
[1] Kraska et. al, "The Case for Learned Index Structures", https://dl.acm.org/citation.cfm?id=3196909, 2018.