推荐系列论文五:Deep & Cross Network for Ad Click Predictions

论文地址

Deep & Cross Network for Ad Click Predictions

前言

这次分享一下来自Standford和google联合发表的Deep&Cross Network，该篇文章主要工作是提出了Cross的结构来进行高阶的特征组合并且引入线性时间复杂度，模型的结构与Wide&Deep类似，不同的地方主要在于在Wide&Deep中，Wide部分使用的交叉特征需要人为进行组合，需要依赖很多的先验知识，而Cross结构则可以自动进行高阶的特征组合从而优化CTR结果，下面来看一下该篇论文的内容。

Abstract

众所周知，特征工程是机器学习任务中非常重要的一环，通常一个好的特征比模型要重要的多，但是这通知需要耗费大量的人工时间去筛选或者穷尽地去尝试特征对。

DNN的出现使得特征自动组合成为可能，也就是说通过将特征统一放入DNN中利用DNN来自动完成高阶非线性特征的拟合以及学习，但是DNN在做这种特征组合时，由于使用神经网络组合后特征的不可见性虽然其泛化能力较好但是相应的记忆能力存在一定的缺失。

在Wide&Deep(后续会对该篇论文进行分享)中，使用了Wide的部分来增加对组合特征的记忆能力，而这仍然需要人为进行特征组合，DeepFM将wide部分的lr替换为了FM，增加了更多的二维特征交叉，而这些特征组合大部分都是二阶特征组合，这是因为当组合的特征越多，特征的维度也容易形成爆炸之势，为学习带来了很大的难度。

DCN做的事情就是替换掉Wide而使用Cross结构从而无需人工进行特征的组合并且利用Cross层次的不同来获得不同阶的组合，利用这种结构DCN在许多任务上相比于当前的主流的结构在内存占用以及准确率上都取得了领先的位置。

小总结

也就说本篇文章的核心内容，就是引入了Cross结构来进行多特征的组合从而避免了人为组合的难度，但是组合特征的种类这么多，是如何进行压缩的呢？接下来是正文部分。

Introduction

Related word

文中主要列举了一些特征组合方面的工作，首当其冲的是FM，其为每个特征均学习一个隐向量，特征的组合就利用两个特征的隐向量的内积作为组合特征，这种方式有效地解决了一般的组合特征中由于稀疏性问题权重难以训练的问题。FFM则在FM的基础上引入了Fields的概念，每一维特征都将学习对应其余所有Fields的隐向量，当与不同的隐向量进行交叉时选择不同的隐向量进行向量内积。

DNN通过多层的神经网络来学习高维的非线性特征组合，而DNN有一个问题就是当神经网络的层数一深很容易导致梯度消失|梯度爆炸的问题，也就导致靠近输入层的权重非常难以更新，这里额外说一下ResNet，因为理论上Deep Network学习的能力至少是大于等于Shallow Network的，但是实际情况当模型深度上升性能却迎来了下降，ResNet的做法通过引入shortcut connection来提升深层神经网络的学习的，其结构如下：

这里看到输出是 F ( x ) + x F(x)+x F(x)+x，输入是x，中间的神经网络是相当于做了个x->F(x)的映射，通常而言，直接学习F(x)->y是比学习F(x)->y-x更困难的，因此Resnet的核心思想就是利用这样的shortcut connection使得这几层神经网络学习的是输出与输入之间的残差，从而简化神经网络的学习难度加深深层网络的学习层数。

DNN非线性的拟合能力非常强，但是DNN进行高阶非线性的组合是否就完美呢？在kaggle竞赛中高排名的做法很多都是低阶组合特征，而DNN的特征组合则是高度非线性的，那么自然而然希望既可以利用DNN学习高阶非线性特征的能力，又希望可以学习显式的特征组合，Wide&Deep就是这种思想下的产物，Deep&Cross在Wide&Deep进一步简化了特征组合的难度以及提升了效果。

Main Contributions

1. 提出了一种无需人工特征组合以及暴力搜寻的可以显示进行特征组合的Cross结构来进行有限阶的特征组合。
2. 随着Cross的layer层数加深组合特征的阶数随之上升，即多少特征组合可控，并且在Cross结构中包含了所有可能的当前阶的特征组合，描述的不是特征清楚，后面结合结构来说。
3. Cross网络并不特征占用内存从而可以轻松实现。
4. DCN在使用差距一个数据量级特征的情况下在测试集上获得了比DNN更优的logloss。

DCN

终于到了正文部分了，第一步，先扔DCN的网络结构。

输入层

输入主要包括Continus Feature以及Category Feature，对于连续值需要经过归一化处理，对于离散特征当前主流的做法都是经过Embedding layer将离散值转为连续特征处理了，因此输入到DCN中的特征是连续特征与离散特征经过处理后Concat(这里叫stack)形成的一个长向量。

Cross network

模型整体结构与Wide&Deep类似，因此这里重点就介绍Cross network部分，可以看到图中Cross共有L1层，每一层的输入如下:

X L + 1 = X 0 ∗ X L T ∗ W L + 1 + b l + 1 + X L X_{L+1} = X_0*X_L^T*W_{L+1}+b_{l+1}+X_L XL+1​=X0​∗XLT​∗WL+1​+bl+1​+XL​

公式中的每个参数均是一个列向量，可以看到 X L + 1 X_{L+1} XL+1​等于 X L X_{L} XL​增加一个 X 0 ∗ X L T ∗ W L + 1 + b l + 1 X_0*X_L^T*W_{L+1}+b_{l+1} X0​∗XLT​∗WL+1​+bl+1​项，将 X 0 ∗ X L T ∗ W L + 1 + b l + 1 X_0*X_L^T*W_{L+1}+b_{l+1} X0​∗XLT​∗WL+1​+bl+1​记为 F ( X L , W L + 1 , b L ) F(X_L,W_{L+1},b_L) F(XL​,WL+1​,bL​)，相当于F()函数学习的就是一个残差，这和Resnet的思想有点像。公式中，w和b均是该层的参数项，可以看到 X L + 1 X_{L+1} XL+1​与 X L X_L XL​的维度是一样的，也就是说输入经过一整个Cross network其维度是一样的，那么Cross network为什么说可以学习到所有的特征组合呢？

这里假设Cross network只有一层，我们的特征为[a,b,c]，w参数我们以 w m n w_{mn} wmn​来表示，m代表第几层，n代表第几位，这里忽略biases，因为不影响我们看结果我们看一下第一层的输出结果：

X 1 = [ w 11 ∗ ( a 2 , b a , c a ) + a , w 12 ∗ ( a b , b 2 , c b ) + b , w 13 ( a c , b c , c 2 ) + c ] X_1=[w_{11}*(a^2,ba,ca)+a,w_{12}*(ab,b^2,cb)+b,w_{13}(ac,bc,c^2)+c] X1​=[w11​∗(a2,ba,ca)+a,w12​∗(ab,b2,cb)+b,w13​(ac,bc,c2)+c]

可以看到第一层的输出中分解开已经包含了所有的二阶的特征组合方式，只是变成了各自求和的形式，再看第二层的输出结果，设：

t e m p = w 11 ∗ w 21 ∗ ( a 2 , b a , c a ) + a ∗ w 21 + w 12 ∗ w 22 ∗ ( a b , b 2 , c b ) + b ∗ w 22 + w 13 ∗ w 23 ∗ ( a c , b c , c 2 ) + c ∗ w 23 temp = w_{11}*w_{21}*(a^2,ba,ca)+a*w_{21}+w_{12}*w_{22}*(ab,b^2,cb)+b*w_{22}+w_{13}*w_{23}*(ac,bc,c^2)+c*w_{23} temp=w11​∗w21​∗(a2,ba,ca)+a∗w21​+w12​∗w22​∗(ab,b2,cb)+b∗w22​+w13​∗w23​∗(ac,bc,c2)+c∗w23​

第二层的输出如下：

X 2 = [ a ∗ t e m p + a , b ∗ t e m p + b , c ∗ t e m p + c ] X_2=[a*temp+a,b*temp+b,c*temp+c] X2​=[a∗temp+a,b∗temp+b,c∗temp+c]

可以看到第二层中包含了所有的一阶到三阶的特征组合，这些特征都是以和的形成从而压缩到了与输入相同的维度。

以上就是Cross network独特的地方，其通过这种形式一方面维持了维度的不变性，并且还包括了所有的特征组合可能。

参数数量分析

可以看到Cross network的参数主要是每一层的系数W以及偏置biases，假设输入维度为d，Cross layer深度为L，那么总的参数数量为2*L*d,深度以及输入维度均是正比关系！！

Deep network

这里没什么新意，就不展开说了。

输出层

