Question

1. 学习和预测用户响应response 在信息检索 information retrieval: IR 的许多个性化任务中起到至关重要的作用，例如推荐系统、web 搜索、在线广告。用户响应预测的目标是估计用户positive response （如点击、购买等）的概率。这个预测的概率表示用户对特定 item （如新闻文章、电商的商品等）的兴趣，并影响后续决策，例如 document ranking、广告出价等等。

   这些 IR 任务中的数据集大多数采用 multi-field 的离散categorical 形式，例如 [Weekday=Tuesday, Gender=Male, City=London] 。通常通过 one-hot 编码将这种形式的特征转换为高维稀疏二元特征。例如包含上述三个 field 的特征向量被 one-hot 编码为：

   $ \underbrace{[0,1,0,0,0,0,0]}_{\text{Weekday = Tuesday}}\quad\underbrace{[0,1]}_{\text{Gender = Male}}\quad\underbrace{[0,0,1,0,\cdots,0,0]}_{\text{City=London}} $

   许多机器学习模型，包括线性逻辑回归logistic regression: LR 、非线性梯度提升决策树gradient boosting decision tree: GBDT、分解机factorization machine: FM 等等，已经被提出来用于处理此类高维稀疏二元特征并产生高质量的用户响应预测。然而，这些模型高度依赖于特征工程来捕获高阶high-order潜在模式 latent pattern 。因此面对极端的稀疏性，传统模型可能会受限于从数据中挖掘浅层模式的能力。

   最近，深度神经网络 DNN 在分类和回归任务中表现出强大的能力，包括计算机视觉、语音识别、自然语言处理。在用户响应预测中采用 DNN 很有前景，因为 DNN 可以自动学习更具有表达性expressive 的特征并提供更好的预测性能。但是面对高维输入的场景，DNN 模型的参数规模巨大导致难以应用。

   为了改善 multi-field 离散数据交互，《Deep learning over multi-field categorical data: A case study on user response prediction》 提出了一种基于FM 预训练的 embedding 方法。该方法基于拼接的 embedding 向量，并构建了多层感知机MLP 来探索特征交互feature interaction 。

   然而，embedding 初始化的质量在很大程度上受限于 FM 。更重要的是，感知机layer 的 add 操作可能无法用于探索 multi-field 中离散数据的交互。先前的工作表明，可以通过特征向量 product 操作而不是 add 操作来有效地探索来自不同field 的特征之间的局部依赖关系。

   为了利用神经网络的学习能力，并以比 MLP 更有效的方式挖掘数据的潜在模式，论文 《Product-based Neural Networks for User Response Prediction》 提出了 Product-based Neural Network: PNN，它具有以下特点：

   • 使用没有预训练的 embedding 层。
   • 基于 embedding 的特征向量构建一个 product layer，从而建模 inter-field 特征交互。
   • 使用全连接的 MLP 进一步提取高阶特征模式。

   论文出了两种类型的 PNN ，分别在 product layer 执行内积 inner product 操作（即 IPNN）和外积 outer product 操作（即 OPNN ），从而有效地对交互模式进行建模。

   论文以在线广告的 CTR 预估为例，探讨 PNN 模型的学习能力。在两个大规模真实世界数据集上的大量实验结果表明：PNN 模型在各种指标上始终优于 state-of-the-art 的用户响应预测模式。

