一、FNN [2016]

《Deep Learning over Multi-field Categorical Data – A Case Study on User Response Prediction》

1. 用户响应（user response）（如点击click-through 或转化 conversion ）预测在很多 web applications 中起着至关重要的作用，包括web 搜索、推荐系统、sponsored 搜索广告、展示广告（display advertising ）。例如，和传统线下广告相比，在线广告精准定向（targeting）到单个用户的能力是核心优势。所有这些 targeting 技术本质上都依赖于系统预测特定用户是否会认为潜在广告是 “相关” 的，即用户在特定上下文中点击给定广告的概率。sponsored 搜索广告、上下文广告、以及最近出现的实时竞价（realtime bidding: RTB）展示广告在很大程度上依赖于模型预测广告点击率 CTR 的能力。

   当今应用的 CTR 预估模型大多数是线性的，从逻辑回归、朴素贝叶斯到 FTRL 逻辑回归、贝叶斯概率回归，所有这些都是基于大量的、基于 one-hot 编码的稀疏特征。线性模型具有易于实现、学习效率高的优点，但性能相对较低，因为无法它无法学习非平凡的（nontrivial）模式来捕获原始特征之间的交互（interaction）。

   另一方面，非线性模型能够利用不同的特征组合，因此有可能提高预估性能。例如：分解机（factorization machine: FM）将用户和 item 的二元特征映射到低维连续空间中，并通过向量内积自动探索特征交互；梯度提升树（gradient boosting tree: GBT）在生成每棵决策树/回归树的同时自动学习特征组合。然而，这些模型不能利用不同特征的所有可能组合，并且在大特征空间中计算量很大。

   此外，很多模型需要特征工程来手动设计输入特征。

   主流的广告点击率预估模型的另一个问题是：大多数预测模型结构浅、表达能力有限，无法从复杂和海量数据中建模潜在模式。因此，它们的数据建模和泛化能力仍然受限。

   近五年来，深度学习在计算机视觉、语音识别、自然语言处理等领域取得了成功。由于视觉信号、听觉信号、文本信号已知在空间/时间上相关，因此新引入的、在深层结构上的无监督训练能够探索这种局部依赖性（local dependency）并建立特征空间的稠密representation，使神经网络模型能够有效地直接从原始特征输入中学习高阶特征。凭借这样的学习能力，深度学习将是估计在线用户响应（如广告点击率）的理想选择。

   然而，CTR 预估中的大多数输入特征都是 multi-field 的，而且是不连续的（discrete） 、离散的（categorical），例如用户所在城市（London, Paris）、设备类型（PC, Mobile）、广告类目（Sports, Electronics）。另外，输入特征之间的局部依赖性是未知的。因此，了解深度学习如何通过在此类大型 multi-field 离散特征上学习特征 representation 来改进 CTR 预估是非常有意义的。距FNN 论文作者所知，到目前为止还没有使用深度学习方法估计广告点击率的文献。 此外，在大型输入特征空间上训练深度神经网络DNN 需要训练大量参数，这在计算上是昂贵的。例如，不同于图像和音频领域，在 CTR 预估任务中，假设在第一层大约有 100 万个二元输入特征和 100 个隐单元，那么构建第一层神经网络就需要 1 亿个权重参数。

   在论文 《Deep Learning over Multi-field Categorical Data – A Case Study on User Response Prediction》 中，作者以广告点击率预估作为示例，通过使用有监督和无监督方式的 embedding 方法在大型 multi-field 离散特征空间上研究深度学习。论文介绍了两种类型的深度学习模型，称为因子分解机支持的神经网络（Factorization Machine supported Neural Network: FNN）、基于采样的神经网络（Sampling-based Neural Network: SNN）。具体而言：

   • FNN 使用分解机来初始化监督学习的 embedding layer，从而将高维稀疏特征有效地降维到低维稠密连续特征。

   • SNN 是一个深度神经网络，由基于采样的受限玻尔兹曼机（sampling-based restricted Boltzmann machine: SNN-RBM）或者基于采样的降噪自编码器（sampling-based denoising auto-encoder: SNN-DAE）提供支持，并且使用了一种负采样方法。

   基于 embedding layer，论文构建了具有全连接的多层神经网络，从而探索非平凡（non-trivial）的数据模式。论文对多个真实世界广告主的广告点击数据进行的实验表明：所提出的模型对 CTR 预估的一致性（consistent）的改进优于 SOTA 的模型。

