學習索引結構的一些案例——Jeff Dean在SystemML會議上發布的論文(中)
摘要: 原文： https://www.arxiv-vanity.com/papers/1712.01208/ 視頻：https://www.youtube.com/watch?v=PWv4ROEvqmk 本文是Google的Fellow，Jeff Dean，把機器學習應用到系統設計的論文，原文發布在SystemML會議上，我做了翻譯。
第一篇請參見：學習索引結構的一些案例——Jeff Dean在SystemML會議上發布的論文(上)
3. RM索引(Recursive-model，遞歸模型)
為了克服挑戰并探索模型作為索引替代或豐富的潛力，我們開發了學習索引框架 （LIF），遞歸模型索引（RMI）和基于標準誤差的搜索策略。 我們主要關注簡單的全連接神經網絡，因為它們的簡單性，但其他許多類型模型也是可能的。
3.1?學習索引框架（LIF）
LIF可以看作是一個索引合成系統或者說索引工廠; 給定一個索引規范， LIF生成不同的索引配置，優化它們并自動化測試它們。 雖然LIF可以即時學習簡單模型（例如，線性回歸模型），但它依賴于更復雜模型（例如NN）的Tensorflow。 但是，它從不使用Tensorflow進行推理。 相反，給定一個經過訓練的Tensorflow模型， LIF會自動從模型中提取所有權重，并根據模型規范在C ++中生成高效的索引結構。 雖然使用XLA的Tensorflow已經支持代碼編譯，但其重點主要放在大規模計算上，其中模型的執行時間量級是微秒或毫秒。 相比之下，我們的代碼生成專注于小型模型，因此必須消除Tensorflow管理大模型的開銷。 這里我們利用來自[ 21 ]的想法，它已經展示了如何避免Spark運行時不必要的開銷。 因此，我們能夠執行30納秒級的簡單模型。
3.2 遞歸模型索引
如第2.3節所述，構建替代B樹的替代學習模型的關鍵挑戰之一是最后一英里的準確性。 例如，使用單個模型把誤差從100M減少到幾百這個數量級是非常困難的。 同時，將誤差從100M降低到10K，例如100 * 100 = 10000的精度實現起來還簡單些，這樣就可以用簡單模型替換B-Tree的前兩層。 同樣的，將誤差從10k降低到100是一個更簡單的問題，因為模型只需要關注數據的一個子集。
基于這種觀察并受到專家們的共同努力[ 51]的啟發，我們提出了遞歸回歸模型（參見圖[3]）。 也就是說，我們構建了一個模型層次結構，其中模型的每個階段都將鍵(Key)作為輸入，并基于它選擇另一個模型，直到最終預測到位置。 更正式地說，對于我們的模型f(x) ，其中x是鍵， y∈ [ 0 ， N )位置，我們假設在階段?有M個模型。 我們在階段0訓練模型， $$f_0(x) ≈y$$ 。 因此，階段?中的模型k，可以寫成由$$f_?^{(k)}$$表示 ，并且被損失地訓練，整個誤差可以表示為如下公式：
注意，我們在這里使用這里的符號$$f_{?-1}(x)$$遞歸執行，這樣
總而言之，我們用迭代地訓練每個階段，誤差為$$L_?$$，以建立完整的模型。
圖3：分階段模型
理解多個不同模型的一種方法是，每個模型都會對關鍵位置進行一定的預測誤差，并使用預測來選擇下一個模型，該模型負責將鍵(Key)空間的某個區域以較低的誤差做出更好的預測。 然而，要注意，遞歸模型索引不是樹 。 如圖[ 3 ]所示，一個階段的不同模型可能會在下面的階段選擇相同的模型。 此外，每個模型并不一定像B-Tree那樣包括同樣數量的記錄（即頁面大小為100的B樹覆蓋100個或更少的記錄）。 4 最后，取決于所使用的模型，不同階段之間的預測不一定會被解釋為位置估計，而應該被視為挑選對某些鍵有更多認知的專家（另見[ 51 ] ）。
這種模型體系結構有幾個好處：(1)它利用了這一事實，即易于學習數據分布的整體形狀。(2)它的體系結構有效地將空間劃分為更小的子空間，就像B樹/決策樹那樣，通過更少的操作更容易地實現所需的“最后一英里”精度。 (3)在階段之間不需要搜索過程。 例如， 模型1.1的輸出y是一個偏移量，它可以直接用于在下一階段中選擇模型。 這不僅減少了管理數據結構的指令數量，而且還允許將整個索引表示為稀疏矩陣乘法跑到TPU / GPU上。
3.3 混合索引
遞歸模型索引的另一個優點是，我們能夠建立模型的混合。 例如，在頂層，一個小的ReLU神經網絡可能是最好的選擇，因為它們通常能夠學習大范圍的復雜數據分布，模型層次結構底部的模型可能有數千個簡單的線性回歸模型，因為它們在空間和執行時間都不貴。 此外，如果數據特別難以學習，我們甚至可以在最后階段使用傳統的B樹。
對于本文，我們只關注2種模型，簡單的神經網絡，具有0到2個完全連接的隱藏層和ReLU激活函數，以及多達32個神經元和B樹（也就是決策樹）的層寬度。 給定一個索引配置，它指定階段的數量和每個階段的模型數量作為一個數組，混合索引的端到端訓練按照算法1完成
Algorithm?1:?Hybrid?End-To-End?Training ????Input:?int?threshold,?int?stages[],?NN?complexity ????Data:?record?data[],?Model?index[][] ????Result:?trained?index ?????1?M?=?stages.size;?????2?tmp?records[][];?????3?tmp?records[1][1]?=?all?data;?????4?for?i??<-?1?to?M?do ?????5 for?j?<-?1?to?stages[i]?do ?????6 index[i][j]?=?new?NN?trained?on?tmp?records[i][j];?????7 if?i??threshold?then????14? index[M][j]?=?new?B-Tree?trained?on?tmp?records[M][j];????15?return?index;
從整個數據集（第3行）開始，它首先訓練頂級節點模型。 根據這個頂級節點模型的預測，它會從下一階段（第9行和第10行）中選取模型，并添加屬于該模型的所有鍵（第10行）。 最后，在混合指標的情況下，如果絕對最小/最大誤差高于預定義閾值（第11-14行），則通過用B樹代替NN模型來優化指數。
請注意，我們在最后階段為每個模型存儲標準誤差和最小誤差和最大誤差。 這樣做的好處是，我們可以根據每個鍵(Key)的使用模型單獨限制搜索空間。 此外，人們可能會想知道具體如何設置混合端到端訓練的各種參數，包括階段的數量和寬度，神經網絡配置（即隱藏層數和寬度）以及何時替換節點的閾值為一棵B樹。 通常，這些參數可以使用簡單的網格搜索進行優化。 此外，可以根據時間來限制搜索空間（找到這些參數）。 例如，我們發現閾值為128或256（B樹的典型頁面大小）效果很好。 此外，對于CPU，我們基本負擔不起1或2個完全連接的隱藏層以及每層8至128個神經元的神經網絡。 最后，考慮到模型的容量較低，可以用較小的數據樣本訓練較高層的階段的模型，這顯然加快了培訓過程。
請注意，混合索引允許我們將學習索引的最差情況性能與B樹的性能相關聯。 也就是說，在學習不到數據分布的情況下，所有模型都會被B-Trees自動替換，實際上是一個完整的B-Tree（階段之間有一些額外的開銷等等，但是性能是總體相似）。
3.4 搜索策略
要在葉頁中查找實際記錄，對于小數據量，無論是二進制搜索還是全量掃描通常都是最快的策略; 盡管（業內）作出了許多嘗試，但反復的結果表明， 其他搜索策略由于其額外的復雜性而沒有提供什么（如果有的話）益處[ 8 ]) ] 。 再一次，學習索引在這里也可能具有優勢：模型實際上預測了鍵(Key)的位置，這可能更接近值記錄(Value)的實際位置，而用最小/最大誤差會差的更遠些。 這就是說，如果我們可以利用這樣一個事實，即在位置估計最小誤差和最大誤差范圍內，我們對位置進行了良好估計，那么我們可能能夠找到記錄（或<=查找鍵的鍵）比傳統的二進制搜索更快。 因此我們制定了幾種搜索策略。
模型二進制搜索：我們的默認搜索策略，和傳統的二分搜索策略的唯一區別在于，把第一個中間點設為模型預測的值。
偏見搜索：這種搜索策略修改了我們的模型二分搜索，在每次迭代中不會平均分割從中間點到左側和右側的距離。 相反，新中間值取決于最后階段的模型的輸出的標準偏差σ 。 例如，如果確定鍵(Key)大于中間值 ，則將新中間值設置為?min(middle+σ,(middle+right)/2)。
偏見四元搜索：最后，我們開發了一種新的搜索策略，在任何迭代中都不會選擇一個新的中間值來進行二分搜索，而是用了三個新的數據點，即所謂的四元搜索。 研究人員過去嘗試四元搜索的主要原因是因為它可以提供更好的預取行為。 也就是說，首先計算三個“中間”點，由使用CPU intrinsics來計算。 之后才會測試不同的“中間”點，并根據結果進行搜索的下一次迭代，非常類似于二分查找。 如果CPU能夠從主存儲器(Memory)中并行獲取多個數據地址，那么這種策略可能更好，但據報道實際上這種策略大部分與二進制搜索相同[ 8 ] 。 然而，再次有一個更好的位置估計可能會有所幫助：也就是說，我們將我們最初的三個四元搜索中點定義為pos - σ ， pos ， pos + σ 。 我們假設，大部分預測都是準確的，首先關注位置估計，然后繼續傳統的四元搜索。
3.5 索引字符串
我們主要關注索引真正有值記錄(Value)的鍵(Key)，但許多數據庫依賴索引字符串，幸運的是，有不少重要的機器學習研究聚焦在字符串建模上。 和以前一樣，我們需要設計一個高效但有表現力的字符串模型。 對字符串做好這個設計會帶來許多獨特的挑戰。
第一個設計考慮是如何將字符串轉換為模型的特征，通常稱為標記化。 為了簡單和高效，我們認為n長度的字符串是長度為$$x∈R^n$$的特征向量，其中$$x_i$$是第i位的字符的ASCII十進制值（或者取決于字符串的Unicode十進制值）。 此外，如果所有輸入的尺寸相同，大多數ML模型的運行效率會更高。 因此，我們將設置最大輸入長度N。 由于數據按字典順序排序，我們將在標記化之前將鍵截斷為長度N. 對于長度為n < N的字符串，我們為i > n設置$$x_i = 0$$ 。
為了提高效率，我們通常采用與我們針對數據特征相似的建模方法。 我們學習了一個相對較小的前饋神經網絡的層次結構。 一個區別是輸入不是一個單一的實數值x，而是一個向量x?。 線性模型w?x + b隨著輸入長度N線性地增加乘法和加法的計算數量。 前饋神經網絡，帶有一個寬度為h的隱藏層，也會擴展到O(hN)乘法和加法計算數量。（在與N無關的更深層網絡中可能會有額外的復雜性）。
這種方法有一些有趣的特性，表明了設計字符串CDF的一般ML模型的困難。 如果我們考慮長度為三的八個字符串，字符串里面的字符是[0,8) ，那么我們可以容易地對位置建模為 $$4 x_0 + 2 x_1 + x _2^5$$ 。 但是，如果我們看看Unix字典的編碼，我們會發現數據更加的復雜。 以“s”以“e”開頭的單詞是其他單詞的三倍，這樣甚至對單詞里面的第一個字符就沒法線性建模。 此外，字符之間存在相互作用 - 大約10％以“s”開頭的單詞以“sh”開頭，而以“e”開頭的單詞只有0.1％以“eh”開頭. DNN算法，如果足夠寬或足夠深，可以成功地對這些相互作用進行建模，更常見的是，遞歸神經網絡（RNN）在建模文本中顯示出非常成功。
最終，我們相信未來會有相當好的研究可以優化字符串的學習索引。 例如，我們可以輕松想象其他標記化算法。 在字符串標記化的自然語言處理方面有大量研究將字符串分解為ML模型中更有用的部分，例如機器翻譯中的字詞[ 59] 。 此外，還有大量關于特征選擇的研究選擇最有用的特征子集，從而限制模型需要處理的特征的數量。 此外，GPU和TPU需要相對較大的模型，因此可以無縫擴展字符串長度增加的場景，及許多更復雜的模型體系結構（例如遞歸和卷積神經網絡）中。
3.6結果
為了將學習指標與B樹進行比較，我們在3個實際數據集上創建了4個二級索引：（1）Weblogs，（2）地圖數據集[ 46]和（3）web文檔以及1個合成數據集（4）正態對數。 Weblogs數據集包含200 M日志條目，是多年來對主要大學網站的每個web請求，并對唯一時間戳進行主索引。 該數據集對于學習索引來說幾乎是一種最壞的情況，因為它包含由課程安排，周末假期，午餐休息，部門活動，學期休息等引起的非常復雜的時間模式，這是眾所周知的難以學習的。 對于地圖數據集，我們將世界各地≈200M用戶維護特征（例如道路，博物館，咖啡店）的經度編入索引。 不出所料，位置的經度相對線性，并且比weblog數據集的不規則性更少。 web文檔數據集由大型互聯網公司的真實產品組成部分的大型網絡索引的10 M個非連續文檔ID組成。 最后，為了測試索引如何處理重尾分布，我們生成了一個從μ = 0和σ = 2的對數正態分布中抽取的190M獨特值的綜合數據集。 這些值被放大到整數1Billon。 這些數據當然是高度非線性的，這使得CDF使用神經網絡學習更加困難。
對于所有數據集，我們使用不同頁面大小的B樹和不同的第二階段大小（即10k，50k，100k和200k模型數量）的RMI學習索引進行比較。 我們的B樹實現類似于stx :: btree，但做了進一步的行緩存優化，在一個針對FAST的微基準[ 36]對比測試中性能很強，在這個測試中把我們的B-樹和一個把SIMD優化用的出神入化的B樹作比較，跑起來差不多。我們使用簡單的網格搜索，基于簡單模型來調整兩階段模型。 也就是說，我們只嘗試了具有零到兩個隱藏層的神經網絡和層數為4到32個節點的神經網絡。 一般而言，我們發現，對于第一階段而言，簡單的（0隱藏層）到半復雜（2隱藏層，8或16寬）模型效果最好。 對于第二階段來說，它變成了我們的簡單（0隱藏層），它們基本上是線性模型，具有最佳性能。 這并不令人驚訝，因為對于最后一英里來說，執行復雜模型往往是不值得的，線性模型可以被最優學習。最后，我們所有學習的索引模型都使用LIF進行編譯，并且我們只顯示具有32GB RAM的Intel-E5 CPU上性能最佳的模型的數字， 而不使用 GPU / TPU，進行超過30M次的查找，重復4次。
加載時間：雖然本文的重點不在加載或插入時間，但應該注意的是，大多數模型可以訓練得相當快。 例如，如果在C ++中實現，那么無需隱藏層的模型可以在幾秒鐘內在超過200M條記錄上進行訓練。 但是，對于更復雜的模型，我們選擇使用Tensorflow，由于其開銷，花費了更長的時間。然而，我們相信我們可以相對較快地對超參數空間進行網格搜索，大約需要分鐘數量級跑簡單模型。 此外，可以使用諸如[ 52 ]之類的自動調整技術來進一步縮短查找最佳索引配置所需的時間。
圖4：地圖數據：學習索引與B-Tree
圖5： Web日志數據：學習索引與B-Tree
圖6：正態分布的對數數據集：學習索引與B-Tree
圖[4]，圖[5]和圖[6]分別顯示了兩個真實世界整數數據集（地圖和博客）和合成數據（對數正態數據）的結果。 作為主要指標，我們將總查找時間分解為模型執行（B樹遍歷或ML模型）和本地搜索時間（例如，在B樹葉子頁面中查找鍵(Key)）。 另外，我們記錄了索引結構的大小（不包括排序數組的大小），空間節省和模型誤差及其誤差方差。 模型誤差是最后階段所有模型的平均標準誤差，而誤差方差則表明這些標準誤差在模型之間有多大變化。 請注意，對于B-Tree而言，由于沒有階段，所以它始終是一個取決于頁面大小的固定誤差。 加速和大小列中的顏色編碼指示索引相對于頁面大小為128的高速緩存優化的B樹索引的基線有多快或多慢（更大或更小）。
可以看出，在幾乎所有配置中，學習索引比B樹要快，速度提高了3 倍 ，并且達到了數量級的更小。 當然，B樹可以以CPU時間為代價進一步壓縮以進行解壓縮。 然而，大多數優化不僅是正交的（可以用在神經網絡上），而且對于神經網絡來說，存在更多的壓縮潛力。 例如，神經網絡可以通過使用4或8位整數而不是32或64位浮點值來表示模型參數（一種稱為量化的過程）進行壓縮。 與B樹壓縮技術相反，這實際上可以進一步加速計算。
有趣的是，四元搜索僅對某些數據集有幫助。 例如，它對weblog和log-normal數據集有一點幫助，但對地圖數據集沒有幫助。 我們沒有報告偏見搜索和B樹，或者不同搜索策略的結果差異，因為它們沒有為數字數據集提供任何好處。 值得注意的是，模型的準確性也有很大差異。 對于合成數據集和博客數據的來說，誤差要高得多，這會影響搜索時間。 作為比較，我們搞了一個學習索引，有更復雜的第一階段模型（“學習索引復合體”），該索引有2層完全連通的隱藏層和每層16個神經元，可以大幅的減少誤差。 然而，在CPU上，模型的復雜性并沒有得到回報（例如，模型執行時間太長，無法證明搜索時間較短）。 然而，正如前面提到了GPU / TPU的發展，這種trade-off會被改變，我們推測下一代硬件對更復雜的模型有利。
可以觀察到，第二階段大小（模型數量）對索引大小和查找性能具有顯著影響。 這并不奇怪，因為第二階段決定了需要存儲多少個模型。 值得注意的是，我們的第二階段使用了10,000或更多的模型。 這在第[2.1]節的分析中特別令人印象深刻，因為它表明我們的第一階段模型可以比B樹中的單個節點在精度上有更大的提高。
最后，我們沒有提到整數數據集的上跑任何混合模型，因為它們像偏見搜索一樣沒有提供任何好處。
圖7：字符串數據：學習索引與B-Tree
圖8：使用不同搜索策略的學習字符串索引
圖[7]顯示了不同的搜索策略。 但是，我們確實在表格中看到最佳模型是一個非混合RMI模型索引，使用四元搜索策略，名為“Learned QS”（表格底部）。 所有RMI索引在第二階段使用10,000個模型，對于混合索引，我們使用兩個閾值128和64，作為模型在用B-Tree替換自己之前的最大容許絕對誤差。
可以看出，用于字符串的B-Trees學習索引的加速不再那么突出。 這因為一個事實——模型執行相當昂貴，這是GPU / TPU可以解決的問題。 此外，搜索字符串要昂貴得多，因此更高的精確度通常會得到更好的結果。 這就導致了混合索引通過B樹取代表現不佳的模型，有助于提高性能。
最后，由于搜索成本的不同，如圖[8]所示，對于具有一個或兩個隱藏層的2級神經網絡模型，不同的搜索策略會產生更大的差異。 請注意，我們沒有為B樹顯示不同的搜索策略，因為它們沒有提高性能。 偏見搜索和四元搜索性能更好的原因是他們可以將標準誤差考慮在內。
3.7未來的研究挑戰
到目前為止，我們的結果集中在只讀內存數據庫系統的索引結構上。 正如我們已經指出的那樣，即使沒有任何重大修改，當前的設計已經可以替代數據倉庫中使用的索引結構，這些索引結構可能每天只更新一次，或者BigTable [ 18 ] ，其中創建B樹批量作為SStable合并過程的一部分。 在本節中，我們將概述如何將學習型索引結構的概念擴展到頻繁插入的工作負載場景下。
初看起來，由于學習模型潛在的高成本，插入似乎是學習索引的致命弱點，但是再次，學習索引對于某些工作負載可能具有顯著的優勢。 一般來說，我們可以區分兩種類型的插入：（1）appends 和（2） inserts in the middle，例如在訂單表上更新客戶id上的二級索引。 現在我們關注后者，并考慮在我們的已排序數據集中引入額外空間的方法，類似于B樹通過其每個頁面的最小和最大填充因子在已有頁面中引入額外空間。 但是，與B樹相反，假設我們不會均勻地分散空間，而是依賴于學習的累積密度函數。 最后，假設插頁大致遵循與學習的CDF相似的模式; 這并不是一個不合理的假設，就像在顧客id的二級索引的例子中，顧客大致會保持購物行為。在這些假設下，模型可能根本不需要再培訓。 這樣，對新項目的插入，學習索引可以“概括”成為O(1) 操作，因為它們可以直接放入可用空間中，并且空間可用于最常用位置。 相反，B-樹需要O (log n)用于查找和重新平衡樹的插入操作（特別是插入某個區域比其他區域更普遍）。 類似的，對于追加插入，如果模型能夠學習新數據的關鍵趨勢，模型也可能不需要重新學習。
顯然，這一觀察結果也提出了幾個問題。 首先，模型的普遍性和“最后一英里”表現似乎有一個有趣的折衷; “最后一英里”預測越好，可以說，模型過度擬合的能力越強，而且對新數據項的適應能力也越低。
其次，如果分布發生變化會發生什么？ 它是否可以被檢測到，并且是否有可能提供與B樹一樣的強力保證，它總是能夠保證O(log n) 的查找和插入成本？ 雖然回答這個問題已經超出了本文的范圍，但我們相信某些模型有可能實現它。 考慮一個簡單的線性模型：在這種情況下，插入的項目絕不會將誤差增加超過max_abs_error + 1 。 此外，重新訓練線性模型的成本為$$O(K_{M + 1})$$ ，其中$$K_{M + 1}$$是模型在數據中覆蓋的項目數。如果線性模型不足以實現可接受的誤差，我們可以將范圍分成兩個模型，并在上層的那個階段重新訓練模型。 這個模型可能需要重新訓練$$O(K_{M})$$，其中$$K_{M}$$是在重新訓練第一個模型之后的最后一個階段的模型數M等等。因此，基于第一個模型的再訓練，容易限制絕對誤差。 但是，為了給第一個模型提供一個很好的誤差，我們可能需要增加模型的容量，例如通過添加一個多項式或一個額外的隱藏層。 這里有可能通過諸如VC維度的技術再次限制所需的復雜度增加。 研究這些影響，尤其是對于其他類型的模型，包括神經網絡，留待未來的人們的工作。
處理插入的另一種更簡單的方法是構建一個增量索引[ 49 ]和許多其他系統中，并且還具有如下優點：對于大型再訓練操作，可以使用諸如GPU / TPU的專用硬件，這將顯著加速，即使需要對整個模型重新訓練也是如此。
最后，通過使用先前的解決方案作為起點，可以對每個模型的訓練進行熱啟動。 特別是依賴梯度下降優化的模型可以從這種優化中獲益[ 33 ] 。
在本節中，我們假定數據（實際記錄或
利用RMI結構：RMI結構已經將空間劃分為區域。 通過對學習過程的小修改，我們可以最大限度地減少它們覆蓋的區域中模型的重疊程度。 此外，可能會復制任何可能被多個模型訪問的記錄。 這樣我們可以簡單地將偏移量存儲到模型中，也就是數據存儲在磁盤上的位置。
另一種選擇是以
使用更復雜的模型，實際上可以學習頁面的實際指針位置。 特別是如果使用文件系統來確定磁盤上的頁面，并且在磁盤上有系統編號的塊（例如， block1，...，block100 ），則學習過程可以保持不變。
顯然，需要更多的研究來更好地理解基于磁盤的系統的學習索引的影響。與此同時，節省的大量空間以及速度優勢，會讓這個工作的未來很有趣。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章
