论文学习：Video Suggestion and Discov

论文《Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph》发表于2008年，是相对比较早的一篇有关于YouTube推荐系统的文章。

1.简介

在最初的阶段，YouTube认为应该给用户推荐曾经观看过视频的同类视频，或者说拥有同一标签的视频。然而此时，YouTube的视频已是数千万量级，主要困难在于，尽管可以通过基于计算机视觉的技术可靠地推断出某些标签，但尚不存在任何令人满意的机制来对视频中的大部分内容进行标签；更为困难的是，YouTube视频中存在的标签通常很小，他们只捕获一小部分内容。解决该困难的核心方案有两部分：一是基于用户共同观看记录构建的图结构（Video Co-View Graph）； 二是基于此数据结构的算法，被称为吸附算法（Adsorption Algorithm）。

2.共视图结构

共视信息为视频推荐提供了简单的基础。可以如下构建通常用作基于项目的协作过滤系统的基础的简单系统。假设用户U观看了两个视频J和K；从我们的共同观看统计数据中，我们知道看到视频J的许多其他用户也看到了视频L，M，N；类似地，对于视频K，我们知道许多其他用户看到了视频N，O，P，Q；因此，根据他对J和K的观看，我们可能推荐给U的视频可以简单地看作是两个共同视图集的集合：L，M，N，O，P，Q。为了对推荐进行排名，我们可以查看一个视频的浏览量（这将推荐流行视频）、每个视频的共同观看次数（这将推荐流行视频，考虑到用户所看到的内容），或者考虑每个视频被推荐给U的次数（注意，视频N被推荐了两次）等因素给出一个打分函数。

3.吸附算法

作者在本文中用大量篇幅讲述了吸附算法（Adsorption Algorithm ），该算法的目的就是为了解决视频标签的扩散，当我们有一个小的labeled数据集和一个很大的unlabeled数据集时，可以通做Adsorption将label从小的数据集推广到大数据集上。论文介绍了三个吸附算法，分别是通过均值的吸附，通过随机游走的吸附和通过线性系统的吸附。
吸附算法是基于图的，而这个图就是视频间的关联度图，公式中代表图中的节点，也就是一个个视频，注意节点会包含多个标签。代表节点间的连线，也就是视频之间是关联的。而代表边的权重，也就是视频之间的关联程度，文章中是用用户共同观看次数来表示这个权重，用户共同看过这两个视频的次数越多，这个权重越大。如果没有，则两个视频间没有关联，也就是没有边。
均值吸附：
均值吸附的算法流程如下：

图中G表示视频的关联图，L表示所有视频标签的合集，而 表示所有有标签视频节点的合集。 代表节点u的标签分布。整个流程很简单，节点 v 的标签的概率分布等 于点 u 和 v 之间的权重 乘以点 u 的 , 通过这样一个传递 , 将邻居和自己的标签进行了"平均" 。
随机游走的吸附：
随机游走的吸附就是将上图中 转换成 ， 其中
表示随机遍历中选择节点u的概率。该算法就是将每一个顶点v的标签发到相关联的邻居上，在每一次传递结束后，对顶点的标签进行归一化。
线性吸附：
线性吸附就是将 理解为线性组合中占的比例。

4.总结

本文发表的时间较早，详细介绍了推荐系统中的吸附算法，主要解决的问题是如何有效的扩大视频标签，最后的实验离线测试效果很好，通过使用吸附算法，能够提高YouTube中建议的预期效率。

注：论文下载链接
学习参考链接