Question

1. 推荐已经被各种内容提供商content provider 广泛使用。基于用户的历史行为或相似偏好的用户来推断出用户兴趣的个性化推荐方法，已经在 YouTube 和 Amazon 中被证明是有效的。设计这样的推荐模型来为每个用户从整个语料库中预测最佳候选集合candidate set 有很多挑战：

   • 在拥有大量语料库的系统中，一些表现良好well-performed 的推荐算法可能无法从整个语料库中进行预测。相对于语料库大小的线性预测复杂度是不可接受的。部署这样的大规模推荐系统需要限制单个用户的计算量。

     假设用户有 10 亿，而 item 有 1 亿，如果是语料库的线性复杂度则需要 10 亿亿次，现有算力难以支持。如果是语料库的对数复杂度，则需要 270 亿次，现有算力可以接受。

   • 而且除了精确性preciseness 之外，也需要推荐项目的新颖性novelty 从而维护用户体验user experience 。我们不希望推荐结果仅包含用户历史行为的同质化homogeneous 的item 。

   为了减少计算量并处理庞大的语料库，基于内存的协同过滤memory-based collaborative filtering 方法被广泛应用于工业界。作为协同过滤家族中的一种代表性方法，item-based 协同过滤可以用相对少得多的计算从非常大的语料库中进行推荐。具体而言：

   • 首先预先计算的item pair 对之间的相似性。
   • 然后使用用户的历史行为作为触发器trigger 来召回那些最相似的 item 。

   然而，候选集的范围是有限制的，即，并不是所有的item、而是只有和trigger 相似的 item 才能被最终推荐。这种直觉阻止了推荐系统跳出历史行为来探索潜在的用户兴趣，这限制了召回结果的准确性accuracy 。而且在实践中，这种方法也限制了召回结果的新颖性novelty 。

   减少计算的另一种方法是进行粗粒度推荐coarsegrained recommendation 。例如，系统为用户推荐少量的item 类目category ，并选择这些类目下对应的所有item 。然后这些 item 进入ranking 阶段。但是对于大型语料库，计算问题仍然没有解决。

   • 如果类目数量很大，那么类目推荐本身也会遇到计算障碍。
   • 如果类目数量很小，那么某些类目将必然包含非常多的 item ，使得接下来的 ranking 阶段的计算不可行。

   此外，所使用的类目体系通常不是为推荐问题而设计的，这可能会严重损害推荐的准确性accuracy 。

   在推荐系统的文献中，基于模型的方法是一个活跃的话题。例如：

   • 矩阵分解matrix factorization: MF 等模型试图将 pairwise 的 user-item 偏好（例如评分rating ）分解成用户因子 user factor 和 item 因子 item factor ，然后向每个用户推荐其最喜欢的 item 。
   • 因子分解机factorization machine:FM 进一步提出了一个统一的模型，它可以用任何类型的输入数据模拟不同的因子分解模型factorization model 。
   • 在一些没有显式偏好而只有隐式用户反馈（例如，像点击或者购买这样的用户行为）的现实场景中，bayesian personalized ranking: BPR 给出了一种以partial order 的三元组来表达偏好的解决方案，并将其应用于 MF 模型。
   • 在工业上，YouTube 使用深度神经网络来学习用户embedding 和 item embedding，其中两种 embedding 分别由它们相应的特征生成。

   在上述各种方法中，user-item pair 对的偏好可以表示为用户向量representation 和 item 向量representation 的内积。因此，预测阶段相当于检索用户向量在内积空间中的最近邻居nearest neighbor 。对于向量搜索问题，针对近似k 近邻 approximate k-nearest neighbor 的索引哈希index hashing 或索引量化index quantization 可以保证检索的效率。

   但是，用户向量representation 和 item 向量representation 之间的内积，这样一种交互形式interaction form 严重限制了模型的能力。还有许多其他类型的、更具有表达能力的交互形式，如，用户历史行为和候选item 之间的叉积特征cross-product feature 被广泛用于点击率预测。最近的工作提出了一种神经协同过滤方法，其中使用神经网络而不是内积来建模用户向量representation 和 item 向量representation 之间交互。实验结果表明，多层前馈神经网络比固定内积的方法具有更好的性能。deep interest network:DIN 指出，用户的兴趣是多样的，类似注意力的网络结构可以根据不同的候选item 生成不同的用户向量。除了上述工作之外，product neural network:PNN 等其它方法也证明了高级advanced 神经网络的有效性。

   然而，由于这些模型不能被规则化 regulated 为用户向量和item 向量之间的内积形式从而有效利用近似kNN 搜索，因此它们不能被用在大规模推荐系统中召回候选item。如何克服计算障碍，使得任意高级神经网络在大规模推荐中可行是一个难题。

   为了解决上述挑战，论文 《Learning Tree-based Deep Model for Recommender Systems》提出了一种新的、基于树tree-based 的深度推荐模型tree-based deep recommendation model: TDM。

   在多类分类问题中，人们研究了树方法以及tree-based 方法。其中，通常使用树来划分样本空间或label 空间以减少计算成本。然而，研究人员很少涉足使用树结构作为检索索引的推荐系统。事实上，信息的层级结构hierarchical structure 普遍存在于很多领域。例如在电商场景中，iPhone 是细粒度的 item，而智能手机是iPhone 所属的粗粒度概念。TDM 方法利用信息的层级结构，将推荐问题转化为一系列的层级分类问题hierarchical classification problem 。通过解决从容易到困难的问题，TDM 可以同时提高准确率accuracy和效率efficiency 。

   论文的主要贡献：

   • 据我们所知，在从大型语料库中生成推荐时，TDM 是第一种使得任意高级模型成为可能的方法。

     得益于层级树搜索hierarchical tree search，TDM 在进行预测时实现了相对于语料库大小对数复杂度的计算。

   • TDM 可以帮助更精确precisely 地找到新颖novel 、但有效effective 的推荐结果，因为整个语料库都被探索，并且更有效的深度模型也有助于找到潜在的兴趣。

   • 除了更高级的模型之外，TDM 还通过层级搜索hierarchical search 提高推荐的准确性accuracy ，其中层级搜索将一个大问题分解为多个小问题，并从易到难依次解决。

   • 作为一种索引，树结构tree structure 还可以学习，从而获得item 和概念concept 的最佳层级optimal hierarchy ，以便更有效地检索。而这反过来又有助于模型训练。

     我们采用一种 tree learning 方法，该方法可以对神经网络和树结构进行联合训练。

   • 我们在两个大规模真实世界数据集上进行了广泛的实验。结果表明：TDM 的性能明显优于现有方法。淘宝display 广告平台的在线 A/B test 结果也验证了该方法在生产环境中的有效性。

