Zi 字媒體

今年4月，WWW大會上出現一篇論文「Related Pins at Pinterest: The Evolution of a Real-World Recommender System」，介紹了Pinterest推薦系統四年的進化之路。四年前，我加入了Pinterest的Discovery Team，那時候大半個Discovery Team都在忙著搭建這個叫Related Pins的新功能。我一不小心見證了Related Pins四年的發展，Related Pins如何從2~3人的項目發展到一個十幾人的團隊。既然這篇論文已經發表，大家不妨一起看看Related Pins的進化史。系統結構道生一，一生二，二生三，三生萬物看Pinterest推薦系統首先要了解產品和數據特徵，用戶在Pinterest上可以點擊一個Pin看大圖；可以再次點擊跳轉到Pin背後的網頁上去；如果在網頁上待很長時間，我們則稱這次點擊是「長點擊」；另外用戶可以把Pin保存在自己的Board里。這個用戶「保存」的比例是Pinterest最關心的產品指標。在Pinterest的數據模型中，每一個Pin都有自己的圖片，鏈接和描述；每個Pin都存在一個Board當中，但是不同的Pin可能有相同的圖片，被保存在不同的Board里。下文提到的Pin通常指包含相同圖片的Pin的集合。Pinterest的推薦系統進化經歷了這麼四個階段：1. 在我2013年剛加入公司的時候，推薦系統主要基於Pin-Board的關聯圖，兩個Pin的相關性與他們在同一個Board中出現的概率成正比。2. 在有了最基本的推薦系統后，我們對Related Pin的排序進行了初步的手調，手調信號包括但不局限於相同Board中出現的概率，兩個Pin之間的主題相似度，描述相似度，以及click over expected clicks得分。3. 漸漸地，我們發現單一的推薦演算法很難滿足產品想要優化的不同目標，所以引入了針對不同產品需求生成的候選集(Local Cands)，將排序分為兩部分，機器粗排，和手調。4. 最後，我們引入了更多的候選集，並且提高了排序部分的性能，用機器學習實現了實時的個性化推薦排序。候選集進化最初的Related Pin只有一種候選集生成演算法，並且我們直接把生成的候選集推薦給用戶。後來引入了Memboost和基於機器學習的排序演算法，候選集的生成更加註意Recall以及結果的開放性，所以產生的候選集越來越多。Board Co-occurrence: 主要的候選集生成演算法還是基於用戶的Pin和Board關聯圖，最初是Map/Reduce離線演算法。對於每個Board，輸出這個Board裡面所有的Pin Pairs，然後在Reducer裡面計算每組Pin Pair出現頻率。由於數據量太大，所以我們進行了隨機取樣。在排序過程中還引入了Pin的描述和主題相似度等特徵進行手調，效果很好。後來我們發現基於Map/Reduce取樣的演算法得到的相關度還有提升空間，對於罕見的Pin常常不能生成足夠多的候選集，所以開始使用online的隨機遊走生成候選集。這個隨機遊走演算法被稱為Pixie，通過對Pin和Board關聯圖進行幾十萬步的模擬隨機遊走產生候選集，能夠很好地解決上面提到的兩個問題。Session Co-occurrence: 基於Pin和Board關聯圖的演算法有很好的Recall，但是有時候他們不能理解Pin裡面很細微的主題，一個Board也容易隨著用戶興趣的轉移而轉換主題。這些問題可以通過挖掘有時效性的用戶行為得到更好的解決，所以Pinterest也搭建了一套Pin2Vec系統來彌補co-occurence的不足。Pin2Vec通過學慣用戶在一定時間內的保存行為，得出N個最流行的Pin的嵌入向量。通過一個Pin的向量和學習網路，既可以預測用戶接下來想保存什麼Pin，也可以找到與用戶詢問Pin最為相似的幾個Pin。Supplement Candidates: 除了以上提到的基礎的候選集，Pinterest還採用了另外兩種演算法來對結果進行發散，並且解決冷啟動的問題。每一個Pin會有相應的描述，主題等文字信息，由此可以產生基於搜索的候選集。這個候選集里的Pin比以上兩種演算法生成的相關度要差，結果相對發散，但是能給用戶帶來更好的探索體驗。另一種是基於圖片相似度產生的候選集，可以直接借用極度相似的圖片生成的推薦結果，也可以把類似的圖片Pin推薦給用戶。Segmented Candidates: 最後，為了優化產品的生態系統，Related Pin引入了針對新鮮內容的推薦集合。在Pinterest走向國際化的道路上，又針對不同的市場做了不同的推薦集合。排序過程從拍腦袋到機器半自動對於基本的搜索引擎和推薦系統，在有了大量數據之後，最容易實現的排序方式就是記住用戶在每一個Related Pin頁面與哪些Pin進行過互動。由於用戶在使用不同客戶端時，對不同位置的同一個Pin互動存在一定的偏差，所以我們在生成這個記憶的時候採用了clicks over expected clicks演算法。一個Pin的Expected Click是這個Pin在不同位置上的impression數量與該位置的期望點擊率的乘積。我們設一個Pin的Memboost得分是clicks over expected clicks：然後將Memboost得分和原始基於Pin和Board關聯圖，主題相似度和文字相似度得分線性結合在一起：這種簡單的排序被實驗證明是非常有效的。這個通過手調和記憶進行排序的過程在Pinterest度過了快三年的時光，在引入了越來越多的候選集后，人們逐漸意識到下一個大的提升可能來自於learning-to-rank。Related Pins設計了ranker對候選集根據query pin，當前用戶，以及當前用戶的上下文進行重新排序。在排序的時候採用了四類不同的特徵：Pin的特徵: 包括文字信息，圖片信息，文字向量，主題類別信息以及Pin的人口信息 (如不同性別，不同國家和語言的統計信息)。歷史特徵: 包括上文提到的Memboost，用戶過去進行的不同類別的動作信息，點擊，長點擊，保存等等。用戶特徵: 用戶的性別，國家和語言。用戶過去保存過的Pin，文字信息，主題信息等。用戶實時特徵: Query Pin是來源於主頁，搜索還是哪一個Board。最近搜索過的問題，特徵向量，最近保存過的，點擊過的，長點擊過的Pin。在最初的版本里，我們從Memboost得分中生成訓練目標，通常認為一個擁有高Memboost得分的Pin好於一個低Memboost得分的Pin，有Memboost得分的Pin好於一個隨機的Pin，然後採用pairwise loss訓練一個RankSVM模型。但是上面的版本很難模擬不同用戶對結果不同的反應，所以我們轉移到一個基於Session的訓練模型。每一個Session都包含一個Query Pin，當前用戶，動作以及一系列的推薦pin。當用戶保存一個pin時，我們把這個pin和之前的pin取出，做pairwise的學習。(筆者認為: 在這個實踐過程中應該還引入了周邊的pin，以及一些不相關的popular pin作為反例，不然學出來的結果有可能會反轉原先排序)版本三採用了RankNet loss和GBDT模型來模擬用戶非線性的行為，新的模型也能更好的考慮「如果Query Pin的類別是藝術，那麼視覺相似度是一個很強的信號」這樣一類組合特徵。 最後，版本4則由pairwise loss回歸到pointwise loss，雖然學術界一直認為排序問題listwise優於pairwise，pairwise優於pointwise，但實踐中pointwise常常能達到與pairwise一樣好的推薦效果。從人理解角度來看，其實用pointwise來預測用戶的點擊率，保存率更容易解釋，從而用得分作為一個參考，在排序過程中引入其他信號，全面的優化產品的生態系統。結語路漫漫其修遠兮推薦系統在學術界已經有很多年的研究，但是在工業界里使用的往往還是最簡單的演算法，大量的數據能夠很好地彌補演算法上的不完美。Pinterest這篇文章很好的描述了推薦系統這幾年是如何跟隨一個創業公司從2~3個人就能搭建的簡單系統成長到一個十幾個人的團隊維護和提高的包含3~4個components的大系統。在成長過程中，他們面臨了「cold-start」, 「rich get richer」, 「engagement is not always correlated to relevance」等挑戰，雖然不是每一個問題都能完美解決，但是提出有效的方案去減小問題影響正是工業界所需要的。筆者為能見證這一功能的完善和隊伍的成長感到榮幸，預祝Pinterest早日上市。王棟清華大學姚班07級，信息學競賽國際金牌。目前任職於矽谷電商網站Wish，專註搜索推薦演算法及系統設計。曾任獨角獸公司Pinterest搜索排名負責人，帶領團隊設計和實現了高度可擴展的搜索平台，以及機器學習搜索結果排名演算法。