From 10 pages to 4 pages(YouTube video recommendation system)(YouTube 视频推荐算法浅析)

最近看 Recommender System 的时候对豆瓣一位推荐算法工程师中一篇关于YouTube的博文感兴趣,就把这两篇文章翻来看了下,08年的十页论文求精求细,算法和实验都很详细,10年的四页论文则更注重从系统的角度简介了一下。我就对算法进行了简单总结,如有不妥请指正:

首先是 Shumeet 等人08年提出的 Random Walks through the view graph 算法,文章在引言提出了相关视图(Co-View Graph)的概念,相关视图(Co-View Graph)由视频节点(vertex)、节点之间的边以及标签等构成,节点之间的边是通过用户行为决定的,比如用户同时观看这两个视频。吸收算法(Adsoption Algorithm)是论文的算法基础,本质上是利用节点上的边将节点进行分类的一种算法。文章中具体谈到了以吸收算法为基础的三种算法:

Adsorption via Avergaing

算法描述如下:


        Input: G = ( V,E,w ) , L , V_L

repeat

    for each v\in V \cup \tilde{V} do:

        Let L_v = \sum_{u} w(u,v)L_u

     end-for

     Normalize L_v to have unit L_1 norm

     until covergence

Output: Distributions { L_v | v \in V }


这里 VV_L 分别代表无标签节点和有标签节点,L 代表标签,w 代表节点之间的边,整个算发就是对每个节点进行标签聚合,节点 v 的聚合方式就是通过将所有和 v 之间有边 w(u,v) 的节点 u 的标签聚合起来 L_v 直到整个算法收敛,这里收敛可以通过取阈值的方式。

Adsorption via Random Walks

Random walks 翻译为中文可以叫做“随机游走”吧,用随机数学的概念来说就是在非常短的时间内状态的该变量为1,它以一个节点 v 为起点开始游走,每游走一步将新的一步的节点加入到集合中,直到没有新的节点可加入为止,算法的好处在于计算量比上一种少,随机性也较好。

Adsorption via Linear Systems:

算法如下:


Input: G= ( V , E , w )

Let n:=|V|

Define the linear system of equations in n^2 variables X_{uv} , for u,v \in V

 \centering \sum_{v}X_{uv} = 1~~~~~~\forall u \in V ;  \\ \vspace{1em} \centering \sum_{z: (z,u)\in E} w(z,u)X_{uv} = X_{uv}~~~~~~\forall u,v \in V.


算法的核心就是计算节点到节点之间的权重 X_{uv},每个节点的权重之和为 1,且计算u点到v点得权重方法是通过计算u点通过所有点到达v点权重的线性组合。算法的好处就是能够很好的处理节点标签的更新以及节点的变化。

接着谈谈10年由 James Davidson 等人的 4 页论文,文章短小意赅。首先是 YouTube 视频面临的主要挑战主要有两点:没有足够的元数据和用户交互相对较短和嘈杂。推荐算法为用户不仅提供离散而且与用户相关的视频,也提供些最新的视频,这种推荐是根据用户的个人行为来决定的。输入数据包括视频数据和用户交互数据,用户交互的数据包括隐形和显性数据,如为视频评分,留言,观看多长时间等。数据处理第一步是关联视频:即为视频 v_i 生成一个相关视频的集合 R_i ,这样用户在看视频 v 时用其做种子生成相关视频,采用的是关联规则挖掘技术,定义视频 v_iv_j 关联分数为:

\centering r( v_i , v_j ) = \frac{c_{ij}}{f( v_i , v_j )}

r( v_i , v_j ) 表示连续看了 v_iv_j 的(从哪到哪没关系) f( v_i , v_j )  是考虑了这两个视频和候选视频“全局欢迎度”的归一化函数,最简单的一个方式就是: f( v_i , v_j ) = c_i \times c_j    ,接着根据视频的关联分数排列 R_i 个关联视频。接着是产生推荐候选视频:还是根据得到的关联视频 R_i 生成第一个相关视频集合:

C_1(S) = \bigcup_{v_i \in S} R_i

S 是种子集合(我理解可以是用户所有看过的视频),将 S 中所有的节点 v_i 通过上面的关联算法生成 R_i 集合的集合 \bigcup_{v_i \in S} R_i 为第一个相关视频集合,并用递归的方式形成第 N 个视频集合:

C_n(S) = \bigcup_{v_i \in C_{n-1}} R_i

我们定义了 C_0 = S 那么我们的推荐应该把 S 剔除,得到最终的推荐视频集合:

C_n(S) = \bigcup_{v_i \in C_{n-1}} R_i \slash S

因为视频分支多,即使只有少量的种子也会有大量的推荐,最后就是排名了,这可以参考三个要素:视频质量、用户的喜好、多样化,最终将这三个参数通过线性组合的方式得到排序的分。

下面是我对 YouTube 视频推荐算法分类的看法,如果不妥请指正:首先我认为两篇论文阐述的 YouTube 视频推荐算法应该都是基于关联规则的推荐算法(Association Rule-based Recommnendation),08年算法核心是吸收算法(Adsorption Algorithm),简单来说就是把用户 u 和用户 v 看过的视频关联起来,10年的算法核心是 r( v_i , v_j ) = \frac{c_{ij}}{f( v_i , v_j )} 关联系数。所以YouTube 视频推荐算法不应该是 item-based CF 算法,我理解的 CF 算法核心应该具有 user-item 的矩阵,至于是 user-based 还是 item-based 就取决于对矩阵行列的分析。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据