CWYAlpha

Just another WordPress.com site

Thought this was cool: Exploitation and Exploration

leave a comment »


假设有这么个网站,用户只能通过推荐系统才能找到自己需要的信息,除此之外没有其他的路径。那么,一个用户对一个物品是否喜欢,必须得推荐系统推荐给他之后,收集他对这个物品的反馈才能知道。也就是说,如果推荐系统不推荐给他,我们永远也不知道这个用户对这个物品是否喜欢。

那么,假设在这个系统刚上线的第一天,我们把所有的物品随机的推荐给用户,从而保证每个物品都有一定的展示之后,我们可以收集的物品的平均点击率。这里面有很多点击率高的物品,也有很多点击率低的物品。

第二天,我们又要做推荐了,最自然的想法就是把我们已经知道的点击率高的物品推荐给用户,而点击率低的物品就不投放了。这样的系统就是一个Exploitation的系统,也就是尽力利用已知的高点击率的物品投放给用户。

但是,如果一个系统只有Exploitation,会出现以个问题:
物品的点击率其实是变化的,假设我们只投放第一天点击率高的10个物品,那么这10个物品之外的其他物品我们就收集不到他们的点击率,那么如果这些物品里忽然有某个物品点击率会变高,我们也是不知道的。而且如果这些物品是新闻,那么其实第一天他们的点击率最高,然后随着时间的推移,他们的点击率很快就下降了。

所以,我们在投放时不能只考虑Exploitation,还需要考虑Exploration,就是投放一些预估点击率较低的物品,保证他们每天有一定的投放量,收集到他们的点击率变化,从而能在他们点击率变高的那一天准确的捕捉到这个信息,提高他们的投放量。

因此,一个好的系统需要平衡Exploitation(投放目前预估点击率高的物品)和Exploration(投放目前预估点击率低的物品或者新的物品)。从另一个角度说Exploitation代表了短期利益,而Exploration代表了长期利益。

那么如何平衡这两点,已经有很多数学方面的探讨了,大家可以在google搜索相关的论文。其中有一个最显而易见的方法这里可以提一下:
1. 每天利用x%的流量投放预估点击率高的物品
2. 利用剩下的1-x%的流量随机投放预估点击率低的物品
这个方法很简单,不过从数学上证明这个方法的损失就是比较复杂的事情了,有兴趣的同学可以搜索相关的论文。

您可能也喜欢:

PageRank算法的几个主要问题

Twitter的用户推荐系统

HTML DOM

圣诞快乐

N-最短路径分词算法

无觅

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

Written by cwyalpha

九月 14, 2012 在 8:58 上午

发表在 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 博主赞过: