阿里TDM召回算法

重点：和头条的召回算法一样，这里基本需要掌握，样本是怎么构建的？模型是怎么训练的？线上是怎么召回的？

Learning Tree-based Deep Model for Recommender Systems

论文链接：https://arxiv.org/pdf/1801.02294.pdf

参考文章：阿里TDM：Tree-based Deep Model - 知乎

阿里妈妈TDM模型详解 - 知乎

源码实现：Issues · alibaba/x-deeplearning · GitHub

1 INTRODUCTION

1：据我们所知，TDM 是第一种可以在大型语料中使用任意高级模型的召回方法。受益于分层树搜索，TDM 实现了log层次的复杂度

2：TDM 可以帮助更准确地找到新颖但有效的推荐结果，因为探索了整个语料库

3：除了更高级的模型，TDM 还通过分层搜索来提升推荐准确度，将

大问题分解成小问题，由易到难依次解决。

3：作为一种索引，树结构也可以学习到item和集合的最优层次结构（整棵树中，最下面叶子节点是item，其余从上到下 是从复杂到简单的集合），以便更有效地检索，这反过来又促进了模型的训练。

我们采用允许联合训练的树学习方法神经网络和树结构。

4：我们对两个大型真实世界数据集进行了大量实验，结果表明 TDM 优于现有的方法。

值得一提的是，还研究了基于树的方法在语言模型工作中使用分层 softmax [24]，但它与所提出的 TDM 不仅在动机上而且在公式上都不同。在下一个词预测问题中，传统的 softmax必须计算归一化项以获得任何一个单个单词的概率，这是非常耗时的。分层 softmax使用树结构，将下一个词的概率转换为沿树路径的节点概率。这样的方法将下一个词概率的计算复杂度降低到log程度。然而，在推荐问题中，目标是在整个语料库中搜索那些最喜欢的项目集合，这是一个检索问题。层次分明softmax 树，父节点的最优不能保证最优的低级节点在它们的子节点中，并且所有项目仍然需要遍历以找到最佳的。因此，它不适合这样的检索问题。为了解决检索问题，我们提出了一个类似最大堆的树公式并引入深度神经网络对树进行建模，形成高效的大规模推荐的方法。以下部分将显示其配方上的差异和性能上的优越性。此外，分层 softmax 采用单个隐藏针对特定自然语言处理问题的层网络，而所提出的 TDM 方法适用于任何神经网络结构。

提出的基于树的模型是适用于所有人的通用解决方案。本文的其余部分是组织如下：在第2节中，我们将介绍淘宝展示广告的系统架构。 第3节将给出详细介绍提出的基于树的深度模型的形式化。 而第 4 节将描述基于树的模型如何服务online。 大规模基准数据集的实验结果和淘宝广告数据集如第 5 节所示。最后，第 6 节对我们的工作进行了总结。

3 TREE-BASED DEEP MODEL

在这部分中，我们首先介绍我们基于树的模型中使用的树结构，以给出一个整体概念。 其次，我们介绍分层 softmax [24] 来说明为什么它的公式不适合推荐。 之后，我们给出一个新的最大堆树公式并展示如何训练基于树的模型。然后，介绍了深度神经网络架构。 最后，我们展示了如何构建和学习基于树的树模型。

树中有N个节点。 ci代表item，只存在于叶子节点中；而那些非叶节点是粗粒度的概念。 我们假设节点 n1 总是根节点。 一个例子树，其中每个圆圈代表一个节点，节点数是它的索引。 树共有8个叶子节点，每个叶子节点对应语料库中的一个item

借助树结构，我们首先介绍分层 softmax 以帮助理解它与我们的 TDM 的区别。在分层 softmax 中，树中的每个叶节点 n 从根到节点都有其唯一的编码。 例如，如果我们将 1 编码为选择左分支，0 选择右分支，n9 的图2树中的编码为110，n15的编码为000。记bj(n)为j级节点n的编码（j级节点的意思是，前面图中一共有3个节点，j的取值就是1 2 3）。 在分层 softmax 的公式中，给定上下文的下一个词的概率，用公式表达为

这是一个累乘器，第一次在context的特征下求出第一层的节点概率，在这个基础上求出第二层的每个节点的概率,..w代码一共有几层节点，上面的图中w=3，lj(n)是j层节点的父节点

hierarchical softmax有两个缺点，一是模型需要遍历整个语料库，这样不适合大的语料库；二是树中的每个非叶节点都被训练为一个二分类，但如果两个节点是树中的邻居，它们可能是相似的。在推荐场景，用户很可能对两者都感兴趣，分层 softmax 的模型侧重于区分最优和次优选择，从全局的角度这可能会失去区分能力。如果使用greedy beam search检索那些最可能的叶节点，一旦做出错误的决定，模型可能无法在较低的低质量候选者中找到相对更好的结果水平。 YouTube 的工作 [7] 说他们尝试了分层 softmax 来学习用户和项目嵌入，但它的性能比采样的 softmax [16]差些

