2020.10.13 最近召回技术的发展趋势

type

Post

status

Published

date

Oct 13, 2020

slug

2020.10.13 最近召回技术的发展趋势

summary

2020.10.13 最近召回技术的发展趋势

1. 召回技术的发展历程

关于召回技术的发展大体可以分为 4 个阶段：

1.1 第一代召回技术

第一代以启发式规则为代表，大体可分为基于用户的协同过滤、基于物品的协同过滤，基于模型的协同过滤（比如 MF 矩阵分解等），以基于 item 的协同过滤思想为例，根据两个item 被同时点击的频率来计算这两个 item 之间的相似度，然后推荐用户历史行为中各个 item的相似相关 item。这一类方法的优点是简单、性能较高，因此在实际的推荐场景中用途十分广泛，缺点是不能面向全量商品库来做检索，系统只能在用户历史行为过的商品里面找到侯选的相似商品来做召回，并且难以结合候选 item 的 Side Information（比如 brand，品类一些 id 信息），使得整个推荐结果的多样性差、对长尾商品的效果差，容易导致推荐系统出现“越推越窄”的问题，即系统总是给你推荐看过的或者买过的商品。

1.2 第二代召回技术

第二代基于内积模型的向量检索方案，比如 YouTube-DNN 召回模型。通过离线学习 item 的 embedding 向量，然后通过积量化的方式构建索引，在线上应用的时候，实时计算 user embedding，在索引中查找最近邻（比较 user emb 和 item emb 的乘积）的 K 个 item 作为推荐候选。这类方法的核心思想是将用户和商品用向量表示，用向量内积大小度量兴趣，借助向量索引实现大规模全量检索。但是这个方法不太方便去学习用户和 item 之间的特征交叉关系，使整个模型能力的表达能力受限。

1.2.1 单 embedding 向量召回

每个 user 和 item 在一个时刻只用一个 embedding 向量去表示，其主要思想为：将 user 和 item 通过 DNN 映射到同一个低维度向量空间中。线上通过 userId 找到相应的 user embedding，然后使用 KNN 方法（比如 faiss）找到相似度最高的 top-N 条候选结果返回。比较经典的是双塔模型，模型两侧分别对 user 和 item 特征通过 DNN 输出向量，并在最后一层计算二个输出向量的内积。

这一类方法中，除了经典的双塔模型（思想可追溯到 2013 年微软发布的 DSSM 模型），还有一些基于 Graph Embedding 的方案：

阿里的 Graph Embedding with Side information，针对那些出现次数很少或者从来没在序列中出现过的 item embedding 无法精确的表征的问题，通过添加side information（比如商品的种类、品牌、店铺 id 等）等辅助类信息来缓解。

GraphSAGE：Inductive representation learning on large graphs，经典的图卷积神经网络 GCN 有一个缺点：需要把所有节点都参与训练才能得到 node 的 embedding，无法快速得到新 node 的 embedding。这是因为添加一个新的 node，意味着许多与之相关的节点的表示都应该调整。所以新的 graph 图会发生很大的变化，要想得到新的 node 的表示，需要对新的graph 重新训练，因此 GraphSAGE 的基本思想就是学习一个 node 节点的信息是怎么通过其邻居节点的特征聚合而来的。

1.2.2 多 embedding 向量召回

只用一个 embedding 向量来表示用户的兴趣其表征能力是远远不够的。所以需要通过一种模型来建模出用户多个 embedding 的表示。阿里提出的 Multi-Interest Network with Dynamic Routing (MIND) 模型，通过引入 capsule network 的思想来解决输出多个向量 embedding 的问题，在线计算用户的多个兴趣向量后，每个兴趣向量 embedding 通过 KNN 检索得到最相似的 Top-N 候选商品集合。

1.3 第三代召回技术

大规模召回匹配问题可以拆解成模型、索引、检索三个模块，在第二代技术中，主要是围绕向量检索，模型主流是双塔模型，索引是向量索引结构，检索使用内积方式，这种方式存在固有的缺陷，因此第三代技术主要是从这三个角度进行升级，允许任意模型而非限定的内积形式，且能够对全库进行更好的检索（比如索引结构升级为阿里的树结构或者字节的矩阵结构，检索方式也随着索引结构而升级）。目前阿里提出的深度树匹配以及字节提出的 DR 方案，就是从这个视角出发做的技术探索，下面会有详细的介绍。

1.4 第四代召回技术

再下一代召回技术优化方向将是全链路的联动优化，从算法链路视角看，用户得到最终的结果经历了召回、Rank 和最后的策略，前三代召回技术都是独立在优化召回结果，从孤立的优化，到协同 Rank 一起联动的优化，可能是第四代召回技术接下来的一个发展的方向，目前百度提出的“莫比乌斯”召回系统和阿里基于 ECPM 的 TDM 召回已经逐步有这种思想的雏形了。

2. 召回的重点问题

2020 年 Facebook 最新论文《Embedding-based Retrieval in Facebook Search》（EBR）针对向量化召回，介绍得非常全面，涵盖了从样本筛选、特征工程、模型设计、离线评估、在线 Serving 的全流程。总结起来召回的几个主要问题：

（1） 正样本怎么筛选：选择点击样本，还是选择曝光样本，或者曝光未点击样本作为权重低一点的正样本？

（2） 负样本怎么筛选：不能用曝光未点击样本做负样本，需要拿随机采样的样本做负样本,如何采样避免热门 item？热门物料做负样本要过采样，热门物料做正样本要降采样，采样率需要考虑。

（3） 负样本怎么增强：随机采样的负样本里有 easy negative 和 hard negative 之分，如果单纯随机采样，easy negative 主导，模型难以做到细致的区分，需要引入 hard negative，如何引入 hard negative？Airbnb 在《Real-time Personalization using Embeddings for Search Ranking at Airbnb》一文中的做法，就是根据业务逻辑来选取hard negative，百度 Mobius 的作法，用上一版本的召回模型筛选出"没那么相似"的<user,doc> 对，作为额外负样本，训练下一版本召回模型。怎么定义“没那么相似”？facebook 文章中是拿召回位置在 101~500 上的物料。排名太靠前那是正样本，不能用，太靠后，与随机无异，也不能用，所以只能取中段。上一个版本的召回模型作用于哪一个候选集上？facebook 提供了 online 和 offline 两个版本。online 时就是一个 batch 中所有 user 与所有 d+ 的 cross join，这一点就与 Mobius 几乎一模一样了。easy:hard = 100:1

（4） 模型结构如何设计：双塔或者其它任意深度模型？双塔模型没法引入 user-item 的交叉特征，在预估精度上有一定影响。

（5） loss 函数如何设计：Pairwise Hinge Loss=$max(0,margin-<u,d_+>+<u,d_->)$ 还是BPR loss=$log(1+exp(<u,d_->-<u,d_+>))$

（6） 离线评估怎么做：facebook 使用的方法是，拿 Top K 召回结果与用户实际点击做交集，然后计算 precision/recall；Airbnb 所使用的方法是看“用户实际点击”在“召回结果”中的平均位置。但无论是 precision/recall 还是平均位置，和实际线上结果之间还是存在一定 gap。一个置信度高的离线评测手段仍然是召回工作中的痛点。

（7） 全链路优化怎么做：A. 精排是在主力召回算法给出的数据下训练的，已经完全适应主力召回的数据分布，新的召回算法召回的物料如果与主力召回算法给出的物料分布差异较大，往往得不到精排的高分，因此导致新召回算法效果不佳。解决方案1: 将各路召回的打分作为特征，加入到精排训练的过程中。但是，这改变不了新召回是少数派的现实，新召回的打分作为特征在训练样本中的占比有限，发挥的作为也可能有限；解决方案2: 将召回结果交人工审核，发现 bad case，增强下一版本的训练样本。B. 召回层和排序层的目标是不一样的，召回层侧重优化相关性，而排序层侧重优化商业指标 ECPM。

（8） 在线检索如何加速：传统 ANN，阿里树搜索，字节 DR 方案

3. 最近业界的几个方案

从最近几年召回方面相关的文章可以看到，国外的 google 和 facebook 等主要还是在第二代方案上精耕细作，从各个细节深挖效果，发表的文章往往具有工业风（不排除他们已经升级到第三代方案，但对外发表的文章只是总结上一代方案）；而国内各大厂已经在逐步探索第三代的召回框架，其中阿里的 TDM 系列方案似乎已经落地应用，而字节的 DR 方案看上去只是个初步方案，训练需要很多技巧，只是在公开数据集上进行了验证，并没有公布在实际业务中的效果。

方案	检索方式	优化点
2019 百度“莫比乌斯”	第二代，向量检索	将 ctr 模型融合到召回模型里
2018 阿里 TDM1.0	第三代，树检索	允许任意深度模型
2019 阿里 TDM2.0，JTM	第三代，树检索	升级为检索模型和检索结构联合学习
2020 阿里 TDM3.0，BSAT	第三代，树检索	升级为检索模型，检索结构，检索过程联合学习
2020 字节 DR	第三代，矩阵路径检索	从树结构改为矩阵结构

3.1 2019 百度凤巢“莫比乌斯”

KDD 2019: MOBIUS: Towards the Next Generation of Query-Ad Matchingin Baidu’s Sponsored Search, http://research.baidu.com/Public/uploads/5d12eca098d40.pdf

本质上还是属于第二代双塔单 embedding 向量召回方法，针对召回层和排序层的目标是不一致问题（召回层侧重优化相关性，而排序层侧重优化商业指标 ECPM）进行优化，提供了一种思路是把召回层和排序层融合，做成一层（mobius系统），兼顾相关性和商业指标。

1、在召回层保证相关性的同时引入 CTR 业务指标作为召回的依据

2、将以往的 CTR 预估模型融合到召回层中，提出一种全新的多目标商业召回系统架构

流程图：先看绿色线，再看红色线。先构造 query 和 ad 的交叉集，然后找到相关性低的那部分，用双塔模型做点击率预估，再筛选出点击率高的样本做为 badcase，混入原有数据集作为label=badcase的样本。

相比原始点击和未点击样本训练的模型，新模型在 auc 上有一定下降，但相关性有大幅提升。

3.2 2018 阿里 TDM 深度树匹配，TDM 1.0

KDD 2018: Learning Tree-based Deep Model for Recommender Systems, https://arxiv.org/pdf/1801.02294.pdf

TDM 的目的比较明确，就是突破向量检索模式的限制，使得任意复杂的深度学习模型，都能够在有限的资源内进行近似的全库最优检索。召回阶段，系统性能是最大的制约，因为一方面要计算用户对商品的兴趣，需要考虑单点的计算消耗 T，同时要考虑对海量商品库来做检索的过程，因此要考虑计算次数 N 的问题，如果要用深度模型，那单点耗时 T 肯定会上去，因此只有在检索上做优化，为此阿里提出了使用树索引结构+兴趣最大堆建模来训练检索模型的方案：

3.2.1 基于树的在线检索

假设已经得到深度树的情况下，高效检索采用的是 Beam-Search 的方式，只需在每层选出 top k，且在下一层仅计算上一层选出来的节点相应子节点的兴趣，对于规模为 M 的语料库，只需要遍历 2 * k * logM 个分支就可以在完全二叉树中找到 top k 的推荐结果。

3.2.2 训练过程

用户行为根据 timestamp 被划分成不同的时间窗口。在每个时间窗口中，item embeddings 被平均加权，权重来自 activation units。每个时间窗口的 output 沿着候选节点的 embedding，被拼接成神经网络的输入。在经过三个带 PReLU activation 和 batch normalization 的 fully-connected layers之后，使用一个二分类 softmax 来输出用户是否对候选节点感兴趣的概率。每个 item 和它对应的叶子节点共享相同的 embedding，所有embeddings 都是随机初始化的。

训练数据构造过程如上图，给定一个用户和它的状态，目标节点是 n13，n13 的所有祖节点是正样本，这些在每个层级上随机抽取的红色节点，作为负样本。

