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

來自專欄一周一paper

論文地址 ：　

https://static.googleusercontent.com/media/research.google.com/zh-CN//pubs/archive/34407.pdf?

static.googleusercontent.com

## ADSORPTION ALGORITHM

論文前面的內容不再贅述 ,我們直接來看 ADSORPTION ALGORITHM , 即 吸附演算法 .

吸附的基本直覺(intuition )是 圖中彼此接近的頂點應該彼此相似。定義兩個節點之間的這種緊密度( closeness )的一種方式是通過在特定步數內對從一個節點開始到達另一個節點的隨機遊走 (Random Walk) 的次數進行計數。也就是說，如果從圖中的一個節點開始隨機移動到與其連接的其他節點，那麼它到達另一個節點的次數可以被認為是兩個節點之間相似度的度量 .

吸附演算法的 Intuition : 「You are what your friends are」 .

例子 :

考慮我們有一個包含N個節點的圖，其中每個邊都有一個表示邊的強度的權重「w」（由邊連接的兩個節點之間的相似性）。假設該圖是Twitter上的人的社交網路，並且邊的權重表示它們之間的相似性。 Twitter上的一些用戶可能會自我聲明他們的政治傾向（保守/自由/其他），而其他許多用戶則可能不會。我們的任務就是估計社交圖譜中每個用戶最有可能的政治傾向標籤。

吸附演算法 可以為每個用戶估算一個標籤。對於每個用戶，維護一個長度為 3 的向量 表示用戶是保守的，自由的或其他的概率。我們可以運行迭代演算法如以下三種方式：

