酷应用

重读经典 | 亚马逊“一键下单”的背后——个性化推荐系统的发展历程

百家作者：AI100 2017-06-30 10:46:37

一般都认为，亚马逊的成功要归功于它鼎鼎大名的“一键下单”功能，但“一键下单”的背后，还需要一个成单量极高的智能推荐系统，来驱动消费者不停地在亚马逊上“买!买!买!”。这就是用户点击分析、机器学习和个性化推荐的综合力量。本文的目的，正是回顾亚马逊这个以成单率著称的个性化推荐系统的发展历程。

本文作者是2003年那篇“久经考验”的亚马逊推荐系统论文的作者，他们在这里分享的是这篇经典论文发布后的新发现与新见解。如果你想阅读这篇经典论文，请在公众号会话回复“亚马逊”，即可获得完整论文。

作者 | Brent Smith，Greg Linden

编译 | AI100（rgznai100）

参与 | Reason_W，波波

二十年来，亚马逊已经为每位顾客建立了一个个性化的商城。每个来到亚马逊的人看到的都不一样，因为它会根据顾客的兴趣个性化生成。就好像你进了一家商店，货架会开始重新排列，把你可能想要的移动到前排，你不太可能感兴趣的排列到远处。

尽管其目录中有数百万种物品，亚马逊的推荐功能会根据您当前的资料和您以前的行为挑选您可能喜欢的一小部分产品进行推荐。算法不是魔术，它们只是与你分享其他人已经发现的东西。算法会完成所有的工作，当然也需要电脑来帮助那些设计算法的人一起实现这些事。

亚马逊在1998年推出了基于项目的协同过滤算法，使得推荐系统能够以一种前所未见的规模处理数百万商品并为数百万的顾客提供服务。

自从2003年我们在IEEE Internet Computing中公开了该算法后，它已经在网络上得到了广泛的使用，包括YouTube、Netflix等。该算法的成功来自于其简单性、可扩展性，经常令人惊讶但却十分有用的推荐结果，以及互联网计算所需要的属性，例如可以根据有关客户的新信息进行即时更新，并能够用一种容易理解的方式解释它为什么以某种方式推荐某些内容。

2003年IEEE Internet Computing发表的文章所描述的内容一直面临着很多挑战，这么多年过去也已经有了很多的发展。在这里，我们会介绍基于项目的协同过滤算法的一些更新，改进和改编，并提供了我们对于协同过滤，推荐系统和个性化的未来发展的看法。

算法

正如我们在2003年描述的那样，基于项目的协同过滤算法是直接的。在20世纪90年代中期，协同过滤通常是基于用户的，这意味着该算法的第一步是先搜索其他用户以找到具有类似兴趣的人（例如类似的购买模式），然后查看那些类似用户已经发现而你还没有发现的内容。不同的是，我们的算法从寻找目录中的每个商品的相关商品开始。 “相关”这个术语在这里可以有几个含义，但是在这里，我们将它简单地定义为“购买一件商品的人非常有可能购买另一件商品”。因此，对于每个商品i1，我们想要找到的商品i2应该是那些购买i1的人购买频率非常高的商品。

一旦构建了相关的商品列表，我们可以快速生成推荐的商品以备用户进一步查询。对于每件商品，它和该客户当前的资料和以前的兴趣点有关，我们都会查找和它相关的商品，将它们组合以产生最有可能的兴趣商品，过滤掉已经看到或购买的项目，然后将保留下来的商品推荐给用户。

该算法相对于旧的基于用户的协同过滤具有许多优点。最重要的一点是，大部分计算是离线完成的——包括相关商品的批量构建，推荐的计算步骤可以实时完成以进行一系列查找。这些推荐不仅高质量而且有用，特别是在给定足够的数据时。即使是和过去二十年中新提出的算法进行比较，在明显可以感觉出来的推荐质量方面仍然保持着足够的竞争。该算法可扩展到数千万商品和数亿用户，而无需借助采样或其他会降低推荐质量的技术。它可以即时更新有关个人兴趣的新信息。最后，直观的说，推荐系统可以解释成根据客户放到购物车里的商品列表进行推荐。

经受时间的考验

