機器之心論文解讀：可用於十億級實時檢索的循環二分嵌入模型

機器之心原創

作者：Olli Huang

編輯：Hao

編譯：Geek AI、路

今年 2 月，來自微軟 Bing 的研究人員在今年的 KDD 會議上發表了論文《Recurrent Binary Embedding for GPU-Enabled Exhaustive Retrieval from Billion-Scale Semantic Vectors》。該論文提出了能夠生成緊湊語義表徵的「循環二分嵌入」（RBE），這些表徵可存儲在 GPU 上，RBE 使得十億級的檢索能夠實時進行。機器之心對這篇論文進行了解讀。

論文鏈接：https://arxiv.org/pdf/1802.06466.pdf

1 簡介

信息檢索（IR）是根據用戶查詢從存儲在計算機上的源數據集合中檢索信息的活動。信息檢索已有長達一個世紀的歷史 [1]，它是許多常見應用（如 web 搜索、產品推薦和社交網路上的個性化推送 feed 流服務）的核心。上世紀六七十年代，該領域的研究取得了重大突破 [2]，研究人員開始將查詢和文檔作為高維向量進行編碼。

然而，處理高維向量並非易事。在涉及高維數據的檢索任務中，基於熵和 KL 散度的統計測量方法，過去被廣泛使用。然而，這類方法通常面臨維數災難 [3,4]。

k 最近鄰演算法（k-NN）是一種廣為人知的經典演算法，用於化解維數災難。k-NN 演算法採用「暴力搜索」（或者「窮舉搜索」）方法找到查詢點在參考點集中的 k 個最近鄰。但是，k-NN 演算法的計算開銷巨大。因此，研究人員們提出了諸如近似最近鄰（ANN）等演算法 [5,6]，使用 kd 樹對數據預先進行組織，從而減小計算量。

近十年，圖形處理單元（GPU）在圖像和視頻處理任務中得到了廣泛應用。然而，在開發基於 GPU 的信息檢索（特別是窮舉搜索）方面，卻鮮有突出的成果。論文《Fast k nearest neighbor search using GPU》[7] 是對基於 GPU 的 k-NN 窮舉搜索的早期嘗試。

本文將解讀微軟 Bing 研究人員的一篇論文《Recurrent Binary Embedding for GPU-Enabled Exhaustive Retrieval from Billion-Scale Semantic Vectors》，他們在這篇論文中提出了一個新模型「循環二分嵌入」（Recurrent Binary Embedding，RBE），它首次將基於 GPU 的窮舉 k-NN 演算法應用到十億級的實時信息檢索任務上。

這篇論文主要的貢獻是設計了能夠生成緊湊語義表徵的「循環二分嵌入」（RBE），使十億級的檢索能夠實時進行，這些表徵可存儲在 GPU 上。RBE 模型使用 CNTK 中的 BrainScript 實現（BrainScript 不久後將被開源，項目地址： https://docs.microsoft.com/en-us/cognitive-toolkit/），且在 GPU 集群上訓練而成。此外，這篇論文在一個自定義多 GPU 伺服器上實現了基於 GPU 的 RBE 信息檢索模型（簡稱 rbeGIR），如圖 1 所示。

圖 1：具備 4 張英偉達 GeForce GTX 1080 GPU、兩個 8 核 CPU、128GB DDR 內存的 rbeGIR 伺服器。

論文的作者利用微軟付費搜索引擎收集的數據，對 rbeGIR 系統進行評估。RBE 模型的訓練數據包含 1.75 億（175M）唯一點擊對，這些數據是從兩年的有效搜索日誌中採樣得到的。通過交叉抽樣給每一個點擊增加 10 個負樣本，使訓練樣本的總數達到 19.25 億（1925M）。為了避免重複，驗證數據由一個月後採樣得到的 1.2M 點擊對組成。此外，測試數據包括人類標註的 0.8M 個點擊對。

此外，rbeGIR 系統在召回和延遲方面取得了非常好的表現。在基於 12 億個關鍵詞和 1 萬條查詢的評估中，該系統的平均召回率達到了 99.99%，而平均延遲僅為 31.17 毫秒，這充分體現了 rbeGIR 系統的實時檢索能力。

2. 要點

