阿里广告match技术最新突破：亿级商品全库最优检索技术 作者 | 阿里定向广告团队 编辑 | 蔡芳芳 1. 背景 当前繁荣发展的互联网行业，不管是搜索、推荐还是广告业务，其本质都是实现了人和海量信息之间的高效连接，其核心是人和信息的匹配技术。其中，“人找信息”主要通过搜索技术来实现，而基于人和信息的关系实现“信息找人”，则主要依赖推荐及广告技术。从匹配这一核心技术出发，搜索、推荐和广告看似业务形态不同，其实技术组成却是非常相通的：搜索可以认为是一种带 query 相关性约束的匹配，而广告则是叠加了广告主营销意愿（价格）约束的匹配。所以，匹配技术的创新对推动搜索、推荐和广告业务、技术的整体发展具有基础性的作用。 就匹配技术而言，其核心问题是如何从大规模的候选集中精准地找到最优质的结果，如用户可能最感兴趣的一系列商品等。当前，大规模匹配、推荐技术的发展，由于受到算力及固有系统架构的局限，往往都是对不同技术方案的拼装或是对系统局部模块的技术升级，而没有从本质上接近匹配技术的终极目标，即如何在全库范围内，使用精准的模型进行打分、排序，进而找到最优的匹配结果。 阿里妈妈精准定向技术团队，面向这一本质问题进行了一些探索，以期能够对业界趋于固化的匹配技术进行新一轮突破，从而进一步推高匹配技术与相应业务的天花板。 面向匹配问题最终目标的技术探索，在具体实现层面面临着诸多挑战。首先，精准的打分模型单次计算量往往都不小。这一问题可以通过算力升级如使用 GPU 推理来解决，实现小规模候选集上可用。其次，全库候选集匹配寻优最大的挑战在于，与候选集规模相对应的计算次数爆炸。当候选集的规模扩展到亿级别时，即使是采用最简单的打分模型，其整体计算量及延时往往也是在线系统不能承受的。 回顾业界的匹配技术发展脉络，大致都是在解决这两个主要的挑战。第一代基于统计的启发式规则方法（代表算法 Item-based Collaborative Filtering, Item-CF），通过离线相似性计算、在线检索候选集限定，解决了整体的效率问题，但匹配结果质量也受到了影响；第二代基于内积模型的向量检索范式，通过内积建模与向量索引实现了高效的全库匹配，但这一范式同时也将打分模型局限在了内积形式上，限制了模型精度的进一步提升。 为了在全库检索的基础上进一步打开模型能力的天花板，2017 年阿里妈妈精准定向广告业务团队在业界率先提出了新一代 任意深度学习 + 树型全库检索算法（Tree-based Deep Model，TDM），在大规模推荐问题上取得了显著的效果提升。TDM 将大规模匹配问题拆解成模型、索引、检索三个模块，提出了树索引中的兴趣建模及检索范式，首次实现了可以使用任意复杂模型的全库近似最优检索。 TDM 技术体系在发展的过程中，逐渐形成了以 Learning to Retrieve 为核心思想的迭代方法论。围绕着 “如何在索引结构中，通过构造样本来学习一个检索模型，使得基于该模型的检索能够找到最优的匹配结果” 这一目标，整个深度树匹配技术的发展大致经历了如下图所示的三个阶段： TDM 1.0 的诞生，有着一个明确的目标，即“如何突破向量检索模式的限制，使得任意复杂的深度学习模型，都能够在有限的资源和 rt 范围内进行近似的全库最优检索”。 围绕这一目标，我们提出了使用树索引结构 + 兴趣最大堆建模来训练检索模型的方案。首先，如下图所示，对于全库商品，我们使用树结构对其进行索引构建，使得商品和树的叶节点形成一一对应关系。然后，为了能够有效地训练检索模型，使其能在树索引中进行精准的检索，我们根据兴趣最大堆建模，将检索目标（目标商品，ITEM6）在树索引中逐层上溯，来得到检索模型在树上各层的训练目标。基于这些目标训练的检索模型，能够在树上通过 Beam Search 来进行有效的近似最优检索。树结构天然的层次性及 Beam Search 提供的有效剪枝，使得模型形式不再受到检索模式和 rt 的限制，可以充分享受兴趣建模技术发展的红利，并提供更精准的召回。 TDM 1.0在 TDM 1.0 的研发过程中，我们发现了在树索引结构的设定下，树结构的质量对检索模型的训练乃至整个召回结果，都有着至关重要的影响。因此，如何通过学习得到高质量的检索结构，是 TDM 2.0 时代想要解决的主要问题。 通过构造同时包含检索模型和检索结构的目标函数，并通过类似 EM 的算法来进行联合学习，TDM 2.0 实现了统一目标下的模型、索引联合学习（Joint Optimization of Tree-based Index and Deep Model, JTM），取得了推荐效果的进一步提升。在公开数据及上的实验表明，基于 JTM 算法的树检索召回，在召回率指标上甚至比相同复杂度模型直接进行全库排序要更优。 深度树匹配技术体系，通过将大规模匹配问题拆解成模型、索引、检索三者，首次实现了任意复杂模型的全库近似最优检索。阿里妈妈技术团队对这一技术体系进行了进一步的透视，发现除了模型和树索引的联合学习之外，对检索过程的联合同样有潜在的空间。基于这一出发点，最新的研究成果，也即第三代 TDM 技术 BSAT(Beam Search aware Training, BSAT) 提出了一种针对检索过程联合建模的任意目标最优检索技术，相关技术沉淀的论文已被 ICML 2020 会议接收。 论文地址： https://proceedings.icml.cc/static/paper_files/icml/2020/2514-Paper.pdf 接下来让我们对该工作进行详细的解读。 2. 现状及缺陷 TDM 技术体系中，利用基于深度神经网络构造的 打分模型 度量用户 - 商品偏好关系，利用 树结构 建模商品集合中的层次化关系，并基于最大堆性质利用在树节点上的正样本上溯 + 同层随机负采样实现对数时间的计算复杂度；在测试时，TDM 利用在树结构上的 Beam Search 进行局部检索及剪枝，以实现在对数时间内召回商品子集的目的。 相比于限定在一个有限的历史兴趣范畴内推荐的第一代基于统计的启发式规则方法和第二代基于内积模型的向量检索方法，TDM 使得引入更加先进的打分模型（例如带有 Attention 结构的 DIN 模型）在实际应用中变为可能，在多个业务场景也取得了显著的效果提升。 围绕着这一思想，我们基于检索结构的学习做了进一步的技术创新，提出了树结构与检索模型联合优化技术 JTM，使得超大规模候选集的检索结构能够和检索模型，进行统一的建模与学习。 这些技术创新主要围绕着模型及索引两大组件的设计展开，而忽视了检索组件的重要性。Beam Search 作为一个贪心的局部检索方法，在树上检索时，只会保留并扩展打分较高的节点而剪枝打分较低的节点。一旦某些符合匹配目标的商品所对应的树上节点的祖先在某层检索中被剪枝掉，这样一个检索过程就会导致召回商品子集并非最优，我们在此统称这种情况为召回性能恶化。在理想情况下，TDM 应当保证基于其打分模型及树结构的 beam search 不会导致召回性能恶化。 然而，当前 TDM 框架将训练与测试视为两个不同的任务从而忽视了这一点，具体表现为：（1）打分模型的训练目标是估计树上节点用户兴趣概率，而非保证基于该打分的 Beam Search 能够实现召回商品 集合 在实际匹配目标（如召回率）上最优；（2）用于训练的树上节点时通过正样本上溯 + 同层随机负采样产生的，但用于测试的树上节点则是通过基于打分模型输出的 Beam Search 召回的，即训练所用树上节点分布和测试所用节点分布并不匹配。 因此，为了保证面向任意目标的最优检索召回，有必要将 Beam Search 建模至 TDM 的训练之中，搭建一整套“模型 - 索引 - 检索”联合优化的完整理论及实践框架。而实现该目的的第一步，就是针对于面向任意目标的最优检索召回的树模型，在理论上解决如何定义、是否存在、如何训练等一系列问题。 实际上，在探索过程中我们发现，训练阶段与测试阶段的不匹配问题并不仅仅存在于 TDM，而是可以广泛存在于各种树模型，如在大规模多标签文本分类问题中常用的 Probabilistic Label Tree （PLT） 模型等等。因此，我们从这一系列树模型中抽象出其数学本质，统一地回答这一系列关于定义、存在性及训练等理论问题，并提出了可用于实践的训练算法。在离线实验中我们发现，该算法可以在不对打分模型及树结构做任何修改的情况下，极大地提高召回的精度。 2.1 现状 2.2 缺陷：训练 - 测试不匹配问题 表 1: 合成数据实验结果 3. 解决方案 工欲善其事，必先利其器。为了解决因训练 - 检索不匹配导致的树模型召回性能恶化问题，我们首先从检索视角出发，构建了一整套最优树模型的理论框架，包括最优树模型的定义、存在性及训练损失函数等等。基于该理论框架，我们提出了面向 Beam Search 最优的树模型训练算法。 3.1 面向 Beam Search 最优的树模型 校准性的定义在理论上为用于树模型训练的损失函数提供了判定标准：如果损失函数不符合校准性的定义，即便是在训练数据无穷的理想情况下，训练得到的树模型也不可能达到零 regret，也就不可能是最优树模型。在 2.2 节的合成数据实验中，我们已经给出了一个 TDM 的训练损失函数不服从校准性的例子。由此反例可以判定，从检索的角度上看，由于训练损失函数的问题，TDM 及 PLT 均非理论最优。 3.2 最优树模型训练算法 图 1: 不同树上节点标签定义方式与 Beam Search 召回节点对比。 最后，相应的训练算法如下所示： 4. 实验 4.1 实验设置 我们使用了 Amazon Books 和 UserBehavior 两个大型公开数据集来进行实验验证。Amazon Books 是用户在 Amazon 上的行为记录，我们选择了其中最大的 Books 这一子类目。UserBehavior 为淘宝全网行为子集，能在一定程度上对应线上真实效果。数据集的规模如下： 4.2 实验结果 实验结果如下图所示，可以看到，OTM 的召回性能比其他方法都要好。相比于之前最优的 JTM，OTM 在 Amazon Books 及 UserBehavior 数据集上分别取得了 29.8%及 6.3%的相对 recall 提升。通过比较 OTM 及 OTM (-OptEst) 可以看到，OTM 性能提升主要来源于基于 Beam Search 生成用于训练的树上节点。 表 2: Amazon Books 及 UserBehavior 数据集实验结果 5. 总结与展望 从面向检索最优的角度出发，在理论层面，我们对于最优树模型的定义、存在性及训练算法等问题做出了解答，构建了一整套泛用的理论框架，是对 TDM 技术体系的一次重大革新；在实践层面，我们提出了 OTM 这一有理论保障的训练算法，在离线实验中验证了该算法相比于其他算法在召回质量上的优势。 从 Matching 阶段的技术需求上看，我们通过理论及实验证实了将检索组件引入模型训练中能够极大地提升召回性能，并从理论上阐述了面向任意目标进行最优集合召回的方案，这是迈向“模型 - 索引 - 检索”三大组件联合优化的重要一步。 未来，我们希望能够深化三者的联系，进一步推动该方向的发展，例如：将目前固定的无参数的 Beam Search 检索组件升级为可以 end-to-end 训练的参数化检索组件；将检索组件引入打分模型及树结构的联合训练等等方向，都有巨大的潜在价值等待挖掘。 你也「在看」吗？?? 阅读原文