Question

1. 个性化personalization 和推荐系统 recommendation systems 目前已经被部署在大型互联网公司的各种任务中，包括广告点击率预估CTR prediction 和排序 ranking。尽管这些方法已经有很长的历史，但是直到最近这些方法才包含神经网络。有两个基本观点primary perspectives 有助于个性化和推荐的深度学习模型的架构设计architectural design 。

   • 第一种观点来自推荐系统。这些系统最初采用内容过滤content filtering，其中一群专家将产品划分为不同的类目categories，用户选择他们喜欢的类目，而系统根据用户的偏好进行匹配。

     该领域随后发展为使用协同过滤collaborative filtering，其中推荐是基于用户历史的行为，例如对item 的历史评分。

     邻域 neighborhood方法通过将用户和item 一起进行分组grouping 从而提供推荐。

     潜在因子latent factor方法通过矩阵分解技术从而使用某些潜在因子来刻画用户和item。

     这些方法后来都取得了成功。

   • 第二种观点来自预测分析 predictive analytics，它依靠统计模型根据给定的数据对事件的概率进行分类classify 或预测predict 。

     预测模型从简单模型（例如线性模型和逻辑回归）转变为包含深度网络的模型。为了处理离散数据categorical data ，这些模型采用了 embedding 技术从而将 one-hot 向量和 multi-hot 向量转换为抽象空间abstract space 中的稠密表示dense representation 。这个抽象空间可以解释为推荐系统发现的潜在因子空间space of the latent factors 。

   在论文 《Deep Learning Recommendation Model for Personalization and Recommendation Systems》 中，论文介绍了一个由上述两种观点结合而成的个性化模型。该模型使用 embedding 来处理代表离散数据的稀疏特征sparse features、使用多层感知机multilayer perceptron: MLP 来处理稠密特征 dense features，然后使用 《Factorization machines》 中提出的统计技术显式的交互interacts 这些特征。最后，模型通过另一个 MLP 对交互作用进行后处理post-processing从而找到事件的概率。

   作者将这个模型称作深度学习推荐模型 deep learning recommendation model: DLRM，如下图所示。该模型的 PyTorch 和 Caffe2 的实现已经发布。

   此外，作者还设计了一种特殊的并行化方案，该方案利用 embedding tables 上的模型并行性model parallelism 来缓解内存限制 memory constraints，同时利用数据并行性data parallelism 从全连接层扩展 scale-out 计算。作者将 DLRM 与现有的推荐模型进行了比较，并在 Big Basin AI 平台上实验了 DLRM 的性能，证明了它作为未来算法实验algorithmic experimentation 、以及系统协同设计system co-design 的 benchmark 的有效性。

   

12.1 模型设计和架构

1. 这里我们将描述 DLRM 的设计。我们将从网络的高级组件high level components 开始，并说明如何以及为什么将它们以特定方式组装assembled 在一起，以及对未来的模型设计产生的影响。

   然后我们描述组成模型的低级算子low level operators 和原语primitives ，以及对未来的硬件和系统设计产生的影响。

12.1.1 DLRM 组件

1. 通过回顾早期模型，我们可以更容易理解 DLRM 的高级组件。我们避免全面的科学文献综述，而将重点几种在早期模型中使用的四种技术上，这些技术可以被解释为 DLRM 的重要高级组件。

2. Embedding：为了处理离散数据，embedding 将每个类目 category 映射到抽象空间abstract space 中的稠密表示dense representation。

   具体而言，每个 embedding lookup 可以被解释为使用一个 one-hot 向量 $ \mathbf{\vec e}_i\in \mathbb R^{m\times 1} $ （第 $ i $ 位为1、其它位为0，索引 $ i $ 代表了第 $ i $ 个类目 ）来获得 embedding table $ \mathbf W\in \mathbb R^{m\times d} $ 中的相应行向量 row vector：

   $ \mathbf{\vec w}_i^\top = \mathbf{\vec e}_i^\top \mathbf W $

   其中 $ m $ 为类目总数， $ d $ 为抽象空间的维度。

   在更复杂的场景中，embedding 也可以表示多个item 的加权组合，其中包含一个 multi-hot 向量的权重：

   $ \mathbf{\vec a}^\top = [0,\cdots,0,a_{i_1},\cdots,a_{i_k},0,\cdots,0]\in \mathbb R^{1\times m} $

   其中 ： $ i_1,\cdots,i_k $ 代表对应的 item ； $ a_i\ne 0, i=i_1,\cdots,i_k $ 代表这些 item 的权重。

   包含 $ t $ 个 embedding lookup 的 mini-batch 可以写作：

   $ \mathbf S = \mathbf A^\top \mathbf W\in \mathbb R^{t\times d} $

   其中 $ \mathbf A = [\mathbf{\vec a}_1,\cdots,\mathbf{\vec a}_t]\in \mathbb R^{m\times t} $ 为一个稀疏矩阵。

   DLRM 利用 embedding tables 将离散特征映射到稠密表示。然而，即使设计了这些有意义的 embedding 之后，如何利用它们来生成准确的预测？为了回答这个问题，我们回到潜在因子方法latent factor methods 。

