一、DREAM [2016]

《A Dynamic Recurrent Model for Next Basket Recommendation》

1. 通常而言，next basket recommendation 有两种不同的方法：

   • 协同过滤（collaborative filtering: CF）模型：它捕获用户的通用兴趣（general interest），但是难以考虑历史交易的序列特征。矩阵分解（matrix factorization: MF）模型是一个成功的 CF 模型，它对整个历史交易数据构建的 user-item 矩阵进行因子分解，并用潜在向量来表达用户的通用兴趣。

   • 基于马尔科夫链的序列推荐模型：它从历史交易中提取序列特征，然后根据这些序列行为预测 next purchase 。

   因此，next basket recommendation 的一种更合适的方法是在混合模型（hybrid model）中同时捕获上述序列行为和用户通用兴趣。

   • 因子分解个性化马尔科夫链（Factorizing Personalized Markov Chain: FPMC ）可以对每两个相邻 basket 之间的序列行为进行建模，并且用户的通用兴趣由 basket 中的 item 来塑造（shaped）。但是，FPMC 只是对多个因子进行线性运算，并不能描述多个因子之间的交互。

   • Hierarchical Representation Model: HRM 似乎部分地解决了如何通过非线性最大池化操作来聚合多个交互因子的问题。然而，所有基于马尔科夫链的方法（包括上述 FPMC 和 HRM）都具有相同的缺陷，即这些推荐器只能对每两个相邻 basket 之间的局部序列行为进行建模，而这这两个相邻 basket 有时可能不相关。例如，用户 $u$$u$ 可能在 $t_1$$t_1$ 时刻购买了一个 ultrabook、在 $t_2$$t_2$ 时刻购买了一些食物、在 $t_3$$t_3$ 时刻购买了ultrabook 的配件，此时每两个相邻 basket 之间不存在任何相关性。因此，我们需要对全局序列行为进行建模，从而充分利用 sequential basket 之间的所有相关性，如 $t_1$$t_1$ 时刻和 $t_3$$t_3$ 时刻的 basket 。出于这个原因，论文 《A Dynamic Recurrent Model for Next Basket Recommendation》计划在用户的所有 sequential basket 中对全局序列特征进行建模。

   如前所述，HRM 提取的局部序列特征不足以对不同 basket 之间的关系进行建模，而深度 RNN 架构的循环操作可以从用户的所有 basket 中捕获全局序列特征。因此，论文 《A Dynamic Recurrent Model for Next Basket Recommendation》提出了一个动态循环模型 DREAM 用于 next basket recommendation 。DREAM 模型的输入由一系列 basket 的 item 组成，这些 item 构成了特定用户的、顺序的交易。随着时间的推移，池化操作和矩阵运算为每个用户提供 dynamic representation。此外，循环结构可以从整体历史交易数据中获得每个用户的一些全局序列特征。论文在两个真实世界数据集上的实验结果表明，和 FPMC、HRM 等 SOTA 模型相比，DREAM 模型在 next basket recommendation 方面取得了很大的进步。

   这项工作的主要贡献：

   • 论文调研了每个用户的 dynamic representation，以及 item 购买历史的全局序列行为。

   • 论文在两个真实世界数据集上进行实验从而验证了 DREAM 模型的有效性。

   据作者所知，DREAM 是首个尝试结合 dynamic representation 和全局序列行为从而提高 next basket recommendation 性能的方法。

1.1 模型

