論文連結 Paper Link
Wide for memorization. Deep for generalization.
介紹 Introduction
推薦系統可以看作是一個 search ranking system，其中 input query 是一組 user 和 contextualized information，output 是排序後的 items。推薦系統中的一個挑戰是同時實現 Memorization 和 Generalization。Memorization 可以粗略地定義為學習歷史資料中的物品或特徵的共現頻率的能力。Generalization 則是基於 transitivity of correlation，並探索過去從未或很少發生的新特徵組合與最後 label 的關係的能力。基於 Memorization 的推薦通常更具主題性，並且與 user 已經有過的 history action 有關。而 Generalization 傾向於提高推薦 items 的多樣性。在這篇論文中，作者專注於 Google Play 商店的 apps 推薦，但這個方法與模型適用於一般的推薦系統。
對於業界的大規模 Online 推薦系統，Generalized linear model (e.g. logistic regression) 被廣泛使用，因為簡單可擴展且具解釋性，通常使用 One-hot Encode 對 binary sparse features 進行訓練。例如：
“user_installed_app=netflix”
其value=1，代表用戶安裝了Netflix這個應用程式Cross-product transformations over sparse features 可以有效地實現 memorization，例如：
AND(user_installed_app=netflix, impression_app=pandora”)
代表user已經安裝了Netflix，且在Google play上面看到過pandora這個app如果以「最後是否安裝 pandora」為 label，則模型可以輕易的統計出 netflix 和 pandora 這個 features 和安裝 pandora 這個 label 的 co-occurrence。假設 co-occurrence 高達 10%，特徵關聯很強，那設計模型時只要模型發現有這樣的現象，他就推薦 pandora 給使用者，這樣的能力即為記憶能力 memorization。但是 Cross-product 其中的限制是它們不能 generalize 那些未出現在訓練資料中的 query-item feature pairs。
Embedding-based Model (e.g. Factorization Machine / DNN) 可以藉由為每個 query 和 item feature 學習低維度稠密向量來泛化到以前未見的 query-item feature pairs，進而減少特徵工程。然而，當底層查詢項矩陣 sparse 且 high-rank 時，很難為 query 和 item 學習有效的 low-dimensional representation (e.g. users with specific preferences / niche items with a narrow appeal)。在這種情況下，query-item pairs 不太有 interaction，但是 dense embedding 可以有能力讓所有 query-item pairs 的預測為 non-zero，因此可能會 over-generalize 並給出相關性較低或不相關的推薦。
本文的 Wide & Deep 學習框架(如下圖)，同時訓練 linear model 以及 DNN，結合推薦系統的 Memorization 和 Generalization 的優勢。雖然這個想法很簡單，但實驗顯示這個模型顯著提升了 app acquisition rate，同時滿足訓練和服務速度的要求。
The main contributions of the paper include:
1. The Wide & Deep learning framework for jointly training feed-forward neural networks with embeddings and linear model with feature transformations for generic recommender systems with sparse inputs.
2. The implementation and evaluation of the Wide & Deep recommender system productionized on Google Play, a mobile app store with over one billion active users and over one million apps.
3. We have open-sourced our implementation along with a high-level API in TensorFlow.
模型架構 Model Architecture
Overview of the App Recommender System
App recommender system 的 overview 如上圖所示。當 user 點進來 app store 時，會產生一個 query，他可以包括各種 user 和 contextual features，此時推薦系統會 return a list of apps (a.k.a. impressions)，user 可以在 app 上執行某些操作，例如點擊或購買。這些 user actions 連同 query 和 impression 一起記錄在 logs 中，形成訓練資料集。由於 database 中有 1M+ 個 apps，很難在 serving latency requirements 內對每個 query 的每個 app 進行詳盡的 scoring。因此，收到 query 的第一步是檢索 retrieval。檢索系統 retrieval system 返回與 query 最匹配的項目的 short list，通常是 ML model 和人工定義規則的組合。減少候選的 pool 後，排序系統 ranking system 按所有 items 的分數 P(y|x) 進行排序。
P(y|x), the probability of a user action label y given the features x, including user features (e.g., country, language, demographics), contextual features (e.g., device, hour of the day, day of the week), and impression features (e.g., app age, historical statistics of an app).
The Wide Component
Wide component 是 y = wT x + b 形式的 generalized linear model，y 是 prediction，x = [x1, x2, …, xd] 是 1*d 的 feature vector，w = [w1,w2,…,wd] 是 1*d 的 weights，b 是 bias term。Feature set 包含原始的輸入特徵以及經轉換後的特徵，其中最重要的一個特徵轉換為：Cross-product transformation：
對於 binary features，只有當組成的特徵都是 1 時，Cross-product transformation 的值才會是 1，否則為0。這捕捉了 binary features 之間的 interaction，並為 generalized linear model 增加了 non-linearity。
E.g. “AND(gender=female, language=en)” = 1 when “gender=female” & “language=en” are all 1s.The Deep Component
Deep component 是一個 Feed-forward NN，對於 categorical features，原始輸入是 feature string (e.g. “language=en”)，這些稀疏且高維的 categorical features 都先轉換為低維且密集的實數值向量，即 Embeddings。Embeddings 的維度通常在 O(10) 到 O(100)，被隨機初始化後跟著模型訓練。最後，這些 low-dimensional dense embeddings 會被傳入 hidden layers 進行深度學習。具體來說，每個 hidden layer 會執行以下的運算：
Joint Training of Wide & Deep Model
如何組合 wide component 和 deep component？作者使用它們的 weighted sum of output log odds 來輸出 prediction，然後將 prediction 餵給 logistic loss function 進行 joint training。
Ensemble v.s. Joint Training (Learning)
In an ensemble, individual models are trained separately without knowing each other, and their predictions are combined only at inference time but not at training time. In contrast, joint training optimizes all parameters simultaneously by taking both the wide and deep part as well as the weights of their sum into account at training time. There are implications on model size too: For an ensemble, since the training is disjoint, each individual model size usually needs to be larger (e.g., with more features and transformations) to achieve reasonable accuracy for an ensemble to work. In comparison, for joint training the wide part only needs to complement the weaknesses of the deep part with a small number of cross-product feature transformations, rather than a full-size wide model.
Wide & Deep 模型的 joint training 是用 mini-batch stochastic optimization 同時將 gradient 從輸出結果 back-propagate 到模型的 wide & deep part。在實驗中，作者使用 Follow-the-regularized-leader (FTRL) 的方法，其中 L1 regularization 作為模型 wide part 的 optimizer，AdaGrad 則用於 deep part。對於此 Logistic Regression Problem，模型的預測是：
實驗 Experiments
Apps Recommendation Pipeline 的實現包括三個階段：數據生成 data generation、模型訓練 model training 和模型服務 model serving。(如上圖)
Part1. Data Generation
在這個階段，會使用某一段時間內的 user 和 app impression data 作為訓練資料。每筆資料對應一個 impression，Label 是 app acquisition：如果安裝了 impression app 為 1，否則為 0。此外，Vocabularies 將 categorical feature strings 映射到 integer IDs 也會在這個階段生成。這邊作者有設定一個 Threshold，當這個 string 的出現次數超過某個值之後，才會把它映射到 ID space。那對於那些 continuous real-value features 會把它映射到 cumulative distribution function (cdf) P(X ≤ x) 並 normalize 到 [0,1] 之間，切割成 nq 個 quantiles，其中 i-th quantile 的值，normalized value = (i - 1) / (nq - 1)。
Part2. Model Training
整個 Wide & Deep 在訓練的資料與模型如上圖。Input layer 接收訓練資料和 Vocabulaires，生成 sparse & dense features 以及 label。Wide part 只包含 user installed apps & impression apps 的 cross-product transformation。Deep part，為所有 categorical features 學各自 32 維的 embedding。將所有 embeddings 與 dense features 給 concatenate 在一起，得到一個大約 1200 維的 dense vector，然後傳入 3 層 ReLU，最後輸出到 logistic unit。
Wide & Deep 模型在 500B+ examples 上進行訓練。當有新的訓練資料要進來時，模型都需要重新訓練。但是，每次從頭開始重新訓練的計算成本很高，而且會延遲從接收數據到提供新模型的時間。對此，作者提出一個 warm-starting system，系統使用來自 previous model 的 embedings and linear model weights 來初始化 new model。
IMHO: 總之就是把之前的模型當作 Pre-trained Weights 餵進來！
Part3. Model Serving
模型經過訓練和驗證後，將其 load 到 model server。對於每個 request，server 會從 app retrieval system 和 user features 接收 a set of app candidates，對每個 app 進行評分(scoring by wide and deep model)並排名，按順序推薦這些 apps 給 user。為了在大約 10 ms 的時間內處理每個 request，使用了 mini-batch 來做 multi-threading parallelism 優化效能，而不是在 single batch inference step 對所有 candidate apps 評分。
Experiment Results: Part1 — App Acquisition
作者執行了三週的 A/B Test。對照組：隨機選擇 1% 的 users，提供給他們由前一版本的模型生成的推薦 (模型為高度優化的 Wide-Only 的 logistic regression model，具有豐富的 cross-product feature transformation)。實驗組：提供 1% 的 users 由 Wide & Deep 模型生成的推薦。這些模型使用相同的 feature set 進行訓練。數據結果如上表。此外，作者還在 offline holdout set 計算 AUC (Area Under Receiver Operating Characteristic Curve)。雖然 Wide & Deep 的 offine AUC 僅略高一點，但對 online traffic 的影響極為顯著。作者提出可能原因為 offline dataset 的 impression 和 label 是固定的，而 online system 可以透過將 Generalization 與 Memorization 相結合來生成 new exploratory recommendation，並從新的 user responses 學習。
Experiment Results: Part2 — Serving Performance
以 high throughput 和 low latency 提供服務是 commercial mobile app store 面臨的高流量挑戰。在流量高峰時，recommender server 每秒為超過 10M+ 個 apps 評分。使用 single thread，在一個 batch 中對所有 candidate apps 進行評分需要 31 ms。作者用 multi thread 有效將 client-side latency 降低到 14 ms。
結論 Conclusion
Memorization & Generalization 對於推薦系統都很重要。Wide linear models 可使用 cross-product 做 feature transform 有效地記憶 sparse features’ interaction，而 DNN 深度神經網路可以通過低維度的向量泛化到先前沒看過的 feature interaction。Wide & Deep 的優勢：
- 抓住問題的本質，結合傳統模型的記憶能力以及深度學習的泛化能力。
- 模型結構並不複雜，利於真實世界的上線、訓練、與部署。
參考資料 Reference
- 帶你學深度學習推薦系統 by 王喆
This article will be updated at any time! Thanks for your reading. If you like the content, please click the “clap” button. You can also press the follow button to track new articles. Feel free to connect with me via LinkedIn or email.
