2020_AutoEmb

一、AutoEmb [2020]

《AutoEmb: Automated Embedding Dimensionality Search in Streaming Recommendations》

deep learning based recommender systems: DLRSs 的架构通常主要由三个关键部分组成：
- embedding layer：将高维空间中的原始的 user/item 特征映射到低维 embedding 空间中的稠密向量。
- hidden layer：进行非线性变换以转换输入特征。
- output layer：根据 hidden layer 的 representation 对特定的推荐任务进行预测。
大多数现有的研究都聚焦在为 hidden layer 和 output layer 设计复杂的神经网络架构，而 embedding layer 并没有获得太多的关注。然而，在拥有海量 user 和 item 的大规模真实世界推荐系统中， embedding layer 在准确推荐中发挥着巨大的关键作用。embedding 最典型的用途是将一个 ID （即 user ID 或 item ID）转换成一个实值向量。每个 embedding 都可以被认为是一个 latent representation 。与手工制作的特征相比，经过良好学习的 embedding 已经被证明可以显著提高推荐性能。这是因为 embedding 可以降低 categorical 变量的维度（如 one-hot id ），并有意义地在潜空间中代表 user/item 。
大多数现有的 DLRSs 在其 embedding layer 中往往采用统一的固定维度。换句话说，所有的 user（或 item）共享相同的、固定的 embedding size 。这自然引起了一个问题：我们是否需要为不同的 user/item 采用不同的 embedding size ？
为了研究这个问题，论文 《AutoEmb: Automated Embedding Dimensionality Search in Streaming Recommendations》movielens-20m $x$ $x$ 时，一个典型的、embedding 维度为 2/16/128 的 DLRS 的推荐性能在 mean-squared-error: MSE 和准确率方面的变化。更低的 MSE （或更高的准确率）意味着更好的性能。注意，作者在这项工作中把 user/item 的交互次数称为 popularitypopularity $x$ 的增加：
- 不同 embedding size 的模型的性能增加，但较大的 embedding size 获益更多。
- 较小的 embedding size 首先工作得更好，然后被较大的 embedding size 所超越。
这些观察结果是非常符合预期，因为 embedding size 通常决定了待学习的模型参数的数量、以及由 embedding 所编码信息的容量。
- 一方面，较小的 embedding size 往往意味着较少的模型参数和较低的容量。因此，当popularity小的时候，它们可以很好地工作。然而，当随着popularity的增加， embedding 需要编码更多的信息，较低的容量会而限制其性能。
- 另一方面，更大的embedding size 通常表示更多的模型参数和更高的容量。它们通常需要足够的数据从而被良好地训练。因此，当popularity小的时候，它们不能很好地工作；但随着popularity的增加，它们有可能捕获更多的信息。
鉴于 user/item 在推荐系统中具有非常不同的popularity，DLRSs 应该允许不同的 embedding size 。这一特性在实践中是非常需要的，因为现实世界的推荐系统是popularity高度动态的 streaming 。例如，新的交互会迅速发生，新的用 user/item 会不断增加。
在论文 《AutoEmb: Automated Embedding Dimensionality Search in Streaming Recommendations》 中，作者的目标是在 streaming setting 下，在 embedding layer 为不同的 user/item 实现不同的 embedding size 。这里面临着巨大的挑战：
- 首先，现实世界的推荐系统中的 user/item 的数量非常大，而且popularity是高度动态的，很难为不同的 user/item 手动选择不同的 embedding size 。
- 其次，在现有的 DLRSs 中，first hidden layer 的输入维度通常是统一的和固定的，它们很难接受来自 embedding layer 的不同维度。
作者试图解决这些挑战，从而建立了一个基于端到端的可微的 AutoML 框架（即，AutoEmb ），它可以通过自动的、动态的方式利用各种 embedding size 。论文通过现实世界的电商数据中的实验来证明了所提出的框架的有效性。
相关工作：
- deep learning based recommender system：近年来，一系列基于深度学习技术的神经推荐模型被提出，性能提升明显（如，NCF, DeepFM, DSPR, MV-DNN, AutoRec, GRU4Rec）。然而，这些工作大多集中在设计复杂的神经网络架构上，而对 embedding layer 没有给予过多关注。
- AutoML for Neural Architecture Search：《Neural input search for large scale recommendation models》 首次将NAS 用于大规模的推荐模型，并提出了一种新型的 embedding 方式，即 Multi-size Embedding: ME 。然而，它不能应用于streaming recommendation setting ，其中popularity不是预先知道的而是高度动态的。