2. 值得一提的是，tree-based 方法也在语言模型的工作 hierarchical softmax 中进行了研究。但是hierarchical softmax 和我们提出的 TDM 不仅在动机上、而且在公式上都不相同。

   • 在 next-word prediction 问题中，传统的 softmax 必须计算归一化的 term 才能获得任何单个word 的概率，这非常耗时。

   • hierarchical softmax 使用树结构，next-word 的概率被转换为沿着树路径tree path 的节点概率的乘积。这种公式将next-word 概率的计算复杂度降低到语料库大小的对数量级。

     然而，在推荐问题中，目标是在整个语料库中搜索那些最喜欢的 item，这是一个检索问题。在 hierarchical softmax 中，父节点的最优不能保证全局最优的叶节点位于该父节点的后代中，并且仍然需要遍历所有item 从而找到最优叶节点。因此，hierarchical softmax不适合这样的检索问题。

     为了解决检索问题，我们提出了一种类似于最大堆 max-heap like 的树公式tree formulation，并引入了深度神经网络对树进行建模，从而形成了一种有效的大规模推荐方法。

   • 此外， hierarchical softmax 采用单隐层网络 single hidden layer network 来处理特定的nlp 问题，而我们提出的 TDM 方法适用于任何神经网络结构。

8.1 模型

1. 首先我们介绍淘宝展示广告推荐系统Taobao display advertising recommender system 的架构，如下图所示。

   • 在收到来自用户的页面浏览请求page view request 之后，系统使用用户特征、上下文特征、item 特征作为输入，从 matching server 的整个语料库（数亿）中生成相对小得多的候选item 集合（通常是数百个）。tree-based 推荐模型在此阶段需要付出努力，将候选集合的大小缩小了几个数量级。
   • 对于这数百个候选item，实时预估server 使用更具有表达能力的、同时也是更耗时的模型来预估点击率或转化率等指标。
   • 在经过策略排序ranking by strategy 之后，最终会有若干个item 曝光给用户。

   如前所述，我们提出的推荐模型旨在构建具有数百个item 的候选集合。这个阶段是必不可少的，也是困难的。用户是否对生成的候选item 感兴趣，这决定了曝光质量impression quality 的上限。如何从整个语料库中抽取候选item，并平衡效率 efficiency 和效果 effectiveness 是一个问题。

   

2. 然后我们介绍 TDM 模型。

   • 首先我们介绍 tree-based 模型中使用的树结构tree structure ，从而给出一个总体概念。
   • 然后我们引入 hierarchical softmax 来说明为什么它的公式不适合推荐。
   • 接着我们给出了一个新颖的、类似于最大堆的树公式tree formulation ，并展示了如何训练 tree-based 模型。
   • 接着我们介绍了深度神经网络体系架构。
   • 接着我们展示了如何在 tree-based 模型中构造和学习树。
   • 最后我们介绍了在线 serving 系统。

8.1.1 推荐树

1. 推荐树recommendation tree 由节点集合 $ \mathbb N $ 组成，其中 $ \mathbb N=\{n_1,n_2,\cdots,n_{|\mathbb N|}\} $ 代表 $ |\mathbb N| $ 个非叶节点或叶节点。

   除了根节点之外， $ \mathbb N $ 中的每个节点都有一个父节点和任意数量的子节点。具体而言，语料库 $ \mathbb C $ 中的每个item $ c_i $ 对应于、且仅对应于树中的一个叶节点，而那些非叶节点是粗粒度的概念coarse-grained concept 。不失一般性，我们假设节点 $ n_1 $ 始终是根节点。

   下图显示了一个示例的树，其中每个圆代表一个节点，节点编号node number 是它在树中的索引。该树总共有 8 个叶节点，每个叶节点对应于语料库中的一个 item 。

   值得一提的是，虽然给定的例子是一棵完整的二叉树complete binary tree ，但是我们并没有对模型中的树的类型施加完整complete 、或者二叉 binary的限制。

   

8.1.2 Hierarchical Softmax

