PNN网络(Product-based Neural Network)

1. 概述

PNN(Product-based Neural Network)是在2016年提出的用于计算CTR问题的深度神经网络模型,PNN的网络结构对传统的FNN(Feedforward Neural Network)网络结构做了一些优化,使得其能够更适合处理CTR问题。在PNN网络模型中,主要的优化点为:

  1. 通过Embedding层处理离散特征。Embedding层现在已经成为DNN模型处理CTR问题的标配;
  2. 增加Product层,在Product Layer中,通过显式构造特征交叉,在不同的特征域之间进行特征组合,在实际的实施过程中,会有不同的product计算方法,在参考文献[1]中,提到了两种不同的product计算方法,分别为inner producr和outer product。

2. 算法原理

2.1. PNN的网络结构

PNN的网络结构如下图所示:

在这里插入图片描述

从网络结构上看,整个网络分成四层,第一层为特征Embedding层,第二层为Product层(PNN最为核心的部分), 第三层与第四层是传统的全连接网络层,最后模型的输出层。其网络结构与传统的DNN网络结构基本一致,不同的就是比传统DNN网络结构增加了Product层,与传统DNN的网络结构对比如下图所示:

在这里插入图片描述

2.2. PNN网络的计算过程

从上到下最上层上PNN的输出层,PNN网络的输出为

$$\hat{y}=\sigma \left (\mathbf{W}_3\mathbf{l}_2+b_3\right )$$

其中,$\mathbf{W}_3\in \mathbb{R}^{1\times D_2}$和$b_3\in \mathbb{R}$是L2层到输出层的参数,$\mathbf{l}_2\in \mathbb{R}^{D_2}$是L2层的输出,$D_2$为隐层L2层输出向量的维度,$\sigma$为输出层的激活函数,且是CTR计算中通常使用的激活函数,此处便不在赘述。L2层的输出$\mathbf{l}_2$为:

$$\mathbf{l}_2=relu\left ( \mathbf{W}_2\mathbf{l}_1+\mathbf{b}_2 \right )$$

其中,$\mathbf{W}_2\in \mathbb{R}^{D_2\times D_1}$和$\mathbf{b}_2\in \mathbb{R}^{D_2}$为L1层到L2层的参数,$\mathbf{l}_1\in \mathbb{R}^{D_1}$是L1层的输出,$D_1$为隐层L1层输出向量的维度,$relu$为L2层的激活函数。L1层的输出$\mathbf{l}_1$为:

$$\mathbf{l}_1=relu\left ( \mathbf{l}_z+\mathbf{l}_p+\mathbf{b}_1 \right )$$

其中,$\mathbf{b}_1\in \mathbb{R}^{D_1}$为Product层到L1层的参数。$\mathbf{l}_z\in \mathbb{R}^{D_1}$为Product的线形部分,$\mathbf{l}_p\in \mathbb{R}^{D_1}$ 为Product的特征交叉部分。$\mathbf{l}_z$和$\mathbf{l}_p$分别为:

$$\mathbf{l}_z=\left ( l_z^1,l_z^2,\cdots ,l_z^n,\cdots ,l_z^{D_1} \right ),\; l_z^n=\mathbf{W}_z^n\odot \mathbf{z}$$

$$\mathbf{l}_p=\left ( l_p^1,l_p^2,\cdots ,l_p^n,\cdots ,l_p^{D_1} \right ),\; l_p^n=\mathbf{W}_p^n\odot \mathbf{p}$$

其中,$\mathbf{W}_z^n$和$\mathbf{W}_p^n$是Embedding层到Product层的参数,$\mathbf{z}$为线型特征部分,$\mathbf{p}$为交叉特征部分,且$\mathbf{z}$为:

$$\mathbf{z}=\left ( \mathbf{z}_1,\mathbf{z}_2,\cdots ,\mathbf{z}_N \right )\overset{\underset{\triangle }{}}{=}\left ( \mathbf{f}_1,\mathbf{f}_2,\cdots ,\mathbf{f}_N\right )$$

其中,$\mathbf{f}_i\in \mathbb{R}^M$为第$i$个Embedding特征。交叉特征$\mathbf{p}$为:

$$\mathbf{p}=\left\{\mathbf{p}_{i,j} \right\}, i=1\cdots N,j=1\cdots N$$

其中,$\mathbf{p}_{i,j}=g\left ( \mathbf{f}_i,\mathbf{f}_j \right )$,$g$表示不同的特征交叉函数。Embedding特征$\mathbf{f}_i$为:

$$\mathbf{f}_i=\mathbf{W}_0^i\: \mathbf{x}_i\left [ start_{i} : end_{i} \right ]$$

而对于Product层的函数$g$,在参考文献[1]中提到了两种方法,分别为Inner Product和Outer Product。

2.2.1. Inner Product

在Inner Product中,函数$g$为:

$$g\left ( \mathbf{f}_i,\mathbf{f}_j \right )=\left<\mathbf{f}_i,\mathbf{f}_j \right>$$

其中,$\left<\mathbf{f}_i,\mathbf{f}_j \right>$表示的是向量$\mathbf{f}_i$和向量$\mathbf{f}_j$的内积。基于Inner Product的PNN模型又可以称为IPNN(Inner Product-based Neural Network)。此时$l_z^n$和$l_p^n$分别为:

$$l_z^n=\mathbf{W}_z^n\odot \mathbf{z}=\sum_{i=1}^{N}\left ( \mathbf{W}_z \right )_{i}\mathbf{z}_i=\sum_{i=1}^{N}\left ( \mathbf{W}_z \right )_{i}\mathbf{f}_i$$

