• 李晗

推荐系统已经深入到每个人生活的方方面面，网购、音乐、新闻、视频等等场景中，用户都可以感受到推荐系统带来的便利。随着技术的不断发展，如何更加精准地进行推荐成为了开发人员的头等大事。

为了提升推荐系统的精准度，最大程度解决推荐系统存在的问题，来自阿里妈妈的高级技术专家李晗和团队提出了一种新型的推荐算法名曰：深度树匹配。在 2018 年 AICon 全球人工智能与机器学习技术大会上，李晗公开分享了这一算法，AI 前线也对此内容进行了独家整理。

本文系 AI 前线“推荐系统”专题系列文章之一。

大家好，我叫李晗。来自阿里妈妈，今天非常有幸能够在 AICon 的现场给大家分享一下我们团队做的工作，我演讲的主题是：深度树匹配，下一代推荐技术的探索和实践。

首先介绍一下我个人。

我是 2013 年加入阿里从事广告算法工作，现在在阿里妈妈。阿里妈妈是阿里巴巴里面主要负责广告营收的业务部门，承载了阿里 50% 以上的收入，我们工作主要的职责也是负责广告投放的算法。

我目前在阿里妈妈主要负责三块工作：第一块工作主要是整体信息流广告的算法策略；第二块工作是整体展示广告的匹配召回技术体系的建设；第三块工作是负责云营销业务的数据算法。

今天的演讲我主要分四个方面来讲述：首先我会重点介绍一下推荐问题的技术概要；之后我会从问题出发，讲述一下我们提出的深度树匹配方案；接着，我会讲一下从深度树匹配来看我们认为的下一代推荐技术面临的核心挑战；最后回归到问题本身，来看一下深度树匹配在下一代推荐技术探索过程中的再思考。

推荐问题和技术概要

首先来讲第一部分，推荐问题和技术概要。其实前面已经讲过了，推荐这样一个典型应用贯穿于我们的生活中，无论是新闻、音乐、商品还是视频，各种各样的推荐应用层出不穷。大家其实平时日常上网，经常能够使用到这些推荐产品。

那么这些推荐业务背后的核心技术是什么样的？简单以淘宝的商品为例，做一个简单的技术拆解。

它核心就是根据用户的请求从海量的商品库挑选合适商品最终展示给用户，考虑到系统和算力的限制，大体分为两个环节：第一个我们叫做 召回环节，又叫 匹配环节。从海量的商品库里面得到一个侯选的商品集合，然后再把这个侯选的商品集合通过更精细的预估模型最终在第二个排序环节展示给用户。

我今天讲的主要内容会围绕着匹配召回阶段来讲述我们的方法。

对于推荐召回阶段，因为它面临着从全量商品库里面，高效召回商品的问题，由于存在系统的性能，这里我们就需要在这样一个召回的问题里面重点去解决两个关键问题：

  • 第一，怎么高效检索，即算的快。高效检索意味着需要设计合理的检索结构和检索策略，能够在一个系统可容纳的时间内来保证可以召回足够量的商品，或者足够量的侯选集。

  • 第二，整个召回的过程虽然算得快，但是不能算得太偏了，还是要把用户真正感兴趣的这些商品能够召回回来，就是所谓的算的准。

所以说，围绕高效检索和相关整个推荐技术面临的问题，至少在召回技术层面的话经历了两代技术的发展。

第一代的技术发展是我们大家都很熟悉的，以启发式规则为代表的推荐技术，这里面的典型代表是什么呢？协同滤波，基于商品的协同过滤，它的流程拆分如下：

首先会根据各种各样的行为数据或者文本相似性来计算商品之间的相关关系。然后在线用的时候，获取用户的历史行为，把用户历史行为中的商品作为触发商品，根据相关关系找到和用户历史行为相似的商品，作为侯选集来进行整个召回和推荐。这种方法通过在用户历史行为里面找相似的商品，保证了基础的相关性。与此同时，因为只找相似的商品，所以系统屏蔽了大规模的计算，使整个召回的过程能够高效地完成。

