阿里广告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 现状

首先，我们先简要介绍一些相关的数学符号。给定用户信息空间 $\mathcal{X}$ 及商品集合 $\mathcal{I}=1,\dots ,M$ （其中 $M\gg 1$ 表示商品数目），对于任意用户 $\mathbf{x}\in \mathcal{X}$ ，其发生交互（如点击、购买或收藏等等）的商品构成 $\mathcal{I}$ 的一个子集，表示为 ${\mathcal{I}}_{\mathbf{x}}$。为了表示方便，我们引入 0/1 编码向量 $\mathbf{y}\in \mathcal{Y}={0,1}^M$ 来表示交互商品子集（其中 $y_j=1$ 表示用户 $\mathbf{x}$ 与商品 $j$ 发生了交互，而 $y_j=0$ 则表示没有）。由此，用户-商品关系可以表示为一个未知的概率分布 $p:\mathcal{X}\times \mathcal{Y}\to {\mathbb{R}}^{+}$ ，而训练数据集 ${\mathcal{D}}_{tr}$ 及测试数据集 ${\mathcal{D}}_{te}$ 则可以视为 $p(\mathbf{x},\mathbf{y})$ 的 i.i.d.采样。

诸如 TDM 及 PLT 等树模型可以统一地表示为 $\mathcal{M}(\mathcal{T},g)$ 。其中， $\mathcal{T}$ 表示用作索引的树结构：假定 $\mathcal{T}$ 是一棵高度为 $H$ 的 $b$ 叉树且 ${\mathcal{N}}_h$ 表示树上第$h$层的节点集合，相应地，树上所有节点集合可以表示为 $\mathcal{N}={\bigcup }_{h=0}^H{\mathcal{N}}_h$ 。我们将第 0 层节点视为根节点 $r(\mathcal{T})$ (即 ${\mathcal{N}}_0=r(\mathcal{T})$ ），第 $H$ 层节点 ${\mathcal{N}}_H$ 视为叶子节点，每个叶子节点都与商品集合中的某个商品一一对应（在数学上等价于存在双射 $\pi :{\mathcal{N}}_H\to \mathcal{I}$ ）。对于树上任意节点 $n\in \mathcal{N}$ ，我们用 $\rho (n)$ 表示其父节点， $\mathcal{C}(n)$ 表示其子节点集合， $\mathcal{L}(n)$ 表示以 $n$ 为根节点的子树的叶子节点集合，而 $\mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}(n)$ 表示树上从根节点 $r(\mathcal{T})$ 到 $n$ 路径上的所有节点集合。 $g:\mathcal{X}\times \mathcal{N}\to \mathbb{R}$ 表示相应的打分模型：对于任意用户信息 $\mathbf{x}$ 及任意树上节点 $n\in \mathcal{N}$ ，打分模型输出相应的分数，该分数在检索中，对于不同的树模型有着不同的用法。

无论是 TDM 还是 PLT，其训练目标函数都可以表示为

在该目标函数中，

• $z_n=\mathbb{I}({\sum }_{n’\in \mathcal{L}(n)}{y}_{\pi (n’)}\ge 1)$ 表示树上节点 $n$ 所对应的标签。该标签用于表示该节点子树中对应于用户交互商品的叶节点的存在性，反映了该节点上的用户兴趣，且由此可定义 ${\mathcal{S}}_h^{+}(\mathbf{x})=n:n\in {\mathcal{N}}_h,z_n=1$ （在TDM中，该过程被称为正样本上溯）。图1(a)给出了这种定义的一个例子；

• ${\ell }_{\mathrm{B}\mathrm{C}\mathrm{E}}(z,g)=-z\log (1+\exp (-g))-(1-z)\log (1+\exp (g))$ 表示交叉熵损失函数，用于度量打分模型输出 $g(\mathbf{x},n)$ 与实际节点用户兴趣分布 $p(z_n|\mathbf{x})$ 的差异；

• ${\mathcal{S}}_h(\mathbf{y})$ 表示用于训练的树上第$h$层节点集合。在TDM中，${\mathcal{S}}_h(\mathbf{y})={\mathcal{S}}_h^{+}(\mathbf{x})\bigcup {\mathcal{S}}_h^{-}(\mathbf{y})$ ，其中 ${\mathcal{S}}_h^{-}(\mathbf{y})$ 表示在第 $h$ 层上随机无放回采样得到的节点集合。在PLT中， ${\mathcal{S}}_h(\mathbf{y})=n:n\in \mathcal{C}(n’),n’\in {\mathcal{S}}_{h-1}^{+}(\mathbf{y})$ 。