1. 令 $\mathbf{N}\in {\mathbb{R}}^{|\mathcal{I}|\times d}$$\mathbf N\in \mathbb R^{|\mathcal I|\times d}$ 为 item 的 representation 矩阵，其第 $i$$i$ 行 ${\overrightarrow{\mathbf{n}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec n}_i \in \mathbb R^{d}$ 为 item $i\in \mathcal{I}$$i\in \mathcal I$ 的 representation 向量，$d$$d$ 为 representation 维度。所有 item 的集合为 $\mathcal{I}$$\mathcal I$ ，集合大小为 $|\mathcal{I}|$$|\mathcal I|$ 。

   对于用户 $u$$u$ ，历史交易 ${\mathbb{B}}^u$$\mathbb B^u$ 为 basket 集合 $\{{\mathcal{B}}_{t_1}^u,{\mathcal{B}}_{t_2}^u,\cdots \}$$\left\{\mathcal B_{t_1}^u,\mathcal B_{t_2}^u,\cdots\right\}$ ，其中该集合按照时间顺序排列，${\mathcal{B}}_{t_i}^u\subseteq \mathcal{I}$$\mathcal B_{ t_i}^u\sube \mathcal I$ 为用户 $u$$u$ 在时刻 $t_i$$t_i$ 购买的 basket of items 。

   对于具有历史交易数据的 next basket recommendation，我们将问题公式化为：预测每个用户在给定时刻 $t_i$$t_i$ 的 item 的 ranking list 。

2. DREAM 的整体框架如下图所示。

   • 模型的输入是 basket 的序列。对于用户 $u$$u$ 的一个 basket ${\mathcal{B}}_{t_i}^u$$\mathcal B_{t_i}^u$ ，我们得到 basket 内 item 的潜在 representation ${\mathbf{B}}_{t_i}^u=\{{\overrightarrow{\mathbf{n}}}_{t_i,j}^u\in {\mathbb{R}}^d\mid j=1,2,\cdots ,|{\mathcal{B}}_{t_i}^u|\}$$\mathbf B_{t_i}^u = \left\{\mathbf{\vec n}_{t_i,j}^u\in \mathbb R^d\mid j=1,2,\cdots,|\mathcal B_{t_i}^u|\right\}$ ，其中 ${\overrightarrow{\mathbf{n}}}_{t_i,j}^u$$\mathbf{\vec n}_{t_i,j}^u$ 为 basket ${\mathcal{B}}_{t_i}^u$$\mathcal B_{t_i}^u$ 中第 $j$$j$ 个 item 的潜在 representation ，$|{\mathcal{B}}_{t_i}^u|$$|\mathcal B_{t_i}^u|$ 为 basket ${\mathcal{B}}_{t_i}^u$$\mathcal B_{t_i}^u$ 中的 item 数量。现在，我们可以通过聚合这些 item representation 来生成basket ${\mathcal{B}}_{t_i}^u$$\mathcal B_{t_i}^u$ 的 basket representation ${\overrightarrow{\mathbf{b}}}_{t_i}^u$$\mathbf{\vec b}_{t_i}^u$ 。在这项工作中，我们采用了两种聚合操作：最大池化、均值池化：

     $$\begin{array}{c}{\overrightarrow{\mathbf{b}}}_{t_i}^u=\text{max-pooling}\left(\{{\overrightarrow{\mathbf{n}}}_{t_i,j}^u\in {\mathbb{R}}^d\mid j=1,2,\cdots ,|{\mathcal{B}}_{t_i}^u|\}\right)\\ {\overrightarrow{\mathbf{b}}}_{t_i}^u=\text{avg-pooling}\left(\{{\overrightarrow{\mathbf{n}}}_{t_i,j}^u\in {\mathbb{R}}^d\mid j=1,2,\cdots ,|{\mathcal{B}}_{t_i}^u|\}\right)\end{array}$$

     basket representation ${\overrightarrow{\mathbf{b}}}_{t_i}^u$$\mathbf{\vec b}_{t_i}^u$ 可以作为 RNN 的输入层。

   • 隐层的 vector representation ${\overrightarrow{\mathbf{h}}}_{t_i}^u$$\mathbf{\vec h}_{t_i}^u$ 是用户 $u$$u$ 在时刻 $t_i$$t_i$ 的 dynamic representation 。RNN 矩阵 $\mathbf{R}$$\mathbf R$ 有助于在每两个相邻隐状态 ${\overrightarrow{\mathbf{h}}}_{t_i-1}^u$$\mathbf{\vec h}_{t_i-1}^u$ 和 ${\overrightarrow{\mathbf{h}}}_{t_i}^u$$\mathbf{\vec h}_{t_i}^u$ 之间传播序列信号。$\mathbf{X}$$\mathbf X$ 为 basket representation 和用户兴趣之间的转移矩阵。最后，隐层的 vector representation 可以计算为：

     $${\overrightarrow{\mathbf{h}}}_{t_i}^u=f(\mathbf{X}{\overrightarrow{\mathbf{b}}}_{t_i}^u+\mathbf{R}{\overrightarrow{\mathbf{h}}}_{t_i-1}^u)$$

     其中： ${\overrightarrow{\mathbf{b}}}_{t_i}^u$$\mathbf{\vec b}_{t_i}^u$ 为用户 $u$$u$ 在时刻 $t_i$$t_i$ 的 basket representation，${\overrightarrow{\mathbf{h}}}_{t_i-1}^u$$\mathbf{\vec h}_{t_i-1}^u$ 为用户 $u$$u$ 在前一时刻 $t_i-1$$t_i-1$ 的 dynamic representation ，$f(\cdot )$$f(\cdot)$ 为激活函数（这里我们选择 sigmoid 函数）。

   • 最后，模型在时刻 $t_i$$t_i$ 输出用户对所有 item 的得分 ${\overrightarrow{\mathbf{o}}}_{t_i}^u$$\mathbf{\vec o}_{t_i}^u$ ：

     $${\overrightarrow{\mathbf{o}}}_{t_i}^u=\mathbf{N}{\overrightarrow{\mathbf{h}}}_{t_i}^u$$

     它是每个 item representation 和user dynamic representation 的内积。$o_{t_i,v}^u$$o^u_{t_i,v}$ 表示用户 $u$$u$ 在时刻 $t_i$$t_i$ 与 item $v$$v$ 之间的交易得分，较高的得分意味着更可能购买相应的 item 。

   

3. 目标函数：我们选择 Bayesian Personalized Ranking: BPR 作为目标函数。我们的基本假设是：用户在特定时间更喜欢 basket 中的 item ，而不是负样本（即 basket 之外的 item ）。负样本可以是basket 之外的任何其它 item 。因此我们最大化以下概率：

   $$p(u,t,v\succ v^{\prime })=\sigma (o_{u,t,v}-o_{u,t,v^{\prime }})$$

   其中：$v$$v$ 为用户 $u$$u$ 在 $t$$t$ 时刻的正样本，$v^{\prime }$$v^\prime$ 为用户 $u$$u$ 在 $t$$t$ 时刻的负样本，$\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 函数。

   考虑所有的对数似然以及正则化项，则我们的目标函数为：

   $$\mathcal{J}=[\sum -\log \sigma (o_{u,t,v}-o_{u,t,v^{\prime }})]+\frac{\lambda }{2}||\mathrm{\Theta }|{|}^2$$

   其中：$\lambda$$\lambda$ 为正则化系数，$\mathrm{\Theta }=\{\mathbf{N},\mathbf{R},\mathbf{X}\}$$\Theta = \{\mathbf N, \mathbf R, \mathbf X\}$ 为待学习的参数矩阵。

   我们使用随机梯度下降来更新求解上述最优化问题。

   DREAM 仅仅建模序列信息，并未建模用户的全局兴趣。可以看到这里并没有 user embedding 矩阵。

4. 注意，DREAM 模型迭代式地学习用户的 representation。即，我们可以迭代式地根据新的交易来更新已有的用户 representation （由于 RNN 的性质），这种更新的代价相比分解完整的 user-item 矩阵而言要小得多。

1.2 实验

1. 数据集：

   • Ta-Feng 数据集：RecSys 会议发布的公开数据集，涵盖了从食品、办公用品到家具产品。

   • T-mall 数据集：淘宝发布的一个公共的在线电商数据集，以品牌（而不是商品）的方式记录了在线交易。

   我们对上述数据集进行预处理，每个用户至少购买 $k$$k$ 个 item 才会被保留。对于 Ta-Feng 数据集我们设置 $k=10$$k=10$，对于 T-Mall 数据集我们设置 $k=3$$k=3$ 。

2. baseline 方法：

   • TOP：将训练集中最流行的 item 作为每个用户的推荐。

   • MC：马尔科夫链模型（即序列推荐器），它根据用户的最后一笔交易来预测 next purchase 。预测模型为：

     $$p(i\in {\mathcal{T}}_{t_u}^u\mid {\mathcal{T}}_{t_u-1}^u)=\frac{1}{|{\mathcal{T}}_{t_u-1}^u|}\sum _{j\in T_{t_u-1}^u}p(i\in {\mathcal{T}}_{t_u}^u\mid j\in {\mathcal{T}}_{t_u-1}^u)$$

     其中转移概率 $p(i\mid j)$$p(i\mid j)$ 是从训练集中估计而来。

   • Nonnegative Matrix Factorization: NMF：是一种 SOTA 的协同过滤方法。它是基于 user-item 矩阵的非负矩阵分解，该矩阵是通过丢弃序列信息从交易数据集构造而来。

   • FPMC：next basket recommendation 的 SOTA 混合模型，预测时同时考虑了序列行为和用户的通用兴趣。

   • HRM：是一种 SOTA 的 hierarchical representation 模型，可以捕获通用的用户兴趣以及序列效应。此外，通过各种非线性操作，HRM 可以比先前的模型更准确地捕获所有这些因子。

3. 评估指标：我们为每个用户 $u$$u$ 生成 $K$$K$ 个（$K=5$$K=5$） item 的 ranking list。我们使用 F1-score 和 Normalized Discounted Cumulative Gain: NDCG 指标。

   我们使用每个用户的最后一笔交易作为测试数据集，其它所有交易作为训练数据集。item representation 是随机初始化的。

   此外我们给出不同 representation 维度 $d$$d$ 的结果。对于 Ta-Feng 数据集，$d\in \{50,100,150\}$$d\in \{50,100,150\}$；对于 T-Mall 数据集，$d\in \{10,15,20\}$$d\in \{10,15,20\}$ 。

4. 首先我们将 DREAM 模型与 baseline 方法比较，如下图所示。整体而言，next basket recommendation 的性能排名如下：DREAM, HRM, FPMC, NMF, MC, TOP 。

   • 由于 TOP 仅推荐流行 item，并且没有利用每个 basket 的特征，因此该方法效果最差。

   • 尽管 NMF 和 MC 仅利用了一种特征（或者是序列行为、或者是用户的通用兴趣），我们观察到 NMF 比 MC 效果更好，尤其是在稀疏的 T-Mall 数据集上。可能是因为 MC 无法揭露用户之间的协同信息。在 T-Mall 的稀疏的 user-item 矩阵上，协同信息相比较于稀疏的序列行为，对于生成用户的准确兴趣更重要。

   • 在这两个数据集上，HRM 模型都优于 FPMC 模型。虽然 FPMC 和 HRM 都利用了序列行为，但是 HRM 的多个因子之间的非线性运算为其带来了更好的性能。而 FPMC 对 basket 中 item 交互的线性独立假设使其不适用于复杂的商业场景。

   • DREAM 在两个数据集上的所有指标方面都优于所有 baseline 。这表明，具有循环架构的 user dynamic representation 在捕获用户的序列特征和动态兴趣方面是有效的。此外，池化操作、激活函数等丰富的非线性操作有助于更好地表达 basket 。

   

5. 然后我们比较最大池化和均值池化对 DREAM 模型的性能影响。可以看到，最大池化的效果要优于均值池化。

   显然，均值池化是一种线性操作，这表明 basket 中的每个 item 都以独立的方式影响 basket representation 。然而在现实世界的场景中，我们购买的许多 item 都是交互的，即，一个 item 会影响我们是否购买另一个 item，而购买 item 的整体可以 shape 我们的兴趣。 因此，更好的解决方案是通过非线性运算来学习 basket 内 item 的复杂交互关系。最大池化是一种非线性操作，能够比线性操作更好地学习复杂的交互。