1.1 模型

Basic DLRS 架构：我们在下图中阐述了一个 basic 的 DLRS 架构，它包含三个部分：
- embedding layeruser ID/item ID $(u_i,v_j)$ embedding $(\mathbf{\vec u}_i, \mathbf{\vec v}_j)$ 。
- hidden layerembedding $(\mathbf{\vec u}_i, \mathbf{\vec v}_j)$ 非线性地转化为 hierarchical feature representation 。
- output layer：生成 prediction 从而用于推荐。
给定一个 user-item 的交互，DLRS 首先根据 user ID 和 item ID 进行 embedding-lookup 过程，并将两个 embedding 拼接起来；然后 DLRS 将拼接后的 embedding 馈入 hidden layer 并进行预测。然而，它有固定的神经网络架构，不能处理不同的 embedding size 。接下来，我们将加强这个 basic 的 DLRS 架构，以实现各种 embedding size 。
AutoEmb 仅聚焦于 user id 和 item id 的 embedding size 优化，而没有考虑其他的 categorical feature 。并且论文描述的算法仅应用 streaming recommendation setting 。
id $N$ embedding size $N$ 倍。
换一个思路：给定一个 baseline model，我们可以将 baseline modelembedding size $N$ 个子维度（类似于 NIS），然后由控制器来选择需要横跨几个子维度。这种方法和 NIS 的区别在于：
- NIS 的控制器是独立的自由变量，每个变量代表对应的概率。虽然控制器没有包含 item 的 popularity 信息，可以自由变量的 update 次数就代表了 item 出现的频次，因此隐式地包含了 popularity 信息。
- 而这个思路里，控制器的输入包含了 item 的 popularity 信息，可以给予控制器一定的指导。
Enhanced DLRS 架构：正如前面所讨论的，当popularity较低时，具有较少模型参数的 shorter embedding 可以产生更好的推荐；而随着popularity的增加，具有更多模型参数和更高容量的 longer embedding 可以获得更好的推荐性能。在这个观察的激励下，为具有不同popularity的 user/item 分配不同的 embedding size 是非常理想的。然而，basic DLRS 架构由于其固定的神经网络架构而无法处理各种 embedding size 。
解决这一挑战的基本思路是将各种 embedding size 转换为同一维度，这样 DLRS 就可以根据当前 user/item 的popularity选择其中一个 transformed embeddingembedding $N$ embedding $\left\{\mathbf E^{1},\mathbf E^{2},\cdots,\mathbf E^{N}\right\}$ ，每个空间的 embeddingembedding size $d_1,d_2,\cdots,d_N$ $d_1\lt d_2\lt\cdots\lt d_N$ $u_i$ ，定义该用户在所有 embeddingembedding $\left\{\mathbf{\vec e}_i^1,\mathbf{\vec e}_i^2,\cdots,\mathbf{\vec e}_i^N\right\}$ embedding $\left\{\mathbf{\vec e}_i^1,\mathbf{\vec e}_i^2,\cdots,\mathbf{\vec e}_i^N\right\}$ $N$ $\left\{\mathbf{\vec e}_i^1,\mathbf{\vec e}_i^2,\cdots,\mathbf{\vec e}_i^N\right\}$ $d_N$ ：
${\tilde{\vec{e}}}_{i}^{r} \leftarrow W_{r}^{⊤} {\vec{e}}_{i}^{r} + {\vec{b}}_{r}, r = 1, 2 \dots, N$
$\mathbf W_r\in \mathbb R^{d_r\times d_N}$ $\mathbf{\vec b}_r\in \mathbb R^{d_N}$ 为 bias 向量。
embedding $\left\{\mathbf{\vec e}_i^1,\mathbf{\vec e}_i^2,\cdots,\mathbf{\vec e}_i^N\right\}$ $\left\{\tilde{\mathbf{\vec e}}_i^1,\tilde{\mathbf{\vec e}}_i^2,\cdots,\tilde{\mathbf{\vec e}}_i^N\right\}\in \mathbb R^{d_N}$ embedding $\left\{\tilde{\mathbf{\vec e}}_i^1,\tilde{\mathbf{\vec e}}_i^2,\cdots,\tilde{\mathbf{\vec e}}_i^N\right\}$ 的向量长度（magnitude）变化很大，这使得它们变得 magnitude-incomparableembedding $\left\{\tilde{\mathbf{\vec e}}_i^1,\tilde{\mathbf{\vec e}}_i^2,\cdots,\tilde{\mathbf{\vec e}}_i^N\right\}$ 进行 Batch- Norm 与 Tanh 激活：
${\hat{\vec{e}}}^{r} \leftarrow \tanh (\frac{{\tilde{\vec{e}}}_{i}^{r} - {\vec{μ}}_{B}^{r}}{\sqrt{{(σ_{B}^{r})}^{2} + ϵ}}), r = 1, 2, \dots, N$
$\vec\mu_\mathcal B^r$ mini-batch $\left(\sigma_\mathcal B^r\right)^2$ mini-batch $\epsilon$ 为一个很小的常数从而保持数值稳定性，Tanh 激活函数将 embedding 归一化到 0~1 之间。
item $v_j$ embedding $\left\{\mathbf{\vec f}_j^1,\mathbf{\vec f}_j^2,\cdots,\mathbf{\vec f}_j^N\right\}$ 进行类似的操作，得到相同维度的、magnitude-comparableembedding $\left\{\hat{\mathbf{\vec f}}_j^1,\hat{\mathbf{\vec f}}_j^2,\cdots,\hat{\mathbf{\vec f}}_j^N\right\}$ 。
根据popularity，DLRSembedding $\left(\hat{\mathbf{\vec e}}_i^*,\hat{\mathbf{\vec f}}_j^*\right)$ user $u_i$ item $v_j$ 的 representation：
$\begin{matrix} {\vec{u}}_{i} = {\hat{\vec{e}}}_{i}^{*}, {\hat{\vec{e}}}_{i}^{*} \in {{\tilde{\vec{e}}}_{i}^{1}, {\tilde{\vec{e}}}_{i}^{2}, \dots, {\tilde{\vec{e}}}_{i}^{N}} \\ {\vec{v}}_{j} = {\hat{\vec{f}}}_{j}^{*}, {\hat{\vec{f}}}_{j}^{*} \in {{\hat{\vec{f}}}_{j}^{1}, {\hat{\vec{f}}}_{j}^{2}, \dots, {\hat{\vec{f}}}_{j}^{N}} \end{matrix}$
embedding size 是由一个控制器 controller 选择的，将在后面详细介绍。然后，我们将 user representationitem representation $\mathbf{\vec h}_0 = \left[\mathbf{\vec u}_i;\mathbf{\vec v}_j\right]$ $\mathbf{\vec h}_0$ $M$ 个全连接的隐层，而隐层的输出被馈入到 output layeruser $u_i$ item $v_j$ 的交互的预测。
$N$ embedding table $N$ embedding table $N$ 倍。这对于模型训练、模型部署都是严重的挑战。因此，该方法不太适用。
Controller：我们提出了一种基于 AutoML 的方法来自动确定 embedding size 。具体而言，我们设计了两个控制器网络，分别决定 user embedding size 和 item embedding size ，如下图所示。
对于一个特定的 user/item ，控制器的输入由两部分组成：user/item 的当前popularity、上下文信息（如 previous 超参数和 loss ）。上下文信息可以被看作是衡量 previously 分配给 user/item 的超参数是否运作良好的信号。换句话说，如果 previous 超参数工作得很好，那么这次生成的新的超参数应该有些类似。
controller 的输入特征具体都是什么？论文并未说明。也不必深究，因为论文的应用价值不高。
该控制器接收上述输入，通过几层全连接网络进行转换，然后生成 hierarchical feature representationoutput layer $N$ Softmax layer $\{\alpha_1,\cdots,\alpha_N\}$ user controller $N$ $\{\beta_1,\cdots,\beta_N\}$ item controller $N$ $n$ $n$ 个 embedding 空间的概率。 controller 自动选择最大概率的空间作为 final embedding 空间，即：
$\begin{matrix} {\vec{u}}_{i} = {\hat{\vec{e}}}_{i}^{*} = {\hat{\vec{e}}}_{k}^{*}, k = max_{1 \leq l \leq N} α_{l} \\ {\vec{v}}_{j} = {\hat{\vec{f}}}_{j}^{*} = {\hat{\vec{f}}}_{k}^{*}, k = max_{1 \leq l \leq N} β_{l} \end{matrix}$
有了控制器，embedding size 搜索的任务就简化为优化控制器的参数，从而根据 user/itempopularity $\{\alpha_n\}$ $\{\beta_n\}$ 。
Soft Selection：上面的控制器对 embedding 空间进行了 hard selection，即：每次我们只从控制器中选择一个具有最大概率的embedding 空间。这种 hard selection 使得整个框架不是端到端的可微的。为此，我们选择了一种 soft selection：
$\begin{matrix} {\vec{u}}_{i} = \frac{1}{N} \sum_{n = 1}^{N} α_{n} \times {\hat{\vec{e}}}_{i} \\ {\vec{v}}_{j} = \frac{1}{N} \sum_{n = 1}^{N} β_{n} \times {\hat{\vec{f}}}_{j} \end{matrix}$
有了 soft selection ，enhanced DLRS 是端到端的可微的。新的结构如下图所示，我们增加了 transformed embedding layer，它对 embedding 空间进行soft selection，选择过程由两个控制器（分别用于 user 和 item ）来决定。
DLRS $\mathbf W$ $\mathbf \Theta$ ）。由于我们的框架是端到端的可微的，受可微分架构搜索（differentiable architecture search: DARTS ）技术概念的启发，我们为 AutoEmbDARTS $\mathcal L_\text{train}$ $\mathcal L_\text{val}$ $\mathbf W$ $\mathbf \Theta$ DLRS $\mathbf W$ $\mathbf\Theta$ 来决定。
embedding dimensionality search $\mathcal L_\text{val}(\mathbf W^∗, \mathbf \Theta^∗)$ $\mathbf \Theta^∗$ DLRS $\mathbf W^∗$ $\mathbf W^∗= \arg\min_{\mathbf W} \mathcal L_\text{train}( \mathbf W, \mathbf \Theta^∗)$ bilevel $\mathbf \Theta$ $\mathbf W$ 是内层变量：
$\begin{matrix} min_{Θ} L_{val} (W^{*}, Θ) \\ s . t . W^{*} = \arg min_{W} L_{train} (W, Θ^{*}) \end{matrix}$
$\mathbf W$ $\mathbf\Theta$ 很耗时。因此，我们利用 DARTS 的近似方案：
$\nabla_{Θ} L_{val} (W^{*}, Θ) ≃ \nabla_{Θ} L_{val} (W - ξ \nabla_{W} L_{train} (W, Θ), Θ)$
$\xi$ $\mathbf W$ $\mathbf W$ training step $\mathbf W^*$ $\mathbf W^* = \arg\min_\mathbf W \mathcal L_\text{train}(\mathbf W, \mathbf\Theta^*)$ $\xi = 0$ ）甚至会导致一定的加速，但根据经验，性能更差。
值得注意的是，与计算机视觉任务上的 DARTS 不同，我们没有推导离散架构的阶段（即，DARTS 根据 softmax 概率选择最可能的操作来生成离散的神经网络架构）。这是因为随着新的 user-item 交互的发生， user/item 的popularity是高度动态的，这使我们无法为user/item 选择一个特定的 embedding size 。
DARTS based Optimization for AutoEmb 算法：
- 输入：user-item 交互、以及 ground-truth 标签
- DLRS $\mathbf W^*$ $\mathbf\Theta^*$
- 算法步骤：
  迭代直到收敛，迭代步骤：
  - 从 previous 的 user-item 交互中随机采样一个 mini-batch 的验证数据。
  - $\mathbf\Theta$ ：
    $\nabla_{Θ} L_{val} (W - ξ \nabla_{W} L_{train} (W, Θ), Θ)$
    $\xi=0$ 用于 first-order approximation 。
  - 收集一个 mini-batch 的训练数据。
  - $\mathbf\Theta$ $\{\alpha_n\}$ $\{\beta_n\}$ 。
  - $\mathbf W$ $\{\alpha_n\}$ $\{\beta_n\}$ 来生成 DLRS 的 prediction 。
  - 评估 prediction 的效果并记录下来。
  - $\mathbf W$ $\nabla_\mathbf W\mathcal L_\text{train}(\mathbf W, \mathbf\Theta)$ 。