在测试时，TDM 及 PLT 等树模型都采用 Beam Search 的方式召回商品子集。假定检索宽度为 $k$ ， ${\mathcal{B}}_h(\mathbf{x})$ 表示给定用户信息 $\mathbf{x}$ 时 Beam Search 在第 $h$ 层召回的节点结合， ${\tilde{\mathcal{B}}}_h(\mathbf{x})={\bigcup }_{n’\in {\mathcal{B}}_{h-1}(\mathbf{x})}\mathcal{C}(n’)$ 表示经由 ${\mathcal{B}}_{h-1}(\mathbf{x})$ 在第 $h$ 层扩展得到的节点集合，则 Beam Search 具体过程可以表示为

在该式中， $p_g(z_n=1|\mathbf{x})$ 表示打分模型 $g(\mathbf{x},n)$ 所对应的节点用户兴趣概率估计。TDM 采用直接的方式构建该估计，即 $p_g(z_n=1|\mathbf{x})=1/(1+\exp (-g(\mathbf{x},n)))$ ；而 PLT 采用层次化的方式构建该估计，即 $p_g(z_n=1|\mathbf{x})={\prod }_{n’\in \mathrm{P}\mathrm{a}\mathrm{t}\mathrm{h}(n)}{p}_g(z_{n’}=1|z_{\rho (n’)}=1,\mathbf{x})$ ，其中 $p_g(z_{n’}=1|z_{\rho (n’)}=1,\mathbf{x})=1/(1+\exp (-g(\mathbf{x},n’)))$ 。由此得到的召回商品集合表示为 $\pi (n):n\in {\mathcal{B}}_H(\mathbf{x})$ ，而召回质量可以用基于召回集合定义的 Precision, Recall, 或广告场景的 ECPM 等评价指标度量。比如，Precision 可以表示为 $P@k=\frac{1}{k}{\sum }_{n\in {\mathcal{B}}_H(\mathbf{x})}{y}_{\pi (n)}$ 。不失一般性，在接下来的推导中，我们将围绕 Precision 展开。

2.2 缺陷：训练-测试不匹配问题

从 2.1 节对树模型训练及测试阶段的介绍可以清晰地看到，训练所用的树上节点 ${\mathcal{S}}_h(\mathbf{y})$ 与测试所用的树上节点 ${\tilde{\mathcal{B}}}_h(\mathbf{x})$ 间的差别。以 TDM 为例， ${\mathcal{S}}_h(\mathbf{y})$ 是基于真实交互商品子集 $\mathbf{y}$ 生成的，而 ${\tilde{\mathcal{B}}}_h(\mathbf{x})$ 则是基于用户信息 $\mathbf{x}$ 、上层召回集合 ${\mathcal{B}}_{h-1}(\mathbf{x})$ 和打分模型 $g(\mathbf{x},n)$ 生成的。这种差别使得在 ${\mathcal{S}}_h(\mathbf{y})$ 上训练的最优打分模型 $g(\mathbf{x},n)$ 在 ${\tilde{\mathcal{B}}}_h(\mathbf{x})$ 上并非最优。

