CIKM 2021 | BH：面向Web级应用的基于二进制码的Hash Embedding
??摘要
現如今，深度學習模型被廣泛的應用于 web 級應用中，比如推薦系統，廣告系統等等。在這些應用中，ID類特征的表示學習(embedding learning)是這些模型成功的關鍵之一。其標準的模式是，為每一個特征值學習一個特征向量。盡管，這種方法能夠刻畫不同特征的特性，有效提升模型的精度。但是，存儲這樣的?embedding 將會消耗大量的空間，極大的約束了這類深度模型的應用和迭代。這樣的問題，對于 web 級應用而言尤為嚴重。在本文中，我們提出了基于二進制碼的 hash embedding 學習，能夠任意比例的壓縮存儲空間的同時基本維持模型的精度。實驗結果表明，模型存儲大小縮減1000倍的時候，仍然能維持原有模型的99%精度。目前，該工作已被 CIKM 2021 接收。
論文下載：
https://arxiv.org/pdf/2109.02471.pdf
??1. 背景
ID類特征的表示學習(embedding learning)在基于 embedding 的深度推薦模型(EDRMs)中起著至關重要的作用。一個經典的 embedding learning (稱為 full embedding)的目標是為每一個特征值學習一個特征向量。具體來講，設為一種ID特征(比如user ID 或者 item ID)，為該特征的詞典大小(即特征值的 unique 數)，對于每一個特征值賦予一個 embedding 的索引(index) , 通過, 找到 embedding 矩陣()中的第行，將該行作為的特征向量 (其中，為 embedding 維度，在 full embedding 中 ，見圖1(a))。
圖1 不同方法之間的比較。Step 1,2,3 分別指特征hash、embedding索引生成、embedding向量生成。然而，full embedding 方法面臨著嚴重的存儲問題。因為，存儲 embedding 矩陣的開銷是隨著線性增長的。
對于一個web級應用而言，的大小可能是億級別的，導致 embedding 矩陣需要巨大的存儲空間。比如，假設為5百萬，，那么對應的開銷為475G。
在實際應用中，如此具大的存儲開銷將會極大的約束模型的部署和應用，尤其是對于一些存儲敏感的場景(如部署在移動設備上)。
因此，減少 embedding 矩陣存儲開銷變得尤為重要，針對該問題，主要會面臨兩大挑戰：
高靈活： 不同的場景對于存儲的約束是不同的(比如分布式服務器和移動設備)。因此，減少 embedding 存儲的方法需要足夠的靈活，來滿足不同場景的 embedding 需求。尤其是對于移動設備而言，一個輕量級的模型是迫切需要的。
效果不降： 一個大模型擁有更多的參數，更多的容量，往往能夠取得更好的效果。然而，縮減模型存儲勢必會減少模型的參數，很有可能帶來模型效果上的損失。因此，在模型存儲減少的同時，如何保持模型的效果不降是一個極大的挑戰，尤其是對于存儲敏感的場景而言。
整體上講，減少 embedding 存儲可以從兩個角度來考慮(1)減少每一個 embedding 向量的大小(即減小)。(2)減少 embedding 向量的個數(即減少)。然而前者雖然能減少存儲，但其存儲開銷仍然隨著線性增長，因此不是一個較優的選擇。現有的大部分工作主要集中在如何減少。這類工作主要采用hash取模的方法(如圖1(b)所示)，其核心思想是對每一個特征值的 Hash ID 進行取模(設模數為)，然后將取模后的余數作為 embedding 的索引（比如 Hash Embedding[1] 方法）。這樣一來，embedding 的存儲開銷可以從減少到。但是這類方法的問題是會使得不同的特征值映射到相同的索引值，導致對應相同的 embedding 向量，這使得模型無法區分這些特征值，損失模型效果。該問題在構建輕量級模型的時候尤為嚴重。盡管，后續方法比如（Multi-hash[2],Q-R trick[3]）都嘗試緩解取模操作帶來的索引沖突問題，但都無法同時解決靈活性和效果問題。
在本工作中，不像現有的采用取模操作的工作，我們另辟蹊徑，利用二進制碼 binary code（比如13的二進制碼為）來唯一對應每一個特征值的 Hash ID，并提出 Binary code based Hash embedding(BH) 來解決 embedding 存儲大的問題。具體來講，我們先將每一個特征值的 Hash ID 轉換成二進制碼。然后，設計 code block strategy 來靈活的調整 embedding 存儲的大小(解決挑戰1)。為了盡可能保留模型效果(挑戰2)，不論 embedding 縮減成多大，我們都能夠為不同的特征值賦予不同的索引值。這樣以來，模型就很容易能夠分辨不同的特征值，從而提升模型的表達能力和效果。此外，BH 的索引值是實時計算出來的，不需要提前存儲索引值，這樣一種模式有利于處理新 ID 的情況。
??2. 模型：Binary Code Based Hash Embedding
在這一章，我們將介紹所提的模型。如圖2所示，Binary code based Hash embedding(BH)分為3步，即特征hash、embedding索引生成、embedding向量生成。
2.1 特征Hash
在實際過程中，ID類特征的原始類型可能是多種多樣的，比如String或者Integer。為了統一不同類型的ID特征，在實際中，經常通過特征Hash[1,2,3]將ID的原始值映射成Integer,稱為Hash ID(如圖2所示)。特征Hash可以被形式化的表達為
其中為 Hash 函數(如Murmur Hash [4]),為特征值的 Hash ID。在實際中，的輸出空間會被設為足夠大 比如(為64-bit整數)來避免之間的Hash沖突。在這種情況下，不同的都有一個唯一的與之對應 [5,6]。
2.2 Embedding 索引生成
Embedding 索引生成主要分為3步：Binarization、Code Block Strategy和Decimalization。
2.2.1 Binarization
在特征 Hash 之后，每一個特征值都會都會有一個唯一的 Hash ID。我們首先將這樣一個整數轉化成二進制碼的形式(表示二進制碼的長度),比如13的二進制碼是。需要注意的是二進制碼仍然與特征值一一對應。
2.2.2 Code Block Strategy
為了能夠靈活的縮減 embedding 的存儲大小，我們提出了Code Block Strategy。
簡單來講，Code Block Strategy 會把中的每一個0-1值分到不同的 block。然后，每一個 block 的 0-1 值可以有序的組成一個 0-1 碼來表示個整數(其中n是每個 block 中0-1的個數)。然后將每一個 block 的 0-1 碼轉換成一個十進制值，將該值作為 block embedding 矩陣的embedding索引。這樣一來，一個特征值的所有block合在一起就唯一確定了該特征值，同時embedding存儲的大小可以靈活的被參數所控制。比如當時，即每個 block 僅有 2 個 0-1 值，embedding 存儲的開銷是。當所有 0-1 值放在同一個 block 的時候，存儲開銷是(相當于Full embedding)。換而言之，通過調整,我們能夠靈活的調整 embedding 大小來滿足不同場景的存儲限制。
形式化講，我們定義為Code Block Strategy產出的的block序列，那么第個block 可以被表示為
其中 是一個分配函數，將每一個 0-1 值分配到不同的 block里。將每個 block 里的0-1值變成有序的 0-1 碼。在這里，我們給出兩個 code block strategies （即 Succession 和 Skip）的例子來展示其是如何起作用的，其他合適的 code block strategies 也都可以被應用。
Succession： 如圖3(a)所示，Succession 從左到右遍歷，每個0-1值分到同一block。 為保持在中原有的順序。注意的是，當最后剩余的 0-1 值不夠時，將剩余的所有 0-1 值放到一個新的 block 中。
Skip： 如圖3(b)所示，Skip 將間隔為的 0-1 值放入同一個 block 中。與Succession一致。
這樣以來，通過 Code Block Strategy，對于每一個,我們可以得到唯一的。也就是說，Code Block Strategy 的過程是一個信息無損的過程。
2.2.3 Decimalization
每一個 block 的 embedding 索引可以通過將轉成十進制值得到，即
比如。
2.3 Embedding向量生成
通過 Code Block Strategy，我們可以為每一個特征值得到多個 embedding 索引。然后，我們通過 embedding lookup 和 embedding fusion 得到對應的 embedding 向量。
2.3.1 Embedding lookup
如前文所介紹，每一個block可以得到一個索引。總共有個。我們可以將每一個 embedding 索引映射成一個 embedding 向量，
其中是第 m 個 block 的 embedding 矩陣，為的 embedding 向量。是 lookup 函數，其返回的第行。此外，為了經一步減少 embedding 存儲開銷，我們讓不同的 block 共享同一個 embedding 矩陣。
2.3.2 Embedding Fusion
Embedding Fusion 函數將所有 block embedding 整合起來，得到特征值最后的 embedding 向量,
其中，Fusion 函數的設計多種多樣，比如 pooling，LSTM，Concatenation 等等。在本工作中，我們采用了 sum pooling 作為默認的 Fusion 函數。
2.4 討論
2.4.1 優勢
這里簡單概括一下所提方法的優越性。
確定性： embedding 索引的產生是一個確定性的無參的實時計算過程，該特性對于新ID的索引計算是十分友好的。
靈活性： embedding 的大小能夠靈活的被超參所調整。這樣一種性質，使得模型能夠被部署在存儲敏感的場景中(如移動設備)。
唯一性： 不論 embedding 縮減到什么程度，始終與特征值一一對應，也就是說不同的有不同的，使得模型能夠很容易的區別出不同的特征，提高模型的表達能力。
2.4.2 和現有方法的關系
Full embedding： 本文所提方法和 Full embedding 都能夠很好地區分不同的特征。而本文方法能夠進一步的減少 embedding 存儲大小。
Hash embedding： 該方法可以看作是本文的一個簡化版。其中，code block strategy 是 Succession 并且僅前個0-1值作為embedding索引。
Multi-Hash Embedding： 本文方法和 Multi-Hash Embedding 都采用的多個 embedding 索引的模式，不同的是，本文對這些索引之間做了唯一性的約束。
Q-R Trick： 該方法可以看作是本文的一個特殊的 case。其中 code block strategy 是 Succession，且 block 的個數為2。然后前個作為 Q-R Trick 的 quotient，剩下的做為 remainder。
??3. 實驗
3.1 實驗設置
數據集
Alibaba
Amazon
MovieLens
Baselines
Full Embedding(Full)
Hash Embedding (Hash)
Multi-Hash Embedding (MH)
Q-R Trick (Q-R)
3.2 CTR 預估任務
我們分別在阿里內部數據和公開數據上做了 CTR 任務的評測。記錄了不同存儲縮減倍數下，模型的效果表現。
如表1所示，可以看到，相比于基于取模的方法和原始的 Full embedding。所提 BH 方法在不同縮減程度下，都取得了最好的效果。并且縮減倍數越多時，效果越好。
表1.CTR預估任務結果3.3 存儲開銷比較
為了比較，縮減 embedding 存儲的能力。我們分別比較在不同縮減方法下取得原模型(Full embedding)99% 效果的時候，能夠縮減的程度。
如表2所示，當都取得原模型 99% 的效果的時候，BH 的模型大小是原先的1000分之一。遠遠小于其他模型大小。這樣一個效果，能夠為移動場景的應用提供良好的條件。
表2.模型縮減能力對比3.4 不同 Code Block Strategy 比較
我們比較了 Succession 和 Skip 兩種 Code Block Strategy 的效果，如表3所示，兩種方式不相上下，且相比于最好的 baseline(Q-R) 均能夠取得更有的效果。
表3.不同Code Block Strategy比較3.5 收斂性比較
我們還比較不同模型的收斂快慢，如圖4所示，相比于模型縮減的方法，所提 BH 方法在 test 的 auc 上收斂更快并更高，loss 上也更小。
圖4. 收斂性比較??4. 結語
通過構建無損的 embedding 索引來獲取不要特征值的 embedding，來使得模型在縮減大小時仍然能夠擁有良好的效果。BH 是我們團隊在模型瘦身(繼FCN-GNN[7]之后)上在一次發力。希望后續能夠在該方向上帶來更多更好的作品。
Reference
[1] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. 2009. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning. 1113–1120.
[2] Dan Tito Svenstrup, Jonas Hansen, and Ole Winther. 2017. Hash embeddings for efficient word representations. Advances in neural information processing systems 30 (2017), 4928–4936.
[3] Hao-Jun Michael Shi, Dheevatsa Mudigere, Maxim Naumov, and Jiyan Yang. 2020. Compositional embeddings using complementary partitions for memory-efficient recommendation systems. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 165–175.
[4] Fumito Yamaguchi and Hiroaki Nishi. 2013. Hardware-based hash functions for network applications. In 2013 19th IEEE International Conference on Networks (ICON). IEEE, 1–6.
[5] Wang-Cheng Kang, Derek Zhiyuan Cheng, Tiansheng Yao, Xinyang Yi, Ting Chen, Lichan Hong, and Ed H Chi. 2020. Deep Hash Embedding for Large-Vocab Categorical Feature Representations. arXiv preprint arXiv:2010.10784 (2020).
[6] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. 2009. Feature hashing for large scale multitask learning. In Proceedings of the 26th annual international conference on machine learning. 1113–1120.
[7] Li F, Yan B, Long Q, et al. Explicit Semantic Cross Feature Learning via Pre-trained Graph Neural Networks for CTR Prediction[J]. SIGIR 2021.
END
歡迎關注「阿里媽媽技術」，了解更多~
瘋狂暗示↓↓↓↓↓↓↓
總結
以上是生活随笔為你收集整理的CIKM 2021 | BH：面向Web级应用的基于二进制码的Hash Embedding的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 2篇CIKM详解阿里妈妈搜索广告CTR模
- 下一篇： 【阿里妈妈营销科学系列】第一篇：消费者资