阿里妈妈深度树检索技术（TDM）及应用框架的探

分享嘉宾：何杰阿里妈妈高级算法专家
编辑整理：孙锴
内容来源：DataFun AI Talk
出品社区：DataFun

导读： 阿里妈妈是阿里巴巴集团旗下数字营销的大中台，2018 年广告营收超过 1500 亿，近乎占据中国广告市场收入的半壁江山。如何驱动这艘商业航母不断前行，阿里妈妈技术团队始终坚持技术创新驱动业务增长的战略，而 TDM 正是在这一战略指导下，由阿里妈妈精准定向广告算法团队自主研究、设计、应用从而创造巨大商业价值的创新算法典型代表。

今天的主要内容分为四个部分：

1. 从互联网推荐业务看检索技术发展现状

2. 深度树检索 (TDM) 的设计原理和具体实现

3. 深度树检索技术对于线上业务场景的适配应用

4. 我们对下一代检索技术未来发展的思考

▌从互联网推荐业务看检索技术发展现状

检索技术，是互联网推荐、搜索、广告的通用底层技术组成。

一提到检索技术，大家首先会想到搜索引擎，但是从另外一个视角来看，搜索、推荐、广告实际上是一脉相承的，他们的检索可以 ** 统一定义为：**** 从全量的物品里面，挑选出来用户感兴趣的物品。** 不同的是，搜索中 Query 词显式表达了用户意图，而在推荐中往往利用的是用户隐式表达如历史行为、用户属性等，而广告则是在搜索 / 推荐上进一步施加了广告出价的影响。

我们认为检索技术的发展是数据、算力、算法相辅相成，协同作用的结果，具体表现为：

最初，数据少所以候选 Items 规模比较小，用很小的算力和简单的算法，就可以一步到位（如全量过一遍候选）计算出来用户感兴趣的 Items 是什么；

然而，数据在不断膨胀，尤其是随着近些年移动互联网的发展和移动设备的普及，使得我们的数据开始呈现爆炸式的增长，从而导致我们的候选 Items 规模也大幅增大，一步到位或者说原来的检索方式已经无法支撑这种量级的数据。

怎么办？在如此大规模数据下，算力和算法如何适应性设计呢？我们首先来看一下算力的发展，在十几年前我们的算力主要还是以 CPU 通用计算为主的算力体系，算力相对比较有限。大数据 + 有限算力，就要求我们对算法进行适应性设计，于是 Match+Rank 分段漏斗的算法架构被引入：从超大规模候选集中，先 Match 出小规模候选集，再通过 Rank 的方式排序出最终用户最感兴趣的 Items。逐渐地，Match+Rank 的模式成为了如今检索体系的主流架构。

数据在发展，算力体系也在发展，尤其是随着近十年来 GPU 大规模应用的兴起，形成了 CPU+GPU 异构计算的算力大融合。在大数据 + 大算力的现状下，我们开始思考，检索算法架构是不是可以再升级？类似于历史中的“合久必分，分久必合”：我们是不是可以突破 Match+Rank 的分段漏斗模式，将检索问题作为一个端到端整体去设计和联合优化？这就是我们今天要探讨和思考的问题，也是 TDM 的由来。

我们怎么来思考检索架构升级呢？首先需要对检索本身进行深入分析，而作为检索的第一阶段，我们先从 Match 入手。Match 的核心任务是从全量的超大规模的候选集中高效的检索相关 TopK，然后交给后链路比如 Rank 做进一步处理。比如在电商场景，我们有大规模商品库，大概是十亿量级，我们会做 Match 召回千到万级别的 TopK，送给后链路做 Rank。

类似于受算力局限下检索 Match+Rank 两阶段的设计，Match 本身也受到算力局限的影响，所以它的经典实现也是两段式的，比如：

搜索场景下，两段式的表现，就是 User 到 Query-rewrite，Query-rewrite 到 Doc；
推荐场景下，两段式的表现，就是 User 到 Interest-tag（如品牌），Interest-tag 到 Item。

这里存在的问题是两段式相互隔离，比如我们对 User 到 Query-rewrite 进行优化形成各种匹配算法，然后对 Query-rewrite 到 Doc 优化形成倒排索引。这种两段式缺少联合优化，并且受限于线上性能影响，两段式的各个阶段的标签数量是有截断的，效果（如全量发现能力）上就存在局限。

Match 两段式的经典实现如图中 Item-CF 所示，这里不做过多论述。如前述说的，它的优势是模型比较简单，实现成本较低，劣势是两段式无法联合优化，各阶段的标签截断导致效果受限。由此，我们自然会想到一个问题：两段式有缺陷，那我们是否可以改为一段式？

答案是肯定的，那么一段式要怎么做？

在推荐和相关领域，简单的一段式全库检索的经典代表，其实借鉴了图像检索的算法，即：内积模型的向量检索。它通过各种方式学到了 Item 的 Embedding，然后通过 PQ 方式构建分库索引，检索时实时计算 User Embedding，做最近邻 TopK Item 检索。内积模型向量检索在 Facebook 17 年开源了 FAISS 库后，得到了广泛的应用。这种一段式全库检索，在发现能力上具有一定优势，但缺点是模型比较简单，能力有限。这里以 PCTR 预估为例，内积模式的 DQM、Attention 的 DIN、Attention+GRU 的 DIEN 做比较来看，内积模式的 AUC 是最低的，间接证明了内积模型是存在能力局限的。

另外，这种模式下索引构建和模型优化的目标存在不一致。积量化索引的优化目标是最小化近似误差，而向量检索（召回问题）的优化目标是最大化 TopK 召回率。所以由于两者优化的目标不一致，这会导致最终效果并不是最优的。

我们总结一下 Match 中检索技术的发展历程，不难发现，检索技术是模型能力和索引效能的融合：

基于商品的协同过滤（Item-CF），模型能力：启发式统计规则，没有学习成分；索引效能：分离两段式；问题：非学习模型，非面向全库索引；
内积模型向量检索，模型能力：内积模型；索引效能：全库一段式；问题：内积模型相对简单（问题：为什么是内积而不能是其他更复杂的模型如 DNN？留给读者思考）；索引和目标之间没有联合优化。

那么面对这样的现状，下一代模型，我们要如何发展？答案是：更先进的模型、更先进（高效）的索引。

**▌**** 深度树检索 (TDM ) 的设计原理和具体实现 **

应用先进模型，我们自然想到了深度学习模型，但它的引入会带来额外的问题：

① 深度学习的单点计算消耗 T 较大，在性能有界的情况下，我们的计算次数 N 不能过大；

② 要实现面向全库的检索，N 越大越好（最大时即为候选集 size），在性能有界的情况下，与上述 ① 产生了矛盾；

如何解决这一矛盾？还是“检索技术 = 模型能力 + 索引效能”，也即模型的升级需要索引结构的升级来适配，于是我们的核心任务变为：建立一个高效的索引结构来承载先进的模型能力。高效索引有很多，散列表、图等都有一些弊端，最终我们选择了树这一层次结构（如图所示）。

以十亿商品为例我们可以构建一棵 30 层的树，检索 Top1 我们只需要计算 30 次。

基于以上这些考量，我们提出了 Tree-based Deep Match（TDM）这个算法，具体我们需要进一步解决以下四个问题：

① 如何基于树实现高效检索?

② 如何做兴趣建模保证树检索有效性?

③ 如何学习兴趣模型?

④ 如何构建和优化树索引结构?

接下来，我们会以淘宝的商品推荐为例，做一个关于 TDM 设计和实现的详细介绍，来帮助大家理解。

如何做高效检索？不失一般性，假定我们的树是一棵完全二叉树，全部叶子节点代表全部商品，中间节点代表某种意义上的粗粒度聚合（例如“iPhone”是商品，作为叶子，“手机”是该商品的类别，作为父节点；但是这里需要说明，在通常的 TDM 树中，我们并不要求中间节点一定存在具体物理意义）。

树上如何做高效检索呢？我们采用了 BeamSearch 这种方式，自顶向下，做快速剪枝。

