常用推荐算法

这篇文章首发在【阿里技术】这个微信公众号,内容上主要围绕电商中用到的一些推荐算法,参考了 Xavier Amatriain 在CMU的 Machine Learning 暑期学校上的讲授的内容。不仅有提到一些基础的推荐算法,也讲了一些推荐系统领域比较新的研究方向,个人认为是一篇不错的概括性文章,摘录在博客里,加入一点自己的理解。

目录

推荐系统简介

g2

推荐系统本身就是为了解决信息过载这个问题而出现的,在互联网出现以后,人们在生活中所能获取到的消息呈爆炸性增长。从衣食住行再到其他一些更高端的需求,我们都有非常多的选择,但是要怎么在较短的时间内从这么多的选择里找到自己最感兴趣的那个呢?推荐系统解决的就是这样一个问题。

g3

事实上,解决信息过载的问题并不是只有推荐系统这一个手段。PC时代早期出现的门户网站是一种手段,帮助上网的人快速找到想要浏览的网站。而搜索引擎也是一种很好的办法,通过关键字来筛选出用户想要看的网页。但以上两种途径展示的内容对任意两个上网用户来说都是相同的。由于每个人的喜好总会有一部分和别人重叠,而一部分比较特殊,为了展示的内容能尽可能符合大多数人的期望,导航/搜索引擎只能给出重叠最多的部分,也即最流行的网站/网页,没有办法做到根据不同用户的喜好提供不同结果。推荐系统则致力于解决这一难点,实现千人千面的效果。

P.S. 事实上,目前在搜索引擎这个研究领域,已经有根据用户搜索习惯和搜索历史进行个性化结果展示的研究了,可以说是吸取了推荐系统的精髓进行改进的结果吧。随着计算机处理数据的能力上升,个性化将是未来的必然趋势。

g4

Netflix举办的百万美元竞赛绝对是推荐系统发展史上一个重要的标志,可以说从那以后,推荐系统的研究才开始真正地被重视,随后就是百花齐放,越来越多的算法和推荐架构被提出来了。

特别Mark一下推荐系统的未来——基于上下文的推荐,这个确实是很值得思考的。尽管目前关注推荐系统的研究已经不少了,但绝大部分都是使用协同过滤技术,或者把推荐视作一个二分类问题来解决的。有一个很明显的缺点就是它们都需要大量的标记数据才能实现准确的预测。还有一个问题就是,这里说的推荐并没有针对用户实际所处的环境来给出结果,只是从用户的历史记录和习惯来推测,给出他可能喜欢的其它商品,而没有关注用户是否真的有需求怎么把我们从大量历史数据中学习到的知识应用到用户所处的具体场景中?这是一个等待研究的相当有价值的问题。

g5

g6

这些指标都蛮有意思的,但是并不是都能通过离线测试来得出,比方说用户满意度、惊喜性等等,都是一些比较主观的东西,在这种情况下,怎么能够提高这些指标呢?

g7

这里列了几个比较传统的因素:相似的人越喜欢一件物品,那么用户就越有可能也喜欢它;用户对相似的物品越喜爱,那么也越有可能喜欢这一件物品;对这件物品的评论中赞赏的话越多,则用户也越有可能对这件物品感兴趣;用户和这件物品的历史交互行为越多,也意味着用户对这件物品越感兴趣…

g8

虽然说我们做研究主要是针对推荐的算法,但在工业界里,一个真正的推荐产品,必须要有良好的用户界面,准确的产品定位,否则从一开始就输了,连用户数据都获取不到,自然也就没有所谓个性化的后话了。特别地,花在处理数据上的时间应该是最多的,因为从真实场景中收集到的数据往往都有很大的噪音,如果不经过处理就放进算法跑的话,算法再好也难以获得好的结果。

g9

传统的推荐算法

非个性化推荐:热度排行(Popularity)

g10

