本文約3480字，建議閱讀7分鐘。
本文介紹萊斯大學的計算機科學家們提出深度學習框架，在大型工業級的推薦數據集上驗證了在沒有類似於 GPU 的專業硬件加速條件下，也可以對深度學習進行加速。
訓練一億參數量的全連接網絡，44 核心 CPU 讓 V100 甘拜下風，靠的居然是——哈希？
深度學習模型的訓練和推理加速近來是研究領域關注的重點。雖然普遍觀點認為，GPU 相比 CPU 有更強的算力優勢。但在近日，萊斯大學的計算機科學家們公佈了新的研究成果，其提出的深度學習框架，在大型工業級的推薦數據集上驗證了在沒有類似於 GPU 的專業硬件加速條件下，也可以對深度學習進行加速。
在論文中，研究者指出，儘管已有的研究表明，在算法端對模型進行優化無法顯示出如同 V100 GPU 那樣強大的性能提升，但是他們提出的 SLIDE 引擎卻可以實現。這一模型可以顯著地減少訓練和推理階段的運算，比在 GPU 上 經過 TensorFlow 高度優化過的算法還要快。
例如，在工業級的推薦數據集上測試 SLIDE 時，Tesla V100 GPU 上的訓練時間是 Intel Xeon E5-2699A 2.4GHZ 的 3.5 倍。而在同樣的 CPU 硬件條件下，SLIDE 比 TensorFlow 快了 10 倍。
我們可以先看張實驗圖，在 Amazon-670K 這樣的複雜分類數據集上，超一億參數量的大型神經網絡訓練時間竟然是 SLIDE + CPU 最快，連 TensorFlow + Tesla V100 都要慢很多。而且從迭代步數上看，它們兩者是等價的，表明模型的收斂行為是相同的。
對於論文和結果的復現，研究者已提供了相應的代碼。
- 論文鏈接：https://www.cs.rice.edu/~as143/Papers/SLIDE_MLSys.pdf
- 開源地址：https://github.com/keroro824/HashingDeepLearning
計算複雜度大降，局部敏感哈希立功
如此神奇的加速是怎麼實現的？具體而言，研究者採用了局部敏感哈希（Locality Sensitive Hashing）算法，並在神經網絡中使用了自適應 dropout。局部敏感哈希是一類哈希算法，當輸入數據彼此類似的時候，具有更高的碰撞概率，而不相似的算法彼此碰撞的概率很低。一種廣泛應用的最近鄰逼近搜索算法就使用了局部敏感哈希理論。
SLIDE 的局部敏感哈希如何構建
在 Indyk 和 Motwani 在 1998 年的一項研究中表明，對於給定的相似性計算，一類 LSH 函數就足以有效地解決次線性時間中的最近相鄰搜索。
算法：LSH 算法使用兩個參數（K,L），研究者構造了 L 個獨立的哈希列表。每個哈希表都有一個原始哈希函數 H，而該函數是由集合 F 裡 K 個隨機的獨立哈希函數串聯而成。在給定一個查詢下，從每一個哈希列表中採集一個 bucket 後會返還 L 個 bucket 的集合。
直觀地說，原哈希函數使得 bucket 變得稀疏，並減少了誤報的數量，因為只有有效的最近相鄰項才可以匹配給所查詢的所有 K 的哈希值。L 的 bucket 集合通過增加可存放的最近相鄰項的潛在 bucket 數量來減少漏報的數量。而候選生成算法分為兩個階段工作：
1. 預處理階段，通過儲存所有 x 元素，從數據層面構造 L 的哈希列表。只存儲哈希列表中指向向量的指針，因為儲存整個數據向量會非常低效。
2. 查詢階段：給定一個查詢 Q，搜索其最近相鄰項，從 L 的哈希列表所收集的所有 bucket 集合進行報告。這裡注意，不需要去掃描所有的元素，只是在探測 L 的不同的 bucket，而每個哈希列表裡都有一個 bucket。
在生成潛在的候選算法後，通過比較候選集裡的每個子項與查詢間的距離從而計算處最近相鄰項。
將局部敏感哈希用於採樣和預估
雖然局部敏感哈希被證明能夠在亞線性條件下進行快速抽取，但是對於精確搜索而言速度非常慢，因為它需要大量的哈希表。有研究表明，通過如圖 1 所示的高效採樣能夠在一定程度上緩解搜索的計算量，只需要看一些哈希桶就能夠做到足夠的自適應採樣。
圖 1：局部敏感哈希的圖示。對於一個輸入，可以從對應的哈希桶中抽取哈希碼。
而最近在最大化內積搜索（maximum inner product search：MIPS）的研究也說明了這一點，在這裡，可以使用非對稱局部敏感哈希，使得采樣大的內積變得可能。給定一個向量集合 C 和查詢向量 Q。使用 (K,L)--參數化的 LSH 算法和 MIPS 哈希，可以獲得一個候選集合 S。在這裡，只需要一次線性成本，對 C 進行哈希化的預處理，而對於 Q 則只需要少量哈希查表工作。
SLIDE 中的算法，包括框架（算法 1）和哈希採樣（算法 2）。
構建 SLIDE 系統
圖 2：SLIDE 系統架構。
在 SLIDE 架構中，其核心模塊是網絡。該神經網絡由一些單層模塊組成。對於每個層的模塊，其都是由神經元和一些哈希表組成——即將神經元的 ids 轉換成哈希。
對於每個神經元來說，它都有多個批大小長度數組：1）一個二元數組，表示對於每個輸入，該神經元是否激活；2）每個輸入的激活；3）批數據中每個輸入的累積梯度；4）該層和上一層連接權重；5）上一層神經元數量，由最後一個數組表示。
初始化
每層對象包含一個神經元列表以及一組 LSH 採樣哈希列表。每個哈希列表包含被散列至 bucket 中神經元的 ids。在網絡初始化過程中，網絡的權重值是隨機初始化的。隨後，對每層使用 L 的哈希列表進行初始化 K * L LSH 函數。
使用哈希表採樣進行稀疏前向傳播
在前向傳播階段，給定一個單獨的訓練實例，研究者會計算直到最後一層的網絡激活，並給出輸出。在 SLIDE 中，他們不會去計算每層的所有激活，而是將每層的輸入 xl 輸入到哈希函數中，得到 hl(xl)，哈希碼作為查詢，從對應匹配的 buckets 中獲得激活（採樣）的神經元的 ids。
稀疏反向傳播/梯度更新
反向傳播步驟緊接著前向傳播進行。計算了神經網絡的輸出之後，研究者會將輸出和標籤進行比較，並將誤差逐層進行反向傳播，來計算梯度、更新權重。這裡他們使用了經典的反向傳播方法。
權重更新後再更新哈希列表
權重值更新後，需要相應地調整哈希列表中神經元的位置。更新神經元通常涉及到從舊的哈希桶中刪除，然後再從新的哈希桶中添加新的內容，這可能會非常耗時。在 4.2 節中，將討論幾種用於優化更新哈希列表所導致昂貴開銷的設計技巧。
OpenMP 跨批量處理的並行化
對於任何給定的訓練實例中，前饋以及反向傳播操作都是按照順序的，因為它們需要逐層的去執行。SLIDE 使用常用的批量處理梯度的下降方法以及 Adam 優化器，批量處理大小通常在幾百個左右。批量處理中的每個數據實例的運行都在單獨的線程中，其梯度是按照並行方式計算的。
梯度更新的極端稀疏性以及隨機性使得我們可以在不導致大量重疊更新的情況下，在不同的訓練數據上通過異步並行處理梯度累積的步驟。SLID 大量地使用了 HOGWILD 的理論 (Recht et al., 2011)，同時也表明少量的重疊是可控的。
真 → CPU 比 GPU 快
研究者在論文後面附上了一系列實驗結果，包括對比採用 Tesla V100 GPU 的 TensorFlow 模型、對比採用 兩個 Intel Xeon E5-2699A CPU（單個 22 核心，總共 44 核心）的 TensorFlow 模型，對比 SLIDE 自適應採樣與帶採樣的 Softmax 之間的性能等等。我們可以發現，SLIDE 在 CPU 上的訓練速度，竟然驚人地高效。
首先對於測試模型，研究者採用了具有一億參數量的超大全連接模型，數據集也是 Delicious200K 和 Amazon-670K 這種大型工業級分類數據集。這兩個數據集分別有 78 萬+和 13 萬+特徵維度，20 萬+和 67 萬+的類別數量，看著就恐怖。因為特徵維度和分類類別太高，即使隱藏層單元不多，整體的參數量也會劇增。
如下圖所示展示了論文的主要結果，CPU 上的 SLIDE 從時間上要比 V100 快（採用 TensorFlow 框架），且能一直優於基於 CPU 的 TF 模型。
圖 5：SLIDE（紅線）、TF-GPU（藍線）和 TF-CPU（黑線）之間的效果對比。
在 Delicious200K 數據集上，SLIDE 比 TF-GPU 快 1.8 倍。而在需要更大算力的 Amazon-670K 上，TF-GPU 的收斂時間是 SLIDE 的 2.7 倍（2 小時與 5.5 小時）。從迭代量來看，兩者之間的收斂行為也是等價的，只不過每一次迭代 SLIDE 都快一些。
此外，在圖 5 中，最後的收斂效果都是差不多的，也就是說在 SLIDE 框架下，模型效果並不會被破壞。
表 2 展示了 CPU 核心的使用情況，其分別測試了框架在使用 8、16、32 線程下的負載情況。我們可以看到，對於 TF-CPU，其使用率非常低（<50%），且隨著線程的增加，使用率會進一步降低。對於 SLIDE，計算核心的利用是非常穩定的，大約在 80% 左右。
圖 6 展示了 TF-CPU 和 SLIDE 在 CPU 無效利用率上的分佈情況。SLIDE 對於計算核心的利用率要遠遠高於 TF-CPU 的利用率。
圖 6：CPU 低效利用率：Memory-bound 的低效利用率（橙色）對於這兩種算法是最顯著的。TF-CPU 隨著核心數的增加，Memory-bound 低效利用率也會增加，而 SLIDE 會降低。
因為能高效利用 CPU 的計算資源，SLIDE 隨著 CPU 核心數的 增加，收斂時間還能極大地降低。
圖 9：TF-CPU 與 SLIDE 之間的可擴展性測試，很明顯 SLIDE 要強很多。
代碼示例
現在 SLIDE 已經開源。在開源項目中，作者提供了數據集和相應的代碼進行測試。
首先，使用者需要安裝 CNPY，並開啟 Transparent Huge Pages，SLIDE 需要大約 900 個 pages，每個 2MB，以及 10 個 1GB 的 pages。
運行代碼過程如下：
<code>make./runme Config_amz.csv/<code>
需要注意的是，Makefile 需要基於 CNPY 修改路徑，同時需要修改的包括在 Config_amz.csv 中的 trainData、testData、logFile 等。
至於訓練數據，它來自 Amazon-670K ，下載地址如下：
https://drive.google.com/open?id=0B3lPMIHmG6vGdUJwRzltS1dvUVk
在工業領域中，模型結構並不一定非常複雜，樸素貝葉斯、全連接網絡這些簡單模型往往能獲得更多的青睞。然而，真實模型通常非常龐大，配置高性能 GPU 來訓練模型非常不划算。即使這篇論文只驗證了全連接網絡，但至少說明高性能 CPU 真的能滿足大模型的訓練，能大量降低硬件成本。
—完—
關注清華-青島數據科學研究院官方微信公眾平臺“ THU數據派 ”及姊妹號“ 數據派THU ”獲取更多講座福利及優質內容。
閱讀更多 數據派THU 的文章