3. 矩阵分解Matrix Factorization：回忆一下，在推荐问题的典型公式中，我们得到了对某些item 进行评分的某些用户的集合 $ \mathbb S $ 。其中，集合 $ \mathbb S $ 由元组 $ (i,j) $ 索引组成，表示第 $ j $ 个用户在第 $ i $ 个 item 上已经评分。我们用向量 $ \mathbf{\vec w}_i\in \mathbb R^{d\times 1} $ 来表示represent 第 $ i $ 个 item 、用向量 $ \mathbf{\vec v}_j\in \mathbb R^{d\times 1} $ 来表示第 $ j $ 个用户，从而找到所有评分ratings 。

   矩阵分解方法通过最小化以下公式来求解这个问题：

   $ \min\sum_{(i,j)\in \mathbb S} r_{i,j} - \mathbf{\vec w}_i^\top \mathbf{\vec v}_j $

   其中 $ r_{i,j}\in \mathbb R $ 为第 $ j $ 个用户在第 $ i $ 个 item 上的评分。

   令 $ \mathbf W^\top=[\mathbf{\vec w}_1,\cdots,\mathbf{\vec w}_m]\in \mathbb R^{m\times d} $ 、 $ \mathbf V^\top=[\mathbf{\vec v}_1,\cdots,\mathbf{\vec v}_n]\in \mathbb R^{n\times d} $ ，我们可以将完整的评级矩阵 $ \mathbf R=[r_{i,j}]\in \mathbb R^{m\times n} $ 近似为矩阵乘积：

   $ \mathbf R\simeq \mathbf W\mathbf V^\top $

   其中 $ m $ 为总的 item 数量， $ n $ 为总的用户数量。

   注意： $ \mathbf W $ 和 $ \mathbf V $ 可以解释为两个 embedding tables，其中每一行代表潜在因子空间latent factor space 中的 user/item。这些 embedding 向量的内积可以得出对评级有意义的后续预测，这是因子分解机factorization machines 和 DLRM 设计的关键观察。

4. 因子分解机Factorization Machine：在分类问题中，我们要定义一个从输入数据点 $ \mathbf{\vec x}\in \mathbb R^{n} $ 到target label $ y\in Y $ 的预测函数 $ \phi:\mathbb R^n\rightarrow Y $ 。例如，我们可以通过定义 $ Y=\{+1,-1\} $ 来预测点击率click-through rate: CTR，其中 +1 表示点击label、-1 表示未点击label 。

   因子分解机Factorization machines: FM 通过以下定义形式的模型，将二阶交互second-order interactions 融合到带有离散数据的线性模型中：

   $ \hat y = b + \mathbf{\vec w}^\top \mathbf{\vec x} + \mathbf{\vec x}^\top \text{upper}\left(\mathbf V \mathbf V^\top\right)\mathbf{\vec x} $

   其中：

   • $ \mathbf V\in \mathbb R^{n\times d}, \mathbf{\vec w}\in \mathbb R^n,b\in \mathbb R $ 为模型参数，且 $ d\ll n $ 。
   • upper(.) 函数严格选择矩阵的上三角部分。

   FM 和多项式核polynomial kernel 的支持向量机SVM 显著不同，因为FM 像矩阵分解一样将二阶交互矩阵分解为潜在因子latent factor （或 embedding 向量），从而更有效地处理稀疏数据。

   通过仅捕获不同 embedding 向量pair 对之间的交互，FM 显著降低了二阶交互的复杂度，从而产生线性计算复杂度。

   根据原始公式，FM 的算法复杂度为 $ O(n^2d) $ ，但是经过数学转换之后，计算复杂度降低到 $ O(nd) $ 。

