用 GPU 加速 TSNE：從幾小時到幾秒
- 2019 年 12 月 2 日
- 筆記
原標題 | Accelerating TSNE with GPUs: From hours to seconds
作 者 | Daniel Han-Chen
翻 譯 | 人氣呆毛選手、米粒_Melxy
審 校 | 鳶尾、唐里
圖1. MNIST Fashion上的cuML TSNE需要3秒。 Scikit-Learn需要1個小時。
TSNE（T分布隨機領域嵌入）是一種流行的無監督降維演算法，其用途廣泛，包括神經病學，影像相似性和可視化神經網路。 但它的最大缺點是在大多數可用的實現中處理時間很長。 RAPIDS現在基於CannyLab.開發的基於GPU的Barnes-Hut方法，提供了GPU加速的快速TSNE。 RAPIDS的cuML機器學習庫中的TSNE的運行速度比相應的CPU處理快2,000倍，並且比當前GPU版本使用的GPU記憶體少30％。
該部落格首先介紹一些用例示例，然後是將cuML的GPU TSNE實現與scikit-learn進行比較的基準測試。 然後，詳細解釋TSNE如何實現以及如何在cuML中對其進行優化，使其能在GPU上運行。
TSNE的應用
TSNE與傳統的監督方法（例如線性回歸和決策樹）形成對比，因為它不需要標籤。 TSNE試圖通過移動相似點和相異點，使其互相遠離來識別數據的結構。
圖2.在時尚用例中使用的TSNE。
在圖2中，TSNE被應用於由60,000件衣物影像組成的時裝數據集。這對於將「相似」服裝聚集的自然分組很有用。 TSNE能夠將時裝影像的複雜空間減小到較小的空間，從而更易於使用。每個影像的像素向量都用作輸入，TSNE將其映射為2個維度，即每個影像映射為2個值。在圖5中，根據原始輸入的服裝類別（例如靴子是藍色）繪製了TSNE的二維輸出並進行了顏色編碼。 TSNE不知道這些類別，但是找到了一個能夠將更多相似項放在一起的分組。
下圖是使用MNIST數字數據集的示例。給定手寫數字，任務是將每個數字分類為0、1、2等。在對所有60,000個數字影像應用TSNE之後，我們發現沒有任何標籤，TSNE設法分離數據。可以在圖3中看到如何用數字類型（0到9）對清晰的簇進行顏色編碼。
圖3. MNIST數字數據集的TSNE圖
TSNE還用於可視化卷積神經網路，以幫助從業者辨別複雜的分類器是否真正在「學習」。下圖顯示了TSNE應用於AlexNet，其中實際分類器（4096維）之前影像的CNN輸出縮減為2維 ，然後顯示實際的輸入影像。 請注意，在圖4中，相似的影像趨於接近，這意味著AlexNet如何將它們「視為」相似。
圖 4. 來源: CS231n Convolutional Neural Networks for Visual Recognition
TSNE vs. Principal Component Analysis (PCA)
TSNE是一種非線性降維演算法，而主成分分析是線性的。這意味著PCA的組成部分通常具有一定的含義，而TSNE不再按重要性排序，其創建的領域之外也不具有可解釋性。在CPU上，通常建議用PCA將維度減小到50，然後再將其輸入TSNE以提高性能。但GPU並非如此。
RAPIDS cuML Speed-Up over Scikit-Learn
許多數據科學家從scikit-learn流行的TSNE實現開始。 Scikit-learn的TSNE提供了熟悉的，易於使用的介面，但會遇到可伸縮性問題。 例如，一個60,000個示例數據集可能需要1個小時才能在CPU上的scikit-learn中收斂。 在但NVIDIA V100 GPU上運行的cuML TSNE可以在同一數據集上3秒內就可以完成收斂。
表1.在NVIDIA DGX-1上使用1個V100 GPU運行的cuML的TSNE時間。
注意表1中的對數log。
表2. cuML和Scikit-Learn（DGX 1）之間的時間間隔（以秒為單位）
因此cuML的TSNE運行速度提高了1000倍，並且獲得了相似的可信度評分.
表3.顯示了cuML在NVIDIA DGX 1上運行的scikit-learn的加速完整的過程圖。
在具有204,800個樣本和80個特徵的數據集上，cuML需要5.4秒，而Scikit學習需要將近3個小時，加速了2,000倍。 而且還在僅使用一個V100 GPU（DGX1：32gb GV100 GPU，Intel Xeon E5–2698 v4 CPU @ 2.20GHz w / 20核和40個執行緒）的NVIDIA DGX-1機器上測試了TSNE。 數據傳輸時間也包括在此基準測試中。 圖5顯示了包含100個樣本和80列的數據集。 請注意，即使在小型數據集上，cuML也可以更快。
圖5.乳腺癌小型數據上的cuML TSNE（1秒）
使用上述PCA技巧確實使scikit-learn的TSNE的端到端性能稍有提高，但是，RAPIDS cuML TSNE仍在204,800個樣本和50列的高數據集上展示了超過1,000倍的加速。 這使TSNE可以在數據集上進行訓練，而無需首先使用PCA縮小維度。
TSNE如何起作用
cuML的TSNE主要基於CannyLab最初的Barnes Hut實現。當前，支援兩種演算法：Barnes Hut TSNE和Exact TSNE。 Barnes Hut的運行速度比Exact版本快得多，但準確性略低（錯誤率最多3％）。對於大型數據集（樣本> = 2,000），建議使用Barnes Hut演算法以提高速度。
TSNE有兩個主要目標：
- 距離近的點應該保持近距離。
- 距離遠的點應該保持遠距離。
給定高維度設置（例如3D或1,000 D）中的某些數據點，目標是將這些點嵌入較低的空間（例如2維），以便保留輸入數據的局部鄰域結構可能以其嵌入式形式出現。
更具體地說，首先將原始高維空間中的點轉換為看起來像鐘形曲線或正態分布的概率密度，如下面的圖6中的紅線所示。 接近的點會彼此增加概率，因此密集區域往往具有更高的值。 同樣，離群點和相異點的值也較小。
圖6.來源：study.com
這是為什麼TSNE名稱中「 T分布」的來源。下部空間中的點也使用鐘形曲線進行建模，儘管它像圖6中的藍線一樣伸展。
人們嘗試使用非擴展版本，但這會導致一個稱為「擁擠問題」的問題，其中嵌入的點會聚在一起。
圖7.左圖顯示了擁擠問題。 TSNE通過使用T分布解決了這一問題。
現在，想像一下彈簧將低維空間中的每個點連接到其他點。 想像以下情況：
- 原先接近的點將互相拖拉。 （吸引）
- 原本不相似的點將相互推動。 （排斥）
從本質上講，我們的彈簧功能已經顛倒了。 人們會期望遙遠的點會有彈簧將它們拉在一起，但在TSNE中則相反。
現在，釋放低維空間中的彈簧，這是TSNE的優化階段。 當所有彈簧停止運動時，我們終止了進化系統。 我們移除彈簧，每個點的終點變成最終的嵌入。
TSNE優化
可以使用四種優化來提高TSNE在GPU上的性能：
- 用更少的GPU記憶體計算更高的維度概率
- 近似高維概率
- 減少算術運算
- 沿行廣播
優化 1 — 用更少的GPU記憶體計算更高維度的概率
還記得通過考慮其他每個點的影響來計算每個點的概率的目標嗎？ 當A點對B點的影響與B點對A的影響不同時，它們是不對稱的。 為了使它們相等，將兩種貢獻相加並在它們之間進行分配，這稱為對稱化概率。
最初，由於使用了不必要的中間存儲緩衝區，對稱化步驟效率很低。 在RAPIDS實現中，記憶體使用減少了30％，並且現在已高度並行化。 現在，在總運行時間中，對稱化花費的時間為總運行時間的1％或更少，而以前為25％。
表4. GPU上每個內核的時序。對稱化花費了總時間的1％。
為了實現此優化，我們首先使用快速cuML primitives將點之間的距離轉換為COO（坐標格式）稀疏矩陣。稀疏矩陣格式擅長表示連接的節點和邊的圖。在k個最近鄰圖的情況下尤其如此，因為它們具有固定數量的連接邊，因為只需要考慮每個點的最近鄰。稀疏格式僅需要存儲連接的頂點，從而為TSNE等演算法提供了顯著的加速和較低的存儲開銷。 COO格式由3個非常簡單的數組表示：數據值（COO_Vals），列索引（COO_Cols）和單個行索引（COO_Rows）。
例如，假設有一個給定的點（0，7），其值為10。它的轉置（或反向）為（7，0），也為10。這是如何將其存儲在最終COO稀疏矩陣中的方法：
const int i = RowPointer[row]; COO_Vals[i] = val; COO_Cols[i] = col; COO_Rows[i] = row;
要使其轉置或反轉，只需像這樣翻轉col和row指針：
const int j = RowPointer[col]; COO_Vals[j] = val; COO_Cols[j] = row; COO_Rows[j] = col;
注意上面的示例還包含一個名為「 RowPointer」的數組。 COO布局不包括有關每一行的開始或結束位置的資訊。 包含此資訊使我們可以並行化查找，並在對稱化步驟中快速求和轉置後的值。 RowPointer的想法來自CSR（壓縮稀疏行）稀疏矩陣布局。 在CSR布局中，entries是根據其所在的行進行索引的。例如，所有行索引為1的元素都以排好序的方式放置在RowPointer索引的開頭。 CSR布局非常適合以行方式訪問數據的演算法。
結合這兩種布局，我們可以將COO格式用於圖形中每個元素的高效並行計算，而CSR格式用於執行元素的轉置。 由於RowPointer包含每一行中存在的元素數，因此可以使用atomicAdd來並行匯總每對點的貢獻。
const int i = atomicAdd(&RowPointer[row], 1); const int j = atomicAdd(&RowPointer[col], 1);
圖8.運行中的對稱內核的示意圖。
圖8顯示了整個過程。 給定點（0，7）的值為10，對行指針進行索引以獲取該點的行索引，並將其存儲。然後，翻轉至（7，0），訪問行指針，並將其與第一個指針並行存儲。
優化2-近似高維概率
TSNE的作者van der Maaten指出，與其計算所有點之間的全距離，不如計算最近鄰並從中計算出高維概率。 cuML遵循CannyLabs使用Facebook的FAISS庫在GPU上計算前k個近鄰的方法。這樣就從必須存儲N²個元素減少到僅存儲N* k個元素（N是數據取樣數，k是近鄰數）的概率計算。
優化3-減少算術運算
在許多TSNE的實現中，將吸引力計算（彈簧拉力）拆分為先在點A上，後在點B上進行計算。如果同時計算交互，而不是單獨計算，TSNE的速度可以顯著提高。這樣可以將乘法和地址的數量，從原來的9個減少到大約4個，並使此計算速度提高50％。
優化4-逐行廣播
圖9.計算公共值並將其分布在每一行！
另一個基本優化是注意到行間重複了維度1中的點A，和維度2之間的距離。這意味著，不必為每個維度分別計算值，只需對它進行一次計算，然後廣播並重新用於其他維度即可。這再次減少了算術運算，並進一步加快了TSNE的速度。這是許多CUDA演算法（包括cuML中的許多演算法）使用的通用技術。
改善TSNE的數值穩定性
在CannyLab的原始實現中，cuML修復了一些罕見的數字穩定性問題，包括一些死循環和越界的記憶體訪問。此外我們還知道TSNE對它的超參非常敏感。 在cuML中提供了一種自適應學習方案，其中可以根據用戶的輸入數據來調整參數。
有時如果學習率太大，嵌入點可能會成為異常值。在cuML中指定了MAX_BOUND，它將小心地將異常值推回並重置所有動量變數。這也有助於提高TSNE的準確性和可信度。
我們如何在RAPIDS中運行TSNE？
讓我們比較scikit-learn的API和RAPIDS cuML的API。 本示例使用scikit-learn的數字數據集。
scikit-learn API：
現在將其與cuML進行比較：
由於cuML幾乎是scikit-learn的直接替代品，因此sklearn.manifold包可以替換為cuml.manifold，其他所有功能都可以使用。
這是一個Jupyter Notebook，展示了在Fashion MNIST數據集上的cuML TSNE的演示。
有關更多TSNE示例和對TSNE的數學優化的更深入了解，請在此處查看更多擴展的Jupyter Notebook。
在波士頓住房數據集上使用cuML TSNE
結論
TSNE在實現非常大和很複雜的數據集可視化方面非常成功。它能夠識別無標籤數據集中的結構。然而它的最大缺點是執行時間慢。
藉助新的RAPIDS TSNE實現可以將速度提高2,000倍，同時使用的GPU記憶體也會減少30％。提出您的想法並提供回饋。在此處的Google Colab實例上免費試用cuML TSNE。
TSNE參考文獻
- David M. Chan, Roshan Rao, Forrest Huang, John F. Canny : t-SNE-CUDA: GPU-Accelerated t-SNE and its Applications to Modern Data https://arxiv.org/pdf/1807.11824.pdf [31 Jul 2018]
- George C. Linderman, Manas Rachh, Jeremy G. Hoskins, Stefan Steinerberger, Yuval Kluger: Efficient Algorithms for t-distributed Stochastic Neighborhood Embedding https://arxiv.org/abs/1712.09005 [25 Dec 2017]
- Laurens van der Maaten, Geoffrey Hinton : Visualizing High-Dimensional Data Using t-SNE https://lvdmaaten.github.io/publications/papers/JMLR_2008.pdf [2008]
via https://medium.com/rapids-ai/tsne-with-gpus-hours-to-seconds-9d9c17c941db
