Netflix推荐系统(第二部分)—— 排序

标签: 未分类 | 发表时间:2012-06-23 13:51 | 作者:xlvector
分享到:
出处:http://xlvector.net/blog

Netflix最近发表了第二篇关于他们推荐系统的技术blog,相比第一篇,这篇blog透露了不少技术细节。因此这里我准备翻译并分析一下这篇博客。这篇blog很长,这里首先分析第一部分:排序。

In part one of this blog post, we detailed the different components of Netflix personalization. We also explained how Netflix personalization, and the service as a whole, have changed from the time we announced the Netflix Prize.The $1M Prize delivered a great return on investment for us, not only in algorithmic innovation, but also in brand awareness and attracting stars (no pun intended) to join our team. Predicting movie ratings accurately is just one aspect of our world-class recommender system. In this second part of the blog post, we will give more insight into our broader personalization technology. We will discuss some of our current models, data, and the approaches we follow to lead innovation and research in this space.

在第一部分,我们讨论了Netflix个性化推荐系统的不同应用。我们也解释了Netflix的推荐系统自从我们宣布Netflix Prize后是如何变化的。100万美元的比赛对Netflix无论是在算法的创新还是在宣传Netflix,帮助招聘上都带来了很大的帮助。不过,准确的预测电影的评分只是我们系统的一方面,在第二部分,我们将会更加深入的讨论个性化推荐技术,我们会讨论一下我们用到的模型,数据和方法。

Ranking 排序

The goal of recommender systems is to present a number of attractive items for a person to choose from. This is usually accomplished by selecting some items and sorting them in the order of expected enjoyment (or utility). Since the most common way of presenting recommended items is in some form of list, such as the various rows on Netflix, we need an appropriate ranking model that can use a wide variety of information to come up with an optimal ranking of the items for each of our members.

推荐系统的目的是给用户提供一个包含令他们感兴趣的物品的推荐列表。完成这个任务的简单方法是对于任意一个用户和物品,计算用户对物品的兴趣权重,然后将物品按照权重排序并展现给用户。因此,推荐系统的问题就转化为一个如何针对一个用户,将物品进行排序的问题。

If you are looking for a ranking function that optimizes consumption, an obvious baseline is item popularity. The reason is clear: on average, a member is most likely to watch what most others are watching. However, popularity is the opposite of personalization: it will produce the same ordering of items for every member. Thus, the goal becomes to find a personalized ranking function that is better than item popularity, so we can better satisfy members with varying tastes.

如果你正在寻找一个能够最大化用户消费的排序函数,那么最显然的基本函数就是物品的热门度。原因是显然的,每个人都很有可能喜欢其他用户都喜欢的物品。但是,热门度和个性化是对立的,单纯靠热门度设计排名函数会使得所有人的推荐结果都是一样的。因此,我们的目标是找到一个个性化排名函数,他的性能要比物品热门度好,从而我们能够满足不同用户的不同口味。

Recall that our goal is to recommend the titles that each member is most likely to play and enjoy. One obvious way to approach this is to use the member’s predicted rating of each item as an adjunct to item popularity. Using predicted ratings on their own as a ranking function can lead to items that are too niche or unfamiliar being recommended, and can exclude items that the member would want to watch even though they may not rate them highly. To compensate for this, rather than using either popularity or predicted rating on their own, we would like to produce rankings that balance both of these aspects. At this point, we are ready to build a ranking prediction model using these two features.

既然我们的目标是给每个用户推荐他们最有可能播放并喜欢的视频。最简单的方法是用我们估计出的用户对物品的评分来代替前面的物品热门度。不过利用预测评分会给用户推荐过于冷门或者用户不熟悉的视频,而且不会给用户推荐那些他们不会打高分但会观看的视频。为了解决这个问题,我们并不会只用热门度或者预测评分,我们希望能够设计出一个能够平衡这两种因素的排名函数。因此,我们可以将预测评分和热门度都作为特征,在此基础上设计一个排序的模型。

(注:关于直接利用预测评分进行排序的缺点可以举一个简单的例子。假设有一个美国人,只看英文电影。但这时如果有个很好的中文电影,看他的中国人都给他打了很高的分数。这时候如果我们用评分预测模型,基本上也会预测出这个美国人会给这个中文电影很高的评分。但显然,将这部电影推荐给美国人是不合适的。这里的原因是,评分预测模型预测的是用户如果看完了这个电影,会给电影打多少分,而不是预测用户会不会看这部电影)

There are many ways one could construct a ranking function ranging from simple scoring methods, to pairwise preferences, to optimization over the entire ranking. For the purposes of illustration, let us start with a very simple scoring approach by choosing our ranking function to be a linear combination of popularity and predicted rating. This gives an equation of the form frank(u,v) = w1 p(v) + w2 r(u,v) + b, where u=user, v=video item, p=popularity and r=predicted rating. This equation defines a two-dimensional space like the one depicted below.