训练过程是首先固定 TDM 树（最大堆树），训练深度网络得到新的节点向量；然后使用新的向量又可以通过聚类等方法重新构建一个 TDM 树；然后再固定 TDM 树重新训练深度网络，如此迭代优化，最终可以得到一个高性能且稳定的模型。

3.2.3 TDM 工程架构

在线端：对整体的架构做了抽象化的设计，把它拆分成了三个环节：

（1）用户定向服务 user targeting service，负责对用户行为序列、用户特征的基础组织；

（2）深度索引服务 deep searching service，用来做整个树的索引构建和检索的过程；

（3）模型计算服务 model serving，专门支持高效的 GPU 计算。

通过上述三个环节形成高效的在线方案，通过跳层检索，多路并行等方案，在真实广告业务中，从千万量级广告库召回 top2K，整体链路 rt 增长不超过 5%。在淘宝首页 “猜你喜欢” 场景 CTR 提升 2.1%，CPM 提升 6.4%。

离线端：依托阿里开源的 X-Deep Learning 框架，支持千亿级样本 & 十亿级特征的离线训练。目前，TDM 召回技术已经随 X-Deep Learning 框架的开源而开源。

3.3 2019 阿里 JTM 深度树匹配，TDM 2.0

NIPS 2019: Joint Optimization of Tree-based Index and Deep Model for Recommender Systems, https://arxiv.org/pdf/1902.07565.pdf

JTM 是对 TDM 的升级，在 TDM 方案中，模型的优化和树形索引结构的学习的优化目标是独立的，分别按各自的优化目标去优化可能导致最终的结果不是最优的，同时树形索引结构学习的好坏会直接影响最终的检索结果，为了解决这个问题，阿里提出了一种统一目标的模型、索引联合优化的 JTM 算法，通过构造同时包含检索模型和检索结构的目标函数，并通过类似 EM 的算法来进行联合学习，JTM 实现了统一目标下的模型、索引联合学习。

同时，树结构的更新也优化到实时和准实时的更新，比如新闻推荐里，对于实时更新的新鲜事，可以根据一些 sideinfo，找到和当前的新闻相似的新闻，挂载到它们的最相近的父亲节点上，保证初始的召回。有了初始的召回之后，就可以积累数据，有了数据之后，就可以通过实时更新，增量学习的方式，实现整个树型索引和层排序模型的学习，来达成整个树结构的更新。

另外，在做广告召回的时候，除了考虑兴趣最大化召回，还可以考虑收入最大化召回，即最大化 ECPM 召回。由于这个 ECPM 是通过 CTR 和 bid 得到的，它是两个因子的乘积，因此很难根据用户直接对一个商品是否有兴趣这样一个隐式的反馈学习得到。那么对于业务目标的最大化召回，需要改善整个深度树匹配的方案，使得它能够适应业务目标。核心是学习一个 ECPM 最大堆，具体的学习方式是通过构建满足 ECPM 最大堆性质的样本去牵引模型拟合这样的 ECPM 最大堆。可以假设已经得到了从叶子层随机抽取的一些样本，基于一些预估模块和后续的反馈模块可以知道用户对叶子层样本的 ECPM 值。

根据叶子层的 ECPM 样本，可以单独去拟合叶子层的 ECPM 样本，从而得到一个叶子层的 ECPM 预估模型，有了叶子层的模型，就可以在倒数第二层随机取一些节点做样本，如果没有这些样本 ECPM 值就无法去学习，怎么构建这些样本的 ECPM 值呢？根据叶子层的模型再考虑最大堆性质，比如现在采了 SN2 这样一个节点，要构建它的样本，可以通过叶子层的模型预估得到 ITEM3 和 ITEM4 的 ECPM 值，根据最大堆的性质，就能够知道 SN2 的 ECPM 值。这样就生成了倒数第二层的 ECPM 样本，进而就可以构建模型去拟合倒数第二层 ECPM 模型，逐层往上溯，以完成整个 ECPM 最大堆的学习。

3.4 2020 阿里 BSAT 深度树匹配，TDM 3.0

ICML 2020: Learning Optimal Tree Models under Beam Search, https://proceedings.icml.cc/static/paper_files/icml/2020/2514-Paper.pdf