$$l_p^n=\mathbf{W}_p^n\odot \mathbf{p}=\sum_{i=1}^{N}\sum_{j=1}^{N}\left ( \mathbf{W}_p^n \right )_{i,j}\mathbf{p}_{i,j}=\sum_{i=1}^{N}\sum_{j=1}^{N}\left ( \mathbf{W}_p^n \right )_{i,j}\left<\mathbf{f}_i,\mathbf{f}_j \right>$$

如何去分析Product层的计算复杂度?已知,$\mathbf{f}_i\in \mathbb{R}^M$,特征的个数为$N$,因此,$l_z^n$的时间复杂度为$O\left ( NM \right )$,$l_p^n$的时间复杂度$O\left ( N^2M \right )$,由$l_p^n$到$\mathbf{l}_p$的时间复杂度为$O\left ( N^2D_1 \right )$。因此,线型部分$\mathbf{l}_z$的时间复杂度为$O\left ( D_1NM \right )$,交叉部分$\mathbf{l}_p$的时间复杂度为$O\left ( N^2\left ( M+D_1 \right ) \right )$。

受FM算法中参数矩阵分解的启发,参考文献[1]中提出使用矩阵分解的方式来降低时间复杂度。其中要注意$\mathbf{p}_{i,j}$,$\mathbf{W}_p^n$都是对称矩阵,所以可以使用一阶矩阵分解。假设$\mathbf{W}_p^n=\mathbf{\theta }^n\mathbf{\theta }^{nT}$,其中$\mathbf{\theta }^n\in \mathbb{R}^N$。$l_p^n$可以表示为:

$$\begin{aligned} l_p^n&amp;=\mathbf{W}_p^n\odot \mathbf{p}=\sum_{i=1}^{N}\sum_{j=1}^{N}\left ( \mathbf{W}_p^n \right )_{i,j}\left<\mathbf{f}_i,\mathbf{f}_j \right> \\ &amp;=\sum_{i=1}^{N}\sum_{j=1}^{N}\theta _i^n\theta _j^n\left<\mathbf{f}_i,\mathbf{f}_j \right> \\ &amp;=\sum_{i=1}^{N}\sum_{j=1}^{N}\left<\theta _i^n\mathbf{f}_i,\theta _j^n\mathbf{f}_j \right> \\ &amp;=\left<\sum_{i=1}^{N}\theta _i^n\mathbf{f}_i,\sum_{j=1}^{N}\theta _j^n\mathbf{f}_j \right> \\ &amp;= \left\| \sum_{i=1}^{N}\delta _i^n\right\|^2 \end{aligned}$$

其中,$\delta _i^n=\theta _i^n\mathbf{f}_i$,则$\mathbf{l}_p$为:

$$\mathbf{l}_p=\left ( \left\| \sum_{i=1}^{N}\delta _i^1\right\|^2,\cdots ,\left\| \sum_{i=1}^{N}\delta _i^n\right\|^2,\cdots ,\left\| \sum_{i=1}^{N}\delta _i^{D_1}\right\|^2 \right )$$

时间复杂度为$O\left ( D_1NM \right )$。

2.2.2. Outer Product

在Outer Product中,函数$g$为:

$$g\left ( \mathbf{f}_i,\mathbf{f}_j \right )=\mathbf{f}_i\mathbf{f}_j^T$$

此时,由于$\mathbf{f}_i\in \mathbb{R}^M$,因此$\mathbf{p}_{i,j}\in \mathbb{R}^{M\times M}$是一个方阵。基于Outer Product的PNN模型又可以称为OPNN(Outer Product-based Neural Network)。此时$l_p^n$为:

$$l_p^n=\mathbf{W}_p^n\odot \mathbf{p}=\sum_{i=1}^{N}\sum_{j=1}^{N}\left ( \mathbf{W}_p^n \right )_{i,j}p_{i,j}=\sum_{i=1}^{N}\sum_{j=1}^{N}\left ( \mathbf{W}_p^n \right )_{i,j}\mathbf{f}_i\mathbf{f}_j^T$$

对于Outer Product,此时的$\mathbf{p}_{i,j}$为$M \times M$的矩阵,而$\mathbf{p}$是$N \times N \times M \times M$的矩阵,因此$\mathbf{p}$的计算时间复杂度为$O\left ( M^2N^2 \right )$,$\mathbf{l}_p$的计算时间复杂度为$O\left ( D_1M^2N^2 \right )$。参考文献[1]使用了叠加(superposition)的思想,重新定义了$\mathbf{p}$矩阵:

$$\mathbf{p}=\sum_{i=1}^{N}\sum_{j=1}^{N}\mathbf{f}_i\mathbf{f}_j^T=\mathbf{f}_{\sum }\left ( \mathbf{f}_{\sum } \right )^T,\; \mathbf{f}_{\sum }=\sum_{i=1}^{N}\mathbf{f}_i$$

此时, $\mathbf{p}\in \mathbb{R}^{M\times M}$,通过上述分析,最终$\mathbf{l}_p$的计算时间复杂度为$O\left ( D_1M\left ( M+N \right ) \right )$。

3. 总结

PNN网络结构在传统的DNN中增加了Product层,从而实现了特征的交叉,在具体的实现过程中,提出了两种Product的计算,分别为Inner Product和Outer Product。在具体的数据中,两种Product的表现并不一致,需要根据具体的数据选择合适的Product计算方法,相比较传统的DNN,从实验结果来看,效果上PNN得到了较大提升。

参考文献

[1] Qu Y , Han C , Kan R , et al. Product-Based Neural Networks for User Response Prediction[C]// 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, 2016.