值得注意的是，在 batch-based streaming recommendation setting 中，优化过程遵循 "evaluate, train, evaluate, train..." 的方式。换句话说，我们总是不断地收集新的 user-item 交互数据。当我们有一个完整的 mini-batch 的样本时，我们首先根据我们的 AutoEmb 框架的当前参数进行预测，评估预测的性能并记录下来；然后我们通过最小化 prediction 和 ground truth label 之间的损失来更新 AutoEmb 的参数。接下来我们收集另一个 mini-batch 的 user-item 交互，执行同样的过程。因此，不存在预先拆分的验证集和测试集。换句话讲：
- $\mathcal L_\text{val}$ ，我们从 previous 的 user-item 交互中采样一个 mini-batch ，作为验证集。
- 没有独立的测试阶段，即没有预先拆分的测试集。
- 遵循 《Streaming recommender systems》 中的 streaming recommendation setting ，我们也有离线参数估计阶段和在线推理阶段：
  - 在离线参数估计阶段，我们使用历史上的 user-item 交互来预先训练 AutoEmb 的参数。
  - 然后我们在线启动 AutoEmb ，在在线推理阶段持续更新 AutoEmb 参数。

1.2 实验

数据集：Movielens-20m, Movielens-latest, Netflix Prize data。统计数据如下表所示。
对于每个数据集，我们使用 70% 的 user-item 交互进行离线参数估计，其他 30% 用于在线学习。为了证明我们的框架在 embedding selection 任务中的有效性，我们消除了其他的上下文特征（如，用户的年龄、item 的 category ）从而排除其他特征的影响。但为了更好地推荐，将这些上下文特征纳入框架是很简单的。
实现细节：
- 对于 DLRS：
  - embedding layer $N=3$ embedding size $[2, 16, 128]$ ，因此转换后的 embedding 维度为 128。我们将每个 user/item 的三个 embedding 拼接起来，这大大改善了 embedding 的 lookup 速度。
  - hidden layer：我们有两个隐层，大小为 256*512 和 512*512 。
  - output layer：我们做两类任务：
    - 对于 rating regression 任务，输出层为 512*1 。
    - 对于 rating classification 任务，输出层为 512*5 ，采用 Softmax 激活，因为有 5 类评级。
