2012年11月17日星期六

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


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
关于作者

没有评论:

发表评论