深度学习在美团点评推荐平台排序中的运用

美团点评作为国内最大的生活服务平台,业务种类涉及食、住、行、玩、乐等领域,致力于让大家吃得更好,活得更好,有数亿用户以及丰富的用户行为。随着业务的飞速发展,美团点评的用户和商户数在快速增长。在这样的背景下,通过对推荐算法的优化,可以更好的给用户提供感兴趣的内容,帮用户更快速方便的找到所求。我们目标是根据用户的兴趣及行为,向用户推荐感兴趣的内容,打造一个高精准性、高丰富度且让用户感到欣喜的推荐系统。为了达到这个目的,我们在不停的尝试将新的算法、新的技术进引入到现有的框架中。

1. 引言

自2012年ImageNet大赛技惊四座后,深度学习已经成为近年来机器学习和人工智能领域中关注度最高的技术。在深度学习出现之前,人们借助SIFT、HOG等算法提取具有良好区分性的特征,再结合SVM等机器学习算法进行图像识别。然而SIFT这类算法提取的特征是有局限性的,导致当时比赛的最好结果的错误率也在26%以上。卷积神经网络(CNN)的首次亮相就将错误率一下由26%降低到15%,同年微软团队发布的论文中显示,通过深度学习可以将ImageNet 2012资料集的错误率降到4.94%。

随后的几年,深度学习在多个应用领域都取得了令人瞩目的进展,如语音识别、图像识别、自然语言处理等。鉴于深度学习的潜力,各大互联网公司也纷纷投入资源开展科研与运用。因为人们意识到,在大数据时代,更加复杂且强大的深度模型,能深刻揭示海量数据里所承载的复杂而丰富的信息,并对未来或未知事件做更精准的预测。

美团点评作为一直致力于站在科技前沿的互联网公司,也在深度学习方面进行了一些探索,其中在自然语言处理领域,我们将深度学习技术应用于文本分析、语义匹配、搜索引擎的排序模型等;在计算机视觉领域,我们将其应用于文字识别、图像分类、图像质量排序等。本文就是笔者所在团队,在借鉴了Google在2016年提出的Wide & Deep Learning 的思想上,基于自身业务的一些特点,在大众点评推荐系统上做出的一些思考和取得的实践经验。

2. 点评推荐系统介绍

与大部分的推荐系统不同,美团点评的场景由于自身业务的多样性,使得我们很难准确捕获用户的兴趣点或用户的实时意图。而且我们推荐的场景也会随着用户兴趣、地点、环境、时间等变化而变化。点评推荐系统主要面临以下几点挑战:

  • 业务形态多样性:除了推荐商户外,我们还根据不同的场景,进行实时判断,从而推出不同形态的业务,如团单、酒店、景点、霸王餐等。

  • 用户消费场景多样性:用户可以选择在家消费:外卖,到店消费:团单、闪惠,或者差旅消费:预定酒店等。

针对上述问题,我们定制了一套完善的推荐系统框架,包括基于机器学习的多选品召回与排序策略,以及从海量大数据的离线计算到高并发在线服务的推荐引擎。推荐系统的策略主要分为召回和排序两个过程,召回主要负责生成推荐的候选集,排序负责将多个算法策略的结果进行个性化排序。

召回层:我们通过用户行为、场景等进行实时判断,通过多个召回策略召回不同候选集。再对召回的候选集进行融合。候选集融合和过滤层有两个功能,一是提高推荐策略的覆盖度和精度;另外还要承担一定的过滤职责,从产品、运营的角度制定一些人工规则,过滤掉不符合条件的Item。下面是一些我们常用到的召回策略:

  • User-Based 协同过滤:找出与当前User X最相似的N个User,并根据N个User对某Item的打分估计X对该Item的打分。在相似度算法方面,我们采用了Jaccard Similarity:1

  • Model-Based 协同过滤:用一组隐含因子来联系用户和商品。其中每个用户、每个商品都用一个向量来表示,用户u对商品i的评价通过计算这两个向量的内积得到。算法的关键在于根据已知的用户对商品的行为数据来估计用户和商品的隐因子向量。

  • Item-Based 协同过滤:我们先用word2vec对每个Item取其隐含空间的向量,然后用Cosine Similarity计算用户u用过的每一个Item与未用过Item i之间的相似性。最后对Top N的结果进行召回。
  • Query-Based:是根据Query中包含的实时信息(如地理位置信息、WiFi到店、关键词搜索、导航搜索等)对用户的意图进行抽象,从而触发的策略。

  • Location-Based:移动设备的位置是经常发生变化的,不同的地理位置反映了不同的用户场景,可以在具体的业务中充分利用。在推荐的候选集召回中,我们也会根据用户的实时地理位置、工作地、居住地等地理位置触发相应的策略。