业界有很多种设计排序模型的方法,从pointwise到pairwise,各种方法都可以用来优化排序。不过我们可以从一个简单的模型开始,这个模型将各种热门度和预测评分通过一个系数进行线性加权。

Once we have such a function, we can pass a set of videos through our function and sort them in descending order according to the score. You might be wondering how we can set the weights w1 and w2 in our model (the bias b is constant and thus ends up not affecting the final ordering). In other words, in our simple two-dimensional model, how do we determine whether popularity is more or less important than predicted rating? There are at least two possible approaches to this. You could sample the space of possible weights and let the members decide what makes sense after many A/B tests. This procedure might be time consuming and not very cost effective. Another possible answer involves formulating this as a machine learning problem: select positive and negative examples from your historical data and let a machine learning algorithm learn the weights that optimize your goal. This family of machine learning problems is known as “Learning to rank” and is central to application scenarios such as search engines or ad targeting. Note though that a crucial difference in the case of ranked recommendations is the importance of personalization: we do not expect a global notion of relevance, but rather look for ways of optimizing a personalized model.
当我们有了这个排序函数后,我们可以将视频按照这个函数进行排序。不过很多人可能会好奇,我们是如何知道这两个因素的线性融合系数的。有两种方法可以找到这个用户系数,第一种是遍历所有的权重可能,并通过AB测试找到最好的权重。这种方法优化速度很慢,效率很低。第二种方式将这个问题转化为一个极其学习的问题,通过收集日志找到正样本和负样本,然后通过一种叫做Learning to rank (LTR)的方法找到这个系数。LTR被广泛的用于搜索引擎和精准广告投放中。

As you might guess, apart from popularity and rating prediction, we have tried many other features at Netflix. Some have shown no positive effect while others have improved our ranking accuracy tremendously. The graph below shows the ranking improvement we have obtained by adding different features and optimizing the machine learning algorithm.

你们应该会猜到,除了热门度和预测评分,我们还尝试了很多不同的特征。有些特征基本没用,而有些特征对排序有很重要的作用。下面的图展示了我们采用不同特征后系统的性能。

Many supervised classification methods can be used for ranking. Typical choices include Logistic Regression, Support Vector Machines, Neural Networks, or Decision Tree-based methods such as Gradient Boosted Decision Trees (GBDT). On the other hand, a great number of algorithms specifically designed for learning to rank have appeared in recent years such as RankSVM or RankBoost. There is no easy answer to choose which model will perform best in a given ranking problem. The simpler your feature space is, the simpler your model can be. But it is easy to get trapped in a situation where a new feature does not show value because the model cannot learn it. Or, the other way around, to conclude that a more powerful model is not useful simply because you don’t have the feature space that exploits its benefits.

很多监督学习的方法都能被用来设计排序模型。其中代表性的有Logistic回归,支持向量机,人工神经网络或者决策树类的算法(GBDT)。此外,有很多专门为排序设计的模型,比如RankSVD和RankBoost。很难说这些方法中哪些比较好。如果你的特征很简单,那么你也可以选择简单的方法。不过很多时候你会发现加入了一个新的特征,但模型却无法学到它。或者用了一个更加NB的模型,但是在你的特征空间上却没有什么提升。

————————————————–

这一部分基本上应该是Netflix推荐系统的离线部分。Netflix提到的这些Ranking的方法一般来说不太可能实时训练。他们通过离线训练找到不同特征的权重,然后在线通过权重模型将实时获得的特征组合成最后的用户对物品的兴趣评分。

不过Netflix没有透露他们的优化目标是什么。一种可能的目标是优化用户对推荐结果的点击。可以将用户点击的推荐结果作为正样本,将用户看到却没有点击的推荐结果作为负样本,然后进行学习。这样做在Netflix是可行的,因为Netflix的页面到处都是推荐系统,推荐几乎是除了搜索以为获得信息的唯一手段。因此Netflix可以收集到大量的用户对推荐结果的点击信息,从而进行模型训练。

不过利用点击并不完美,更好一点是利用转化,因为转化才代表了收益的增长。不过转化数据相对点击就更加稀疏了。

此外,Netflix的博客介绍他们最终的性能相对只利用热门度提高了2倍左右。这里他们并没有说他们通过什么指标评测性能。如果是利用点击率,那么Youtube和Hulu都有过类似的实验,也都公开过他们的提升率。他们的提升率也都在2-3倍左右,从而说明视频网站的个性化的提升率大概就在2-3倍左右。

您可能也喜欢:
Movie/Video Recommendation : Jinni, GetGlue, Netflix …
Min-Hash和推荐系统
[resys 精华帖]为什么中国没有Netflix?
Netflix Update Leaderboard
Photos of The Ensemble from Netflix Prize
无觅