2. 相关工作：点击率在在线广告中至关重要。为了最大化收入和用户满意度（satisfaction），在线广告平台必须预测每个展示广告的预期用户行为，并最大化用户点击的期望。

   当前的大多数模型使用基于一组稀疏二元特征的逻辑回归，这些特征是通过 one-hot 编码从原始离散特征（categorical feature）转换而来的。在这个过程中需要大量的特征工程。

   将维度很高的特征向量嵌入到低维 embedding 空间，这对于预测任务很有用，因为它降低了数据和模型的复杂性，并提高了训练和预测的效果（effectiveness）和效率（efficiency）。人们已经提出了各种 embedding 方法。例如因子分解机（Factorization machine: FM）最初是为协同过滤推荐而提出的，被认为是最成功的 embedding 模型之一。FM 天然地可以通过将任意两个特征映射到低维潜在空间中的向量，从而估计它们之间的交互。

   深度学习是人工智能研究的一个分支，它试图开发新技术使得计算机能够处理复杂的任务（诸如识别recognition 和预测 prediction ）。深度神经网络 DNN 能够从训练数据中提取不同抽象级别的隐藏结构（hidden structures）和内在模式（intrinsic patterns），目前已经成功应用于计算机视觉、语音识别、自然语言处理。此外，在无监督预训练的帮助下，我们可以获得良好的特征 representation，引导学习朝着更好泛化的极小值区域发展。

   通常，这些深度模型有两个学习阶段：第一阶段通过无监督学习（即受限玻尔兹曼机RBM或堆叠降噪自编码器SDAE）执行模型初始化，使模型捕获输入数据的分布。第二阶段涉及通过反向传播的监督学习对初始化模型进行微调。

   我们的深度学习模型的新颖之处在于第一层初始化，其中输入的原始特征是从原始离散特征转换而来的高维稀疏二元特征。这种高维稀疏二元特征使得大规模训练传统 DNN 变得困难。与 NLP 中使用的 word embedding 技术相比，我们的模型处理更通用的 multi-field 离散特征，而没有任何假设的数据结构，如 word alignment 以及 letter-n-gram 等。

1.1 模型

1. 里我们将详细讨论两种 DNN 架构，即因子分解机支持的神经网络（Factorization-machine supported Neural Networks: FNN）、基于采样的神经网络（Sampling-based Neural Networks: SNN）。

   这输入的离散特征是 field-wise one-hot 的。对于每个field（例如 city），有多个unit，每个 unit 代表该field 的一个特定值（例如 city=London），并且只有一个 postive unit （取值为 1）、其它所有 unit 都是 negative（取值为 0）。编码后的特征记作 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$，这是很多 CTR 预估模型以及我们 DNN 模型的输入。

1.1.1 FNN

1. 我们的第一个模型 FNN 基于因子分解机 FM，网络结构如下图所示。网络分为以下几层：

   • 第 0 层输入层：离散特征经过 one-hot 编码之后作为输入，该层也被称作 sparse binary feature 层。

   • 第1层embedding 层：输入层经过局部连接生成embedding 向量，该层也被称作 dense real layer 层。

   • 第2层到第 $L$$L$ 层：全连接层。也被称作 hidden layer。

   • 最后一层：sigmoid 输出层。

   