2. 相关工作：响应预测response prediction 问题通常被表述为基于最大似然或交叉熵的二分类问题。

   从建模的角度来看，线性逻辑回归 logistic regression: LR、非线性梯度提升决策树 gradient boosting decision tree: GBDT 、非线性因子分解机 factorization machine: FM 在工业 application 中得到广泛应用。然而，这些模型在挖掘高阶潜在模式或学习高质量特征 representation 方面受到限制。

   深度学习能够探索高阶潜在模式high-order latent pattern以及泛化的、有表达力的数据 representation 。DNN 的输入通常是稠密实值向量，而multi-field 离散categorical 数据的解决方案尚未得到很好的研究。

   • 《Deep learning over multi-field categorical data: A case study on user response prediction》 中提出了 Factorization-machine supported neural network: FNN，它通过预训练的 FM 学习离散数据的 embedding 向量。
   • 《A convolutional click prediction model》 中提出了 Convolutional Click Prediction Model: CCPM 来预测广告点击。然而在 CCPM 中，卷积仅在某种对齐 alignment 的相邻 fields 上执行，无法对非相邻 fields 之间的完整交互进行建模。
   • 《Sequential click prediction for sponsored search with recurrent neural networks》 利用 RNN 将用户 queries 建模为一系列用户上下文，从而预测广告点击行为。
   • 《Training product unit neural networks》 提出了 Product unit neural network: PUNN 来构建输入的高阶组合。然而，PUNN 既不能学习局部依赖local dependency ，也无法产生有界的输出bounded output 从而适应响应率response rate （即点击率）。

   在本文中，我们展示了我们的 PNN 模型学习局部依赖和高阶特征交互的方式。

3.1 模型

1. 我们以在线广告的 CTR 预估为例来描述我们的模型，并探索该模型在各种指标上的表现。 CTR 预估任务是构建一个预估模型从而估计用户在给定上下文中点击特定广告的概率。

   每个数据样本由 multi-field 的离散数据组成，例如用户信息（性别、城市等）、广告信息（广告ID、广告类目ID）、上下文信息（曝光时刻等）。所有信息都表示为一个 multi-field categorical 特征向量，其中每个 field （例如城市）都是 one-hot 编码的，如前所述。

   这种 field-wise 的 one-hot 编码会导致维数灾难和巨大的稀疏性。此外，field 之间存在局部依赖性 local dependency 和层级结构 hierarchical structure 。因此，我们正在寻求一种 DNN 模型来捕获 multi-field 离散数据中的高阶潜在模式。

   我们提出的 product layer 的想法来自自动探索特征交互。在 FM 中，特征交互被定义为两个特征向量的内积。因此，我们提出了 Productbased Neural Network: PNN 模型。接下来我们详细介绍 PNN 模型并讨论该模型的两种变体，即Inner Product-based Neural Network: IPNN （采用 inner product layer）、Outer Product-based Neural Network : OPNN（采用 outer product layer）。