相关 [netflix 推荐系统 二部] 推荐:

Netflix推荐系统(第二部分)—— 排序

- - xlvector - Recommender System
Netflix最近发表了第二篇关于他们推荐系统的技术blog,相比第一篇,这篇blog透露了不少技术细节. 因此这里我准备翻译并分析一下这篇博客. 这篇blog很长,这里首先分析第一部分:排序. We will discuss some of our current models, data, and the approaches we follow to lead innovation and research in this space..

Netflix 公布个性化和推荐系统架构

- - 互联网分析
Netflix的推荐和个性化功能向来精准,前不久,他们公布了自己在这方面的系统架构. 3月27日,Netflix的工程师 Xavier Amatrain和 Justin Basilico在官方博客 发布文章,介绍了自己的个性化和推荐系统架构. 要开发出这样的一个软件架构,能够处理海量现有数据、响应用户交互,还要易于尝试新的推荐方法,这可不一点都不容易.

聊聊 API Gateway 和 Netflix Zuul

- - ScienJus's Blog
最近参与了公司 API Gateway 的搭建工作,技术选型是 Netflix Zuul,主要聊一聊其中的一些心得和体会. 本文主要是介绍使用 Zuul 且在不强制使用其他 Neflix OSS 组件时,如何搭建生产环境的 Gateway,以及能使用 Gateway 做哪些事. 不打算介绍任何关于如何快速搭建 Zuul,或是一些轻易集成 Eureka 之类的的方法,这些在官方文档上已经介绍的很明确了.

Min-Hash和推荐系统

- - xlvector - Recommender System
前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼. 不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处. 其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数.

推荐系统实战

- - 博客园_首页
推荐算法:基于特征的推荐算法. 推荐算法准确度度量公式:. 其中,R(u)表示对用户推荐的N个物品,T(u)表示用户u在测试集上喜欢的物品集合. 集合相似度度量公式(N维向量的距离度量公式):. 其中,N(u)表示用户u有过正反馈的物品集合. 其中,S(u,k)表示和用户u兴趣最接近的K个用户集合;N(i)表示对物品i有过正反馈的用户集合;w(u,v)表示用户u和用户v的兴趣相似度;r(v,i)表示用户v对物品i的兴趣.

推荐系统杂谈

- - 后端技术杂谈 | 飒然Hang
推荐系统是近些年非常火的技术,不管是电商类软件还是新闻类app,都号称有精准的推荐系统能给你推送你最感兴趣的内容. 现象级的资讯类app“今日头条”就得益于此成为了势头非常猛的一款产品. 本文就针对推荐系统讲述一些相关概念和实践经验. 首先需要明确的就是推荐系统的目标,一般来说不外乎以下几个:. 用户满意性:首当其冲的,推荐系统主要就是为了满足用户的需求,因此准确率是评判一个推荐系统好坏的最关键指标.

Netflix开源数据流管理器Suro

- - IT经理网
Netflix近日开源了一个叫做Suro的工具,可以收集来自多个应用服务器的事件数据,并实时定向发送到目标数据平台如Hadoop和Elasticsearch. Netfix的这项创新有望成为大数据主流技术. Netflix用Suro进行数据源到目标主机的实时导向,Suro不但在Netflix的数据管道中扮演关键角色,而且也是脱胎大型互联网公司的众多开源数据分析工具中的佼佼者.

Netflix的网站优化经验

- - 程序师
Netflix团队首先要做的一件事是改进他们的整体前端架构. 改版前的netflix.com网站对于服务端生成html标记与客户端的增强这两个过程进行了严格的分离,采用这一设计的主要原因在于前后端所使用的编程语言不同. 服务端主要使用Java的技术栈以生成基本的html页面,而在浏览器端的工作则主要是通过jQuery等JavaScript库的使用为服务端生成的html添加一些客户端的行为.

个性化推荐系统综述

- Tony - 所有文章 - UCD大社区
上个月写过一篇产品推荐的文章,详情请见《我所了解的产品推荐》,内容很泛,多为工作心得. 本周读了几篇相关的论文,收获颇多,分享点干货. 以下内容摘自《个性化推荐系统的研究进展》,该文发表于2009年1月的《自然科学进展》专题评述,作者是刘建国、周涛、汪秉宏. 我略去了具体的算法和许多公式,重点看原理、思路和比较.

Reculike : 开源论文推荐系统

- votis - Resys China
今天这篇博文主要总结一下reculike的系统架构. 两周前我们宣布发布了reculike的alpha版. 本着分享的原则,今天在这儿介绍一下我们的各个模块的设计方法. 我们这个项目一开始叫paperlens,这是因为我们想学习业界的前辈movielens,开发一个源代码和数据都开源的系统. 关于数据的开源,我想当用户数达到一定程度后,每个月会dump一次我们所有的数据库(密码等隐私信息除外),放到网络上供大家下载.