推荐系统的PNN算法

看算法看到了PNN，找了好几篇介绍没太看懂，决定自己看完章理一遍。
前期算法储备：

FM算法
FFM算法
DeepFM
PNN算法结构图

PNN结构图

从上往下看：
最后一层为输出层执行操作为：
$\hat{a} =\sigma(W_{3}l_{2}+b_{3})$
其中 $l_{2}$ 表示第二层隐藏层的输出。
隐层二执行操作：
$l_{2} = relu(W_{2}l_{1}+b_{2})$
$l_{1}$ 为隐藏层1的输出。
隐藏层1执行操作：
$l_{1} = relu(l_{z}+l_{p}+b_{1})$
$l_{z}$ 表示线性部分， $l_{p}$ 表示非线性部分。
定义
$l_z=(l^1_z,l^2_z,...,l^{D_{1}}_z),l^1_z = W^n_{z} \oplus z\\ l_p=(l^1_p,l^2_p,...,l^{D_{1}}_p), l^1_p = W^n_{p} \oplus p\\$
其中 $W^n_{z}$ 和 $W^n_{z}$ 为权重参数, $D$ 为第一层神经元的个数。 $\oplus$ 表示矩阵或者向量对应位置相乘后所有元素的和，即 $A \oplus B = \sum_{i,j}A_{i,j}B_{i,j}$ (这个定于与卷积的定义相同)，如 $A=\left( \begin{aligned} 1, 2 \\ 2, 1 \\ \end{aligned} \right),B= \left( \begin{aligned} 2,1 \\ 3, 2 \\ \end{aligned} \right)\\ A \oplus B = 1*2+2*1+2*3+1*2=12$
有 $\oplus$ 的定义可以知道， $l^i_{z}$ 和 $l^i_{p}$ 均是一个一个的数值。

首先明确一下各个字母的含义： $M$ 为特征 $embedding$ 后的向量维度， $N$ 表示用于 $embedding$ 的特征总数， $D_{1}、D_{2}$ 表示一层和而第二层的神经元个数。 $f_{i}$ 表示特征 $i \space embedding$ 后的 $M$ 维向量， $f_{i} \in R^M$ 。

下面具体先看一下 $l_{z}$
$定义： l_z=(l^1_z,l^2_z,...,l^D_z),l^1_z = W^n_{z} \oplus z \\ z = (z_{1},z_{2},...z_{N})=(f_{1},f_{2},...f_{N})\\ 即： z =\begin{bmatrix} {z_{11}}&{z_{12}}&{\cdots}&{a_{1N}}\\ {a_{21}}&{a_{22}}&{\cdots}&{a_{2N}}\\ {\vdots}&{\vdots}&{\ddots}&{\vdots}\\ {a_{M1}}&{a_{M2}}&{\cdots}&{a_{MN}}\\ \end{bmatrix}_{M*N}\\$
$W^n_{z}$ 与z按元素相乘，所以 $W^n_{z} \in R^{M*N},W^n_{z} \oplus z=一个数值$
$l_z=(num^1_z,num^2_z,...,num^D_z)$
所以线性层的参数维度为 $D_{1}*M*N$

下面再看 $l_{p}$ :
由定义 $p$ 层中 $l_p = (l^1_p,l^2_p,...,l^n_p),l^n_p=W^n_{p} \oplus p$ , $p = \{ p_{ij} \}，p为一个矩阵$ ，同理 $W^n_{p}$ 为 $p$ 的权重，也为一个矩阵。
具体的：
$p = \{ p_{ij} \}= \{g(f_i,f_j)\}$
即 $p$ 中的每一个元素 $p_{ij}，均是由f_i和f_j的函数g$ 计算得出， $g$ 可以给出不同的定义。
文章中函数 $g$ 定义了两种
1. 基于内积的函数(Inner Product-based Neural Network,IPNN)
$g(f_i,f_j)=<f_i,f_j>$
即向量的内积。则 $f_i$ 可以表示为
$f_i = \left( f_{i1}, f_{i2}, ..., f_{iM}\right)^{T}$
$g(f_i,f_j)=<f_i,f_j>=f_{i1}*f_{j1},+f_{i2}*f_{j2}+ ...,+f_{iM}*f_{jM}$
由于 $i = 1,2,...N$ ,所以 $p \in R^{N*N}$ ，故权重矩阵 $W^n_{p} \in R^{N*N}$ 。 $l^n_{p}=W^n_{p} \oplus p$ =一个数值。

与FM算法的思路类似，考虑将 $W^n_{p}$ 进行因子分解。因为 $p_{ij}=p_{ji},p为对称矩阵，所以W^n_{p}$ 也为对称矩阵，因此可以将其分解为 $W^n_{p} = \theta^n\theta^{n^T}, \theta^n \in R^N$ ,此时
$W^n_{p} \oplus p = \sum^N_{i=1} \sum^N_{i=1} \theta^n_{i}\theta^n_{j}<f_{i},f_{j}> = <\sum^N_{i=1} \delta^n_{i}, \sum^N_{i=1} \delta^n_{i}> = ||\sum_{i}\delta^n_{i}||\\ 其中\delta^n_{i} = \theta^n_{i}f_{i},\delta^n_{i} \in R^M$
记 $\delta^n = (\delta^n_{1} ,\delta^n_{2} ....\delta^n_{N} )\in R^{M*N}$
$l_{p} =(||\sum_{i}\delta^1_{i}||...||\sum_{i}\delta^n_{i}||...||\sum_{i}\delta^{D^{1}}_{i}||)$
最终参数 $W^n_{p}$ 中的参数即为 $\theta^{n}$ ,故inner product涉及的参数总量为 $D_{1}*N$ 。
2. 基于外积的函数(Outer Product-based Neural Network)
此处外积定义为矩阵乘法：
$g(f_i,f_j)=f_if_j^T=\left( \begin{aligned} f_{i1} \\ f_{i2} \\ {\vdots}\\ f_{im} \end{aligned} \right)_{M*1}*(f_{j1} ,f_{j2} ,{\cdots},f_{im})_{1*M}$
由矩阵的乘法，得到 $p_{ij} =g(f_i,f_j) \in R^{M*M},p=\{ p_{ij} \} \in R^{M*M}$ 。即 $g$ 为一个 $M$ 维的方阵，其中其每个元素同时也是一个 $M$ 维的方阵。

如果第一层神经元的个数用 $D_{1}$ 表示，此时模型的时间复杂度为 $O(D_{1}N^2M^2)$ ,其中 $f_if_j^T$ 复杂度为 $M^2$ ,样本个数为 $N$ ， $f_if_j^T$ 需要计算 $N(N-1)/2$ 次，复杂度为 $O(N^2)$ ,故总的为 $O(D_{1}N^2M^2)$ 。
为了降低复杂度，定义
$p = \sum^N_{i=1}\sum^N_{j=1}f_{i}f_{j}^T = (\sum^N_{j=1}f_{i})*(\sum^N_{j=1}f_{j})^T$
此时仍有 $p\in R^{M*M}$ ，复杂度为 $O(D_{1}M(M+N))$ , $W^n_{p} \in R^{M*M}$ 。故outer product层的参数总量为 $D_{1}*M*M$ 。 $l^n_{p}=W^n_{p} \oplus p$ =一个数值。
$l_{p} = (num^1_p,num^2_p,...,num^D_p)$
即其实最终 $l_{p}和l_{z}均为一个D^1$ 维的数组。

代码部分参考: 推荐系统遇上深度学习(六)--PNN模型理论和实践

推荐系统的PNN算法

推荐阅读更多精彩内容