前Pinterest搜索排名技術負責人，為你解讀Youtube推薦系統

最近一直在花時間研究和實現一些推薦演算法，並且搭建系統在產品中進行測試。

我讀了一些關於Netflix等網站「如何使用Collaborative Filtering來預測用戶對其他影片的打分」的文章，之前也曾在Pinterest目睹了Related Pin從傳統的計算co-occurence，到深度學習以及兩次打分系統的設計轉變。

但最讓我好奇的，還是以技術著稱的Google是怎麼做推薦系統的。

經過一番調查，我找到了4篇能夠描述這些年YouTube推薦系統變化的論文。

在這裡同大家分享一下。

Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph

這篇論文發表於2008年，是我發現的相對比較早的一篇有關於YouTube推薦系統的文章。作者里有一位前同事Kevin Jing，是後來Pinterest圖像組的奠基人。

這篇文章從最基本的co-view概念入手，先講了一個直觀的概念——item-based collaborative filtering system。

假設一個用戶B看了兩個視頻，1和4，根據歷史，我們知道很多看了視頻1的人也看了視頻5，9。同時，我們知道很多看了視頻4的人也看了別的視頻12，13(請讀者自行想像)。那我們可以把視頻5，9，12，13推薦給用戶B。

在對推薦結果排序的時候，我們可以根據一個視頻的流行度，和用戶已經觀看過得視頻的co-view，從前該視頻推薦成功的概率等因素給出一個打分函數。

作者在這篇文章里提出一種叫做Adsorption的學習框架，當我們有一個小的labeled數據集和一個很大的unlabeled數據集時，可以通做Adsorption將label從小的數據集推廣到大數據集上。

一種Adsorption的方法就是進行Random Walk，將每一個頂點v的label發到相關聯的鄰居上，在每一次傳遞結束後，對頂點的label進行歸一化。

這種Adsorption的方法可以用來做推薦系統。

一種做法是把user觀看video的關係當做一張圖，把用戶喜歡看的視頻當做label，然後進行random walk，將label推廣到其他的視頻上。

這篇文章最後的實驗離線測試效果很好，後來Pinterest也採用random walk來生成related pin的候選集，能夠很好的提高用戶互動情況。如果挑一挑刺的話，這篇文章並沒有太多系統方面的介紹，如何對上億用戶，上億視頻生成推薦結果對於小公司來說仍是一個很難的挑戰。

The YouTube Video Recommendation System

這是一篇2010年發表在RecSys上的文章，篇幅僅有短短的4頁，但是包含了YouTube推薦系統的產品理念，數據處理，系統設計以及實驗結果，可謂是麻雀雖小，五臟俱全。

這篇文章主要介紹如何在YouTube主頁上給用戶提供的個性化推薦內容，其目的是為了提高用戶使用網站的互動性以及娛樂性。

文章中所提到的演算法會輸出用戶可能喜歡的視頻集合，而不是給出一個具體的用戶喜歡某一視頻的概率。

在主頁上推薦視頻和推薦一個視頻的相關視頻在需求上有一定的差異，主頁上的推薦對內容的新鮮度，發散性以及用戶近期行為的相關性要求比較高。

另外還有一個重要的考慮因素就是需要幫助用戶理解"為什麼我會看到這些推薦內容"，這樣可以幫助用戶根據自己的喜好改善推薦引擎。

搭建一個主頁的推薦系統，一個基礎的組件就是對於任意一個視頻u，生成一系列相關的視頻v，在文章中作者使用了簡單的co-view來計算兩個視頻的相關度：

這裡的Cij是視頻i和j的co-view數，f(Vi,Vj)則是根據視頻Vi和Vj的觀看次數給出的一個折扣，這樣可以避免總是給用戶推薦最流行的視頻。

根據相關性R，我們可以找到每個視頻最相關的N個視頻，這裡作者還引入了一個minimum score threshold，用來去除那些並不十分確定的相關視頻。

所有推薦視頻的集合主要是根據用戶過去的行為決定，一個用戶可能會觀看，喜歡多個視頻或者給他們進行打分。根據這些視頻，我們可以找到所有距離為1的相關視頻，然後根據所有距離為1的相關視頻找到距離為2的相關視頻。

日常應用當中，距離為1的相關視頻就足夠提供很多推薦結果，但是他們可能會十分偏向於用戶某一個狹窄的興趣點，所以我們需要增加距離使推薦結果有更多的新穎性。

當我們得到所有的推薦視頻集合後，可以對他們進行一次打分，根據視頻的觀看總量，用戶的打分，評價，喜歡和分享動作來預測哪一個視頻會得到用戶的青睞。通過對用戶的反饋進行分析，我們可以把用戶不感興趣的視頻原因從推薦初始集合中刪去，或者限制某一個看過的視頻生成的推薦視頻數量。

我個人非常喜歡這篇文章，他涵蓋了最基本的推薦引擎樣例生成以及額外的排序過程，並且從系統上分析了如何通過Bigtable，MapReduce來搭建這一推薦系統，值得深入學習。

Label Partitioning For Sublinear Ranking