5. 多层感知机Multilayer Perceptrons：最近机器学习的成功很大程度上归功于深度学习的兴起。其中，最基本的模型是多层感知机multilayer perceptron: MLP ，它是一个由全连接层fully connected layers: FC 和激活函数 $ \sigma: \mathbb R\rightarrow \mathbb R $ 交替组成的预测函数prediction function：

   $ \hat {\mathbf {\vec y}} = \mathbf W_k\sigma\left(\mathbf W_{k-1}\sigma\left(...\sigma_1\left(\mathbf W_1\mathbf{\vec x + \mathbf{\vec b}_1}\right)...\right) + \mathbf{\vec b}_{k-1}\right) + \mathbf{\vec b}_k $

   其中权重矩阵 $ \mathbf W_l\in \mathbb R^{d_l\times d_{l-1}} $ ，bias 向量 $ \mathbf{\vec b}_l\in \mathbb R^{d_l} $ ， $ d_0 = n $ 。

   这些方法被用来捕获更复杂的交互interactions 。例如，已经表明：给定足够的参数、具有足够深度depth 和宽度 width 的 MLP 能够以任何精度precistion 拟合数据。

   这些方法的变体已经广泛应用于各种application ，包括计算机视觉和 NLP。一个具体的例子是神经协同过滤 Neural Collaborative Filtering: NCF 被用作 MLPerf benchmark 的一部分，它使用 MLP 而不是内积来计算矩阵分解中 embedding 之间的交互。

12.1.2 DLRM 架构

1. 目前为止，我们已经描述了推荐系统和预测分析中使用的不同模型。现在，让我们结合它们的直觉intuitions 来构建 state-of-the-art 的个性化模型。

   令用户和 item 使用很多连续continuous 的、离散categorical 的特征来描述。

   • 为了处理离散特征，每个离散特征将由相同维度的 embedding 向量来表示，从而推广了矩阵分解中潜在因子的概念。
   • 为了处理连续特征，所有的连续特征整体上将被一个 MLP 转换（这个 MLP 我们称之为 bottom MLP 或者 dense MLP），这将产生和 embedding 向量相同维度的 dense representation 。

   注意：每个离散特征会得到一个 embedding，而所有连续特征整体才能得到一个 embedding 。

   我们将根据 FM 处理稀疏数据的直觉，通过 MLP 来显式计算不同特征的二阶交互。这是通过获取所有 representation 向量（包括每个离散特征的 embedding 向量、连续特征整体的 representation 向量）之间的 pair 对的内积来实现的。

   这些内积和连续特征 representation （即经过原始连续特征经过 bottom MLP 之后得到的）拼接起来，馈入另一个 MLP（我们称之为 top MLP 或者 output MLP）。最终这个 MLP 的输出馈入到一个 sigmoid 函数从而得到概率。

   我们将这个模型称作 DLRM。

   top MLP 的特征有：显式二阶交互特征、连续representation 特征。这里并没有馈入一阶 embedding 特征。

2. 和早期模型的比较：许多基于深度学习的推荐模型使用类似的基本思想来生成高阶项 term 从而处理稀疏特征。例如：Wide and Deep、Deep and Cross、DeepFM、xDeepFM 网络等等，它们设计了专用网络specialized networks 来系统地构建高阶交互 higher-order interactions 。然后，这些网络将它们专用网络和 MLP 的结果相加，并通过线性层和sigmoid 激活函数产生最终的概率。

   DLRM 特别地模仿因子分解机，以结构化方式与 embedding 交互，从而在最终 MLP 中仅考虑 embedding pair 对之间的内积所产生的的交叉term，从而显著降低了模型的维度。我们认为，在其他网络中发现的、超过二阶的更高阶交互可能不一定值得额外的计算代价和内存代价。

   DLRM 和其它网络之间的主要区别在于：网络如何处理 embedding 特征向量及其交叉项 cross-term 。具体而言：

   • DLRM（以及 xDeepFM）将每个embedding 向量解释为表示单个类目category 的单元unit，交叉项仅在类目之间产生。

   • 像 Deep and Cross 这样的网络将embedding 向量中的每个元素视为单元，交叉项在元素之间产生。

     因此，Deep and Cross 不仅会像 DLRM 那样通过内积在不同embedding 向量的元素之间产生交叉项，而且会在同一个embedding 向量内的元素之间产生交叉项，从而导致更高的维度。

12.2 并行性

1. 现代的个性化和推荐系统需要大型复杂的模型来利用大量的数据。DLRM 尤其包含大量参数，比其它常见的深度学习模型（例如 CNN、RNN、GAN）多几个数量级。这导致训练时间长达数周或者更长。因此，更重要的是有效地并行化这些模型，以便在实际数据规模上解决这些问题。