另一方面，树上节点标签 $z_n=\mathbb{I}({\sum }_{n’\in \mathcal{L}(n)}{y}_{\pi (n’)}\ge 1)$ 的定义无法保证基于 $p_g(z_n=1|\mathbf{x})$ 的 Beam Search 过程不出现召回性能恶化现象。这一点可以通过一个简单的合成数据实验看出：假设训练数据集为 ${\mathcal{D}}_{tr}={{\mathbf{y}}^{(i)}}_{i=1}^N$ （忽略用户信息），边缘分布参数 ${\eta }_j=p(y_j=1)$ 为 $[0,1]$ 上的均匀采样，且其真实概率分布为 $p(\mathbf{y})={\prod }_{j=1}^{M}p(y_j)$ ，TDM 的训练可以简化为对节点用户兴趣概率的直接估计，也即 $p_g(z_n=1)={\sum }_{i=1}^N{z}_n^{(i)}/N$ 。在测试阶段，其召回集合 ${\mathcal{B}}_H$ 的性能可以用 regret，即 ${\mathrm{r}\mathrm{e}\mathrm{g}}_{p@k}(\mathcal{M})=({\sum }_{j\in {\mathcal{I}}^{(k)}}{\eta }_j-{\sum }_{n\in {\mathcal{B}}_H}{\eta }_{\pi (n)})/k$ 表示，其中 ${\mathcal{I}}^{(k)}$ 表示根据真实概率 ${\eta }_j$ 的 top-$k$ 商品。regret 反映了召回子集与最优商品子集的差别： ${\mathrm{r}\mathrm{e}\mathrm{g}}_{p@k}(\mathcal{M})$ 越大，表明召回子集质量越差；当 ${\mathrm{r}\mathrm{e}\mathrm{g}}_{p@k}(\mathcal{M})=0$ 时，表明召回子集最优。下表展示了该合成数据实验的结果，可以看到，召回性能恶化现象（regret 不为零）普遍存在于任意训练集大小 $N$ 及检索宽度 $k$ 下，即便是在理想情况下 $N=\infty$ ，该现象依然存在。

表 1: 合成数据实验结果

3. 解决方案

工欲善其事，必先利其器。为了解决因训练-检索不匹配导致的树模型召回性能恶化问题，我们首先从检索视角出发，构建了一整套最优树模型的理论框架，包括最优树模型的定义、存在性及训练损失函数等等。基于该理论框架，我们提出了面向 Beam Search 最优的树模型训练算法。

3.1 面向 Beam Search 最优的树模型

首先，我们需要回答的问题是，从检索视角出发，什么样的树模型才是最优的。一个非常直观的想法是，最优的树模型应当保证其 Beam Search 召回的商品子集在相应的评价指标下最优。以 Precision 为例，给定用户信息 $\mathbf{x}$ ，在该评价指标下最优的召回商品子集应当为用户商品分布 $p(\mathbf{y}|\mathbf{x})$ 中交互概率 ${\eta }_j(\mathbf{x})=p(y_j=1|\mathbf{x})$ 最高的商品子集。由此，我们最优树模型的定义，如下所示：

定义（树模型的最优性）：给定概率分布 $p:\mathcal{X}\times \mathcal{Y}\to {\mathbb{R}}^{+}$ ，若对于任意 $\mathbf{x}\in \mathcal{X}$ ，树模型 $\mathcal{M}(\mathcal{T},g)$ 检索宽度为 $k$ 的Beam Search召回集合 ${\mathcal{B}}_H(\mathbf{x})$ 均满足 $\pi (n):n\in {\mathcal{B}}_H(\mathbf{x})\in {\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{T}\mathrm{o}\mathrm{p}\mathrm{k}}_{j\in \mathcal{I}}{\eta }_j(\mathbf{x})$ （其中 ${\eta }_j(\mathbf{x})=p(y_j=1|\mathbf{x})$ ），则该模型被称为面向Beam Search的top-$k$ 最优（top-$k$ Bayes optimal under beam search）；若该关系对于任意检索宽度 $1\le k\le M$ 均成立，则该模型被称为面向Beam Search最优（Bayes optimal under beam search）。

随后，我们需要回答的问题是，在该定义下，最优树模型是否存在？我们能够证明，对于任意概率分布 $p:\mathcal{X}\times \mathcal{Y}\to {\mathbb{R}}^{+}$ 及树结构 $\mathcal{T}$ ，面向 Beam Search 最优的树模型总是存在的，如下所示：

定理（最优树模型的存在性）：给定概率分布 $p:\mathcal{X}\times \mathcal{Y}\to {\mathbb{R}}^{+}$ ，对于任意数据 $(\mathbf{x},\mathbf{y})\sim p$ ，定义

若树模型 $\mathcal{M}(\mathcal{T},g)$ 对任意 $n\in {\bigcup }_{h=1}^H{\tilde{\mathcal{B}}}_h(\mathbf{x})$ 均满足 $p_g(z_n|\mathbf{x})=p^{\ast }(z_n|\mathbf{x})$ ，则对于任意 $m\le k$ ，该模型均为面向Beam Search的top-$m$ 最优；若 $\mathcal{M}(\mathcal{T},g)$ 对任意 $n\in \mathcal{N}$ 均满足 $p_g(z_n|\mathbf{x})=p^{\ast }(z_n|\mathbf{x})$ ，则该模型为面向Beam Search最优。