2. PNN 模型的架构如下图所示。假设 one-hot 向量为 $ \mathbf{\vec x}\in \mathbb R^n $ 包含 $ F $ 个 field ，field i 在向量中的起始位置为 $ s_i $ 、终止位置为 $ e_i $ （包含），即 $ \mathbf x[s_i:e_i] $ 。其中 $ n=e_F-s_1 $ 。每个 field 生成一个 embedding 向量，即 field i 生成 $ \mathbf{\vec f}_i = \left(f_1^{(i)},f_2^{(i)},\cdots,f_K^{(i)}\right)^\top \in \mathbb R^{K} $ 。

   模型包含以下几层：

   • 第 0 层输入层：categorical 特征经过 one-hot 编码之后作为输入。

   • 第1层embedding 层：模型从每个 field 中学得各 field 的 embedding 表示。

     输入位置 $ s_i \sim e_i $ 仅仅与 $ \mathbf{\vec f}_i $ 相连，即局部连接： $ \mathbf{\vec f}_i = \mathbf W_0^{(i)} \mathbf x[s_i:e_i] $ ，其中 $ \mathbf W_0^{(i)} \in \mathbb R^{K\times (e_i-s_i+1)} $ 为映射参数。

   • 第2层 product 层：由embedding 特征的一阶特征和二阶交互特征拼接而成。其中 $ \mathbf Z $ 表示一阶特征， $ \mathbf P $ 表示二阶特征。为统一生成方式， $ \mathbf Z $ 由常数 1 和一阶特征进行交互而生成。

     $ \mathbf Z = \left[\mathbf{\vec f}_1,\cdots,\mathbf{\vec f}_F\right]\in \mathbb R^{K\times F}\\ \mathbf P = \{p_{i,j}\}=\left\{g\left(\mathbf{\vec f}_i,\mathbf{\vec f}_j\right)\right\},\quad i=1,\cdots,F;j=1,\cdots,F $

     其中 $ g(\cdot,\cdot) $ 表示成对特征交互。当定义不同的 $ g $ 函数时，就定义了不同的 PNN 实现。

     product 层的输出为：

     $ h_z^{(i)} = \mathbf W_z^{(i)}\odot \mathbf Z,\quad h_p^{(i)} = \mathbf W_p^{(i)}\odot \mathbf P\\ \mathbf{\vec h}_z = \left(h_z^{(1)},h_z^{(2)},\cdots,h_z^{(d_2)}\right)^\top\\ \mathbf{\vec h}_p = \left(h_p^{(1)},h_p^{(2)},\cdots,h_p^{(d_2)}\right)^T\\ \mathbf{\vec h}_{2} = \text{relu}\left(\mathbf{\vec h}_z + \mathbf{\vec h}_p + \mathbf{\vec b}_1\right) $

     其中：

     • $ \odot $ 表示张量的内积，定义为： $ \mathbf A\odot \mathbf B = \sum_{i,j}A_{i,j}\times B_{i,j}\in \mathbb R $ 。
     • $ \mathbf W_z^{(i)}\in \mathbb R^{K\times F},\mathbf W_p^{(i)}\in \mathbb R^{F\times F} $ 类似于 CNN 的卷积核，它们在整个输入上进行张量内积。 $ i $ 表示第 $ i $ 个卷积核，一共有 $ d_2 $ 个卷积核。

   • 第 3 层到第 $ L $ 层：全连接层。

     $ \mathbf{\vec h}_{3} = \text{relu}\left(\mathbf W_2 \mathbf{\vec h}_2+\mathbf{\vec b}_2\right)\in \mathbb R^{d_3}\\ \vdots\\ \mathbf{\vec h}_{L} = \text{relu}\left(\mathbf W_{L-1} \mathbf{\vec h}_{L-1}+\mathbf{\vec b}_{L-1}\right)\in \mathbb R $

   • 最后一层：sigmoid 输出层。

     $ \hat y = \text{sigmoid}(h_L) $

   模型的损失函数为 logloss：

   $ \mathcal L(y,\hat y) = -y\times \log \hat y - (1-y)\times \log(1-\hat y) $

   

3.1.1 IPNN

1. Inner Product-based neural network: IPNN：IPNN 的特征交互函数为：

   $ p_{i,j} = g\left(\mathbf{\vec f}_i,\mathbf{\vec f}_j\right) = \mathbf{\vec f}_i\cdot\mathbf{\vec f}_j $

   则有：

   $ h_z^{(i)} = \mathbf W_z^{(i)}\odot \mathbf Z =\sum_{t=1}^F\sum_{s=1}^K \left(W_z^{(i)}\right)_{t,s}\times z_{t,s}=\sum_{t=1}^F\sum_{s=1}^K \left(W_z^{(i)}\right)_{t,s}\times f_{t,s}\\ h_p^{(i)} = \mathbf W_p^{(i)}\odot \mathbf P = \sum_{t=1}^F\sum_{s=1}^F\left(W_p^{(i)}\right)_{t,s}\times p_{t,s} = \sum_{t=1}^F\sum_{s=1}^F \left(W_p^{(i)}\right)_{t,s}\times \mathbf{\vec f}_t\cdot \mathbf{\vec f}_s $

   则计算 $ \mathbf{\vec h}_2 $ 的复杂度为：

   • 空间复杂度： $ O(d_2F\times (K+F)) $ 。它们分别是计存储 $ \mathbf W_z,\mathbf W_p $ 的空间需求。
   • 时间复杂度： $ O(F^2d_2+FKd_2) $ 。其中 $ \left\{ \mathbf{\vec f}_t\cdot \mathbf{\vec f}_s\right\}_{t,s} $ 可以预先计算好，其计算复杂度为 $ O(F^2d_2) $ 。

