淺談機器學習時代的哈希演算法（二）

來自專欄 我是程序員

摘要：來，咱們聊聊機器學習時代的哈希演算法～

上篇文章中，我們了解哈希演算法相關知識，淺談機器學習時代的哈希演算法（一）

接著我們介紹機器學習如何重新創建哈希表！高能！

機器學習基礎

為了理解機器學習如何被用來重新創建哈希表（和其他索引）的關鍵特徵，我們需要快速重新審視統計建模的主要思想。統計模型是一種函數，它接受一些向量作為輸入，並返回：標籤（用於分類）或數值（用於回歸）。輸入向量包含有關數據點的所有相關信息，標籤/數值輸出是模型的預測。

在預測高中生是否會進入哈佛大學的模型中，向量可能包含學生的GPA、SAT分數、該學生所屬的課外俱樂部數量以及與其學業成績相關的其他數值；該標籤將是真/假（會進入/不會進入哈佛）。

在預測抵押貸款違約率的模型中，輸入向量可能包含信用評分值、信用卡賬戶數量、延遲付款頻率、年收入以及與申請抵押貸款的人的財務狀況相關的其他值；該模型可能會返回0到1之間的數字，表示違約的可能性。

通常，機器學慣用於創建統計模型。機器學習從業者將大型數據集與機器學習演算法相結合，並且在數據集上運行演算法的結果是訓練有素的模型。機器學習的核心是創建演算法，該演算法可以從原始數據自動構建精確的模型，而無需人類幫助機器「理解」數據實際表示的內容。這與其他形式的人工智慧不同，人類對數據進行廣泛檢查，為計算機提供有關數據含義的線索（例如通過定義啟發式演算法），並定義計算機將如何使用該數據（例如，使用最小最大值或A *）。然而，在實踐中，機器學習經常與經典的非機器學習技術相結合，人工智慧代理商會經常使用學習和非學習策略來實現其目標。

考慮著名的國際象棋「深藍」和最近廣受好評的「AlphaGo」。深藍是完全非機器學習的AI；人類計算機程序員與人類國際象棋專家合作創建一個函數，該函數將棋局的狀態作為輸入（所有棋子的位置，以及該棋手的狀態），並返回與該狀態的「良好」相關的值對於深藍。深藍從來沒有「學過」任何東西，而是人類國際象棋運動員苦苦編纂機器的評估功能。深藍的主要特點是樹搜索演算法，它允許它計算所有可能的移動，以及它的所有對手對這些移動的可能響應，以及將來的許多移動。

AlphaGo樹搜索的可視化。

AlphaGo也執行樹搜索，就像Deep Blue一樣，AlphaGo在每一個可能的移動中都會看到幾個動作。與Deep Blue不同，AlphaGo創建了自己的評估功能，沒有Go專家的明確指示。在這種情況下，評估函數是一個訓練有素的模型。AlphaGo的機器學習演算法接受Go的狀態（對於每個位置，是否有白色的石頭、黑色的石頭或沒有石頭），標籤代表哪個玩家贏得了遊戲（白色或黑色）。利用這些信息，在數十萬種遊戲中，機器學習演算法決定了如何評估任何特定的電路板狀態。AlphaGo通過觀察數以百萬計的例子，教會自己哪種舉動將提供最高的勝利可能性。

（這是一個非常重要的簡化，就像AlphaGo的工作原理一樣。你可以從AlphaGo的創建者那裡了解更多關於AlphaGo的信息。）

模型作為指標，從ML標準出發

Google的研究人員在他們的論文中首先提出了索引是模型的前提，或者至少可以使用機器學習模型作為索引。理由是：模型是接受一些輸入並返回一個標籤的機器；如果輸入是關鍵字，標籤是模型對內存地址的估計，那麼可以使用模型作為索引。雖然這聽起來很簡單，但索引問題顯然不適合機器學習。以下是谷歌團隊不得不脫離機器學習規範以實現其目標的一些領域。

通常情況下，機器學習模型會根據其所了解的數據進行訓練，並負責對未見數據進行估算。當我們對數據建立索引時，估計是不可接受的。索引唯一的工作是實際查找內存中某些數據的確切位置。Google通過跟蹤訓練期間每個節點所經歷的最大（最正）和最小（最負）誤差來處理這個問題。使用這些值作為邊界，ML索引可以在這些邊界內執行搜索以查找元素的確切位置。

另一個出發點是機器學習從業者通常必須小心避免將他們的模型「過度擬合」到訓練數據上；這樣的「過度擬合」模型將對其所訓練的數據產生高度準確的預測，但通常會對訓練集外的數據執行得非常糟糕。另一方面，索引從定義上講是過度擬合的。訓練數據是被索引的數據，也使其成為測試數據。由於查找必須發生在索引的實際數據上，所以在這種機器學習應用中，過度擬合更容易被接受。同時，如果模型過度適合現有數據，則向索引添加項目可能會產生可怕的錯誤預測；正如文件中指出的那樣：

這個模型的普遍性和「最後一英里」表現似乎有一個有趣的折衷; 「最後一英里」預測越好，可以說，模型過度擬合的能力就越強，而對新數據項的推廣能力就越差。