3.3 Tree-based Model Formulatio

为了解决最优选的top-k检索问题，我们提出了一个类似于树概率公式的最大堆。最大堆树是一种树结构，对于每个用户，其中每个非叶节点 n在第 j 层满足以下等式

其中p(n|u)表示的就是用户u对j层节点n感兴趣的概率，α(j)是归一化因子，从上式可以得出，用户u对j层节点n感兴趣的概率，等于用户对该节点的子节点的偏好概率的最大值

上面是说明了如何构建样本，下面说明如果构建损失函数

3.4.

请注意，提出的抽样方法与分层 softmax 中的底层完全不一样。 与分层 softmax方法相比，softmax方法会导致模型产出最优和次优结果，我们为每个正节点随机选择同一级别的负样本。 这种方法使每层的鉴别器都是一个级别内的全局鉴别器。 每个级别的全局判别器可以独立做出精确的决策，而不依赖于上层决策的优劣。 全局区分能力对于分层推荐方法非常重要。 它确保即使模型选错了一个父节点，那些相对较好的节点而不是非常糟糕的节点也可以由下面模型选择出

给定推荐树和优化模型，详细的分层预测算法在算法 1 中描述。检索过程是分层和自上而下的。 假设期望的候选项目编号是 k。 对于大小为 C 的语料库|C|，最多遍历 2 ∗ k ∗ log |C| 节点可以得到一个完整的二叉树中的最终推荐集。节点数需要遍历的是对数关系，这使得高级二元概率模型成为可能

构造完训练样本后，可以利用DIN（这里可以是任何先进的模型）承担用户兴趣判别器的角色，输入就是每层构造的正负样本，输出的是（用户，节点）对的兴趣度，将被用于检索过程作为寻找每层Top K的评判指标。如下图：在用户特征方面仅使用用户历史行为，并对历史行为根据其发生时间，进行了时间窗口划分。在节点特征方面，使用的是节点经过embedding后的向量作为输入。此外，模型借助attention结构，将用户行为中和本次判别相关的那部分筛选出来，以实现更精准的判别。

推荐树是基于树的推荐树的基础部分的深度推荐模型。与多分类和多标签分类工作 [26, 32] 不同，树用于划分样本或标签，我们的推荐树索引项目以供检索。在分层 softmax [24] 中，单词层次结构是根据 WordNet [21] 的专家知识构建的。在推荐场景下，并不是每个语料库都能提供特定的专家知识。一种直观的替代方法是根据从数据集中提取的项目并发性或相似性，使用层次聚类方法构建树。但是簇状树可能相当不平衡，不利于训练和检索。给定的成对物品相似度，[2] 中的算法给出了一种分割物品的方法通过谱聚类递归地分成子集[25]。然而，谱聚类的可扩展性不够（三次时间复杂度 w.r.t.语料库大小）用于大规模语料库。在本节中，我们重点介绍合理可行的树构建和学习方法

树初始化。由于我们假设树代表用户兴趣的层次信息，很自然地将树建立在一种将相似物品组织在相近位置的方式。给定的该类别信息在许多领域都有广泛的可用，我们直观地提出了一种利用项目类别的方法构建初始树的信息。不失一般性，我们本节以二叉树为例。首先，我们对所有类别随机打乱，并将属于同一类别的项目在类别内随机顺序放在一起。如果一个项目属于多个类别，则该项目被随机分配到其一。这样，我们就可以得到一个排序项的列表，这些排序项递归地减半为两个相等的部分，直到当前集合只包含一个项，这可以自顶向下构造一个近乎完整的二叉树。以上那种基于类别的初始化可以获得更好的层次结构和结果在我们的实验中，不是一个完整的随机树。

树学习。 作为模型的一部分，可以在模型训练后学习每个叶节点的嵌入。 然后我们使用学习到的叶子节点的嵌入向量来聚类一棵新树。 考虑到语料库大小，我们使用 k-means 聚类算法，因为它具有良好的可扩展性。 在每一步，item根据自身的嵌入向量聚类到两个子集中去。 注意调整两个子集等于一个更平衡的树。 只有当递归停止只剩下1个item，这样就可以构造一个二叉树。 在我们的实验中，在语料大小在400万左右的情况下，构建这样的聚类树大约需要一个小时，使用一台机器。 第 5 节中的实验结果将显示给定树学习算法的有效性。