- 对于控制器：
  - input layer：输入特征维度为 38 。
  - hidden layer：我们有两个隐层，大小为 38*512 和 512*512 。
  - output layer：形状为 512*3Softmax $N=3$ 个单元的权重。
- batch-size = 500，DLRS 和控制器的学习率分别为 0.01 和 0.001 。AutoEmb 框架的所有超参数都通过交叉验证来调优。相应地，我们也对 baseline 进行了超参数调优，以进行公平的比较。
评估指标：
- 对于回归任务，我们首先将评分二元化为 {0, 1} ，然后通过最小化 mean-squared-error: MSE 损失来训练框架。性能可以通过 MSE 损失和准确率来评估（我们使用 0.5 作为阈值来分配标签）。
  如何二元化，作者并未说明。读者猜测是用当前评分除以最大评分（如，5 分）从而得到 0 ~ 1 之间的浮点数。
- 对于分类任务，评分 1~5 被视为 5 个类，框架通过最小化交叉熵损失（ CE loss ）进行训练。性能由交叉熵和准确率来衡量。
baseline 方法：
- Fixed-size Embedding：为所有的 user/item 分配了一个固定的 embedding size 。为了公平比较，我们将 embedding size 设定为146 = 2 + 16 + 128 。换句话说，它占用的内存与 AutoEmb 相同。
- Supervised Attention Model: SAM：它具有与 AutoEmb 完全相同的架构，同时我们通过端到端的监督学习的方式，在同一个 batch 的训练数据上同时更新 DLRS 的参数和控制器的参数。
- Differentiable architecture search: DARTS：它是标准的 DARTSembedding $N=3$ 个实值权重。
值得注意的是， Neural Input Search model 和 Mixed Dimension Embedding model 不能应用于 streaming recommendation setting ，因为它们假设 user/item 的popularity是预先知道的和固定的，然后用大的 embedding size 来分配高popularity的 user/item 。然而，在现实世界的 streaming recommender system 中，popularity不是预先知道的，而是高度动态的。
在线阶段的比较结果如下表所示。可以看到：
- SAM 的表现比 FSE 好，因为 SAM 根据popularity在不同维度的 embedding 上分配注意力权重，而 FSE 对所有 user/item 都有一个固定的 embedding 维度。这些结果表明，推荐质量确实与 user/item 的popularity有关，而引入不同的 embedding 维度并根据popularity调整 embedding 上的权重可以提高推荐性能。
- DARTS 优于 SAM ，因为像 DARTS 这样的 AutoML 模型在验证集上更新控制器的参数，可以提高泛化能力，而像 SAM 这样的端到端模型在同一个 batch 训练数据上同时更新 DLRS 和控制器的参数，可能导致过拟合。这些结果验证了 AutoML 技术比传统的监督学习在推荐中的有效性。
- 我们提出的模型 AutoEmb 比标准 DARTS 模型有更好的性能。
  DARTS 在三种 embeddinguser/item $N=3$ 个实值权重。一个特定的 user/item 的这些权重可能不会被很好地训练，因为这个 user/item 的交互有限。AutoEmb 的控制器可以纳入大量的 user/item 交互，并从中捕获到重要的特征。
  另外，控制器有一个显式的popularity输入，这可能有助于控制器学习popularity和 embedding 维度之间的依赖关系，而 DARTS 则不能。这些结果证明了开发一个控制器而不仅仅是实值权重的必要性。
