利用product解决特征交叉问题——PNN模型

解决痛点

传统模型：（应该指的是逻辑回归这种）挖掘特征的能力有限，比如无法挖掘到二阶特征
深度网络模型：无法应用到大规模高维稀疏特征上。
所以提出了PNN模型，该模型先用embedding层学习到类别特征的表达形式，再用一个乘积层学习到不同特征间的交叉信息，最后用全连接层学习到更高阶的特征表达。

网络结构

利用product解决特征交叉问题——PNN模型
从一个top-to-down的视角来看：

最顶层

最上面一层是一个CTR的输出
$\hat{y}=\sigma\left(\boldsymbol{W}_{3} \boldsymbol{l}_{2}+b_{3}\right)$ $\sigma(x)=1 /\left(1+e^{-x}\right)$

L2层

$l_{2}=\operatorname{relu}\left(\boldsymbol{W}_{2} \boldsymbol{l}_{1}+\boldsymbol{b}_{2}\right)$ 即一个**层，其中 $\boldsymbol{l}_{1} \in \mathbb{R}^{D_{1}}$

L1层

$\boldsymbol{l}_{1}=\operatorname{relu}\left(\boldsymbol{l}_{z}+\boldsymbol{l}_{p}+\boldsymbol{b}_{1}\right)$ 其中 $l_{z}, l_{p} ,b_{1} \in \mathbb{R}^{D_{1}}$ ，该维度与 $l_2$ 层维度相对应

这里定义tensor乘积的表达式
$\boldsymbol{A} \odot \boldsymbol{B} \triangleq \sum_{i, j} \boldsymbol{A}_{i, j} \boldsymbol{B}_{i, j}$ 即对应位置元素相乘然后求和。

定义：
$\begin{array}{l} \boldsymbol{z}=\left(\boldsymbol{z}_{1}, \boldsymbol{z}_{2}, \ldots, \boldsymbol{z}_{N}\right) \triangleq\left(\boldsymbol{f}_{1}, \boldsymbol{f}_{2}, \ldots, \boldsymbol{f}_{N}\right) \\ \boldsymbol{p}=\left\{\boldsymbol{p}_{i, j}\right\}, i=1 \ldots N, j=1 \ldots N \end{array}$
$l_z和l_p$ 的计算方法如下：
$\begin{array}{ll} \boldsymbol{l}_{z}=\left(l_{z}^{1}, l_{z}^{2}, \ldots, l_{z}^{n}, \ldots, l_{z}^{D_{1}}\right), & l_{z}^{n}=\boldsymbol{W}_{z}^{n} \odot \boldsymbol{z} \\ \boldsymbol{l}_{p}=\left(l_{p}^{1}, l_{p}^{2}, \ldots, l_{p}^{n}, \ldots, l_{p}^{D_{1}}\right), & l_{p}^{n}=\boldsymbol{W}_{p}^{n} \odot \boldsymbol{p} \end{array}$

其中：

$\boldsymbol{f}_{i} \in \mathbb{R}^{M}$ ，表示每个filed特征的embedding向量，由结构图可以看到，输入的是不同filed下的特征，（对于每个样本而言，每个filed下只有一个特征值），每个filed都有自己对应的权证矩阵 $W_{z}^{n}$ 和 $W_{p}^{n}$ 。
$z$ 部分和输入 $f$ 是完全等价的，只有 $p$ 部分用了特征的交叉

乘积函数 $g\left(\boldsymbol{f}_{i}, \boldsymbol{f}_{j}\right)$ 及其优化

根绝向量间求积的方式不同，有以下两种方式（内积和外积）：

Inner Product-based Neural Network (IPNN)
Outer Product-based Neural Network(OPNN)

IPNN

对于内积而言， $g\left(\boldsymbol{f}_{i}, \boldsymbol{f}_{j}\right)=<f_{i}, f_{j}>$ ，向量对应位置相乘求和得到一个数。
$l_{z}^{n}=\boldsymbol{W}_{z}^{n} \odot \boldsymbol{z}=\sum_{i=1}^{N} \sum_{j=1}^{M}\left(\boldsymbol{W}_{z}^{n}\right)_{i, j} \boldsymbol{z}_{i, j}\\l_{p}^{d}=\boldsymbol{W}_{p}^{d} \odot \boldsymbol{P}=\sum_{i=1}^{N} \sum_{j=1}^{N}\left(\boldsymbol{W}_{p}^{d}\right)_{i,j} \boldsymbol{P}_{i,j}$
对于每个部分而言，都有 $d$ 个 $W$ 矩阵， $w$ 的维度跟 $f$ 的维度有关,注意这里每个 $l_{z}^{n}$ 或者 $l_{p}^{n}$ 的计算都用到了 $z$ 或者 $p$ 的所有元素（之前有点confusion，以为是分别乘的）。

对于 $l_{1}$ 层的计算，其空间复杂度为 $O\left(D N M+D N^{2}\right)$ ，时间复杂度为 $O\left(D N M+D N^{2}\right)$ ， $D_{1}$ 为 $l_{1}$ 层的维度， $M$ 为特征的维度，为超参 $N$ 为filed的个数。

对于 $l_{p}$ 的计算，考虑到 $P$ 是个对称矩阵（ $P_{i,j} = P_{j,i}$ ）， $W$ 也是对称矩阵（相当于P矩阵中元素系数，相同元素系数相同），可以将 $W$ 矩阵进行分解， $\boldsymbol{W}_{p}^{n}=\boldsymbol{\theta}^{n} \boldsymbol{\theta}^{n T}，\boldsymbol{\theta}^{n} \in \mathbb{R}^{N}$ ，那么：
$\boldsymbol{W}_{p}^{n} \odot \boldsymbol{p}=\sum_{i=1}^{N} \sum_{j=1}^{N} \theta_{i}^{n} \theta_{j}^{n}\left\langle\boldsymbol{f}_{i}, \boldsymbol{f}_{j}\right\rangle=\left\langle\sum_{i=1}^{N} \boldsymbol{\delta}_{i}^{n}, \sum_{i=1}^{N} \boldsymbol{\delta}_{i}^{n}\right\rangle$ $\boldsymbol{\delta}_{i}^{n}=\theta_{i}^{n} \boldsymbol{f}_{i}$ $\boldsymbol{\delta}^{n}=\left(\boldsymbol{\delta}_{1}^{n}, \boldsymbol{\delta}_{2}^{n}, \ldots, \boldsymbol{\delta}_{i}^{n}, \ldots, \boldsymbol{\delta}_{N}^{n}\right) \in \mathbb{R}^{N \times M}$
通过该变换，可以将原来时间和空间复杂度都降到 $O(DNM)$ （在真实场景中特征filed的个数N要远大于embedding的维度M）;

OPNN

外积的结果是矩阵
$\boldsymbol{P}_{i j}=\boldsymbol{f}_{i} \boldsymbol{f}_{j}^{T} \in \mathbb{R}^{M * M}$

$\boldsymbol{P}=\sum_{i=1}^{N} \sum_{j=1}^{N} \boldsymbol{P}_{i j}=\sum_{i=1}^{N} \sum_{j=1}^{N} \boldsymbol{f}_{i} \boldsymbol{f}_{j}^{T}=\left(\sum_{j=1}^{N} \boldsymbol{f}_{i}\right)\left(\sum_{j=1}^{N} \boldsymbol{f}_{i}\right)^{T} \in \mathbb{R}^{M * M}$ 待研究
ps(写完代码再来完善理论）