该定理表明，对于任意概率分布 $p:\mathcal{X}\times \mathcal{Y}\to {\mathbb{R}}^{+}$ 及任意树结构 $\mathcal{T}$ ，面向 Beam Search 最优的树模型总是存在的（只要其打分模型满足相应的条件）。因此，我们可以专注于打分模型的训练而暂时不考虑树结构的优化。

接下来，我们需要解答的问题是，如何得到最优的树模型？注意到，在最优树模型的定义中，判定条件存在等价表示，即 ${\mathbb{E}}_{p(\mathbf{x})}\left[{\sum }_{n\in {\mathcal{B}}_H(\mathbf{x})}{\eta }_{\pi (n)}(\mathbf{x})\right]={\mathbb{E}}_{p(\mathbf{x})}\left[{\sum }_{j\in {\mathcal{I}}_{\mathbf{x}}^{(k)}}{\eta }_j(\mathbf{x})\right]$ 。由此，我们可以非常自然地得到一个树模型的最优性度量，即 ${\mathrm{r}\mathrm{e}\mathrm{g}}_{p@k}(\mathcal{M})={\mathbb{E}}_{p(\mathbf{x})}\left[\frac{1}{k}\left({\sum }_{j\in {\mathcal{I}}_{\mathbf{x}}^{(k)}}{\eta }_j(\mathbf{x})-{\sum }_{n\in {\mathcal{B}}_H(\mathbf{x})}{\eta }_{\pi (n)}(\mathbf{x})\right)\right]$ 。然而，因为在得到 ${\mathcal{B}}_H(\mathbf{x})$ 的过程中存在不可导的 $\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{T}\mathrm{o}\mathrm{p}\mathrm{k}$ 算子，所以该度量无法直接被用作损失函数来训练。为了训练最优树模型，我们需要引入能够保证其最优解即为最优树模型的损失函数作为替代，其定义如下：