其实在没有电商的时候,传统的线下店铺就是采用热度排行的方式来增加销量的,因为能展示给客户的商品有限,所以只能选最热门的商品放在店铺里。

虽然这种做法可以避免新用户的冷启动窘境,因为我们不需要知道新用户是怎样的,只要知道大的趋势就可以了。但这样做对新的商品来说显然是致命的,因为热门的商品被展示得越多就越热门,长期占据热度榜,而新商品得不到被展示的机会,就只能烂在仓库里了。这个问题也被称为马太效应(The Matthew Effect)

比较有意思的是这里指出除了单纯地考虑热度,在基于热度排行时还可以综合考虑一些其它因素。事实上,即使是如此强调个性化的今天,热度依然是影响用户做出购买决定的一个很重要的因素,所以在构建推荐系统时也要充分考虑到这一点。

协同过滤(Collaborative Filtering)

Memory-based 方法

Memory-based 方法又可以称为 neighborhood-based方法。可以简单分为User-based CF和Item-based CF两种思路。

g11

g12

注意一下Step3过滤这个步骤,比方说用户已经买过某一本书,如果再推荐他重复购买是不合理的。但是,对于一些可能会周期性购买的物品(如抽纸、沐浴露etc),我们要怎么处理呢?

g13

g14

可以说各有各好处吧,Item-based更流行除了准确性好之外,物品的变动相对用户较少也是一个很大的原因,这能够减少很多计算花费。但是相对地,Item-based可能没有办法很好地承担开拓用户的眼界这个功能,是不是真的这样呢?值得思考。

g15

这里提到的缺点是需要注意的,但并不是说协同过滤就必定有这些缺点,我们可以针对这些缺点对协同过滤进行改良。这里记录一下一些简单的思路:

  • 冷启动问题怎么解决呢?是否可以引入一些领域知识?或者引入额外的数据来源(社交、地点、时间etc)呢?如果引入了,又该怎么使用呢?

  • 过去的行为真的决定现在吗?过去的行为有哪些特征是可以视为用户的特征的呢?有哪些特征可能只是干扰因素呢?

  • 怎么才能引入小众偏好,让推荐系统更强调个性化呢?

g16

LSH是一个相当有意思的减少计算量的方法。协同过滤的一个最基本步骤就是计算相似性,而无论从用户的角度还是从物品的角度来看,维度都相当高,计算花费很大。而使用LSH进行映射后,既能保持相似关系不会发生太大的变化,又能降低维度,确实是一种很好的解决方案。不过要特别注意哈希函数的选择

g17

g18

Model-based方法

基于模型的方法,用到的技术就比较多涉及到机器学习领域了。

g19

关联规则挖掘

g20

关联规则挖掘其实跟买东西的场景是非常搭的,有兴趣的朋友不妨查查 “啤酒与尿布” 这个经典案例。

值得注意的是:我们从结果反推出的 “现象” 并不一定是事实,这其中有可能存在巧合的因素,所以我们一定要慎重地对待。

g21

g22

Mark一下这里产生悖论的原因:数据的不同分组之间基数差异很大,导致合并时产生了偏差。用上面的例子来说就是对顾客分组是,在职人员的数量要远多于大学生的数量,在把这两个分组合并为顾客来考虑时就会产生偏差。

g23

聚类

g24

事实上,我们并不一定要在同一个簇里面找推荐物品的候选集,完全可以基于簇之间来使用KNN,把最近邻的簇对应的物品集作为候选,这样做就有一定概率引入一些额外的物品,给用户带来惊喜了。当然,如何平衡好这一点和推荐的准确性是需要研究的。

SVD

g25

比方说把推荐看作一个二分类问题,预测用户是否购买/点击;把推荐看作一个回归问题,预测用户对推荐物品的评分。这样来看的话,很多有监督学习的机器学习技术都能被用上了。但是,如何获得大量独立同分布的训练数据会是一个很大的问题。

