本文涉及的論文如下：

• 【2008 年】Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph
• 【RecSys 2010】The YouTube Video Recommendation System
• 【ICML 2013】Label Partitioning For Sublinear Ranking

內容主要介紹Youtube在機器學習方面的探索和嘗試！后續會更新Youtube在深度學習和強化學習方向的幾篇論文解讀，以及在推薦系統方向做的探索！

2008年-Adsorption（吸附演算法）

在論文《Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph》中作者定義了介紹的演算法為：Adsorption（吸附演算法），這篇論文比較老了，沒有很大的參考意義，但是對于我們系統的了解Youtube推薦系統的進步卻很有幫助，下面簡單看下這篇論文的核心內容，

在最初，Youtube認為應該給用戶推薦曾經看過視頻的同類視頻，或者說擁有同一標簽的視頻（有點類似于ItemCF），但是對于存在的視頻，并不是都有標簽的，雖然可以通過計算機視覺技術可靠的推斷出某些視頻的標簽，但大部分unlabel的視頻仍不能得到有效的標簽，因此提出了論文中的Adsorption（吸附演算法），通過吸附演算法得到未知視頻的標簽，繼而進行推薦，

演算法實作的偽代碼如下：

其中

• G ( V , E , w ) G(V,E,w) G(V,E,w) 表示的是一個節點圖， V V V表示節點集合， E E E表示邊的集合， w w w表示邊的權重
• L L L表示標簽集合
• V L V_L VL?表示 V V V中擁有標簽的節點集合
• L v L_v Lv?表示視頻 v v v的標簽分布概率
• V ~ \widetilde{V} V 表示的是特殊處理的一些節點， V ~ = { v ~ ∣ v ∈ V L } \widetilde{V} = \{ \widetilde{v} | v \in V_L\} V ={v ∣v∈VL?}，即 v ~ \widetilde{v} v 只有一個鄰節點 v v v，且 v ~ ? v \widetilde{v} - v v ?v的連接權重為1
• V ∪ V ~ V \cup \widetilde{V} V∪V 表示的是節點圖中的節點只有一個連接的節點，且其 w = 1 w=1 w=1

每一輪迭代，將重新為所有節點計算標簽概率分布，節點對應的標簽分布由其連接的相鄰節點關系強度，以及標簽在相鄰節點的分布概率乘積后累加得到，

即節點 v v v的標簽的概率分布 L v L_v Lv?等于點 u u u和 v v v之間的權重 w w w乘以點 u u u的 L u L_u Lu?，通過這樣一個傳遞，將鄰居和自己的標簽進行了“平均”，

其實這里的演算法思想和PageRank演算法是相似的，最終停止迭代的條件是標簽分布相對平衡，

論文中提到了三種方式的吸附，分別為：

• 均值吸附
• 隨機游走吸附
• 線性吸附

這三種方式的吸附主要區別在于更新 L v L_v Lv?時的方式，當是均值吸附時，如上圖所示，當是隨機游走吸附時，將 L v L_v Lv?的迭代公式修改為：
L v = ∑ u w ( w , v ) ∑ u w ( w , v ) ? L u L_v = \sum_{u} \frac{ w(w,v) }{ \sum_u w(w,v) } * L_u Lv?=u∑?∑u?w(w,v)w(w,v)??Lu?
其中 w ( w , v ) ∑ u w ( w , v ) \frac{ w(w,v) }{ \sum_u w(w,v) } ∑u?w(w,v)w(w,v)? 表示隨機遍歷選擇節點 u u u的概率，該演算法就是將每一個頂點 v v v的標簽發到相關聯的鄰居上，在每一次傳遞結束后，對頂點的標簽進行歸一化，

當為線性吸附時，即將 w ( w , v ) ∑ u w ( w , v ) \frac{ w(w,v) }{ \sum_u w(w,v) } ∑u?w(w,v)w(w,v)? 理解成線性組合中占的比例，

總結思考

本論文主要介紹的是推薦系統中的吸附演算法，主要解決的是如何使用有效的視頻標簽為無標簽的視頻打標并為用戶進行推薦，在如今的場景中可以將其應用到用戶畫像的技術上，擴展未知用戶的標簽屬性，