BeamSearch 检索方式如图中右侧流程所示：假设要寻找最优 Top2 个 Item，第一层有两个子节点，打分排序选出 Top2（只有 2 个，全取）；扩展出第二层四个子节点，打分排序选出 Top2；扩展出第三层四个子节点，打分排序选出 Top2，达到叶子层，最终返回 Top2 个 Items，查找复杂度为 O(2Klog2N)，K 为返回个数，N 为叶子个数。

衍生问题：为什么该检索策略检索出来的 Top2，一定会是用户感兴趣的 Top2 呢？即 BeamSearch 的有效性要如何保证？

有效的检索背后蕴藏了有效的兴趣建模，也即，要如何建模，使得 BeamSearch 检索有效。

为此我们提出了兴趣最大堆树的概念：用户对 n 节点兴趣的偏好，是用户对 n 节点的孩子节点们的兴趣偏好，取 max 后，在 n 所在的节点层做归一化。如图中右侧树所示，SN4 的兴趣偏好：

PSN4=normalization(LayerSN, max(PItem7, PItem8))

在这样的假设下，有个很好的性质：最大堆树下，当前层最优 TopK 节点的父亲，一定属于上一层的最优 TopK。

以右图举例：如果 Item8 和 Item6 是叶子层最优 Top2，那么根据我们之前的描述，SN4 和 SN3 是 SN 层的最优 Top2。

因此，最大堆树的定义是 BeamSearch 有效的充分条件。所以我们可以从根节点递归向下，逐层挑选 TopK，然后扩展至叶子层。

我们如何学习最大堆树的模型？BeamSearch 检索本质上要求具备对每一层进行 TopK 排序的能力。我们的做法是：构建符合这样性质的样本，让样本牵引模型学习，去逼近最大堆。

具体思路：

叶子层的节点兴趣比较容易构建，因为用户对叶子层的节点是有行为产生的，有行为 / 没有行为对应感兴趣 / 不感兴趣，以此来构建序标签；中间节点，用最大堆递归上述的方式去推导每一层的序标签；当我们有了每一层的序标签，就可以用深度学习去拟合序标签的样本

在实际操作中，我们没有用序样本去构建序模型，而是把序估计还原成点估计，此处可以理解为把排序模型转换成分类模型。

有了分类样本之后，就可以让模型去拟合，牵引模型学习逼近最大堆性质。

采样方案：

我们认为绿色代表正样本，红色代表负样本，如果用户对 Item6 节点有访问，那我们认为用户对 Item6 节点是一个正兴趣，我们在当前的叶子层做随机的负采样，那么上一层怎么做呢？正样本上溯路径的祖先仍然为正样本，然后每一层再做负采样，所以这样就固定出来每一层的正负样本，这样整个树的样本都已经固定完毕。

有了正负样本，我们就可以用任意复杂模型去拟合 label。可以看到这样模式的优点：

我们刚刚一直在提要用先进模型或者深度模型，这里发现最大堆树的训练模式和检索阶段的效率保证了可以基于在线检索的性能约束（上界）来决定可以用多复杂的模型达到最高的检索效果。

上图为具体的模型结构，可以看到：

先进模型网络结构：采用以 Attention 为核心的多层深度神经网络，实现对多峰兴趣的强大判别，F1（Precision 和 Recall 的调和平均数）提升了 16%。
时空兼顾特征表征：以序列化建模用户特征的时序表达，对时序特征进行树上溯（Hierarchical Representation）实现用户特征的层上空间归约，F1 又提升了 18%。

树结构在 TDM 算法中所扮演的关键角色：树不仅决定了检索的索引结构，更是决定了用于模型学习的样本分布，所以树结构的“好坏”直接决定了最大堆树模型学习的效果上界。

不失一般性**，** 假定我们的树仍为完全二叉树，叶子节点为 n 个，那树的本质其实就是如何将 n 个商品一一投射到 n 个叶子上去，也即树的形式化定义是找个一个 π 映射实现 n 对 n 的二部完美映射。那怎么样的树是好的树呢？也即何种 π 映射是最优的呢？从左下图可以看出来，右侧的树结构更优，因为它隐含了性别分类，可以使得 TDM 模型学习得更好（上限更高）。

