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

http://cvpr2019.thecvf.com/

KDD 2020

https://www.kdd.org/kdd2020/

Top Conference Paper Challenge:

https://medium.com/@arthurlee_73761/top-conference-paper-challenge-2d7ca24115c6

My Website:

https://light0617.github.io/#/

--

--

An machine learning engineer in Bay Area in the United States

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Arthur Lee

Arthur Lee

An machine learning engineer in Bay Area in the United States