2. 为降低复杂度，可以将 $ \mathbf W_p^{(i)} $ 分解为 $ \mathbf W_p^{(i)} = \vec\theta^{(i)} \left(\vec\theta^{(i)} \right)^\top $ ，其中 $ \vec\theta^{(i)} = \left(\theta^{(i)}_1,\cdots,\theta^{(i)}_F\right)^\top\in \mathbb R^F $ 。则有：

   $ h_p^{(i)} = \mathbf W_p^{(i)}\odot \mathbf P = \sum_{t=1}^F\sum_{s=1}^F \left(W_p^{(i)}\right)_{t,s}\times\mathbf{\vec f}_t\cdot\mathbf{\vec f}_s\\ = \sum_{t=1}^F\sum_{s=1}^F \theta^{(i)}_t\theta^{(i)}_s\times\mathbf{\vec f}_t\cdot\mathbf{\vec f}_s = \left( \sum_{s=1}^F \vec\delta_s^{(i)}\right)\cdot \left( \sum_{s=1}^F \vec\delta_s^{(i)}\right) $

   其中 $ \vec\delta_s^{(i)} = \theta_s^{(i)} \mathbf{\vec f}_s \in \mathbb R^K $ 。

   则有：

   $ \mathbf{\vec h}_p = \left(\left\|\sum_{s=1}^F \vec\delta_s^{(1)}\right\|^2,\cdots,\left\|\sum_{s=1}^F \vec\delta_{s}^{(d_2)}\right\|^2\right)^\top $

   则计算 $ \mathbf{\vec h}_2 $ 的复杂度为：空间复杂度 $ O(d_2FK) $ ，时间复杂度 $ O(d_2FK) $ 。

3. $ \mathbf W_p^{(i)} = \vec\theta^{(i)} \left(\vec\theta^{(i)} \right)^\top $ 仅仅是一阶分解，实际上可以进行更加通用的 $ M $ 阶分解：

   $ h_p^{(i)} = \mathbf W_p^{(i)}\odot \mathbf P = \sum_{t=1}^F\sum_{s=1}^F \left(W_p^{(i)}\right)_{t,s}\times\mathbf{\vec f}_t\cdot\mathbf{\vec f}_s\\ = \sum_{t=1}^F\sum_{s=1}^F \left(\vec \theta^{(i)}_t\cdot\vec \theta^{(i)}_s\right)\times\mathbf{\vec f}_t\cdot\mathbf{\vec f}_s = \left( \sum_{s=1}^F \vec\delta_s^{(i)}\right)\cdot \left( \sum_{s=1}^F \vec\delta_s^{(i)}\right) $

   其中 $ \vec\theta_s^{(i)} \in \mathbb R^M $ 。此时有：

   $ \mathbf W_p^{(i)} =\mathbf\Theta^{(i)}\left(\mathbf\Theta^{(i)}\right)^{\top},\quad \mathbf \Theta ^{(i)} = \begin{bmatrix} \left(\vec\theta_1^{(i)}\right)^\top\\ \vdots\\ \left(\vec\theta_F^{(i)}\right)^\top \end{bmatrix}\in \mathbb R^{F\times M} $

   这种分解的代价更高，同时约束更弱。

3.1.2 OPNN

1. 给定两个输入向量，向量内积输出一个标量，而向量外积输出一个矩阵。Outer Product-based neural network: OPNN 利用了向量外积，它和 IPNN 的唯一区别在于特征交互函数 $ g(\cdot,\cdot) $ 。在 OPNN 中，特征交互函数为：

   $ p_{i,j} = g\left(\mathbf{\vec f}_i,\mathbf{\vec f}_j\right) = \mathbf{\vec f}_i \mathbf{\vec f}_j ^\top\in \mathbb R^{K\times K} $

   与内积产生标量不同，这里的外积产生一个矩阵。则 $ \mathbf P \in \mathbb R^{F\times F\times K\times K}, \mathbf W_p^{(i)} \in \mathbb R^{F\times F\times K\times K} $ 。

   计算 $ \mathbf{\vec h}_2 $ 的复杂度为：

   • 空间复杂度： $ O(d_2\times F^2\times K^2) $ 。它完全由 $ \mathbf W_p $ 主导。
   • 时间复杂度： $ O(d_2\times F^2\times K^2) $ 。它完全由 $ \mathbf{\vec h}_p $ 主导。