2. 如前所述，DLRM 以耦合的方式coupled manner 处理离散特征（通过 embedding）和连续特征（通过 bottom MLP）。 embedding 贡献了大部分参数，每个lookup table 都需要超过几个 GB 的内存，使得 DLRM 的内存容量和带宽bandwidth代价昂贵。

   • 由于embedding 太大，因此无法使用数据并行data parallelism ，因为数据并行需要在每个设备上拷贝超大的 embedding。在很多情况下，这种内存限制需要将模型分布在多个设备上，从而满足内存容量要求。
   • 另一方面，MLP 参数在内存中较小，但是却有相当可观的计算量。因此，对于 MLP 而言，数据并行是首选的，因为这样可以在不同的设备上同时处理样本，并且仅在累计更新accumulating updates时才需要通信。

   我们的并行化 DLRM 联合使用模型并行model parallelism和数据并行 data parallelism：针对embedding 使用模型并行、针对 MLP 使用数据并行，从而缓解 embedding 产生的内存瓶颈memory bottleneck，同时并行化 MLP 上的前向传播和反向传播计算。

   由于 DLRM 的体系结构和较大的模型尺寸，因此将模型并行和数据并行相结合是 DLRM 的独特要求。Caffe2 或 PyTorch （以及其它流行的深度学习框架）均不支持这种组合并行性，因此我们设计了一个自定义的实现。我们计划在未来的工作中提供其详细的性能研究。

3. 在我们的设置setup中，top MLP 和交互算子interaction operator 要求从 bottom MLP 和所有 embedding 中访问部分 mini-batch。由于模型并行已用于在设备之间分布 embedding，因此这需要个性化的 all-to-all 通信。

   在 embedding lookup 的最后，每个设备都针对 mibi-batch 中的所有样本，将对应的 embedding table 中的embedding 向量驻留在这些设备上。需要驻留的embedding 向量需要沿着 mibi-batch 维度分割，并传送到适当的设备，如下图所示（如黄色embedding 向量都传送到 Device 3 ）。

   PyTorch 和 Caffe2 都不提供对模型并行的原生支持，因此我们通过将 embedding 算子显式映射到不同的设备来实现它。然后使用 butterfly shuffle 算子实现个性化的all-to-all 通信，该算子将生成的 embedding 向量适当的分片slice，并将其传输到目标设备 target device 。在当前版本中，这些传输是显式拷贝，但是我们打算使用可用的通信原语（如 all-gather 和 send-recv）进一步优化这一点。

   下图为用于 all-to-all 通信的butterfly shuffle 。

   注意，目前 pytorch.distributed package 已经支持模型并行、数据并行，也支持个性化的 all-to-all 通信。

   

4. 我们注意到，对于数据并行 MLP，反向传播中的参数更新以 allreduce 进行积累accumulated，并以同步synchronous 的方式应用于每个设备上的拷贝参数replicated parameters ，从而确保每个设备上的更新参数updated parameters 在每次迭代之前都是一致consistent 的。

   • 在 PyTorch 中，通过 nn.DistributedDataParallel 和 nn.DataParallel 模块启用数据并行，这些模块在每个设备上拷贝模型并插入allreduce 以及必要的依赖。
   • 在 Caffe2 中，我们在梯度更新之前人工插入 allreduce 。

1.3 实验