但是这类方法其实存在一个很关键的问题：在召回的时候，并不能真正的面向全量商品库来做检索，系统只能在用户历史行为过的商品里面找到侯选的相似商品来做召回，使得整个推荐结果的多样性和发现性比较差。人们经常会诟病说：为什么点了还推，买了还推，看了还推？

结合这种方法的局限性，研究人员也在尝试用更先进的方法来解决这个问题，问题的核心是什么？就是怎么来做真正的全库检索。推荐技术人员借鉴一些图像检索问题的方案，提出了 基于内积模型的向量检索方案，经典代表就是基于内积的 Youtube 的视频向量推荐方案。

它的具体的方案是什么呢？

通过离线学习 item 的 embedding 向量，然后通过积量化的方式构建索引，在线上应用的时候，实时计算 user embedding，在索引中查找最近邻的 K 个 item 作为推荐候选。这里用户 embedding，和 item embedding 可以通过用户对商品的兴趣建模得到。这类方法的核心思想是将用户和商品用向量表示，用向量内积大小度量兴趣，借助向量索引实现大规模全量检索。

这代技术也是目前推荐召回核心发展的一代技术，我相信有不少公司应该都在上面做了很多的研究，但是现在，我们发现这一代方法存在一些局限性，因为它最终的模式是将用户描述成一个向量，再把商品做一个向量，用它们的内积表达用户对商品的兴趣。做过预估模型的同学都知道，特征组合对模型效果是相当关键的，但在这种方法下，其实不太方便去做用户和商品之间的特征组合关系，使整个模型能力受限。

我们认为这是现在这一代技术的核心问题，它对模型结构做了很大的限制，必须要求是用户向量和商品向量的 embedding 在顶层做内积的模型结构。在深度学习领域其实模型结构层出不穷，百花齐放，但是这样一个特定的结构实际上对模型能力造成了很大的限制。

所以对于这样的问题，我们进行了持续的思考：下一代推荐技术应该怎么去发展？

如果说内积检索相对于启发式规则，它打开的是整个全库检索的天花板，要进一步提高推荐效果，我们就需要打开模型能力的天花板。所以我们在想：能否设计一套全新的推荐算法框架，它允许容纳任意先进的模型而非限定内积形式，并且能够对全量候选集进行更好的推荐。我们今天所讲的方案 深度树匹配，就是从这个视角出发做的技术探索。

深度树匹配：下一代推荐技术的探索

先来思考一下怎么做到全库检索和先进模型。

我们知道整个召回阶段，系统性能是最大的制约，因为一方面要计算用户对商品的兴趣，需要考虑单点的计算消耗 T，同时要考虑对海量商品库来做检索的过程，这里还有个计算次数 N 的问题。

如果我们引入了先进模型，就使得在单点上的消耗不可避免的增大；如果说要把这个先进模型用到全库遍历去计算，对于淘宝这样一个亿级的商品库，要计算一亿次，这个 N 又非常大，使得整体的性能不可行。这就造成我们很难将一些排序预估环节的先进模型用到召回阶段，这样的问题好像不是特别容易解决。那怎么来更深入的去剖析这个问题给出一个解法呢？

我们做了这样一个推演来重新认识这个问题，如果先进模型要在匹配召回阶段应用，核心的单点计算消耗是降不下来的，要使得整个系统可行的话，必须要降低 N，也就是计算次数。那么面向全量的检索，需不需要对全库做遍历计算呢？这个答案其实是不一定的，如果说我们能够设计一个高效的检索结构，使得系统可以对整个商品库里面只做有限次的计算，就近似等价于对全量做了遍历计算，那就可以使先进模型能够在这运用。所以说我们整体的方案围绕的是怎么构建一套高效的索引结构，来承载先进的模型能力。

有了这样一个想法之后，我们下一步来看看应该采用什么样的方法。

面对复杂的问题，我们知道人脑常用的思考模式是什么：是确定大方向之后再细化。我们也尝试从这个角度思考，能否有一个从粗到细的检索模式，它能够逐步判断和细化，最终给出最优推荐。

