|如何斩获KDD Cup两冠一季？美团广告团队公开解决方案
机器之心发布
机器之心编辑部
在不久前结束的 KDD Cup 2020 竞赛中 ， 美团到店广告平台搜索广告算法团队在 Debiasing、AutoGraph、Multimodalities Recall 三道赛题中获得了两冠一季的成绩 。 本文将介绍该队伍的解决方案 。
ACM SIGKDD （国际数据挖掘与知识发现大会 ， 简称 KDD）是数据挖掘领域的国际顶级会议 。 KDD Cup 比赛是由 SIGKDD 主办的数据挖掘领域顶级赛事 ， 该赛事自 1997 年开始 ， 每年举办一次 ， 是目前数据挖掘领域最具影响力的赛事 。
KDD Cup 2020 共设置五道赛题（四个赛道） ， 分别涉及 Debiasing（数据偏差问题）、Multimodalities Recall（多模态召回问题）、AutoGraph（自动化图表示学习）、对抗学习问题和强化学习问题 。
本文插图
图 1：KDD 2020 会议
美团到店广告平台搜索广告算法团队的黄坚强、胡可、漆毅、曲檀、陈明健、郑博航、雷军与中科院大学唐兴元共同组建参赛队伍 aister ， 参加了 Debiasing、AutoGraph、Multimodalities Recall 三道赛题 ， 并最终在 Debiasing、AutoGraph 赛道中获得冠军（1/1895、1/149） ， 在 Multimodalities Recall 赛道中获得季军（3/1433） 。
本文插图
图 2：KDD Cup 2020 Debiasing、AutoGraph、Multimodalities Recall 赛题榜单
本文将分别介绍 aister 团队针对 Debiasing、AutoGraph 和 Multimodalities Recall 三道赛题的解决方案 。
Debiasing 赛题
赛题介绍与问题分析
KDD Cup Debiasing 赛题是电子商务用户下一次点击商品预测（Next-Item Prediction）问题 ， 核心关注点在于如何解决推荐系统偏差 。
推荐系统面临的一个严峻挑战是公平性（Fairness）问题 ， 即如果机器学习系统配备了短期目标（例如短期的点击、交易） ， 单纯朝短期目标进行优化将会导致严重的「马太效应」 ， 热门商品容易受到更多的关注 ， 冷门商品愈发被遗忘 ， 从而造成系统中的流行度偏差 。 并且大多数模型和系统的迭代依赖于页面浏览（Pageview）数据 ， 而曝光数据是实际候选中经过模型选择的一个子集 ， 不断地依赖模型选择的数据与反馈再进行训练 ， 将形成选择性偏差 。
上述流行度偏差与选择性偏差不断积累 ， 就会导致系统中的「马太效应」越来越严重 。 因此 ， 人工智能公平性问题对于推荐系统的不断优化至关重要 ， 这将对推荐系统的发展以及生态环境产生深远的影响 。
赛题提供了用户点击数据与商品多模态数据 ， 但用户特征数据大量缺失 。 为了聚焦消除偏差问题 ， 赛题提供的评测指标包括 NDCG@50_full、NDCG@50_half、hitrate@50_full、hitrate@50_half 。
NDCG@50_full、NDCG@50_half 这两项指标用于排名评估 。 首先通过 NDCG@50_full 筛选出前 10% 的队伍 ， 然后在这些队伍中使用 NDCG@50_half 进行最终排名 。 NDCG@50_half 是在长尾商品数据上进行评测 ， 能够更好地评估选手们对数据偏差的优化 。
NDCG@50_full：与常规推荐系统评价指标 NDCG 一致 ， 该指标在整个评测数据集上评估每次用户请求所推荐的前 50 个商品列表的平均排序效果 。 该评测集被称为 full 评测集 。
NDCG@50_half：关注偏差问题 。 从整个 full 评测数据集中取出一半历史曝光少的点击商品 ， 对这些商品的推荐列表进行 NDCG 指标评估 。 该评测集被称为 half 评测集 。
为了更好地理解赛题 ， 该团队对提供的数据进行了分析 。
商品多模态数据分析：商品多模态数据包含文本向量及图片向量 ， 覆盖率高达 92.52% ， 我们可以根据向量来计算商品间的文本相似度及图片相似度 。 由于用户信息及商品信息的缺少 ， 如何利用好这些仅有的商品多模态向量对于整个任务而言是极其重要的 。
选择性偏差分析：如表 1 所示 ， 该团队对基于 i2i（item2item）点击共现以及基于 i2i 向量相似度两种 Item-Based 协同过滤方法所召回的商品候选集进行对比 ， 发现两种召回方法在评测集上都有一个较低的 hitrate 。 不管使用哪种方法 ， 系统都存在较大的选择性偏差 ， 即推荐给用户的样本是根据系统来选择的 ， 真实的候选集合大大超过了推荐给用户的样本 ， 导致训练数据带有选择性偏差 。 进一步地 ， 该团队发现基于 i2i 点击共现在 full 评测集上相对于 half 评测集有更高的 hitrate ， 说明其更偏好于流行商品；相反 ， 基于 i2i 向量相似度的召回方法对于流行度无偏好 。 同时两种方式召回的候选集只有 4% 的重复率 ， 因此我们需要结合点击共现和向量相似度两种商品关系来生成更大的训练集 ， 从而缓解选择性偏差 。
本文插图
表 1：i2i 点击共现与 i2i 向量相似度的召回 hitrate
流行度偏差分析：如图 3 所示 ， 该团队对商品的流行度进行了分析 ， 其中横坐标为商品点击频数 ， 即商品流行度 ， 纵坐标为商品个数 。 图中对流行度做了截断 ， 横坐标最大值本应为 228 。 可以看出 ， 大部分商品的流行度较低 ， 符合长尾分布 。
图中的两个箱型图分别是 full 评测数据集商品流行度的分布 ， 以及 half 评测数据集商品流行度的分布 。 从这两个箱型图可以看出 ， 流行度偏差存在于数据集中 。 整个 full 评测集中有一半评测数据是基于流行度较低的商品 ， 而另一半评测数据商品的流行度较高 ， 直接通过点击商品去构建样本 ， 会导致数据中拥有较多流行度高的正例商品 ， 从而形成流行度偏差 。
本文插图
图 3：商品的流行度偏差
不同于传统的封闭数据集点击率预估问题（CTR 预估） ， 上述数据特点与评测方式更关注偏差优化 。 赛题中主要存在两种偏差：选择性偏差（Selection Bias）和流行度偏差（Popularity Bias） 。
选择性偏差：曝光数据是由模型和系统选择的 ， 与系统中的全部候选集不一致 。
流行度偏差：商品历史点击次数呈现长尾分布 ， 因此流行度偏差存在于头部商品和尾部商品之间 。 如何解决流行度偏差是赛题的核心挑战之一 。
冠军解决方案
针对选择性偏差和流行度偏差这两项挑战 ， aister 团队进行了建模设计 ， 有效地优化了上述偏差 。 已有的 CTR 建模方法可以理解为 u2i 建模 ， 通常刻画用户在特定请求上下文中对候选商品的偏好 ， 而该团队的建模方式是学习用户的每个历史点击商品和候选商品的关系 ， 可以理解为 u2i2i 的建模 。 这种建模方法更有助于学习多种 i2i 关系 ， 并且轻松地将 i2i 图中的一跳关系拓展到多跳关系 。 多种 i2i 关系可以探索更多无偏数据 ， 进而增大商品候选集和训练集 ， 达到缓解选择性偏差的目的 。
同时 ， 考虑到流行商品引起的流行度偏差 ， 该团队在构图过程中对边权引入流行度惩罚 ， 使得多跳游走时更有机会探索到低流行度的商品 ， 同时在建模过程以及后处理过程中引入了流行度惩罚 ， 缓解流行度偏差 。
最终 ， 该团队形成了一个基于 i2i 建模的排序框架 ， 框架图如图 4 所示 。 在此框架中商品推荐过程被分为三个阶段 ， 分别是：基于多跳游走的 i2i 候选样本生成、基于流行度偏差优化的 i2i 建模 ， 以及用户偏好排序 。
本文插图
图 4：基于 i2i 建模的排序框架
1. 基于多跳游走的 i2i 候选样本生成
为了探索更多的 i2i 无偏候选样本来进行 i2i 建模 ， 从而缓解选择性偏差 ， 该团队构建了一个具有多种边关系的 i2i 图 ， 并在构边过程中引入了流行度惩罚来消除流行度偏差 。
如图 5 所示 ， i2i 图的构建与多跳游走 i2i 候选样本的生成过程被分为三个步骤：i2i 图的构建、i2i 多跳游走以及 i2i 候选样本生成 。
本文插图
图 5：基于多跳游走的 i2i 候选样本生成
i2i 图的构建：i2i 图中存在一种结点即商品结点 ， 两种边关系即点击共现边和多模态向量边 。 点击共现边基于用户的历史商品点击序列而构建 ， 边的权重通过以下公式得到 ， 其在两个商品间的用户历史点击共现频数的基础上 ， 考虑了每次点击共现的时间间隔因子 ， 并加入了用户活跃度惩罚以及商品流行度惩罚（用户活跃度即用户的历史点击次数 ， 商品流行度即商品的被点击次数） ， 通过惩罚它们来缓解流行度偏差 。
本文插图
i2i 多跳游走：该团队通过枚举不同的一跳 i2i 关系 ， 组合构成不同类型的二跳 i2i 关系 ， 并在构建好二跳 i2i 关系之后删除原本的一跳 i2i 关系来避免冗余 ， 这样就形成了图 5 中的五种多跳 i2i 关系 。 多跳 i2i 关系得分由以下公式得来 ， 即对每条路径的边权相乘得到路径分 ， 并对所有路径分求平均 。 通过不同边类型多跳游走的方式 ， 更多商品有更多的机会和其他商品构建多跳关系 ， 从而扩大了商品候选集 ， 缓解了选择性偏差 。
i2i 候选样本生成：每种 i2i 关系根据 i2i 得分对所有商品的候选商品集合分别进行排序和截断 ， 每种 i2i 关系间的相似度热图如图 6 所示 。 相似度是通过两种 i2i 关系构造的候选集重复度计算得出 ， 我们可以根据不同 i2i 关系之间的相似度来确定候选商品集合的数量截断 ， 以得到每种 i2i 关系中每个商品的 i2i 候选集 ， 供后续 i2i 建模使用 。
本文插图
图 6：i2i 关系相似度热图
2. 基于流行度偏差优化的 i2i 建模
该团队通过 u2i2i 建模转换 ， 将传统的基于 u2i 的 CTR 预估建模方式转换为 i2i 建模方式 。 它可以轻松使用多跳 i2i 关系 ， 同时该团队引入带流行度惩罚的损失函数 ， 使 i2i 模型朝着缓解流行度偏差的方向学习 。
如图 7 所示 ， 该团队拆分用户前置点击行为序列 ， 将每一个点击的商品作为 source item ， 从 i2i graph 中的多跳游走候选集中抽取 target item ， 形成 i2i 样本集 。 对于 target item 集合 ， 该团队基于用户下一次点击的商品与 target item 是否一致来引入该样本的标签 。 这样 ， 就可以将基于用户选择的序列建模转变为基于 i2i 的建模 ， 通过两个商品点击的时间差以及点击次数间隔 ， 从侧面引入用户的序列信息 ， 强调 i2i 的学习 ， 从而达到消除选择性偏差的目的 。 最终用户的推荐商品排序列表可以基于用户下的 i2i 打分进行 target item 排序 。
本文插图
图 7：i2i 训练样本生成
如图 8 所示 ， 该团队利用自动化特征工程思想探索高阶特征组合 ， 缓解了偏差问题业务含义抽象的问题 。 他们通过人工构造一些基础特征（如频数特征、图特征、行为特征和时间相关特征等） ， 将基础特征类型划分为 3 种：类别特征、数值特征以及时间特征 。 然后 ， 基于这些特征做高阶特征组合 ， 每一次组合形成的特征都会加入下一次组合的迭代之中 ， 以此降低高阶组合的复杂度 。 该团队基于特征重要性和 NDCG@50_half 进行快速的特征选择 ， 从而挖掘到更深层次的模式 ， 同时节省了大量的人力成本 。
本文插图
图 8：自动化特征工程
在模型方面 ， 他们尝试了 LightGBM、Wide&Deep、时序模型等 ， 最终由于 LightGBM 在 tabular 上的优异表现力 ， 选择了 LightGBM 。 在模型训练中 ， 该团队使用商品流行度加权损失来消除流行度偏差 ， 损失函数 L 参见下式 。 其中 ， 参数 α 与流行度成反比 ， 以削弱流行商品的权重 ， 消除流行度偏差 。 参数 β 是正样本权重 ， 用来解决样本不平衡问题 。
3. 用户偏好排序
最终 ， 用户的商品偏好排序是通过用户的历史点击商品来引入 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 提升 ， 能够引入更多无偏数据来增大训练集和候选集 ， 从而缓解系统的选择性偏差 。
本文插图
表 2：不同 i2i 关系的 hitrate
最终 ， 由美团搜索广告团队组建的 Aister 在包括 NDCG 和 hitrate 的各项评价指标中都取得了第 1 名 。 如表 3 所示 ， NDCG@50_half 比第二名高出 6.0% ， NDCG@50_full 比第二名高出 4.9% ， NDCG@50_half 相较于 NDCG@50_full 有更明显的优势 ， 这说明该团队针对消除偏差问题做出了更好的优化 。
本文插图
表 3：不同参赛团队解决方案的 NDCG 评估结果
AutoGraph 赛题
赛题介绍与问题分析
KDD Cup AutoGraph 赛题是有史以来第一个应用于图结构数据的自动化机器学习（AutoML）挑战 ， 参与者需设计一个解决方案来自动化进行图表示学习问题 。
传统做法一般利用启发法从图中提取每个结点的特征 ， 而近些年来 ， 研究者提出了大量用于图表示学习任务的复杂模型（如图神经网络） ， 使许多下游任务取得了最新成果 。 然而 ， 这些方法需要投入大量的计算和专业知识资源 ， 才能获得令人满意的任务性能 。
而 AutoML 是一种降低机器学习应用人力成本的有效方法 ， 在超参数调整、模型选择、神经架构搜索和特征工程方面取得了巨大成功 。 如何将 AutoML 应用于图表示学习任务也是业界关注的热点问题 。
本次 AutoGraph 竞赛针对自动化图表示学习这一前沿领域 ， 选择了图结点多分类任务来评估表示学习的质量 。 竞赛官方准备了 15 个图结构数据集 ， 5 个供下载以便离线开发解决方案 ， 5 个评估公共排行榜得分 ， 5 个评估最终排名 。 这些数据集均从真实业务中收集 ， 每个数据集提供了图结点 id 和结点特征、边和边权信息 ， 以及数据集的时间预算 。 参赛者必须在给定的时间预算和算力内存限制下设计自动化图学习解决方案 。 每个数据集会通过精度来评估准确性 ， 最终排名基于 5 个测试数据集的平均排名 。
Aister 团队对五个离线图数据集进行分析后 ， 发现图的类型多种多样 。 如表 4 所示 ， 从图的平均度可以看出离线图 3、4 较为稠密 ， 而图 1、2、5 较为稀疏；从特征数量可以看出图 5 无结点特征 ， 其余图有结点特征；同时我们可以发现 ， 图 4 是有向图 ， 而其余图是无向图 。
从表 4 我们可以看出 ， 大部分图数据集的时间限制在 100 秒左右 ， 这是一个很短的时间限制 。 大部分神经网络架构和超参数搜索方案都需要较长的搜索时间 ， 数十个小时甚至长达数天 。 因此 ， 不同于神经网络架构搜索 ， 我们需要一个架构和超参数快速搜索的方案 。
本文插图
表 4：五个离线图数据集的概况
如图 9 所示 ， 该团队发现在图数据集 5 上存在模型训练不稳定的问题 ， 模型在某个 epoch 上验证集精度显著下降 。 该团队认为这主要是因为图数据集 5 易于学习 ， 会发生过拟合现象 ， 因此在自动化建模过程中需要保证模型的强鲁棒性 。
本文插图
图 9：模型在训练过程中的不稳定性
同时 ， 从图 10 可以发现 ， 保证每个数据集排名的稳定性相比于优化某个数据集的精度更为重要 。 例如数据集 5 模型精度差异仅为 0.15% 却导致了十个名次的差异 ， 数据集 3 模型精度差异有 1.6% 却仅导致 7 个名次的差异 。 因此 ， 该团队需要采用排名鲁棒的建模方式 ， 来增强数据集排名的稳定性 。
本文插图
图 10：不同选手在不同数据集上的精度及排名
基于以上数据分析 ， 该赛题存在以下三个挑战：
图数据的多样性：解决方案要在多个不同的图结构数据上均达到优秀效果 。 图的类型多种多样 ， 包含了有向图 / 无向图、稠密图 / 稀疏图、带特征图 / 无特征图等 。
超短时间预算：大部分数据集的时间限制在 100 秒左右 ， 在图结构和参数搜索方面需要有一个快速搜索方案 。
鲁棒性：在 AutoML 领域 ， 鲁棒性是非常重要的因素 。 最后一次提交要求选手在之前没见过的数据集上进行自动化建模 。
冠军解决方案
针对以上三个挑战 ， aister 团队设计了一个自动化图学习框架 ， 如图 11 所示 ， 该框架对输入的图进行预处理和图特征构建 。
本文插图
图 11：自动化图学习框架
aister 团队使用了多种具有不同特点的图神经网络 ， 采用图神经网络结构和超参数快速搜索方法 ， 还设计了一个多级鲁棒性模型融合策略 ， 来分别克服上述三项挑战 。 最终 ， 该团队的自动化图学习解决方案在较短的时间内对多个不同图结构数据进行结点分类 ， 并达到鲁棒性效果 。 接下来 ， 我们将详细介绍整个解决方案 。
1. 图神经网络模型
为了克服图的多样性挑战 ， 该团队结合谱域及空域两类图神经网络方法 ， 采用 GCN、TAGConv、GraphSAGE、GAT 四个图神经网络模型对多种不同图结构数据进行更好地表示学习 ， 每个模型针对不同类型的图结构数据具备各自的优势 。
图作为一种非欧式空间结构数据 ， 其邻居结点个数可变且无序 ， 因此直接设计卷积核是困难的 。 谱域方法通过图拉普拉斯矩阵的谱分解 ， 在图上进行傅立叶变换得到图卷积函数 。 GCN 作为谱域的经典方法 ， 公式如下所示：
其中 D 是对角矩阵 ， 每个对角元素为对应结点的度 ， A 是图的邻接矩阵 ， 其通过给每个结点加入自环使卷积函数获取自身结点信息 ， 并在傅立叶变换之后使用切比雪夫一阶展开近似谱卷积 ， 使每一个卷积层仅处理一阶邻域信息 ， 通过堆叠多个卷积层达到多阶邻域信息传播 。
由于依赖拉普拉斯矩阵 ， GCN 等谱域方法并不能很好地处理有向图 ， 有向图无法直接定义拉普利矩阵及其谱分解 ， 因此该团队将有向图的边进行反转改为无向图 。 GCN 方法简单且有效 ， 该团队将 GCN 应用到所有数据集上 ， 大部分数据集能取得较好的效果 。
相较于堆叠多层获取多阶邻域信息的 GCN 方法 ， TAGConv 通过邻接矩阵的多项式拓扑连接来获取多阶邻域信息 ， 公式如下所示：
可以发现 ， 其通过预先计算邻接矩阵的 k 次幂 ， 在训练过程中实现多阶邻域卷积并行计算 ， 且高阶邻域的结果不受低阶邻域结果的影响 ， 从而加快模型在高阶邻域中的学习 。 就实验结果来看 ， 其在稀疏图上能快速收敛 ， 相比于 GCN 能够达到更好的效果 。
相较于利用傅立叶变换来设计卷积核参数的谱域方法 ， 空域方法的核心在于直接聚合邻居结点的信息 ， 难点在于如何设计带参数、可学习的卷积核 。 GraphSAGE 提出了经典的空域学习框架 ， 通过图采样与聚合来引入带参数可学习的卷积核 ， 其核心思想是对每个结点采样固定数量的邻居 ， 这样就可以支持各种聚合函数 。 均值聚合函数的公式如下所示 ， 其中的聚合函数可以替换为带参数的 LSTM 等神经网络：
由于 GraphSAGE 带有邻居采样算子 ， 因此 Aister 团队引入该图神经网络来极大地加速稠密图的计算 。 就实验结果而言 ， 其在稠密图上的运行时间远小于其他图神经网络 ， 并且由于采样能一定程度上避免过拟合 ， 因此它在有些稠密图上能够达到较好的效果 。
GAT 方法将 Attention 机制引入图神经网络 ， 公式如下所示：
本文插图
本文插图
其通过图结点特征间的 Attention 计算每个结点与其邻居结点的权重 ， 通过权重对结点及其邻居结点进行聚合作为结点的下一层表示 。
通过 Masked Attention 机制 ， GAT 能处理可变个数的邻居结点 ， 并且其使用图结点及其邻居结点的特征来学习邻居聚合的权重 ， 有效利用结点的特征信息进行图卷积 ， 泛化效果更强 ， 它参考了 Transformer 引入 Multi-head Attention 的做法来提高模型的拟合能力 。 GAT 利用结点特征来计算结点与邻居结点间的权重 ， 因此在带有结点特征的数据集上表现优异 ， 但如果特征维度多就会使得 GAT 计算缓慢 ， 甚至出现内存溢出的现象 。 这就需要在特征维度多的情况下对 GAT 的参数进行搜索限制 ， 要求其在一个参数量更小的空间下搜索 。
2. 超参快速搜索
由于超短时间预算的挑战 ， 该团队需要设计一个超参快速搜索方法 ， 来保证花较少的时间就可以对每个图模型进行参数搜索 ， 并且在每个数据集上尽可能地使用更多的图模型进行训练和预测 。 如图 12 所示 ， 该团队将参数搜索分为线下搜索和线上搜索两部分 。
本文插图
图 12：超参快速搜索
该团队在线下搜索时 ， 针对每一个图模型在多个数据集上使用一个大的搜索空间去确定图结构和参数边界 ， 保证每个数据集在这个边界中都有较好的效果 。
具体而言 ， 他们基于有向图 / 无向图、稀疏图 / 稠密图、带特征图 / 无特征图等不同图类型对不同模型的大多数参数进行了搜索 ， 确定了几个重要的超参数 ， 例如对于稀疏图 ， 调整 TAGConv 多项式的阶数 ， 可使其卷积感受野更大 ， 迅速对数据集进行拟合 。 该团队在线下主要确定了不同图模型学习率、卷积层数、隐层神经元个数这三个重要参数的边界 。
由于线上的时间预算限制 ， 该团队基于线下的参数边界
确定了一个小的参数搜索子空间 ， 以便执行线上搜索 。 由于时间预算相对较少 ， 没有充足的时间在参数上做完整的训练验证搜索 ， 因此该团队设计了一个快速参数搜索方法 。
对于每个模型的超参空间 ， 通过少量 epoch 的训练来比较验证集精度 ， 从而确定超参数 。 如图 13 所示 ， 该团队通过 16 轮的模型训练 ， 来选取验证集精度最优的学习率 0.003 ， 此举意在确定哪些超参数可使模型快速拟合该数据集而不追求选择最优的超参数 ， 以加快参数搜索和模型训练 。
本文插图
图 13：少量 epoch 模型训练下不同学习率的验证集精度
通过快速超参搜索 ， 该团队保证每个模型在每个数据集上均能在较短时间内确定超参数 ， 从而利用这些超参数进行每个模型的训练 。
3. 多级鲁棒模型融合
由于该次竞赛通过数据集排名平均来确定最终排名 ， 故而鲁棒性是特别重要的 。 为了达到鲁棒效果 ， 该团队采用了一个多级鲁棒模型融合策略 。
如图 14 所示 ， 在数据层面进行切分来进行多组模型训练 ， 每组模型包含训练集及验证集 ， 通过验证集精度使用 Early Stopping 来保证每个模型的鲁棒效果 。 每组模型包括多种不同的图模型 ， 每种图模型训练 n 次进行均值融合得到稳定效果 。 由于不同种类图模型的验证精度差异较大 ， 因此需要对不同种类的图模型根据图的稀疏性以及验证集精度进行稠密度自适应带权融合 ， 以便利用不同模型在不同数据集上的差异性 ， 最后再对每组图模型进行均值融合来利用数据间的差异性 。
本文插图
图 14：多级鲁棒模型融合
评估结果
表 5 展示了不同图模型在五个离线图数据集上的测试精度：与「图神经网络模型」章节所描述的一致 ， GCN 在各个图数据集上有较好的效果 ， 而 TAGConv 在稀疏图数据集 1、2、5 有更优异的效果 ， GraphSAGE 在稠密图数据集 4 上取得最好的效果 ， GAT 在有特征的数据集 1、2、4 中表现较为良好 ， 而模型融合在每个数据集上均取得更稳定且更好的效果 。
本文插图
表 5：不同图模型在五个离线图数据集上的测试精度
如表 6 所示 ， 该团队的解决方案在每个图数据集上均达到鲁棒性效果 ， 每个数据集的排行均保持较领先的水平 ， 并避免过度拟合 ， 从而在平均排行上取得第一 ， 最终 aister 团队在 KDD Cup 2020 AutoGraph 赛题上获得冠军 。
本文插图
表 6：Top 5 参赛队伍在最后 5 个数据集上所有图数据集的平均排行及在每个图数据集的单独排行
Multimodalities Recall 赛题
赛题介绍与分析
多模态召回赛题由阿里巴巴达摩院智能计算实验室发起并组织 ， 关注电商行业中的多模信息学习问题 。
2019 年 ， 全世界线上电商营收额达到 3530 亿美元 。 据相关预测 ， 到 2022 年 ， 总营收将增长至 6540 亿美元 。 大规模的营收和高速增长预示着 ， 消费者对于电商服务有着巨大需求 。 跟随这一增长 ， 电商行业中各种模态的信息越来越丰富 ， 如直播、博客等等 。 怎样在传统的搜索引擎和推荐系统引入这些多模信息 ， 更好地服务消费者？这值得相关从业者深入探讨 。 基于此背景 ， 主办方发起了该赛题 。
主办方提供了淘宝商城的真实数据 ， 包括两部分：一是搜索短句（query）相关 ， 为原始数据；二是商品图片相关 ， 考虑到知识产权等 ， 提供的是使用 faster rcnn 基于图片提取出的特征向量 。 两部分数据被组织为基于 query 的图片召回问题 ， 即有关文本模态和图片模态的召回问题 。
为方便理解 ， 主办方提供了少量真实图片及其对应的原始数据 ， 如图 15 所示 。 该图例是一个正样例 ， 其 query 为 sweet french dress；图片主体部分是一名身着甜美裙装的女性 ， 主体部分以外 ， 则有大量杂乱信息 ， 包括一个手提包、一些气球以及一些商标和促销文字信息 。 赛题本身不提供原始图片 ， 提供的是 faster rcnn 基于图片提取出的特征向量 ， 即图片中被框出的几个部分 。 可见 ， 一方面 faster rcnn 提取了图片中有明显语义的内容 ， 有助于模型学习；另一方面 ， faster rcnn 的提取会包含较多的框 ， 这些框体现不出主次之分；此外 ， faster rcnn 也并非完美无缺 ， 因而多模态召回问题还有赖进一步地挖掘 。
本文插图
图 15：搜索短语与图片的匹配示例
本次赛题设置的评价指标为 NDCG@5 ， 计算逻辑如下：在给定的测试集里 ， 每条 query 会给出约 30 个样本 ， 其中大约 6 条为正样本 ， 其余为负样本；赛题需要选手设计匹配算法 ， 召回出任意 5 条正样本 ， 即可获得该 query 的全部分数 ， 否则 ， 按照召回的正样本条数来计算 NDCG 指标作为该 query 的分数 。 全部 query 的分数进行平均 ， 即为最终得分 。
主办方提供了三份数据集 ， 分别是训练集、验证集和测试集 。 各个数据集的基本信息如表 7 所示 。
本文插图
表 7：数据集概况
为进一步探索数据特征 ， 该团队将验证集给出的原始图片和特征信息做了聚合展现 ， 表 8 是一组示例 。
本文插图
表 8：搜索短语与图片的匹配正负例
根据如上基本信息 ， 该团队总结了数据集的三个重要特点：
训练集和验证集 / 测试集的数据特点大不相同 。 训练集量级显著高于验证集 / 测试集 ， 足有三百万条 query-image 对 ， 是验证集 / 测试集的一百倍以上 。 同时 ， 训练集的每条 query-image 对均被视为正样本 ， 这和验证集给出的一条 query 下挂多个有正有负的 image 截然不同 。 而通过对验证集原始图片和 query 进行可视化探索 ， 可以发现验证集数据质量很高 ， 应该为人工标注 。 考虑人工标注成本和负样本的缺失 ， 训练集极大可能描述的是点击关系 ， 而非人工标准的语义匹配关系 。 该团队的解决方案必须考虑「训练集和测试集并不匹配」这一基本特点 。
图片信息复杂 ， 常常包含多个物体 。 这些物体均被框出作为给定特征 ， 但各个框之间的语义信息并不平等；某些是噪音 ， 如 query (men's high collar sweater) 下的墨镜、围巾、相机等框图 ， 某些又因商品展示需要而重复 ， 如 query (breathable and comfortable children's shoes) 下重复鞋的框图 。 平均来说 ， 一张图片有 4 个框 ， 怎么将多个框包含的语义信息去噪、综合 ， 得到图片的语义 ， 是建模的重点 。
query 作为给定的原始文本 ， 有着与常用语料截然不同的构造和分布情况 。 从示例表可见 ， query 并非自然语句 ， 而是一些属性和商品实体连缀成的短语 。 经过统计发现 ， 90% 的 query 由 3-4 个单词组成；训练集有约 150 万不同的 query ， 其词表大小在 15000 左右；通过最后一个单词 ， 可将全部 query 归约为大约 2000 类 ， 每一类是一个具体的商品名词 。 我们需要考虑文本数据的这些特质 ， 进行针对性处理 。
从上述数据集的三个特点出发 ， 该团队总结了此竞赛的两大主要挑战 。
分布不一致问题：经典统计机器学习的基础假设是训练集和测试集分布一致 ， 不一致的分布通常会导致模型学偏 ， 训练集和验证集效果难以对齐 。 我们必须依赖已有大规模训练集中的点击信号和和测试集同分布的小规模验证集 ， 设计可行的数据构建方法和模型训练流程 ， 采取诸如迁移学习等技术 ， 来处理这一问题 。
复杂多模信息匹配问题：怎么进行多模信息融合是多模态学习中的基础性问题 ， 而怎么对复杂的多模信息进行语义匹配 ， 是本竞赛特有的挑战 。 从数据看 ， 一方面商品图片多框 ， 信息含量大、噪点多；另一方面用户搜索 query 一般具有多个细粒度属性词 ， 且各个词均在语义匹配中发挥作用 。 这就要求我们在模型设计上针对性地处理图和 query 两方面的复杂性 ， 并做好细粒度匹配 。
竞赛技术方案
该团队的方案直接回应了上述两项挑战 ， 其主体部分包含两方面内容：一是通过联合多样化的负采样策略和蒸馏学习来桥接训练数据和测试集的分布 ， 处理分布不一致问题；二是采取细粒度的文本 - 图片匹配网络 ， 进行多模信息融合 ， 处理复杂多模信息匹配问题 。 最后 ， 通过两阶段训练和多模融合 ， 进一步提升模型表现 。
整个方案的流程如图 16 所示：
本文插图
图 16：基于多样化负采样的多阶段蒸馏学习框架
下面我们来看该方案的各个部分 。
1. 多样化负采样策略和预训练
训练集和测试集分布不一致 。 最直观的不一致是 ， 训练集中只有正样本 ， 没有负样本 ， 因此需要设计负采样策略来构造负样本 ， 并尽可能使得采样的样本靠近测试集的真实分布 。
最直观的想法是随机采样 。 随机采样简单易行 ， 但和验证集区别较大 。 分析验证集发现 ， 同一 query 下的候选图片通常有着紧密的语义关联 。 如「甜美法式长裙」这一 query 下 ， 待选的图片全是裙装 ， 只是在款式上有所不同 。 这说明 ， 这一多模匹配赛题需要在较细的属性粒度上对文本和图片进行匹配 。 从图片标签和 query 词两个角度出发 ， 我们可以通过相应的聚类算法 ， 使得待采样的空间从全局细化为相似语义条目 ， 从而达到负采样更贴近测试集分布的目的 。
基于如上分析 ， 该团队设计了如表 9 所示的四种采样策略来构建样本集 。 这四种策略中 ， 随机采样得到的正负样本最容易区分 ， 按 query 最后一词采样得到的正负样本最难区分；在训练中 ， 该团队从基准模型出发 ， 先在最简单的随机采样上训练基准模型 ， 然后在更困难的按图片标签采样、按 query 的聚类采样上基于先前的模型继续训练 ， 最后在最难的按 query 最后一词采样的样本上训练 。 这样由易到难、由远到近的训练方式 ， 有助于模型收敛到验证集分布上 ， 在测试集上取得更好的效果 。
本文插图
表 9：多样化负采样
2. 蒸馏学习
尽管使用多种采样策略 ， 可从不同角度逼近测试集的真实分布 ， 但由于未直接利用测试集信息指导负采样 ， 因此该方法仍存在不足 。
于是 ， 该团队采用蒸馏学习的办法 ， 来进一步优化负采样逻辑 ， 以便获取更贴近测试集的 label 分布 。 如图 17 所示 ， 在通过训练集负采样得到的样本集上预训练以后（第 1 步）；将该模型在验证集上进一步 finetune ， 得到微调模型（第 2 步）；利用微调模型 ， 反过去在训练集上打伪标签 ， 作为 soft label ， 并把 soft label 引入 loss ， 和原始的 0-1 hard label 联合学习（第 3 步） 。 这样 ， 在训练集的训练上 ， 直接引入了验证集的分布信息 ， 进一步贴近了验证集分布 ， 提升了预训练模型的表现 。
本文插图
图 17：多阶段蒸馏学习
3. 细粒度匹配网络
多模态学习方兴未艾 ， 各类任务、模型层出不穷 。 针对此次竞赛面临的复杂图片和搜索 query 匹配的问题 ， 参照 CVPR 2017 VQA 竞赛的冠军方案 ， 该团队设计了图 18 所示的神经网络模型作为主模型 。
本文插图
图 18：细粒度匹配网络
该模型的设计主要考虑以下三点：
利用带门全连接网络做语义映射 。 图片和 query 处于不同的语义层级 ， 需利用函数映射到相同的语义空间 ， 该团队采取两个全连接层的方式达到该目的 。 实验发现 ， 全连接层的隐层大小是比较敏感的参数 ， 适当增大隐层 ， 可在不过分增加计算复杂度的情况下 ， 显著提升模型效果 。 此外 ， 如文献所述 ， 使用带门的全连接层可进一步提升语义映射网络的效果 。
采用双向 attention 机制 。 图片和 query 均由更细粒度的子语义单元组成 。 具体来说 ， 一张图片上可能有多个框 ， 每个框均有独立的语义信息；一个 query 分为多个词 ， 每个词也蕴含独立的语义信息 。 这一数据特点是由电商搜索场景决定的 。 因而 ， 在模型设计时 ， 需考虑到单个子语义单元之间的匹配 。 该团队采用单个词和全部框、单个框和全部词双方向的注意力机制 ， 去捕捉这些子单元的匹配关系和重要程度 。
使用多样化多模融合策略 。 多模信息融合有很多手段 ， 大部分最终归结为图片向量和 query 向量之间的数学操作符 。 考虑到不同融合方式各有特点 ， 多样融合能够更全面地刻画匹配关系 ， 因此该团队采用了 Kronecker Product、Vector concatenation 和 self-attention 三种融合方式 ， 将经过语义空间转化和 attention 机制映射后的图片向量和 query 向量进行信息融合 ， 并最终送入全连接神经网络 ， 最终得到匹配与否的概率值 。
多模融合
在上述技术手段的处理下 ， 可以得到多个基础模型 。 这些模型均可在验证集上进行 finetune ， 从而使其效果更贴近真实分布 。 一方面 ， finetune 阶段可继续使用前述的神经网络匹配模型 。 另一方面 ， 前述神经网络可作为特征提取器 ， 将其在规模较小的验证集上的输出 ， 放入树模型重新训练 。 这一好处是树模型和神经网络模型异质性大 ， 融合效果更好 。 最终 ， 该团队提交的结果是多个神经网络模型和树模型融合的结果 。
评估结果
以随机采样训练的粗粒度（图片表示为所有框的平均 ， query 表示为所有词的平均）匹配网络为基准模型 ， 表 10 列出了该团队解决方案各个部分对基准模型的提升效果 。
本文插图
表 10：不同方法的 NDCG 提升
总结
KDD Cup 竞赛与工业界联接十分紧密 ， 每年的赛题紧扣业界热点问题与实际问题 ， 历年的 Winning Solution 对工业界也有很大的影响 。 例如 ， KDD Cup 2012 获胜方案产出了 FFM (Feild-aware Factorization Machine) 与 XGBoost 的原型 ， 在工业界取得广泛应用 。
今年 KDD Cup 的几大赛题也是当前广告与推荐领域中最具挑战性的问题 ， 本文介绍了美团搜索广告团队在 KDD Cup 2020 Debiasing、AutoGraph、Multimodalities Recall 三个赛题上取得两冠一季的解决方案 。
Debiasing 赛题解决方案从消除推荐数据偏差的目的出发 ， 进行 i2i 多跳游走、i2i 建模以及 u2i 排序 ， 克服了选择性偏差和流行度偏差两个赛题挑战 。
AutoGraph 赛题解决方案将 AutoML 应用于自动化图表示学习中 ， 通过搭建多种图神经网络 ， 并采用快速参数搜索方法以及多级鲁棒模型融合策略 ， 来克服图数据的多样性、超短时间预算以及鲁棒性等三个赛题挑战 。
Multimodalities Recall 赛题解决方案通过多样化负采样策略和预训练、蒸馏学习等方法 ， 搭建细粒度匹配网络并采用多模型融合等方法来克服分布不一致问题以及复杂多模信息匹配问题等两个赛题挑战 。
这些解决方案多数从数据分析出发来定位赛题难点 ， 找寻赛题突破口 ， 从而设计赛题解决方案来克服赛题挑战 。 同样地 ， 这种解决问题的思路也有助于美团到店广告团队在广告领域上做进一步的探索 。
aister 团队简介
黄坚强 ， 美团广告平台搜索广告算法团队算法工程师 ， 毕业于北京大学 。
胡可 ， 美团广告平台搜索广告算法团队资深算法专家 ， 毕业于香港中文大学 。
陈明健 ， 美团广告平台搜索广告算法团队算法工程师 ， 毕业于北京大学 。
漆毅 ， 美团广告平台搜索广告算法团队算法工程师 ， 毕业于清华大学 。
唐兴元 ， 毕业于中国科学院大学 。
曲檀 ， 美团广告平台搜索广告算法团队算法工程师 ， 毕业于中国人民大学 。
【|如何斩获KDD Cup两冠一季？美团广告团队公开解决方案】雷军 ， 美团广告平台搜索广告算法团队研究员 ， 毕业于清华大学 。
推荐阅读
![[卜广鉴八字一绝]生辰算八字：这几类八字的人多晚婚之命](https://imgcdn.toutiaoyule.com/20200417/20200417152127812452a_t.jpeg)
- 小龙虾|三农探析：池塘养殖小龙虾如何高产？高产养殖技术全解析
- 菜籽饼|菜籽饼被誉为果园之宝，但用错了烧苗烧根，果农如何来使用？
- 水产养殖|生态水产养殖如何提高鱼病的预防工作？大疆渔业这样建议
- 瘦肉精|如何避开 315曝光的瘦肉精问题肉？
- 美国_军事|那个帮美国破解北斗卫星的清华才女高杏欣，13年过去了，近况如何
- 花菜有人焯水，有人直接下锅炒，都错了，看饭店大厨是如何做的
- 如何晚上发面早上蒸？教你用冷藏发酵，一学就会，馒头包子特好吃
- 急性肠胃炎|急性肠胃炎是如何“起哄”的？这4个“不舒服”一出现，赶紧就医
- 鸭子|养鸭要注意什么，在每个季节里，如何来放牧
- 柑橘|开春柑橘落叶严重怎么办？如何预防柑橘落叶？