2. FNN 的核心在于 embedding 向量的生成。假设 one-hot 向量为 $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^n$$\mathbf{\vec x}\in \mathbb R^n$ 包含 $F$$F$ 个 field ，field i 在向量中的起始位置为 $s_i$$s_i$、终止位置为 $e_i$$e_i$（包含），即 $\mathbf{x}[s_i:e_i]$$\mathbf x[s_i:e_i]$。其中 $n=e_F-s_1$$n=e_F-s_1$ 。

   每个 field 生成一个 embedding 向量，即 field i 生成 ${\overrightarrow{\mathbf{z}}}_i={(w_i,z_1^{(i)},z_2^{(i)},\cdots ,z_K^{(i)})}^{\mathrm{\top }}\in {\mathbb{R}}^{K+1}$$\mathbf{\vec z}_i = \left(w_i,z_1^{(i)},z_2^{(i)},\cdots,z_K^{(i)}\right)^\top \in \mathbb R^{K+1}$ 。同时还有全局bias 。因此embedding 层的输出为：

   $$\overrightarrow{\mathbf{z}}={(w_0,w_1,z_1^{(1)},z_2^{(1)},\cdots ,z_K^{(1)},\cdots ,w_F,z_1^{(F)},z_2^{(F)},\cdots ,z_K^{(F)})}^{\mathrm{\top }}$$

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

   • ${\mathbf{W}}_0\in {\mathbb{R}}^{(K+1)\times n}$$\mathbf W_0\in \mathbb R^{(K+1)\times n}$ 由 FM 模型初始化，即：

     $$y_{\text{FM}}\left(\overrightarrow{\mathbf{x}}\right)=\text{sigmoid}({\tilde{w}}_0+\sum _{i=1}^n{\tilde{w}}_i{x}_i+\sum _{i=1}^n\sum _{j=i+1}^n({\overrightarrow{\mathbf{v}}}^{(i)}\cdot {\overrightarrow{\mathbf{v}}}^{(j)})x_i{x}_j)$$

     其中 ${\overrightarrow{\mathbf{v}}}^{(i)}\cdot {\overrightarrow{\mathbf{v}}}^{(j)}$$\mathbf{\vec v}^{(i)}\cdot \mathbf{\vec v}^{(j)}$ 用于建模特征之间的交互。

     在 FM 模型中，${\tilde{w}}_i$$\tilde w_i$ 为第 $i$$i$ 个特征的 bias 参数，${\overrightarrow{\mathbf{v}}}^{(i)}\in {\mathbb{R}}^K$$\mathbf{\vec v}^{(i)}\in \mathbb R^K$ 为第 $i$$i$ 个特征的 embedding 向量。$x_i$$x_i$ 为 field $i$$i$ 的取值。${\mathbf{W}}_0$$\mathbf W_0$ 的第 $i$$i$ 列由向量 $({\tilde{w}}_i,v_1^{(i)},\cdots ,v_K^{(i)})\in {\mathbb{R}}^{K+1}$$\left(\tilde w_i, v_1^{(i)},\cdots,v_K^{(i)}\right)\in \mathbb R^{K+1}$ 初始化。

   • 模型采用逐层预训练，一旦初始化后就冻结 ${\mathbf{W}}_0$$\mathbf W_0$ ，直到最后的微调阶段才更新 ${\mathbf{W}}_0$$\mathbf W_0$ 。

3. 一旦求解出 $\overrightarrow{\mathbf{z}}$$\mathbf{\vec z}$，就可以计算后续网络：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_1=\sigma ({\mathbf{W}}_1\overrightarrow{\mathbf{z}}+{\overrightarrow{\mathbf{b}}}_1)\in {\mathbb{R}}^{d_1}\\ ⋮\\ {\overrightarrow{\mathbf{h}}}_L=\sigma ({\mathbf{W}}_l{\overrightarrow{\mathbf{h}}}_{L-1}+{\overrightarrow{\mathbf{b}}}_L)\in {\mathbb{R}}^{d_L}=\mathbb{R}\\ \hat{y}=\text{sigmoid}({\overrightarrow{\mathbf{h}}}_L)\end{array}$$

   其中 $\sigma (\cdot )$$\sigma(\cdot)$ 为激活函数， $d_l$$d_l$ 为第 $l$$l$ 层输出的维度。

   网络每层通过 layer-wise RBM 逐层预训练来初始化。

4. 通过这种方式，上述神经网络可以更有效地从分解机 representation 中学习，从而很自然地绕过了高维二元输入的计算复杂性问题。不同隐层可以看作是不同的内部函数，捕获了数据样本的不同representation 形式。因此，该模型具有更强的捕获内在数据模式的能力。

5. 在底层使用 FM 的想法是由卷积神经网络CNN 启发的，CNN 通过在相邻层的神经元之间强制执行局部连接模式来利用空间局部相关性。同样地，第一层隐层的输入连接到特定 field 的输入单元。此外，底层不是全连接的，因为 FM 对 one-hot 稀疏编码输入执行 field-wise 训练，从而允许局部稀疏（local sparsity），如上图中的虚线所示。

6. FM 在潜在空间中学习良好的结构数据representation，有助于构建任何更好的模型。但是，FM 的乘积规则和 DNN 的求和规则之间出现了细微的差异。然而，如果观察到的判别性的信息（discriminatory information）是高度模糊的（在我们的广告点击场景下是这样的），后验权重（来自 DNN）不会显著偏离先验权重（来自 FM）。

   此外，隐层（FM 层除外）中的权重通过使用对比散度contrastive divergence 的 layer-wise RBM 预训练进行初始化，这有效地保留了输入数据集中的信息。