在我們聊現在最火的Deep Learning演算法前，不妨先看一看YouTube發表於2013年的這一文章，因為它回答了一個Deep Learning中一個很難的問題，如何在包含很多節點的神經網路output layer找到概率最大的輸出節點。

這篇文章中談到的演算法可以被應用到很多互聯網服務上，比方對很多documents進行排序的時候，可以對每一個document設定一個輸出點。在做推薦系統的時候，可以從大規模可選推薦內容中找到最有可能的那些結果。

基本思路如下：

1. 對於任意一個測試樣例x，首先根據訓練樣例劃分找到最有可能的劃分集合p=g(x)。

2. 取到訓練樣例劃分中最有可能的輸出集合L。

3. 對輸出集合樣例中每一個輸出y進行打分，計算f(x,y)，並且根據結果進行排序。

對輸入樣例的劃分可以採用兩種方法，一種是Weighted Hierarchical Partitioner，類似Weighted K-means，給訓練樣例xi到中心的距離cj一個根據label預測準確度得出的weight,優化:

一種是Weighted Embedding Partitioner，通過對訓練樣例的轉化使得label相同的訓練樣例儘可能被劃分到一個集合中去，優化:

對於我們常用的SVD，LSI和神經網路相關模型，可以直接使用中間層當做input space。

對於測試輸出的label劃分，文中也提到兩種方法，一種是設計優化函數，計算每一個label被分到一個partition後的loss，然後優化所有label劃分的整體loss。

一種是簡單的計算每一個partition內的label出現頻率，選擇出現最頻繁的幾個。

在實驗結果上，採用優化函數的劃分的方案可以帶來兩倍以上的提高。

這篇文章比較理論，所以讀起來也很困難。我個人認為這是YouTube開始轉向採用embedding來進行視頻推薦的基礎，非常值得一讀。

Deep Neural Networks for YouTube Recommendations

這是2016年發表於RecSys的文章，其中介紹了Google如何通過深度學習來改進YouTube推薦系統，從演算法和系統上都做了詳細介紹，引來了無數人圍觀。

首先從整體結構上來看，推薦系統分為兩部分。

第一部分是Candidate Generation，用來從上千萬上億個視頻中選擇少數(幾百，幾千)個候選視頻，然後通過第二部分ranking來對這些候選視頻進行詳細打分，得分最高的視頻作為最終結果呈現給用戶。

在Candidate Generation的時候，這篇文章採用了word embedding的技巧來計算每一個視頻的embedding；然後將視頻的embedding，用戶搜索問題的embedding分別計算average，再加入用戶的性別，國家，年齡，視頻質量等特徵，採用兩個完全相連的ReLU層和softmax函數來預測用戶下一個看的視頻是什麼。

推薦時可以採用最近鄰搜索的解決方案，在上億數據中找到用戶最有可能觀看的下一個視頻。在最初讀這篇文章的時候我就有一個問題，如何在上億輸出中找到最有可能的一個，在讀了上一篇「Label Partitioning for Sublinear Ranking」後我感覺YouTube就是採用把中間層當做input space，進行最近鄰搜索，然後衡量下一個可能看的視頻的概率。

當我們把推薦量從上億減少到數百，或數千視頻後，就可以採用Ranking函數進行打分了。

儘管深度神經網路可以在很大程度上減少工程師的工作量，但是YouTube還是花了不少人力從視頻中抽取更多有效的特徵，包括預測視頻的特徵，預測視頻和歷史觀看記錄生成的crossing features，以及用戶觀看視頻的時效特徵。

Ranking的主要目標是根據用戶過去觀看記錄和推薦視頻的特徵，採用logistic regression去預測下一個視頻的用戶觀看時間。

因為有明確的優化函數和衡量標準，得出的結果更容易讓人理解。

雖然Learning to Rank已經是一個很經典的機器學習問題了，但是這篇文章發現深度學習仍然能比以前線性模型和基於GBDT的樹狀模型預測的更好。

在最終實現時，YouTube推薦系統面臨兩大考驗，一方面是Freshness，每小時都有很多新的視頻上傳，但是推薦演算法偏向老的內容，這篇文章中提到用age作為一個特徵進行訓練，在最後推薦時設所有的內容age為0，有效的模擬了老內容引入的bias。

另一方面是訓練時的噪音，很多時候用戶點擊觀看一個視頻並不代表用戶真的喜歡，滿意這個內容，所以在最後選擇訓練樣例時，加入了觀看時長這一衡量標準。

小結

關於YouTube的推薦系統總結就進行到這裡，從4篇論文里我們可以看到YouTube在不同時段，基於不同的資源和技術對系統的進化過程，也能幫助自己更好的在不同情況下選擇最合適的解決方案。

作者介紹

王棟

清華大學姚班07級，信息學競賽國際金牌。目前任職於矽谷電商網站Wish，專註搜索推薦演算法及系統設計。曾任獨角獸公司Pinterest搜索排名負責人，帶領團隊設計和實現了高度可擴展的搜索平台，以及機器學習搜索結果排名演算法。

推薦閱讀：