推荐系统的苟且和远方

苟且和远方

提到推荐系统,你们会首先想到什么?

产品和运营们首先想到的就是打标签,而做过的人还会想到协同过滤(collaborative filter,下面简称CF)。

是的,CF几乎是推荐系统发展史上浓墨重彩的一笔,其背后的思想简单深刻,在万物互联的今天,协同过滤的威力更加强大。CF看上去是一种技术,不如说是一种方法论,不是机器在给你推荐,而是“集体智慧”在给你推荐。

CF的基本假设就是“物以类聚,人以群分”,你的圈子决定了你能见到的物品。这很靠谱,但是却隐藏了一些重要的问题:作为用户的我们还可能看到新的东西吗?还可能有惊喜吗?还可能有圈子的流动吗?

是咯,我就知道你会提出这么精妙的问题,要不然也不会有这篇文章了。毕竟你我都曾经站在高高的谷堆上唱过:“推荐系统不是只有眼前的苟且,还有诗和远方的田野”。这也是在推荐和广告界被大量研究的EE问题(Exploit & Explore),Exploit就是眼前的苟且,Explore就是诗和远方的田野。

做Explore的方法有很多,bandit算法是其中的一种流派。前面也介绍过几种bandit算法,基本上就是估计置信区间的做法,然后按照置信区间的上界来进行推荐,以UCB、LinUCB为代表。

作为要寻找诗和远方的bandit浪漫派算法,能不能和CF这种名门望族结合起来呢?事实上已经有人这么尝试过了,前阵子在arxiv看到一篇论文,题目是Collaborative Filtering Bandits[1],arxiv上还有另一篇是同一作者先前的尝试(Online Clustering of Bandits)[2],两者的区别是后者只对用户聚类(即只考虑了User-based的协同过滤),而前者采用了协同聚类(co-clustering,可以理解为item-based和user-based两种协同方式在同时进行),后者算是前者的一个特殊情况。今天我们就一起来开拓一下思路,看看Collaborative Filtering Bandits这篇文章是如何把CF和Bandit结合起来的。

bandit怎么结合CF

很多推荐场景中都有这两个规律:

  1. 相似的用户对同一个物品的反馈可能是一样的。也就是对一个聚类用户群体推荐同一个item,他们可能都喜欢,也可能都不喜欢,同样地,同一个用户会对相似的物品反馈相同。这是属于CF可以解决的问题;
  2. 在使用推荐系统过程中,用户的决策是动态进行的,尤其是新用户。这就导致无法提前为用户准备好推荐候选,只能“走一步看一步”,是一个动态的推荐过程。

这篇文章就提出,每一个推荐候选item,都可以根据用户对其偏好不同(payoff不同)将用户聚类成不同的群体,一个群体来集体预测这个item的可能的收益,这就有了协同的效果,然后再实时观察真实反馈回来更新用户的个人参数,这就有了bandit的思想在里面。

举个例子,如果你父母给你安排了很多相亲对象,要不要见面去相一下?那需要提前看看每一个相亲对象的资料,每次大家都分成好几派,有说好的,有说再看看的,也有说不行的;你自己也会是其中一派的一员,每次都是你所属的那一派给你集体打分,因为他们是和你“三观一致的人”,“诚不欺我”;这样从一堆资料中挑出分数最高的那个人,你出去见TA,回来后把实际感觉说给大家听,同时自己心里的标准也有些调整,重新给剩下的其它对象打分,打完分再去见,周而复始……

以上就是CF和bandit结合的思想。

另外,如果要推荐的候选item较多,还需要对item进行聚类,这样就不用按照每一个item对user聚类,而是按照每一个item的类簇对user聚类,如此以来,item的类簇数相对于item数要大大减少。

COFIBA算法

基于这些思想,文中设计的算法COFIBA(读作coffee bar),简要描述如下:

在时刻t,有一个用户来访问推荐系统,推荐系统需要从已有的候选池子中挑一个最佳的物品推荐给他,然后观察他的反馈,用观察到的反馈来更新挑选策略。 这里的每个物品都有一个特征向量,所以这里的bandit算法是context相关的。 这里依然是用岭回归去拟合用户的权重向量,用于预测用户对每个物品的可能反馈(payoff),这一点和我们上一次介绍的linUCB算法是一样的。

对比上一次介绍的LinUCB算法,COFIBA的不同有两个:

  1. 基于用户聚类挑选最佳的item(相似用户集体决策的bandit)
  2. 基于用户的反馈情况调整user和item的聚类(CF部分)

整体算法过程如下:

对关键部分用人话来说就是:

在针对某个用户i,在每一轮试验时做以下事情:

  1. 首先计算该用户的bandit参数W(和LinUCB相同),但是这个参数并不直接参与到bandit的选择决策中(和LinUCB不同),而是用来更新用户聚类的;
  2. 遍历候选item,每一个item表示成一个context向量了。
  3. 每一个item都对应一套用户聚类结果,所以遍历到每一个item时判断当前用户在当前item下属于哪个类簇,然后把对应类簇中每个用户的M矩阵(对应LinUCB里面的A矩阵),b向量(payoff向量,对应linUCB里面的b向量)聚合起来,从而针对这个类簇求解一个岭回归参数(类似LinUCB里面单独针对每个用户所做),同时计算其payoff预测值和置信上边界
  4. 每个item都得到一个payoff预测值及置信区间上界,挑出那个上边界最大的item推出去(和LinUCB相同)
  5. 观察用户的真实反馈,然后更新用户自己的M矩阵和b向量(更新个人的,对应类簇里其他的不更新)