7. FM 的初始权重通过随机梯度下降 SGD 进行训练。注意，我们只需要更新连接到 positive input 单元的权重，这在很大程度上降低了计算复杂度。

   在对 FM 和上层进行预训练后，我们应用监督微调（反向传播）以最小化交叉熵的损失函数：

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

   其中 $\hat{y}$$\hat y$ 为预估的点击率，$y$$y$ 为 ground-truth label。

   通过反向传播的链式法则，可以有效地更新包括 FM 权重在内的 FNN 权重。

   $$\begin{array}{c}\frac{\partial \mathcal{L}}{\partial {\mathbf{W}}_0^{(i)}}=\sum _{k=1}^{K+1}\frac{\partial \mathcal{L}}{\partial z_{i,k}}\frac{\partial z_{i,k}}{\partial {\mathbf{W}}_0^{(i)}}=\frac{\partial \mathcal{L}}{\partial {\overrightarrow{\mathbf{z}}}_i}\mathbf{x}[s_i:e_i]\\ {\mathbf{W}}_0^{(i)}\leftarrow {\mathbf{W}}_0^{(i)}-\eta \frac{\partial \mathcal{L}}{\partial {\overrightarrow{\mathbf{z}}}_i}\mathbf{x}[s_i:e_i]\end{array}$$

   当 $x_j=0$$x_j = 0$ 时对应梯度为 0，因此只需要更新 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 中非零的分量对应的参数，这大大降低了参数更新的计算量。

1.1.2 SNN

1. SNN 的模型如下图 (a) 所示。SNN 和 FNN 的区别在于第一层的结构和训练方法。SNN 的第一层是全连接的：

   $$\overrightarrow{\mathbf{z}}=\sigma ({\mathbf{W}}_0\overrightarrow{\mathbf{x}}+{\overrightarrow{\mathbf{b}}}_0)$$

   其中 $\sigma (\cdot )$$\sigma(\cdot)$ 为激活函数，${\mathbf{W}}_0,{\overrightarrow{\mathbf{b}}}_0$$\mathbf W_0,\mathbf{\vec b}_0$ 为第一层的网络参数。

   为了初始化第一层的权重，我们在预训练阶段尝试了受限玻尔兹曼机（restricted Boltz- mann machine: RBM）和降噪自编码器（denoising auto-encoder: DAE）。

   为了处理训练大型稀疏 one-hot 编码数据的计算问题，我们提出了一种基于采样的 RBM（如下图 (b)，记作 SNN-RBM），以及基于采样的 DAE（如下图 (c)，记作 SNN-DAE），从而有效地计算第一层的初始权重。

   我们不是为每个训练样本集合建模整个 feature set。对于每个特征 field，每个训练样本只有一个 positive value feature ，例如 city= London，并且我们随机采样 $m$$m$ 个 negative units （取值为零）。图 (b) 和 (c) 中的黑色单元是未采样到的，因此在预训练数据样本时被忽略。使用采样的单元，我们可以通过对比散度（ contrastive divergence ）训练 RBM，并通过 SGD 使用无监督方法训练 DAE，从而大大降低数据维度，并具有高的 recovery 性能。

   此外，实值稠密向量用作 SNN 中其它层的输入。

   通过这种方式，我们可以显著降低计算复杂度，进而可以快速计算初始权重，然后执行反向传播来微调 SNN 模型。

    

   

1.1.3 正则化

1. 为了防止过拟合，我们在损失函数中加入了广泛使用的 L2 正则化，例如 FNN 中的正则化项为：

   $$\mathrm{\Omega }(\mathrm{\Theta })={\Vert {\mathbf{W}}_0\Vert }_2^2+\sum _{l=1}^L({\Vert {\mathbf{W}}_l\Vert }_2^2+{\Vert {\overrightarrow{\mathbf{b}}}_l\Vert }_2^2)$$

   另一方面，我们还实现了 dropout ，并在实验中对这两种正则化方式进行了比较。

1.2 实验

1. 数据集：我们基于 iPinYou 数据集评估我们的模型，这是一个公开的真实世界展示广告（display ad）数据集，包含每个广告曝光信息和相应的用户点击反馈。数据日志由不同的广告主以每条记录的格式进行组织。

   数据集包含 1950 万个数据样本，共有 14790 个 positive label （正样本）。所有的特征都是离散的，特征包括 user agent、partially masked IP、地区、城市、广告交易平台、域名（domain）、URL、广告位ID 等等。经过 one-hot 编码后，整个数据集中的二元特征数量为 937.67K 。

   在我们的实验中，我们分别使用来自广告主 1458、2259、2261、2997、3386 以及整个数据集的训练数据。

