細說YouTube推薦系統的變遷
達觀數據高級工程師，曾獲美國大學生數學建模競賽二等獎，目前參與達觀數據推薦系統研發，負責酷6，wifi萬能鑰匙和視頻看看等項目。
介紹
總所周知，YouTube是世界上最大的視頻網站，網站每天要面對著不同興趣的用戶，它需要從視頻池中撈出當前用戶感興趣，想看的視頻，以留住老用戶吸引新用戶，而這個功能就是視頻推薦系統提供的。而隨著不同算法技術的興起，推薦系統的核心算法也在發生變化。本文主要從YouTube推薦系統的四篇論文《Video Suggestion and Discovery for YouTube》、《The YouTube Video Recommendation System》、《Label Partitioning For Sublinear Ranking》和《Deep Neural Networks for YouTube Recommendations》入手，介紹YouTube對視頻推薦系統的升級改造–在08年使用了基于用戶-視頻圖的隨機遍歷算法，而到了10年，又升級為基于物品的協同過濾算法，而13年將推薦問題轉換成多分類問題，并解決從神經網絡最后的眾多輸出節點中找出最大概率的輸出節點。此舉也為16年將推薦核心算法升級為深度學習算法打下了基礎。
論文簡介
本文參考的四篇論文中，第一篇《Video Suggestion and Discovery for YouTube》和第三篇《Label Partitioning For Sublinear Ranking》重點是對推薦系統中使用的算法進行了一些說明介紹，但是對本身使用的推薦系統并未做詳細介紹。而第二篇《The YouTube Video Recommendation System》和第四篇《Deep Neural Networks for YouTube Recommendations》詳細介紹了YouTube的推薦系統，它都由兩部分構成，第一部分是候選集的生成，就是根據內容數據(比如視頻流，標題，標簽，類別等元數據)和用戶行為日志(比如視頻點擊，觀看時長，視頻打分等)等信息來找出要推薦給用戶的候選視頻，第二部分是對這些候選視頻進行排序，給出最優的或者top k最優的視頻給用戶。下圖就是YouTube推薦系統的大體流程：
基于用戶-視頻圖的隨機遍歷
論文《Video Suggestion and Discovery for YouTube》是由Shumeet Baluja，Shumeet Baluja等人在2008年發表在 the International World Wide Web Conference Committee (IW3C2)上。文章花了大量篇幅講了吸附算法(ADSORPTION)，該算法的目的就是為了解決視頻標簽的擴散。所以就大膽推測當時YouTube推薦系統應該就是根據用戶曾經看過的視頻給用戶推薦同類視頻，也就是擁有相同標簽的視頻。
視頻相關圖
TIPS:
其實這個視頻間的關聯度就可以作為用戶根據其中看過的一個視頻作相關推薦的依據，這個也就是后來大名鼎鼎的基于物品的協同過濾算法，只不過當時的目光聚焦在標簽擴散找同類上，而沒有使用這個特征。
吸附算法
論文介紹了三個吸附算法，分別是通過均值的吸附，通過隨機走 的吸附和通過線性系統的推薦。不過這三個是等價的。而之所以叫吸附可能是因為算法的整個過程就是吸附節點不斷吸附標簽的過程。
- 均值吸附
- 均值吸附的算法流程圖如下：
基于ItemCF的推薦系統
論文《The YouTube Video Recommendation System》是由Davidson J, Liebald B, Liu J等人在2010年發表在第四屆ACM RecSys上。當時YouTube推薦系統的核心算法就是基于Item的協同過濾算法，換句話說就是對于一個用戶當前場景下和歷史興趣中喜歡的視頻，找出它們相關的視頻，并從這些視頻中過濾掉已經看過的，剩下就是可以用戶極有可能喜歡看的視頻。這里的視頻相關性是用共同點擊個數來描述的。整個推薦過程分為兩步：
2.根據視頻的相關性和用戶的歷史行為給用戶生成推薦列表。
生成推薦侯選集
排序
對于排序而言，有三方面影響排序的因素
1 視頻質量相關： 能夠證明用戶喜歡視頻的因素
- 視頻觀看次數
- 視頻評分
- 視頻評論
- 視頻收藏和轉發行為
- 上傳時間
2 用戶特性相關： 和用戶的品味和喜好相關
- 種子視頻的屬性
3 多樣性： 推薦不同主題
- 限制單個種子視頻得出的候選視頻
- 限制同一個上傳者的視頻數量
- 主題聚類
- 文本分析
TIPS:
在目前的推薦系統中，協同過濾的應用是最廣泛的，它的優勢很明顯，就是個性化程度高，但是不可否認的是它的冷啟動問題以及稀疏問題。而這兩個問題可以被基于內容過濾推薦方法所解決，這二者的融合可以使推薦系統更加健壯高效。
次線性排序的標簽分區
論文《Label Partitioning For Sublinear Ranking》是由Jason Weston，Jason Weston等人在2013年發表在第三十屆國際機器學習大會上。該論文將推薦問題變成了一個多分類的問題，并解決了在神經網絡中如何從最后一層輸出層中共找到概率最大的輸出節點。
TIPS:
這個算法的適用性很廣，像多文本排序等。
算法說明
該算法基本的思路如下：
輸入輸出的劃分
對于輸入樣例的劃分，本文提到了兩種，一種是Weighted Hierarchical Partitionr, 它的思想和加權的K-means算法一樣，而權重是通過給訓練樣例xi到中心的距離cj一個根據label預測準確度得出的weight,另一個叫Weighted Embedding Partitioner，它是通過對訓練樣例的轉換使得label相同的訓練樣例盡可能被劃分到一個集合中取。實驗結果顯示，采用優化函數的分布的。
而對于對于測試輸出的label劃分，文中也提到兩種方法，一種是設計優化函數，計算每一個label被分到一個partition后的loss，然后優化所有label劃分的整體loss。另一個是簡單的計算每一個partition內的label出現頻率，選擇出現最頻繁的幾個。實驗證明，采用優化函數的劃分方案比另一種提高1倍。
基于深度學習的推薦系統
論文《Deep Neural Networks for YouTube recommendations》是由Covington P, Adams J, Sargin E等人在2016年發表在第十屆ACM RecSys上。這時YouTube推薦系統的核心算法是深度學習方法。該方法將推薦問題轉變成一個分類問題，舉個例子就是之前是用戶在看了一些視頻后，用戶最有可能看哪個視頻?這是推薦問題，而現在變成了用戶在看過一些視頻后(這里一個視頻就是一個類別)，需要預測下一個要看的視頻是視頻池中的哪一個分類。不過這個類別數目非常大。對于用戶C和用戶行為C，把語料庫V中的視頻i，在時間t時做出的分類為
生成推薦侯選集
如下圖所示，推薦候選集的生成是將推薦問題當做多類(百萬個類別)分類問題。步驟如下：
1 將用戶的歷史信息(如觀看歷史、搜索歷史)和其他特征(如地理位置、用戶性別，發表時間等)接成向量，輸入給由修正線性單元(ReLU)構成的非線形多層感知器(MLP)，得到用戶興趣特征;
2 訓練階段時，將所有用戶的興趣特征輸入 Softmax 進行多分類訓練，獲得模型;
3 預測階段時，計算用戶興趣特征與所有視頻特征的相似度，用最近鄰搜索獲取分較高的 k 個視頻給排序網絡。
排序
排序的目的是將候選集中的候選視頻再進行過濾一遍，挑出其中最適合的，用戶最有可能喜歡看的視頻給用戶。文中用于排序的神經網絡和生成推薦候選集的結構類似，唯一的不用只是在最后一層用邏輯回歸給每個視頻打分。由于候選集中的視頻數目遠遠少于原始的視頻池中數目，所以這個過濾過程中會加入更多的視頻特征(比如視頻圖片信息)和用戶特征，這樣可以對用戶進行更加精確化的推薦。 推薦的結果按照每個視頻的得分進行排序，最后按照分數高低推薦視頻給用戶。
TIPS:
而對于深度學習，它具有優秀的提取特征能力，能夠學習到多層次的特征，將視頻信息和用戶信息中隱藏的特征抽象出來。像YouTube基于深度學習的推薦先用視頻和用戶的主要信息通過深度候選生成模型從百萬級視頻中找出數百個相關的視頻，再用視頻和用戶的其他信息通過深度排序模型從數百個視頻中找出幾十個最有可能受用戶歡迎的視頻給用戶。這樣使得推薦系統對用戶喜好的刻畫能力大大增強，刻畫的范圍更加廣泛。
思考
從上面四篇論文中，我們可以看到YouTube一直在嘗試將最熱門的技術應用到推薦系統中，并不斷的給系統進行升級進化，這樣可以讓它更好的在不同的環境下選擇最適合的解決方案。簡而言之，多個模型多條路。
【本文為51CTO專欄作者“達觀數據”的原創稿件，轉載可通過51CTO專欄獲取聯系】