为了达到模型和树的联合最优化，我们建立了统一的全局经验损失函数（如右上公式），并通过交替迭代的方式进行模型参数 θ 和映射函数 π 的联合优化。其中 π 的优化是一个带权二部图的最大匹配问题，复杂度比较高（O(n^3)），为此我们建立了右下的贪心近似算法（Algorithm2）来优化 π。最终的效果是这种联合优化让 F1 提升近 10%。

PS：这里有现场同学提问

Q：前几页的最大堆树学习里有正负采样，为什么“统一的全局经验损失函数”里面没有负样本项了？

A：为了实现统一 Loss，我们这里对 TDM 模型进行了建模变换，从之前的二分类转换到了多分类，即将层上用户兴趣建模成用户对当前层上的全部树节点做多分类问题。上述统一 Loss 即为多分类建模下的标准交叉熵 Loss，其中的 p 为归一化概率。在实际实现方式上，我们采用了负采样 + NCE 的方法来近似多分类 Softmax。所以上述统一 Loss 里面确实没有了负样本项，“负样本”是以 NCE 方法中的负采样方式表现了。

TDM 在 AmazonBooks 和 TaobaoUserBehavior 两个公开数据集上进行了测试。相对于基线的 ItemCF 和 Youtube 内积模型，TDM 的提升非常显著。我们也对 TDM 各种优化做了单项拆分分析，Attention、HierarchicalRep. 和联合学习的效果如之前所说，其中三者的联合效果达到了 1+1+1>3。

回到最初的图中，我们再次发现：检索技术是模型能力和索引效能的融合。

从这个角度，大家思考一下，TDM 为什么可以解决这个融合呢？我们实现了对更先进模型，即深度学习模型的融合；其次，我们实现了更先进索引，采用了树结构来做索引，有别于常用的倒排索引，并且我们的树结构是一个与模型适配且联合学习的树。

总结一下 TDM 提出、设计和实现的脉络：

目标：解决从超大规模全量商品库中高效检索 TopK 商品的问题
思考：希望由先进模型带来性能 / 效果的提升；为赋能先进模型，需要高效索引；由此产生最大堆树的理论建模
探索：基于最大堆树，我们链接了 BeamSearch 检索下深度学习模型和高效树索引联合学习的方式，形成了基于学习树的全库索引的检索框架。

▌深度树检索技术对于线上业务场景的适配应用****

原生 TDM 是兴趣最优的检索方案，但是在实际业务中，有些业务目标不一定是兴趣最优。例如在广告业务中，我们要考虑 ECPM 最优。那么，我们要如何改造 TDM，使得其可以满足不同的业务目标？

这里面有如下挑战：

算法要从理论上进行升级适配，使得最大堆树的建模适配业务指标；检索也需要改造，在整体链路的设计上要考虑多目标融合，使得检索体系可以支持多个业务目标
此外，克服性能瓶颈，实现检索功能的真正在线应用，也需要一段路要走。

“兴趣最大堆”改造成“任意指标最大堆”的过程中，也存在一些问题，比如：“兴趣”是二值问题，即感兴趣 / 不感兴趣，可以抽象成分类问题；而在广告中，“ECPM”是一个连续问题，即 ECPM 是一个连续的数字，更适合抽象成回归问题。基于这个现状，我们需要思考，如何构建这样的 TDM 模型。

仍然以广告为例：由于叶子层是每一个具体的 Item，那么这些 Item 的 ECPM 是可以计算的（由于 ECPM=PCTRBID1000，我们可以通过其他的模型计算 Item 的 PCTR，BID 通过查找 / 统计的方式可以得到），所以我们有叶子层的所有 Item 的 ECPM 值。所以我们可以通过 max 上溯的方式，将其引入到我们的最大堆树中来，也即：

PParent1= max(PItem1, PItem2)

上一层的节点值为该节点的孩子节点的最大值，此处不需要归一化。并以此方式递归上溯生成整棵树，并在检索的时候递归往下完成 TopK 检索。