g26

  • 如何应对评分矩阵的稀疏性? —— 现实问题,用户接触到的商品仅占非常小的一部分,会进行反馈的就更少了
  • 如何降低大规模矩阵计算的时间开销? —— 决定能否满足实时性的需求

图片中的两条式子可能有些模糊,它们分别是是:

式(1)是标准的SVD矩阵分解,式(2)则是利用SVD技术进行低阶近似,也称为截断SVD(Truncated SVD),它只取最大的k个奇异值,而k要远小于原矩阵的行数m和列数n,因此能够大大地降低计算开销。由于篇幅原因,这里就不科普SVD相关的知识了,详细内容可以check一下维基百科里对SVD的描述

g27

Funk提出的这种矩阵分解算法在很大程度上弥补了标准SVD的不足,它不需要关注缺失值,而且计算复杂度也降低了很多。这种矩阵分解方法后来被Netflix Prize的冠军Koren称为Latent Factor Model(简称LFM),也即后来大名鼎鼎的隐语义模型

g28

加入偏置项是一种很直觉的想法,举一个简单的例子,对商品要求较高的用户通常会给出较低的评分,所以在满意程度同等时,他给出的评分可能比其他用户都要低。如果我们不排除这个影响的话,他的评分就会错误地拉低了商品的评价。

g29

更进一步地,我们还可以考虑用户的历史行为对评分的影响。

g30

向量化可以理解为对原事物表现形式的改变,不仅仅用于推荐系统领域,也是很多其他研究领域的基础。比方说自然语言处理,要理解对话,就先就要把对话的句子进行向量化,将句子分解为不同的单词,每个单词对应一个维度(最近Google翻译已经改进为以句子为单元了,使得翻译更加准确,不过由于我没有进行过自然语言处理相关的研究,所以不太清楚具体的情况)。

RBM

g31

Boltzmann机是全连接的一个网络,参数相当多,即使去除同同一层内的连接,变为RBM,参数依然很多。参数越多,自然拟合的能力就越强,所以RBM可以说是浅层学习(相对于深度学习的一个概念,毕竟RBM就只有两层神经元)中非常强大的一个模型。

g32

g33

Mark一下,一个用户一个RBM,也即为每个用户都训练一个RBM模型,这样开销固然很大,但私以为这样做要比协同过滤更加符合个性化的需求。除了开销大之外,这种方法还需要海量的训练数据,否则无法得到可以接受的结果。

g34

自从深度学习火了之后,越来越多的研究者开始对其进行研究。在推荐系统领域也不例外,虽然RBM并不算“深”,但是可以帮助我们理解深度学习技术是如何应用到推荐系统领域的。我个人还不是太过了解深度学习,上面的PPT也不是讲得讲得很清楚(在推荐系统问题中应用的RBM是改良过的)。感兴趣的朋友不妨阅读一下腾讯数字音乐部智能推荐组编写的文章——解密深度学习在智能推荐系统的实践与应用

图模型

g35

g36

g37

Mark一下:图模型可以发现协同过滤发现不来的弱相似性,给推荐带来一定的惊喜。

基于内容/知识的推荐(Content-based/Knowledge-based)

g38

g39

混合方法(Hybird Approaches)

g40

所谓混合方法,指的是将多个算法集成在一起来完成任务,更详细的讲解可以查询集成学习相关的内容了解。

推荐算法的最新研究

学习排序(Learning to Rank)

g41

对NDCG和MRR这两种排序评价准则感兴趣的朋友可以浏览这篇文章

页面整体优化(Page Optimization)

g42

情景推荐:张量分解/分解机(Factoriztion Machine)

g43

g44

深度学习(Deep Learning)

g45

g46

Mark一下:仅仅利用行为数据的RNN可能效果有限,可以结合更多数据来源。

总结

g47

g48

g49

坚持技术分享,您的支持将鼓励我继续创作!