除了模型和树索引的联合学习之外，对检索过程的联合同样有潜在的空间。在上两代 TDM 方案中，Beam Search 作为一个贪心的局部检索方法，在树检索时，只会保留并扩展打分较高的节点而剪枝打分较低的节点。一旦某些符合匹配目标的商品所对应的树上节点的祖先在某层检索中被剪枝掉，这样一个检索过程就会导致召回商品子集并非最优，我们在此统称这种情况为召回性能恶化。在理想情况下，TDM 应当保证基于其打分模型及树结构的 Beam Search 不会导致召回性能恶化。然而，当前 TDM 框架将训练与测试视为两个不同的任务从而忽视了这一点，因此，阿里又在 JTM 技术的基础上提出了一种针对检索过程联合建模的任意模型全库最优检索技术 BSAT。

思想已阐明，欲知细节则可以阅读上文链接中的文章。

3.5 2020 字节 Deep Retrieval

2020: Deep Retrieval: An End-to-End Learnable StructureModel for Large-Scale Recommendations, https://arxiv.org/pdf/2007.07203.pdf

阿里 TDM 系列深度树匹配模型，也有几点问题（个人觉得 DR 论文里提的这两个问题有点故意为了推出 DR 而强行找的问题）：首先，树结构本身很难学习，而且树结构的部分叶子结点可以会因为稀疏数据而导致学习不充分；其次，每个候选 item 只属于一个叶子节点，不符合常理（比如“巧克力”应该可以同时属于食物类和礼物类）。同时这也限制了模型只能从一个角度来刻画候选集，影响了模型的表达。

为此，字节提出了一种端到端的模型训练框架“深度检索” DR，不同于 TDM 用树结构，该模型使用 D*K 维的矩阵来作为索引结构（如下图所示）。每个 Item 都需要走 D 步，每一步有 K 种选择。走到最后会有 K^D 可能的路径（也可以叫做编码），每一条路径可以代表一个包含多个 Item。每个 Item 也可以被这样编码一次或多次，所以 Item 也可以属于多条路径。

3.5.1 基于矩阵的在线检索

假设每一层有三个节点(a,b,c)，Beam Size 为 2，Beam search 搜索过程大致如下：

（1）在第一层时，选择概率最大的 2 个，假设为 a 和 c，那么当前的 2 个路径就是 a 和 c；

（2）到第二层时，我们将当前路径 a 和 c 分别与该层的所有节点进行组合，得到新的 6 个组合 aa ab ac ca cb cc，计算每个组合的得分并选择得分最高 2 个序列，作为新的当前序列，假如为 aa cb；

（3）不断重复（2），直到遇到结束符或者达到最大长度为止。最终输出得分最高的 2 个路径。

预测过程中，为每个 User Embedding 进行搜索从而获取多条候选路径，并将路径下包含的 Items 合并起来作为候选集。在搜索过程中，模型在每一层只保留最好的 B 个节点，所以到最后一层后会获得 B 个路径。故每次推断的时间复杂度为 O(DKBlogB)。

3.5.3 训练过程

由于优化目标同时涉及路径和 Item 之间的映射关系，属于离散型关系，而梯度下降是针对连续型关系的，因此 DR 没有用梯度下降类方法，而是采用 EM 算法进行训练。

E 步，由于实际过程中无法计算出所有可能路径的分数，因此通过 Beam Search 获取较高分数的 top 路径；

M 步，最大化目标函数。

上述算法必须增加防过拟合的正则化项，即对于包含 Item 数目较大的路径进行惩罚，否则容易过拟合，导致某一条路径对于所有输入都可取得最大值。

另外，作者发现加入一个 Softmax 分类模型和 DR 模型进行联合训练可以大大提高性能。即在用上述方法得到候选集后，再用这个 Softmax 分类模型重排一次获得最终的 top 候选集。因此，最终的目标函数是上述模型的目标函数和 Softmax 分类模型之和。这个方法之所以有效，作者推测是由于路径在开始是随机分配的，增大了优化的难度，而通过与一个容易训练的 Softmax 模型共享输入，能够加速模型的优化。