本文根據前荔枝FM資深數據挖掘工程師莊正中近期的技術分享整理而來，主題為《圖推薦算法在E&E問題上的應用》。本次分享將圍繞以圖為基礎衍生的一類推薦算法原理和應用，以及 E&E 問題 ( 如何應對新用戶和新內容 ) 的一些處理方法。E&E 指探索與利用，是推薦系統當中的兩個核心問題。完整分享PPT可在本公眾號後臺回復「推薦系統01」獲取。
莊正中：前荔枝FM資深數據挖掘工程師現於某網際網路公司任資深推薦算法工程師，負責直播產品推薦系統的設計開發工作。曾在荔枝FM和酷狗音樂負責推薦算法和文本處理相關工作，擅長神經網絡的數據建模。
在建立推薦系統的模型之前，我們需要獲得用戶和內容的相關數據。可是在推薦系統的實踐中，經常會遇到冷啟動的問題，即缺少新進入的用戶信息和新進入的內容信息。對於用戶信息，很多公司都會有市場部從市場上的各個渠道導入進來，成本較高，且無法完全覆蓋。對於新進入的用戶，他們往往是沒有歷史行為的，而這個行為特徵卻是推薦系統中最重要的特徵之一。而新用戶的留存對於公司是至關重要的，所以對於新用戶的推薦要求儘可能的精準，使其對於平臺產生忠誠度。新用戶的推薦是推薦系統的第一個難題。第二個難點則是新內容的推薦，新內容首先是沒有用戶的反饋，沒有用戶的反饋也就無法利用相應的評估體系總結內容的真實價值。同時，新內容還存在難曝光的問題。現存的推薦系統，從比較傳統的推薦系統，到 Word2Vec，再到現在各種各樣的神經網絡，在召回階段都無法很好的召回新內容， 所以很難進入到訓練樣本中去，這是新內容的長尾問題。我們可以把協同過濾認為是一種圖推薦模型， 因為用戶和內容可以認為是二分圖結構。推薦系統的宗旨是建立更多的用戶到內容的連結，隨著圖越來越大，就可以抽取到更多的信息， 從而服務更多的用戶。以 item-based CF 為例，通過計算 item 之間的相似度，從而計算出最相似的 topK 內容，把它們當作當前 item 的鄰接點，構成物與物相連的有向圖保存在起來。推薦時快速定位用戶接觸過的 seeds 列表：在"一推多"場景直接查找節點的鄰邊。 在 "n 推 n" 場景根據多節點對各鄰邊加權求和。在多樣性推薦中將 seeds 分組並執行多個"一推多"操作。CF 的缺點也很明顯，首先，由於算法的設計問題，導致了它是一種偏熱門推薦。在數據過濾的初期，沒有達到某種閾值的 user 和 item 將會被過濾掉，形成馬太效應。第二，容易形成內部環路。比如某些很受歡迎的主播，他們互為 topK，導致一直在他們內部互推。這時，我們可以通過知識圖譜和 node2vec 來拓展圖的泛化能力。
我們都知道在 NLP 任務中，word2vec 是一種常用的 word embedding 方法，來源於神經網絡模型，是神經網絡的一種中間結構的簡化。結構如上圖所示：word2vec 通過語料庫中的句子序列來描述詞與詞的共現關係，進而學習到詞語的向量表示。它是將序列向量化的一個淺層神經網絡，通常只需要有效行為的序列就可以快速得到一個以 id 為單特徵 item2vec 召回模型。Graph Embedding 的思想類似 word2vec，使用圖中節點與節點的共現關係來學習節點的向量表示。在 graph 中隨機遊走生成頂點序列，構成訓練集，然後採用 skip-gram 算法，訓練出低維稠密向量來表示頂點。這種思想與傳統的協同過濾相比有兩個比較明顯的特點：在 graph 中主要存在兩種關係，homophily 和 structural equivalence。所謂 homophily，即是在 graph 中緊密相連的鄰域。具有這種關係的頂點之間，學習出來的向量應該接近或者相似。structural equivalence，就是指在圖中具有相似作用的頂點，他們之間未必相鄰，甚至可能相隔較遠，都是所在鄰域的中心頂點。滿足這種關係的頂點之間，特徵向量也應該接近或者相似。通常在現實世界的 graph 中，會同時存在這兩種關係。可以表示如下結構：但是在不同的任務中需要關注的重點不同，可能有些任務需要關注網絡 homophily，而有些任務比較關注網絡的 structural equivalence，可能還有些任務兩者兼而有之。那麼關鍵的問題就是如何來描述節點與節點的共現關係。RandomWalk 是一種可重複訪問已訪問節點的深度優先遍歷算法。給定當前訪問起始節點，從其鄰居中隨機採樣節點作為下一個訪問節點，重複此過程，直到訪問序列長度滿足預設條件。DeepWalk 從一個節點開始採樣，跳到下一個節點的概率完全取決於鄰邊的權重， 無法靈活地捕捉這兩種關係，在這兩種關係中有所側重。而實際上，對於這兩種關係的偏好，可以通過不同的序列採樣方式來實現。有兩種極端的方式，一種是 Breadth-First Sampling ( BFS )，廣度優先搜索，如圖中紅色箭頭所示，從 u 出發做隨機遊走，但是每次都只採樣頂點 u 的直接鄰域，這樣生成的序列通過無監督訓練之後，特徵向量表現出來的是 structural equivalence 特性。另外一種是 Depth-First Sampling ( DFS )，深度優先搜索，如圖中藍色箭頭所示，從 u 出發越走越遠，學習得到的特徵向量反應的是圖中的 homophily 關係。Node2vec 則額外定義了參數 p、q，用於控制回退、BFS、DFS 動作。
1. Alibaba graph-embedding首先我們介紹一篇阿里巴巴的圖嵌入技術論文 "Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba ( kdd 2018 )"， 其流程如下圖所示：首先如圖 (a)，假設每個用戶有不同的用戶行為，每個用戶瀏覽過不同的 item 按時間順序排列。這裡有一個業務上的技巧，就是把用戶在某個時間窗內的連續行為作為一個 session，例如一個小時，如果超過時間窗，就劃分為不同的 session。通常在短周期內訪問的商品更具有相似性。每個 session 構成一個 sampled sequence，將所有 sampled sequence 構成有向圖，圖邊表示該方向流過的次數，得到的 graph。如圖 (b)，邊權重記錄了商品的出現次數。計算商品的轉移概率，並根據轉移概率做遊走，生成商品序列，圖 (c)。最後通過 skip-gram 訓練出 embedding。新商品沒有用戶行為，因此無法根據 Base Graph Embedding ( BGE ) 訓練得出向量。為了解決物品的冷啟動問題，阿里加上了物品的邊信息 Side Information ( SI )，例如品牌，類別，商店等信息。SI 相似的商品，在向量空間中也應該接近。如下圖所示：在最下面的 Sparse Features 中， SI0 表示商品本身的 one-hot 特徵， SI1 到 SIn 表示 n 個邊信息的 one-hot 特徵，阿里採用了13種邊信息特徵。每個特徵都索引到對應的 embedding 向量，得到第二層的 Dense Embeddings，然後將這 (n+1) 個向量做平均來表示這個商品，公式如下圖。 其中，Wvs 表示商品 v 的第 s 個邊信息向量， Hv 是隱向量。剩下的事情就和 BGE 相同了。這個做法叫 Graph Embedding with Side Information ( GES )。不同的邊信息對於商品的向量可能會有不同的貢獻，可以另外學習一個權重矩陣 A∈R|V|×(n+1)，其中 |V| 表示商品集合 V 的數量，Aij 表示第 i 個商品的第 j 個邊信息權重。計算方法如下所示，從平均變成了加權求和。對權重取 e 的指數是為了保證所有邊信息的權重大於0。這個方法叫做 Enhanced Graph Embedding with Side Information ( EGES )。Airbnb 提出的冷啟動和採樣方式同樣值得我們借鑑。首先，它同樣是採用 session 進行分割的，而且明確指出 30mins 內的連續有序 sequences。同時提出了一個新的負採樣策略，即從與當前 item 的同一個 cluster 裡面採樣負樣本。而且 Airbnb 強化了付費行為的訓練。點擊序列中若有付費行為，則將這個 item 強制納入該序列每個 item 的上下文窗口。Airbnb 的冷啟動策略很簡單， 他並沒有做 end2end 的學習屬性的 embedding，而是直接把 new item 按主要屬性 ( 房間數，地域，地段等等 ) 檢索到最相似的 top3 個已知的 item，取3個 item 向量的平均值初始化 new item embedding。Real-time Personalization using Embeddings for Search Ranking at Airbnb ( kdd 2018 )
1. Mixed Graph-Vector model在實踐中，我們發現 CF 算法用於實時召回表現出的點擊率較高，但召回存在上限，word2vec 算法表現出的泛化能力較好，可以讓更多的內容得到召回，但也就帶了泛化提升後的不確定性。兩個召回策略是存在很多數據重疊，思考能否從精簡算法的角度將兩者合併起來，並各取所長。先利用之前 CF 算法的計算得到的內容相似度矩陣，取最相似的 topK 重建一個 item 間相似性關聯圖，採用 node2vec 算法，對上圖進行隨機遊走生成序列，再使用 word2vec 完成 graph embedding。所以我們最終可以得到兩個產物，一個 item similarity graph，即原來的協同過濾圖。第二個則是由 graph embedding 產生的 item embedding。在推薦時，先通過用戶觸摸過的 item seed 定位到圖節點，如果 item 不在模型則終止。然後獲取到圖節點距離1的鄰接點，如果已推薦則擴展到距離2的鄰接點，此時會進行一個過濾操作，已推薦的不會再推。如果推薦數據不足則使用圖節點向量進行 vector search，運用向量最簡單的方法就是內積或者餘弦相似度，尋找出 N 個與其最相似的 item 進行補充。所以最終的推薦結果，結合了 CF 與 Graph embedding 兩者的優勢。上述的混合模型在性能上的提升僅來自其模型層面做的 graph embedding，即圖中的節點為所有內容的邊界，帶來的覆蓋提升也不會突破這個邊界。因此對於冷啟動內容的處理，我們將標籤作為一種冷啟動參數參與到模型訓練，使得新內容可以被高級模型接受。這裡與阿里巴巴的 EGES 構建圖的策略不同，我們沿用了協同過濾生成的 item 相似矩陣構建 graph。在 embedding 和權重的訓練過程與 EGES 過程一樣。訓練完之後，我們可以獲得特徵的 embedding 和權重矩陣。這個方法主要是針對新內容的冷啟動問題。對於 user 和 item 的匹配，我們採用的是雙塔結構進行匹配，具體結構如下：雙塔結構很簡單，左側為 user 的行為特徵和基本特徵的 embedding，拼接後經過全連接層和激活層的特徵融合和提取，形成 user vector。同理右側的 item network，可以通過之前 GES 計算的 item 的 embedding，進行特徵融合。最後將 user vector 和 item vector 進行內積和 sigmoid 函數輸出匹配分數。在工程上，由於用戶行為的實時性，user vector 需要進行實時計算。但 item 側的相關 embedding 可以通過查表得到，節省資源和計算時間。
4. Graph Restrict Vector Search我們採用圖來約束推薦的搜索範圍。我們的新用戶面臨兩種類型：我們主要利用圖結構 item 之間的約束關係，比如說我們剛剛生成的用戶向量，它的搜索結果僅限於用戶剛剛點擊或者瀏覽的 item 相鄰的節點，而這些節點是我們通過大量的用戶反饋所生成的邊的關係。所以用圖約束進行搜索，一方面可以加快計算速度，還可以進一步探索下一個曝光 item 的性質。
Q：構建 session 過程中怎麼過濾異常的數據？Q：Two tower 中的 user scene vector 和 item scene vector 的區別？A：這兩個是 user 和 item 的 feature field，可以根據需要進行整理。比如 user scene 包括 location、time、event、weather 等， item scene 包括 location、upload、division 等。
Q：圖不是全連通的，有多個子圖，這種怎麼樣做 embedding 比較好？A：如果圖是隔斷的，那直接當作兩個圖來做兩次 embedding，因為很難有額外信息通過邊把兩個圖聯繫起來。
Q:千萬級結點的圖Embedding有什麼快速的訓練方法或者訓練框架嗎？
A: 建議借鑑PinSage的大規模Graph Embedding方案，採用的訓練框架為TensorFlow。
Q: Airbnb Embedding中的Listing Embedding方法能同時訓練: (1)click click ... book (2)click click ... click這兩種的session嗎？用損失函數來區分嗎？
A: 可以。對於這種情況，原理是類似Doc2vec算法將book放到了其他click在Skip-gram模型的context中，即book樣本會更多參與訓練。
Q: CF圖Graph Embedding後的向量是如何和item對應的呢？
A: 訓練出來是一個MxN的矩陣，這需要看事先你是如何定義的這個Embedding，需要與節點id通過之前的順序關聯起來。
Q: "看了又看" 場景可以只用類似於i2i這樣的方法嗎？不涉及用戶側特徵，只用i2i效果怎麼樣？
A: 可以，而且這是一般做法。想不u2i，i2i的擬合能力理論上稍弱一些，因為特徵少了一些，不過可以解決大部分情況。
Q: DSSM和YouTube的雙塔"Sampling-Bias-Corrected Neural Modeling for Large Corpus Item Recommendations"有什麼區別？
A: 基本模型一樣，但後者提出通過Batch SoftMax Optimization、Streaming Frequency Estimation提升訓練效率、修正Sampling Bias。
Q: 圖的存儲有常用的格式嗎？可否理解為Redis裡key是一個商品id，value是一串逗號連接的商品id？
A: 內存裡可以用map<string,float[]>，外存裡可以使用你說的方式。
Q:Category Embedding Entity Embedding 為什麼對應著多個Embedding，然後進行pooling？
A: 一個欄位如果屬於Multi-hot離散特徵類型，一般用自己的Embedding，然後採用pooling得到Field Vector，聯合編碼做大Embedding通常只對1-hot離散特徵和連續特徵有效。
Q:Mixed graph給Word2vec的Sequence如何構建？和Similarity矩陣有何關係？
A: 請查閱Node2vec算法，Similarity矩陣即item與item的相似度，如果取每個item最相似的topK個item，它本質上可以變成一張圖。
Q: 雙塔裡面的基礎特徵向量如何來的（例如年齡，地區，職業等）？
A: 隨機初始化它們的Embedding，並參與模型的訓練得到。
Q: 圖像量如何存儲，提高查詢性能？
A: 建議放在內存裡。
Q: 能不能直接用Session的序列，算出vec，而不是先構建Graph？
A: 可以，並且可以將Graph抽樣的序列和Session原來的序列一起訓練。
Q: Mix Graph,兩種圖怎麼Random walk，邊的權值同等對待？
A: 請查閱Node2vec算法，邊上如果記錄的是頻率，則是帶權Random Walk。
Q: Graph Restrict Vector Search具體做什麼用的？
A: 對於item2item這種場景，使用Vector可以加入用戶個性化的一些信息。
在本公眾號【
智東西公開課】後臺回復「
推薦系統01」獲取本次完整講解PPT（
限時24小時內無門檻領取哦）
5月13日，MCU&MPU安全技術公開課恩智浦半導體專場開講！恩智浦微控制器與處理器事業部資深系統工程師、安全專家鍾菊英和張曉東兩位講師將直播講解MCU及MPU的物聯網安全技術。
掃描下方海報中的二維碼快速報名👇👇👇