Deep&Cross Network介绍

Reading time ~2 minutes

google在2017年提出了一个Deep&Cross Network的模型:

1.介绍

在该paper中,提出了Deep&Cross Network(DCN)模型,它能对sparse和dense的输入进行自动特征学习。DCN可以有效地捕获关于有限阶(bounded degrees)上的有效特征交叉,学到高度非线性交叉,无需人工特征工程或暴力搜索(exhaustive searching)。并且计算代价低。

  • 我们提出了一个新的cross network,它显式地在每个layer上进行特征交叉(feature crossing),可有效学习有限阶(bouned degrees)的特征交叉预测,无需人工特征工程和暴力搜索。
  • 该cross network简单有效。通过设计,最高的多项式阶在每一layer递增,由layer depth决定。该网络包含了所有阶的交叉项(直到最高阶),它们的系数都不同。
  • 该cross network内存高效,很容易实现。
  • 我们的实验结果表明,比起接近相同阶的DNN,DCN具有更低的logloss,更少的参数。

2.DCN

本节描述了Deep & Cross Network模型。一个DCN模型会以一个embedding and stacking layer开始,接着并列连一个cross network和一个deep network。接着通过最后一个combination layer将两个network的输出进行组合。完整的DCN模型如图1所示。

图片名称

图1: Deep & Cross Network

2.1 Embedding and Stacking Layer

输入数据带有sparse和dense feature。在大规模推荐系统的CTR预测中,输入几乎都是类别型特征(categorical features),比如:”country=usa”。这样的feature通常被编码成one-hot vectors,比如:”[0,1,0]”;然而,对于大的vocabularies,这通常会产生超高维度的特征空间。

为了减小该维度,我们使用一个embedding procedure来将这些二元features转换到关于真实值(real values)的dense vectors中(称为embedding vectors)。

\[x_{embed,i} = W_{embed,i} x_i\]

…(1)

其中\(x_{embed,i}\)是embedding vector,\(x_i\)是第i个category的二元输入,\(W_{embed,i} \in R^{n_e \times n_v}\)是对应的embedding matrix,会与网络中的其它参数一起进行优化,\(n_e, n_v\)分别是embedding size和vocabulary size。

最后,我们将embedding vectors,以及归一化稠密特征(normalized dense features)\(x_{dense}\)进行stack成一个vector:

\[x_0 = [ x_{embed,1}^T, ..., X_{embed,k}^T, X_{dense}^T]\]

…(2)

2.2 Cross Network

新的cross network的核心思想是,将显式特征(explicit feature)以一种有效方式进行交叉。cross network由多个cross layers组成,每一个layer具有以下的公式:

\[x_{l+1} = x_0 x_l^T w_l + b_l + x_l = f(x_l, w_l, b_l) + x_l\]

…(3)

其中:

  • \(x_l, x_{l+1}\)是列向量(column vectors),分别表示来自第l层和第(l+1)层cross layers的输出;
  • \(w_l, b_l \in R^d\)是第l层layer的weight和bias参数。

在完成一个特征交叉f后,每个cross layer会将它的输入加回去,对应的mapping function f:\(R^d \rightarrow R^d\),刚好等于残差\(x_{l+1} - x_l\)。一个cross layer的可视化如图2所示。

图片名称

图2: 一个cross layer的visualization

特征的高阶交叉(high-degree interaction):cross network的独特结构使得交叉特征的阶(the degress of cross features)随着layer的深度而增长。对于第l层layer,它的最高多项式阶(在输入\(x_0\)上)是\(l+1\). 实际上,cross network由这些交叉项\(x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d}\)组成,对应的阶从1到l+1. 详见第3节。

复杂度分析:假设\(L_c\)表示cross layers的数目,d表示输入维度。那么,在该cross network中涉及的参数数目为:

\[d \times L_c \times 2\]

一个cross network的时间和空间复杂度对于输入维度是线性关系。因而,比起它的deep部分,一个cross network引入的复杂度微不足道,DCN的整体复杂度与传统的DNN在同一水平线上。如此高效(efficiency)是受益于\(x_0 x_l^T\)的rank-one特性,它可以使我们生成所有的交叉项,无需计算或存储整个matrix。

cross network的参数数目少,从而限制了模型的能力(capacity)。为了捕获高阶非线性交叉,我们平行引入了一个deep network。

2.3 Deep Network

Deep network是一个fully-connected feed-forward神经网络,每个deep layer具有以下的公式:

\[h_{l+1} = f(W_l h_l + b_l)\]

…(4)

其中:

  • \(h_l \in R^{n_l}, h_{l+1} \in R^{n_{l+1}}\)分别是第l层和第(l+1)层hidden layer;
  • \(W_l \in R^{n_{l+1} \times n_l}, b_l \in R^{n_{l+1}}\)是第l个deep layer的参数;
  • \(f(\cdot)\)是ReLU function。

复杂度分析:出于简洁性,我们假设所有的deep layers具有相同的size。假设\(L_d\)表示deep layers的数目,m表示deep layer的size。那么,在该deep network中的参数的数目为:

\[d \times m + m + (m^2 + m) \times (L_d - 1)\]

2.4 Combination Layer

Combination Layer将两个network的输出进行拼接(concatenate),然后将该拼接向量(concatenated vector)feed 进一个标准的logits layer上。

下面是一个二分类问题的公式:

\[p = \sigma ( [x_{L_1}^T, h_{L_2}^T] w_{logits})\]

…(5)

其中:

  • \(x_{L_1} \in R^d, h_{L_2} \in R^m\)分别是来自cross network和deep network的输出
  • \(W_{logits} \in R^{d+m}\)是combination layer的weight vector,其中\(\sigma(x) = 1/(1+exp(-x))\)。

loss function是logloss,带有一个正则项。

\[loss = - \frac{1}{N} \sum_{i=1}^{N} y_i log(p_i) + (1-y_i) log(1-p_i) + \lambda \sum_{l} \| w_l \|^2\]

…(6)

其中 \(p_i\)是等式(5)计算得到的probabilities,\(y_i\)是true labels,N是输入的总数,\(\lambda\)是\(L_2\)正则项参数。

我们对两个network进行jointly train,在训练期间,每个独立的network会察觉到另一个。

3.Cross Network分析

在这一节,我们分析了DCN的cross network,以便于更有效地理解。我们提供了三个视角:多项式近似,泛化到FM,有效投影。为了简洁,我们假设:\(b_i = 0\)

概念:假设在\(w_j\)中的第i个元素是\(w_j^{(i)}\)。对于多索引(multi-index) \(\alpha = [\alpha_1, ..., \alpha_d] \in N^d\),以及\(x = [x_1, ..., x_d] \in R^d\),我们定义了:\(\| \alpha \| = \sum_{i+1}^d \alpha_i\)。

术语:交叉项\(x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d}\)的阶(degree)由\(\|\alpha\|\)定义。一个多项式的阶由它的项的最高阶决定。

3.1 多项式近似

根据维尔斯特拉斯逼近定理(Weierstrass approximation theorem),任意满足特定平滑假设条件下的函数,可以通过一个多项式进行逼近到一个特定的精度上。因而,我们从多项式近似的角度分析了cross network。特别的,cross network会以一种高效的、有表现力的、能更好地对现实世界数据集进行泛化的方式,近似相同阶的多项式类。

我们详细研究了一个cross network,将它近似成相同阶的多项式类(polynomial class)。假定\(P_n(x)\)表示n阶的多元多项式类(multivariate polynomial class):

\[P_n(x)= \{ \sum_{\alpha} w_{\alpha} x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d} | 0 \le |\alpha| \le n, \alpha \in N^d \}\]

…(7)

在该类中的每个多项式具有\(O(d^n)\)个系数。只有\(O(d)\)个参数,cross network包含了在相同阶的多项式中的所有交叉项,每一项的系数与其它项各不相同。

理论 3.1: 一个l-layer的cross network,具有i+1个layer,定义成:\(x_{i+1} = x_0 x_i^T w_i + x_i\)。假设网络的输入是\(x_0 = [x_1, x_2, ..., x_d]^T\),输出是\(g_l(x_0) = x_l^T w_l\),参数是\(w_i, b_i \in R^d\)。接着,多元多项式\(g_l(x_0)\)会以下面的类进行重现(reproduce):

\[\{ \sum_{\alpha} (w_0,...,w_l) x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d} | 0 \le |\alpha| \le l+1, \alpha \in N^d \}\]

其中:

  • 其中 \(c_\alpha = M_\alpha \sum_{i \in B_\alpha} \sum_{j \in P_\alpha} \prod_{k=1}^{|\alpha|} w_{i_k}^{j_k}\), \(M_\alpha\)是一个与\(w_i\)独立的常数
  • \(i = [i_1, ..., i_{|\alpha|}]\)和 \(j = [j_1, ..., j_{|\alpha|}]\)是多元索引(multi-indices), \(B_{\alpha} = \{ y \in \{ 0, 1,...,l\}^{|\alpha |} | y_i < y_j \wedge y_{|\alpha|} = l \}\),
  • \(P_\alpha\)是indice \((\underbrace{1, ..., 1}_{\alpha_1 times} ... \underbrace{d, ..., d}_{\alpha_d times})\)的所有排列(permutations)的集合。

定理3.1的理论证明详见paper中的附录。举个例子,\(x_1 x_2 x_3\)的系数\(c_\alpha\),其中\(\alpha = (1,1,1,0,...,0)\)。直到一些常数,其中\(l = 2, c_\alpha = \sum_{i,j,k \in P_\alpha} w_0^{(i)} w_1^{(j)} w_2^{(k)}\);其中\(l=3, c_\alpha = \sum_{i,j,k \in P_\alpha} w_0^{(i)} w_1^{(j)} w_3^{(k)} + w_0^{(i)} w_2^{(j)} w_3^{(k)} + w_1^{(i)} w_2^{(j)} w_3^{(k)}\)

3.2 FM的泛化

cross network共享参数,类似于FM模型的参数共享,并扩展到了一个更深的结构上。

在FM模型中,特征\(x_i\)与一个 weight vector \(v_i\)相关联,交叉项\(x_i x_j\)的权重通过 \(<v_i, v_j>\)计算得到。在DCN中,\(x_i\)与标量\(\{ w_k^{(i)} \}_{k=1}^{l}\)有关,\(x_i x_j\)的权重是集合\(\{ w_k^{(i)}\}_{k=0}^l\)和\(\{ w_k^{(j)}\}_{k=0}^{l}\)的参数乘积。两种模型都会为每个特征学到一些与其它特征相互独立的参数,交叉项的权重是相应参数的一种特定组合。

参数共享(parameter sharing)不权使得模型更有效,也使模型可以泛化到未见过的特征交叉上,对噪声更健壮。例如,使用sparse features的数据集。如果两个二元特征\(x_i\)和\(x_j\)很少或者几乎从未在训练集中共现过,假设,\(x_i \ne 0 \wedge x_j \ne 0\),接着,学到关于\(x_i x_j\)的权重不会带有对预测有意义的信息。

FM是一个浅层结构(shallow structure),受限于交叉项的阶是2. 而DCN可以构建所有的交叉项\(x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d}\),其中阶 \(|\alpha|\)由一些常数决定,见理论3.1。因而,cross network扩展了参数共享的思想,将单个layer扩展到多个layer,并且有更高阶的交叉项。注意,与高阶FM不同的是,在cross network中的参数数目,只随着输入维度线性增长。

3.3 有效投影

每个cross layer会以一种有效方式,将在\(x_0\)和\(x_l\)间的所有pairwise交叉进行投影到输入维度上。

考虑到\(\tilde{x} \in R^d\)是一个cross layer的输入。cross layer首先隐式构建了\(d^2\)个关于\(x_i \tilde{x}_j\)的pairwise交叉,接着以一种内存高效的方式,隐式地将它们投影到维度d上。这种直接的方式会带来3次方开销。

我们的cross layer提供了一种有效的解决方式,将开销减小到维度d的线性开销上。考虑\(x_p = x_0 \tilde{x}^T w\)。事实上等于:

\[x_p^T = [x_1\tilde{x}_1 ... x_1\tilde{x}_d ... x_d\tilde{x}_1 ... x_d\tilde{x}_d] \left[ \begin{array}{ccc} w&0&...&0\\ 0&w&...&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&...&w \end{array} \right]\]

…(8)

其中,row vectors包含了所有\(d^2\) 个 \(x_i \tilde{x}_j\)的pairwise交叉,投影矩阵具有一个块对角化结构,其中:\(w \in R^d\)是一个列向量。

4.实验结果

在本节中,我们评估了CDN在多个数据集上的效果。

4.1 Criteo Display Ads数据集

Criteo Display Ads数据集用于预测点击率。具有13个integer features和26个categorial features。其中,每个category都具有一个很高的维度基数。对于该数据集,在logloss上提升0.001可以看成是巨大的提升。当考虑到在一个很大的用户基数时,在预测准确率(prediction accuracy)的一个小的提升,可以为公司带到来一个大的回报。数据包含了11GB的包含7天的用户日志(~41000,000条记录)。我们使用前6天的数据做为训练,并将第7天的数据随机划分成等size的validation和test set。

4.2 实现细节

DCN在tensorflow上实现,我们会讨论一些关于训练CDN的细节。

数据处理和embedding。实数型特征通过一个log转换进行归一化。对于类别型特征,会将这些特征嵌入到dense vectors中,维度为 \(6 \times (category \ cardinality) ^{1/4}\)。最后将所有的embedding结果拼接(concatenating)成一个维度为1026的向量。

优化(Optimization):我们使用Adam optimizer,mini-batch进行随机优化。batch size=512. Batch normalization被应用于deep网络,gradient clip norm设置为100.

正则化:我们使用early stopping,我们未发现L2正则或dropout很有效。

超参数:我们基于一个grid search来在hidden layers的数目、size、初始learning rate以及cross layers的数目上进行探索。hidden layers的数目范围为2一5, hidden layers的数目从32到1024. 对于DCN,cross layers的数目从1到6.初始learning rate从0.0001依次递增调到0.001. 所有试验都使用early stopping,训练step为150000, 超过它可能会发生overfitting。

参考

https://arxiv.org/pdf/1708.05123.pdf

STAR算法介绍

阿里在《One Model to Serve All: Star Topology Adaptive Recommenderfor Multi-Domain CTR Prediction》中提出了一种思路来解决不同模块使用同一模型的思路:# 1.介绍传统CTR模型关注于si...… Continue reading

PLE介绍

Published on March 04, 2021

DTS介绍

Published on January 02, 2021