排序层:每类召回策略都会召回一定的结果,这些结果去重后需要统一做排序。点评推荐排序的框架大致可以分为三块:

  • 离线计算层:离线计算层主要包含了算法集合、算法引擎,负责数据的整合、特征的提取、模型的训练、以及线下的评估。

  • 近线实时数据流:主要是对不同的用户流实施订阅、行为预测,并利用各种数据处理工具对原始日志进行清洗,处理成格式化的数据,落地到不同类型的存储系统中,供下游的算法和模型使用。

  • 在线实时打分:根据用户所处的场景,提取出相对应的特征,并利用多种机器学习算法,对多策略召回的结果进行融合和打分重排。

具体的推荐流程图如下:

dw topic

从整体框架的角度看,当用户每次请求时,系统就会将当前请求的数据写入到日志当中,利用各种数据处理工具对原始日志进行清洗,格式化,落地到不同类型的存储系统中。在训练时,我们利用特征工程,从处理过后的数据集中选出训练、测试样本集,并借此进行线下模型的训练和预估。我们采用多种机器学习算法,并通过线下AUC、NDCG、Precision等指标来评估他们的表现。线下模型经过训练和评估后,如果在测试集有比较明显的提高,会将其上线进行线上AB测试。同时,我们也有多种维度的报表对模型进行数据上的支持。

3. 深度学习在点评推荐排序系统中应用

对于不同召回策略所产生的候选集,如果只是根据算法的历史效果决定算法产生的Item的位置显得有些简单粗暴,同时,在每个算法的内部,不同Item的顺序也只是简单的由一个或者几个因素决定,这些排序的方法只能用于第一步的初选过程,最终的排序结果需要借助机器学习的方法,使用相关的排序模型,综合多方面的因素来确定。

3.1 现有排序框架介绍

dw topic

到目前为止,点评推荐排序系统尝试了多种线性、非线性、混合模型等机器学习方法,如逻辑回归、GBDT、GBDT+LR等。通过线上实验发现,相较于线性模型,传统的非线性模型如GBDT,并不一定能在线上AB测试环节对CTR预估有比较明显的提高。而线性模型如逻辑回归,因为自身非线性表现能力比较弱,无法对真实生活中的非线性场景进行区分,会经常对历史数据中出现过的数据过度记忆。下图就是线性模型根据记忆将一些历史点击过的单子排在前面:

dw topic

从图中我们可以看到,系统在非常靠前的位置推荐了一些远距离的商户,因为这些商户曾经被用户点过,其本身点击率较高,那么就很容易被系统再次推荐出来。但这种推荐并没有结合当前场景给用户推荐出一些有新颖性的Item。为了解决这个问题,就需要考虑更多、更复杂的特征,比如组合特征来替代简单的“距离”特征。怎么去定义、组合特征,这个过程成本很高,并且更多地依赖于人工经验。

而深度神经网络,可以通过低维密集的特征,学习到以前没出现过的一些Item和特征之间的关系,并且相比于线性模型大幅降低了对于特征工程的需求,从而吸引我们进行探索研究。

在实际的运用当中,我们根据Google在2016年提出的Wide & Deep Learning模型,并结合自身业务的需求与特点,将线性模型组件和深度神经网络进行融合,形成了在一个模型中实现记忆和泛化的宽深度学习框架。在接下来的章节中,将会讨论如何进行样本筛选、特征处理、深度学习算法实现等。

3.2 样本的筛选

数据及特征,是整个机器学习中最重要的两个环节,因为其本身就决定了整个模型的上限。点评推荐由于其自身多业务(包含外卖、商户、团购、酒旅等)、多场景(用户到店、用户在家、异地请求等)的特色,导致我们的样本集相比于其他产品更多元化。我们的目标是预测用户的点击行为。有点击的为正样本,无点击的为负样本,同时,在训练时对于购买过的样本进行一定程度的加权。而且,为了防止过拟合/欠拟合,我们将正负样本的比例控制在10%。最后,我们还要对训练样本进行清洗,去除掉Noise样本(特征值近似或相同的情况下,分别对应正负两种样本)。