RBE 模型是在大型搜索引擎的搜索廣告（sponsored search）背景下提出的。本質上，搜索廣告機制是同時顯示出廣告與搜索結果。該生態系統中三個重要的相關利益方為「用戶」、「廣告商」和「搜索平台」。搜索平台的目標是顯示出用戶可能想要點擊的廣告。

用戶將在搜索框中輸入「查詢」，而搜索引擎會查找到相關的信息。然後，搜索引擎將使用信息檢索技術，提取出能夠將用戶和廣告商意圖相結合的「關鍵詞」。最終，搜索引擎會根據這些關鍵詞顯示一些廣告（或稱「展現」）。如果用戶點擊了廣告，則記錄這個「點擊」事件。

本節將介紹這篇論文的三個要點。第一個要點是 RBE 模型，它提供了一種為搜索廣告語境中的查詢和關鍵詞生成緊湊向量表徵的新方法。第二個要點是基於 RBE 的信息檢索，這一部分關注的是將 RBE 模型應用在基於 GPU 信息檢索系統中。最後一個要點，是使用基於 GPU 的窮舉 k-NN 選擇演算法，這也是 rbeGIR 系統的重要組成部分，專門為十億級檢索而設計。

2.1 RBE 模型

如圖 3 所示，RBE 模型旨在為搜索廣告中的查詢和關鍵詞，生成緊湊的向量表徵。RBE 模型是基於 CLSM 模型 [8] 構建而成（CLSM 模型架構如圖 2 所示）。

RBE 模型與 CLSM 模型在「multi-layers」之前的部分是相同的前饋過程，multi-layers 以上的部分叫做 RBE 層。RBE 層由公式 8-11 形式化表示的。如圖 3 和公示 9-11 所示，正是其中的循環結構使得 RBE 模型具備「循環」的性質。然而，RBE 模型與其他網路結構（如 RNN 或 LSTM）沒有聯繫。這裡「循環」僅僅指的是 RBE 模型中的循環模式。對於 RNN 或 LSTM 類模型，從時間步 t 到 t-1 的轉換會共享同一組參數，以學習持續的記憶單元。而 RBE 模型在確定參數集是否固定或隨著時間變化方面更加靈活。

圖 2：CLSM 模型架構。

圖 3：RBE 模型架構。

本質上，公式 8-11 背後的關鍵思想是通過最大化從實值向量 f_i 中提取出的信息來建立二值分解 b_i^t。為了重構這樣的二值分解，訓練過程中會生成多個中間向量。

2.2 基於 RBE 的信息檢索

用於關鍵詞檢索的系統架構如圖 4 所示。該系統被稱為基於 GPU 的 RBE 信息檢索系統，或 rbeGIR 系統。首先，該系統採用了多個 GPU 來存儲和處理 RBE 嵌入。圓角矩形內展示了第 p 個 GPU 的組成部分。在圖 4 底部我們可以看到，關鍵詞首先被離線轉換為 RBE 向量，然後從 CPU 存儲單元（寄存器、cache 等）轉移到 GPU 顯存中。另一方面，查詢會被即時轉換為 RBE 向量。GPU 內的窮舉匹配組件，則負責計算查詢的 RBE 嵌入與每個關鍵詞之間的相似度。為了找到最佳關鍵詞，匹配結果將指導第 p 個 GPU 負責局部選擇和全局選擇過程。所有 GPU 的計算結果都將通過選擇合併（Selection Merge）對生成的 top N 關鍵詞作出貢獻。

內存效率是 RBE 模型的關鍵優勢。舉例而言，存儲十億個關鍵詞需要 14.90GB 的內存空間，而使用浮點類型進行存儲只需要 238GB 的存儲空間。這為在多 GPU 進行 內存檢索（in-memory retrieval）鋪平了道路。此外，RBE 還能夠學習針對於特定應用的表徵，因此它比通用的量化演算法更加準確。

圖 4：基於 GPU 的 RBE 信息檢索（rbeGIR）系統圖示。

rbeGIR 系統是基於論文作者開發的生產檢索系統評估的。評估過程用到了兩個對比基線：prod_1 指的是具有等量存儲空間的生產環境；prod_2 指具備同等數量關鍵詞的設置。此外，rbeGIR 系統中還存儲了 12 億個唯一關鍵詞的嵌入。