2. 为降低复杂度，定义：

   $ \mathbf P = \sum_{i=1}^F\sum_{j=1}^F \mathbf{\vec f}_i \mathbf{\vec f}_j ^\top = \mathbf{\vec f}_\Sigma \mathbf{\vec f}_\Sigma ^\top \in \mathbb R^{K\times K}\\ \mathbf{\vec f}_\Sigma = \sum_{i=1}^F \mathbf{\vec f}_i \in \mathbb R^K $

   此时 $ \mathbf W_p^{(i)} \in \mathbb R^{ K\times K} $ 。

   则计算 $ \mathbf{\vec h}_2 $ 的复杂度为：空间复杂度 $ O(d_2K\times (F+K)) $ ，它们分别是计存储 $ \mathbf W_z,\mathbf W_p $ 的空间需求；时间复杂度： $ O(d_2 K\times (K+F)) $ 。

3.1.3 讨论

1. 和 FNN 相比，PNN 有一个 product layer。如果移除product layer 中的 $ \mathbf{\vec h}_p $ 部分时，FNN 和 PNN 完全相同。

2. IPNN 和 FM 模型非常相似。

   • FM 模型将抽取的一阶、二阶特征直接送入分类器。
   • IPMM 模型将抽取的一阶、二阶特征，首先使用类似 CNN 的 “核函数” （由 $ \mathbf W_z,\mathbf W_p $ 给出）抽取 $ d_2 $ 个特征，然后将抽取后的特征送入 DNN 。

3. PNN 使用 product layer 来探索特征交互。向量的product 可以视为一系列的 “乘法&加法” 操作，内积和外积只是两种不同的实现。

   事实上可以定义更通用或者更复杂的 product layer，从而获得 PNN 更好的探索特征交互的能力。

4. 类似于电子电路，乘法相当于 AND、加法相当于 OR。product layer 似乎学习特征以外的规则。因此我们相信在神经网络中引入 product 运算将提高网络对 multi-field 离散数据建模的能力。

3.2 实验

1. 数据集：

   • Criteo：Criteo 1TB 点击日志是著名的广告技术工业 benchmark 数据集。我们选择连续 7 天的样本进行训练，第 8 天的数据进行评估。

     由于数据规模巨大，因此我们对数据集进行负降采样。我们将降采样比例定为 $ w $ ，将预估的 CTR 定义为 $ p $ ，重新校准的 CTR $ q $ 为： $ q = p/(0+ \frac{1-p}{w}) $ 。

     经过降采样和特征映射之后，我们得到一个数据集，其中包含 7938 万个样本，特征维度为 164 万维。

   • iPinYou：iPinYou 数据集是另一个真实世界数据集，记录了超过 10 天的广告点击日志。经过 one-hot 编码之后，我们得到一个包含 1950 万个样本的数据集，特征维度为 937.67K 。

     我们保留原始的训练/测试拆分方案：对于每个广告主，最后 3 天的数据用作测试集，其余的数据用作训练集。

2. baseline 方法：

   • LR：LR 是工业中使用最广泛的线性模型，它易于实现且训练速度快，但是无法捕获非线性信息。
   • FM：FM 在推荐系统和用户响应预测任务中有很多成功的应用。FM 探索特征交互，这对稀疏数据很有效。
   • FNN：FNN 能够捕获 multi-field 离散数据的高阶潜在模式。
   • CCPM：CCPM 是一种用于点击预估的卷积模型。该模型有效地学习 local-global 特征。然而，CCPM 高度依赖特征对齐feature alignment，并且缺乏解释。
   • IPNN：采用内积的 PNN。
   • OPNN：采用外积的 PNN。
   • PNN*：该模型的 product layer 是 IPNN product layer 和 OPNN product layer 的拼接。