( Here is an algorithm that can estimate a label for each user. For each user, maintain a vector of length 3 that indicates the probability of a user being a conservative, liberal or other. We can run an iterative algorithm as follows:

• Adsorption via averaging
• Adsorption via random walks
• Adsorption via Linear Systems

這三種方式分別是基於平均的 , 基於隨機遊走的 ,和基於線性系統的 .

Adsorption via averaging

先讓我們來看看基於平均的迭代方法 :

1. 上面提到 , maintain a vector of length 3 that indicates the probability of a user being a conservative, liberal or other , 所以首先初始化用戶的向量 , 如果用戶聲明了自己的政治傾向 , 比如馬爾斯說自己是個保守派 , 那麼馬爾斯的標籤向量就是 ( 1,0,0 ) , 對於其他沒有聲明自己政治傾向的用戶 , 我們將其聲明為 (0,0,0 ) , 表示暫時沒有政治傾向 .

注意這句話 , 是平均吸附的精華所在 :

" For each user, compute the new value of their vector by averaging the labels of their neighbors in the social graph "

" 對於Adsorption Algorithm , 當我們有一個小的 labeled 數據集和一個很大的 unlabeled 數據集時，可以通做 Adsorption 將 label 從小的數據集推廣到大數據集上。

標籤可以看成是一個分類，所謂 "近朱者赤，近墨者黑"，在圖結構中，一個節點的信息與屬性可以通過其周圍的節點得到。"標籤" 也不例外。Adsorption Algorithm 的核心思想是，部分節點將擁有一些標籤，每一次迭代，可以將標籤傳遞給相鄰的節點，如此不停迭代，直到標籤穩定分布在節點中。 將每一個頂點 v 的 label 發到相關聯的鄰居上，在每一次傳遞結束後，對頂點的 label 進行歸一化。"

演算法解釋 :

關於 "節點(node ) / 頂點(vertex )" : 節點表示線的終點和起點

Given a graph

: the set of vertices (nodes) 節點集合

: the set of edges 邊集合

: weight function on the edges (non-negative , 非負 ) 權重

: denote a set of labels 標籤集

We assume that each node in a subset carries (攜帶) a probability distribution(概率分布) on the label set . 的子集 里的節點攜帶概率分布 .

說明 : for each vertex ,we create a "shadow" vertex with exactly one out-neighbor , namely ,connected via an edge of weight "1" .

we will re-locate the label distribution from to , leaving with no label distribution , 我們將重新定位從 to 的標籤分布 , 使 v 不帶標籤分布 . (?)

Let denote the set of shadow vertices , .

we will assume that at the beginning of the algorithm, only vertices in have non-vacuous label distributions . 在演算法的 beginning , 中的頂點有非空分布 .

演算法的偽代碼如下 :

為 中擁有標籤的節點，每一個視頻都對應一個標籤的分布概率 。每一輪迭代，將重新為所有節點計算標籤概率分布。節點對應的標籤分布由其連接的相鄰節點關係強度，以及標籤在相鄰節點的分布概率乘積後累加得到 。

或者這樣說 , 節點 v 的標籤的概率分布 等於點 u ,和 v 之間的權重 乘以點 u 的 , 通過這樣一個傳遞 , 將鄰居和自己的標籤進行了"平均" .

精華就是 : .

Algorithm Comments :

1. In the summation (在求和中? )，u 在具有非空標籤分布( non-vacuous label distribution) 的 中的所有頂點上變化。
2. 在演算法中，如果沒有一個節點的標籤分布在一輪中變化，就說收斂已經發生(convergence has occurred)。可以證明，該演算法收斂於一組獨特的標籤分布 ( It can be shown that the algorithm converges to a unique set of label distributions )。In practice，我們將施加一個小的閾值，以便如果沒有一個分布的變化幅度大於這個閾值，我們會說演算法已經收斂。
3. Upon convergence (收斂後) , each node carries a label distribution , 前提是 there is a path from v to some node ( 為 中擁有標籤的節點)
4. The choice of unit weight on the edge for each 是完全隨機的 , and may be replaced by other interesting choices , this will turn out to be a very useful feature.
5. 敏銳的讀者可能已經注意到，我們沒有更新每一輪中的標籤分布( we do not update the label distribution in each round ) ; 相反，我們根據鄰居提供的分布從頭開始重新計算它。事實證明，這些演算法是完全等效的，並且所提出演算法的無記憶特性使得數學分析變得更容易。
6. 吸附演算法允許非常有效的迭代計算 (類似於 PageRank )，其中，在每次迭代中，標籤分布沿著每個邊傳遞。 這也是一個在 MapReduce model/infrastructure 中實現並行編程的高效操作 .

關於 Absorption :

Adsorption via averaging

Adsorption via RandomWalk

http://meandmyresearch.blogspot.com/2012/05/video-suggestion-and-discovery-for.html 中提到 :

" If we reverse the edges from G, the above algorithm is equivalent to a random walk algorithm over the bipartite graph. Shadow vertices become absorbing states. Simple as that. 如果我們逆轉G的邊，上面的演算法等價於二部圖上的隨機遊走演算法。 Shadow vertices become absorbing states , 就那麼簡單。"

Quera 中提到 :

Repeat the following random walk, each time starting with the user u .

a. Select a neighbor (in the reversed graph) with a probability proportional to its edge weight

b. If the neighbor is a known node, store its label and stop. Else, repeat Step a. 如果鄰居是已知節點，則存儲其標籤並停止。否則，重複步驟a。

c. Average the labels obtained in Step 2 to estimate the label for user u.

我們現在有Adsorption演算法的隨機遊走版本。為了估計所有用戶的標籤，我們可以為每個用戶重複這種隨機遊走演算法。

Each random walk needs to end, so we designated the known nodes as the sinks where the random walk stops. 每個隨機遊走都需要結束，因此我們可以將已知節點指定為"匯點" 作為Random walk 停止的地方 . (source and sinks , 原點和匯點 ) 但是，我們可能想要儘早結束隨機遊走。比如在已知用戶非常稀少的情況下 , Random Walk 老是停不下來 , 這時候我們就想儘早結束他 .

In that case, we can add more users as sink, (添加更多用戶作為匯點 ) or more generally, assign a sink probability to each node. This sink probability is also known as the injection probability. 注入概率 ?

如何使用吸附推薦？How to use adsorption for recommendation?

一旦我們擁有吸附演算法，將其應用於推薦是非常簡單的。關鍵的想法是，對於任何推薦系統，我們可以在用戶和項目之間構建一個二部圖(bipartite graph )。用戶與項目之間的每個edge 傳達了(conveys)用戶與項目之間的 similarity （例如，用戶對項目的評分）。

關於 bipartite graph

維基百科中對二分圖的介紹為：二分圖是一類圖(G,E)，其中G是頂點的集合，E為邊的集合，並且G可以分成兩個不相交的集合U和V，E中的任意一條邊的一個頂點屬於集合U，另一頂點屬於集合V。一個簡單的形象表示如下圖：

For recommendation, the task of adsorption is to find relevant items for each user. We consider relevant items for each user as the label vector(我們將每個用戶的相關(relevant) item 視為標籤向量 (label vector) ), and items as known nodes in the graph. (將 items 視為圖中已知的節點) , Thus, the values of a users label vector represent relevance of each item for a user ( 因此，用戶標籤向量的值代表每個 items 對用戶的相關性 )

引用 - 未獲授權

Quera :