同时,推荐业务作为整个App首页核心模块,对于新颖性以及多样性的需求是很高的。在点评推荐系统的实现中,首先要确定应用场景的数据,美团点评的数据可以分为以下几类:

  • 用户画像:性别、常驻地、价格偏好、Item偏好等。
  • Item画像:包含了商户、外卖、团单等多种Item。其中商户特征包括:商户价格、商户好评数、商户地理位置等。外卖特征包括:外卖平均价格、外卖配送时间、外卖销量等。团单特征包括:团单适用人数、团单访购率等。
  • 场景画像:用户当前所在地、时间、定位附近商圈、基于用户的上下文场景信息等。

3.3 深度学习中的特征处理

机器学习的另一个核心领域就是特征工程,包括数据预处理,特征提取,特征选择等。

  1. 特征提取:从原始数据出发构造新的特征的过程。方法包括计算各种简单统计量、主成分分析、无监督聚类,在构造方法确定后,可以将其变成一个自动化的数据处理流程,但是特征构造过程的核心还是手动的。

  2. 特征选择:从众多特征中挑选出少许有用特征。与学习目标不相关的特征和冗余特征需要被剔除,如果计算资源不足或者对模型的复杂性有限制的话,还需要选择丢弃一些不重要的特征。特征选择方法常用的有以下几种:

dw topic

特征选择开销大、特征构造成本高,在推荐业务开展的初期,我们对于这方面的感觉还不强烈。但是随着业务的发展,对点击率预估模型的要求越来越高,特征工程的巨大投入对于效果的提升已经不能满足我们需求,于是我们想寻求一种新的解决办法。

深度学习能自动对输入的低阶特征进行组合、变换,得到高阶特征的特性,也促使我们转向深度学习进行探索。深度学习“自动提取特征”的优点,在不同的领域有着不同的表现。例如对于图像处理,像素点可以作为低阶特征输入,通过卷积层自动得到的高阶特征有比较好的效果。在自然语言处理方面,有些语义并不来自数据,而是来自人们的先验知识,利用先验知识构造的特征是很有帮助的。

因此,我们希望借助于深度学习来节约特征工程中的巨大投入,更多地让点击率预估模型和各辅助模型自动完成特征构造和特征选择的工作,并始终和业务目标保持一致。下面是一些我们在深度学习中用到的特征处理方式:

3.3.1 组合特征

对于特征的处理,我们沿用了目前业内通用的办法,比如归一化、标准化、离散化等。但值得一提的是,我们将很多组合特征引入到模型训练中。因为不同特征之间的组合是非常有效的,并有很好的可解释性,比如我们将"商户是否在用户常驻地"、"用户是否在常驻地"以及"商户与用户当前距离"进行组合,再将数据进行离散化,通过组合特征,我们可以很好的抓住离散特征中的内在联系,为线性模型增加更多的非线性表述。组合特征的定义为:

1

3.3.2 归一化

归一化是依照特征矩阵的行处理数据,其目的在于样本向量在点乘运算或其他核函数计算相似性时,拥有统一的标准,也就是说都转化为“单位向量”。在实际工程中,我们运用了两种归一化方法:

Min-Max:1

Min是这个特征的最小值,Max是这个特征的最大值。

Cumulative Distribution Function(CDF):CDF也称为累积分布函数,数学意义是表示随机变量小于或等于其某一个取值x的概率。其公式为:1

在我们线下实验中,连续特征在经过CDF的处理后,相比于Min-Max,CDF的线下AUC提高不足0.1%。我们猜想是因为有些连续特征并不满足在(0,1)上均匀分布的随机函数,CDF在这种情况下,不如Min-Max来的直观有效,所以我们在线上采用了Min-Max方法。

3.3.3 快速聚合

为了让模型更快的聚合,并且赋予网络更好的表现形式,我们对原始的每一个连续特征设置了它的super-liner和sub-liner,即对于每个特征x,衍生出2个子特征:

1

实验结果表示,通过对每一个连续变量引入2个子特征,会提高线下AUC的表现,但考虑到线上计算量的问题,并没有在线上实验中添加这2个子特征。

3.4 优化器(Optimizer)的选择

在深度学习中,选择合适的优化器不仅会加速整个神经网络训练过程,并且会避免在训练的过程中困到鞍点。文中会结合自己的使用情况,对使用过的优化器提出一些自己的理解。

3.4.1 Stochastic Gradient Descent (SGD)