作为IEEE Internet Computing 20年出版物的一部分，我向编辑委员会推荐了我们从我们的杂志中挑选的一篇文章，在过去20年中，它经受住了“时间的考验”。在选择文章时，我们对二十年来被称为“常青”研究领域的20多篇候选文章的观点进行了评价，然后根据IEEE Xplore的下载，引用和流行媒体中提及的工作，对这些文章进行了评定。该信息被提交到了由以前的杂志编辑组成的委员会。感谢由Arun Iyengar领导的编委会选拔委员会，包括Fred Douglis，Robert Filman，Michael Huhns，Charles Petrie，Michael Rabinovich和Munindar Singh。本委员会通过对每项工作内容以前和未来的重要性进行评估，评选出了排名前三的文章。

我很高兴能够认识委员会的官方“时间考验”获奖者：2003年1月/ 2月，由Greg Linden，Brent Smith和Jeremy York发表的一篇名为“亚马逊推荐系统：商品到商品的协作过滤”的工业界的文章，（发行IC（见doi：10.1109 / MIC.2003.1167344））。现在距这篇文章发表已经过去十四年了，它在IEEE Xplore的月下载量达到125次，2011年1月以来的下载量超过12,754次。文章目前在Google学术报告中引用达4,258次。我很高兴选拔委员会推荐了一篇工业界的文章，因为它符合杂志在学术，研究和工业人群中的无障碍的宗旨。

除了对这篇文章表示肯定之外，我们还要求作者写下这篇回顾性的论文，讨论一下他们从发表这篇获奖的“时间考验”文章之后发现的研究和见解，同时展望未来。

展望未来，这本杂志希望每2-3年评选一次“历经时间考验”的文章。我希望你喜欢这篇回顾性文章，请花点时间祝贺格雷格·林登，布伦特·史密斯和杰里米·约克。

- 布莱恩·布莱克

IEEE Internet Computing总编辑

德累斯顿大学教授和杰出教授

2003年：Amazon.com、Netflix、YouTube等

当我们在2003年把文章发布到IEEE的时候，基于项目的协同过滤已经被广泛地应用到亚马逊官网上。主页会根据您的购买记录和在商店浏览过的商品，突出地显示推荐商品。搜索结果页面会推荐与您的搜索相关的商品。购物车会推荐您可能已经在考虑要补充到购物车里的商品，或者某些您可能在下单前最后一分钟才突然想到要购买的商品。在完成订单时，会出现更多推荐，提示一些您以后可能会订购的商品。亚马逊网站上的许多页面，包括使用电子邮件，浏览页面，产品详细信息页面等，都会有一些推荐的内容，来尝试建立每个客户的个性化商店。

其他不少网站也使用了该算法。 2010年，YouTube被报道使用它来进行视频推荐。许多开源代码和第三方供应商也都包含了该算法，并在网络零售，旅游，新闻，广告等领域进行了广泛应用。在以后的几年中，推荐系统被亚马逊广泛使用，一份微软的研究报告估计亚马逊30％的网页浏览量都来自于推荐系统。同样，Netflix也在非常广泛地使用推荐系统，其首席产品官Neil Hunt表示，Netflix上用户80％以上的电影都是通过推荐系统看到的，其推荐系统每年产生的价值超过10亿美元。

当我们一开始开发基于项目的协同过滤算法时，亚马逊官网主要是一个书店。此后，亚马逊的销售额已经增长了百倍以上，销售范围已经不限于书籍，扩大到了非媒体类的商品，笔记本电脑、女装等。这种扩张对我们原始算法中的许多假设都造成了挑战，需要算法适应新的和不断变化的环境。通过经验，我们找到了改进算法的方法来为许多新的应用程序提供更相关的建议。

关于推荐系统和协同过滤的一些观点

作为一名博士生,我的工作使用定制推荐技术和协同过滤来选择把工作分配给互联网上的哪些外包人员。这期文章对我来说特别有意义。协同过滤是一种通过利用其他类似用户的体验，针对用户兴趣定制生成推荐来个性化用户体验的技术。传统上，该技术用于电子商务平台，通过将有针对性的推荐转换为购买来提升销售量. 这项技术比全面投放广告获得了更好的结果，能够更有针对性地定制个人用户的购买体验。尽管算法取得了这么大的成功，但是仍存在两个主要挑战：实时可扩展性和推荐质量。这些问题直接影响用户的个人体验，或者说，使用该技术的平台的成功。

作为首先要考虑的问题，可扩展性受到当今廉价和不断发展的存储和计算能力的影响。这些都导致了压倒性数量的数据的生成和收集。不幸的是，算法（包括传统的协同过滤）在实时或在线模式下处理这一新数据量的能力还没有得到发展。为了解决可扩展性的问题，研究人员采用了各种技术来以结构化的方式减少数据集。这些方法包括用户抽样，由物品分类驱动的数据分区，以及过滤高频或低频项目以将其他项目放到推荐列表的顶部。这些办法在寻求可扩展性问题的同时，也会影响到推荐的质量；这直接影响我们关心的第二个问题。