- 在离线参数估计阶段之后，在线阶段的大多数 user/item 已经变得非常 popular 。换句话说，AutoEmb 对热门 user/item 有稳定的改进。
综上所述，所提出的框架在不同的数据集和不同的指标上都优于 baseline 。这些结果证明了 AutoEmb 框架的有效性。
我们将调查所提出的控制器是否能根据各种popularity产生适当的权重。因此，我们比较了没有控制器的 FSE 、有监督注意力控制器的SAM 、以及有基于 AutoML 的控制器的 AutoEmb 。Figure 6 显示了 Movielens-20m 数据集的结果，其中 x 轴是popularity，y 轴对应的是性能。由于篇幅有限，我们省略了其他数据集的类似结果。可以看到：
- 当popularity较小时，FSE 的表现比 SAM 和 AutoEmb 差。这是因为较大维度的embedding 需要足够的数据才能很好地学习。参数较少的小型 embedding 可以快速捕捉一些 high-level 的特性，这可以帮助冷启动预测。
- 随着popularity的提高，FSE 的表现超过了 SAM 。这个结果很有趣，但也很有启发性，原因可能是，SAM 的控制器过拟合少量的训练样本，这导致了次优的性能。
  相反，AutoEmb 的控制器是在验证集上训练的，这提高了它的泛化能力。这个原因也将在下面的小节中得到验证。