3. 模型配置：

   • 所有方法都是基于 TensorFlow 实现，并采样随机梯度下降SGD 来训练。

   • 在 FM 中，我们采用 10 维的分解。相应地，我们在网络模型中采用 10 维的 embedding 。

   • 网络结构：

     • CCPM 有 1 个 embedding 层、2 个卷积层（具有最大池化）、1 个隐层，一共4 层。
     • FNN 有 1 个 embedding 层、3 个隐层，一共 4 层。
     • 每种 PNN 都有 1 个 embedding 层、1 个 product layer、3 个隐层，一共 5 层。

   • 为了防止过拟合，LR 和 FM 模型使用 L2 正则化训练，而 FNN, CCPM, PNN 使用 dropout 训练。

     默认情况下，我们设置 dropout rate = 0.5 。下图给出了 Criteo 数据集上 OPNN 模型的 AUC 随着 dropout rate 变化的曲线。

     

4. 评估指标：我们采用评估指标为 AUC 和相对信息增益 Relative Information Gain: RIG。其中，RIG 定义为： $ \text{RIG = 1- NE} $ ，NE 为归一化的交叉熵。

   此外，我们还使用 LogLoss 和 RMSE 作为额外的评估指标。

3.2.1 模型对比

1. 不同模型在这两个数据集上的实验结果如下表所示。首先我们关注 AUC 性能，表 I 和表 II 的结果表明：

   • FM 优于 LR，证明了特征交互的有效性。
   • 神经网络优于 LR 和 FM，这证明了高阶潜在模式的重要性。
   • PNN 在所有数据集上表现最好。
   • 另外，结合了 IPNN 和 OPNN 的 PNN* 没有明显优于 IPNN 或 OPNN。我们认为 IPNN 和 OPNN 足以捕获 multi-field 离散数据中的特征交互。

   关于 logloss, RMSE, RIG 指标，结论也是类似的。

   

2. 然后我们还在 PNN 和 baseline 模型之间进行 t-test 。下表给出了两个数据集上 logloss 损失下计算的 p-value 。结果验证了我们的模型相对于 baseline 模型显著提高了用户响应预测性能。

   

3. 下图显示了在 iPinYou 数据集上训练迭代的 AUC 性能。可以看到：

   • 我们发现神经网络模型比 LR 和 FM 收敛得更快。
   • 我们还发现，我们提出的两个 PNN 比其它网络模型具有更好的收敛性。

   

3.2.2 消融研究

1. 这里我们讨论神经网络架构的影响。对于 IPNN 和 OPNN，我们考虑三个超参数：embedding 维度、网络深度、激活函数。

   由于 CCPM 和其它神经网络几乎没有相似之处，而 PNN* 只是 IPNN 和 OPNN 的组合，因此我们在这里仅比较 FNN、IPNN、OPNN。

2. embedding layer：我们采用了 FNN 论文中的 embedding layer 的思想。我们比较了不同的 embedding 维度，例如 [2, 10, 50, 100]。但是当维度增加时，模型训练更加困难，并且模型更容易过拟合。在我们的实验中，我们使用 embedding 维度等于 10 。

3. 网络深度：我们还通过调整 FNN 和 PNN 中隐层的数量来探索网络深度的影响。我们比较了不同数量的隐层，例如 [1,3,5,7]。下图给出了随着网络深度增长的性能。可以看到：一般而言，具有 3 层隐层的网络在测试集上表现更好的泛化能力。

   为方便起见，我们将卷积层或者 product layer 都称作 representation layer。这些层可以用较少的参数捕获复杂的特征模式，因此训练效率高，并且在测试集上可以更好地泛化。

   

4. 激活函数：我们比较三种主要的激活函数，sigmoid、tanh、relu。与 sigmoid 族激活函数相比，relu 函数具有稀疏性和梯度计算效率高的优点，有可能在 multi-field 离散数据上获得更多的好处。

   下图比较了 FNN、IPNN、OPNN 上的这些激活函数。可以看到：

   • tanh 激活函数 比 sigmoid 激活函数具有更好的性能。

   • 除了 tanh，我们发现 relu 函数也有很好的表现。可能的原因包括：

     • 稀疏激活，即负输出的节点不会被激活。
     • 高效的梯度传播，没有梯度消失问题或爆炸问题。
     • 计算效率高，只有比较、加法、乘法运算。