1. 为了衡量模型的准确性accuracy、测试模型的整体性能、并描述各个算子operator 的特征，我们需要为DLRM 创建或获取一个数据集。

   我们提供了三种类型的数据集：随机数据集random dataset、人工合成数据集synthetic dataset、公共数据集public dataset 。从系统的角度来看，前两个数据集可用于试验模型。具体而言，它允许我们通过动态生成的数据来试验不同的硬件属性和瓶颈，同时消除对数据存储系统的依赖。后者允许我们对真实数据集进行实验，并度量模型的的准确性accuracy。

   • 随机数据集：回忆一下，DLRM 接受连续continuous 特征和离散categorical 特征作为输入。

     • 对于连续特征，可以通过使用 numpy.random package 的 rand 或者 randn 调用具有默认参数的均匀分布或正态分布（高斯分布）生成随机向量来建模。 然后可以通过生成一个矩阵来获得一个 mini-batch 的输入，其中矩阵的每一行代表 mini-batch 中的一个样本。

     • 对于离散特征，我们需要确定给定的的 multi-hot 向量中有多少个非零元素。benchmark 允许非零元素数量是固定的、或者是 1~k 范围内的一个随机数。

       然后，我们生成相应数量的整数索引，数量范围在 1~m 范围内，其中 m 为 embedding 矩阵 $ \mathbf W $ 的行数。

       最后，为了创建一个 mini-batch 的 lookup，我们拼接上述索引，并用lengths （Caffe 中的 SparseLengthsSum）、或者 offsets （PyTorch 中的nn.EmbeddingBag）来描述每个单独的 lookup 。

   • 人工合成数据集：有很多理由支持对应于离散特征的索引的自定义生成。例如，如果我们的application 使用一个特定的数据集，但出于隐私的目的我们不愿意共享它，那么我们可以选择通过索引分布来表达离散特征。这可能会替代联邦学习federated learning 等应用于 application 中的隐私保护技术。此外，如果我们想要测试系统组件system components，例如研究内存行为memory behavior，我们可能希望在合成的 trace 中捕获原始 trace 访问的基本局部性fundamental locality 。

     让我们说明如何使用合成数据集。假设我们有索引的 trace，这些索引对应于某个离散特征的所有 embedding lookup 轨迹。我们可以在这个 trace 中记录去重访问unique accesses 和重复访问repeated accesses 之间的距离频次，然后生成合成 trace。具体生成算法参考原始论文。

   • 公共数据集：Criteo AI Labs Ad Kaggle 和 Criteo AI Labs Ad Terabyte 数据集是公开的数据集，由用于广告点击率预测的点击日志组成。

     每个数据集包含 13 个连续特征和 26 个离散特征。通常，连续特征使用简单的对数变换 log(1+x) 进行预处理。离散特征映射到相应的 embedding index，而未标记的离散特征映射到 0 或者 NULL。

     • Criteo Ad Kaggle 数据集包含 7 天内的 4500 万个样本，每天的样本量大致相等。在实验中，通常将第 7 天拆分为验证集和测试集，而前面6 天用作训练集。
     • Criteo Ad Terabyte 数据集包含 24 天的样本，其中第 24 天分为验证集和测试集，前面 23 天用作训练集。每天的样本量大致相等。

2. 模型配置：DLRM 模型在 PyTorch 和 Caffe2 框架中实现，可以在 Github 上获得。模型分别使用 fp32 浮点数作为模型参数，以及 int32(Caffe2)/int64(PyTorch) 作为模型索引。实验是在 BigBasin 平台进行的，该平台具有双路 Intel Xeon 6138 CPU @ 2.00GHz 以及 8 个 Nvidia Tesla V100 16GB GPUs 。

3. 我们在 Criteo Ad Kaggle 数据集上评估了模型的准确性accuracy，并将 DLRM 和 Deep and Cross network: DCN 的性能进行了比较，后者没有进行额外的调优。我们和 DCN 进行比较，因为它是在相同数据集上具有综合结果comprehensive results 的少数模型之一。

   • DLRM 既包含用于处理连续特征的 bottom MLP（该 bottom MLP 分别由具有 512/256/64 个节点的三个隐层组成），又包括top MLP （该 top MLP 分别由具有 512/256 个节点的两个隐层组成）。
   • DCN 由六个 cross layer 和一个具有 512/256 个节点的深度网络组成。embedding 的维度为 16。

   这样产生的 DLRM 和 DCN 两者都具有大约 540M 的参数。

   我们使用 SGD 和 Adagrad 优化器绘制了两个模型在完整的单个 epoch 内的训练准确率（实线）、验证准确率（虚线）。我们没有使用正则化。

   可以看到：DLRM 获得了稍高的训练准确率和验证准确率，如下图所示。我们强调，这没有对模型的超参数进行大量的调优。

   DLRM 和 DCN 都没有经过超参数调优，因此实验结果的对比没有任何意义。

   

4. 为了分析我们模型在单设备上的性能，我们考虑了一个具有8 个离散特征、512 个连续特征的模型。每个离散特征都通过一个包含 1M 个向量的 embedding table （即类目总数有1M ）进行处理，向量维度为 64。而连续特征被组装assembled 为一个 512 维的向量。bottom MLP 有两层，而 top MLP 有四层。我们让具有 2048K 个随机生成样本的数据集上分析了该模型，其中 mini-batch 的 batch size = 1K 。

   Caffe2 中的这个模型实现在 CPU 上运行大约 256 秒，在 GPU 上运行大约 62 秒，每个算子的分析如下图所示。正如预期所示：大部分时间都花在了执行 embedding lookup 和全连接层上。在 CPU 上，全连接层占了很大一部分计算，而 GPU 上全连接层的计算几乎可以忽略不计。