CWYAlpha

Just another WordPress.com site

Thought this was cool: Netflix推荐系统(第二部分)—— 排序

leave a comment »


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?

Twitter的用户推荐系统

Netflix Update Leaderboard

无觅

from xlvector – Recommender System: http://xlvector.net/blog/?p=854

Written by cwyalpha

六月 23, 2012 在 2:23 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: