KDD Cup 2020 Debiasing比赛冠军技术方案及在美团广告的实践
ACM SIGKDD （国际数据挖掘与知识发现大会，简称 KDD）是数据挖掘领域的国际顶级会议。
美团到店广告平台搜索广告算法团队基于自身的业务场景，一直在不断进行前沿技术的深入优化与算法创新。团队的坚强、胡可、漆毅、曲檀、明健、博航、雷军与中科院大学唐兴元共同组建参赛队伍Aister，参加了Debiasing、AutoGraph、Multimodalities Recall三道赛题，最终在Debiasing赛道中获得冠军（1/1895），在AutoGraph赛道中也获得了冠军（1/149），并在Multimodalities Recall赛道中获得了季军（3/1433）。
本文将介绍Debiasing赛题的技术方案，以及团队在广告业务中偏差消除的应用与研究。
背景
KDD Cup比赛是由SIGKDD主办的数据挖掘研究领域的国际顶级赛事，从1997年开始，每年举办一次，是目前数据挖掘领域最具影响力的赛事。该比赛同时面向企业界和学术界，云集了世界数据挖掘界的顶尖专家、学者、工程师、学生等参加，为数据挖掘从业者们提供了一个学术交流和研究成果展示的平台。KDD Cup 2020共设置五道赛题（四个赛道），分别涉及数据偏差问题（Debiasing）、多模态召回问题（Multimodalities Recall）、自动化图学习（AutoGraph）、对抗学习问题和强化学习问题。
在广告系统中，如何对数据偏差进行消除是最具挑战性的问题之一，也是近年来学术界的研究热点。随着产品形态与算法技术的持续演进，系统会不断积累偏差。搜索广告算法团队在数据偏差问题取得了突破，带来了较显著的业务效果提升。特别是在Debiasing赛题中，团队基于偏差消除问题的技术积累，从全球1895支队伍的激烈角逐中取得第1名，并在最终评测指标（ndcg_half）领先第2名6.0%。下面我们将介绍Debiasing赛题的技术方案，以及团队在广告业务中偏差消除的应用与研究，希望对从事相关研究的同学能够有所帮助或者启发。
附：技术方案开源代码
赛题介绍与问题分析
偏差消除问题概述
大多数电子商务和零售公司利用海量数据在其网站上实现搜索和推荐系统，从而来促进销售，随着这样的趋势发展以及流量的大量增加，对推荐系统产生了各式各样的挑战。其中一个值得探索的挑战是推荐系统的人工智能公平性（Fairness）问题[1,2]，即如果机器学习系统配备了短期目标（例如短期的点击、交易），单纯朝短期目标进行优化将会导致严重的“马太效应”，即热门的商品受到更多的关注，冷门商品则愈发的会被遗忘，产生了系统中的流行度偏差[3]，并且大多数模型和系统的迭代依赖于页面浏览（Pageview）数据，而曝光数据是实际候选中经过模型选择的一个子集，不断地依赖模型选择的数据与反馈再进行训练，将形成选择性偏差[3]。
上述流行度偏差与选择性偏差不断积累，就会导致系统中的“马太效应”越来越严重。因此，人工智能公平性问题对于推荐系统的不断优化至关重要，并且这将对推荐系统的发展以及生态环境产生深远的影响。
由于不是一个定义充分的优化问题，偏差消除是当前推荐系统非常具有挑战性的问题，也是当前学术界的一个研究热点。本次KDD的赛题也是围绕偏差问题展开，基于电子商务中用户下一次点击商品预测（Next-Item Prediction）的问题，进行无偏估计。
赛题官方提供了用户点击数据、商品多模态数据、用户特征数据。其中用户点击数据提供了用户历史点击的商品以及点击的时间戳，商品多模态数据主要为商品的文本向量以及图片向量，用户特征数据有用户的年龄、性别、城市等等。数据涉及超过100万次点击，10万商品和3万用户。并根据时间窗口划分数据阶段，一共分为十个阶段，最终评分以最后3个阶段为准。
为了关注于消除偏差问题，本次赛题提供的评测指标包括NDCG@50_full，NDCG@50_half，hitrate@50_full，hitrate@50_half。采用NDCG@50_full，NDCG@50_half两项指标进行评估。
- NDCG@50_full：与常规推荐系统评价指标NDCG一致，在整个评测数据集上评估了每次用户请求所推荐的前50个商品列表的平均排序效果，该评测集我们称之为full评测集。
- NDCG@50_half：关注于偏差问题，从整个full评测数据集中取出一半历史曝光少的点击商品，对这些商品的推荐列表进行NDCG指标评估，该评测集我们称之为half评测集。
评分首先通过NDCG@50_full筛选出前10%的队伍，然后在这些队伍中使用NDCG@50_half来进行最终排名。在最终的评估中NDCG@50_half将对Top名次的差异，在长尾数据预测更重要的评测方式能够更好地评估选手们对于数据偏差的优化。不同于传统的封闭数据集点击率预估问题（CTR预估），上述数据特点与评测方式侧重于偏差的优化。
数据分析与问题理解
数据分析与问题：用户特征数据中一共有35444个用户，但只有6789个用户有特征，故而特征覆盖率只有19.15%，由于覆盖率较低且只有年龄、性别、城市等三个特征，我们发现这些特征对我们的整个任务而言是无用的。商品特征数据中一共有117720个商品，有108916个商品拥有文本向量及图片向量，覆盖率高达92.52%，可以根据向量去计算商品间的文本相似度及图片相似度，由于用户信息及商品信息的缺少，如何利用好这些商品多模态向量对于整个任务而言是极其重要的。
选择性偏差分析：如表1所示，我们对基于i2i（item2item）点击共现以及基于i2i向量相似度两种Item-Based协同过滤的方法所召回的商品候选集做对比，由于系统的性能限制，我们将候选集长度最大值限制到1000，我们发现两种召回方法在评测集上都有一个较低的hitrate，则不管使用哪种方法系统都存在着一个较大的选择性偏差，即推荐给用户的样本是根据系统来选择的，而不是所有候选集合，真实的候选集合大大超过了推荐给用户的样本，导致训练数据带有选择性偏差。
进一步的，我们发现基于i2i点击共现在full评测集上相对于half评测集有更高的hitrate，说明其更偏好于流行商品，而基于i2i向量相似度在full和half的评测集上hitrate相差不大，说明其对于流行度无偏好，同时两种方式召回的候选集只有4%的重复率，故而我们需要去结合点击共现和向量相似度两种商品关系来生成更大的训练集，从而缓解选择性偏差。
如图3所示，我们对商品的流行度进行了分析，其中横坐标商品点击频数，即商品流行度，纵坐标为商品个数。图中我们对流行度做了截断，横坐标最大值本应为228。可以看出，大部分商品的流行度较低，符合长尾分布。图中的两个箱型图分别是full评测数据集商品流行度的分布，以及half评测数据集商品流行度的分布。从这两个箱型图可以看出，流行度偏差存在于数据集中，整个full评测集中有一半评测数据是基于流行度较低的商品，而另一半评测数据商品的流行度较高，直接通过点击商品去构建样本，会导致数据中拥有较多流行度高的正例商品，从而形成流行度偏差。
问题挑战
该竞赛的主要挑战是消除推荐系统中的偏差，从上述数据分析中可以看出，主要存在两种偏差，选择性偏差（Selection Bias）和流行度偏差（Popularity Bias）。
- 选择性偏差：曝光数据是由模型和系统选择的，与系统中的全部候选集不一致[4,5]。
- 流行度偏差：商品历史点击次数呈现一个长尾分布，故而流行度偏差存在于头部商品和尾部商品之间，如何解决流行度偏差也是赛题的核心挑战之一[6,7]。
基于上述偏差，传统的利用Pageview（曝光）->Click（点击）的点击预估建模思路并不能合理地建模用户的真实兴趣，我们在初步尝试中也发现采用传统建模思路效果较差。不同于传统的用户兴趣建模思路，首先，我们通过u2i2i（user2item2item）建模转换，采用侧重于i2i的建模代替传统CTR预估方式中的u2i（user2item）的兴趣建模。并且，我们采用基于i2i图的多跳游走进行候选样本生成，代替基于Pageview样本生成思路。同时，在构图过程、i2i建模过程我们引入了流行度惩罚。最终有效地解决了上面的偏差挑战。
竞赛技术方案
针对选择性偏差和流行度偏差两方面挑战，我们进行了建模设计，有效地优化了上述偏差。已有的CTR建模方法可以理解为u2i的建模，通常刻画了用户在特定请求上下文中对候选商品的偏好，而我们的建模方式是去学习用户的每个历史点击商品和候选商品的关系，可以理解为u2i2i的建模。这种建模方法更有助于学习多种i2i关系，并且可以容易地将i2i图中的一跳关系拓展到多跳关系，多种i2i关系可以探索更多无偏数据来增大商品候选集和训练集，达到了缓解选择性偏差的目的。
同时，考虑到流行商品引起的流行度偏差，我们在构图过程中对边权引入流行度惩罚，使得多跳游走时更有机会探索到低流行度的商品，同时在建模过程以及后处理过程中我们也引入了流行度惩罚，缓解了流行度偏差。
最终，我们形成了一个基于i2i建模的排序框架，框架图如图4所示。在我们的框架中商品推荐过程被分为三个阶段，第一个阶段是基于用户行为数据和商品多模态数据构建i2i图，并基于i2i图进行多跳游走生成i2i候选样本；第二个阶段是拆分用户点击序列，并根据i2i候选样本构建i2i关系样本集，基于i2i样本集进行自动化特征工程，以及使用流行度加权的损失函数进行消除流行度偏差的建模；第三个阶段根据用户点击序列将i2i模型生成的i2i打分进行聚合，对打分的商品列表进行消除流行度偏差的后处理，从而对商品列表进行排序推荐。我们将详细介绍这三个阶段的方案。
基于多跳游走的i2i候选样本生成
为了探索更多的i2i无偏候选样本来进行i2i建模，从而缓解选择性偏差，我们构建了一个具有多种边关系的i2i图，并在构边过程中引入了流行度惩罚来消除流行度偏差。如下图5所示，i2i图的构建与多跳游走i2i候选样本的生成过程被分为三个步骤：i2i图的构建、i2i多跳游走以及i2i候选样本的生成。
第一个步骤为i2i图的构建，图中存在一种结点即商品结点，两种边关系即点击共现边和多模态向量边。点击共现边通过用户的历史商品点击序列所构建，边的权重通过以下的公式得到，其在两个商品间的用户历史点击共现频数的基础上，考虑了每次点击共现的时间间隔因子，并加入了用户活跃度惩罚以及商品流行度惩罚。时间间隔因子考虑到了两个商品间的共现时间越短则这两个商品有更大的相似度；用户活跃度惩罚考虑了活跃用户与不活跃用户的公平性，通过用户历史商品点击次数来惩罚活跃用户；商品流行度惩罚考虑了商品的历史点击频数，对流行商品进行惩罚，缓解了流行度偏差[8]。
多模态向量边则通过两个商品间文本向量及图片向量的余弦相似度进行构建，对一个商品的向量利用K最近邻的方法去寻找最邻近的K个商品，对这个商品与其最近邻的K个商品分别构建K条边，向量间的相似度即为边权，多模态向量边与流行度无关，可以缓解流行度偏差。
第二个步骤是通过多跳游走探索多种i2i关系，我们通过枚举不同的一跳i2i关系组合构成不同类型的二跳i2i关系，并且在构建好二跳i2i关系之后删除原本的一跳i2i关系以避免冗余。i2i关系包括基于点击一跳邻居构建i2i，基于向量一跳邻居构建i2i，基于点击-点击二跳游走构建i2i，基于点击-向量二跳游走构建i2i，基于向量-点击二跳游走构建i2i，一跳i2i关系得分由一跳边权得来，多跳i2i关系得分则由以下公式得来，即对每条路径的边权相乘得到路径分，并对所有路径分求平均。通过不同边类型多跳游走的方式，更多的商品有更多的机会和其他商品构建多跳关系，从而扩大了商品候选集，缓解了选择性偏差。
第三个步骤则基于每种i2i关系根据i2i得分对所有商品的候选商品集合分别进行排序和截断，每个i2i关系间的相似度热图如下图6所示，相似度是通过两种i2i关系构造的候选集重复度所计算，我们可以根据不同i2i关系之间的相似度来确定候选商品集合的数量截断，以得到每种i2i关系中每个商品的i2i候选集，供后续i2i建模使用。
基于流行度偏差优化的i2i建模
我们通过u2i2i建模转换，将传统的基于u2i的CTR预估建模方式转换为i2i建模方式，它可以容易地使用多跳i2i关系，同时我们引入带流行度惩罚的损失函数，使得i2i模型朝着缓解流行度偏差的方向学习。
如下图7所示，我们拆分用户前置点击行为序列，将每一个点击的商品作为source item，从i2i graph中的多跳游走候选集中抽取target item，形成i2i样本集。对于target item集合，我们将用户下一次点击的商品与target item是否一致来引入该样本的标签。这样，我们将基于用户选择的序列建模[9]转变为基于i2i的建模，通过两个商品点击的时间差以及点击次数间隔来从侧面引入用户的序列信息，强调了i2i的学习，从而达到消除选择性偏差的目的。最终用户的推荐商品排序列表可以基于用户下的i2i打分进行target item的排序。
如图8所示，我们利用自动化特征工程的思想去探索高阶特征组合，缓解了偏差问题业务含义抽象的问题。我们通过人工构造一些基础特征例如频数特征、图特征、行为特征和时间相关特征等特征后，将这些基本的特征类型划分为3种，类别特征、数值特征以及时间特征，基于这些特征做高阶特征组合，每一次组合形成的特征都会加入下一次组合的迭代之中，来降低高阶组合的复杂度，我们并且基于特征重要性和NDCG@50_half进行快速的特征选择，从而挖掘到了更深层次的模式并节省了大量的人力成本。
在模型上，我们尝试了LightGBM、Wide&Deep、时序模型等等，最终由于LightGBM在tabular上的优异表现力，选择了LightGBM。
在模型训练中，我们使用商品流行度加权损失去消除流行度偏差[10]，损失函数L如下式所示：
其中，参数α与流行度成反比，来削弱流行商品的权重，可以消除流行度偏差。参数β是正样本权重，用来解决样本不平衡问题。
用户偏好排序
最终，用户的商品偏好排序是通过用户的历史点击商品来引入i2i，继而对i2i引入的所有商品形成最终的排序问题。在排序过程中，根据图7所示，target item集合是由每一个source item分别产出的，所以不同的source item以及不同的多跳游走i2i关系可能会产出相同的target item。我们需要考虑如何将相同用户的相同target item的模型打分值进行聚合，如果直接进行概率求和会加强流行度偏差，而直接取均值又容易忽略掉一些强信号。最终，我们对一个用户多个相同的target item采用最大池化聚合的方式，然后对用户的所有target item进行排序，可以在NDCG@50_half上取得一个不错的效果。
为了进一步优化NDCG@50_half指标，我们对所得到的target item打分进行后处理，通过提高低流行度商品的打分权重来进一步打压高流行度的商品，最终在NDCG@50_half上取得了一个更好的效果，这其实是一个NDCG@50_full与NDCG@50_half的权衡。
评估结果
在基于多跳游走的i2i候选样本生成过程中，各种i2i关系的hitrate如表2所示，可以发现，在相同长度为1000的截断下对多种方法做混合有更高的hitrate提升，能引入更多无偏数据来增大训练集和候选集从而缓解系统的选择性偏差。
最终，由美团搜索广告团队组建的Aister在包括NDCG和hitrate的各项评价指标中都取得了第1名，如表3所示，NDCG@50_half比第二名高了6.0%，而NDCG@50_full比第二名高了4.9%， NDCG@50_half相较于NDCG@50_full有更明显的优势，说明我们更好地针对消除偏差问题进行了优化。
广告业务应用
搜索广算法团队负责美团与点评双平台的搜索广告与筛选列表广告业务，业务类型涉及餐饮、休闲娱乐、丽人、酒店等，丰富的业务类型为算法优化带来很大空间与挑战。
在搜索广告业务问题中，数据偏差问题是个重要且具挑战性的问题。广告系统中有两个重要的数据偏差——位置偏差与选择性偏差，搜索广告算法团队也针对这两个偏差问题进行了较多优化。位置偏差问题，即位置靠前的点击率天然高于位置靠后的，不同于传统的作为偏差的处理方式，我们引入一致性建模的思想，并通过灵活的深度网络设计达到一致性目标，取得业务效果提升。
在选择性偏差问题上，整个广告系统投放过程呈现出了一个漏斗图，如图9所示，系统分为Matching、Creative-Select、Ranking、Auction几个阶段。每一个阶段的候选是由上一阶段选择。以排序阶段为例（Ranking），线上系统排序的候选包含了匹配（Matching）阶段输出的所有候选，但是排序模型的训练数据是根据模型选择的曝光（Pageview）数据，仅为线上排序系统候选的一个小的子集，模型线上与线下输入数据的差异违反了建模分布一致性假设，上述选择性偏差会导致两方面明显的问题：
- 模型预估不准确：从曝光样本中学习到的模型存在偏差且不准确，会导致线上预估效果较差，尤其对于同历史曝光样本分布差异大的候选样本。
- 反馈链路循环影响广告生态：由于模型选择的样本进行曝光，然后进入模型训练进一步选择新的曝光样本，模型基于有偏样本不断学习，使得整体反馈环路不断受到偏差影响，系统选择面越来越窄形成“马太效应”。
为了解决上面的预估与生态问题，我们通过样本生成和多阶段训练两方面进行算法优化。在样本生成方面，我们进行三方面的数据生成与样本选择。首先，如图10所示，我们采用基于Beta分布的Exploration算法，通过历史点击率和统计置信度生成Exploration候选，算法背后的假设是置信度越大点击率的方差越小。
如下图所示，横轴代表预估点击率，纵轴代表概率密度，在黄框中参数的Beta分布生成的样本预估点击率分布接近于真实的样本分布，用于补充仅通过模型选择的曝光数据；其次，我们结合随机游走进行负样本优化，并通过采样算法和Label优化来控制精度。最后，训练样本大多由系统主流量选择，而在下一次模型优化全量后选择的训练样本会发生较大变化，上述差异性也会导致在ABTest时小流量模型精度不符合预期，我们也针对上述不同模型挑选的数据分布差异进行数据选择。
并且，结合上述多种样本分布的差异性，通过多阶段训练来优化模型，如图11所示，我们基于样本强度控制训练顺序与参数，使得训练数据同线上真实候选分布更一致。最终不仅在CTR预估模型（Ranking阶段）和创意优选模型（Creative-Select阶段）两个模块均取得较显著的业务效果提升，并且更一致的建模方式也使得了候选扩量等偏差较重问题的实验由负向变正向，更扎实的验证方式也为未来优化打下了坚实的基础。
总结与展望
KDD Cup是同工业界联接非常紧密的比赛，每年赛题紧扣业界热点问题与实际问题，其中历年产出的Winning Solution对工业界也有很大的影响。例如，KDD Cup 2012获胜方案产出了FFM（Feild-aware Factorization Machine）与XGBoost的原型，在工业界取得广泛应用。
今年KDD Cup 的Debiasing问题也是当前广告与推荐领域中最具挑战性的问题之一，本文介绍了我们在KDD Cup 2020 Debiasing赛题上取得第1名的解决方案，解决方案不同于以往CTR预估方式等u2i的兴趣建模方法，我们采用u2i2i方式将u2i建模转换为i2i建模，并构建异构图通过多跳游走探索更多无偏样本，从而缓解了选择性偏差，在建模过程中对图的构建、模型的损失函数以及预估值后处理等过程都引入了流行度惩罚来缓解流行度偏差，最终克服了选择性偏差和流行度偏差两个赛题挑战。
同时本文也介绍我们在美团搜索广告上关于数据选择性偏差问题的业务应用，之前在广告系统中已经针对偏差问题进行了较多优化，这次比赛也让我们对偏差问题的研究方向有了更进一步的认知。我们希望在未来的工作中会基于本次比赛取得的偏差优化经验进一步地去优化广告系统中的偏差问题，让广告系统变得更加公平。
参考文献
[1] Fairness in Recommender Systems
[2] Singh A, Joachims T. Fairness of exposure in rankings[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018: 2219-2228.
[3] Stinson C. Algorithms are not Neutral: Bias in Recommendation Systems[J]. 2019.
[4] Ovaisi Z, Ahsan R, Zhang Y, et al. Correcting for Selection Bias in Learning-to-rank Systems[C]//Proceedings of The Web Conference 2020. 2020: 1863-1873.
[5] Wang X, Bendersky M, Metzler D, et al. Learning to rank with selection bias in personal search[C]//Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval. 2016: 115-124.
[6] Abdollahpouri H, Burke R, Mobasher B. Controlling popularity bias in learning-to-rank recommendation[C]//Proceedings of the Eleventh ACM Conference on Recommender Systems. 2017: 42-46.
[7] Abdollahpouri H, Mansoury M, Burke R, et al. The impact of popularity bias on fairness and calibration in recommendation[J]. arXiv preprint arXiv:1910.05755, 2019.
[8] Schafer J B, Frankowski D, Herlocker J, et al. Collaborative filtering recommender systems[M]//The adaptive web. Springer, Berlin, Heidelberg, 2007: 291-324.
[9] Zhang S, Tay Y, Yao L, et al. Next item recommendation with self-attention[J]. arXiv preprint arXiv:1808.06414, 2018.
[10] Yao S, Huang B. Beyond parity: Fairness objectives for collaborative filtering[C]//Advances in Neural Information Processing Systems. 2017: 2921-2930.
作者简介
坚强，明健，胡可，曲檀，雷军等，均来自美团广告平台搜索广告算法团队。
Kubernetes已经成为美团云基础设施的管理引擎，它带来的不仅仅是高效的资源管理，同时也大幅降低了成本，而且为美团云原生架构的推进打下了坚实的基础，支持了Serverless、云原生分布 ...