1. 在树形结构tree structure 中，我们首先介绍相关的工作 hierarchical softmax ，从而帮助了解它与我们的 TDM 之间的差异。

   在 hierarchical softmax 中，树中的每个叶节点 $ n $ 具有从根节点到该叶节点的唯一编码。例如，如果我们将 1 编码为选择左分支、将 0 编码为选择右分支，那么上图中的叶节点 $ n_9 $ 在树中的编码为 110、 $ n_{15} $ 在树中的编码为 000 。

   令 $ b_j(n) $ 为叶节点 $ n $ 在 level j 中的编码。在 hierarchical softmax 中，给定上下文的next-word 概率为：

   $ P(n\mid\text{context}) = \prod_{j=1}^w P(b=b_j(n)\mid l_j(n),\text{context}) $

   其中：

   • $ w $ 为叶节点 $ n $ 的编码长度。
   • $ l_j(n) $ 为叶节点 $ n $ 在 level j 的祖先。

   这样，hierarchical softmax 通过避免常规 softmax 中的归一化项（需要遍历语料库中的每个word ）来解决概率计算问题。

   然而，为了找到最可能的叶节点，模型仍然必须遍历整个语料库。因为沿着树路径 tree path 自上而下遍历每一层最可能的节点并不能保证成功地检索到最优的叶节点。因此，hierarchical softmax 公式不适用于大规模检索问题。

   此外，根据上式，树中的每个非叶节点被训练为 binary 分类器，以区分其两个子节点。但是，如果这两个子节点是树中的邻居，它们很可能是相似的。在推荐场景中，用户很可能对这两个子节点都感兴趣。

2. hierarchical softmax 模型侧重于区分最优选择 optimal choice 和次优选择 suboptimal choice ，这可能会失去从全局角度进行区分的能力。

   即，对于某个非叶节点的两个子节点，hierarchical softmax 只能选择其中一个（最优选择），而无法同时选择二者。

   另外，如果使用贪婪的 beam search 来检索那些最可能的叶节点，一旦在树的较高level 做出了错误的决定，那么该模型可能无法在较低level 的那些低质量候选中找到相对较好的结果。

   YouTube 的工作报告说：他们已经尝试了 hierarchical softmax 来学习用户embedding 和 item embedding，而它的性能要比 sampled-softmax 方式更差。

   鉴于 hierarchical softmax 的公式不适合大规模推荐，我们在下面的部分提出了一个新树模型公式。

8.1.3 Tree-based 模型公式