SGD 是一种常见的优化方法,即每次迭代计算Mini-Batch的梯度,然后对参数进行更新。其公式为:

1

缺点是对于损失方程有比较严重的振荡,并且容易收敛到局部最小值。

3.4.2 Momentum

为了克服SGD振荡比较严重的问题,Momentum将物理中的动量概念引入到SGD当中,通过积累之前的动量来替代梯度。即:

11

相较于SGD,Momentum就相当于在从山坡上不停的向下走,当没有阻力的话,它的动量会越来越大,但是如果遇到了阻力,速度就会变小。也就是说,在训练的时候,在梯度方向不变的维度上,训练速度变快,梯度方向有所改变的维度上,更新速度变慢,这样就可以加快收敛并减小振荡。

3.4.3 Adagrad

相较于SGD,Adagrad相当于对学习率多加了一个约束,即:

1

Adagrad的优点是,在训练初期,由于gt较小,所以约束项能够加速训练。而在后期,随着gt的变大,会导致分母不断变大,最终训练提前结束。

3.4.4 Adam

Adam是一个结合了Momentum与Adagrad的产物,它既考虑到了利用动量项来加速训练过程,又考虑到对于学习率的约束。利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后,每一次迭代学习率都有个确定范围,使得参数比较平稳。其公式为:

1

其中:

1

小结

通过实践证明,Adam结合了Adagrad善于处理稀疏梯度和Momentum善于处理非平稳目标的优点,相较于其他几种优化器效果更好。同时,我们也注意到很多论文中都会引用SGD,Adagrad作为优化函数。但相较于其他方法,在实践中,SGD需要更多的训练时间以及可能会被困到鞍点的缺点,都制约了它在很多真实数据上的表现。

3.5 损失函数的选择

深度学习同样有许多损失函数可供选择,如平方差函数(Mean Squared Error),绝对平方差函数(Mean Absolute Error),交叉熵函数(Cross Entropy)等。而在理论与实践中,我们发现Cross Entropy相比于在线性模型中表现比较好的平方差函数有着比较明显的优势。其主要原因是在深度学习通过反向传递更新Wb的同时,激活函数Sigmoid的导数在取大部分值时会落入左、右两个饱和区间,造成参数的更新非常缓慢。具体的推导公式如下:

一般的MSE被定义为:

1

其中y是我们期望的输出,a为神经元的实际输出a=σ(Wx+b)。由于深度学习反向传递的机制,权值W与偏移量b的修正公式被定义为:

1

因为Sigmoid函数的性质,导致σ′(z)z取大部分值时会造成饱和现象。

Cross Entropy的公式为:

1

如果有多个样本,则整个样本集的平均交叉熵为:

1

其中n表示样本编号,i表示类别编号。 如果用于Logistic分类,则上式可以简化成:

1

与平方损失函数相比,交叉熵函数有个非常好的特质:

1

可以看到,由于没有了σ′这一项,这样一来在更新wb就不会受到饱和性的影响。当误差大的时候,权重更新就快,当误差小的时候,权重的更新就慢。

3.6 宽深度模型框架

在实验初期,我们只将单独的5层DNN模型与线性模型进行了比对。通过线下/线上AUC对比,我们发现单纯的DNN模型对于CTR的提升并不明显。而且单独的DNN模型本身也有一些瓶颈,例如,当用户本身是非活跃用户时,由于其自身与Item之间的交互比较少,导致得到的特征向量会非常稀疏,而深度学习模型在处理这种情况时有可能会过度的泛化,导致推荐与该用户本身相关较少的Item。因此,我们将广泛线性模型与深度学习模型相结合,同时又包含了一些组合特征,以便更好的抓住Item-Feature-Label三者之间的共性关系。我们希望在宽深度模型中的宽线性部分可以利用交叉特征去有效地记忆稀疏特征之间的相互作用,而在深层神经网络部分通过挖掘特征之间的相互作用,提升模型之间的泛化能力。下图就是我们的宽深度学习模型框架:

dw topic

在离线阶段,我们采用基于Theano、Tensorflow的Keras作为模型引擎。在训练时,我们分别对样本数据进行清洗和提权。在特征方面,对于连续特征,我们用Min-Max方法做归一化。在交叉特征方面,我们结合业务需求,提炼出多个在业务场景意义比较重大的交叉特征。在模型方面我们用Adam做为优化器,用Cross Entropy做为损失函数。在训练期间,与Wide & Deep Learning论文中不同之处在于,我们将组合特征作为输入层分别输入到对应的Deep组件和Wide组件中。然后在Deep部分将全部输入数据送到3个ReLU层,在最后通过Sigmoid层进行打分。我们的Wide&Deep模型在超过7000万个训练数据中进行了训练,并用超过3000万的测试数据进行线下模型预估。我们的Batch-Size设为50000,Epoch设为20。