鉴于这些问题，研究界和从业者有义务制定一种可以在不牺牲推荐质量的情况下获得可扩展性的优势的方法。基于项目的协同过滤是目前最成功的方法。在主要的如亚马逊等大型电子商务平台中，其算法的持续性成功也显而易见。它通过用户的购买历史或商品评价进行推荐，将它们与已建立的指标进行类似的项目配对，最后组成类似商品的列表作为推荐。与以用户为中心的手段采用的减少数据集的技术相反，这种方法是以项目为中心，大大减少了评估的数据空间。正如IEEE Internet Computing的“历经时间考验的文章”和其他相关的工作所说，这种数据空间缩减可以达到其原始大小的三个数量级。以项目为中心，它克服了传统方法中用户数据稀疏的问题（这种方法在很大程度上有助于克服不必要的评估）。它也克服了与其个人资料相关联的重度用户大量数据的的密度问题。

基于项目的协同过滤仍然需要离线处理来配对相似的项目。通过离线预处理信息，基于项目的协同过滤可以在在线模式中实时生成推荐列表。这样可以为用户提供简单，快速，更个性化的推荐。与整个数据集中的其他项目相反，类似的项目列表是针对用户的购买或评级历史的一组光滑子集。它也克服了具有稀疏历史的新用户和轻度用户的挑战，因为类似的项目列表侧重于用户的历史，而不是其他用户的历史。这种技术更有效率，但对推荐质量没有任何不利影响；因此，它仍然是实时，在线协同过滤和推荐算法的首选技术。

— Julian Jarrett

PhD Student, Computer Science, Drexel University

定义“相关”商品

推荐的质量在很大程度上取决于我们所谓的“相关”。例如，假设您购买了X，我们所谓的“非常可能”购买物品Y是什么意思？当我们观察到用户购买了X和Y时，我们可能会想知道如果这两个商品是无关的，有多少X买家会随机购买Y。推荐系统最终是统计性质的应用。人们的行为信息充满了噪声，我们的挑战就是要在随机事件中发现有用的模式。

估计购买X和Y的用户数量的一种方式是假设普通X的买家有相同的概率购买Y，，同时将作为对购买X和Y的客户期望数量的估计。我们2003年发表的论文以及2003年以前的大部分工作都使用了类似的计算。

然而，有一个有趣的事实是，对于几乎任何两个X和Y商品，算法结果是购买X的客户都比一般人更有可能购买Y。怎么会这样呢？想象有一个重度买家，购买了目录中的所有商品。当我们寻找所有购买X的客户时，该客户肯定会被选中。同样， 1,000次购买记录的客户被选中的概率将比只有20次购买记录的人高约50倍；随机抽样购买记录并不能让所选的客户保持均匀的分布。所以我们有一个有偏样本。对于任何项目X，购买X的客户都将比一般顾客更有可能购买其他商品。

这种客户购买记录的不均匀分布意味着我们在试图估计预期随机购买Y商品的X买家数量时，不能忽视X买家。我们认为对有很多机会购买Y商品的客户进行建模是有用的。例如，对于有20次购买操作的客户，我们将这20次操作中的每一次都作为一个独立购买Y的记录。

更正式地，对于购买X的指定客户c（由c∈X表示），我们可以估计c购买Y的概率为1-(1-PY)|C|，其中| c |是根据c和或任意随机选择的购买商品为Y的概率得出的不购买X的顾客。然后，我们可以通过对所有X买家进行求和并使用扩展二项式来计算X买方中预期购买Y商品的买方的数量（见下图）。

根据X买家购买Y的多个可能推导预期购买X和Y项目的用户数量。

我们可以将EXY作为PY中的多项式写入，其系数完全依赖于X。实际计算的时候，PY很小，因此可以用有界k进行近似逼近。此外，可以预先计算所有商品的PY和αk（X），然后可以通过预先计算的值的简单组合对EXY进行近似。