2010年-Youtube Video 推薦

該部分內容來自于論文：《The YouTube Video Recommendation System》該論文發表于2010年的RecSys上，雖然只有四頁，但是在當時也是干貨滿滿，下面我們來復習一下這篇論文介紹的是什么內容，

目標

用戶在瀏覽Youtube視頻時一般有三種目的：

• 觀看特定的video
• 觀看特定型別的video
• 瀏覽尋找感興趣的video

推薦系統的目的也是為了滿足用戶瀏覽尋找感興趣的video，因此推薦系統的目標是為用戶推薦高質量并且符合興趣的視頻，推薦結果應該隨時間和用戶的行為進行更新，

系統設計

論文中提到的Youtube的推薦系統應該是目前推薦系統架構的比較古老的版本，其是一個經典的「二段式推薦架構」，包含召回和排序兩個部分，只不過使用到的演算法和策略相比現在來講比較簡單和直接，

召回部分

召回部分主要是將用戶有行為的視頻作為種子集合，再將它們相關的視頻集合合并到一起，就是一個最簡單的召回策略，但是由于用戶的口味在一定時期往往保持一致，這些種子視頻的范圍往往很狹窄，為了擴大多樣性，Youtube選擇召回的不是1步相關視頻，而是n步相關視頻，即種子視頻迭代n次后得到的相關視頻集合，

這里我們說一下如何選擇種子視頻集合和計算種子視頻的相關視頻，

a）選擇種子視頻集合

在系統中，用戶的行為包括explicit（顯式）和implicit feedback（隱式），顯式的行為包括：用戶評分、明確表示喜歡，不喜歡等行為，隱式的行為包括：瀏覽、觀看等，因為可以考慮結合用戶的顯式和隱式行為進行種子視頻的選擇，比如用戶觀看過的視頻、喜歡過的視頻、收藏過的視頻等，

但是原始資料中還含有非常多的噪聲，很多不可控的因素會影響原始資料的質量，因此在使用資料的時候要進行一定的清洗和選擇，這一點無論是過去，還是現在未來都是需要進行處理的，

b）計算視頻相關性

論文中指出相關視頻的定義為：視頻 v v v的相關視頻為用戶觀看視頻 v v v之后可能想看的視頻，

兩個視頻的相關性由關聯規則挖掘方法來確定，視頻 i i i和視頻 j j j的相關性定義為：
r ( v i , v j ) = c i j f ( v i , v j ) r(v_i, v_j) = \frac{c_{ij}}{f(v_i, v_j)} r(vi?,vj?)=f(vi?,vj?)cij??

其中:

• c i j c_{ij} cij?表示 v i v_i vi?和 v j v_j vj?共同出現的次數
• f ( v i , v j ) f(v_i, v_j) f(vi?,vj?)是一個和視頻 v i v_i vi?和 v j v_j vj?出現的次數相關的函式，最簡單的此類函式為： f ( v i , v j ) = c i ? c j f(v_i, v_j) = c_i * c_j f(vi?,vj?)=ci??cj?

利用這個相關系數可以選擇出與種子視頻 v i v_i vi?相關的視頻集合 R i = r ( v i , v j ) R_i = r(v_i, v_j) Ri?=r(vi?,vj?)，簡單的說，這個視頻集合是由一個閾值進行確定的，

排序部分

在得到召回的視頻集合以后，需要對這些相關視頻進行排序，
用于排序的資料主要包括：

• 視頻質量：包括觀看次數、視頻評分、評論、喜歡和分享次數等等
• 用戶資料：視頻和當前用戶的興趣的match程度
• 多樣性：要在被推薦的視頻集合的類別中做一個平衡，以保持結果的多樣性

這些資料最終被線性組合起來，得到ranking的評分，

總結