最後，訓練模型通常是該過程中最昂貴的部分。不幸的是，在廣泛的資料庫應用程序（和其他索引應用程序）中，向索引添加數據相當普遍。

學習哈希

該論文審查了使用機器學習模型替代標準哈希函數的可能性。研究人員有興趣了解的一個問題是：知道數據的分布能否幫助我們創建更好的索引？通過我們上面探討的傳統策略（移位乘法、murmur hash、素數乘法...），數據的分布被明確忽略。每個傳入項目都被視為一個獨立的值，而不是作為具有寶貴屬性的較大數據集的一部分來考慮。結果是，即使在很多先進的哈希表中，也存在很多浪費的空間。

哈希表的實現具有大約50％的內存利用率是常見的，這意味著哈希表佔用了實際需要存儲的數據兩倍的空間。換句話說，當我們存儲與數組中存儲的數量完全一樣多的項時，哈希表中的一半地址仍為空。通過用機器學習模型替換標準哈希表實現中的哈希函數，研究人員發現它們可以顯著減少浪費的空間量。

這並不是特別令人意外的結果：通過對輸入數據進行訓練，學習的散列函數可以更均勻地在一些空間上分布值，因為ML模型已經知道數據的分布！ 然而，這是一種潛在的強大方式，可以顯著減少基於散列索引所需的存儲量。這帶來了一個折衷：ML模型比我們上面看到的標準哈希函數要慢一些，並且需要一個標準哈希函數不需要的訓練步驟。

也許使用基於ML的散列函數可以用於有效的內存使用，但關鍵問題是計算能力很大的情況下。谷歌/麻省理工學院的研究小組認為數據倉庫是一個很好的用例，因為計算能力正在很快的提升過程中；使用更多的計算時間來獲得顯著的內存節省可能是許多數據倉庫環境的一個勝利。

但還有一個情節扭轉，進入布谷鳥哈希。

布谷鳥哈希（Cuckoo Hashing）

布谷鳥哈希於2001年發明，並以布谷鳥命名。布谷鳥哈希是鏈接和線性探測碰撞處理的替代方案（不是替代哈希函數）。該策略的名稱也有一定的來歷，因為在某些布谷鳥種群中，準備下蛋的雌性會找到一個被佔領的巢穴，並將它現有的卵子從它上面取下來以便自己放置。在布谷鳥哈希中，傳入的數據會竊取舊數據的地址，就像布谷鳥鳥偷走對方的巢穴一樣。

以下是它的工作方式：當你創建你的哈希表時，你立即將表分成兩個地址空間；我們會稱它們為主要和次要地址空間。此外，還可以初始化兩個獨立的散列函數，每個地址空間一個散列函數。這些散列函數可能非常相似，例如它們都可以來自「主要乘數」族，其中每個散列函數使用不同的素數。我們將這些稱為主要和次要散列函數。

如果該次要地址空間已被佔用，則會發生另一次逐出，並將次要地址空間中的數據發送回主地址空間。因為有可能造成無限的驅逐循環，所以通常設置逐出驅逐的門檻；如果達到這種驅逐次數，則重建該表，這可能包括為該表分配更多空間和/或選擇新的散列函數。

眾所周知，這種策略在記憶受限的場景中是有效的。所謂的「兩種選擇的力量」允許布谷鳥哈希即使在非常高的利用率下也具有穩定的性能（這不是鏈式或線性探測的真實情況）。

Bailis和他在斯坦福大學的研究團隊發現，通過一些優化，布谷鳥散列速度可以非常快，即使在99％的利用率下也能保持高性能。從本質上講，布谷鳥哈希可以通過利用兩種選擇的力量，在沒有昂貴的訓練階段的情況下實現機器學習的哈希函數的高度利用。

索引的下一步是什麼？

最終，每個人??都對能夠學習的索引結構的潛力感到興奮。隨著越來越多的ML工具的推出，像TPU這樣的硬體進步使機器學習工作負載更快，索引可以越來越受益於機器學習策略。與此同時，像布谷鳥哈希這樣的漂亮演算法提醒我們，機器學習不是萬能的。融合了機器學習技術和古老理論（如「兩種選擇的力量」）的令人難以置信的力量將繼續提高計算機效率和能力的界限。

索引的基本原理似乎不可能一夜之間被機器學習策略所取代，但自調整索引的想法是一個強大而令人興奮的概念。隨著我們繼續更善於利用??機器學習，並且隨著我們不斷提高計算機處理機器學習工作負載的效率，利用這些進步的新想法必將找到主流使用方式。下一個DynamoDB或Cassandra可能會很好地利用機器學習策略，PostgreSQL或MySQL的未來實現最終也可能採用這種策略。最終，這將取決於未來研究的成功，這將繼續建立在最先進的非學習策略和「AI革命」的尖端戰術上。

數十款阿里雲產品限時折扣中，趕緊點擊領劵開始雲上實踐吧！

以上為譯文，由@阿里云云棲社區組織翻譯。

文章原標題《an-introduction-to-hashing-in-the-era-of-machine-learning》

譯者：虎說八道，審校：袁虎。

文章為簡譯，更為詳細的內容，請查看原文。

更多技術乾貨敬請關注云棲社區知乎機構號：阿里云云棲社區 - 知乎

本文為雲棲社區原創內容，未經允許不得轉載。

推薦閱讀：