通过这种鲁棒的方法计算EXY的值，我们可以用它来评估观察到的买入X和Y的客户数量NXY是高于还是低于随机预期。例如，NXY-EXY给出了非随机同现数量的估计值，给出了与预期随机同现的差的百分比。这些是创建相似性评分函数S（X，Y）以观察和预计购买X和Y的用户数量的两个示例。第一个，NXY-EXY将偏向流行的Y，比如《哈利波特》这本书，所以推荐结果可能被认为是太明显或无关紧要。第二个，[NXY-EXY] / EXY，这让低销量商品很容易得到高的分数，所以推荐结果可能被认为是模糊的和随机的，特别是大量不受欢迎的商品。相关性评分需要在人气这方面和不受欢迎的商品的分配规则这方面之间取得平衡。卡方积分是一个保持这种平衡的例子。

相关性评分函数还有其他一些选择和参数可以考虑，并从相关商品中得到建议。我们的经验是，没有一个得分可以在所有设置中都能奏效。最终，明显可以感觉到的质量才是对推荐结果的判断；当人们发现推荐有用时它才有用。

机器学习和可控的在线实验可以了解用户实际喜欢的内容，挑选最佳参数以便提供具体的使用建议。我们不仅可以衡量哪些推荐是有效的，而且还可以提供关于人们喜欢、点击的推荐商品的反馈信息，整合进我们的算法中，了解到底是什么帮助客户最多。

例如，兼容性是一个重要的因素。我们可能会观察到，购买特定数码相机的客户非常喜欢购买某种存储卡，但这并不能保证该存储卡适用于该相机。客户购买存储卡有很多原因，我们观察到的相关性可能是随机的。事实上，亚马逊的商品目录中有成千上万的存储卡，其中许多都是与相机随机相关的。许多电子商务网站使用一个手工制作的兼容性知识库，这维护起来不仅昂贵而且容易出错，特别是对亚马逊这样的数据规模来说。我们发现，给定足够的数据和关于商品相关性的鲁棒指标，兼容性可能在人们的行为中体现出来，结果是虚假信号失效，真正适合的商品显现出来。

奇怪的是，我们发现由数据引起并由客户自己发现的相关商品也可以很特殊。考虑一下人们浏览的物品与他们购买的物品，对于书籍来说，音乐和其他低成本商品，人们倾向于浏览和购买相同的东西。对于许多价格较高的物品，特别是对于非媒体类的商品，人们浏览的和他们购买的商品可能截然不同。例如，人们倾向于浏览许多电视机，但只能购买一台电视机。他们在浏览电视机的时候看的东西往往是其他电视机。但他们购买的东西往往会成为购买特定电视机（如蓝光播放器和壁挂式显示器）后为了增强使用体验的补充。

时间的重要性

了解时间的作用对于提高推荐的质量很重要。例如，当计算相关商品表时，一次购买与另一次购买的相关性在很大程度上取决于它们在时间上的接近程度。如果客户在购买一本书后五个月购买了另一本书，与客户在同一天购买了这本书的相关性相比，相关性就更弱。时间的方向性也是有帮助的。例如，客户倾向于在购买相机之后购买存储卡，而不是相反，这可能是一个很好的提示，当有人购买存储卡后，我们不应该再推荐相机。有时，物品是按顺序购买的，如书籍，电影或系列电视剧，推荐应该是下一步要做的事情。

亚马逊的商品目录在不断变化。每天都会有成千上万的新物品到达，有很多其他的商品过时。这个周期在某些类别中尤其明显。例如，服装有季节性潮流，消费电子技术创新迅速。新商品可能处于不利地位，因为他们没有足够的数据与其他商品产生很强的相关性。这被称为冷启动问题，通常需要一个探索/开发的过程来给尚未有机会的商品提供一个被展示的机会。诸如新闻或社交媒体帖子之类的时效性项目是一种特别具有挑战性的冷启动形式，通常需要使用基于内容的算法（学科，话题和文字）与基于行为的算法（使用购买，观看或评级）混合数据。

用户也有一个生命周期，并且会经历他们自己的冷启动问题。当我们对新用户的兴趣信息非常有限时，想要知道为他们推荐什么商品一直是个问题。什么时候利用有限的信息，什么时候使用普遍受欢迎的商品来确保推荐结果的稳定是一个很容易出错的微妙转换。

即使对于老客户，正确地对时间建模也对推荐的质量有很大的影响。随着年龄的增长，以前的购买行为与客户当前兴趣的相关性会逐渐变弱。这种情况很复杂，因为这种相关性针对不同类型的商品会以不同的速率衰减。例如，一些购买 - 例如在大海上航行的手册 - 可能表明持久的长期兴趣。其他如洗碗机修理工具，在用户过完周末的活动之后，可能变的并不相关。甚至有一些购买，如婴儿摇铃，推荐结果必须改变很长一段时间；四年后，我们应该推荐平衡自行车和书籍，而不是婴儿奶瓶和牙胶。一些商品，如书籍，通常只买一次；其他商品，如牙膏，两次购买的时间间隔具有相当的可预测性。

