DLRM

有在真实线上实践的同学应该都有过各自的思考,其实我觉得这里边的思路相关同学都是了解的,模型结构也不是壁垒,许多推荐系统问题在实践中更偏向于工程问题。像现今的开源框架都无法支持大规模推荐系统,所以各家其实都有自研的框架和配套设施,去解决海量用户&产品等对应的embeddings,合适的online training等等问题。

博客里latex公式显示的更好些

另外发个广告,字节跳动抖音火山技术团队开启2020届校招提前批,失败也不影响正常秋招流程, 需要内推可发我邮箱wangmhwd@gmail.com or wangminghui.wd@bytedance.com,社招同学也欢迎,算法,大数据,服务端等都需要

简介

目前个性化推荐有两个主要的方向,现在基本都投奔了深度学习的怀抱中。

the view of recommendation systems

早期系统雇佣专家们来对产品进行分类,用户选择他们喜好的类别并基于他们的偏好进行匹配。此领域后来演变成了协同过滤,推荐基于用户过去的行为,比如对产品的打分。Neighborhood methods将用户和产品分组并用矩阵分解来描述用户和产品的latent factors,获得了成功。

the view of predictive analytics

用统计学模型去分类或预测给定数据的事件概率。预测模型从原来的用简单的linear and logistic regression建模转向了用deep networks。为了处理类别特征,一般采用embeddings,将one-hot或multi-hot vectors转换到抽象空间的dense respresentations。这里的抽象空间其实也就是推荐系统中的latent factors空间。

本文结合了上边的两种角度,模型使用embeddings处理稀疏特征,MLP处理稠密特征,然后用统计技术进行显示的特征交叉。最后用另一个MLP来处理交差后的特征,得到事件的概率。我们将这个模型称为RLRM,见图1。Pytorch&Caffe2开源实现地址


模型设计&结构

Components of DLRM

Embeddings

处理类别特征时,一般使用embedding,实现的时候其实是搞了个lookup table,然后去查对应类别的embedding,所以one-hot vector $e_i$就相当于是embedding lookup(对位i是1,其他为0),embedding table $W \in \mathbb{R}^{m \times d}$

\boldsymbol{w}{i}^{T}=\boldsymbol{e}{i}^{T} W

embedding也可以被理解为是多个items的带权组合,mulit-hot vector \boldsymbol{a}^{T}=\left[0, \ldots, a_{i_{1}}, \ldots, a_{i_{k}}, \ldots, 0\right] , a_{i} \neq 0 , index $i_k$ 对应items.一个大小为t的mini-batch embedding lookups可以写为:

S=A^{T} W

DLRMs利用embedding tables将类别特征映射到稠密表示。但即使embeddings是有意义的,但我们要如何利用它们进行准确的预测呢? latent factor methods。

Matrix Factorization

回顾推荐问题的典型场景,有一组用户S已经给一些产品进行了评价。我们将产品表示为vector $w_i$,将用户表示为vector $v_j$,共n个产品,m个用户。$(i,j) S$

The matrix factorization approach solves this problem by minimizing

\min \sum_{(i, j) \in \mathcal{S}} r_{i j}-\boldsymbol{w}{i}^{T} \boldsymbol{v}{j} (3)

R \approx W V^{T} ,R其实就是Reward matrix,W,V是两个embedding tables,每一行分别表示着laten factor space里的user/product. vectors的点积代表对rating的预测。

Factoriation Machine

在分类问题中,我们会顶一个预测函数:$\phi : \mathbb{R}^{n} \rightarrow T$ 输入x预测 label y. 我们定义T={+1, -1},+1代表有点击,-1代表每点击,去预测click-through rate。 FM在线性模型上引入了二阶交叉。

\hat{y}=b+\boldsymbol{w}^{T} \boldsymbol{x}+\boldsymbol{x}^{T} \text { upper }\left(V V^{T}\right) \boldsymbol{x} (4)

V \in \mathbb{R}^{n \times d}, \boldsymbol{w} \in \mathbb{R}^{n}, \text { and } b \in \mathbb{R}

FM明显不同于多项式核函数SVM的是,它将分解二阶交叉矩阵到latent factors(or embedding vectors)就像矩阵分解似的,更高效的处理了稀疏数据。通过仅用不同embedding vectors交叉显著减少了二阶交叉的复杂度。转为了线性计算复杂度。

Multilayer Perceptrons

当然,当前许多在机器学习上的成功是源于深度学习的兴起。这里边最基础的模型就是MLP了,一个由FC layers和激活函数组成的预测函数。

\hat{y}=W_{k} \sigma\left(W_{k-1} \sigma\left(\ldots \sigma\left(W_{1} \boldsymbol{x}+\boldsymbol{b}{1}\right) \dots\right)+\boldsymbol{b}{k-1}\right)+\boldsymbol{b}_{k} (5)

\text { weight matrix } W_{l} \in \mathbb{R}^{n_{l} \times n_{l-1}}, \text { bias } \boldsymbol{b}{l} \in \mathbb{R}^{n{l}} \text { for layer } l=1, \ldots, k

这些方法备用来捕获更复杂的interactions。比如在有足够的参数下,MLPs有足够的深度和广度来适应数据到任意精度。各种方法的变种被广泛应用到了各种场景下,包括cv和nlp。有一个特别的case,NCF被用来做MLPerf benchmark的一部分,它使用MLP来计算矩阵分解中embeddings直接的interaction,而非dot product。

DLRM Architecture

上边描述了推荐系统和预测分析使用的不同模型,现在我们将其组合起来,构建一个state-of-the-art 的个性化模型。 users和products可以用许多的连续特征和类别特征来描述. 类别特征,用同一尺寸的embedding vector表示 连续特征用MLP(bottom or dense MLP)转换为同样长度的稠密向量。

我们按照FM的方式处理稀疏特征,显示地计算不同特征的二阶交叉,可选的将其传给MLPs。将这些dot products与原始的dense features拼接起来,传给另一个MLP(the top or output MLP),最后套个sigmoid函数输出概率。

Comparison with Prior Models

许多基于深度学习的推荐模型使用类似的想法去处理稀疏特征,生成高阶项。 Wide and Deep, Deep and Cross, DeepFm, xDeepFM 都设计了特别的网络去系统性地构建higher-order interactions。这些网络将他们特别的结构和MLP相加,然后传到一个linear layer使用sigmoid函数去输出一个最终概率。DLRM模仿因子分解机,以结构化的方式interacts embeddings,通过仅在最终MLP中对embeddings进行dot product产生交叉项来显着降低模型的维数。 我们认为其他网络中发现的二阶以上的高阶交互可能不值得额外的计算/内存消耗。

DLRM与其他网络之间的关键区别在于这些网络如何处理embedded feature vectors 及其交叉项。 特别是,DLRM(和xDeepFM)将每个特征向量解释为表示单个类别的单个unit,而像Deep and Cross这样的网络将特征向量中的每个元素视为一个新的unit来产生不同交叉项。 因此,Deep and Cross不仅会像DLRM中通过点积产生来自不同特征向量的元素之间的交叉项,还会在相同特征向量内的元素之间产生交叉项,从而产生更高的维度。

Parallelism

DLRMs
DLRMs
RLRMCaffe2Pytorch

在我们的设置里,top MLP和interaction op需要能连接到bottom MLP和所有embeddings。因为模型并行已经将embeddings分散到各个device上,这就需要个性化的all-to-all的通信。在embedding lookup最后这块,每个设备都驻留着一个embedding tables的向量,用于mini-batch中的所有样本,需要沿着min-batch的维度进行拆分并于对应设备通信,如图2所示。


PytorchCaffe2

Data

搞了三个数据集,随机集、人造集和公开数据集.前两个可用于从系统角度试验模型,它允许我们通过动态生成数据,消除对数据存储系统的依赖性来测试不同的硬件属性和瓶颈。 后者让我们对实际数据进行实验并测量模型的准确性。

Random

连续特征用numpy根据均匀分布或者高斯分布来生成。

离散特征我们直接生成embedding matrix以及对应的index

Synthetic

有很多理由让我们定制化的生成类别特征的indices,比如我们用了个特别的数据集,并因为隐私问题不想共享它。那么我们可以通过分布来表达类别特征。这可能有助于替代应用中使用的隐私保护技术,比如federated learning。同样,如果我们想要研究内存行为,我们synthetic trace中原始trace的基本访问位置。

假设我们有所有特征的embedding lookups indices的trace。我们可以记录轨迹中的去重后的访问和重复访问的距离频率(算法.1),生成[14]提的synthetic trace(算法2)。

请注意,我们只能生成到目前为止看到的s次唯一访问,因此s是控制算法2中分布p的支撑集。 给定固定数量的唯一访问,input trace越长将导致在算法1中分配给它们的概率越低,这将导致算法2要更长的时间取得完整分布支撑集。 为了解决这个问题,我们将唯一访问的概率提高到最小阈值,并调整支撑集以便在看到所有访问后从中删除唯一访问。基于original and synthetic traces的概率分布p的可视化比较如图3所示。在我们的实验中,original and adjusted synthetic traces产生了类似的缓存命中/未命中率。

算法1和算法2设计过去用于更精确的缓存模拟,但是它们表明一般概念,那就是概率分布可以怎样用来生成具有期望属性的synthetic traces。

Public

个性化推荐系统的公开数据比较少,The Criteo AI Labs Ad Kaggle和Terabyte数据集为了做点击率预估包含了点击日志。每个数据有13个连续特征,26个离散特征。连续特征用log(1+x)处理。离散特征映射到对应embedding的index, 无标注的离散特征被映射到0或NULL.

Experiments

The experiments are performed on the Big Basin platform with Dual Socket Intel Xeon 6138 CPU @ 2.00GHz and eight Nvidia Tesla V100 16GB GPUs

Model Accuracy on Public Data Sets

Deep and Cross(DCN)

我们画出了训练集和验证集在单epoch的准确率,每个模型都使用了SGD和Adagrad优化器,没有使用正则化。实验中DLRM在训练集和验证集的准确率都略高一些,如图5.值得注意的是,这里边没有进行额外的调参。


Model Performance on a Single Socket/Device

这里使用8个离散特征+512个连续特征的模型去测我们模型在单socket device上的性能。每个离散特征被处理为有1M vectors的embedding table,vector dimension是64,这些连续特征等价一个有512维的vector。让bottom MLP有两层,top MLP有四层。我们在一个2048K的随机生成样本数据集即1K个mini-batches上评估模型。

这个模型用Caffe2实现,在CPU上要跑256s,GPU上跑62s,具体见图6。不出所料,主要的时间花费在embedding lookups和全连接层。在CPU上全连接层的计算消耗显著,而GPU上几乎可以忽略。

Conclusion

在本文中,我们提出并开源了一种新的基于深度学习的推荐模型,利用分类数据。尽管推荐和个性化系统已在当今工业界中通过深度学习获得了实用的成功,但这些网络在学术界仍然很少受到关注。通过详细描述先进的推荐系统并开源其实现,我们希望人们能关注到这类特别的网络,以便进一步进行算法实验、建模、系统协同设计和基准测试。