• 在進行視頻推薦時，會顯示視頻的縮略圖、標題、以及視頻的年齡、受歡迎程度等資訊，也會解釋為什么推薦該視頻
• 會讓用戶控制他們看到的推薦結果的位置和數量，用戶可以提供相關的建議（針對某些場景，數量這個可以進行設定，建議即反饋）
• 采用AB實驗（CTR指標）來測驗結果
• 文中利用到了BigTable和MapReduce的技術（這在當時也是很厲害的主流大資料方案，雖然今天不再使用，但是其思想仍然產生了很大的影響）

這是一個比較經典的二段式推薦架構，在今天的推薦系統中仍然被延用，如果是一個公司初代推薦系統版本，其實完全可以借用該篇論文的思想，然后再進行逐步的完善和優化，

2013年-基于標簽分割的亞線性排序

本篇論文是Youtube在2013年發表在RecSys上的-《Label Partitioning For Sublinear Ranking》，主要介紹的是如何根據標簽分割進行線性排序，下面進行簡單的復習和說明，

背景

現實中，許多任務需要對巨大得目標進行排序，例如在推薦系統中，回應一個用戶得請求時，可能對數百萬個視頻進行打分排序，然后把前 k k k個視頻呈現給用戶，通常得做法是依次對每個視頻進行打分，但是隨著視頻數量得增加，演算法的實時性會受很大得影響，

因此論文提出了一種基于標簽分割的演算法，最終實作壓線性的排序，

演算法

假設存在一個資料集， ( x i , y i ) , i = 1 , . . . , m (x_i, y_i), i=1,...,m (xi?,yi?),i=1,...,m，其中 x i x_i xi?是輸入樣本， D D D是所有標簽的集合， y i y_i yi?是D的子集，我們得目標是給定一個新樣本 x ? x^* x?的情況下，對 D D D中所有標簽進行排序，并將 k k k個最想管得標簽呈現給用戶，

eg：在視頻推薦系統中， x i x_i xi?是某個狀態（搜索歷史，觀看歷史，地理位置）下的用戶， D D D是整個視頻庫， y i y_i yi?是和用戶最相關的視頻集合，假設 ∣ y i ∣ |y_i| ∣yi?∣ 表示 y i y_i yi?中的數量，假設在回應用戶 x ? x^* x?的請求時，我們需要給用戶呈現 k = 10 k=10 k=10個視頻，假設和用戶最相關的視頻集為 y ? y^* y?，如果 k < ∣ y ? ∣ k < |y^*| k<∣y?∣，我們希望這 k k k 個視頻都屬于 y ? y^* y?，如果 k > ∣ y ? ∣ k > |y^*| k>∣y?∣，我們希望 y ? y^* y?中所有視頻都在這 k k k個視頻中，

論文中提出的標簽分割演算法，包含兩個部分：

• 輸入分割：給定一個輸入樣本，將其映射成一個 key，這里表示為：
  p = g ( x ) , p ∈ { 1 , . . . , P } p = g(x), p \in \{1, ..., P\} p=g(x),p∈{1,...,P}
• 標簽分割：為每個key分配一個標簽子集 L L L

在預測階段，給定一個輸入樣本 x ? x^* x?，找到其對應的 p p p 和 L L L，用 f ( x , y ) f(x,y) f(x,y) 對 L L L中所有標簽打分并排序，由于 ∣ L ∣ < < ∣ D ∣ |L| << |D| ∣L∣<<∣D∣，因此可以大大提高打分的速度，并且，如果 L L L中不包含 f ( x , y ) f(x,y) f(x,y)打分很高但是不相關的物品，還是改善系統的準確度，

a）輸入分割

對于輸入樣例的劃分，論文提到了兩種，一種是 Weighted Hierarchical Partitionr，它的思想和加權的 K-means 演算法一樣，而權重是通過給訓練樣例到中心的距離一個根據 label 預測準確度得出的 weight，即如果在樣本上打分函式表現的好(與用戶相關的物品打分都高，下面簡稱好樣本)，那么該樣本在損失函式中占有更高的權重，這么做的目的是讓表現好的樣本優先聚成一類，優先將好樣本聚成一類的好處是只要對該類分配的標簽集合中包含與樣本相關的標簽，就能夠給用戶呈現出來（排名靠前），

