<mark id="oztn4"></mark>
0
雷鋒網 AI 科技評論按：伴隨著機器學習理論和技術的發展、以及機器學習作為一門學科有越來越多的人關注以及參與，機器學習的落地應用場景也越來越多、越來越多樣化。這兩年的熱門的應用大家都已非常熟悉，深度神經網絡+強化學習下圍棋的 AlphaGo，還有用深度神經網絡做語音生成的 WaveNet，都是在傳統方法研究已久但沒有什么突破性進展的領域引入深度學習，用全新的思路、全新的工具達到了天神下凡一般令人驚嘆的效果，稍加迭代更新以后更是盡善盡美。
近期，谷歌大腦也公開了一篇新的革命性論文，嘗試把機器學習運用在傳統上基于確定的規則和算法的數據庫系統中，并且還取得了很好的初步成果：對于真實數據的索引任務，神經網絡建立的索引可以比傳統的緩存優化 B 樹索引方法提高 70% 的速度，同時存儲空間還能節省一個數量級。包括 Jeff Dean 在內的作者們也討論并嘗試了如何用神經網絡承擔數據庫系統中更多不同的任務，他們覺得這是一個全新的、非常有潛力的研究和應用方向，很可能會影響未來的數據庫系統的設計理念。雷鋒網 AI 科技評論把這篇論文《The Case for Learned Index Structures》（聊一聊學習得到的索引架構）的部分內容介紹如下。
對于計算機系統來說，只要有高效訪問數據的需求，就可以建立一個索引結構。索引的思想發展到現在，也已經有了各種各樣的方法可以處理各種不同的訪問模式。舉例來說，對于范圍訪問（比如讀取某個時間段內的所有記錄），B 樹是最佳選擇；對于基于鍵值的查詢任務，哈希表方法的性能非常優秀；而如果要查詢記錄是否存在，Bloom Filter 就是多數時候的選擇。由于索引在數據庫系統以及其它一些應用中有著非常重要的作用，過去的十多年中各種索引方法就不斷地得到更新改進，各種新方法對內存、緩存以及 CPU 資源的使用也越來越高效。
不過，目前所有的索引方法都仍然是通用型的數據結構，它們都假設數據是以最糟糕的方式分布的，而沒有利用到真實數據中常常體現出的分布特點。比如，如果目標是構建一個高度定制化的系統，用于固定長度的、連續的整型（比如 1 一直到 1 億這樣）鍵值的存儲和查詢，這種時候用傳統的 B 樹對鍵值建立索引就不是一種好方法，因為鍵值自己就可以看作偏移量，對于查找任意鍵值、或者查找某個范圍鍵值起始位置的任務，時間復雜度反倒從 O(log n) 提高到 了 O(1)；同樣，把鍵值自己看作偏移量的話，索引所用的內存大小也可以從 O(n) 減少到 O(1)。可能有點驚人的是，其它的數據分布模式也都可以找到各自適合的優化方式。換個角度說，如果知道了數據的確切分布，不管數據庫現在用的是什么樣的索引方法，幾乎都還可以做進一步的高度優化。
當然了，多數實際應用場景中的數據都不一定完美符合某個已知的數據分布，并且，如果為每一種使用狀況都分別構建專用的解決方案的話，需要投入的成本也太高了。不過，這篇文章的作者們（包括 Jeff Dean 在內的四位谷歌研究員以及一位當時在谷歌訪問的 MIT 學者）認為機器學習現在帶來了一個全新的機會，它學到的模型可以反映數據的內在聯系和分布模式。在此基礎之上還可以進一步自動生成專用的索引結構，作者們稱之為「學習得到的索引」（learned indexes），同時工程方面的成本也較低。
在這篇論文中，作者們探究了機器學習學到的模型（包括神經網絡），能否用來替代 B 樹、Bloom Filter 等這樣的傳統索引結構。這件事可能有點反直覺，因為傳統索引方法往往需要有確定的語義保障，而機器學習通常提供不了這個；另外，神經網絡雖然是最強大的一類機器學習模型，但同時人們也傳統上認為評估它們效果所需的成本太高。不過作者們提出，這些明顯的困難在實際中并沒有看起來那么嚴重，而且恰恰相反，作者們提出的學習模型的方法很有潛力可以帶來明顯的好處，尤其是在為大規模矩陣運算設計的下一代硬件上。
具體來說，在語義保障方面，現代索引方法很大程度上已經是一些學到的模型，在這種現狀下，把現有的模型替換成新的模型其實已經是一件非常簡單直接的事情了，包括替換成神經網絡也是一樣。比如，一個 B 樹索引可以看作是這樣一個模型：它接收一個鍵值作為輸入，然后預測對應的數據記錄的位置；Bloom Filter 可以看作一個二值分類器，給定一個鍵值以后它可以預測這個鍵值是否存在。當然了，這其中也有一些細微但是非常重要的區別，比如現在的 Bloom Filter 可能會出現誤報為真的情況，但不會出現誤報為假。不過，這篇論文稍后將會展示出，借助新的學習技巧和/或簡單的輔助數據結構，這些區別都是有可能得到解決的。
在性能方面，作者們觀察到如今的 CPU 全都有強大的 SIMD（單指令多數據）計算能力，而且他們也推測許多筆記本電腦和手機很快都會有 GPU 或者 TPU。他們還推測，CPU-SIMD/GPU/TPU 都會變得越來越強大，因為相比通用指令集來說，這些處理器都能夠更簡便地擴大神經網絡需要的非常有限的一部分數學運算的運算規模。那么運行神經網絡所需的高計算力消耗未來就可能終于變得不值一提。舉例來說，NVIDIA GPU 和谷歌 TPU 都可以在單個時鐘循環內完成數千、甚至數萬次神經網絡的計算操作。更進一步地，已經有人指出，到 2025 年時 GPU 的速度還能再提升一千倍，到那時摩爾定律對于 CPU 已經基本失效了。只要把分支數量可觀的索引結構替換為神經網絡，數據庫系統就可以從這樣的硬件發展趨勢中受益。
這里我們重點介紹一下論文中神經網絡學習得到的索引與 B 樹索引之間的對比。
數據庫的索引結構其實已經是一種模型，因為索引的作用就是給定鍵值之后「預測」這條記錄所在的位置。假設這樣一種情況，用 B 樹對內存中的分析型數據庫（也就是只讀數據庫）的有序主鍵建立索引，如下圖 1(a)。在這種情況下，B 樹索引提供了從要查詢的鍵值到各條記錄組成的有序數組中的一個位置的映射，同時能夠保證記錄數組中這個位置的鍵值和查詢的鍵值相等或者大于查詢的鍵值。值得一提的是，數據需要是有序的才能進行范圍訪問請求；并且，這種總體概念同樣適用于二級索引，其中最下層是<鍵值，指針>對組成的列表，其中的鍵值就是被索引的屬性，指針指向的就是數據記錄。
為了讓索引比較有效率，通常的做法中并不會對有序記錄數組中的每一個鍵值都做索引，而是每隔 n 個記錄做一個索引，這也就是每個分頁中的第一個鍵值。這樣可以顯著減小索引中需要存儲的數據量，同時性能下降非常輕微。正因為這樣，B 樹就是一個模型，用機器學習的術語的話可以把它稱為回歸樹（regression tree）：它把一個鍵值映射到一個位置，它帶有最大和最小誤差（這里的最小誤差為 0，最大誤差是分頁大小），同時只要這個值存在，就可以確保在這個范圍內找到它。
那么接下來，我們就可以把這個索引機制用其它類型的機器學習模型替換掉，包括可以用深度學習模型替換，只要它們也同樣可以提供類似的保證，確保數據只要存在就能在最小誤差和最大誤差組成的范圍之間找到它。
第一眼看上去似乎很難找到有什么類型的機器學習模型可以提供這樣的誤差保證機制，但是它實際上出奇地容易。B 樹其實只能對存儲了的數據提供這種保證，而不能對所有可能的數據提供這樣的保證。對于新增加的數據，B 樹需要重新平衡——用機器學習的術語來說就是「重新訓練」——之后才能提供同樣的誤差保證。這就可以大幅度簡化問題：要提供保證的最小和最大誤差就是模型對于訓練數據（存儲的數據）的最大誤差。也就是說只需要做一件事，對每一個鍵值執行機器學習模型，然后記住位置預測時最糟糕的向上偏離值和向下偏離值。給定了一個鍵值以后，模型就會對在哪里找到這條數據做出預測；如果這個鍵值存在，那它就一定在預測的最小誤差和最大誤差定義出的范圍內。接下來就可以把 B 樹替換為任意一個具體類型的回歸模型，包括線性回歸或者神經網絡，如上圖 1(b) 所示。
在正式把 B 樹更換為學習得到的索引之前，還是有一些技術方面的挑戰需要解決的。比如，B 樹對于插入和查詢操作的計算成本是在有限的范圍內的，而且能夠非常好地利用緩存；同時，B 樹可以把鍵值映射到并不連續映射在內存或者磁盤中的分頁中；進一步地，如果要查詢的鍵值在數據庫中不存在，這樣的模型返回的位置可能會在最小/最大誤差范圍之外，如果這不會單調地增加模型大小的話。所有這些特點都是有趣的挑戰和研究課題。機器學習，尤其是神經網絡有這樣一種魔力，就是它們可以學習到許多種不同的數據分布、數據混合以及其它一些數據的模式以及奇怪的特點。那么，這里還剩下的明顯的挑戰，就是在模型的復雜度和準確度之間找到平衡，而作者們也提出了一些可能的解決方案。
一個樸素的全連接網絡表現并不好
作者們首先嘗試了一個樸素的方法，用 TensorFlow + Python 實現了一個具有兩層全連接層、每層 32 個神經元的神經網絡。用它為 200MB 的 web 服務器日志記錄做二級索引，把時間作為輸入特征、把位置作為網絡預測的標簽進行訓練和測試。這樣得到的模型執行一次就需要花費 8 萬納秒；相比之下 B 樹只需要 300 納秒時間，而且在鍵值空間中搜索的速度也要更快。
作者們認為這是由于以下幾點原因：
TensorFlow 平臺本身的設計目標是高效運行較大的模型，所以運行開銷很大，尤其是搭配 Python 使用時；
B 樹，或者決策樹模型，總體來說逐次切分數據空間時非常高效；其它模型估計數據存在的總體累積概率密度的能力要更好，但是到了最后數據空間不大（統計規律開始變得不明顯）時，速度就會變慢；
典型的機器學習優化目標是優化平均誤差。然而對于索引任務，實際上更重要的是具體的最大誤差和最小誤差值；
B 樹的緩存效率非常高，它總會緩存頂端的節點，然后再緩存一些其它需要的分頁。相比之下神經網絡就需要從內存中讀取所有的權值才能完成一次運算。
為了克服這幾個問題，展現出理論上可行的想法的實際可行性，作者們專門開發了這樣幾個方法幫助實現學習得到的索引。
Learning Index Framework
作者們編寫了 Learning Index Framework，索引學習框架 LIF，可以把它看作一個索引生成系統：給定一種索引規格，LIF 就會生成不同的索引配置，并且優化它們、自動測試它們。LIF 可以借助 TensorFlow 中實現的更復雜的模型，邊運行邊學習簡單的模型；同時它的推理過程并不依靠 TensorFlow，它會從學到的模型構建出高效的 C++編譯版本，這樣推理時可以大幅減少不必要的計算開銷，運行時間縮減到了30納秒級別。
The Recursive Model Index
Recursive model index，遞歸模型索引 RMI 是為了解決前面提到的數據空間變小以后模型預測能力變差的問題。舉例來說，從 100M 條記錄中尋找數據時，最大最小誤差如果想要縮小到幾百的數量級，只憑單個模型是非常難的；但同時，把誤差縮小到 10k 的數量級，用這一個模型替代 B 樹的最上兩層就要簡單得多，用簡單的模型就可以做到。同樣，下一層的模型只需要把誤差從 10k 縮小到幾百，由于它只需要關注數據的一個子集，所以也是一個較為簡單的問題。
這樣，作者們提出了遞歸模型索引 RMI。如圖，作者們設計了層級化的網絡結構，其中包含許多個模型，每一層中的模型都接收鍵值作為輸入，然后據此選擇下一層的模型，直到最后一層的模型對位置做出預測。在這里，每一個模型都可以看作是對鍵值空間的某一部分負責，在逐層選擇的過程中逐漸降低了預測誤差。作者們也證明了這樣的模型是可以逐層訓練，最終得到完整的網絡的。
但同時值得注意的是，RMI 不是樹模型。正如上圖所示，不同的上層模型可以選擇同一個下層模型；并且，其中的每個模型覆蓋的數據范圍并不是像 B 樹那樣固定的；最后，由于預測是靠不同模型間的選擇完成的，所以對這個過程的理解不應該看作是“對位置的預測逐漸精確”，而是“逐次選擇了對這個鍵值具有更好知識的模型”。
這種模型結構有這么幾種好處：
數據分布的總體形狀是更容易學的，這樣的模型結構就利用了這個規律；
這樣的模型可以高效地把數據空間分割成了多個小空間，從而用更少的操作提高了最后數據空間很小時的預測精度；
網絡中不同的層之間不需要任何搜索操作。比如，模型 1.1 的輸出直接就選擇出了下一層的模型 1.2。這不僅減少了管理整個結構所需的指令的數目，而且還可以把整個索引表達成可以在 TPU/GPU 上完成的矩陣相乘操作；
這樣的結構可以允許混用不同的模型。比如最上層的模型可以是使用 ReLU 激活函數的神經網絡，因為它們通常可以學到很多種不同的復雜數據分布；底層的模型就可以是數千個簡單的線性回歸模型，因為它們需要的空間和執行時間都很少。
混用模型的網絡和它的訓練
這篇論文中作者們就編寫算法訓練了一個不同模型組成的 RMI 網絡。具體來說，其中的單個模型可以是帶有 0 到 2 層全連接層和 ReLU 激活函數的簡單神經網絡，每層最大寬度為 32 個神經元；也可以是 B 樹，也就是決策樹。想要其它類型的模型也可以，這里作者們先用了這兩類。
根據作者們的設計，每個模型的標準最小/最大誤差會存儲在最下面一層的模型中，這種做法帶來的好處是可以根據使用的模型為每個鍵值單獨設定搜索空間的大小。作者們也為混用模型網絡中設計了一個替換功能，一開始網絡中所有模型都是神經網絡，而如果某處神經網絡模型的絕對最小/最大誤差高于某個閾值的話，訓練算法就會把這個神經網絡模型替換成 B 樹。這樣實際上也就是設定了這個混用模型網絡的表現的下限：對于最糟糕的、無法學習的數據分布，混用模型網絡就基本上是一個 B 樹模型；而在除此之外的情況下，模型都理應有更好的表現。
作者們在幾個數據集上把學到的索引模型和 B 樹模型進行了對比。B 樹模型選用了不同的分頁大小；而學到的索引模型選用了一個 2 層的 RMI 模型，測試中也給出了不同的第二階段模型搜索數量大小的表現。對于模型結構，第二階段的模型實際上在結構最簡單（0 個全連接層），基本就是線性模型的時候有最好的表現；這也并不奇怪，因為搜索空間已經減小之后，運行更復雜的模型反倒不劃算。整個學到的索引模型用 LIF 編譯之后，運行在不帶有 GPU/TPU 的英特爾 E5 CPU 上。
Weblogs 數據集包含近幾年中某個大學網站的 200M 條訪問記錄，每條記錄都有不同的時間戳。這個數據集幾乎可以算是最糟糕的情況了，因為它的數據模式會受到課程規劃、周末、節假日、午餐、學院活動、放假時間等等因素的影響，非常難以學習。
而實際測試結果顯示出，與 B 樹相比，學到的索引模型不僅總是更快，消耗的空間也最多可以節省 99%，也就是兩個數量級。
地圖數據集包含了大約 200M 條用戶添加的全世界的地標信息。這個數據集的數據就更線性、不規律性更小。所以學習得到的索引相比 Weblogs 數據集中更好的表現，不僅可以提速超過 60%、大小減小最多 99%，最大預測誤差也減小了很多。
這樣的結果不僅有力地驗證了論文開頭作者們提出的「當數據有規律時，機器學習的方法可以優化索引效率」的猜想，而且初步實驗的效果就出人意料地好。
值得說明的是，作者們并沒有打算用學到的索引完全取代傳統的索引架構。實際上，他們是想要指出一種新的建立索引方式，它應當是現有研究的補充，而且為已經有幾十年歷史的數據庫索引領域開啟了一個全新的研究方向（當然這也還有待更多后續研究和討論）。
這篇論文中作者們的研究重點在于純讀取負載（鍵值查找、數據定位、存在性搜索），同時也大概討論了如何把這種思路拓展到重寫入負載的系統的加速上。作者們也進一步簡要描述了如何用同樣的思想把數據庫系統的其它組件和操作也做個替換，包括排序和合并。如果這些研究的進展順利的話，這可能會發展成脫離現有數據庫系統模式的新做法，高維度索引、學習數據庫操作算法、GPU/TPU 加速數據庫操作都會是有意思而且有深遠實用意義的研究目標。
總的來說，作者們表明了機器學習學到的模型有潛力在現有的頂級數據庫索引方法基礎上繼續帶來顯著的提高，這不僅是數據庫相關技術研究的新方向，更是機器學習在又一個新領域拓土開疆。
論文地址：https://arxiv.org/abs/1712.01208
雷鋒網 AI 科技評論編譯
相關文章：
醫學領域的AI除了看醫療影像還能做什么？谷歌帶來一個新答案：幫醫生寫醫療檔案
Jeff Dean兩年AMA全盤點：26個關于谷歌大腦和機器學習未來的問題（上）
效果超過SGD和Adam，谷歌大腦的「神經網絡優化器搜索」自動找到更好的訓練優化器