基于这样的思考，我们把探索的方向就定位在使用层次兴趣树来增加检索效率。例如对一个面向十亿商品库挑 Top 1 的问题，它的计算次数能从遍历的 10 亿次下降到 30 次，我们就认为 OK 了。

有了这样的一个兴趣树之后，实际上只是有了一个大概的探索方向，并没有给出具体的实施。在具体的实施里面仍然要考虑，有如下三个关键性的问题：

  1. 怎么基于树来实现高效的检索；

  2. 怎么在树上面做兴趣建模；

  3. 兴趣树是怎么构建的。

结合这几个问题的解法，我们构建了深度树匹配技术 Tree-based Deep Match（TDM）这一全新的推荐算法框架的内核。

接下来我会把这个解决方案拆开具体讲一下。

BeamSearch

首先讲怎么做高效地检索。我们假定整个树结构的叶子层是具体要推荐的商品，然后从上到下，把兴趣从粗到细构建了一个平衡二叉树。那么要高效的完成 topK 检索，关键点在于自顶向下的过程中能够快速剪枝。因此我们采用 beamsearch，根据用户对每层节点的兴趣挑选 topK，将每层 topK 节点的子节点作为下一层挑选的候选集合逐层展开，直到最终的叶子层。

这个方案大家应该很熟悉，每一层节点中挑选 Top K 节点，比如说第一层要挑选的 Top2 是 LN1 和 LN2，展开的子节点是 SN1 到 SN4，在这个侯选集里挑选 SN2 和 SN3 是它的 Top2，沿着 SN2 和 SN3 它的整个子节点集合是 ITEM3 到 ITEM6，在这样一个子结合里去挑 Top2，最后把 ITEM4 和 ITEM6 挑出来。

通过这样的方式，我们在每一层能够对非 topK 兴趣的节点分支快速剪枝停止搜索。这样 topK 召回总体的计算次数是 2_logN_K ，N 是整个叶子个数，这个数量是一个可控的计算量，使得先进模型能够使用。

但这里大家会产生一个疑问，为什么你能够采用这样的检索策略。？

要知其然，还要知其所以然。我们知道，刚才的分析里面，整个检索策略依赖于用户对树结构上的每个节点的兴趣判别来挑选 TopK，而兴趣判别的依据是来自于它的兴趣建模。因此我们兴趣建模的核心是要能够承载刚才提出来的 Beam Search 检索方案的。

最大堆树

这里我们提出了兴趣最大堆结构。直观上这么来理解：用户对树上的每个节点的兴趣是正比于对这个节点子节点兴趣的最大值。这是一个假设，我们希望能够建立一个模型，满足这样的最大的兴趣。

基于这样的性质，我们来看一下它有什么样的好处？

如果用户对叶子层这么多节点中的 ITEM8 是最感兴趣的，我们就知道，该用户应该对 SN4 的兴趣也是最大的。因为根据最大堆的性质，父节点的兴趣等于子节点兴趣的最大值。同样，我们也可以推导出用户对 LN2 的兴趣应该是最大的。那么在自顶向下检索的时候，我们就可以每层只挑 Top1 节点，沿着 Top1 子节点展开继续检索，保证这样的检索方式能够最终挑选到 Top1 叶子节点。我们在这里提出兴趣最大堆这样建模结构，本质上是来承载高效的检索策略。

接下来就谈到另外一个核心问题：有了这样的兴趣建模方案，模型该怎么进行学习？

我们拥有的数据是用户对具体商品的行为反馈，这可以帮助我们建模用户对叶子节点的兴趣，得到叶子层节点的兴趣序关系。但是如何学习最大堆形式的中间层节点兴趣则是问题的关键点，例如对中间节点 LN1、LN2、SN2 还有 SN3 这样节点的兴趣。最大堆模型给出了用户对中间节点的兴趣模型定义，我们可以从叶子层的兴趣序关系根据最大堆性质推导出树结构上每一层节点的兴趣序关系。然后让深度学习模型分别去拟合每一层的兴趣序关系即可。