如表 3 所示，在 2000 個查詢中，每個查詢返回的前 5 個關鍵詞的平均質量為「差」、「一般」、「良」或「優」。表 3 中的每一列代表對應於每列標籤的查詢-關鍵詞對數量的百分比差距。例如「良」的結果，rbeGIR 系統分別比 prod_1 和 prod_2 高出了 18.52% 和 11.19%。

為了評估 rbeGIR 系統的召回性能，論文作者首先使用精確的最近鄰演算法，將 1 萬條查詢和 12 億個關鍵詞，與 RBE 嵌入進行匹配。每個查詢的 recall @1000 表示，rbeGIR 獲得的 top 關鍵詞，與相關關鍵詞重疊的總數除以 1000 後的結果。實驗結果顯示，rbeGIR 系統的平均召回率（recall @1000）高達 99.99%。此外，rbeGIR 系統的平均延遲時間為 31.17 毫秒，這充分體現了該系統的實時檢索能力。

2.3 基於 GPU 的窮舉 k-NN 選擇演算法

rbeGIR 系統的一個重要組成部分是，可用於十億級檢索的窮舉 k-NN 選擇演算法。該演算法從局部的分段處理開始，它依賴於 k-NN 內核（如 Algorithm 1 所示）。該演算法將查詢和每個關鍵詞的 RBE 嵌入作為輸入，並輸出一個具有最高相似度得分和索引的優先隊列（priority queue）。輸出的優先隊列被傳輸給全局選擇和合併選擇過程，從而獲得排序最靠前的關鍵詞。全局選擇和合併選擇都採用了 Radix 排序方法 [9]，這也是最快的排序演算法之一。

3. 結論

這篇論文介紹了一種可為十億級信息檢索任務生成語義向量表徵的 RBE 模型，它能在 GPU 上存儲和運行。RBE 表徵可以進一步與窮舉 k-NN 搜索相結合。此外，文中實現的 rbeGIR 系統，是利用深度學習演算法和強大 GPU 算力的一次早期嘗試。

論文作者指出，RBE 表徵不局限於 CLSM 模型。如圖 5 所示，未來 RBE 的概念可進一步泛化到語義哈希 [10] 或 word2vec [11] 等網路中。

圖 5：RBE 的概念可以推廣到其他網路，如語義哈希（左圖）和 word2vec（右圖）。

參考文獻：

[1] Sanderson, M., and Croft, W. B. The history of information retrieval research. Proceedings of the IEEE 100, Special Centennial Issue (2012), 1444-1451.

[2] Salton, G., Wong, A., and Yang, C.-S. A vector space model for automatic indexing. Communications of the ACM 18, 11 (1975), 613-620.

[3] Weber, R., Schek, H.-J., and Blott, S. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB (1998), vol. 98, pp. 194-205.

[4] Aggarwal, C. C., Hinneburg, A., and Keim, D. A. On the surprising behavior of distance metrics in high dimensional spaces. In ICDT (2001), vol. 1, Springer, pp. 420-434.

[5] Friedman, J. H., Bentley, J. L., and Finkel, R. A. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS) 3, 3 (1977), 209-226.

[6] Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. S. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry (2004), ACM, pp. 253-262.

[7] Garcia, V., Debreuve, E., and Barlaud, M. Fast k nearest neighbor search using GPU. arXiv preprint arXiv:0804.1448.

[8] Shen, Y., He, X., Gao, J., Deng, L., and Mesnil, G. A latent semantic model with convolutional-pooling structure for information retrieval. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management (2014), ACM, pp. 101-110.

[9] Merrill, D. G., and Grimshaw, A. S. Revisiting sorting for gpgpu stream architectures. In Proceedings of the 19th international conference on Parallel architectures and compilation techniques (2010), ACM, pp. 545-546.

[10] Salakhutdinov, R., and Hinton, G. Semantic hashing. RBM 500, 3 (2007), 500.

[11] Mikolov, T., Chen, K., Corrado, G., and Dean, J. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013).

本文為機器之心原創，轉載請聯繫公眾號獲得授權。

------------------------------------------------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！