2. baseline 方法：

   • LR：逻辑回归是一种实现简单、训练速度快的线性模型，广泛用于在线广告点击率预估。

   • FM：因子分解机是一种非线性模型，即使在具有巨大稀疏性的问题中也能估计特征交互。

   • FNN：我们提出的分解机支持的神经网络，如前所述。

   • SNN：我们提出的基于采样的神经网络，其中基于采样的 RBM 表示为 SNN-RBM、基于采样的 DAE 表示为 SNN-DAE 。

   为了衡量每个模型的 CTR 预估性能，我们使用 AUC 指标。

3. 下表给出了5 个不同广告主和整个数据集上不同模型的比较结果。可以看到：

   • FM 并没有显著优于 LR，这意味着二阶组合特征不足以捕获底层数据模式。

   • 在所有测试集上，FNN 和 SNN 的性能超越了 LR 和 FM。

     • 基于FM 学习的潜在结构，FNN 进一步学习这些潜在特征之间的有效模式，并提供对 FM 的一致提升。

     • SNN-DAE 和 SNN-RBM 的性能大体上是一致的，即SNN 的结果几乎相同。

   

4. 超参数调优：深度神经网络需要调优相当多的超参数，这里展示我们如何实现我们的模型以及调优超参数。

   • 我们使用随机梯度下降来训练模型，训练 epoch 的数量由早停策略来自动决定。

   • 我们尝试了不同的学习率（[1, 0.1, 0.01, 0.001, 0.0001]），并选择在验证集上最佳性能的学习率。

   • 对于 SNN-RBM 和 SNN-DAE 的负采样unit，我们尝试每个field 的 negative units数 $m=1,2,4$$m=1,2,4$ 。我们发现 $m=2$$m=2$ 在大多数情况下产生最佳结果。

   • 对于隐层的激活函数，我们尝试了线性函数、sigmoid 函数、tanh 函数，最终发现 tanh 函数的结果最优。

5. 架构选择：在我们的模型中，我们通过固定所有层的尺寸来研究具有 [3, 4, 5] 层隐层的架构，并发现具有三层隐层（即，包括输入层、输出层一共有五层）的架构在 AUC 性能方面最佳。

   但是如何选择层的尺寸是一个困难。假设具有 $L$$L$ 层隐层，每一层的隐单元数量取值集合为 [100, 200, 300, 400, 500]，那么一共有 $5^L$$5^L$ 种选择。在我们的实验中，我们并没有尝试所有的组合，而是采用另一种策略：所有隐层使用相同数量的隐单元，因为根据经验具有相同尺寸的隐层的架构优于尺寸增加或减小的架构。

   事实上除了尺寸增加、尺寸不变、尺寸减小之外，还有一种更有效的结果，即菱形结构，如下图 (a) 所示。我们将这几种网络结构在不同数据集上进行比较。可以看到：

   • 菱形架构在几乎所有层尺寸设置中都优于其它架构。这种菱形之所以有效，可能是因为这种特殊形状的神经网络对模型容量有一定的约束，这在测试集上提供了更好的泛化能力。

   • 另一方面，菱形架构的最佳隐单元总数为 600，即 (200,300,100) 的组合。这取决于训练样本的数量。针对小规模数据集，如果有太多隐单元可能会导致过拟合。

   

6. 正则化：我们比较了 L2 正则化和 dropout 。下图显示了 SNN-RBM 模型采用不同正则化的性能比较。可以看到：在所有情况下 dropout 都优于 L2 。

   dropout 更有效的原因是：在馈入每个训练样本时，每个隐单元都以 dropout rate 的概率从网络随机排除，即每个训练样本都可以视为一个新的模型，并将这些模型平均为 bagging 的特殊case，这有效地提高了 DNN 模型的泛化能力。

   

7. dropout rate：下图显示了 FNN 和 SNN 中， AUC 性能如何随着的 dropout rate 的增加而变化。这里的 dropout rate 指的是每个神经单元处于激活状态的概率（而不是丢弃的概率）。可以看到：

   • 两个模型的性能在开始时都有上升的趋势，然后随着 dropout rate 的不断降低而急剧下降。

   • 这两种模型的区别在于对 dropout 的敏感性不同。

     • 模型 SNN 对 dropout rate 很敏感，这可能是由于 SNN 第一层的全连接而引起的。

     • 模型 FNN 对 dropout rate 相对不敏感，这是因为 FNN 第一层部分连接而引起的。当一些隐单元被丢弃时，FNN 更鲁棒。

     因此，FNN 和 SNN 最佳性能时的 dropout rate 有很大不同。对于 FNN，最佳 dropout rate 大约为 0.8，对于 SNN 大约为 0.99 。