我们可以做出的推荐的质量不仅取决于过去购买的时间，而且取决于购买的商品。我们发现买一本书可以反映出客户的很多兴趣，让我们推荐几十个高度相关的商品。但是，非媒体类商品中的许多购买行为都只反映一点点客户的兴趣。从购买订书机的行为中可以得到什么信息？买一双袜子可以做出什么令人惊奇和有见地的推荐？推荐给用户胶带分配器或更多的内衣在现在可能有帮助，但长期来看却是很乏味的推荐。因此，我们必须开发算法来学习哪些购买行为会导致有用的推荐，那些时候应该忽略某些那些购买行为。

最后，各种推荐的重要性是众所周知的；有时最好给出各种相关的商品，而不是一个有限的目标清单。亚马逊有许多类型的产品，会产生大量的目录，这种广泛性也产生了一个独特的挑战，在单一产品类别的商店（如书店）中未见到。例如，向重度读者推荐更多书籍可能会导致把书卖出去，但是通过发现他们在另一个产品系列中从未考虑过的商品，人们的长期受益反而会增加。即时意图也是多样性的一个因素。当顾客明确寻求具体的内容时，推荐应该精准化，以帮助他们快速找到所需要的内容。但是，当意图不明确或不确定时，推荐的目标应该变成探索性的和意外的发现。在建议的多样性中找到适当的平衡，需要大量的实验和长期进行优化。

未来：无处不在的“推荐”

推荐系统的未来是什么？我们相信在我们面前有大量的机会都将超越我们。想象一下未来的智能互动服务，在里面购物会像谈话一样容易。

这超出了现在我们还要在搜索框中键入关键字再跳转到目标网页的框架。使用推荐系统应该像与一个了解你的朋友聊天一样，他知道你喜欢什么，会和你一起工作，并预计你的需要。

这是一个智慧无处不在的愿景。你的每一次和推荐系统的互动都应该反映出你是谁，喜欢什么，帮助你找到和你类似的人已经发现的东西。当你看到一些显然不是你的东西时，它应该感到空虚和悲哀；你现在不认识我吗？

要实现这一点，需要一种全新的方法来设计推荐系统，不应该再有推荐特征和推荐引擎。相反，理解你，其他人和可用的信息应该是每次互动的一部分。

推荐系统和个性化就生活在我们在世界各地创造的数据之海中，包括我们寻找的，我们发现的，以及我们所爱的东西。我们相信未来的推荐系统将进一步建立在利用集体人力智能的智能计算机算法上。未来将继续属于帮助研究人员实现算法造福别人的电脑。

二十年来，亚马逊向数以百万计的客户推出了数百万商品的建议，帮助人们发现自己可能找不到的内容。从那时起，原始的算法已经扩散到大部分的网页上，被改编为帮助人们观看视频或者阅读新闻的算法，受到其他算法和其他技术的挑战，并被修改以改善其多样性和发现，近因，敏感性或商品顺序，以及许多其他问题。由于其简单性，可扩展性，可解释性，适应性和相对高质量的推荐结果，基于项目的协同过滤仍然是当今最流行的推荐算法之一。

然而，该领域仍然是非常开放的。为每位用户的构建个性化的体验仍是一个没有完全实现的愿景。大量的改变需要被智慧地和个性化地添加到每个系统的每一部分中，创造出一种看起来像一个知道你，你喜欢什么，以及其他人喜欢什么的朋友的体验，并了解你们有什么选择。推荐的本质是发现，用他们帮助你发现的东西为你提供惊喜和喜悦。每次互动都应该是一次推荐。

作者
Brent Smith已经为亚马逊的个性化推荐系统工作了17年，一直在领导这场面向消费者的快速创新革命。他是加州大学圣地亚哥分校的数学学士、华盛顿大学的数学硕士。他的邮箱是smithbr@amazon.com。

Greg Linden如今是微软的数据科学家了。发表那篇经典论文的时候，他是在亚马逊，随后又去过Google和其他几家创业公司。他此前的工作多集中在推荐系统、个性化、人工智能、搜索和广告方面。Linden是华盛顿大学的计算机硕士、斯坦福大学MBA。他的邮箱是glinden@gmail.com。