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