KDD 21':Learning to Embed Categorical Features without Embedding Tables for Recommendation (google)
🤗 Recommendation system paper challenge (30/50)
paper link Google KDD 2021
🤔 What problem do they solve?
background:
當我們推薦系統使用embedding features並且在做model serving時候,我們需要一個”機制/方法”還查找這個feature對應的embedding
舉例來說,當我們有item_id,然後需要在serving時候知道item_embedding
傳統做法 (big lookup table):
就是有一個lookup table (key: feature, value:embedding)
以剛剛的例子來說,假設我們有1B的item_ids,然後每個item_embedding length is 100,我們就需要一個大table(1B * 100)
BUT! 這方法有兩個問題
- 當item_ids太多,導致table太大塞不下memory
- 有新的item出現,要一直成長我們的table
提出的方法 (Deep Hashing embedding)
做encoding, decoding
- encoding又分為hashing + transform
- hashing: 用大量的hashing (k個不同的hashing functions),把一個item_id轉乘k維的vector (一個hash轉乘一個數字,有k個hash就有k個數字,把他們concate一起形成k*1維的vector)
- transform: 針對”k*1維的vector”去做normalization (uniform or Gaussian),主要是把entropy越高越好(每一個維度的數字分配越平均越好,1-hot-encoding就是entropy很低,1-d value-vector則是最高),output一樣是k*1維的vector
- decoding 則是把output from transform, 拿來跑DNN (MLP)希望讓network去學怎麼把transform後的vector對應回我們要的embedding
過度方法:hashing -> reduce dimension
中間本篇論文也提到中間一些過度方法,例如其他人如何解決lookup table過大問題,基本上就是hash trick在做mapping來降低維度,進而降低lookup table大小(從n -> m)
但hashing又會衍生其他問題, 例如collision (可以想像pizza, car發生collision後map到同一個embedding嗎?), 這可能導致performance下滑
其他衍生做法避免collision也只是多加幾層hashing,但不管怎麼加就是會平均有 n/m個collision發生(原本n個item, 後來的m個維度)
以上三個詳細data flow流程如下圖
😎設計巧思
接著作者來說明如何設計出這個encoding跟decoding
定義好的encoding
首先作者定義什麼是好的encoding,最好滿足以下條件
- Uniqueness
- Equal Similarity
- High dimensionality
- High Shannon Entropy
Uniqueness: 唯一性
首先如果發生collision就不滿足了,所以其他只要用了hashing來降維就不滿足,但是為什麼作者也用hashing卻滿足了呢?因為作者的hashing是map到一個自然數空間[1,…m],可以是非常大的值域,paper上用了10⁶當作空間的大小,有k個hashing function,就有k個整數形成的vector,雖然也是降維,但實際可能降很少,而且從機率看,幾乎不可能發生collision,如果發生,也可以輕易調整m因為跟最後的emb大小無關
Equal Similarity
相似性,相似的vector應該要代表他們是相似的,這有點抽象,來舉個例子
像是7,8,9應該是”7跟8距離” 與 “8跟9距離”一樣,但如何我們用binary representation, H(7) = [0,1,1,1], H(8) = [1,0,0,0], H(9)=[1,0,0,1] 如果我們用Hamming distance去測量會發現7,8更接近但是這是錯的
而當我們用hashing也會有問題,因為我們hashing之前是item_id並沒有semantic,我們就直接說會collision的兩個item_id是一樣的,也是不準確
而因為我們的方法DHE,用非常大的數字hash,幾乎不用有collision發生,所以也就沒有不同item碰再一起的情況
High dimensionality
這是說明要節省空間,當我們用1-hot-encoding,太浪費空間;當我們用identity-encoding雖然用很小空間,但此造成訊息流失使得decoding更加困難
而我們方法DHE, encoding大小適中,這也是為什麼他要把hashing變成一個整數而不是一個1-hot-encoding (using k x 1 instead of (m*k) x 1)也是為了要節省空間,但同時讓k變大來增加訊息量,可以看成每一用一個hashing就是從不同角度看原本的item
High Shannon Entropy
The Shannon entropy measures (in the unit of ‘bits’) the information carried in a dimension
越高的entropy越能避免浪費維度
所以最高的entropy就是用identity-encoding因為他只用一維度就可以,而且這個維度每個數字發生次數都一樣(uniform distribution),最低的最浪費的就是1-hot-encoding(每個維度99.999%都是0,非常skewed)
而我們DHE用general的hashing,他會平均地把value分配到1到m的數字上,以藉此提高entropy
設計decoding
因為我們的decoding要用deep neural network,最好的input不是一個整數而是real-valued,且normalized最好, 所以我們可以加一下transform在前面(類似GAN的做法);
- Uniform: [-1, 1]
- Gaussian distribution
心得
這篇論文非常實用,尤其是當categorical feature ids非常巨大的時候,大到塞不進memory
Serving Latency?
但我也思考了serving latency不知道是否會增加? hashing 可能還好,計算量算不多,作者也提到可以用GPU, TPU加速, 但decoding這一塊DNN不知道latency增加的如何,如果對於小categorical data也許還是直接lookup table更加naive而且維護成本更低
Cold-Start problem?
雖然作者提到他解決了out of table問題,因為table是固定,隨著新item加入可能查不到,而DHE是用general hashing在用DNN,兩者都沒limitation,大不了map到奇怪得數字/vector, decoding看似學item_id對應到embedding的關係,如果是feature value本身就包含semantic那可能可以學得到,還可以舉一反三,但如果input feature是item_id = 1, 2, 3, 4這種沒有任何semantic information,可能很難舉一反三,還是會suffer cold-start problem
版本問題?
與lookup table一樣,有新的item加入或是新的model,我們都要重新學習neural network
結語
看完了這篇paper收穫非常多,這篇非常實務,加上最近有些類似的工作經驗更能體會這篇paper的強大之處
🙃 Other related blogs:
KDD 19': Sampling-bias-corrected neural modeling for large corpus item recommendations
KDD 19': Heterogeneous Graph Neural Network
KDD 19': Applying Deep Learning To Airbnb Search
KDD 18': Real-time Personalization using Embeddings for Search Ranking at Airbnb
KDD 18': Notification Volume Control and Optimization System at Pinterest
KDD 19': PinText: A Multitask Text Embedding System in Pinterest
CVPR19' Complete the Look: Scene-based Complementary Product Recommendation
NAACL’19: Utilizing BERT for Aspect-Based Sentiment Analysis via Constructing Auxiliary Sentence
NIPS’2017: Attention Is All You Need (Transformer)
KDD’19: Learning a Unified Embedding for Visual Search at Pinterest
BMVC19' Classification is a Strong Baseline for Deep Metric Learning
KDD’18: Graph Convolutional Neural Networks for Web-Scale Recommender Systems
🤩 Conference
ICCV: International Conference on Computer Vision
http://iccv2019.thecvf.com/submission/timeline
CVPR: Conference on Computer Vision and Pattern Recognition
KDD 2020
Top Conference Paper Challenge:
https://medium.com/@arthurlee_73761/top-conference-paper-challenge-2d7ca24115c6
My Website: