推荐系统与DNN的结合

这篇博客记录自己前段时间对基于DNN的推荐模型的学习，包括FM、FFM、DCN、PNN、AFM和XDeepFM。

FM

全称是Factorization Machine，分解机。FM的思想在于公式 $\sum_{i=1}^n\sum_{j=i+1}^nW_{ij}X_iX_j=\sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>X_iX_j$ ，也就是 $W_{ij}:=<v_i,v_j>$ ，如何将巨大的稀疏矩阵 $W$ 分解，用两个小的矩阵的乘积来表示。所以利用FM的思想就可以对二阶组合特征 $\sum_{i=1}^n\sum_{j=i+1}^nW_{ij}X_iX_j$ 进行一定的变换，变换公式如下：
$\begin{align} \sum_{i=1}^n\sum_{j=i+1}^nW_{ij}X_iX_j &= \sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>X_iX_j \\ &= \sum_{i=1}^n\sum_{j=i+1}^n\sum_{f=1}^k v_{i,f}v_{j,f}X_iX_j \\ &= \cfrac{1}{2}(\sum_{i=1}^n\sum_{j=1}^n\sum_{f=1}^k v_{i,f}v_{j,f}X_iX_j- \sum_{i=1}^n\sum_{f=1}^kv_{i,f}v_{i,f}X_iX_i) \\ &= \cfrac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i,f}X_i)*(\sum_{j=1}^nv_{j,f}X_j)-\sum_{i=1}^n(v_{i,f}X_i)^2) \\ &= \cfrac{1}{2}\sum_{f=1}^k((\sum_{i=1}^nv_{i,f}X_i)^2-\sum_{i=1}^2(v_{i,f}X_i)^2) \end{align}$
借助对神经网络的理解，我们可以将 $v_{i,f}x_i$ 看做是输入层的第 $i$ 个值经过神经网络后在隐层中的第 $f$ 个神经元上得到的值，此时就可以将 $\sum_{i=1}^nv_{i,f}X_i$ 看作是 $matmul(\vec{v},\vec{x})$ 。那么公式中的 $(\sum_{i=1}^nv_{i,f}X_i)^2$ 和 $\sum_{i=1}^2(v_{i,f}X_i)^2$ 就可以用下面代码来实现。

sum_square_part = tf.pow(tf.matmul(x, tf.transpose(v)), 2)
square_sum_part = tf.matmul(tf.pow(x, 2), tf.pow(v, 2))

当然也可以利用embedding的思想来理解FM，认为 $\vec{v} \times \vec{x}$ 就是将原始特征向量映射到一个新的低维空间中，用一个低维embedding向量来表示原始特征向量，此时可以利用tf.nn.embedding_lookup函数来实现特征向量的低维嵌入。
补充：tf.nn.embedding_lookup()中的核心就是gather函数，从array中取出特定的几行数据。因此我们可以用tf.gather()或者tf.gather_nd()实现embedding操作，其中，tf.gather()针对一维数据，而tf.gather_nd()针对多维数据。

FFM

FFM可以理解为考虑了field的FM，与FM最大的不同在于分解矩阵的设定。FM的二阶组合特征式是 $\sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>X_iX_j$ ，而FFM的二阶组合特征式是 $\sum_{i=1}^n\sum_{j=i+1}^n<v_{i,f_j},v_{j,f_i}>X_iX_j$ 。也就是说，FM中不同特征组合时使用的隐变量是唯一的，但是FFM中不同特征组合用的隐变量是不一样的。FM中值维护1个embedding矩阵，而FFM中要维护field个embedding矩阵（field是one hot前样本的特征数量），也就是要维度一个3维的embedding矩阵，维度是[feature_size, embedding_size, field_size]。下面用图表示：

FM和FFM的embedding表.png

FM和FFM带来的改进是给LR加入了二阶组合特征，同时优化了二阶组合特征的计算和表示方式。其中，FM在计算上进行了优化，使得二阶组合特征的计算复杂度由

O(kn^2)

降低到

O(kn)

；而FFM则在FM的基础上对表示方式做了改进，FM和FFM都对one-hot后的稀疏特征进行了embedding操作，但是FM中每个稀疏特征只映射成1个隐变量，而FFM中每个稀疏特征都映射成field_size个隐变量，特征的表示更加多样，对应的二阶组合方式也就更多。
其实FM和FFM与DNN并没有多大联系，但是想要了解推荐模型是如何与DNN结合的话，还是需要很好的理解FM。因为FM带来一个很重要的思想就是将高维稀疏特征映射到低维空间中，这在于DNN的结合中是至关重要的。因为推荐任务中特征经过one-hot后维度都会变得巨大，直接传给DNN带来的后果就是参数量爆炸，模型根本无法收敛，甚至都没法运行这个巨大的模型，所以后续基于DNN的推荐模型都是先对稀疏特征进行embedding操作的。

DCN

DCN.png

DCN，全程是Deep&Cross Network。模型有2个组成部分——Cross Network和Deep Network。显然模型的关键在于Cross Network的设计（说实话，我个人认为与DNN结合的模型一般重点都不在DNN的设计上，更多在于输入特征的处理方式或者并行网络的设计上）。Cross Network的核心思想是以有效的方式应用显式特征交叉，Cross Network由cross layer组成，每个cross layer公式是： $X_{l+1}=X_0 \otimes X_l^T * W_l+b_l+X_l=f(X_l,W_l,b_l)+X_l$ 可见Cross Network中 $l$ 层的输出 $X_{l+1}$ 与 $X_0$ 和 $l$ 层输入 $X_l$ 相关，交叉特征的交叉程度随着层深度的增加而增加。Cross Network的参数量是 $交叉层数*输入维度*2$ ，“2”包含了 $W$ 和 $b$ 。Cross layer实现代码如下：

x_l = tf.tensordot(tf.matmul(x0, x_l, transpose_b=True), weights['cross_layer_%d' % l], 1) 
      + weights['cross_layer_%d' % l] + x_l

补充1：公式右边最后一项 $+X_L$ 借鉴了残差网络的思想。
补充2：Cross layer的实现可以进行改进。上面的实现代码并没有逻辑上的bug，但是这种实现方式是非常消耗计算和存储资源的，原因就在于 $X_0 \otimes X_l$ 这一步是极度浪费计算和存储资源的。更好的实现方式是将计算过程由 $(X_0 \otimes X_l) * W_l$ 改为 $X_0 * (X_l \otimes W_l)$ ，因为 $X_0 \otimes X_l$ 得到的是一个大的2维矩阵，而 $X_l \otimes W_l$ 得到的是一个标量。详细的解释看知乎上的这篇文章。

PNN

PNN.png

PNN，全称是Product-based Neural Network，关键在于提出了product layer，放在embedding层和DNN之间，对embedding后的特征向量进行基于乘法的特征交叉操作。Product的思想来源于，CTR预估认为特征之间的关系更多的是一种and“且”的关系，而非add“加”（个人认为DNN中实现的特征交互本质上就是add“加”）的关系。
Product layer分为两部分——线性部分 $l_z$ 和非线性部分 $l_p$ 。其中， $\begin{align} & l_z=(l_z^1,l_z^2,...,l_z^{D_1}),l_z^n=W_z^n \odot Z \\ & l_p=(l_p^1,l_p^2,...,l_p^{D_1}),l_p^n=W_p^n \odot P \end{align}$ 线性部分有： $\begin{align} & l_z^n=W_z^n \odot Z=\sum_{i=1}^N \sum_{j=1}^M(W_z^n)_{i,j}Z_{i,j} \\ & Z=(Z_1,Z_2,...,Z_N) \doteq (f_1,f_1,...,f_N) \end{align}$ $W$ 的维度是 $[N,M,D_1]$ ，所以线性部分中每个特征点都可以看作是embedding特征矩阵的加权和，可见上面PNN的图中线性部分是有问题的，线性部分中每个点都跟所有的embedding向量有关，而不是只跟一个有关。
非线性部分则分为2种计算方式，因为P的定义分为2种——内积和外积。内积也就是两个embedding向量进行点积，外积就是两个embedding向量进行矩阵乘法（其中一个embedding向量需要进行转置）。
内积：此时 $P_{i,j}=<f_i,f_j>$ ，可见 $P$ 是2维对称矩阵， $W^n$ 也可以分解成两个向量做外积，即 $W^n=\theta^n \otimes (\theta^n)^T$ 。所以 $l_p^n=W_p^n \odot P=\sum_{i=1}^N \sum_{j=1}^N\theta_i^n\theta_j^nf_i f_j=\sum_{i=1}^N\theta_i^nf_i \sum_{j=1}^N\theta_j^nf_j=(\sum_{i=1}^N\theta_i^nf_i)^2$ 。假设 $\delta_i^n=\theta_i^nf_i$ ，那么有 $l_p^n=(\sum_{i=1}^N\delta_i^n)^2$ 。从这里的定义可以看出，如果选择product选择内积，那么非线性部分中每个点也是跟所有的embedding向量有关，而不是只跟两个有关，所以上图中非线性部分也画错了。
外积：此时 $P_{i,j}=f_if_j^T$ ，每两个embedding特征向量左外积就可以得到一个矩阵 $P_{i,j}$ 。论文中定义外积的 $P=\sum_{i=1}^N \sum_{j=1}^N p_{i,j}$ ，也就是所有外积矩阵的和，然后再对这个 $P$ 求加权和得到非线性部分的一个点。可见外积形式下非线性部分每个点也是跟所有embedding特征向量有关，所以确定PNN图中product layer那一部分是错误的。

