Youtube视频推荐算法：从10页论文到4页论文的变迁

所以说豆瓣广播是个好东西，长久以来已经怠于主动关注paper的我，每次都能通过我那些专业敬业的友邻们发现有意思的文章或话题，知识因分享而伟大！而这一次，这篇来自youtube的4页论文[1]，最初是通过Chen_1st同学的博客介绍知道的。追溯过去，又找到了Greg Linden的评荐博客。这篇文章很新，以至于我根本找不到免费的全文下载，于是很感谢zibuyu博士帮了一忙，还把youtube在08年发的那篇10页论文[2]一并给我发了过来，于是就有这个有点标题党的题目。

实话说，那篇10页论文我没仔细看，但还是先来回顾一下。08年的论文主要思想是把推荐问题建立在一个user-video的图上，试图在该图上给user u找到合适的video v。作者认为对某个u，他感兴趣的v应该是符合如下三个条件的。
1、 u与v之间的路径应该是短的；
2、 u与v之间应该有多条路径可达；
3、 u与v之间的路径应该排除掉那些度很高的节点。

为了在图上搜索符合这三个条件的解，作者提出了多种方法来解决这个被命名为Adsorption的算法，如Averaging、Random Walk、Linear System。给出了不少的概念定义与算法描述，并附赠一系列美好的实验结果。

但在那篇4页的论文里，之前的那些工作似乎都成了浮云，除了是来自于同一个公司的人，做的是同一个推荐产品之外，你几乎很难从这篇文章里再找到从前系统的影子，不单作者换了，行文风格从研究人员变成了工程师，甚至连最后的REFERENCES都没有对之前的文章加以引用。于是Greg不无戏谑地说：尽管我们做了上十年的工作，中间还穿插了对netflix竞赛的孜孜探讨，但好像一切又回到了原点，古老的item-based思想仍然发挥着其独有的魅力。

下面看看在遥远的墙外，那个叫youtube的视频网站始祖做了些什么复古式的工作。

首先无需求不产品，推荐产品也是要面向用户的特定需求的。Youtube用户的需求主要有三个方面：明确知道自己要看哪个视频；通过搜索来获取某些主题的视频；也不知道看什么，纯粹逛逛，找找乐子。Youtube的推荐产品面向的就是第三种需求，需要达成的目标是：视频推荐的时效性、精确性与多样性，可解释性是一个plus。

接下来几个工程师开始进行系统设计，搬出了诸如解耦、降低系统复杂性等等工程概念之后，介绍了他们本质上就是简单的item-based的推荐算法（但他们说这是关联规则）。最重要的公式就是以下的video相似性计算公式：

其中分子是video i与video j在用户session数据库中共同出现的次数，分母是一个规范化函数。当函数取值为ci时，这其实就是关联规则的置信度的计算公式，而当函数取值为vi与vj的模的乘积时，这个就是余弦相似度计算公式（因为在向量取值为1与0时，cij等于vi与vj的内积）。所以可以说这是关联规则与余弦相似度的通式。但youtube对这个函数的取值是ci * cj，如果把i作为种子，要找i的相似video的话，ci是不会影响到相似video的排序的，所以只有cj在起作用，而cj的作用则起到了打压热门视频的效果（因为播放得越多，cj越大，相似度越小），从另一个侧面可以提升推荐的多样性。当然这只是一种最简单的相似性描述，youtube实际系统当中还会考虑一些别的因素，如播放时间戳、视频的元信息等等。

理论上可以为每一个video pair计算出一个相似度rij，但实际中通常要对这个值进行截断，而以video作为节点，以有效的rij为边的权值就构成了一个有向的video graph。接下来就是根据这个图来为某个用户u生成候选推荐了。假设我们拥有用户u的一个视频种子集S，它可能来自于用户的收藏、评星或者简单的收看记录，一般意义上的item-based方法这时就会对S中的每一个视频，寻找它在video graph上的最近邻居，并以此作为推荐的候选。如下面的公式所示。

而这篇文章的方法稍有不同，但也很简单。作者们认为一般的item-based方法通常会压缩推荐候选的范围，即这种方法得到的结果通常多样性比较差。于是他们在第一步搜索最近邻居的基础上加以扩展：搜索多阶的最近邻居，如下面的两个公式所示。

这样就完成了推荐池的扩容。但这个推荐池通常比较庞大，而推荐系统只能从中选择几个或几十个推送到用户面前，这样就必须知道其中哪些视频的权重更大，哪些更小，所以就需要一个赋权的过程。Youtube对视频的赋权方式主要考虑了三方面的因素：1）视频的质量；2）跟用户的切合程度；3）多样性。第一个因素取决于视频上传时间、播放、评星、收藏、分享、评论等等视频本身的数据。第二个因素取决于用户对种子集中视频的喜好程度，以及推荐池中的视频跟种子集视频的相似程度。第三个因素可以通过多种方法来评判。然后把这三方面的因素作一个线性加权，就得到了推荐池中每个视频的权重，接下来的推荐就顺理成章了。

如此三步：构造video graph；在图上生成扩展的候选推荐池；为推荐池的video赋权。就是一个大致的框架，简单明了，非常工程化实用化的实现，一贯的google范。

为了说明这种推荐方法的有效性，作者以最多收看、最多收藏、最多评星的视频作为baseline，用以与推荐视频作比较，实验是在线进行的A/B Test，实验框架我以前也有过简要介绍。实验时间是21天，评判标准是点击率。结果发现，在这段时间里，推荐视频的点击率都稳定地比那三个baseline高出两倍，这已经足够说明问题了。

最后提一个数据，在youtube首页的推荐模块中的视频点击，占了首页视频点击的60%，虽然有模块位置的因素在里面，这也是个相当可观的数字。

Greg那篇博客下面还有一些饶有趣味的讨论话题，比如Greg说这篇文章应该引用早期amazon的那篇关于item-based的文章，因为从推荐算法本质上它们是同一套东西。当然同时Greg也坚称amazon是item-based推荐应用的始祖，而有人则指出，其实这样的思想在90年代的paper就已经有人提出过，但Greg认为这并不影响amazon是第一个把这项技术成功地应用于商业、特别是大规模数据应用领域的始作俑者，就如pagerank的想法在google诞生之前就已经存在，但没有人怀疑google是使用这项技术的成功的先行者。我认同Greg的说法，要是从paper或纯粹想法的角度不断回溯，估计某位古希腊哲人或古中国的科学家都可以跳出来说：哥当初就已经是这么想的！

参考文献：
[1] Davidson, J. and Liebald, B. and Liu, J. The YouTube video recommendation system. Proceedings of the fourth ACM conference on Recommender systems. 2010
[2] Baluja, S. and Seth, R. and Sivakumar, D. and Jing, Y. Video suggestion and discovery for youtube: taking random walks through the view graph. Proceeding of the 17th international conference on World Wide Web. 2008

转自：http://www.wentrue.net/blog/?p=1181