由于一个模型并不能适配所有的场景，满足所有目标（例如：广告业务考虑广告收入的最大化；电商业务考虑电商成交最大化等），因此，我们对检索模型做了另外一个改造，也即：分模型联合检索框架，上层是公共部分，对通用的功能做抽象，下层是业务部分，根据业务现状做设计，两部分实现并行调用。

虽然 TDM 理论上可以支持任意深度模型，但实际应用中，我们仍然需要考虑在线检索 Bound 的约束。在一开始上线之初，TDM 的 RT 增量达到了 60ms，对于阿里妈妈的在线广告链路完全不可用。但通过后续的包括通信、计算、链路等优化，最终 TDM 实现了上线后 RT 增加接近于 0ms 的良好性能。

现阶段 TDM 主要接入了阿里妈妈定向广告的 Match 阶段，包括 Shop/Node/Item 已经全量上线，覆盖了阿里妈妈定向广告主要场景的大部分流量，CTR 和 RPM 的效果提升都达到了两位数。

最后，从学习树全库索引的检索，我们进一步把 TDM 扩展到了通用的业务应用框架。左边纵向为基于学习树全库索引的超大规模检索是如何设计的，右边纵向为如何应用 TDM 到线上业务，包括改造成业务最大堆树，然后面向业务的高性能优化和多层多模型的设计，最后真正应用于实际。

▌我们对下一代检索技术未来发展的思考****

对于未来，我们希望将创新推向一个新的高度，当然这只靠我们一个团队是很难做到的。结合当前 TDM 在阿里妈妈的应用，我们希望能在下一个阶段，可以将 TDM 与现有技术做更深层的融合，比如在图检索、搜索业务等领域上面做一些优化和探索。

我们也一直坚持开放、开源的态度。TDM 的离线训练、在线预测的代码已经在 github 开源：

离线训练：

https://github.com/alibaba/x-deeplearning/wiki/ 深度树匹配模型 (TDM)

在线 Serving：

https://github.com/alibaba/x-deeplearning/wiki/TDMServing

我们也正在集团内部推动 TDM 一站式服务化平台的建设，第一阶段实现 DIMO（Data In, Model Out），第二阶段实现 DISO（Data In, Service Out），以期未来可以实现：算法工程师提供场景内行为数据，我们可以自动化构建 TDM 模型；算法工程师将 TDM 模型提交至云端，在线服务就可以自动加载运行，实现 TopK 检索。

TDM 也还在继续创新过程中，包括：

技术方面：实现千人千树、图空间增强、检索最优化；
业务方面：可解释性，基于树结构的广告白盒透出等；
生态建设：学术上正在承办 CIKM2019 比赛，工业上会持续开放、开源，加强云端建设能力。

“合久必分，分久必合”，受限于数据发展的爆炸式增长，和计算性能的限制，两段式 Match+Rank 统治了检索架构的主流，但在大数据 + 大算力的大环境下，我们需要对算法做出改变，为此 TDM 突破了原有的架构约束，做出了部分创新工作，实现了端到端联合优化的一体化检索框架。

当前的 TDM 不管是技术创新还是业务应用还处在发展初期，我们相信随着技术和业务的持续创新，TDM 未来有望发展成为一个面向搜索、推荐、广告业务领域的通用的底层框架。我们也非常欢迎各位可以一起来探讨、应用和改造 TDM 技术，实现更优的检索效果，取得更大的业务成果！今天的分享就到这里，谢谢大家。

关于 TDM 大家有问题可以通过 DataFun 联系到本次 TDM 技术分享人何杰（花名：壶源），也可以直接发邮件到 jay.hj@alibaba-inc.com。同时，阿里妈妈精准定向广告算法团队也欢迎各位志士仁人加盟（校招 / 社招持续进行和开放中），简历发送，同上述邮箱 **^^**

嘉宾介绍

何杰，花名壶源，阿里妈妈定向广告算法核心成员，商品 / 广告推荐算法匹配 (Matching) 方向负责人，阿里原创的基于树全库索引的全新一代大规模检索技术 (Tree-based Deep Match，TDM) 项目 PM，推动阿里巴巴定向广告新一代广告推荐匹配技术体系演进，在定向广告业务的实际应用中取得了显著的效果提升。