AFM

AFM.png

AFM，全程是Attentional Factorization Machine，从名字就可以看出AFM是在FM的基础上加上了attention机制。原始FM在进行预测时，FM会让一个特征映射成一个特定的向量，当这个特征与其他特征做交叉时都是用相同的向量去做计算。这是不合理的，因为特征A与特征B做交叉特征时A的重要程度和特征A与特征C做交叉特征时是不一样的。如何体现出这种差异性呢？除了FFM模型外，AFM中的attention机制就是做这个工作的。这里attention可以视为权重，衡量不同特征之间交互的重要程度。AFM和FM的实现公式对比如下：

\begin{align} y_{AFM}&=w_0+\sum_{i=1}^Nw_ix_i+P^T\sum_{i=1}^N\sum_{j=i+1}^Na_{ij}(\vec{v_i} \odot \vec{v_j})x_ix_j \\ y_{FM}&=w_0+\sum_{i=1}^Nw_ix_i+\sum_{i=1}^N\sum_{j=i+1}^N(\vec{v_i} \odot \vec{v_j})x_ix_j \end{align}

其中，

a_{ij}

就是attention值，是将交叉特征向量传入attention网络（可以理解就是一个DNN）中学到权重。
AFM中的改进工作就是：

对原始的one-hot特征进行embedding操作；
对embedding特征进行两两交叉（相乘）并拼接得到组合特征向量；
将组合特征向量传到attention网络中学习的组合特征向量对应的权重向量；
将组合特征向量与权重向量相乘求和就得到了二阶部分的预测值。

xDeepFM

XDeepFM.png

xDeepFM其实就是Cross Network和DeepFM结合起来，既有Cross Network中的显示高阶组合特征，又有DNN中的隐式高阶组合特征。不过xDeepFM中对Cross Network做了一定的改进，在DCN中已经提到了cross layer的公式

x_k=x_0x_{k-1}^Tw_k+b_k+x_{k-1}

，xDeepFM利用数学归纳法证明了上述公式可以变成

x_k=\alpha^{i+1}x_0

，其中

\alpha^{i+1}=\alpha^i(x_0^Tw_{i+1}+1)

是一个标量，但这并不意味着

x_k

与

x_0

线性相关，因为

x_0

的乘子

\alpha

与

x_0

有关。不过这种形式的cross network还是有一些缺陷——输出格式受限（必须得和输入维度相同）和特征交互是bit级别的（没有体现出filed的概念）。而xDeepFM对cross network进行了改进，提出了CIN（Compressed Interaction Network）。下图是CIN的网络结构：

xDeepFM结构之CIN模块.png

对应的公式是

X_{h,\ast}^k=\sum_{i=1}^{H_{k-1}}\sum_{j=1}^mW_{ij}^{k,h}(X_{i,\ast}^{k-1} \odot X_{j,\ast}^0)

，此时输入

X^0

并不是一个向量，而是矩阵，维度是

[m,\ \ast]

，m表示有输入有m个embedding特征向量。CIN中第

k-1

层的输出也是一个矩阵

X^{k-1}

，维度是

[H_{k-1},\ \ast]

。此时

X^0

和

X^{k-1}

并不能直接做外积，所以xDeepFM的做法是对

X^0

和

X^{k-1}

做列切分，找相应列做外积，就可以得到一个3维的中间态矩阵。我们可以将这个中间态矩阵想象成图片经过CNN提取的特征图，对每张特征图求加权和就可以得到新向量中的一个点，也就是将原特征图压缩成一个向量。如果同一张特征图进行多次不同加权和，那么就可以得到多个向量中的点，这就是CIN中的压缩过程，图(b)展示了这一过程。CIN的另外一个改进就是并不是只输出最后一层的结果，而是对每一层的输出都进行sum pooling后，再将所有的输出拼接成一个向量作为最终的特征，这样就将不同阶的组合特征结合起来了，具体可看图(c)。这里挖个坑，后面再写论文对CIN的空间和时间复杂度的分析，以此来对比和原cross network的优劣。
2018.12.24 补充：看了下论文中对CIN模型的复杂度分析，主要是将CIN与相同层数的DNN进行了比较。在空间复杂度上，CIN是