4. 深度学习线下/线上效果

在实验阶段,分别将深度学习、宽深度学习以及逻辑回归做了一系列的对比,将表现比较好的宽深度模型放在线上与原本的Base模型进行AB实验。从结果上来看,宽深度学习模型在线下/线上都有比较好的效果。具体结论如下:

dw topic

随着隐藏层宽度的增加,线下训练的效果也会随着逐步的提升。但考虑到线上实时预测的性能问题,我们目前采用256->128->64的框架结构。

dw topic

下图是包含了组合特征的宽深度模型与Base模型的线上实验效果对比图:

dw topic

从线上效果来看,宽深度学习模型一定程度上解决了历史点击过的团单在远距离会被召回的问题。同时,宽深度模型也会根据当前的场景推荐一些有新颖性的Item。

dw topic

5. 总结

排序是一个非常经典的机器学习问题,实现模型的记忆和泛化功能是推荐系统中的一个挑战。记忆可以被定义为在推荐中将历史数据重现,而泛化是基于数据相关性的传递性,探索过去从未或很少发生的Item。宽深度模型中的宽线性部分可以利用交叉特征去有效地记忆稀疏特征之间的相互作用,而深层神经网络可以通过挖掘特征之间的相互作用,提升模型之间的泛化能力。在线实验结果表明,宽深度模型对CTR有比较明显的提高。同时,我们也在尝试将模型进行一系列的演化:

  1. 将RNN融入到现有框架。现有的Deep & Wide模型只是将DNN与线性模型做融合,并没有对时间序列上的变化进行建模。样本出现的时间顺序对于推荐排序同样重要,比如当一个用户按照时间分别浏览了一些异地酒店、景点时,用户再次再请求该异地城市,就应该推出该景点周围的美食。

  2. 引入强化学习,让模型可以根据用户所处的场景,动态地推荐内容。

深度学习和逻辑回归的融合使得我们可以兼得二者的优点,也为进一步的点击率预估模型设计和优化打下了坚实的基础。

6. 参考文献

  1. H. Cheng, L. Koc, J. Harmsen et al, Wide & Deep Learning for Recommender Systems, DLRS 2016 Proceedings of the 1st Workshop on Deep Learning for Recommender Systems.
  2. P. Covington, J. Adams, E. Sargin, Deep Neural Networks for YouTube Recommendations, RecSys '16 Proceedings of the 10th ACM Conference on Recommender Systems.
  3. H. Wang, N. Wang, D. Yeung, Collaborative Deep Learning for Recommender Systems, KDD '15 Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.

7. 作者简介

潘晖,美团点评高级算法工程师。2015年博士毕业后加入微软,主要从事自然语言处理的研发。2016年12月加入美团点评,现在负责大众点评的排序业务,致力于用大数据和机器学习技术解决业务问题,提升用户体验。

搜索推荐技术中心:负责点评侧基础检索框架及通用搜索推荐平台的建设;通过大数据及人工智能技术,优化搜索列表的端到端用户体验,提升推荐展位的精准性及新颖性;构建智能技术平台,支持点评侧业务的智能化需求。我们的使命是用搜索推荐技术有效连接人,商家及服务,帮助用户精准高效地发现信息内容,优化用户体验,扩展用户需求,推动业务发展。

美团点评搜索推荐团队招聘各类机器学习、数据挖掘人才,base在上海。我们致力于通过机器学习、数据挖掘、实时数据流分析等前沿技术手段对大数据进行分析,挖掘各类用户特征,为用户提供最佳的个性化搜索/推荐体验,你将从多个角度对用户进行建模,并不断优化机器学习模型来优化点评搜索的用户体验。欢迎各位朋友推荐或自荐至wanxia.wang@dianping.com。

下一章:Android远程调试的探索与实现

作为移动开发者,最头疼的莫过于遇到产品上线以后出现了bug,但是本地开发环境又无法复现的情况。常见的调查线上棘手问题方式大概如下:方法优点缺点联系用户安装已添加测试日志的APK方便定位问题需要用户积极配合 ...