[人工智能]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,?,l_z^n,?,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,?,l_p^n,?,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,?,{\mathbf{z}}_N\right)\stackrel{\underset{△}{}}{=}\left({\mathbf{f}}_1,{\mathbf{f}}_2,?,{\mathbf{f}}_N\right)$$

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

p = { p i , j } , i = 1 ? N , j = 1 ? N \mathbf{p}=\left\{\mathbf{p}_{i,j} \right\}, i=1\cdots N,j=1\cdots N p={pi,j?},i=1?N,j=1?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[star{t}_i:en{d}_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)=?{\mathbf{f}}_i,{\mathbf{f}}_j?$$

其中，$?{\mathbf{f}}_i,{\mathbf{f}}_j?$表示的是向量${\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}?{\mathbf{f}}_i,{\mathbf{f}}_j?$$

如何去分析Product层的计算复杂度？已知，${\mathbf{f}}_i\in {\mathbb{R}}^M$，特征的个数为$N$，因此，$l_z^n$的时间复杂度为$O\left(NM\right)$，$l_p^n$的时间复杂度$O\left(N^{2}M\right)$，由$l_p^n$到${\mathbf{l}}_p$的时间复杂度为$O\left(N^2{D}_1\right)$。因此，线型部分${\mathbf{l}}_z$的时间复杂度为$O\left(D_{1}NM\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={\theta }^n{\theta }^{nT}$，其中${\theta }^n\in {\mathbb{R}}^N$。$l_p^n$可以表示为：

$$\begin{array}{rl}{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{f}}_i,{\mathbf{f}}_j?\\ & =\sum _{i=1}^N\sum _{j=1}^N{\theta }_i^n{\theta }_j^n?{\mathbf{f}}_i,{\mathbf{f}}_j?\\ & =\sum _{i=1}^N\sum _{j=1}^N?{\theta }_i^n{\mathbf{f}}_i,{\theta }_j^n{\mathbf{f}}_j?\\ & =?\sum _{i=1}^N{\theta }_i^n{\mathbf{f}}_i,\sum _{j=1}^N{\theta }_j^n{\mathbf{f}}_j?\\ & ={\Vert \sum _{i=1}^N{\delta }_i^n\Vert }^2\end{array}$$

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

$${\mathbf{l}}_p=?{\Vert \sum _{i=1}^N{\delta }_i^1\Vert }^2,?,{\Vert \sum _{i=1}^N{\delta }_i^n\Vert }^2,?,{\Vert \sum _{i=1}^N{\delta }_i^{D_1}\Vert }^2?$$

时间复杂度为$O\left(D_{1}NM\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^2{N}^2\right)$，${\mathbf{l}}_p$的计算时间复杂度为$O\left(D_1{M}^2{N}^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_{1}M\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.