具体实践中，我们将每一层兴趣的序关系估计还原成兴趣点估计，然后构建符合满足最大堆概率性质的样本，牵引模型去拟合样本，进而逼近最大堆性质。注意这里我们并没有使用一些结构化正则去约束每一层概率满足最大堆性质，因为我们发现这样的方法求解起来非常困难，所以用样本牵引模型的方式更轻巧的来解决。

那么具体怎么做呢？假设用户对叶子层 ITEM6 这样一个节点是感兴趣的，那么可以认为它的兴趣是 1，同层其他的节点兴趣为 0，从而也就可以认为 ITEM6 的这个节点上述的路径的父节点兴趣都为 1，那么这一层就是 SN3 的兴趣为 1，其他的为 0，这层就是 LN2 的兴趣为 1，其他为 0。

通过这样的样本分布，就可以满足兴趣最大堆的性质，接下来只需要让模型去拟合样本分布就 OK 了。在这里我们总结一下采样方案：从叶子层确定正样本节点，那么就可以沿着正样本上溯确定每一层的正样本，其他的同层采一些负样本，构建用于每一层偏序学习模型的样本。

基于这样的性质，我们来看一下最开始提出的问题：怎么承载先进模型。

因为我们通过整个树的结构和最大堆性质，构建了模型的样本，而真正对于每个模型要学习的时候，它只关心它的模型是否足够拟合样本就可以了。我们在这里就并没有要求模型一定要把用户特征和 item 特征转换为顶层向量内积的形式，而是给模型很大的自由度，只要去拟合好足够的样本，那么任意的模型都是 OK 的。我们的做法使得整个模型结构和检索结构解绑了，进而使得任何模型都可以用在这样一个召回的问题上来，同时结合高效的检索策略，实现召回阶段模型能力的提升。

具体在兴趣模型设计的时候，我们的核心考虑是：怎么让候选的节点和用户特征进行自动的特征组合学习？我们在这里引入了 attention 结构，给用户行为序列设计了不同的时间窗，对用户行为序列做有权重的挑选，来实现对用户多峰兴趣的捕捉。

第三个方面，就是整个树结构是怎么生成的。

假定叶节点对应具体的 item，我们的目标是构建一个好的树结构来优化我们的检索效果。通过前面的分析知道，对于叶子层的样本我们通过用户行为反馈得到，而中间层的样本则通过树结构采样得到。所以树结构决定了我们中间层的样本。

我们从顶向下的检索策略，利用的是我们对每一层节点兴趣建模进行快速剪枝，要保证最终的检索效果，就需要我们每一层的兴趣判别模型能力足够强。由于树结构负责我们中间层的样本生成，所以我们的思路是通过优化树结构影响样本生成进而提升模型能力。具体来说，通过树结构优化降低中间层的样本混淆度，让中间层样本尽可能可分。

所以，整个树结构的生成创建和优化的过程，实际上是围绕着怎么来生成更好的样本、帮助模型学习的视角进行的，而不是只是考虑相似、聚类这样的模式。那么这里的核心方案是什么呢？

考虑到我们的叶子层样本来自于用户行为序列，对于同一个用户，其行为序列中相近的 target item 构成的不同样本。设计树结构让中间层样本样本尽可能可分，具体来说，就是相近的 X 所对应的 Y 的标签也尽可能的相近。在具体的实现上面，相近的 X（即用户行为序列中间的一些抽取的片断）对应的真实的标签 item pair，我们希望它在树上的距离尽可能足够的近，通过这样一种规则来建立树结构，能够使得检索的效果有大幅度的提升。

到这里，我们来对深度树做一个算法总结。

首先我们提出了 BeamSearch 方案来实现对树上面的高效检索；然后提出了兴趣最大堆的兴趣建模的方案，通过生成样本，用样本迁牵引型拟合，去满足这个最大堆性质来做兴趣建模；最后我们通过让树生成尽可能可分的样本去建立树结构，这就是我们整个方案的内核。