以上是COFIBA算法的一次决策过程。在收到用户真实反馈之后,还有两个计算过程:

  1. 更新user聚类
  2. 更新item聚类

如何更新user和item的聚类呢?文章中给出了一个示意图:

解释一下这个图。

(a) 这里有6个user,8个item,初始化时,user和item的类簇个数都是1

(b1) 在某一轮试验时,推荐系统面对的用户是4。推荐过程就是遍历1~8每个item,然后看看对应每个item时,user4在哪个类簇中,把对应类簇中的用户聚合起来为这个item预测payoff和CB。这里假设最终item5胜出,被推荐出去了。

(b2) 在时刻t,item有3个类簇,需要更新的用户聚类是item5对应的user4所在类簇。更新方式:看看该类簇里面除了user4之外的用户,对item5的payoff是不是和user4相近,如果是,则保持原来的连接边,否则删除原来的连接边。删除边之后重新构建聚类结果。这里假设重新构建后原来user4所在的类簇分裂成了两个类簇:{4,5}和{6}

(c) 更新完用户类簇后,item5对应的类簇也要更新。更新方式是:对于每一个和item5(被推荐出的那个item)还存在连接边的item j,都去构造一个user的近邻集合N,这个集合的用户对item j有相近的payoff,然后看看N是不是和刚刚更新后的user4所在的类簇相同,是的话,保留item5和item j之间的连接边,否则删除。这里假设item 3和item 5之间的连接边被删除。item3独立后给他初始化了一个聚类结果:所有用户还是一个类簇。

简单来说就是这样:

  • User-based协同过滤来选择要推荐的item,选择时用了LinUCB的思想
  • 根据用户的反馈,调整User-based和Item-based的聚类结果
  • Item-based的聚类变化又改变了User的聚类
  • 不断根据用户实时动态的反馈来划分User-Item矩阵

cofiba算法也很容易实现,github上就有[3]。论文也从理论和实验两方面证明了它的有效性,但是能否在实际项目中用上,仍然存疑,毕竟复杂度不低。

关于EE问题的思考

之所以想写bandit算法系列,是因为Exploit-Explore这一对矛盾一直客观存在,而bandit算法是公认的一种比较好的解决EE问题的方案。除了bandit算法之外,还有一些其他的explore的办法,比如跟xlvector大牛讨论时,他就提到一种:在推荐时,随机地去掉一些用户历史行为(特征)。

解决Explore,势必就是要冒险,势必要走向未知,而这显然就是会伤害用户体验的:明知道用户肯定喜欢A,你还偏偏以某个小概率给推荐非A。

实际上,很少有公司会采用这些理性的办法做Explore,反而更愿意用一些盲目主观的方式。究其原因,可能是因为:

  1. 互联网产品生命周期短,而Explore又是为了提升长期利益的,所以没有动力做。
  2. 用户使用互联网产品时间越来越碎片化,Explore的时间长,难以体现出Explore 的价值。
  3. 同质化互联网产品多,用户选择多,稍有不慎,用户用脚投票,分分钟弃你于不顾。
  4. 已经成规模的平台,红利杠杠的,其实是没有动力做Explore的。

基于这些,我们如果想在自己的推荐系统中引入Explore机制,需要注意以下几点:

  1. 用于Explore的item要保证其本身质量,纵使用户不感兴趣,也不至于引起其反感。
  2. Explore本身的产品需要精心设计,让用户有耐心陪你玩儿。
  3. 深度思考,这样才不会做出脑残的产品,产品不会早早夭折,才有可能让Explore机制有用武之地。

好了,让我们再唱一遍,结束本系列。

推荐不止眼前的苟且,还有诗和远方的田野。

参考资料:

[1] http://arxiv.org/abs/1401.8257

[2] http://arxiv.org/abs/1502.03473

[3] https://github.com/qw2ky/CoLinUCB_Revised/blob/master/COFIBA.py

本文作者:

陈开江@刑无刀

2013年之前在新浪微博搜索部和商业产品部任资深算法工程师,先后负责过微博反垃圾,基础数据挖掘,智能客服平台,个性化推荐等产品的后端算法。2012-2013领导翻译了《机器学习:实用案例解析》一书。

2013年末加入传统媒体公司车语传媒,任算法主管,负责从零打造公司转型产品考拉FM的个性化推荐系统,如今个性化推荐已成为考拉FM与其他FM之间最大差异化特性。

2015年~2016年,离职创业,公司拿到IDG和晨兴资本的天使投资

 

未经允许不得转载:氢网 » 推荐系统的苟且和远方

支付宝扫码打赏 微信打赏

欢迎点击上方按钮对我打赏

分享到:更多 ()

评论 抢沙发

评论前必须登录!