接着我們介紹機器學習如何重新建立哈希表！高能！
機器學習基礎為了了解機器學習如何被用來重新建立哈希表（和其他索引）的關鍵特征，我們需要快速重新審視統計模組化的主要思想。統計模型是一種函數，它接受一些向量作為輸入，并傳回：标簽（用于分類）或數值（用于回歸）。輸入向量包含有關資料點的所有相關資訊，标簽/數值輸出是模型的預測。
在預測高中生是否會進入哈佛大學的模型中，向量可能包含學生的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 》， 譯者：虎說八道，審校：袁虎。 文章為簡譯，更為詳細的内容，請檢視 原文 。