讲述到此，听众可能会有这样两个问题：这个方案并不简单，是否给效果带来足够大的提升？同时这么一套复杂的方案，意味着要把排序阶段那么复杂的模型引入到召回阶段，工程能力是否足够的去支持真正在线应用？

为了回答这些问题，我们先分享一下结果。

首先，我们认为这样的技术实际要通过离线和在线的验证。通过离线端我们构造了一个基于淘宝数据的大规模数据集名为：User behaviour，我们在这个数据集上面验证了三代方法的对比，可以看到我们的方法获得了显著的离线效果提升。去年 KDD2018 也收录了我们的论文，大家感兴趣的话，可以看一下相关的论文。

另外，从在线效果来说，我们用这样一套方案，已经承载了整个阿里信息流广告流量 80% 召回工作，同时能够支持对千万量级 AD 的全量检索，核心的业务场景取得了显著效果提升，所以从算法效果是足够有信心的。

从工程实践来说，整个工程架构离不开我们的工程团队强大的支持。在线端：我们对整体的架构做了抽象化的设计，把它拆分成了三个环节：

首先是用户定向服务，叫做 user targeting service，它能够负责对用户行为序列、用户特征的基础组织；其次，我们还构建了 deep searching service，它用来做整个树的索引构建和检索的过程；此外，考虑到在这个过程中要进行复杂的模型计算，我们构建了 model serving 这样的服务来专门支持高效的 GPU 计算。通过这三个环节，我们形成了高效的在线方案。通过跳层检索，多路并行等方案，我们在真实广告业务中，从千万量级广告库召回 top2K，整体链路 rt 增长不超过 5%。离线端依托于阿里即将开源的 X-Deep Learning 框架，我们能够支持千亿级样本 & 十亿级特征的离线训练。

到这里，我对整个深度树匹配方案进行总结和思考。

我们从一个本质性的问题出发：怎么从全量的商品库里面高效检索 TopK 的相关商品；为了解决这个问题，我们提出一套全新的推荐算法框架，它能够支持全库检索和先进模型。在此过程中，我们提出了兴趣最大堆的结构，通过兴趣最大堆这样一个结构，决定了我们的检索策略可以采用 BeamSearch 这样的方案，同时兴趣最大堆结构又阐明了样本是怎么生成的，进而指导了树结构是怎么优化的。此外兴趣最大堆又给出了兴趣建模，同时推导出用样本牵引模型学习的方案。回顾整个流程我们知道兴趣最大堆链接了推荐技术的三个核心环节，索引构建，兴趣模型和检索策略，形成了统一框架。

而我们又跳开这个层面深入思考一个新问题：兴趣最大堆性质本身源于数据中学习得到，因此我们思考下一代推荐技术不止于全库检索 + 先进模型，而是数据驱动下三者（索引，模型，检索）的联合优化学习。

下一代推荐技术的核心挑战

沿着这样一个思路，我们来看一下深度树匹配在这样一个全新的视角上，面临的挑战是什么。

如果说下一代推荐技术应该围绕的是索引结构、模型能力和检索策略的联合端到端学习，那么在这样一个大的目标下面，深度树匹配要成为下一代推荐核心技术，我们认为仍然存在 3 个方面的问题：

  • 第一个问题是：它能不能真正做到数据驱动的端到端的模块优化？

  • 第二个问题是：它如果成为一代技术，那么应该具有业务的普适性，不应该只停留在商品推荐、视频推荐、新闻推荐等业务，它该怎么做到业务赋能下的端到端的联合优化？

  • 第三个问题是：为了能够适应不同的场景以及不同的推荐业务，它一定要抽象出公共可复用的模块来做平台性的输出。

围绕这三个问题，我们把深度树匹配进一步做了迭代和探索。

端到端的模块优化

首先是端到端的模块优化。