∑ i = 1 m ∑ j = 1 P l ( f ( x i ) , y i ) ∣ ∣ x i ? c j ∣ ∣ 2 \sum_{i=1}^{m}\sum_{j=1}^{P} l (f(x_i), y_i)||x_i - c_j||^2 i=1∑m?j=1∑P?l(f(xi?),yi?)∣∣xi??cj?∣∣2

另一個叫 Weighted Embedding Partitioner，它是通過對訓練樣例的轉換使得 label 相同的訓練樣例盡可能被劃分到一個集合中去，即作采用embedding的方法，將標簽相似的樣本映射到相似的空間:

∑ i = 1 m ∑ j = 1 P l ( f ( x i ) , y i ) ∣ ∣ M x i ? c j ∣ ∣ 2 \sum_{i=1}^{m}\sum_{j=1}^{P} l(f(x_i), y_i)||Mx_i - c_j||^2 i=1∑m?j=1∑P?l(f(xi?),yi?)∣∣Mxi??cj?∣∣2
其中 M M M 表示的是 embedding矩陣，

b）標簽分割

輸入分割完成之后，就可以進行標簽分配，下面討論如何為一個key分配標簽子集，論文中分為四種進行處理，分別為：

1、每個樣本一個相關標簽，且 k = 1 k=1 k=1，優化后最終的目標函式為：

m a x a ∑ t a y t ( 1 ? m a x R t , i < R t , y t a i ) \underset{a}{max} \sum_{t} a_{y_t} (1- \underset{R_{t,i} < R_{t,y_t}} {max} a_i) amax?t∑?ayt??(1?Rt,i?<Rt,yt??max?ai?)

2、每個樣本一個相關標簽，且 k > 1 k>1 k>1，優化后最終的目標函式為：

m a x a ∑ t a y t ( 1 ? Φ ( ∑ R t , i < R t , y t a i ) ) \underset{a}{max} \sum_{t} a_{y_t}(1- \Phi ( \sum_{R_{t,i} < R_{t,y_t}}a_i)) amax?t∑?ayt??(1?Φ(Rt,i?<Rt,yt??∑?ai?))
其中 r < k r < k r<k時， Φ ( r ) = 0 \Phi(r) =0 Φ(r)=0, 否則 Φ ( r ) = 1 \Phi(r) =1 Φ(r)=1，

3、每個樣本多個相關標簽，且 k = 1 k=1 k=1，目標函式為：
m a x a ∑ t m a x y ∈ y t ? a y ( 1 ? m a x R t , i < R t , y a i ) \underset{a}{max} \sum_{t} \underset{y \in y_t}{max} \, a_y(1- \underset{R_{t,i} < R_{t,y}} {max} a_i) amax?t∑?y∈yt?max?ay?(1?Rt,i?<Rt,y?max?ai?)

4、每個樣本多個相關標簽，且 k > 1 k>1 k>1，此種情況下，目標函式為：
m a x a ∑ t 1 ∣ y t ∣ ∑ y ∈ y t a y w ( R t , y ) ( 1 ? Φ ( ∑ R t , i < R t , y a i ) ) \underset{a}{max} \sum_{t} \frac{1}{|y_t|} \sum_{y \in y_t} \frac{a_y}{w(R_{t,y})}(1 - \Phi ( \sum_{R_{t,i} < R_{t,y}}a_i) ) amax?t∑?∣yt?∣1?y∈yt?∑?w(Rt,y?)ay??(1?Φ(Rt,i?<Rt,y?∑?ai?))

然后使用隨即梯度下降法去優化該目標函式就好了，

總結

本文提出了一種“包裝器”方法來加快標簽得分排名，它采用了一種新穎的優化方法來進行輸入分割和標簽分配，結果與原始標簽評分器相似或更好，但速度快了幾個數量級，這使該技術可以在數量級很大的視頻推薦系統中使用，

目前的推薦系統場景中，此方法已經沒有太大的借鑒意義，但是通過上面Youtube發表的三篇論文來看，可以得知，Youtube在推薦系統方面也是在做不同的嘗試和探索，從而更好的服務用戶，