YouTube 的視頻推薦演算法是怎樣的？
國內的大型視頻網站，首頁的內容基本都是頻道的內容編輯推薦的。YouTube 的推薦演算法又是怎樣的？
youtube的推薦演算法經歷過好幾次大的改動，都有論文發表的：
第一版 是基於graph和random walk的演算法。Video suggestion and discovery for youtube: taking random walks through the view graph。Video suggestion and discovery for youtube第二版 是基於item based協同過濾。the YouTube video recommendation system。The YouTube video recommendation system第三版 基於topic representation和搜索的方法。Retrieval Methods for
Large Scale Related Video Suggestion。http://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/42623.pdf
第一階段，基於User-Video圖遊歷演算法，2008年[1]。
在這個階段，YouTube認為應該給用戶推薦曾經觀看過視頻的同類視頻，或者說擁有同一標籤的視頻。然而此時，YouTube的視頻已是數千萬量級，擁有標籤的部分卻非常小，所以如何有效的擴大視頻標籤，被其認為是推薦的核心問題。解決方案的核心有兩塊，一是基於用戶共同觀看記錄構建的圖結構（Video Co-View Graph）； 二是基於此數據結構的演算法，被稱為吸附演算法（Adsorption
Algorithm）。
圖1.User-Video Graph
視頻的共同觀看關係構建的圖，可以從兩個角度觀察，一是視頻構成的圖，一是視頻-用戶構成的圖，「視頻」圖可以看成由「視頻用戶」圖（圖1）抽取出。而視頻之間的邊，可以是同時觀看過兩個視頻的用戶個數，或者是在同一個Session中被同時觀看的次數，甚至可以將順序也考慮於其中。
那麼到底如何給視頻擴大標籤呢？標籤可以看成是一個分類，所謂「近朱者赤，近墨者黑」，在圖結構中，一個節點的信息與屬性可以通過其周圍的節點得到。「標籤」也不例外。Adsorption
Algorithm的核心思想是，部分節點將擁有一些標籤，每一次迭代，可以將標籤傳遞給相鄰的節點，如此不停迭代，直到標籤穩定分布在節點中。偽代碼如下：
其中V為節點集合，E為邊集合，W為節點與邊之間的權重，L為標籤集合，VL為V中擁有標籤的節點，每一個視頻都對應一個標籤的分布概率Lv。每一輪迭代，將重新為所有節點計算標籤分布。節點對應的標籤分布由其連接的相鄰節點關係強度，以及標籤在相鄰節點的分布概率乘積後累加得到。
本演算法與PageRank接近，也類似馬爾可夫鏈的遊走過程，由於每個節點中Label權重來自於周圍節點對應權重的線性組合，也與線性系統近似。另外，論文並未花篇幅陳述如何利用本演算法進行推薦備選生成，只說可以將經過迭代穩定後的圖結構中用戶的標籤作為備選（生成的依據），或者說是連接備選視頻的紐帶。同樣的，也並沒有花篇幅論文如何進行最終排序，以及如何歸併多種備選結果，雖然在這個階段的YouTube的推薦體系已經具備了這個模塊。
筆者認為，本演算法可以劃為「用戶畫像」推薦方法類別。以標籤為視頻以及用戶的描述，通過某種方式挖掘用戶與視頻的標籤信息，作為相互連接的紐帶。YouTube對比了本方法與熱門結果以及簡單的協同，均取得了完勝。其試驗方法也較為初步：採用完全離線的方式進行效果評價，無法對新用戶進行評測，也無法對新產生內容的價值進行衡量；另外對於視頻來講，以點擊作為衡量標準也是不夠的，播放時長是必須要考量的因素。
第二階段，基於Video-Video圖遊歷演算法，2010年[2]。
在這個階段，YouTube認為需要將用戶觀看過的視頻的相似視頻推薦給用戶。而什麼是相似視頻？主要以用戶行為對其進行界定，可以是：
1. 被一定量用戶共同觀看的視頻；
2. 在同一個Session中經常被同時觀看的視頻；
3. 考慮順序信息的，在同一個Session中經常被同時觀看的視頻。
如上這幾種選擇，信息的有效性逐漸更好，但數據則逐漸稀疏，YouTube更加偏好第二種方式。相似視頻的形式化定義如下：
其中Cij為所有被共同觀看的次數，而F(vi,vj)是一個規整化函數，試圖消歧視頻的流行度，因為Vi跟Vj中一旦存在比較Popular的結果Cij往往會偏大，一種簡單的方案是將兩個視頻被觀看的次數相乘。
初步的推薦備選結果即是用戶消費過視頻的相似視頻。如上公式，S是用戶消費的視頻集合，Vi為S中的某一個視頻，Ri則是Vi對應的相似視頻集。最終的備選集合C，則是所有Ri的並集。一般而言這種方式生成的結果作為備選的量充足的，但往往內容聚焦難以為用戶找到新視頻，也有備選結果不充足的情況。在這種情況下，相似視頻集合可以繼續擴展，從「相似視頻」擴展到「相似視頻的相似視頻」，以此類推迭代一定的次數，得到最終的備選集合。
備選生成後是排序階段，主要考量兩類因素。一是視頻的質量，包含視頻的播放數量，評分等；二是用戶的需求信息，包含用戶觀看歷史中的一些信息，例如視頻觀看數量，以及觀看時間等；用一個線性公式可以對這兩類因素進行綜合考量（此處並未提及線性公式如何而來，應該不會是拍腦袋吧—_—#）。最終只能呈現比較小數量的備選結果，所以只能從中挑選部分數據，而這個過程，則需要處理多樣性問題：將標籤類似的數據進行去除，或者將屬於同一個頻道的數據去掉，進一步的基於聚類與內容分析的方法也可以採用。
文章也陳述了具體系統實現方案。因為每個用戶的備選結果在一定時間內可以完全保持不變，所以選用了離線計算的方式。但這樣做將導致實效性不佳，所以YouTube優化了數據生成的環節，做到了每天數次數據更新。其系統架構主要分為數據收集，備選生成，推薦服務三個部分。用戶日誌被抽取後，存儲入BigTable中，然後基於MapReduce生成備選，最終得到的生成結果存儲入提供線上服務的BigTable
伺服器。推薦服務不涉及太多實時計算，延遲時間更多的是網路傳輸。
為了確認本方法的有效性，YouTube選擇了在線A/B測試的方法，主要指標包括CTR，Long
CTR（觀看超過一定時長的有效點擊），Session的平均觀看時間，第一次觀看時間，以及推薦的覆蓋率。第三階段，基於搜索以及協同過濾，2014年[3]。
本文陳述了「相關視頻」的優化方法，即用戶在觀看某一個視頻時推薦的視頻。但實質上是定義了一種相似或者相關視頻的計算方式。而「相似對象」的定義是推薦的核心問題，有了不同的計算方法，也意味著有了新的推薦方法。
為什麼要有一個新的「相關視頻」計算方法呢？協同過濾是當時最好的方法，但其適用於有了一定用戶觀看記錄的視頻，但對於新視頻以及長尾視頻，並不能良好應用。
圖2.視頻主題描述示意圖
我們來看看YouTube是怎麼做的。首先，視頻通過&<主題，權重&>集合進行描述。如上圖，《World War Z》電影包含了四個主題以及對應權重。主題名從視頻的描述信息，上傳者定義的關鍵詞，被搜索後的觀看記錄對應的檢索詞，播單名字等等抽取而來。
第二步，計算視頻與視頻之間的相似度。主要通過兩個主題集合進行計算得到。文章主要提出了兩個方法，第一個方法借鑒傳統信息檢索排序理論，將視頻VW與VR 的相似度定義為：
其中，c(t, V) 表示視頻V與包含主題t的視頻集合被「共同觀看」的次數，也就意味著t與V之間的接近程度。而df(t)則是t出現的文檔頻率，log(1 + df(t))用來對流行度太高的主題進行懲罰，與著名的IDF類似。Ts(t)是一個閥門，如果t出現在文檔中的次數超過閥值，則本值為0，也就是不考慮此t的影響，反之為1，將其納入考慮。q(VR) 則代表視頻VR的質量，通過上傳時間，上傳者，點贊與差評的數量進行構建。
第二種方法，主要思想是試圖藉助用戶行為優化主題詞的權重。文中以《World War Z》電影為例，其中「World War Z」Topic的權重最高，高於Topic「驚悚片」。但是，基於「World War Z」主題出來的結果，可能將過度的擬合本電影，導致出的結果更多的是本電影相關的內容。但實際上同一類電影可能更好。也就是說「驚悚片」在這個場景下比「World War Z」主題更有用。
主題權重訓練演算法借鑒PairWise排序方法。基本思想如下，被推薦的視頻分為兩類，一類被用戶點擊與觀看，一類並未被點擊與觀看。在排序時，將後者放在了前者的前面，則生成了一個錯誤的排序對，對應著一條訓練數據X。而X的長度為主題個數，當某一個主題出現在這個Pair對應的兩條視頻上，則對應的值為0，如果只出現在被消費過的視頻上，則為1，如果只出現在沒有被消費的視頻上，則為-1。被優化的參數W，則是X的對應係數，即主題的權重，優化的目標是在訓練集合上錯誤最小，並加入正則化：
實驗階段，YouTube主要採用在線實驗的方式驗證效果優劣。指標包括觀看時長，觀看完成率（度量有多少視頻被從頭到位看完），以及丟棄率，即沒有任何相關視頻被觀看的比例（在這種情況下，用戶行為終止）。從這三個指標來看，本文的方法與協同過濾聯合後，效果有明顯提升，並且，基於主題權重重新訓練的方法要好於借鑒搜索理論的人工擬合排序公式方法。
值得一提的是，本文提出的相似度的計算方式與基於用戶行為的方式（例如協同過濾）有著根本不同，對用戶行為的依賴更小，適用於新數據以及長尾數據，可以極大的剋制馬太效應。同時，本文也提供了成熟的實現方案：基於搜索底層進行備選生成。通過正在被觀看的視頻主題信息構建檢索句，到倒排索引中進行查詢。再者，也提到通過再排序模塊，與協同過濾方法的備選集合進行融合，將更進一步提升效果：
圖3.相關視頻系統架構圖
第四階段，基於深度神經網路，2016年[4]。
YouTube轉用深度學習做推薦系統，也許有跟風的意味，希望跟隨谷歌「using deep
learning as a general-purpose solution for nearly all learning problems」也就是將深度學習作為幾乎所有機器學習問題通用解決方案。所幸這樣的方法是成功的，帶來了推薦系統的「Dramatic Improvement」。本文陳述了YouTube推薦系統的三大難點：一是規模太大，簡單的推薦演算法在如此大規模數據量上可能是失效的；二是實效性，即新數據不斷產生，需要將其良好的呈現給用戶，以平衡舊有的好內容以及新內容；三是噪音問題，用戶行為與視頻描述均有噪音，並且只能獲得充滿噪音的用戶隱含反饋，而不能直接獲取用戶滿意度。
圖4.YouTube基於深度學習推薦系統架構圖
本文呈現的推薦系統解決方案分為兩個部分，一個是備選生成（Candidate Generation），其目標是初選結果，從海量數據中選擇出符合其個人需求偏好的百級別數據。一個則是排序（Ranking），通過更加豐富的用戶，視頻乃至場景信息，對結果進行精細化排序，得到呈現給用戶的備選。
在本文中，推薦系統的建模方式有了實質性不同，即將推薦系統定義為一個多分類器，其職責是確定某個用戶，在某個場景與時間下，將從系統的視頻中選擇消費哪一個視頻。具體的方法是，將用戶與視頻全部轉化為Embedding描述，即一個向量，最終用戶消費某個視頻的概率通過如下方式計算得到：
首先獲取視頻的Embedding描述，將視頻的文本放入Embedding工具即可（例如Word2Vec，但TensorFlow自帶）即可。構建用戶的Embedding，則是通過訓練而來。以SoftMax分類為最終優化對象，將用戶觀看視頻的Embedding整合值，搜索記錄，其它信息如年齡性別等作為特徵。中間為數層ReLU。能利用除了用戶行為外的其它信息，也是神經網路相對於普通MF類演算法的優勢。
圖5.YouTube推薦備選生成階段架構
對於YouTube產品層來講，鼓勵內容產生毫無疑問是至關重要的，所以推薦系統也希望對用戶上傳的新內容的有所偏好。然而幸運的是，即使損失一部分相關性，視頻的消費者也偏好新內容。也就是說，新內容的價值可以良好的通過其帶來的吸引力呈現出來，並不需要平台刻意而為之。本文講到了機器學習系統對於處理這實效性特徵所犯的慣常的錯誤，由於訓練行為往往發生在行為之後，但視頻信息在這個階段中並非保持不變，尤其是實效性信息，所以應該將數據的上傳時間在動作發生時候的瞬時值作為訓練特徵。這樣的處理方式偏好了新內容，並明顯的提升了效果。
YouTube選擇用戶觀看記錄作為訓練數據的初始來源，即完成觀看視頻記錄為正樣本。主要原因是用戶觀看記錄相對於用戶的顯性行為例如點贊收藏要多得多。還有一些非常有參考價值的推薦系統實現方案，例如需要對於推薦系統保留一些信息輸入，以防止過渡擬合「代理問題」（即推薦系統所優化的具體指標，例如點擊率），例如用戶往往會順著一個檢索結果頁或者用戶發布者瀏覽頁進行順序觀看，然而將檢索結果頁面或者用戶發布視頻界面直接作為推薦結果呈現給用戶是非常不好的。所以此處，YouTube做了一些處理規避這個問題，例如選擇放棄檢索句的序列信息，並其打散成詞袋。另外，YouTube發現，用戶進行視頻閱讀往往是有序的，例如用戶會按照劇集的順序進行觀看，而用戶進行信息發現的過程往往也由流行到自己的喜好。於是，去預估用戶的下一個觀看記錄，比預估用戶的觀看記錄中中間的某一個更好，這一點也有別於傳統的協同過濾。
圖6.YouTube推薦排序階段架構
備選生成的下一個階段是排序，排序模塊更多的是面向「場景」的，說的簡單一點，就是界面。用戶可能在某一地方願意點擊某一條數據，但是在別的地方則不會願意，可能在某一時間願意點擊某一條數據，但在另一個時間不會。用戶觀看了一個推薦界面，但是並未在這個界面上進行操作，那麼隨之應該進行對應內容的降級，所以對上一個推薦界面的瀏覽信息也可以進入到本模型中。排序的另一個職能是將各種備選聯合起來。此處，需要納入到模型中的信息更多，例如，用戶最近的一次搜索詞，用戶最近觀看的同一個主題下的視頻數量，用戶上一次觀看同主題視頻的時間，用戶所使用的語言等。其架構跟備選生成階段類似，將所有排序模型中的信息輸入後，進入多層ReLU，最終進行優化的是一個加權邏輯回歸層，陽性樣本的權重是其觀看時間。在這一層，也可以看到其推薦「代理問題」的轉化，由點擊行為轉為了點擊與觀看行為結合。
總結
總體上講，YouTube的推薦系統在採用深度學習之前，多數基於用戶畫像（說的高大上一丟丟其實就是標籤）與協同過濾。第一篇本質是基於圖的畫像挖掘演算法，第二篇則是對協同數據的深度利用，即不僅僅將「相似視頻」作為備選，也將「相似視頻的相似視頻」同樣納入備選集合。第三篇，則對用戶畫像法進一步深化，提出了用戶畫像法經典的基於搜索架構的實現方式，以及如何通過用戶行為進一步克服文本畫像所帶來的相關性計算偏差。這三篇在不同的地方也提到過，給用戶進行結果呈現之前，還需要做最終排序，但是這並未被深入論述。最終，採用深度網路方法，在之前紮實工作基礎上，進一步升華。
[1]Video Suggestion and Discovery for YouTube: Taking Random
Walks Through the View Graph[2] The YouTube Video Recommendation System
[3] Up Next: Retrieval Methods for Large Scale Related Video
Suggestion[4] Deep Neural Networks for YouTube Recommendations
YouTube的推薦演算法 經歷了幾個階段，2008年公開的第一階段的演算法是基於user-video graph，從用戶co-view的角度來看待資源訪問關係。[1]
參考文獻：
[1] Baluja, S. and Seth, R. and
Sivakumar, D. and Jing, Y. Video suggestion and discovery for youtube: taking
random walks through the view graph. Proceeding of the 17th international
conference on World Wide Web. 2008
[2] Davidson, J. and Liebald, B. and Liu, J. The YouTube video
recommendation system. Proceedings of the fourth ACM conference on Recommender
systems. 2010
[3] Kevin Canini and Tushar Chandra, Sibyl: A
System for Large Scale Machine Learning at Google.IEEE/IFIP. 2014
[4] GoogLeNet presentation, http://image-net.org/challenges/LSVRC/2014/slides/GoogLeNet.pptx, Last retrieved on:
19-09.2014.
在用戶個人個性化上，用過去瀏覽的視頻（添加一些人工規則去噪等）做關聯推薦（共現加降權），在驚喜度考慮上用擴散的思想尋找非直接關聯的視頻。
在群組個性化上也是一個擴散的思路，讓一部分tag非常好的視頻去給用戶打分，然後反作用於視頻打tag。最後用一些聚類演算法給用戶聚類同時給各個群組做一些推薦。推薦閱讀：