1. 概述
PNN（Product-based Neural Network）是在2016年提出的用于计算CTR问题的深度神经网络模型，PNN的网络结构对传统的FNN（Feedforward Neural Network）网络结构做了一些优化，使得其能够更适合处理CTR问题。在PNN网络模型中，主要的优化点为：
- 通过Embedding层处理离散特征。Embedding层现在已经成为DNN模型处理CTR问题的标配；
- 增加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}_3mathbf{l}_2 b_3right ) 其中，mathbf{W}_3in mathbb{R}^{1times D_2} 和b_3in mathbb{R} 是L2层到输出层的参数，mathbf{l}_2in mathbb{R}^{D_2} 是L2层的输出，D_2 为隐层L2层输出向量的维度，sigma 为输出层的激活函数，且是CTR计算中通常使用的激活函数，此处便不在赘述。L2层的输出mathbf{l}_2 为：
其中，mathbf{W}_2in mathbb{R}^{D_2times D_1} 和mathbf{b}_2in mathbb{R}^{D_2} 为L1层到L2层的参数，mathbf{l}_1in mathbb{R}^{D_1} 是L1层的输出，D_1 为隐层L1层输出向量的维度，relu 为L2层的激活函数。L1层的输出mathbf{l}_1 为：
其中，mathbf{b}_1in mathbb{R}^{D_1} 为Product层到L1层的参数。mathbf{l}_zin mathbb{R}^{D_1} 为Product的线形部分，mathbf{l}_pin mathbb{R}^{D_1} 为Product的特征交叉部分。mathbf{l}_z 和mathbf{l}_p 分别为：
其中，mathbf{W}_z^n 和mathbf{W}_p^n 是Embedding层到Product层的参数，mathbf{z} 为线型特征部分，mathbf{p} 为交叉特征部分，且mathbf{z} 为：
其中，mathbf{f}_iin mathbb{R}^M 为第i 个Embedding特征。交叉特征mathbf{p} 为：
其中，mathbf{p}_{i,j}=gleft ( mathbf{f}_i,mathbf{f}_j right ) ，g 表示不同的特征交叉函数。Embedding特征mathbf{f}_i 为：
而对于Product层的函数g ，在参考文献[1]中提到了两种方法，分别为Inner Product和Outer Product。
2.2.1. Inner Product
在Inner Product中，函数g 为：
其中，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 分别为：
如何去分析Product层的计算复杂度？已知，mathbf{f}_iin mathbb{R}^M ，特征的个数为N ，因此，l_z^n 的时间复杂度为Oleft ( NM right ) ，l_p^n 的时间复杂度Oleft ( N^2M right ) ，由l_p^n 到mathbf{l}_p 的时间复杂度为Oleft ( N^2D_1 right ) 。因此，线型部分mathbf{l}_z 的时间复杂度为Oleft ( D_1NM right ) ，交叉部分mathbf{l}_p 的时间复杂度为Oleft ( N^2left ( M D_1 right ) right ) 。
受FM算法中参数矩阵分解的启发，参考文献[1]中提出使用矩阵分解的方式来降低时间复杂度。其中要注意mathbf{p}_{i,j} ，mathbf{W}_p^n 都是对称矩阵，所以可以使用一阶矩阵分解。假设mathbf{W}_p^n=mathbf{theta }^nmathbf{theta }^{nT} ，其中mathbf{theta }^nin mathbb{R}^N 。l_p^n 可以表示为：
其中，delta _i^n=theta _i^nmathbf{f}_i ，则mathbf{l}_p 为：
时间复杂度为Oleft ( D_1NM right ) 。
2.2.2. Outer Product
在Outer Product中，函数g 为：
此时，由于mathbf{f}_iin mathbb{R}^M ，因此mathbf{p}_{i,j}in mathbb{R}^{Mtimes M} 是一个方阵。基于Outer Product的PNN模型又可以称为OPNN（Outer Product-based Neural Network）。此时l_p^n 为：
对于Outer Product，此时的mathbf{p}_{i,j}为M times M 的矩阵，而mathbf{p} 是N times N times M times M 的矩阵，因此mathbf{p} 的计算时间复杂度为Oleft ( M^2N^2 right ) ，mathbf{l}_p 的计算时间复杂度为Oleft ( D_1M^2N^2 right ) 。参考文献[1]使用了叠加（superposition）的思想，重新定义了mathbf{p} 矩阵：
此时， mathbf{p}in mathbb{R}^{Mtimes M} ，通过上述分析，最终mathbf{l}_p 的计算时间复杂度为Oleft ( D_1Mleft ( 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.