1. 为了解决最喜欢item 的高效 top-k 检索问题，我们提出了类似于最大堆max-heap like 的树概率公式tree probability formulation 。

   max-heap like tree 是一种树结构，其中对于每个用户 $ u $ ，level j 的每个非叶节点 $ n $ 满足以下方程：

   $ p^{(j)}(n\mid u) = \frac{\max_{n_c\in \{\text{n's children nodes in level j+1} \}} p^{(j+1)}(n_c\mid u) }{\alpha^{(j)}} $

   其中：

   • $ p^{(j)}(n\mid u) $ 是用户 $ u $ 对 $ n $ 感兴趣的 ground truth 。
   • $ \alpha^{(j)} $ 是 level j 的 layer-specific 归一化项，以确保 level j 中的概率之和为 1.0 。

   上式表明：父节点的 ground truth 偏好等于其子节点的最大偏好，然后再除以归一化项。

   这类似于最大池化，即 “粗粒度概念”偏好为 “细粒度概念”偏好的最大值。

   注意，我们稍微混用了符号，让 $ u $ 表示特定的用户状态。换句话讲，一旦用户具有新的行为，特定的用户状态 $ u $ 可能迁移到另一个状态 $ u^\prime $ 。

2. 我们的目标是找到偏好概率largest preference probability 最大的 $ k $ 个叶节点。

   假设我们在树中有每个节点 $ n $ 的 ground truth $ p^{(j)}(n\mid u) $ ，我们可以逐层layer-wise 检索偏好概率最大的 $ k $ 个节点，只需要探索每个 level 的 top k 个子节点。通过这种方式，最终可以检索到 top k 个叶节点。

   实际上，我们不需要知道每个节点的确切 ground truth probability 。 我们只需要每个 level 中，节点概率的相对顺序（layer-wise 的顺序），从而帮助找到该 level 的 top k 个节点。基于这一观察，我们使用用户的隐式反馈数据 implicit feedback data 和神经网络来训练每个 level 的判别器discriminator ，该判别器可以区分偏好概率 preference probability 的顺序。

   每个 level 代表该 level 粒度的概念，因此对于每个 level 选择 top k 偏好的粒度即可。例如：假设 k=2，level 1 选择(图书, 数码)， level2 选择 (科技图书, 育儿图书, 笔记本电脑, 手机)，... 。

   实际上，这里每个 level 代表的物理意义可能并不是具体的类目体系，而是比较抽象的概念。

   假设用户 $ u $ 和叶节点 $ n_d $ 有交互，即 $ n_d $ 是 $ u $ 的正样本节点 positive sample node 。这意味着一个排序：

   $ p^{(m)}(n_d\mid u) \gt p^{(m)}(n_t\mid u) $

   其中 $ m $ 为叶节点的 level， $ n_t $ 为任意其它叶节点。

   这里假设只有一个正样本节点。如果有多个正样本节点，则可以在正样本节点和负样本节点之间比较。正样本节点 A 和正样本节点 B 之间无法比较。

   在任意 level j ，令 $ l_j(n_d) $ 表示为 $ n_d $ 在 level j 的祖先。根据树公式 $ p^{(j)}(n\mid u) $ 的定义，我们可以得到：

   $ p^{(j)}(l_j(n_d)\mid u) \gt p^{(j)}(n_q\mid u) $

   其中 $ n_q $ 为在 level j 中除 $ l_j(n_d) $ 之外的其它任意节点。

   在上述分析的基础上，我们可以使用负采样negative sampling 来训练每个level 的顺序判别器order discriminator 。具体而言：

   • 与 $ u $ 有交互的叶节点及其祖先节点构成了 $ u $ 的每个level 的正样本集合。
   • 在每个level 中，除了正样本节点之外随机采样的节点构成了负样本集合。

   下图中的绿色节点和红色节点给出了采样示例。假设给定一个用户及其状态，目标节点是 $ n_{13} $ 。那么 $ n_{13} $ 的祖先节点就是正样本，每个level 随机抽样的那些红色节点就是负样本。

   然后，这些样本被输入到 二元概率模型binary probability models 中，从而获得 level 顺序判别器。我们使用一个具有不同输入的全局深度神经网络二元模型binary model 作为所有level 的顺序判别器。可以使用任意高级神经网络来提高模型能力。

   

3. 定义 $ \mathbb Y_u^+,\mathbb Y_u^- $ 分别为用户 $ u $ 的正样本节点集合、负样本节点集合。那么似然函数likelihood function 为：

   $ \mathcal J = \prod_u\left(\prod_{n\in \mathbb Y_u^+}p\left(\hat y_u(n)=1\mid n,u\right)\prod_{n\in \mathbb Y_u^-}p\left(\hat y_u(n)=0\mid n,u\right)\right) $

   其中：

   • $ \hat y_u(n) $ 为给定 $ u $ 的情况下，对于节点 $ n $ 的预估label。
   • $ p\left(\hat y_u(n)\mid n,u\right) $ 是二元概率模型的输出，它以用户状态 $ u $ 和采样的节点 $ n $ 作为输入。

   对应的损失函数为：

   $ \mathcal L = -\sum_u\sum_{n\in \mathbb Y_u^+\bigcup\mathbb Y_u^-} \left[y_u(n)\log p\left(\hat y_u(n)=1\mid n,u\right) +(1-y_u(n))\log p\left(\hat y_u(n)=0\mid n,u\right) \right] $

   其中 $ y_u(n) $ 为给定 $ u $ 的情况下，节点 $ n $ 的 ground truth label 。关于如何根据损失函数训练模型的详细信息，参考后面的内容。

   注意：这里预估的是排序关系，而不是ctr ；这里的节点集合不仅包含叶节点，也包含非叶节点。

4. 注意，我们提出的采样方法和 hierarchical softmax 中的采样方法有很大不同。

   和 hierarchical softmax 中使用的方法（该方法使模型能够区分最优optimal 结果和次优suboptimal 结果）相比，我们为每个正样本节点随机选择相同level 的负样本。这种方法使得每个level 的判别器都是一个 level 内 intra-level 的全局判别器。每个 level 的全局判别器可以独立地做出精确precise 的决策，而不依赖于上层决策的好坏。

   这种全局判别能力对于层级推荐hierarchical recommendation 方法非常重要。它确保即使模型做出错误的决策，并且低质量的节点泄露到上层的候选集合中，模型也可以在接下来的 level 中选择那些相对较好的节点，而不是非常差的节点。

5. 层级预测算法hierarchical prediction algorithm ：

   • 输入：

     • 用户状态 $ u $
     • 推荐树recommendation tree
     • 需要检索的 item 数量 $ k $
     • 训练好的二元预估模型

   • 输出：推荐的 $ k $ 个叶节点集合

   • 算法步骤：

     • 初始化：设置结果集合 $ \mathbb A=\phi $ ，设置候选集合 $ \mathbb Q=\{根节点n_1\} $ 。

     • 迭代直到 $ \mathbb Q $ 为空集。迭代步骤为：

       • 如果 $ \mathbb Q $ 中有任何叶节点，则从 $ \mathbb Q $ 中移除这些叶节点，并将这些叶节点加入到集合 $ \mathbb A $ 中。
       • 对于 $ \mathbb Q $ 中剩下的每个节点 $ n\in \mathbb Q $ ，计算 $ p\left(\hat y_u(n)=1\mid n,u\right) $ 。
       • 对 $ \mathbb Q $ 中的节点按照 $ p\left(\hat y_u(n)=1\mid n,u\right) $ 进行降序排列，选择其中的 top k 个节点集合，记作 $ \mathbb I $ 。
       • $ \mathbb Q $ 设置为 $ \mathbb I $ 中节点的子节点集合： $ \mathbb Q=\{ \text{children nodes of } n\mid n\in \mathbb I\} $ 。

       $ \mathbb Q $ 中始终保持相同 level 的节点，因此每次选择同 level 中的 top k 节点。对于 top k 叶节点，根据树公式 $ p^{(j)}(n\mid u) $ 的定义，在每个level 中它们的祖先节点也是 top k 的。

     • 根据 $ p\left(\hat y_u(n)=1\mid n,u\right) $ 的排序来选择集合 $ \mathbb A $ 中的 top k 个 item 。

6. 预测阶段的层级预测算法hierarchical prediction algorithm 中，检索过程是 layer-wise 和自上而下的top-down 。

   假设期望的候选item 数量为 $ k $ ，对于大小为 $ |\mathbb C| $ 的语料库 $ \mathbb C $ ，最多遍历 $ 2\times k\times \log |\mathbb C| $ 个节点就可以得到一个完整二叉树中的最终推荐集合。需要遍历的节点数量和语料库大小成对数关系，这使得可以采用高级的二元概率模型。

   前面的图例假设每个叶节点的路径长度相同。实际上每个叶节点的长度可以不同，比如有的叶节点 level 较小（到根节点较短）、有的叶节点 level 较大（到根节点较长），树模型的训练算法、预测算法仍然成立。

7. 我们提出的TDM 方法不仅减少了预测时的计算量，并且与在所有叶节点中进行暴力搜索brute-force search 相比也可能提高推荐质量。

   在没有树的情况下，训练模型以直接找到最优item 是一个困难的问题，因为语料库太大。

   利用树的层级结构，一个大规模的推荐问题被分解为许多小问题。在树的高level 只存在几个节点，因此判别问题discrimination problem 更容易。而高level 做出的决策精化 refine 了候选集，这可能有助于低 level 做出更好的判断。

   后面的实验结果将表明：我们提出的层级检索 hierarchical retrieval 方法比直接暴力搜索性能更好。

8.1.4 深度模型

1. 这里介绍我们使用的深度模型，整个模型如下图所示。为了简单起见，我们仅在下图中说明了用户行为特征的使用。而其它特征，如用户画像特征、上下文特征在实践中可以毫无障碍地使用。

   • 受点击率预估工作的启发，我们学习树中每个节点的低维embedding ，并使用 attention 模块来软性 softly 搜索相关的行为，从而获得更好的用户 representation 。

     每个节点视为一个 target item 。

   • 为了利用包含时间戳信息的用户行为，我们设计了 block-wise 的 input layer 来区分不同时间窗口中的行为。

     • 历史行为记录可以沿着时间线timeline 被划分为不同的时间窗口。

       通过时间窗口来捕获时间效应，这使得距离当前不同天数的用户历史行为被聚合到不同的 embedding 。另外一种简单做法是：在 attention 中加入时间距离 embedding （例如：距离现在 7 天时，time span = 7 的 embedding ）。

     • 每个时间窗口内的 item embedding 被加权平均，权重来自于激活单元activation unit 。

   激活单元的输入分为三部分：用户侧的历史互动 item 的embedding、目标节点 embedding、以及这两个 embedding 的 element-wise 乘积（捕获二阶交互）。

   • 每个时间窗口的输出以及目标节点的 embedding 被拼接作为神经网络的输入。
   • 在三个全连接层（具有 PReLU 激活以及 batch normalization ）之后，使用 binary softmax 来产生用户是否对候选节点感兴趣的概率。
   • 每个 item 及其对应的叶节点共享相同的 embedding 。
   • 所有 embedding 都是随机初始化的。
   • attention 模块和后续的网络极大地增强了模型的容量capability，也使得用户对候选item 的偏好无法被标准化为内积的形式。
   • 树节点的 embedding 和树结构本身也是模型的一部分。为了最小化损失函数 $ \mathcal L $ ，我们使用采样的节点和相应的特征来训练网络。

   这里无法引入 item 侧的特征，每个 item 视为一个节点，节点只有节点 embedding 而没有辅助信息（例如属性）。

   这种方式会大大扩充样本数量（正样本扩充且负样本扩充）。

   

8.1.5 树的构建和学习

1. 推荐树 recommendation tree 是tree-based 的深度推荐模型的基础部分。

   与多类别multi-class 分类以及多标签multi-label 分类工作不同，其中树用于划分样本空间或 label 空间，我们的推荐树为要检索的 item 建立索引。在 hierarchical softmax 中，单词的层级hierarchy 是根据 WordNet 的专家知识 expert knowledge 建立的。在推荐场景中，并不是每个语料库都能提供具体的专家知识。

   一种直观的替代方法是：基于从数据集抽取的item 共现concurrence 或者 item 相似性similarity ，使用层级聚类 hierarchical clustering 方法构建树。但是聚类树可能非常不平衡，这对于训练和检索是不利的。给定 pair-wise 的 item 相似性，文献《Label embedding trees for largemulti-class tasks》 中的算法提供了一种通过谱聚类spectral clustering 从而将item 递归地分割成子集的方法。然而，谱聚类对于大型语料库是无法scalable 的（它是语料库大小的三次方时间复杂度）。

   在这里，我们重点介绍合理、可行的树构造tree construction和树学习tree learning方法。

2. 树初始化tree initialization：由于我们假设树代表了用户兴趣的层级信息hierarchical information ，所以很自然地以相似的item 被组织在相近的位置close position 的方式来构建树。鉴于类目信息category information 在许多领域中广泛可用，我们直观地提出了一种利用 item 的类目信息来构建初始树initial tree 。

   不失一般性，这里以二叉树为例。

   • 首先，我们对所有类目进行随机排序，并将属于同一类目的 item 以类目内随机顺序放在一起。如果一个item 属于一个以上的类目，则出于唯一性uniqueness ，该item 被随机分配给它所属的某个类目。通过这种方式，我们就可以得到一个 ranked item 列表（基于类目的排序）。

   • 其次，这些 ranked item 被递归地划分为两个相等的部分，直到当前集合仅包含一个 item为止。这可以自顶向下构建一个近似完全的二叉树near-complete binary tree 。

     这使得在树靠近根节点的 level 中，相似的 item （即相同类目）位于相近的位置。

   在我们的实验中，上述基于类目的初始化可以获得比完全随机的树complete random tree 更好的层级hierarchy 和结果。

3. 树结构学习tree learning ：作为模型的一部分，每个叶节点的 embedding 可以在模型训练后学到。然后，我们可以使用学到的叶节点的 embedding 向量来聚类一棵新的树。

   考虑到语料库的规模，我们使用 k-means 聚类算法，因为它具有良好的可扩展性scalability 。在每个聚类 step，根据item 的 embedding 向量将item 分为两个子集。注意，为了得到更平衡的树，这两个子集被调整为相同规模。当仅剩下一个item 时，递归就停止。通过这种方法可以自顶向下地构建二叉树。

   在我们的实验中，当语料库大小约为 400 万时，使用单台机器构建一个聚类树cluster tree 大约需要一个小时。后面的实验结果将显示 tree learning 算法的有效性。

   深度模型deep model 和树结构tree structure 以交替方式联合学习：

   • 构建初始树并训练模型直到收敛。
   • 在训练好的叶节点 embedding 的基础上，通过聚类得到新的树结构。
   • 用所学到的新树再次训练模型。

8.1.6 在线 Serving

1. TDM 在线 Serving 系统如下图所示。输入特征组装assembling 和 item 检索被划分为两个异步阶段：

   • 包括点击、购买、加购物车在内的每个用户行为都会触发实时特征服务器real-time feature server 从而组装assemble 新的输入特征。
   • 一旦收到页面查看请求page view request，user targeting server 将使用预组装pre-assembled 的特征从树中检索候选item。

   如 hierarchical prediction algorithm 所述，检索是 layer-wise 进行的，并且训练好的神经网络用于计算给定输入特征的情况下节点是否是用户喜欢preferred 的节点的概率。

   

2. 预测效率prediction efficiency：TDM 使得高级神经网络在大规模推荐中对 user 和 item 进行交互成为可能，这为推荐系统开辟了一个新的视角。

   值得一提的是，虽然高级神经网络在推断时需要更多的计算，但是整个预测过程的复杂度不会大于 $ O(k\times \log |\mathbb C|\times t) $ ，其中 $ k $ 为所需的结果集合大小， $ |\mathbb C| $ 为语料库大小， $ t $ 为网络单次前向传播的复杂度。在当前 CPU/GPU 硬件条件下，该复杂度上限是可接受的，并且用户侧特征在一次检索中跨不同的节点共享，而一些计算可以根据模型设计进行共享。

   在淘宝展示广告系统Taobao display advertising system 中，实际部署的 TDM DNN 模型平均需要 6ms 左右才能推荐一次。这样的运行时间比后续的点击率预估模型要短，并且不是系统的瓶颈。

8.2 实验

1. 这里我们研究了TDM 的性能，并给出在 MovieLens-20M 和淘宝广告数据集 UserBehavior 上的实验结果。

2. 数据集：实验是在两个带时间戳的大规模真实世界数据集上进行的，来自于 MovieLens 数据集的用户观看电影数据、来自于淘宝的 user-item 行为数据（称作 UserBehavior 数据集）。

   • MovieLens-20M 数据集：该数据集包含带时间戳的user-movie 评级数据。

     当我们处理隐式反馈问题时，通过将评分为4 分（满分5 分）或者4 分以上的评分作为正label、4 分以下的评分作为负label 来二元化binarize 。这是其它工作中常用的方式。

     此外，只有看过至少10 部电影的用户才会被保留。

     我们随机抽取了 1000 个用户作为测试集，另外随机抽取了 1000 个用户作为验证集，剩余用户作为训练集。对于验证集和测试集，user-movie 观看记录中，沿着 timeline 的前半部分作为预测后半部分的已知行为 known behavior 。

   • UserBehavior 数据集：该数据集是淘宝用户行为数据集的子集。

     我们随机挑选了大约 100 万名用户，然后给出了他们在 2017-11-25 ~ 2017-12-03 期间的行为（包括点击、购买、加购物车）。数据的组织形式和 MovieLens-20M 非常相似，即：一个 user-item 行为由 user ID、item ID、item 类目 ID、行为类型behavior type、时间戳组成。item 的类目是从淘宝当前商品分类法commodity taxonomy 的 bottom level 开始的。

     就像我们在 MovieLens-20M 中做的那样，只有至少 10 个行为的用户才会被保留。

     我们随机选择 10000 个用户作为测试集，另外随机选择 10000 个用户作为验证集，剩余用户作为训练集。

   下表总结了预处理后上述两个数据集的主要统计信息。

   

3. 评估指标：我们使用 Precision@M、Recall@M、F-Measure@M 等指标。

   令用户 $ u $ 召回的item 集合为 $ \mathbb P_u $ （其中 $ |\mathbb P_u|=M $ ），用户的ground truth 集合为 $ \mathbb G_u $ 。

   • Precision@M 定义为：

     $ \text{Precision@M}(u) = \frac{|\mathbb P_u\cap \mathbb G_u|}{|\mathbb P_u|} $

   • Recall@M 定义为：

     $ \text{Precision@M}(u) = \frac{|\mathbb P_u\cap \mathbb G_u|}{|\mathbb G_u|} $

   • F-Measure@M 定义为：

     $ \text{F-Measure@M}(u) = \frac{2\times \text{Precision@M}(u) \times \text{Precision@M}(u)}{\text{Precision@M}(u)+ \text{Precision@M}(u)} $

   • 正如我们所强调的，推荐结果的新颖性 novelty 决定了用户体验。现有工作给出了几种方法来衡量推荐item 列表的新颖性。根据其中的一个定义，我们定义 Novelty@M 为：

     $ \text{Novelty@M}(u) = \frac{|\mathbb P_u\backslash \mathbb S_u|}{|\mathbb P_u|} $

     其中 $ \mathbb S_u $ 是用户 $ u $ 有历史交互的item 集合。

   我们在测试集上计算所有用户上述四个指标的均值，从而作为每个方法的评估指标。

4. baseline 方法：

   • FM ：FM 是因子分解任务的框架。我们使用 xLearn 项目提供的 FM 实现。

   • BPR-MF：我们使用矩阵分解形式进行隐式反馈推荐。

     我们使用 《MyMediaLite: A free recommender system library》 提供的 BPR-MF 的实现。

   • Item-CF：基于item 的协同过滤是大规模语料库在生产环境中最广泛使用的个性化推荐方法之一，这也是淘宝上主要的候选item 生成方法之一。

     我们使用阿里巴巴机器学习平台提供的 Item-CF 的实现。

   • YouTube product-DNN：是YouTube 提出的深度推荐方法。在训练中使用了 sampled-softmax ，用户 embedding 和 item embedding 的内积反映了偏好。

     我们在阿里巴巴深度学习平台上实现了 YouTube product-DNN，其输入特征和我们提出的模型相同。预测阶段采用内积空间的精确 kNN 搜索。

   • TDM attention-DNN: tree-based deep model using attention network：是我们提出的方法。树以前文所述的类目信息初始化，并在实验过程中保持不变。

5. 实验配置：

   • 对于 FM, BPR-MF, Item-CF，我们根据验证集调优几个最重要的超参数，即 FM 和 BPR-MF 中的因子数、迭代数，以及 Item-CF 中的邻居数。

   • FM 和 BPR-MF 要求测试集或验证集中的用户在训练集中也有反馈。因此，我们将测试集和验证集的 timeline 中，各自的前半部分的 user-item 交互记录都加入到训练集中。

   • 对于 YouTube product-DNN 和 TDM attention-DNN，node embedding 维度设为 24，因为在我们的实验中，更高的维度不会表现得更好。

   • TDM attention-DNN 三个全连接层的隐单元数量分别为 128、64、24 。根据时间戳，用户行为分为 10 个窗口。

   • 在 YouTube product-DNN 和 TDM attention-DNN中：

     • 对于 MovieLens-200M 数据集，每个隐式反馈我们随机选择 100 个负样本。
     • 对于 UserBehavior 数据集，每个隐式反馈我们随机选择 600 个负样本。

     注意，TDM 的负样本数是所有 level 负样本之和。由于树的性质，我们在接近叶节点的level 采样了更多的负样本。

8.2.1 离线实验

1. 不同方法比较结果如下表的虚线上方所示，每个指标都是测试集中所有用户的均值，并且每种配置我们运行五次并报告五次结果的均值和方差。其中在 MovieLens-20 中以 @10 评估指标，在 UserBehavior 中以 @200 评估指标。

   结论：

   • 我们提出的 TDM attention-DNN 在两个数据集上的大多数指标都显著优于所有 baseline 。

     和排名第二的 YouTube product-DNN 方法相比，在没有过滤的情况下（用户历史互动 item 过滤条件Filtering=None），TDM attention-DNN 在两个数据集上的召回率分别提高了 21.1% 和 42.6% 。该结果证明了 TDM attention-DNN 采用的高级神经网络和 hierarchical tree search 的有效性。

   • 在以内积形式对用户偏好进行建模的方法中，YouTube product-DNN 超越了 BPR-MF 和 FM ，因为前者使用了神经网络。

   • 广泛使用的 Item-CF 方法具有最差的新颖性novelty 结果，因为它对用户已经交互的item 具有很强的记忆性memory 。

   为了提高新颖性，实践中常用的方法是过滤推荐集合中已经交互的 item 。也就是说，最终只能推荐那些新颖的 item 。因此，在一个完全新颖的结果集合中比较 accuracy 是非常重要的。在本实验中，如果过滤后结果集合的大小小于 $ M $ ，则结果集合的大小将补充到 $ M $ 。结果表明（Filtering = Interacted items）：在过滤掉历史已经交互的 item 之后，TDM attention-DNN 在大大超越了所有 baseline 。

   

2. 为了进一步评估不同方法的探索能力exploration ability ，我们通过从推荐结果中排出那些已经历史交互的类目category 来进行实验。每种方法的结果也被要求补足结果集合大小为 $ M $ 的要求。事实上，类目新颖性category-level novelty是目前淘宝推荐系统中最重要的新颖性指标，因为我们希望减少和用户历史交互item 相似的推荐 item 的数量。

   由于 MovieLens20M 总共只有 20 个类目，因此该实验仅在 UserBehavior 数据集上进行，结果如下表所示。以召回率指标为例，可以看到：

   • Item-CF 的召回率只有 1.06%，因为它的推荐结果很难跳出用户的历史行为记录。
   • 和 Item-CF 相比，YouTube product-DNN 获得了更好的结果，因为它可以从整个语料库中探索用户的潜在兴趣。
   • 我们提出的 TDM attention-DNN 在召回率方面比 YouTube product-DNN 高 34.3%。这种巨大的提升对于推荐系统而言是非常有意义的，它证明了更高级的模型对于推荐问题来说是一个巨大的差异enormous difference 。

   

8.2.2 实证研究

1. TDM 变体：为了理解所提出的 TDM 方法本身，我们评估了 TDM 的几种变体：

   • TDM product-DNN：为了证明高级神经网络是否可以使TDM 结果受益，我们测试了 TDM 的变体 TDM product-DNN 。TDM product-DNN 使用 YouTube product-DNN 相同的内积方式。具体而言，TDM attention-DNN中的 attention 模块被删除，并且node embedding 项也从网络输入中删除。 node embedding 和第三个全连接层的输出（没有 PReLU 和 BN）的内积、以及 sigmoid 激活函数构成了新的 binary 分类器。
   • TDM DNN ：为了进一步验证 TDM attention-DNN 模型中 attention 模块带来的增益，我们测试了仅去除激活单元activation unit 的变体 TDM DNN ，即，TDM attention-DNN中所有 item 的权重都是 1.0 。
   • TDM attention-DNN-HS：如前所述，hierarchical softmax: HS 方法不适合推荐。我们测试了 TDM attention-DNN-HS 变体，它使用 positive node 的邻居作为 negative 样本，而不是随机选择负样本。相应地，在 hierarchical prediction algorithm 的检索中，ranking indicator 将从从单个节点的 $ p\left(\hat y_u(n)=1\mid n,u\right) $ 变化为 $ \prod_{n^\prime \in \text{n's ancestors}} p\left(\hat y_u(n^\prime)=1\mid n^\prime,u\right) $ 。另外，attention-DNN 作为网络结构。

   上述变体在两个数据集上的实验结果如下表的虚线下方所示。结论：

   • 相比于 TDM DNN，TDM attention-DNN 在 UserBehavior 数据集上召回率提升了将近 10%， 这表明attention 模块做出了显著的贡献。

   • 相比于 TDM DNN 和 TDM attention-DNN ， TDM product-DNN 表现更差，因为内积方式远不如神经网络交互形式那么强大。

     这些结果表明：在 TDM 中引入高级模型可以显著提高推荐性能。

   • 相比于 TDM attention-DNN ，TDM attention-DNN-HS 效果更差，因为 hierarchical softmax 的公式不适合推荐问题。

   

2. 树的作用role：树是我们提出的 TDM 方法的关键组成部分，它不仅作为检索中使用的索引，而且以从粗粒度到细粒度的层级hierarchy 对语料库进行建模。

   在前文中我们提出，直接进行细粒度推荐比层级化hierarchical 的方式更困难。我们进行实验来证明这个观点。

   下图说明了hierarchical tree search （即 hierarchical prediction algorithm 算法）和暴力搜索（遍历相应 level 的所有节点）的 layer-wise 的 Recall@200 。实验是在 UserBehavior 数据集上使用 TDM-product-DNN 模型进行的，因为这是唯一一种可以使用暴力搜索的变体。测试集中的 ground truth 可追溯到每个节点的祖先，直到根节点为止。

   可以看到：

   • 暴力搜索在高 level （level 8, 9） 稍微优于 tree search，因为那里的节点数很少。

     暴力搜索是基于节点 embedding 的相似度进行检索的。而 tree search 是基于 $ p\left(\hat y_u(n)=1\mid n,u\right) $ 进行检索的。

     另外，这里是预测阶段的性能比较。二者都是训练好的同一个 TDM-product-DNN 模型。

   • 一旦一个 level 中的节点数增加，tree search 就比暴力搜索获得更好的召回结果，因为 tree search 可以在高level 中排出那些低质量的结果，这降低了低 level 问题的难度。

     越靠近叶节点则噪音越大，基于暴力搜索得到的 top k 节点越容易陷入过拟合。

   这些结果表明：树结构中包含的层级信息有助于提高推荐的精确性preciseness 。

   

3. 树学习tree learning ：前面我们提出了树初始化tree initialization 和树学习tree learning 算法。下表给出了初始树 initial tree 和学习树learnt tree之间的比较结果。这是 TDM attention-DNN 模型在 （@200）UserBehavior 数据集上的不同树结构的比较结果。

   初始树：树被初始化之后，树结构后续不再变化；学习树：树被初始化之后，反复迭代从而学习树结构。

   可以看到：学习树结构learnt tree structure 的模型显著优于初始树结构initial tree structure的模型。在过滤交互类目的实验中，和初始树相比，学习树的召回率从 4.15% 提升到 4.82% ，大大超越了 YouTube product-DNN 的 3.09% 和 Item-CF 的 1.06% 。

   

   为了进一步比较这两种树，我们在下图中展示了 UserBehavior 数据集上对初始树和学习树得到的测试集损失曲线和测试集Recall@200曲线 。下图表明：使用学习树，模型收敛到更好的结果。

   以上结果证明，树学习算法能够改善 item 的层级结构hierarchy，从而进一步促进训练和预测。

   

8.2.3 在线实验

1. 我们在真实流量的淘宝展示广告平台Taobao display advertising platform 上对提出的 TDM 方法进行了评估。实验在淘宝 App 首页的 “猜你喜欢” 栏目进行，时间为2018-01-22 ~ 2018-01-28 连续一周。我们使用两个在线指标online metric 来评估效果：

   • 点击率click-through rate: CTR：CTR = 点击量/曝光量。
   • 每千次曝光收入revenue per mille: RPM：RPM = 广告收入Ad revenue / 曝光量 * 1000 。

   在我们的广告系统中，广告主对一些给定的 ad cluster 竞价。大约有 140 万个 cluster，并且每个 ad cluster 包含数百或者数千个类似的广告。实验在 ad cluster 粒度上进行的，从而与现有系统保持一致。

   对比的方法是逻辑回归的混合mixture，它用于从那些相互作用的 cluster 中挑选出更好的结果。这是一个很强的 baseline。

   由于系统中有很多阶段stage，如 CTR 预估、ranking ，因此在线部署和评估提出的 TDM 方法是一个庞大的工程，涉及整个系统的链接和优化。目前为止，我们已经完成了 TDM DNN 第一版的部署，并在线评估了其效果提升。每个比较的 bucket 都有 5% 的在线流量。

   值得一提的是，有几种在线同时运行的推荐方法。它们从不同的角度进行努力，并且推荐结果被合并在一起从而用于后续阶段。TDM 只替换其中最有效的一个，同时保持其他模块不变。下表列出了采用 TDM 所在的测试 bucket 的指标平均提升比例。

   可以看到：

   • TDM 方法的点击率提升了 2.1% 。这一提升表明，所提出的方法可以为用户召回更准确accurate 的结果。
   • TDM 方法的RPM 指标提升了 6.4%，这意味着 TDM 方法也可以为淘宝广告平台Taobao advertising platform 带来更多的收入。

   目前 TDM 已经部署到主要的在线流量中，我们认为上述改进只是一个大型项目的初步结果，还有进一步改进的空间。