Google Apps 如何給用戶做應用程式推薦 — Wide&Deep Model
[讀論文] Wide And Deep Learning For Recommender Systems — 2016 Google Inc.
很長的前言 : 推薦系統的經典算法
因緣際會下，最近回過頭研究推薦系統。不知道是不是近期業界發展的原因，聽到越來越多的使用案例，尤其在商業決策圈(相對於產品研發端)而言，基於推薦系統給出的想法做決策的模式似乎越發盛行。
早先我針對這個議題研究過一些經典且泛用的模型，主要就是協同過濾(Collaborative Filtering)與分解機(Factorization Machines)，兩者的思路相對都好懂，但在實際應用上仍有不少缺陷，此外在對於如何定義用戶的喜好這點上而言，其基本假設都是需要再斟酌的。進入正文前，我想花一些時間簡述這兩者的前世今生，包括他們的核心思路，以及其優缺點，然後基於這些差異，去說明 Wide And Deep 架構的精髓。
* 如果你本身對於這些算法已經熟悉，建議直接跳過，看第二段正文
【一、協同過濾算法 Collaborative Filtering】
史丹佛大學著名的人工智慧教授 Andrew Ng 有一個很簡潔易懂的影片教學如下 :
協同過濾實際上要解決的問題就是，在一個用戶/產品的交互矩陣中，我怎麼樣更好的去評估/預測某用戶對某產品的喜好程度，舉例而言，用戶會對其喜好的影片打上評分，於是我們就得到了以下用戶-產品矩陣 :
矩陣中的問號，代表我們想知道消費者對該電影的評分，比如 Alice 看過 Love at last，評分是五分，那麼 Alice 對於 Cute Puppies of Love 的評分是多少？這是我們想知道的問題。一般而言我們可以通過很簡單的外加變量(上途中 x1, x2)用做估計工具，這個外加變量可以是用戶屬性、產品屬性，或等等你想的到能夠派上用場的資訊，比如上述就是將所有電影通過 romance, action 兩種分數來相對描述。
此時，這個問題就變成簡單的優化問題，比如你可以引入回歸中的最小二乘損失函數思想來處理 :
很熟悉且簡單的回歸問題，我要估計一組參數 theta 滿足其與外加變量交替後的結果與實際輸出值要最小 (式子右邊為懲罰項)。比較不一樣的是為了同時估計多種電影，並使其損失函數值最小，我們不能用閉式解去處理，得使用如梯度下降等迭代算法去做，如果到這邊你並不知道怎麼處理梯度下降，建議可以回頭看影片(連結在上面)。
有人就問了，那如果沒有外加變量怎麼辦？想像一個 Youtube 的使用場景，實際我們很難提供每部影片都有預定義的產品屬性，那我們能不能僅針對用戶-產品矩陣本身做優化預測呢？答案是，可以，這就要扯到另外一種算法，也就是矩陣分解。如果對這個詞不熟的話可以參考我之前寫的一篇整理 :
當然，之前是說明矩陣分解方法如何加速某些場景下的運算，但這邊我想要提及另一種思路。我們先專注於 SVD 奇異值分解，我們知道一個矩陣可以分解成如下形式 :
如果 M 是我們的用戶-產品矩陣，那他可以被分解為如上圖的三個子矩陣，這樣的話，如果要預測一個用戶對某產品的分數，那只需要計算 uEv 就好，相當簡單明瞭。不過，SVD 是有基本假設的，他要求矩陣本身不能是稀疏矩陣 (Sparse Matrix)，否則分解上會出現問題。然而大部分情況下矩陣都是稀疏的，因為用戶總不可能看過所有 Youtube 上的影片吧！（聽說你花一輩子時間 24 小時不間斷都看不完）
因此呢，有人提出了改進，比如改採用 FunkSVD 這樣的偽 SVD 算法(也有人稱為隱語義模型) :
參考連結補在上面，我就不詳細說了否則整篇文重點都跑掉了。總之概念就是回歸到最小化損失函數的概念，說一個矩陣 M 可以分解成兩個矩陣 PQ，每個 M 裡頭的元素都是對應的 PQ 兩矩陣裡的元素相乘。那怎麼找 PQ 呢，就是透過最小化 m-pq 這樣的概念去完成的，最小化就不用我多說了，無腦寫成最小平方就對了。
當然，為了解決各種問題，有人提了 BiasSVD，考慮了有外加變量的情況，也就是把 funkSVD + 外加變量(用戶屬性啊、產品特徵等等)，一起拿進來喪心病狂地最小化。或把隱性回饋考慮進來的 SVD++ 啊，就是 funk + 外加 + 隱性回饋，仗著電腦厲害就一股腦往裡面扔變量。(隱性回饋指實際的用戶行為，但無法表現出真正的用戶偏好，比如電影的點擊次數，可能無法真實反映用戶是否喜歡該電影)。好總之，協同過濾到此結束，總歸一句話就是對用戶-產品之間的交互矩陣去做全局優化。
【二、貝氏與圖論算法】
當然，除了以上的矩陣分解思想以外，基於貝氏機率與圖論的理論也可用於推薦系統。其解決的問題以及問題背後的基本假設都與矩陣分解有所不同，舉例而言，我之前介紹過 :
這東西也是我之前寫的文章了，與協同過濾的思想比較不同，他專注於用戶本身，也就是用戶本身對某商品的偏好與其他用戶無關，專注於考慮對該用戶來說，特定商品的偏好是不是高於其他商品。分解的思路與funkSVD有點類似，但採用了最大化後驗機率的方式求解。
那麼這會有甚麼問題呢 ? 實際上與矩陣分解有兩個最大的差異，一是其隱含假設，矩陣分解的核心思路是去相信用戶-產品矩陣的背後是能夠分解為用戶行為矩陣與產品特性矩陣，藉由兩個子矩陣的交叉去模擬出用戶對產品的實際偏好的；而貝氏機率只專注在找出每個本身購買過的商品中，偏好排序是怎麼樣的，藉由最大化這個偏好排序去模擬其他用戶的行為，因此給出的推薦比較像是在茫茫的產品海中，其他人都比較喜歡的特定產品。二是運算中他不是一次做全局優化，而是用排序資料迭代，因此更適合多數產品中要推薦少數強而有力的商品時的情境，相對而言全局性與客製化程度相對不高。
* 補充一下與某學長討論的關於貝氏推薦的一些缺點，主要還是在資料的時間性問題，也就是後驗機率的估計容易被資料的時間侵蝕，尤其以BPR在做偏好排序的時候，不同時間點給出的偏好，實際上是難以放在一起比較的
另一種算法是基於圖論的推薦系統，比如 MIT 實驗室在 2002 年時提出的SimRank，本質上是在尋找圖之間的相似程度，也廣泛用在比如關聯分析、社群網絡分析等算法上，這邊推薦一篇文章 :
其核心思想不複雜，把消費者與商品之間的購買關係想像成圖 G(V, E)，其中Vertex是消費者以及產品本身，Edge代表其有無購買。此時我們想知道兩個Vertex之間的相似度，可以透過以下方式得到 :
有了兩個點的相似度計算方法以後，我們就可以透過 user-to-user，或是 item-to-item 的方式去進行有效推薦，式子的計算迭代方法可以參考上方文章內容，我就不多說了，否則真的要離題太遠。
【三、分解機 Factorization Machines】
先上完整資料。
總之呢，大家也看出來了，矩陣分解的演進就是不斷補足更多的變量，從原先單靠行為矩陣的分解到SVD++時考慮了用戶屬性與隱性反饋，而當然實際應用的時候那增加的變量實在是多如過江之鯽，真實完整的資料集常常長得像這樣 :
包含用戶編號矩陣、產品實際行為矩陣、產品隱性行為矩陣、評分時間，甚至你用戶最近一段時間評分了哪項產品都是一個矩陣，當然以上這些類別那是族繁不及備載，但觀察一下，這樣的數據結構造成的最大問題就是所謂的稀疏性(Sparsity)，這牽扯到傳統推薦算法最令人頭疼的問題之一 : 冷啟動(Cold Start)，也就是通常相較產品數量而言，用戶真正能夠評分，或表現偏好的數量少之又少，但我們又需要這些少數人的行為來做推薦，此時就會面臨到資料一開始沒有蒐集到實際資料時，整個矩陣就會產生高度稀疏性，早成一個推薦算法裡頭的惡性循環。
這個時候引入上面我們提過偽矩陣分解的思路，也就是透過想像一個模擬的矩陣相乘，將其用來近似實際資料，並求最小化其誤差，比如 :
當然，上面是變量組只有兩種的情況，可以想像隨著變量數目增加，式子會無限的增長下去，而又因為數據稀疏的問題，傳統的矩陣分解單純求解效果是不好的。此時，分解機(Factorization Machine)提出了一個類似矩陣分解的方案，那就是對於係數 w 去做分解，將它以另一種形式表達，而非直接進行分解模擬 :
其中的 v 代表的是輔助向量，我們此時可以改寫上式變成 :
為甚麼這樣就能夠改善稀疏性的問題? 這是因為稀疏性原先會造成直接對 W 估計造成困難，但透過將 W = V'V 的矩陣分解，我們可以確定每個對角線的元素 (因為是自己，因此不受稀疏項影響) 都能夠找到對應的 v，也就是 w1 一定等於 v1'v1，同理 w2 = v2'v2，以此類推我們就可以找到確定的分解矩陣 V，當然在線性代數的證明裡頭，說的是對於任何正定矩陣 Mn*n，當 k 足夠大時都可以找到 Vn*k 去做為其近似。這邊我就不細究了，實際也不重要，這裡要介紹的核心思想僅是，在一個高度稀疏的場景裡頭，基於與矩陣分解相似的概念，FM可以更好地解決問題。
當然，FM的表達式如此泛用，以至於在回歸、二分類等問題上也可以用類似的方式去解決，對於一般的回歸當然我們有更快的閉式解，但是當考慮交乘項數目夠多，或是如推薦系統般沒有確定的輸入數值的情況下，FM實際上是更加泛用的，目前也受到業界青睞。不過要補充說明的是，實際上 FM 還是會很大一部分受到冷啟動的影響，只能說對於傳統方法來說，FM 改進了冷啟動問題，但並沒有真正地解決他。
終於要進入正文之 : Wide And Deep 架構簡介
介紹了這麼久，終於要進入正題。前面說明推薦系統算法的前世今生只是個引子，讀者應該不難看出來，整個推薦系統的核心思路就是透過那些已經有表現出偏好行為(不管是訂閱、點擊、評論，看你怎樣定義)的用戶，去預測那些尚未表現出行為的潛在用戶是否可能偏好某產品，而不同的方法論只是在於基本假設不同(如何讓潛在用戶與現有用戶Match)，以及計算迭代的方式不同而已。
然而，不同的方法都可以用兩種屬性去歸納其差異，一種是Memorization，另一種則是Generalization。Memorization指的是透過產品或是變量的關聯性，去探索在歷史資料裡頭的某種關係，比如我們使用外加變量對產品-用戶矩陣做回歸優化，那麼此時過去被挑選過的產品會賦予相對應的變量高度權重，此時做出的推薦很有可能就是過去最熱門的幾樣單品。Generalization則是指去專注於拓展推薦產品的多樣性，而非只是拘泥於過去出現過的組合，但相對地就需要手動去做變量加工，以剛剛的例子而言，我可以很人為地認為只要用戶看了A產品，就會買B產品，進而去給予一個加工過的人工變量，很明顯地這樣做的泛用程度較高，然而精準程度就不好，比方說上面提到的分解機，顯而易見地透過將係數矩陣分解的方式，給予模型一個低秩的嵌入向量，如果對Embedding-Model熟悉的讀者就會發現，其實概念與自然語言處理中常用的概念是一樣的，將高維度的稀疏矩陣去降維分解成嵌入向量，避免掉維度災難導致得過擬合，但精準度則會略有降低。
一般而言不論你選用矩陣分解、貝氏方法或圖論，都還是會面臨到究竟要以那些變量進去學習的問題。而ㄧ般來說Memorization與Generalization就是有如Bias-Variance一般的存在，難以兩者兼得。而這篇論文所提到的其實就是一個能夠兼備兩者的方案。Wide & Deep Structure 中的 Wide 代表廣義的線性模型，可以讓模型學習到過去的歷史資料，而 Deep 則代表深度神經網絡結構，讓模型學習一些不一樣的參數組合，而整個結構就是透過這兩者的交替訓練，進而去最佳化 Memorization 與 Generalization。在進一步說明細節前，我們還是先看一下大方向的架構 :
如上圖所示，整個模型是透過 Wide 結構與 Deep 結構去聯合訓練的，這樣的好處在於同時兼有兩者的效果。實際應用時，就跟一般的推薦系統一樣 :
Wide And Deep 細部結構與模型訓練
在開始之前，先分享我在 Medium 上找到另外一位前輩的文章 :
其實我認為他講的已經非常清楚易懂，並且有附上圖片說明，但我這邊想要從頭順一遍整個文章的思路、數學細節，因為有些子模型的選擇，比如深度結構為何應該使用 Adagrad，是可以根據情況有討論空間的，加上由於該架構簡單易懂，我也想在最後給出一些實作範例，模擬真實情境下的使用，甚至在其結構中加入一些新的組合，嘗試能否給出新的思路。以下進入正題 :
既然整個模型是由 Wide & Deep 兩部分組成，我們就先分開理解兩個部份分別代表甚麼。首先，Wide Component 是一個廣義的線性模型，預測對象當然是該用戶對於某產品的喜好，而 X 是輸入的變量，W 則是估計係數，b 則是偏誤項，到這邊都與我們熟悉的線性回歸並無二致。在這之上，為了考慮跨產品的轉換問題，給出以下定義 :
這是甚麼意思呢 ? 想像我們有 d 個訓練變量，並給定任意一個常數 k，指的是所有可能的變量組合數。假設我們輸入的是 3 個二元變量，如下表 :
那麼，產品交互的變量可能就有以下幾種可能 :
此時，透過上式可以較好地表達出變量的所有組合，並避免掉線性模型本身的線性限制，充分考慮到非線性的組合情況。
Deep 元素則是一個前饋的神經網絡，首先輸入高維度、高稀疏性的向量特徵讓神經網路並手動轉換成低維度、較不稀疏的實數向量(也就是Embedding，對這部分不熟的讀者請參考以下連結)，這個 Embedded 向量通常是透過隨機初始化，隨後透過模型訓練去最小化誤差得到的。得到完整的嵌入向量後，再去餵到神經網絡結構裏頭，後面的事情你我就比較熟悉了，通過 Forward Pass 的方式去過網絡，然後藉由給定的激活函數取輸出。
有人可能會問，那麼 Embedding 是怎麼處理的呢? 這一點在論文中並沒有詳細說明方法，但一般常見的方式是通過一個監督的任務給定一個損失函數，然後通過神經網絡的方式去最小化該損失函數，當然你得指定要轉換的實向量維度，在論文中作者認為通常會在 O(10) 至 O(100) 的區間。
得到 Wide 元素和 Deep 元素後，如同一開始提及的架構，我們要對其進行聯合訓練(Joint Training)，注意這邊的觀念與集成訓練(Ensemble Training)還是不大一樣的，集成指的是把模型分開訓練，彼此訓練時獨立，後續在透過某種方式將其串接起來；聯合訓練則是將 Wide & Deep 的參數同時納進來考慮，旨在縮小這兩者整體的損失，而同時納入的方法則是加權加總，而這個好處是甚麼呢? 也就是不要求像集成模型那樣每個獨立的模型都要有一定的樣本量(否則單一基模型的效果太差，再怎麼後續組合也不會變好)，每個聯合訓練的子模型可以是相對小的樣本，這尤其在產品數量大時能派上用場。
如何聯合訓練呢? 作者給出的方法是，對於兩者模型的產出，透過反向傳播的方式，對梯度進行小批次隨機優化的方式去處理。而兩者模型是如何分別優化的 ? 在論文的實驗中，Wide 部分使用的是 FTRL 演算法，並使用 L1 正則化，為了讓參數解相對稀疏；Deep 部分則使用 AdaGrad 處理。至於 FTRL 演算法實際上是一個線上凸函數優化 (Online Convex Optimization，表示隨著時間經過會時刻進行的凸函數優化) 的經典方式，有興趣的讀者可以參考以下連結 :
簡單說明一下即可，OCO 最大的不同是在於其優化的目標損失函數是有時間性的，也就是相比於 loss(y)，實際上你得到的是 loss(yt)，這時候我們需要一個 Regret 項 :
這個概念是甚麼意思呢? 就是說隨著你時間不同，所收到的損失函數值也會不同，有高有低。既然這樣，我怎麼知道在經過時間 T 後，我的模型訓練效果究竟是好或不好? 解決方法通常是設定一個基準，稱為 Expert's Advice，根據模型在時間 T 後的總損失函數與專家建議相減，去得到一個基準 Regret 項用做後續的評判標準。
FTRL 的概念就是希望不管在任何時間 t，我的 Regret 都不要太大，因此在時間 t 的時候，雖然我的資訊只有 t-1 往前的資料，但我可以藉由模擬猜測時間 t 時候損失函數的值，去給予他一個區間，藉此去找出最佳步驟。詳細的請參考上面的連結，已經講得非常清楚。
而 AdaGrad 因為相對有名，我就不廢話了，對於梯度最佳解的常見演算法有興趣的，可以參考這篇 :
總之，一路到這邊，我們對於 Y 的估計式就可以用很漂亮的一行式子表達 :
當然，最外面那層函數如果是以 0, 1 的二元表達為目標，就會是 sigmoid 函數，A^l(f)指的是深度結構中的最後一層 layer 給出的係數。至此，整個學習結構就結束了，非常的簡潔有力。
透過 Tensorflow API 訓練模型
Google用該算法做為 Google Apps 的推薦系統模型，並將實作方法與教學做成了 Tensorflow API，放在以下的連結中 (Tensorflow 0.12版本):
這是一段 207 行的程式碼，使用 tf.learn API，由於相對其他的深度學習模組，tensorflow的運作功能複雜且多元，因此這裡簡單說明一下運行邏輯 :
首先，程式碼是使用 tf.app 這個模組來執行的，在開始的時候調用了 tf.app.flags，這東西是用來模擬命令行傳送參數使用的。甚麼意思呢? 如果你寫了以下的程式碼 :
你就可以在 Command Line 輸入如 : python XXX.py —learning_rate 0.05，這樣的方式去更改程式碼吃到的參數，在執行上還挺方便的。
這段程式碼的用途是獲取資料，如果執行時沒有傳入資料的話，那麼就會透過 urllib.request 函數去將資料下載下來，如果你將其另外拉出來保存成 csv 的話，形式會像是這樣 :
Columns 過多我就分開截圖，可以看到整個資料集與我們熟悉的格式還是滿相近的，包含用戶編號(Primary Key)，連續與類別資料(Features)以及輸出標籤(Y Values)。
接下來就進入到 tensorflow 痛苦的指定 Layer 階段，這裡呼叫的 tf.contrib.layers 系列，我將其用途一併整理如下 :
如果要更詳盡的匯總可以參考這篇 :
接著，模型呼叫了一個 DNNLinearCombinedClassifier 的函數，我們深入研究一下就會發現，這東西基本是一個巨大的外包商，只做了最後的包裝工作而已，基本就是某水果的商業模式(純屬玩笑)。包裝的部分如下 :
128 行以前基本上都可以忽略，那是分別對 Wide 端以及 Deep 端建立模型，前者透過 110 行的 linear_logit_fn_builder，後者則是 86 行的 dnn_logit_fn_builder。而兩者的結合是用 144 行 control_flow_ops 中的 group 函數，這東西是 tf 用來流程控制的，可以組合多種操作。因此結合代碼來看，整個邏輯會變成是 : 透過 Group 函數分組操作，針對 Deep 部分用 AdaGrad 去優化，並針對 Wide 部分用 Linear Optimizer ，也就是 FTRL 來處理，同時針對這兩者做優化，這樣就達成了對兩者同時處理的目的。
快速的結語
說一些心得方面的 :
Wide And Deep 在 2016 年推出之後，緊接著 2017 年哈爾濱工業大學與華為的幾名研究人員又將 DeepFM 給發明了出來用作 CTR 的預測，近兩年 NLP 領域取得重大突破以後，又有人將其引入推薦系統，搞出了一些比如說 Self-Attentive Sequential 等模型。另闢蹊徑的話，包括將社交網絡交互行為考慮進去的 RippleNet 模型，用以解決冷啟動問題，或是直接針對矩陣分解改進的 Metric-Factorization 等等。可以說這個領域實際上在近年有著不輸 NLP、影像辨識等領域的飛躍進展，當然這也是在一些網際網絡公司巨頭的需求帶動下而有的發展。
推薦系統往高層級去說，實際上就是一個同時考慮二維、三維甚至更多面向的回歸或分類優化問題，這裡的二三維並不是指輸入變量的維度多寡，而是在輸入面與輸出面之間有多少維度必須同時考慮。比如協同過濾其實可以想像成是同時對多種產品，在給定 Y 並不完全匹配的情況下 (有的產品有評分、有的沒有)，如何同時最小化所有產品輸出值的損失函數。
我認為跟上這些技術發展的節奏還是挺有趣的，當然對於非研究人員來說(不管是在學界或是業界研究室裡頭)要緊跟隨瞬息萬變的發展是十分痛苦的。然而，由於在複雜模型的可解釋性與彈性上，比起傳統模型都還是差一大截，造成現在這些模型雖然不斷對產品端開發上做出改進，對於決策端實際上幫助意義相對不大，你還是很難說明為何顧客會喜歡A產品勝過B產品、怎麼樣的用戶會適合A產品、如果要改進A產品功能讓其更受顧客喜歡應該往哪個方向做等等，這也是在人工智慧算法快速發展下的一個礁石。因此，透過多讀論文跟上時代節奏，以及在決策端、應用端的經驗累積，興許不久後來者就能提出更多新穎的思維等等，因此我個人充滿期待。
之後我會盡量時不時的把論文感想寫下來，這個 數學、人工智慧與蟒蛇 系列的宗旨還是在整理。因此會盡量以大多數入門者能看懂，即使看不懂也知道從哪邊補足相關知識的方向出發，避免學習中常出現的斷片問題。感謝各位讀者的支持與Follow，有任何反饋也都歡迎提出，雖然我只是個業餘愛好者，並非專業的工程師或統計學家，但還是很有熱情與社群交流的。
附錄 :
【一、tf.contrib.layer.cross_column() 變量交叉方式】
【二、tf.contrib.layer.embedding_column() 運作方式】
首先，運行以後會返回一個 _EmbeddingColumn 類，該類實際上是繼承一個普通 Layer 得來的結果 :