定义（损失函数的校准性）：对任意概率分布 $p:\mathcal{X}\times \mathcal{Y}\to {\mathbb{R}}^{+}$ ，给定树模型 $\mathcal{M}(\mathcal{T},g)$ ，若损失 $L:{0,1}^M\times {\mathbb{R}}^{|\mathcal{N}|}\to \mathbb{R}$ 满足 ${\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_g{\mathbb{E}}_{p(\mathbf{x},\mathbf{y})}\left[L(\mathbf{y},\mathbf{g}(\mathbf{x}))\right]\subset {\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_g{\mathrm{r}\mathrm{e}\mathrm{g}}_{p@k}(\mathcal{M})$ ，则该损失函数被称为面向Beam Search的top-$k$ 校准的（top-$k$ calibrated under beam search）。若该式对于任意 $1\le k\le M$ 均成立，则该损失函数被称为面向Beam Search校准的（calibrated under beam search）。

校准性的定义在理论上为用于树模型训练的损失函数提供了判定标准：如果损失函数不符合校准性的定义，即便是在训练数据无穷的理想情况下，训练得到的树模型也不可能达到零 regret，也就不可能是最优树模型。在 2.2 节的合成数据实验中，我们已经给出了一个 TDM 的训练损失函数不服从校准性的例子。由此反例可以判定，从检索的角度上看，由于训练损失函数的问题，TDM 及 PLT 均非理论最优。

3.2 最优树模型训练算法

基于 3.1 节提出的理论基础，我们可以构造训练最优树模型的损失函数并设计相应的训练算法。首先，在最优树模型的存在性定理中， $p^{\ast }(z_n|\mathbf{x})$ 实际上提供了一种不同于 TDM 及 PLT 的树上节点标签定义方式。为以示区别，我们称之为最优树上标签，并将其表示为 $z_n^{\ast }$ ，也即

$z_n^{\ast }$ 与 $z_n$ 的不同之处可以从图 1(a)及图 1(c)的对比看出：可以看到，根据 $z_n^{\ast }$ 的定义，树上节点标签等于其子树中边缘概率 ${\eta }_j(\mathbf{x})$ 最高的商品标签 $y_j$ ，由此导致了用户实际交互商品（ $y_j=1$ ）所对应的树上节点并不总是被当作正样本（ $z_n^{\ast }=1$ ），如节点 1 及节点 6 所示。

图 1: 不同树上节点标签定义方式与 Beam Search 召回节点对比。

在实际训练中，假设打分模型对应的模型参数为 $\mathbf{\theta }\in \mathbf{\Theta }$ ，则打分模型、Beam Search 在第 $h$ 层扩展集合、打分模型及对应的节点用户兴趣概率估计可以表示为 ${\tilde{\mathcal{B}}}_h(\mathbf{x};\mathbf{\theta })$ , $g_{\mathbf{\theta }}(\mathbf{x},n)$ 及 $p_{g_{\mathbf{\theta }}}(z_n=1|\mathbf{x})$ 。根据最优树模型的存在性定理，我们可以很自然地得到符合 top-$k$ 校准性定义的损失函数，即

然而， $z_n^{\ast }$ 依赖于在实际训练中未知的 ${\eta }_j(\mathbf{x})$ ，因此该损失函数依旧不能用于训练。此外，待训练的模型参数 $\mathbf{\theta }$ 出现在 ${\tilde{\mathcal{B}}}_h(\mathbf{x};\mathbf{\theta })$ ，由于 $\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{T}\mathrm{o}\mathrm{p}\mathrm{k}$ 算子不可导，该损失函数依旧不可导。为此，我们提出两项近似：

• 基于当前树模型 $\mathcal{M}(\mathcal{T},g_{{\mathbf{\theta }}_t})$ 估计 $z_n^{\ast }$ ，即

• 采用分部优化的方式，优化当前树模型 $\mathcal{M}(\mathcal{T},g_{{\mathbf{\theta }}_t})$ 时，固定 ${\hat{z}}_n(\mathbf{x};{\mathbf{\theta }}_t)$ 及 ${\tilde{\mathcal{B}}}_h(\mathbf{x};{\mathbf{\theta }}_t)$ ，单独优化 $g_{\mathbf{\theta }}(\mathbf{x},n)$ 中的模型参数。

由此，我们得到最终的训练损失函数为

可以看到，该损失函数与 TDM 等树模型的区别有两处，分别为使用 ${\tilde{\mathcal{B}}}_h(\mathbf{x};{\mathbf{\theta }}_t)$ 而非 ${\mathcal{S}}_h(\mathbf{y})$ 生成用于训练的树上节点集合，以及使用 ${\hat{z}}_n(\mathbf{x};{\mathbf{\theta }}_t)$ 而非 $z_n$ 作为树上节点标签。这两处区别恰好分别对应于 2.2 节所分析的两处训练-测试不匹配问题。

最后，相应的训练算法如下所示：

尽管做出了多项近似，该损失函数在一定程度上依旧保留了最优树模型的特性：定义损失函数 $L_{{\mathbf{\theta }}_t}^{\ast }(\mathbf{y},\mathbf{g}(\mathbf{x});\mathbf{\theta })={\sum }_{h=1}^H{\sum }_{n\in {\mathcal{N}}_h}{w}_n(\mathbf{x},\mathbf{y};{\mathbf{\theta }}_t){\ell }_{\mathrm{B}\mathrm{C}\mathrm{E}}({\hat{z}}_n(\mathbf{x};{\mathbf{\theta }}_t),g_{\mathbf{\theta }}(\mathbf{x},n))$ ，其中 $w_n(\mathbf{x},\mathbf{y};{\mathbf{\theta }}_t)>0$ 。由此， $L_{{\mathbf{\theta }}_t}(\mathbf{y},\mathbf{g}(\mathbf{x});\mathbf{\theta })$ 可以看作是 $L_{{\mathbf{\theta }}_t}^{\ast }(\mathbf{y},\mathbf{g}(\mathbf{x});\mathbf{\theta })$ 在满足 $w_n=\mathbb{I}(n\in {\bigcup }_{h=1}^H{\tilde{\mathcal{B}}}_h(\mathbf{x};{\mathbf{\theta }}_t))$ 的极限情况。可以证明， $L_{{\mathbf{\theta }}_t}^{\ast }(\mathbf{y},\mathbf{g}(\mathbf{x});\mathbf{\theta })$ 满足如下定理：

定理（训练算法理想结果）：假设打分模型对应的函数空间 $\mathcal{G}=g_{\mathbf{\theta }}:\mathbf{\theta }\in \mathbf{\Theta }$ 容量足够，对任意概率分布 $p:\mathcal{X}\times \mathcal{Y}\to {\mathbb{R}}^{+}$ ，若树模型 $\mathcal{M}(\mathcal{T},g_{{\mathbf{\theta }}_t})$ 满足存在 ${\mathbf{\theta }}_t\in \mathbf{\Theta }$ 使得

$${\mathbf{\theta }}_t\in {\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{\mathbf{\theta }\in \mathbf{\Theta }}{\mathbb{E}}_{p(\mathbf{x},\mathbf{y})}\left[L_{{\mathbf{\theta }}_t}^{\ast }(\mathbf{y},\mathbf{g}(\mathbf{x});\mathbf{\theta })\right],$$

则该树模型为面向Beam Search最优。

该定理表明，引入对 $z_n^{\ast }$ 的估计 ${\hat{z}}_n(\mathbf{x},\mathbf{\theta })$ 及引入分步优化并不会对 $\mathcal{M}(\mathcal{T},g_{{\mathbf{\theta }}_t})$ 的最优性造成影响。 然而，使用 ${\tilde{\mathcal{B}}}_h(\mathbf{x};{\mathbf{\theta }}_t)$ 而非 ${\mathcal{N}}_h$ 会对最优性造成影响，原因在于 $w_n(\mathbf{x},\mathbf{y};{\mathbf{\theta }}_t)=\mathbb{I}(n\in {\tilde{\mathcal{B}}}_h(\mathbf{x};{\mathbf{\theta }}_t))$ 不符合 $w_n(\mathbf{x},\mathbf{y};{\mathbf{\theta }}_t)>0$ 的要求。在实践中，我们可以通过引入随机采样等策略来避免该问题，但通过实验我们发现，这些策略引入与否对效果的影响并不显著。因此，在后续实验中我们均直接使用 $L_{{\mathbf{\theta }}_t}(\mathbf{y},\mathbf{g}(\mathbf{x});\mathbf{\theta })$ 损失函数。

4. 实验

4.1 实验设置

我们使用了 Amazon Books 和 UserBehavior 两个大型公开数据集来进行实验验证。Amazon Books 是用户在 Amazon 上的行为记录，我们选择了其中最大的 Books 这一子类目。UserBehavior 为淘宝全网行为子集，能在一定程度上对应线上真实效果。数据集的规模如下：

在实验中，我们比较了如下几种不同的模型算法，包括两种非树模型算法：

• Item-CF: 基本的协同滤波算法，被广泛应用于个性化推荐任务中。

• YouTube product-DNN: 应用于Youtube视频推荐的向量内积检索模型。

• 以及四种树模型算法

• HSM: 层次Softmax模型（依赖前提假设 ${\sum }_{j=1}^M{y}_j=1$ ），被广泛应用于NLP领域，作为归一化概率计算的一种替代。

• PLT: HSM的多标签版本，被广泛应用于大规模多标签文本分类任务中。

• JTM: TDM的升级版本，通过打分模型及树结构的联合优化，在这两个数据集上取得了最优结果。

• OTM: 本文中提出的最优树模型训练算法。同时，我们也比较了OTM的一个变种OTM (-OptEst)，即将算法中 ${\hat{z}}_n(\mathbf{x};\mathbf{\theta })$ 的估计替换为TDM及PLT中所使用的 $z_n$ 。

对于所有的树模型，我们采用相同的树结构及相同的打分模型网络结构。具体来说，我们使用 JTM 算法训练得到的树结构作为所有树模型共享的树结构，使用三层全连接网络作为所有树模型共享的打分模型网络结构。在召回性能评价上，我们使用在测试集 ${\mathcal{D}}_{te}$ 上估计的 Precision@m, Recall@m 和 F-measure@m 作为评价指标，对任意 $(\mathbf{x},\mathbf{y})\in {\mathcal{D}}_{te}$ ，其定义如下：

其中， ${\mathcal{B}}_H^{(m)}(\mathbf{x})$ 表示在 Beam Search 叶子层召回集合中的 top-$m(m\le k)$ 节点所构成的集合。

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 训练的参数化检索组件；将检索组件引入打分模型及树结构的联合训练等等方向，都有巨大的潜在价值等待挖掘。