- AutoEmb 总是优于 FSE 和 SAM ，这意味着所提出的框架能够根据popularity自动地、动态地调整不同维度的 embedding 的权重。
- 为了进一步探究 AutoEmb 的控制器根据popularity产生的权重，我们在Figure 7 中画出了不同popularity的权重分布。我们可以观察到：在小的popularity下，分布倾向于小维度的 embedding ；而随着popularity的增加，分布倾向于大维度的 embedding 。这一观察验证了我们的上述分析。
综上所述，AutoEmb 的控制器可以通过自动的、动态的方式为不同的popularity产生合理的权重。
不同数据规模下的性能：训练基于深度学习的推荐系统通常需要大量的 user-item 交互数据。我们提出的 AutoEmb 框架在 DLRS 中引入了一个额外的控制器网络、以及一些额外的参数，这可能使它难以被很好地训练。我们在下图中展示了优化过程，其中 x 轴是训练样本的数量，y 轴对应的是性能。可以看到：
- 在早期训练阶段，SAM 的表现最差，因为它的控制器对少量的训练样本过拟合。
- 随着数据的增加，SAM 的过拟合问题逐渐得到缓解，SAM 的表现优于 FSE ，这验证了在不同 embedding 维度上加权的必要性。
- AutoML 在整个训练过程中优于 SAM 和 FSE 。尤其是在训练样本不足的早期训练阶段，它能明显提高训练效果。