文章作者：日涉、卓立、谨持
内容来源：阿里妈妈技术
导读：随着整个互联网行业的发展，各大互联网公司作为服务提供商，积累了越来越多能够服务用户的优质内容，如电商领域的各类商品、视频领域丰富的视频、直播等。而随着信息量的爆炸，算法技术作为连接内容和用户的桥梁，在服务质量的提升上发挥着至关重要的作用。随着业界在搜索、推荐、广告技术上多年的迭代积累，逐步形成了较为稳定的召回（匹配）、粗排、精排这一多阶段的系统架构，而召回模块及其相关的算法，在各类业务中处于链路最前端，其决定着整体服务质量的天花板。
就召回技术而言，其核心问题是如何从大规模的候选集中，找到一个足够优质且大小有限的子集供后链路做进一步处理。因此，召回阶段与其他模块的本质差异，在于其面对的是极大的全量候选集。业界在解决这一问题的过程中，经历了启发式规则类召回、协同过滤类召回、模型类召回等多个阶段。近年来，随着机器学习，尤其是深度学习技术的发展，学术界及工业界已经全面进入到了model-based召回算法的研究与应用阶段。目前，业界存在两种主流的模型召回解决思路：两段式解决方案和一段式解决方案。其中以向量检索为代表的两段式解决方案将模型结构限定为双塔结构，然后通过高效的大规模内积近邻检索来完成Topk查询。其主要问题是模型能力受到了较强的限制，因此模型能力天花板受限。为了突破模型结构的束缚，一些同时建模索引结构与模型的一段式召回方案被提出，其中以我们阿里妈妈展示广告团队此前提出的TDM系列算法为代表，通过显式建模索引结构来提供高效的剪枝能力，减少在线打分量进而承载复杂模型，打开了召回精度的天花板。在持续的大规模召回算法探索与迭代过程中，我们逐渐发现，类似TDM的一段式解决方案，在具备高精度召回能力的同时，由于索引结构与模型训练的强耦合，导致离在线链路过于厚重，对维护、迭代以及快速的业务支持带来了比较大的挑战。因此在年，我们一直在思考的一个主题是：有没有一种更进一步的召回解决方案，能在支持复杂模型的同时，实现对模型训练与索引结构学习的解耦。基于这一理念，我们研发了二向箔算法体系，在保留复杂模型召回能力的同时，将索引学习和模型训练解耦，提供了轻量化的任意复杂模型召回解决方案。二向箔算法体系已在阿里妈妈展示广告业务中全量上线应用，成功支持了双十一大促，相关算法升级带来了信息流核心商业化场景RPM+3.1%/CTR+2.4%的业务效果提升。01模型召回的形式化目标及主流解法1.模型召回的形式化目标召回模型技术由于其应用模式，天生具备“集合属性”，即在单纯的“预估”概念之上，还需要更进一步地基于预估结果从全量候选集中拿到优质子集。首先给召回模型技术的目标做一个简单的形式化定义：假定函数为一个针对用户
和候选项
的价值度量函数，则召回目标可以定义为
其中
为全量候选集。总的来说，这一目标可以概括为：对于每一次请求，从候选集中找到给定价值度量下价值最高的一个子集。当然，在实际的召回系统与算法迭代中，也还存在一些启发式的召回模式如i2i召回，以及对于集合的多样性等指标要求等，本文暂不进行探讨。从上述的召回目标定义中不难发现，召回阶段的模型技术迭代，需要考虑两个重要的问题：1）对于召回模型而言，如何通过更好的网络结构、训练样本或loss设计，使得模型能更好地拟合或者反映真实的价值度量函数，即如何让模型预估
更接近groundtruth的
；2）当训练好的预估模型
给定时，如何得到更精准的
集合，即常规意义上的检索问题。业界的召回模型技术发展，在根据上述召回目标进行优化时，迭代出了两种主流的解决思路。可将其概括为两段式的解决方案和一段式的解决方案，接下来会进行一个简单的介绍。2.两段式解决方案所谓两段式的解决方案，是将目标中的
部分和
训练部分完全分开来考虑，其代表做法是向量检索的模式，即通过特定的模型结构设计，将价值度量函数表达成用户表征向量与候选item向量内积计算的模式，然后通过高效的大规模内积近邻检索来完成Topk查询。针对向量内积的KNN检索，有不少通用高效且成熟的解决方案，如开源的Faiss[1]和阿里内部的Proxima[2]。因此，对于两段式的召回方案，大家迭代的重点一般都聚焦在模型结构、训练样本、损失函数的迭代上，比如：MIND[3]、ComiRec[4]、CurvLearn[5]等优秀的工作，都是在这一框架下往不同的方向做了一些尝试和突破，如用户多兴趣表征、内积之外的相似度量空间等。这类两段式的召回解决方案，由于其对召回问题分阶段的建模思路非常清晰，且各阶段都有相对成熟的工具和方法来支持迭代，因此在实际系统中被广泛使用。但是对于这一类建模方式，在原理上存在两个不足：1）第一阶段向量形式的
模型训练过程中，一般不会考虑第二阶段检索过程的精度损失，因此可能会导致近似近邻检索（ANN）的误差较大，这也是通常所说的两阶段目标不一致的问题。针对这一问题，业界有一些工作已经尝试解决，例如在模型训练阶段就把检索误差纳入考虑[6]等。但是在实际应用中，即使训练阶段不考虑检索误差，一些ANN检索工具如Proxima[2]一般都能将精度做到95%甚至更高。所以在实际应用中两个阶段目标不一致并不算是一个严重的问题；2）由于ANN检索的需求，
模型结构最终需要被设计成用户向量与item向量之间直接计算的模式，而这一要求对模型能力造成了较大的限制。事实上，如果不考虑检索模式对模型结构的要求，召回模型结构设计与后链路的一些模型如点击率、转化率预估模型等，可能并没有太本质的差异，但正是由于向量结构限制的存在，使得召回模型能力的天花板受到了较大限制。虽然目前还没有发现严格的证明与推导，能够论证向量结构到底在多大程度上影响了模型能力，但很多的实践结果都表明了这一限制切实存在且影响很大。下图中，我们给了一个简单的实验数据验证，来说明模型结构限制对模型能力的影响程度。不难发现，当结构从内积升级成带targetattention的DIN结构后，模型精度有了一个大的提升。3.一段式解决方案鉴于两段式解法存在的目标不一致、模型结构受限的问题，业界在技术迭代的过程中，也发展出了一段式的召回解决方案，其中代表性的工作为我们团队之前提出的TDM系列算法[7-9]和字节跳动提出的DeepRetrieval算法[10]。所谓的“一段式”，是相较两段式的价值度量模型训练、Topk检索分开考虑而言，直接面向检索目标来同时学习索引结构和检索模型。这类方法一个比较大的特点是需要定义“参数化的索引结构”，并在训练中和模型进行同步优化。像TDM中的树结构、DR中的多层编码结构，以及索引结构中虚拟节点的embedding，都属于索引结构参数的一部分。此外，在TDM、DR中，item与树的叶节点、与最底层编码节点之间的挂载关系映射函数，同样属于索引结构参数的一部分，是需要通过训练过程来优化的。正是由于索引结构与模型联合优化的模式存在，这类一段式解决方案通常不存在两阶段目标不一致的问题。同时，显式建模的检索过程往往能实现高效的候选集剪枝，所以可以使用计算力要求更高的复杂模型结构，而不局限于向量计算的模式。一段式的解决方案同时解决了两段式中存在的两阶段目标不一致、模型结构受限两大问题，但在长期实践过程中，也发现了这一方式存在的不足，主要也是有两点：
1）索引结构与模型联合训练，从原理上实现了对召回目标的end-to-end一致优化，但是也给训练带来了额外的系统、时间成本。在TDM和DR中，都是通过EM算法来交替优化索引结构、检索模型，最终实现索引和模型的共同收敛，这一过程通常需要过多轮训练，相比两段式方案中的模型训练及训练后的一次性索引构建而言，一般会需要更多的时间。此外，在训练引擎中实现索引结构训练算法，并同时考虑新增item在索引中的引入问题，会带来不少额外的工程成本；
2）模型结构不再局限于内积形式，是一段式解决方案在召回精度上最大的优势，但是实际上对模型结构依然有一些要求。由于索引结构中间节点是虚拟节点，因此不能方便地使用一些在向量模型中普遍应用的目标item侧的sideinformation特征，如淘内的商品类目属性、店铺属性、title等，而这类特征通常在实践中被证明是非常有效的。虽然在实际工程应用中，依然有一些办法能利用上这类特征，如进行top特征上溯等，但同时也意味着额外的系统复杂性。02二向箔算法体系1.为什么叫二向箔二向箔是科幻小说《三体》中的一种降维打击武器，能将空间结构从三维压缩成二维。将上述两种召回解法和维度做一个简单类比：对于基于向量的两段式解决方案，由于检索范式比较固定，因此大家在迭代的过程中主要考虑的是如何在向量结构的框架下，去迭代模型能力，近似于在一维空间中做优化，技术轻量但天花板受限；而对于一段式的解决方案，由于显式索引结构和复杂模型的引入，在迭代中通常需要同时将索引学习、模型结构优化、系统可提供算力的约束这三者同时纳入考虑，近似于在三维空间中做优化，效果天花板高但系统过于厚重。在过去的算法迭代中，通过对上述两类方案的长期探索与应用，我们愈发频繁地在思考一个问题：有没有一种更简洁有效的解决方案，能够在保持一段式解决方案中复杂模型召回能力的同时，不需要在训练中考虑索引结构的优化，进而降低整个系统的复杂度并提升迭代效率？这也是“二向箔(DualVectorFoil,DVF)”算法体系名称的由来，我们希望在新的体系下，召回算法可以不受限制地迭代模型，同时只需要考虑系统可提供的算力这一唯一约束。面对这一问题，我们找到了一个可行路径：保留索引的同时，将索引和模型训练解耦，即给定任意召回模型
，通过模型无感知的索引结构构建及相对应的检索能力，来支持高效、高质量的KNN检索，返回模型打分最高的K个结果
。2.Post-training的索引构建为了使模型训练不再依赖于索引，我们选择在模型训练后再构建没有任何虚拟节点的索引。一种很自然的想法是，将TDM树索引构建方式修改为通过层次k-medoids聚类的方式构建，其中叶节点依然为所有item，但中间节点不再是虚拟节点，而是类簇的中心item。但是，这种索引构建方式要求itemembedding有层次化的类簇结构，实际上模型在训练时并没有加入相关约束，因此学出的itemembedding并没有层次化类簇结构。从离线实验结果来看，这种索引构建方案的效果也比较差。
k-mediods层次聚类构建树索引
因此，我们的目光转向了对模型和itemembedding都没有任何约束的图检索。具体来说，我们选用检索精度较高的HNSW检索图[11]来根据所有候选项的embedding构建索引（构建算法见原始论文）。如下图所示，HNSW检索图是一个层次化的图检索结构，第0层包含所有节点，上层节点为下层节点的随机采样，每层采样比固定（如32、64）；每层都是一个近似Delaunay图[12]，图中每个节点都有节点与之相邻，且相邻节点距离相近（如欧式距离）。HNSW层次化图检索结构
3.检索实现检索过程如下，给定打分模型、HNSW检索图
、用户
，从上往下逐层检索(通过SEARCH-LAYER函数)得到每层打分最高的候选项
，作为下一层的检索起始点；最后，将最底层的检索结果中打分最高的
个候选项作为该用户
的最终检索结果。每层的检索算法如下，给定打分模型
、用户
、检索起始点
。使用
记录本层访问过的节点，
记录待拓展近邻的候选集，
动态记录本层检索结果。初始化
、
、
均为检索起始点
。核心检索过程包含多次循环。每次循环中，首先获取候选集
中所有节点的所有未访问过的近邻
，并将
中所有节点设为已访问，然后维护
为旧
和
中打分最高的
个节点，最后更新待拓展近邻的候选集
为
，即
中打分较高的节点集。因此，每层检索共包含
次近邻查询、模型打分和集合交并差操作，这些操作在Tensorflow中可以高效实现。4.模型结构采用的打分模型结构如下图，其主要由以下四部分构成：
用户聚合特征提取：用户聚合特征包含用户性别、nickname等聚合特征。在获取原始embedding后采用transformer提取user侧深度特征。
用户行为序列特征提取：用户行为序列特征与目标target间采用了targetattention的方式进行交互，以获取与目标target最相关的行为特征。该部分模型结构见下图右边，将序列特征中的item和target都通过MLP进行特征提取后，利用ScaledDot-ProductAttention得到最终用户行为序列特征。
Target特征提取：使用多层MLP进一步提取target侧的特征。这是与TDM等一段式召回方案中模型结构区别最大的部分。由于TDM中模型训练与索引强耦合，且索引中存在虚拟中间节点，因此item侧sideinformation特征比较难以直接应用，需要一些类似top特征上溯的机制来支持。在二向箔算法体系对模型结构没有任何限制，因此可以很自然的加入各种item侧特征。
MLP打分：将上述三路深度特征合并后，经由多轮MLP得到最终打分。
二向箔模型结构
03二向箔工程链路1.整体链路从链路设计上，我们将索引与模型两个部分放入模型推理模块中，实现模型推理模块的“featuresin、tokensout”，减少了请求的传输成本，相较之前的链路，通信部分rt减少12ms。从整体链路上看，“featuresin、tokensout”的方式简化了链路，即召回模块只负责特征生成及对返回token的正/倒排查询，将所有打分及检索逻辑在模型推理模块完成。该设计与排序模型的做法是一致的，这种简化的链路设计完全兼容向量ANN检索。与此同时，索引与模型在同一模块进行部署避免了跨模块同步更新时出现系统卡顿或者版本一致性问题的可能。2.在线检索与打分流程①图表示我们利用Tensorflow的不规则张量（raggedtensor）来表示检索图的节点及邻居关系。raggedtensor主要由values和rowsplits两个tensor构成，对应到二向箔的场景，values是flatten了所有节点的邻居节点的集合，同时用rowsplits的下标来表示节点
本身。举例说明：values：[7,8,10,12,15,5,6,3]row_splits：[0,3,6,8]其表示的图关系如下：
②检索如下图所示，在实际运行时，在CPU端进行检索以得到扩展且未曾打分的邻居集合，然后在CPU端gather出对应的embedding，通过PCIe将embedding由host传至device（GPU），在GPU上完成打分，并同样通过PCIe将打分结果从GPU传至CPU，然后进行TopK运算，进而进入下一轮检索。具体实现中，将检索过程归纳为了多个算子，如：setdifference、setunion等。针对原生Tensorflow没有或者性能较差的Op进行了定制化，整个检索过程均由TensorflowOp构成。此外，set相关Op也经历了多轮迭代，最终采用了bitmap来实现了setdifference/setunion相关逻辑，详细的压测数据将会在后文给出。3.打分采用了DNN模型进行打分，该DNN模型由user侧的transfomer、targetattention、多层fc构成。模型结构见3.4节。在打分过程中，target没有实时特征，也没有featuregeneration的过程，而是在离线计算所有target侧embedding，并在host上以tensor的形式缓存。而user侧则接入了实时序列特征来保证兴趣捕捉的实时性。04离在线实验及性能指标对比1.离线实验①实验设置
样本构造：我们采用用户兴趣最大化召回样本进行模型训练和效果测试。正样本包含两部分，一部分是用户在手淘首页猜你喜欢场景点击过的item，另一部分是用户在全网存在收藏、加购、购买行为对应的样本。训练时，一条样本仅包含一个groundtruth，而负样本是从其他用户的groundtruth中带权重随机采样得到。
Recall计算：在测试时，根据离线recall来评估检索效果。由于一条样本只有一个groundtruth，因此recall其实与正样本的命中率等价。在下述离线实验中，采用召回top-item中正样本的命中率作为recall。
训练、测试流程：通过多机多卡同步训练模式对模型进行训练。训练结束后，计算所有item的经过网络变换后的embedding并保存。接着根据保存的embedding构建索引，并基于索引对十万条测试样本进行检索，计算平均top-recall。此外，为了验证索引检索的有效性，还测试了线上不可行的全库打分方案的recall作为对比。
②实验结果内积形式对召回模型能力的限制为了高效进行大规模内积近邻检索，现有两段式解决方案的模型结构被限制为用户向量与item向量之间直接内积计算的向量结构，而这一要求大幅限制了模型表达能力。而在二向箔算法体系下，模型结构没有任何限制，可以和后链路的点击率、转化率预估等任务用相似的模型。上述结果对比了DNN结构和向量结构的离线recall。其中DNN结构为本文采用的模型结构（见第3.4节）；多兴趣向量结构与DNN结构拥有相同的特征输入，同时采用transformer来提取用户的多峰兴趣向量（参考