输出层将Cross network以及DNN network的输出直接进行stack操作，然后以一层全连接进行连接并使用sigmoid计算最终的pCTR。

Cross network分析

Polynomial Approximation

这部分，我没太看明白，猜测是推导Cross的结构可以获取到bound-degree下所有的组合吧。

Generalization of FMs

我们知道FM核心的思想就是参数共享，即不同的特征组合只要使用了同一个特征，那么使用的对应的隐向量也是相同的，这样即使是不同的特征组合也可以对同一个特征的隐向量进行更新。

Cross结构继承了FM的这一思想，具体体现在，如只考虑 x i x_i xi​与 x j x_j xj​特征的组合，其在Cross后的系数是 { w k i } k = 1 l \{w_k^i\}_{k=1}^l {wki​}k=1l​以及 { w k j } k = 1 l \{w_k^j\}_{k=1}^l {wkj​}k=1l​的组合，而这些参数不仅是在具有 x i x j x_ix_j xi​xj​时才可以更新，在拥有其他的组合时均可以进行更新。

Efficient Projection

每一层的Cross layer相当于计算了x0与 X L X_L XL​的所有二阶组合，假设输入维度为d，则所有二阶组合数量为 d 2 d^2 d2，再将其映射到d维，相当于再与 d 2 ∗ d d^2*d d2∗d的矩阵相乘进行降维，时间复杂度为三次方消耗，而Cross network通过分解为向量计算并加入权重矩阵将时间复杂度下降到线性级别，先看图：

看图，感觉完全看不出来是如何压缩到线性时间复杂度，那么他是怎么压缩的呢？很简单。

x p = x 0 x l T w = x 0 ( x l T w ) x_p=x_0x_l^Tw=x_0(x_l^Tw) xp​=x0​xlT​w=x0​(xlT​w)

由于输入都是长度为d的向量，先计算 x l x_l xl​与w的乘积得到一个标量值，再通过一个向量与标量进行乘积最终的时间复杂度就来到了O(d)，并且占用的内存也小的多的多，试想如果输入维度d非常高，简单说10000维，10000*10000*4bytes=4亿bytes就是400MB的空间。

实验

数据集

The Criteo Display Ads2 dataset is for the purpose of predicting ads click-through rate. It has 13 integer features and 26 categorical features where each category has a high cardinality.

For this dataset, an improvement of 0.001 in logloss is considered as practically significant. 这是因为在用户数量非常多的情况下，CTR即使只提升一点点带来的收益都非常高。

实现细节

特征处理

论文中的DCN是基于TensorFlow搭建训练的 ，其中Real-value通过log transform进行了转换(不知道是不是先对数转换再归一化处理)，categorical feature通过Embedding进行转换，Embedding的长度选择经验是 6 ∗ ( c a t e g o r i c a l   c a r d i n a l i t y ) 1 / 4 6*(categorical\ cardinality)^{1/4} 6∗(categorical cardinality)1/4 ,stack后的维度为1026维。

优化方法

使用的是基于Adam优化器的SGD方法进行参数更新。batch_size为512，在DNN中使用了batch normalization在一层训练完成后进行归一化重新将分布拉到正态分布中。gradient clip norm was set at 100，这个参数我没使用用，查询到应该是防止梯度爆炸的，当累计梯度到达限定阈值则进行截断处理。

regularization

在防止过拟合方面，使用的是early stop，在实验中发现L2正则以及drop out效果都不怎么显著。

超参数

We report results based on a grid search over the number of hidden layers, hidden layer size, initial learning rate and number of cross layers.以上就是主要进行的网格搜索的超参数，具体范围为：

The number of hidden layers ranged from 2 to 5, with hidden layer sizes from 32 to 1024. For DCN, the

number of cross layers3 is from 1 to 6. The initial learning rate4 was tuned from 0.0001 to 0.001 with increments of 0.0001. All experiments applied early stopping at training step 150,000, beyond

which overfitting started to occur.

后面的实验结果我就不解释了，还是那句，知道效果好就ok了，但是具体的应用还是需要根据场景去尝试。

小结

这篇2017年google与stanford联合发表的论文等于加强了16年google的wide&deep模型，Cross结构可以有效地控制多阶特征的组合以及学习，但是这里想到的问题是在将如此多的组合特征利用求和进行压缩后学习的能力是否还强呢？即是否可以有效地学习每层的weights和biases从而帮助筛选出最有效的组合特征呢？这部分以后有机会可以进行验证，今天的文章就到这吧，下期见。