論文學習：Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph

論文《Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph》發(fā)表于2008年，是相對比較早的一篇有關(guān)于YouTube推薦系統(tǒng)的文章棒厘。

1.簡介

在最初的階段黄痪，YouTube認為應該給用戶推薦曾經(jīng)觀看過視頻的同類視頻，或者說擁有同一標簽的視頻。然而此時绩鸣，YouTube的視頻已是數(shù)千萬量級鼎文，主要困難在于，盡管可以通過基于計算機視覺的技術(shù)可靠地推斷出某些標簽贬墩，但尚不存在任何令人滿意的機制來對視頻中的大部分內(nèi)容進行標簽榴嗅；更為困難的是，YouTube視頻中存在的標簽通常很小陶舞，他們只捕獲一小部分內(nèi)容嗽测。解決該困難的核心方案有兩部分：一是基于用戶共同觀看記錄構(gòu)建的圖結(jié)構(gòu)（Video Co-View Graph）；二是基于此數(shù)據(jù)結(jié)構(gòu)的算法肿孵，被稱為吸附算法（Adsorption Algorithm）唠粥。

2.共視圖結(jié)構(gòu)

共視信息為視頻推薦提供了簡單的基礎(chǔ)⊥Ｗ觯可以如下構(gòu)建通常用作基于項目的協(xié)作過濾系統(tǒng)的基礎(chǔ)的簡單系統(tǒng)晤愧。假設用戶U觀看了兩個視頻J和K；從我們的共同觀看統(tǒng)計數(shù)據(jù)中雅宾，我們知道看到視頻J的許多其他用戶也看到了視頻L养涮，M，N眉抬；類似地贯吓，對于視頻K，我們知道許多其他用戶看到了視頻N蜀变，O悄谐，P，Q库北；因此爬舰，根據(jù)他對J和K的觀看们陆，我們可能推薦給U的視頻可以簡單地看作是兩個共同視圖集的集合：L，M情屹，N坪仇，O，P垃你，Q椅文。為了對推薦進行排名，我們可以查看一個視頻的瀏覽量（這將推薦流行視頻）惜颇、每個視頻的共同觀看次數(shù)（這將推薦流行視頻皆刺，考慮到用戶所看到的內(nèi)容），或者考慮每個視頻被推薦給U的次數(shù)（注意凌摄，視頻N被推薦了兩次）等因素給出一個打分函數(shù)羡蛾。

3.吸附算法

作者在本文中用大量篇幅講述了吸附算法（Adsorption Algorithm ），該算法的目的就是為了解決視頻標簽的擴散锨亏，當我們有一個小的labeled數(shù)據(jù)集和一個很大的unlabeled數(shù)據(jù)集時痴怨，可以通做Adsorption將label從小的數(shù)據(jù)集推廣到大數(shù)據(jù)集上。論文介紹了三個吸附算法屯伞，分別是通過均值的吸附腿箩，通過隨機游走的吸附和通過線性系統(tǒng)的吸附。
吸附算法是基于 $G$ 圖的劣摇，而這個圖 $G=<V,E,\omega>$ 就是視頻間的關(guān)聯(lián)度圖珠移，公式中 $V$ 代表圖中的節(jié)點，也就是一個個視頻末融，注意節(jié)點會包含多個標簽钧惧。 $E$ 代表節(jié)點間的連線，也就是視頻之間是關(guān)聯(lián)的勾习。而 $\omega$ 代表邊的權(quán)重浓瞪，也就是視頻之間的關(guān)聯(lián)程度，文章中是用用戶共同觀看次數(shù)來表示這個權(quán)重巧婶，用戶共同看過這兩個視頻的次數(shù)越多乾颁，這個權(quán)重越大。如果沒有艺栈，則兩個視頻間沒有關(guān)聯(lián)英岭，也就是沒有邊。
均值吸附：
均值吸附的算法流程如下：