这里重点讲一下树结构和模型是怎么联合优化的。因为树结构会影响中间层的样本生成，那么从模型视角来看，模型效果不好的话，一般就是把样本错分了。但是样本错分这样一个具体事实，背后又可能有两个原因：第一个原因就是模型确实训练的不好；第二个原因是可能样本标签本身打错了，比如说树结构本身生成的样本标签打错了。

所以我们提出了一套方案：优化模型和优化样本标签交替进行，来实现树结构和模型的联合优化方案。最开始先生成一个初始的树，根据这个初始的树去训练模型，有了模型之后，再对数据进行判别，找出哪些样本标签打错了，从而进行一些标签的调整，相当于做一些树结构的调整。完成一轮新的树的结构的调整之后，我们再来做新的模型学习，实现整个交替的优化。

端到端的流程优化

第二部分是怎么在业务赋能下面来做到端到端的流程优化。

举个具体的例子：广告召回的时候，不是考虑兴趣最大化召回，而是考虑收入最大化召回，我们叫做 ECPM。从公式上讲，它包括 PCTR×BID，PCTR 是预估点击率，BID 是广告主的出价。

由于这个 ECPM 是通过公式得到的，它是两个因子的乘积，因此很难根据用户直接对一个商品是否有兴趣这样一个隐式的反馈学习得到。那么对于业务目标的最大化召回，怎么来改善整个深度树匹配的方案，使得它能够适应业务目标，就是我们探究的一个问题。

我们借鉴深度树匹配方案来改进，核心是学习一个 ECPM 最大堆，具体的学习方式是通过构建满足 ECPM 最大堆性质的样本去牵引模型拟合这样的 ECPM 最大堆。可以假设我们已经得到了从叶子层随机抽取的一些样本，基于一些预估模块和后续的反馈模块可以知道用户对叶子层样本的 ECPM 值。

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

平台能力输出

第三个挑战就是整个平台能力的输出。

这里我们计划搭建一套通用框架，其中核心能力包括三个部分：

  • 第一部分是可学习的树型的索引结构；

  • 第二部分是能够支持灵活的层排序深度模型，比如 DIN，PNN 等；

  • 第三部分就是我们能够面向业务目标，能够定制全局最优化检索方案。

那么对于推荐召回问题，可能很多人会关心树结构是怎么更新的，比如新闻推荐，如果现在就有新的新闻，要怎么被这个树的结构捕捉到。实际上我们已经给出了一个方案：对于实时更新的新鲜事，可以根据一些 sideinfo，找到和当前的新闻相似的新闻，挂载到它们的最相近的父亲节点上，保证初始的召回。有了初始的召回之后，就可以积累数据，有了数据之后，就可以通过实时更新，增量学习的方式，实现整个树型索引和层排序模型的学习，来达成整个树结构的更新。

下一代推荐技术探索的再思考

最后再讲一些内容，是对深度树匹配再进一步的思考。

要完成从全量商品库里面高效检索 TopK 商品这样一个推荐问题，实际上最核心关注的是三个大的模块：检索、模型和索引。

索引决定了整个数据的组织结构，它承载的是模型能力和检索策略，实现检索的快速准确。检索实际上是面向目标，它需要和索引结构相适配。模型支撑的是整个检索效果的优化。

我们认为，在数据驱动下的三者联合学习，才能实现整个推荐效果的最优化。之前的两代发展，可能索引、模型和检索的策略往往是分离的优化，那么接下来要进一步去优化它，我们考虑的是怎么让它进行联合优化学习。所以说深度树匹配这样一个方案，还会沿着联合优化学习的方案持续的去探索创新。

第二，我们尝试把深度树匹配方案跳出推荐业务，再来看一下，它有哪些横向和纵向业务的发展空间。

从算法链路视角看，用户得到最终的结果经历了召回、CTR 预估 Rank 和最后的策略，TDM 更多承担的是召回的工作。我们现在是独立在优化召回结果，从孤立的优化，到协同 Rank 联合一起联动的优化，可能是 TDM 接下来的一个发展的方向。

同时我们从技术和业务的视角来考虑扩展，因