基于会话的推荐

注：会话 session 通常意味着短期的用户行为序列。

一、FPMC[2010]

1. 在 next basket recommendation 任务中，我们已知用户在各个时刻购买的 basket 的 item，目标是向用户推荐该用户下一次访问时可能想要购买的 item 。

   • 基于马尔科夫链 Markov Chain: MC 模型的推荐系统通过上一个动作来预测下一个动作，从而利用这种序列数据。MC估计了一个概率转移矩阵transition matrix，它给出了已知上一个动作的情况下，发生下一个动作的条件概率。预测时，模型对每个用户的最近一次行为应用概率转移矩阵从而进行推荐。

     然而，MC模型的概率转移矩阵对所有用户都是相同的，即非个性化的。

   • 另一方面，协同过滤方法（如矩阵分解 matrix factorization: MF）学习了个性化的、用户的一般兴趣general taste ，而忽略了序列信息。

   MC和MF 各有优势：MC可以通过非个性化的概率转移矩阵来及时地捕获序列效果（即，概率转移矩阵是在所有用户的所有数据上学习的），而MF 可以通过所有数据来学习个性化的、每个用户的一般兴趣。

   在论文《Factorizing Personalized Markov Chains for Next-Basket Recommendation》 中，论文提出了一个基于个性化MC的模型，其中概率转移矩阵是 user-specific 的。具体而言，论文建模了一个概率转移立方体transition cube，这个立方体的每个切面都是 user-specific 概率转移矩阵。通过这种个性化，论文将MC和MF 的优点结合在一起：序列数据由概率转移矩阵捕获；由于所有概率转移矩阵都是 user-specific 的，因此模型捕获了个性化的用户兴趣。

   除了引入个性化MC之外，这项工作的核心贡献是估计概率转移张量 transition tensor（即概率转移立方体）。由于数据的稀疏性，不可能通过在完全参数化complete parametrization 上使用标准计数方法（即，最大似然估计的估计Maximum Likelihood Estimator: MLE）来获得个性化概率转移矩阵的良好估计。相反，论文通过一个分解模型 factorization model 来建模概率转移张量。这允许在相似的用户、相似的 item、以及相似的转移之间传播信息。通过使用基于 pairwise interaction 的MF，模型能够处理高度稀疏性。论文表明，该模型包含了个性化的MF 模型、以及非个性化的MC模型。为了学习模型参数，论文将 Bayesian Personalized Ranking: BPR 框架扩展到 next basket recommendation 。

   最后，论文将所提出的方法应用到真实的电商数据集，实验结果表明所提出的方法优于MF和MC模型。

   总而言之，论文的贡献如下：

   • 论文引入了依赖于个性化的概率转移矩阵的个性化MC，这允许我们同时捕获序列效应和长期用户兴趣。论文证明这是标准MC和MF的推广。
   • 为了处理转移概率估计的稀疏性，论文引入了一个可以应用于个性化概率转移矩阵的分解模型。这种分解方法导致参数更少，并且由于泛化能力导致它比完全参数化的模型更好的质量。
   • 论文的实验表明，所提出的模型在序列数据上优于其它 state-of-the-art 方法。

2. 相关工作：

   • 一些研究人员已经研究了马尔科夫链或推荐系统。我们没有使用启发式方法来改善最大似然估计，而是使用为优化 ranking （而不是优化 MLE）而学习的分解模型。总体而言，我们的工作与之前所有方法的主要区别在于使用个性化的概率转移矩阵，这结合了序列的好处（如时间感知、具有时不变用户兴趣的马尔科夫链）。此外，转移概率的分解和用于 ranking 的参数优化准则是新提出的。
   • 另一方面，大多数推荐系统未考虑序列模式，而是基于整个用户历史进行推荐。最近，来自隐式反馈的 item 推荐已经开始成为热点。item 推荐是相比评分预测更难的问题，因为只有正反馈而没有负反馈，因此无法直接应用标准的回归方法或分类方法。最近人们提出了一些基于矩阵分解的模型，这些模型分解了 user-item 相关性矩阵correlation matrix 。在这项工作中，我们将这些 MF 模型的优点与 MC 模型结合起来。

1.1 模型

1. 生成推荐的最常见方法是丢弃任何序列信息并学习用户的一般兴趣。另一方面，序列方法（主要依赖于马尔科夫链）的推荐仅基于最近的用户事件来学习相邻购买行为的关联。这两种方法都各有优缺点。

2. 令 $\mathcal{U}=\{u_1,u_2,\cdots ,u_M\}$$\mathcal U = \{u_1,u_2,\cdots,u_{M}\}$ 为用户集合，$\mathcal{I}=\{i_1,i_2,\cdots ,i_N\}$$\mathcal I = \{i_1,i_2,\cdots,i_{N}\}$ 为 item 集合，$M$$M$ 为用户数量，$N$$N$ 为 item 数量。

   假设用户 $u$$u$ 在时刻 $t$$t$ 购买的 busket 为 ${\mathcal{B}}_t^u\subseteq \mathcal{I}$$\mathcal B_t^u\sube \mathcal I$ ，用户 $u$$u$ 的历史 busket 集合为 ${\mathbb{B}}^u=\{{\mathcal{B}}_1^u,\cdots ,{\mathcal{B}}_{t_u-1}^u\}$$\mathbb B^u = \left\{\mathcal B_1^u,\cdots,\mathcal B_{t_u-1}^u\right\}$ 。令所有用户的所有历史 busket 为 $\mathbb{B}=\{{\mathbb{B}}^{u_1},{\mathbb{B}}^{u_2},\cdots ,{\mathbb{B}}^{u_M}\}$$\mathbb B = \left\{\mathbb B^{u_1},\mathbb B^{u_2},\cdots,\mathbb B^{u_{M}}\right\}$ 。给定 $\mathcal{B}$$\mathcal B$， next basket recommendation 任务是：在用户下次访问商店的时候向用户推荐 item 。注意，我们处理的不是绝对时间，而是关于用户的相对时间，如用户 $u$$u$ 的第一个 busket、第二个 busket 等等。

   因此该方法未考虑时间信息（绝对时间、相对时间间隔），仅考虑相对次序。

   next basket recommendation 推荐任务可以公式化为：为用户 $u$$u$ 的第 $t$$t$ 个 busket 中的所有 item 创建个性化的 ranking 函数 ${\succ }_{u,t}\subset \mathcal{I}\times \mathcal{I}$$\succ_{u,t} \sub \mathcal I\times \mathcal I$ 。通过这个 ranking 函数，我们可以向用户推荐 top n item。

3. 首先，我们为顺序的集合 sequential set 引入 MC，并将其扩展到个性化 MC。然后，我们讨论概率转移立方体transition cube 的最大似然估计的弱点。然后，为解决这个问题 ，我们引入了分解的概率转移立方体 ，其中转移之间的信息被传播。最后，我们结合了所有的思想从而得到 FPMC 模型。

1.1.1 用于集合的个性化马尔科夫链

a. 用于集合 Set 的马尔科夫链

1. 通常，阶次为 $m$$m$ 的一条马尔科夫链定义为：

   $$p(X_t=x_t\mid X_{t-1}=x_{t-1},\cdots ,X_{t-m}=x_{t-m})$$

   其中：$X_t,\cdots ,X_{t-m}$$X_t,\cdots,X_{t-m}$ 为随机变量；$x_t,\cdots ,x_{t-m}$$x_t,\cdots,x_{t-m}$ 为对应的随机变量的取值。

   在非集合的推荐应用application 中，随机变量是在 $\mathcal{I}$$\mathcal I$ 上定义的，即单个的 item $i\in \mathcal{I}$$i\in \mathcal I$ 。但是我们这里的随机变量是定义在 basket 上的，因此其状态空间大小是 $2^N$$2^{N}$ （即，对于一个 basket，它包含不同 item 的组合有 $2^{|\mathcal{I}|}$$2^{|\mathcal I|}$ 种）。显然，在整个状态空间中定义一个长的马尔科夫链是不可行的。

   为了处理这个巨大的状态空间，我们做了两个简化：

   • 我们使用长度为 $m=1$$m = 1$ 的链。

     对于 basket 场景， $m=1$$m=1$ 的非个性化马尔科夫链是：

     $$p({\mathcal{B}}_t\mid {\mathcal{B}}_{t-1})$$

     在非集合的推荐场景中，通常可以选择更长的马尔科夫链（如 $m=3$$m=3$ ），因为 $m=1$$m=1$ 的历史仅包含一个 item 。在我们的 case 中，即使长度为 $m=1$$m=1$ 的马尔科夫链也是合理的，因为一个 basket 包含很多 item。例如，在我们评估的 application 中，平均每个 basket 大约有 10 个 item 。

   • 我们简化了转移概率 transition probability 。

     长度为 $m=1$$m=1$ 的马尔科夫链由它们在状态空间上的随机转移矩阵 $\mathbf{A}$$\mathbf A$ 来描述。在我们的例子中，由于状态空间的大小为 $2^N$$2^{N}$，因此转移矩阵的维度为 $2^N\times 2^N$$2^{N}\times 2^{N}$ 。因此，我们并没有在 basket 上建模转移，而是在描述了 basket 状态的 $N$$N$ 个二元变量（每个二元变量表示对应的 item 是否包含在当前 basket 中）上建模转移：

     $$a_{j,i}=p(i\in {\mathcal{B}}_t\mid j\in {\mathcal{B}}_{t-1})$$

     $a_{j,i}$$a_{j,i}$ 的物理意义为：已知 item $j$$j$ 在前一个 basket 的情况下，下一个 basket 中出现 item $i$$i$ 的条件概率。

     这种建模方式意味着：

     • 状态空间现在是 $\mathcal{I}$$\mathcal I$，因此转移矩阵 $\mathbf{A}$$\mathbf A$ 的维度为 $N\times N$$N\times N$ 。通过因子分解，我们进一步可以将参数数量从 $N^2$$N^2$ 降低到 $2kN$$2kN$ ，其中 $k\ll N$$k\ll N$ 为潜在因子的维度。

     • 状态空间的元素是二元变量，因此 $p(i\in {\mathcal{B}}_t\mid j\in {\mathcal{B}}_{t-1})+p(i\notin {\mathcal{B}}_t\mid j\in {\mathcal{B}}_{t-1})=1.0$$p(i\in \mathcal B_t\mid j\in \mathcal B_{t-1}) + p(i\notin \mathcal B_t\mid j\in \mathcal B_{t-1}) = 1.0$ 。注意，转移矩阵 $\mathbf{A}$$\mathbf A$ 不再是随机的，因为 $\sum _{i\in \mathcal{I}}{a}_{j,i}\ne 1.0$$\sum_{i\in \mathcal I} a_{j,i} \ne 1.0$ 。

       因为下一个 basket 可能包含很多 item，使得 $\sum _{i\in \mathcal{I}}{a}_{j,i}>1.0$$\sum_{i\in \mathcal I} a_{j,i} > 1.0$ 。

2. 对于 item 推荐，我们感兴趣的是：在给定用户最近一个 basket 的情况下购买某个 item 的概率。这可以定义为从最近一个 basket 到该 item 的所有转移概率的均值：

   $$p(i\in {\mathcal{B}}_t\mid {\mathcal{B}}_{t-1})=\frac{1}{|{\mathcal{B}}_{t-1}|}\sum _{j\in {\mathcal{B}}_{t-1}}p(i\in {\mathcal{B}}_t\mid j\in {\mathcal{B}}_{t-1})$$

   这里假设最近一个 basket 中所有 item 对于 next item $i$$i$ 的作用是独立的、线性的、等权重的。也可以通过基于 attention 的 DNN 模型，从而得到交互的、非线性的、自适应权重的模型。

   basket 上完全的马尔科夫链可以表示为：

   $$p({\mathcal{B}}_t\mid {\mathcal{B}}_{t-1})\propto \prod _{i\in {\mathcal{B}}_t}p(i\mid {\mathcal{B}}_{t-1})$$

   注意，我们的目标是寻求 item ranking list，因此对完全的马尔科夫链 $p({\mathcal{B}}_t\mid {\mathcal{B}}_{t-1})$$p(\mathcal B_t\mid \mathcal B_{t-1})$ 不感兴趣，而是对单个 item 概率 $p(i\mid {\mathcal{B}}_{t-1})$$p(i\mid \mathcal B_{t-1})$ 感兴趣。

b. 转移概率的估计

1. 给定所有用户的所有历史 busket $\mathbb{B}$$\mathbb B$，转移概率 $a_{j,i}$$a_{j,i}$ 的最大似然估计为：

   $${\hat{a}}_{j,i}=\hat{p}(i\in {\mathcal{B}}_t\mid j\in {\mathcal{B}}_{t-1})=\frac{\hat{p}(i\in {\mathcal{B}}_t\wedge j\in {\mathcal{B}}_{t-1})}{\hat{p}(j\in {\mathcal{B}}_{t-1})}=\frac{|\{({\mathcal{B}}_t,{\mathcal{B}}_{t-1}{)}_{i\in {\mathcal{B}}_t\wedge j\in {\mathcal{B}}_{t-1}}\}|}{|\{({\mathcal{B}}_t,{\mathcal{B}}_{t-1}{)}_{j\in {\mathcal{B}}_{t-1}}\}|}$$

   其中：

   • 分子为所有历史 busket $\mathbb{B}$$\mathbb B$中， $j$$j$ 位于前一个basket、$i$$i$ 位于后一个 basket 的 basket pair 数量。
   • 分母为所有历史 busket $\mathbb{B}$$\mathbb B$中， $j$$j$ 位于前一个 basket 的basket pair 数量。

   这里基于统计的方法来估计 $\hat{p}(i\in {\mathcal{B}}_t\mid j\in {\mathcal{B}}_{t-1})$$\hat p(i\in \mathcal B_t\mid j\in \mathcal B_{t-1})$，并未考虑到 ${\mathcal{B}}_{t-1}$$\mathcal B_{t-1}$ 中其它 item 的存在对于概率的影响。即，认为 basket 中所有 item 对于 next item $i$$i$ 的作用是独立的。

c. 用于集合的个性化马尔科夫链

1. 上述的马尔科夫链是非个性化的，即与用户无关。现在我们将其扩展到个性化马尔科夫链 $p({\mathcal{B}}_t^u\mid {\mathcal{B}}_{t-1}^u)$$p\left(\mathcal B_t^u\mid \mathcal B_{t-1}^u\right)$ 。同样地，我们通过 item 的转移概率来表示每个马尔科夫链，但是现在是 user-specific 的：

   $$a_{u,j,i}=p(i\in {\mathcal{B}}_t^u\mid j\in {\mathcal{B}}_{t-1}^u)$$

   同样地，预测结果也是 user-specific 的：

   $$p(i\in {\mathcal{B}}_t^u\mid {\mathcal{B}}_{t-1}^u)=\frac{1}{\left|{\mathcal{B}}_{t-1}^u\right|}\sum _{j\in {\mathcal{B}}_{t-1}^u}p(i\in {\mathcal{B}}_t^u\mid j\in {\mathcal{B}}_{t-1}^u)$$

   同样地，这里假设最近一个 basket 中所有 item 对于 next item $i$$i$ 的作用是独立的、线性的、等权重的。

   $a_{u,j,i}$$a_{u,j,i}$ 的最大似然估计为：

   $${\hat{a}}_{u,j,i}=\hat{p}(i\in {\mathcal{B}}_t^u\mid j\in {\mathcal{B}}_{t-1}^u)=\frac{\hat{p}(i\in {\mathcal{B}}_t^u\wedge j\in {\mathcal{B}}_{t-1}^u)}{\hat{p}(j\in {\mathcal{B}}_{t-1}^u)}=\frac{|\{({\mathcal{B}}_t^u,{\mathcal{B}}_{t-1}^u{)}_{i\in {\mathcal{B}}_t^u\wedge j\in {\mathcal{B}}_{t-1}^u}\}|}{|\{({\mathcal{B}}_t^u,{\mathcal{B}}_{t-1}^u{)}_{j\in {\mathcal{B}}_{t-1}^u}\}|}$$

   这意味着对于每个用户 $u$$u$ 都有一个对应于该用户的转移矩阵 ${\mathbf{A}}^u\in {\mathbb{R}}^{N\times N}$$\mathbf A^u\in \mathbb R^{N\times N}$ 。因此我们得到一个维度为 $M\times N^2$$M\times N^2$ 的转移张量（即转移立方体）$\mathbf{A}$$\mathbf A$。

2. 下图展示了个性化概率转移矩阵的一个例子。许多参数无法估计（图中以 ? 标记 ），因为没有对应的观察数据。此外，估计的转移概率仅基于少量观察数据，这意味着这些估计是不可靠的。乍一看，使用个性化马尔科夫链似乎是不合理的，接下来我们将讨论导致错误估计的原因是什么，并展示如何解决它。

   

d. 最大似然估计和完全参数化的局限性

1. 非个性化马尔科夫链和个性化马尔科夫链的不可靠转移概率的问题在于：它们使用完全参数化full parametrization 的转移图transition graph（即转移矩阵、转移立方体）、以及参数估计的方式。

   • 完全参数化意味着我们分别有 $N^2$$N^2$ 和 $M\times N^2$$M\times N^2$ 个独立参数来描述概率转移。

   • 此外，最大似然估计独立地估计每个转移概率参数 $a_{j,i}$$a_{j,i}$，即：任何共现 $(j,i_1)$$(j,i_1)$ 都不会对另一个转移概率 $a_{j,i_2}$$a_{j,i_2}$ 有贡献，它仅对于 $a_{j,i_1}$$a_{j,i_1}$ 有贡献。对于个性化马尔科夫链而言甚至更糟，任何共现 $(u_1,j,i)$$(u_1,j,i)$ 都不会对另一个转移概率 $a_{u_2,j,i}$$a_{u_2,j,i}$ 有贡献。

   • 此外，最大似然估计的重要性质（如高斯分布、无偏估计、无偏估计的最小方差）仅存在于渐进理论中。当数据较少的情况下，最大似然估计会遭受欠拟合。由于我们的场景中数据非常稀疏，因此最大似然估计很容易失败。

     即模型的容量空间太大，数据量太少，导致模型欠拟合。

   为了得到更可靠的转移概率估计，我们分解了概率转移立方体。这种方式打破了参数的独立性、以及估计的独立性。这样，每个转移概率都受到相似用户、相似 item、以及相似转移的影响，这是因为信息通过该分解模型进行传播。

1.1.2 分解转移图

1. 我们对概率转移立方体 $\mathbf{A}\in {\mathbb{R}}^{M\times N\times N}$$\mathbf A\in \mathbb R^{M\times N\times N}$ 进行因子分解，这意味着我们通过低秩近似 $\hat{\mathbf{A}}$$\hat{\mathbf A}$ 对观察到的转移张量 $\mathbf{A}$$\mathbf A$ 进行建模。这种方法相比较于完全参数化的优势在于：它可以处理数据稀疏性并泛化到未观察到的数据， 因为信息通过模型传播（即模型参数）来相互影响。

2. 概率转移立方体的分解：用于估计概率转移立方体 $\mathbf{A}$$\mathbf A$ 的通用线性分解模型是 Tucker Decomposition: TD：

   $$\hat{\mathbf{A}}=\mathbf{C}{\times }_U{\mathbf{V}}^U{\times }_J{\mathbf{V}}^J{\times }_I{\mathbf{V}}^I$$

   其中：

   • $\mathbf{C}\in {\mathbb{R}}^{k_U\times k_J\times k_I}$$\mathbf C\in \mathbb R^{k_U\times k_J\times k_I}$ 为 core tensor ，$k_U,k_J,k_I$$k_U,k_J,k_I$ 为因子分解的维度。
   • ${\mathbf{V}}^U\in {\mathbb{R}}^{M\times k_U}$$\mathbf V^U\in \mathbb R^{M\times k_U}$ 为用户的特征矩阵。
   • ${\mathbf{V}}^J\in {\mathbb{R}}^{N\times k_J}$$\mathbf V^J\in \mathbb R^{N\times k_J}$ 为最近一次交易中的 item 的特征矩阵（outgoing 节点）。
   • ${\mathbf{V}}^I\in {\mathbb{R}}^{N\times k_I}$$\mathbf V^I\in \mathbb R^{N\times k_I}$ 为待预测的 item 的特征矩阵（ingoing 节点）。

   Tucker Decomposition 包含其它分解模型，如 Canonical Decomposition: CD （也称作并行因子分析 parallel factor analysis: PARAFAC）。CD 假设 core tensor 是对角矩阵，即：

   $$\begin{array}{c}{c}_{f_u,f_i,f_j}=\{\begin{array}{ll}1,& \text{if }{f}_u=f_i=f_j\\ 0,& \text{else}\end{array}\end{array}$$

   并且因子分解的维度相等，即 $k_U=k_J=k_I$$k_U = k_J = k_I$ 。

   由于观察到 $\mathbf{A}$$\mathbf A$ 是非常稀疏的，因此我们使用 CD 的一种特殊情况来建模 pairwise 交互：

   $${\hat{a}}_{u,j,i}={\overrightarrow{\mathbf{v}}}_u^{U,I}\cdot {\overrightarrow{\mathbf{v}}}_i^{I,U}+{\overrightarrow{\mathbf{v}}}_i^{I,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,I}+{\overrightarrow{\mathbf{v}}}_u^{U,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,U}$$

   这里类似于 FFM 的思想，每个 field 都有两个 embedding 从而与不同的其它 field 进行交互。

   此外，这里的 core tensor 对角线为 1，意味着不同的 field 交互的重要性都是相同的。能否自动学习不同 field 交互的重要性？

   该模型直接建模张量的所有三种模式之间的 pairwise 交互，即user 和 next item 之间、 user 和 last item 之间、以及 last item 和 next item 之间的交互。对于每种模式，我们有两个分解矩阵：

   • 对于user 和 next item 之间的交互：${\mathbf{V}}^{U,I}\in {\mathbb{R}}^{M\times k_{U,I}}$$\mathbf V^{U,I}\in \mathbb R^{M\times k_{U,I}}$ 建模用户特征，${\mathbf{V}}^{I,U}\in {\mathbb{R}}^{N\times k_{U,I}}$$\mathbf V^{I,U}\in \mathbb R^{N\times k_{U,I}}$ 建模 next item 特征。
   • 对于 user 和 last item 之间的交互：${\mathbf{V}}^{U,J}\in {\mathbb{R}}^{M\times k_{U,J}}$$\mathbf V^{U,J}\in \mathbb R^{M\times k_{U,J}}$ 建模用户特征，${\mathbf{V}}^{J,U}\in {\mathbb{R}}^{N\times k_{U,J}}$$\mathbf V^{J,U}\in \mathbb R^{N\times k_{U,J}}$ 建模 last item特征。
   • 对于 last item 和 next item 之间的交互：${\mathbf{V}}^{I,J}\in {\mathbb{R}}^{N\times k_{I,J}}$$\mathbf V^{I,J}\in \mathbb R^{N\times k_{I,J}}$ 建模 next item特征，${\mathbf{V}}^{J,I}\in {\mathbb{R}}^{N\times k_{I,J}}$$\mathbf V^{J,I}\in \mathbb R^{N\times k_{I,J}}$ 建模 last item特征。

   该模型优于 TD 的一个优点是：预测和学习复杂度远远低于 TD。此外，即使 TD 和 CD 包含了上述 pairwise 交互模型，但是它们无法识别到 pairwise 交互模型。

3. 我们提出的分解概率转移立方体的模型也可以用于非个性化的概率转移矩阵 $\mathbf{A}\in {\mathbb{R}}^{N\times N}$$\mathbf A\in \mathbb R^{N\times N}$ ，即：

   $${\hat{a}}_{j,i}={\overrightarrow{\mathbf{v}}}_i^{I,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,I}$$

4. 总结：将个性化的、集合的马尔科夫链与分解的概率转移立方体相结合，则得到分解的个性化马尔科夫链 factorized personalized Markov chain: FPMC：

   $$p(i\in {\mathcal{B}}_t^u\mid {\mathcal{B}}_{t-1}^u)=\frac{1}{\left|{\mathcal{B}}_{t-1}^u\right|}\sum _{j\in {\mathcal{B}}_{t-1}^u}p(i\in {\mathcal{B}}_t^u\mid j\in {\mathcal{B}}_{t-1}^u)$$

   其中我们通过被分解的立方体 $\hat{\mathbf{A}}$$\hat{\mathbf A}$ 来建模 $p(i\in {\mathcal{B}}_t^u\mid j\in {\mathcal{B}}_{t-1}^u)$$p\left(i\in \mathcal B_t^u\mid j\in \mathcal B_{t-1}^u\right)$ ：

   $$\begin{array}{c}\hat{p}(i\in {\mathcal{B}}_t^u\mid {\mathcal{B}}_{t-1}^u)=\frac{1}{\left|{\mathcal{B}}_{t-1}^u\right|}\sum _{j\in {\mathcal{B}}_{t-1}^u}{\hat{a}}_{u,j,i}\\ =\frac{1}{\left|{\mathcal{B}}_{t-1}^u\right|}\sum _{j\in {\mathcal{B}}_{t-1}^u}({\overrightarrow{\mathbf{v}}}_u^{U,I}\cdot {\overrightarrow{\mathbf{v}}}_i^{I,U}+{\overrightarrow{\mathbf{v}}}_i^{I,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,I}+{\overrightarrow{\mathbf{v}}}_u^{U,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,U})\end{array}$$

   因为 user 和 next item 之间的交互 ${\overrightarrow{\mathbf{v}}}_u^{U,I}\cdot {\overrightarrow{\mathbf{v}}}_i^{I,U}$$\mathbf{\vec v}_u^{U,I}\cdot \mathbf{\vec v}_i^{I,U}$ 与 $j$$j$ 无关，因此上式等价于：

   $$\hat{p}(i\in {\mathcal{B}}_t^u\mid {\mathcal{B}}_{t-1}^u)={\overrightarrow{\mathbf{v}}}_u^{U,I}\cdot {\overrightarrow{\mathbf{v}}}_i^{I,U}+\frac{1}{\left|{\mathcal{B}}_{t-1}^u\right|}\sum _{j\in {\mathcal{B}}_{t-1}^u}({\overrightarrow{\mathbf{v}}}_i^{I,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,I}+{\overrightarrow{\mathbf{v}}}_u^{U,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,U})$$

   可以看到 FPMC 的预测结果可以分为几个部分：

   • user 和 next item 之间的交互，建模next item 与用户长期偏好的关系，因为这部分与时间 $t$$t$ 无关。
   • last item 和 next item 之间的交互，建模next item 与用户短期偏好的关系。
   • user 和 last item 之间的交互，这一部分可以建模了用户长期偏好和用户短期偏好的关系。随后的章节中，论文证明这个部分可以被移除。

   所有的这些部分都可以用更复杂的模型（如 DNN）、引入更多的辅助信息（如用户画像、item 画像）来刻画。

   在接下来的章节中，我们将 FPMC 模型应用于 item 推荐任务。我们将证明，在这种情况下模型可以进一步简化，此时 user 和 last item 之间的交互可以移除。

   与完全参数化的概率转移立方体相比，分解模型的泛化性能更好、且参数更少。

   • 完全参数化的模型需要 $M\times N^2$$M\times N^2$ 个参数（个性化的概率转移立方体）或 $N^2$$N^2$ 个参数（非个性化的概率转移矩阵）。
   • 分解模型只需要 $2k_{I,J}\times N+k_{U,I}\times (M+N)$$2k_{I,J}\times N+ k_{U,I}\times (M + N)$ 个参数（个性化的概率转移立方体） 或 $2k_{I,J}\times N$$2 k_{I,J}\times N$ 个参数（非个性化的概率转移矩阵）。

   对于具有大量 item 的 application 而言，使用 $O(N^2)$$O(N^2)$ 个参数的完全参数化是不可行的。

1.1.3 Item 推荐

1. 前面已经介绍了个性化马尔科夫链的分解模型，接下来我们将该模型应用于 item 推荐任务中。这意味着模型参数应该针对 ranking 进行优化。

   • 首先，我们从sequential set数据中导出 S-BPR，它是 item 推荐的通用优化准则。该优化准则不仅可用于我们的 FPMC 模型，还可用于其他模型，如 kNN 或标准 MF 模型。

   • 其次，我们将 S-BPR 应用于 FPMC，并展示了在使用 S-BPR 进行 item 推荐的情况下如何简化模型。

   • 最后，我们提出了一种基于 bootstrap 采样的随机梯度下降学习算法，用于使用 S-BPR 优化模型参数。

     这个 bootstrap 采样的随机梯度下降学习算法就是 mini-batch 随机梯度下降学习算法。

a. S-BPR 优化准则

1. 如前所述，从 sequential basket 数据中推荐 item 的目标是推导出 item 的 ranking 函数 ${\succ }_{u,t}$$\succ_{u,t}$ 。为了建模 ranking，我们假设有一个估计量 $\hat{g}:\mathcal{U}\times \mathcal{T}\times \mathcal{I}\to \mathbb{R}$$\hat g: \mathcal U \times \mathcal T\times \mathcal I \rightarrow \mathbb R$ （如个性化马尔科夫链的购买概率）从而用于定义 ranking ：

   $$i_1{\succ }_{u,t}{i}_2\iff \hat{g}(u,t,i_1){>}_{\mathbb{R}}\hat{g}(u,t,i_2)$$

   其中 $\mathcal{T}$$\mathcal T$ 为时间的集合。

   由于 ${>}_{\mathbb{R}}$$\gt_\mathbb R$ 是实数集合 $\mathbb{R}$$\mathbb R$ 上的全序total order，所以 ${\succ }_{u,t}$$\succ_{u,t}$ 也是全序。因此 $\hat{g}(u,t,i)$$\hat g(u,t,i)$ 能够为 item 集合 $\mathcal{I}$$\mathcal I$ 生成时刻 $t$$t$ 的个性化排序。

2. 接下来我们导出类似于通用 BPR 方法 的 sequential BPR: S-BPR 优化准则。用户 $u$$u$ 在时刻 $t$$t$ 的最佳 raking ${\succ }_{u,t}\subset \mathcal{I}\times \mathcal{I}$$\succ_{u,t} \sub \mathcal I\times \mathcal I$ 可以公式化为：

   $$p(\mathrm{\Theta }|{\succ }_{u,t})\propto p({\succ }_{u,t}\mid \mathrm{\Theta })p(\mathrm{\Theta })$$

   其中 $\mathrm{\Theta }$$\Theta$ 为模型参数，在我们的场景中就是 $\mathrm{\Theta }=\{{\mathbf{V}}^{U,I},{\mathbf{V}}^{I,U},{\mathbf{V}}^{J,I},{\mathbf{V}}^{I,J},{\mathbf{V}}^{U,J},{\mathbf{V}}^{J,U}\}$$\Theta = \left\{\mathbf V^{U,I},\mathbf V^{I,U},\mathbf V^{J,I},\mathbf V^{I,J},\mathbf V^{U,J},\mathbf V^{J,U}\right\}$ 。

   假设 basket 和用户独立，这导致模型参数的最大后验 maximum a posterior: MAP估计：

   $$\arg \underset{\mathrm{\Theta }}{max}\prod _{u\in \mathcal{U}}\prod _{{\mathcal{B}}_t\in {\mathbb{B}}^u}p({\succ }_{u,t}\mid \mathrm{\Theta })p(\mathrm{\Theta })$$

   对所有 item pair $(i_1,i_2)\in \mathcal{I}\times \mathcal{I}$$(i_1,i_2)\in \mathcal I\times \mathcal I$ 展开 ${\succ }_{u,t}$$\succ_{u,t}$ ，并且假设用户basket 内的 next item 之间是相互独立的（来自于 BPR 原始论文的假设），则 $p({\succ }_{u,t}\mid \mathrm{\Theta })$$p(\succ_{u,t}\mid \Theta)$ 可以重写为：

   $$p({\succ }_{u,t}\mid \mathrm{\Theta })=\prod _{u\in \mathcal{U}}\prod _{{\mathcal{B}}_t\in {\mathbb{B}}^u}\prod _{i_1\in {\mathcal{B}}_t}\prod _{i_2\notin {\mathcal{B}}_t}p(i_1{\succ }_{u,t}{i}_2\mid \mathrm{\Theta })$$

   然后我们用模型定义 $\hat{g}(u,t,i)$$\hat g(u,t,i)$ 来表达 $p(i_1{\succ }_{u,t}{i}_2\mid \mathrm{\Theta })$$p(i_1\succ_{u,t} i_2\mid \Theta)$：

   $$p(i_1{\succ }_{u,t}{i}_2\mid \mathrm{\Theta })=p(\hat{g}(u,t,i_1){>}_{\mathbb{R}}\hat{g}(u,t,i_2)\mid \mathrm{\Theta })=p((\hat{g}(u,t,i_1)-\hat{g}(u,t,i_2)){>}_{\mathbb{R}}0\mid \mathrm{\Theta })$$

   这里我们忽略参数 $\mathrm{\Theta }$$\Theta$，因为它是 $\hat{g}(\cdot )$$\hat g(\cdot)$ 模型参数。此外，我们定义 $p(z>0)=\sigma (z)=1/(1+\exp (-z))$$p(z \gt 0) = \sigma(z) = 1/(1+\exp(-z))$ ， 其中 $\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 函数，则有：

   $$p(i_1{\succ }_{u,t}{i}_2\mid \mathrm{\Theta })=\sigma (\hat{g}(u,t,i_1)-\hat{g}(u,t,i_2))$$

   进一步地，我们假设模型参数 $\mathrm{\Theta }$$\Theta$满足高斯先验，即：$\theta \sim \mathcal{N}(0,1/{\lambda }_{\theta })$$\theta\sim \mathcal N(0,1/\lambda_{\theta})$ ，则我们得到S-BPR 的 MAP 估计：

   $$\begin{array}{c}\arg \underset{\mathrm{\Theta }}{max}\ln p({\succ }_{u,t}\mid \mathrm{\Theta })p(\mathrm{\Theta })=\arg \underset{\mathrm{\Theta }}{max}\ln \prod _{u\in \mathcal{U}}\prod _{{\mathcal{B}}_t\in {\mathbb{B}}^u}\prod _{i_1\in {\mathcal{B}}_t}\prod _{i_2\notin {\mathcal{B}}_t}\sigma (\hat{g}(u,t,i_1)-\hat{g}(u,t,i_2))p(\mathrm{\Theta })\\ =\arg \underset{\mathrm{\Theta }}{max}\sum _{u\in \mathcal{U}}\sum _{{\mathcal{B}}_t\in {\mathbb{B}}^u}\sum _{i_1\in {\mathcal{B}}_t}\sum _{i_2\notin {\mathcal{B}}_t}\ln \sigma (\hat{g}(u,t,i_1)-\hat{g}(u,t,i_2))-{\lambda }_{\mathrm{\Theta }}||\mathrm{\Theta }|{|}_F^2\end{array}$$

   其中 ${\lambda }_{\mathrm{\Theta }}$$\lambda_\Theta$ 为对应于参数 $\mathrm{\Theta }$$\Theta$ 的正则化系数。

   S-BPR 和 BPR 的核心区别在于：

   • BPR 的 (positive, negative) pair 中，negative 是用户 $u$$u$ 的所有历史item 之外选取，即全局负样本。
   • S-BPR 的 (positive, negative) pair 中，negative 是用户 $u$$u$ 的当前 basket item （即 positive 所在的 basket ）之外选取，即局部负样本。

b. 采用 FPMC 的 Item 推荐

1. 首先，我们用 FPMC 模型来表示 ${\hat{g}}^{\prime }(\cdot )$$\hat g^\prime(\cdot)$ ，并应用 S-BPR ：

   $${\hat{g}}^{\prime }(u,t,i)=\hat{p}(i\in {\mathcal{B}}_t^u\mid {\mathcal{B}}_{t-1}^u)={\overrightarrow{\mathbf{v}}}_u^{U,I}\cdot {\overrightarrow{\mathbf{v}}}_i^{I,U}+\frac{1}{\left|{\mathcal{B}}_{t-1}^u\right|}\sum _{j\in {\mathcal{B}}_{t-1}^u}({\overrightarrow{\mathbf{v}}}_i^{I,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,I}+{\overrightarrow{\mathbf{v}}}_u^{U,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,U})$$

2. 引理一（user 和 last item 之间分解的不变性）：对于使用 S-BPR 的 item 排序和优化，FPMC 模型对于user 和 last item 之间的分解是不变的，即 ${\hat{g}}^{\prime }(\cdot )$$\hat g^\prime(\cdot)$ 对 $\hat{g}(\cdot )$$\hat g(\cdot)$ 是不变的，其中：

   $$\hat{g}(u,t,i)={\overrightarrow{\mathbf{v}}}_u^{U,I}\cdot {\overrightarrow{\mathbf{v}}}_i^{I,U}+\frac{1}{\left|{\mathcal{B}}_{t-1}^u\right|}\sum _{j\in {\mathcal{B}}_{t-1}^u}{\overrightarrow{\mathbf{v}}}_i^{I,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,I}$$

   证明过程见原文。主要思路：令 ${\succ }^{\prime }$$\succ^\prime$ 是由 ${\hat{g}}^{\prime }(\cdot )$$\hat g^\prime(\cdot)$ 产生的排序函数，$\succ$$\succ$ 是由 $g(\cdot )$$g(\cdot)$ 产生的排序函数。则根据：

   $$\mathrm{\forall }u,t,i_1,i_2:{\hat{g}}^{\prime }(u,t,i_1)-{\hat{g}}^{\prime }(u,t,i_2)=\hat{g}(u,t,i_1)-\hat{g}(u,t,i_2)$$

   则可以证明：

   • 两个模型 ${\hat{g}}^{\prime }(\cdot )$$\hat g^\prime(\cdot)$ 和 $g(\cdot )$$g(\cdot)$ 产生相同的排序结果。
   • 两个采用 S-BPR 的模型最优化得到相同的参数解 $\mathrm{\Theta }$$\Theta$ ，这是因为二者的目标函数 $\arg \underset{\mathrm{\Theta }}{max}\ln p({\succ }_{u,t}\mid \mathrm{\Theta })p(\mathrm{\Theta })$$\arg\max_\Theta \ln p(\succ_{u,t}\mid \Theta) p(\Theta)$ 是等价的。

   因此对于采用 FPMC 的 item 推荐，我们使用新的 $\hat{g}(\cdot )$$\hat g(\cdot)$ 公式。

3. 然后，我们将展示简化的 FPMC 模型与标准的矩阵分解matrix factorization: MF 和分解马尔科夫链factorized Markov chain: FMC 的关联。

   • 用于 item 推荐的标准 MF 模型为：

     $${\hat{g}}^{\text{MF}}(u,t,i)={\overrightarrow{\mathbf{v}}}_u^{U,I}\cdot {\overrightarrow{\mathbf{v}}}_i^{I,U}$$

     其中 $\hat{g}(\cdot )$$\hat g(\cdot)$ 独立于序列行为，即独立于 $t$$t$ 。

   • 非个性化的分解马尔科夫链FMC 模型为：

     $${\hat{g}}^{\text{FMC}}(u,t,i)=\frac{1}{|{\mathcal{B}}_{t-1}|}\sum _{j\in {\mathcal{B}}_{t-1}}{\overrightarrow{\mathbf{v}}}^{I,J}\cdot {\overrightarrow{\mathbf{v}}}_j^{J,I}$$

   因此，FPMC 是 MF 模型和 FMC 模型的线性组合：

   $${\hat{g}}^{\text{FMPC}}(u,t,i)={\hat{g}}^{\text{MF}}(u,t,i)+{\hat{g}}^{\text{FMC}}(u,t,i)$$

   这意味着 FPMC 可以包含这两种模型：

   • 通过将 user 和 next item 之间分解的维度设为 0，即 $k_{U,I}=0$$k_{U,I} = 0$，则可以获得单纯的 FMC。
   • 通过将 last item 和 next item 之间分解的维度设为 0，即 $k_{I,J}=0$$k_{I,J} = 0$，则可以获得单纯的 MF 模型。

4. 需要注意的是： item 推荐中，即使FPMC 的模型方程可以通过 MF 和 FMC 模型的线性组合来表示，但是FPMC 不同于单个 MF 模型和单个 FMC 模型的线性组合。因为FPMC 模型的参数是联合学习的，而不是每个子模型（如 MF 模型和 FMC 模型）单独学习的。这在 FPMC 的通用情况下更为明显，其中 FPMC 的模型方程 无法由 MC 和 FMC 的线性组合来表示，如：

   • 当FPMC 优化另一个准则（如最小平方误差）而不是 S-BPR 准则时，其中user 和 last item 之间的分解不能被丢弃，因为这个准则下的不变性（即引理一）不成立。此时 FPMC 的模型方程无法由 MC 和 FMC 的线性组合来表示。
   • 当FPMC 中为张量 $\mathbf{A}$$\mathbf A$ 使用另一种分解模型（如 TD 或 CD）而不是 pairwise 交互时，此时即使采用 S-BPR 优化准则，则 FPMC 的模型方程也无法由 MC 和 FMC 的线性组合来表示。

c. 最优化

1. FPMC 包含 MF 和 FMC，而这两个模型也可以使用它们各自所提供的的算法针对 S-BPR 准则进行优化。

   尝试直接优化 S-BPR 非常耗时，因为 $(u,t,i_1,i_2)$$(u,t,i_1,i_2)$ 四元组的数量很大，即 $O(|\mathcal{S}|\times |\mathcal{I}|)$$O(|\mathcal S|\times |\mathcal I|)$ ，其中 $\mathcal{S}=\{(u,t,i)\mid u\in \mathcal{U},{\mathcal{B}}_t^u\in {\mathbb{B}}^u,i\in {\mathcal{B}}_t^u\}$$\mathcal S = \{(u,t,i)\mid u\in \mathcal U,\mathcal B_t^u\in \mathbb B^u,i\in \mathcal B_t^u\}$ 。因此，标准梯度下降和 basket-wise 随机梯度下降方法的收敛速度非常慢。相反，我们通过 bootstrapp 独立地随机抽取四元组，并对这些样本进行随机梯度下降。在每次迭代中，我们随机抽取一个四元组 $(u,t,i_1,i_2)$$(u,t,i_1,i_2)$ ，其中包括用户 $u$$u$ 在时刻 $t$$t$ 的 basket ${\mathcal{B}}_t^u$$\mathcal B_t^u$ 中的一个 item $i_1$$i_1$ 和另一个不在basket 中的 item $i_2$$i_2$ 。然后使用这个四元组对 S-BPR 执行梯度下降。算法的复杂度为 $O(n\times (k_{U,I}+k_{I,J}\times \overline{b}))$$O(n\times (k_{U,I} + k_{I,J}\times \bar b))$ ，其中 $n$$n$ 为迭代数量，$\overline{b}$$\bar b$ 为平均的 basket 大小。

   感觉这就是常规的 mini-batch 随机梯度下降。

1.2 实验

1. baseline 方法：factorized Markov chain: FMC、non-factorized Markov chain: MC dense 、matrix factorization: MF、最流行 most-popular: MP 。

   注意，这里包含很强的 baseline 方法 BPR-MF。由于 MF 和 FMC 都是 FPMC 的特例，因此对于这三种方法我们都是用 FPMC 的学习算法。

2. 数据集：我们使用在线药店的匿名购买数据集。我们使用的数据集是一个 10 core 子集，其中每个用户总共至少购买了 10 个 item ，每个 item 至少被 10 个用户购买。我们还创建了它的一个子集，其中包含 10000 个最多购买的用户、以及 1000 个最多购买的 item ，从而评估稀疏性对方法的影响。

   

   

3. 评估方式：我们将每个用户的最后一个 basket 作为测试集，并将剩余的 basket 作为训练集。我们从测试集中删除了过去购买少于 10 种不同 item 的用户。

   对于每个用户，我们从测试集中删除该用户已经购买过的所有 item ，这是因为我们希望向用户推荐其不知道的新品。这使得预测任务变得更加困难。否则，对于牙刷、清洁剂等药店中的非耐用品，仅重复推荐已购买商品将是一个简单的、但是非常成功的策略。然而，这不是推荐系统的任务，因为推荐系统应该帮助用户发现新事物。

   我们针对每个用户 $u$$u$ 的测试 basket 来测试不同模型的质量。评估指标：

   • Half-life-utility: HLU：测试 basket 中每个 next item 的归一化衰减因子之和。其中，归一化衰减因子为：

     $$\frac{2^{-\frac{r-1}{\alpha -1}}}{\sum _{r=1}^{|{\mathcal{B}}_t^u|}{2}^{-\frac{r-1}{\alpha -1}}}$$

     $r$$r$ 为 next item 在所有 $\mathcal{I}$$\mathcal I$ 中预估结果的排名。这里我们选择 $\alpha =5$$\alpha = 5$ 。

     我们报告所有测试 basket 的 HLU 均值。

   • Precision：top K 预估结果中，命中 next item 的 item 数量除以 $K$$K$ 。这里我们选择 $K=5$$K=5$ 。

   • Recall：top K 预估结果中，命中 next item 的 item 数量除以测试 basket 的大小。这里我们选择 $K=5$$K=5$ 。

     此外，我们还报告 F-measure 指标，它是 Precision 和 Recall 的调和均值。

   • AUC：Area under the ROC curve 。

4. 实验结果如下图所示。对于分解方法，我们使用 $k_{U,I}=k_{I,J}\in \{8,16,32,64,128\}$$k_{U,I} = k_{I,J}\in\{8,16,32,64,128\}$ 。

   • 正如预期的那样，所有其它方法都优于 most-popular 方法。
   • 其次，在合理的分解维度（如 32）下，所有其它分解方法都优于标准 MC 方法（即 MC dense）。
   • 总体而言，FPMC 优于所有其它方法。

   我们比较 FMC 和 MC 。结果表明：学习分解的概率转移矩阵相比通常的计数方案counting scheme 产生更好的估计。分解方法有两个优点：它的参数规模更小，并且通过使用低秩近似来防止过拟合。

   我们比较FMC 和 MF 。可以看到：在稠密场景下MF 似乎优于 FMC ，而在稀疏场景下FMC 似乎更胜一筹。原因可能是：

   • 在稠密场景中，每个用户的信息要多得多，因此使用所有全部用户购买信息的 MF 方法，要优于仅使用最后一次购买的 FMC 方法。
   • 反之，FMC 在稀疏数据集上具有优势。而结合了这两种方法优点的 FPMC 在两个数据集上都优于它们。

   

二、GRU4Rec[2015]

1. 有些电商推荐系统、新闻网站、媒体网站不会跟踪用户 ID 。虽然 cookie 和浏览器指纹技术可以提供一些程度上的用户识别，但是这些技术通常不可靠并且容易引发隐私问题。即使可以跟踪用户 ID，但是用户在一些小型电商网站上可能只有一两个会话session，并且在某些领域（如分类网站classified site）中，用户的行为通常表现出session-based的特征。因此，同一个用户的每个会话应该独立地处理。

   在中国的互联网早期，存在大量的、可以匿名访问的网站或 APP，因此不会跟踪用户 ID 。随着移动互联网浪潮的兴起，中国互联网大多数网站或 APP 需要登录才能访问，典型的例子是淘宝，因此可以跟踪到用户 ID。即使能够跟踪到用户 ID，我们也无法保证操作手机的是同一个用户。

   目前大多数电商的session-based的推荐系统都使用相对简单的方法，如 item-to-item 相似性、item 共现、转移概率等等。虽然有效，但是这些方法仅考虑用户的最后一次行为，而忽略了用户的历史行为。

   此外，推荐系统中最常用的是因子模型 factor model 和邻域方法 neighborhood method。

   • 因子模型将稀疏的 user-item 交互矩阵分解为一组 $d$$d$ 维潜在因子向量，然后根据 user 潜在因子向量和 item 潜在因子向量来完成矩阵补全问题（例如用潜在因子向量的内积）。由于无法跟踪用户 ID （导致无法获取用户历史交互的 item ），所以因子模型很难应用于session-based的推荐。
   • 邻域方法依赖于会话内的 item 共现，因此被广泛应用于 session-based 推荐中。

   RNN 在翻译、对话建模、图像标注image captioning 等领域取得了显著成功，但是很少有人将其用于推荐领域。在论文 《Session-Based Recommendations With Recurrent Neural Networks》 中，作者认为 RNN 可以应用于 session-based 推荐并取得了显著效果。作者处理了在建模这类稀疏序列数据进行时出现的问题，并通过引入适当的、新的 ranking loss function 来使得 RNN 模型适应推荐 setting 。

   session-based 推荐问题在建模方面与一些 NLP-related 问题相似，比如它们都处理序列数据。在 session-based 推荐中，我们可以将用户在会话中的第一个交互 item 作为 RNN 的初始输入，然后我们根据这个初始输入来 query 模型从而获得推荐。然后，用户的每次后续交互都会产生一个推荐，这个推荐取决于所有先前的、同一个会话内的交互。 item 集合可能是数万甚至数十万，另外交互行为可能非常频繁，因此训练时间和可扩展性非常重要。

   和大多数信息检索和推荐 setting 一样，论文主要关注于建模用户最感兴趣的 top item ，为此论文使用 ranking loss function 来训练 RNN。

2. 相关工作：

   • session-based 推荐：推荐系统领域的大部分工作都集中在当 user ID 可用并且可以获取用户画像时的模型上。这种情况下，矩阵分解模型、邻域模型在文献中占据主导地位。session-based 推荐中采用的主要方法之一是 item-to-item 推荐，此时 item-to-item 相似度矩阵是从可用的会话数据中预计算而来，也就是说，在同一个会话中共现的 item 被认为是相似的。这种方法虽然简单但是已被证明有效，并被广泛采用。但是，该方法仅考虑用户的最近一次行为，忽略了用户历史行为信息。

     session-based 推荐的另一个稍微不同的方法是马尔科夫决策过程 Markov Decision Processes: MDP。MDP 是序列随机决策问题的模型，最简单的 MDP 本质上是一阶马尔科夫链，其中 next 推荐可以简单地根据 item 之间的转移概率来计算。 在 session-based 推荐中应用马尔科夫链的主要问题是：当试图包含所有可能的用户行为序列时，状态空间很快变得无法管理。

     通用分解框架 General Factorization Framework: GFM 的扩展版本能够使用会话数据来推荐。该方法通过事件event 的 sum 来建模会话，并对 item 使用两种潜在 representation ：一种代表 item 本身、另一种代表 item 是会话的一部分。然后将会话中所有 item 的第二种 representation 取平均从而作为会话的 representation 。但是，该方法不考虑会话中的行为顺序。

   • 推荐系统中的深度学习：在推荐系统中最早应用深度学习的相关方法之一是 《Restricted boltzmann machines for collaborative filtering》，它使用 RBM 来对 user-item 交互进行建模并执行推荐。此外，深度模型也用于从音乐或图像等非结构化内容中提取特征，然后与更传统的协同过滤模型一起使用，如 《Deep content-based music recommendation》。最近，《Collaborative deep learning for recommender systems》 引入了一种更通用的方法，该方法使用深度网络从任何类型的 item 中抽取通用的内容特征，然后将这些特征集成到标准的协同过滤中从而提高推荐性能。这些方法在缺乏足够 user-item 交互的 setting 中特别有用 。

2.1 模型

2.1.1 模型

1. 标准的 RNN：

   $${\overrightarrow{\mathbf{h}}}_t=g(\mathbf{W}{\overrightarrow{\mathbf{x}}}_t+\mathbf{U}{\overrightarrow{\mathbf{h}}}_{t-1})$$

   其中：${\overrightarrow{\mathbf{x}}}_t$$\mathbf{\vec x}_t$ 为 $t$$t$ 时刻的输入，${\overrightarrow{\mathbf{h}}}_t$$\mathbf{\vec h}_t$ 为 $t$$t$ 时刻的隐状态 hidden state，$\mathbf{W}$$\mathbf W$ 和 $\mathbf{U}$$\mathbf U$ 为待学习的权重矩阵，$g(\cdot )$$g(\cdot)$ 为一个平滑有界的函数（如 sigmoid 函数）。

   Gated Recurrent Unit: GRU 是一个更精细的 RNN 模型，旨在处理梯度消失问题。GRU gates 本质上是学习何时更新单元的隐状态、以及更新多少：

   $$\begin{array}{c}{\overrightarrow{\mathbf{z}}}_t=\sigma ({\mathbf{W}}_z{\overrightarrow{\mathbf{x}}}_t+{\mathbf{U}}_z{\overrightarrow{\mathbf{h}}}_{t-1})\\ {\overrightarrow{\mathbf{r}}}_t=\sigma ({\mathbf{W}}_r{\overrightarrow{\mathbf{x}}}_t+{\mathbf{U}}_r{\overrightarrow{\mathbf{h}}}_{t-1})\\ {\widehat{\overrightarrow{\mathbf{h}}}}_t=\tanh (\mathbf{W}{\overrightarrow{\mathbf{x}}}_t+\mathbf{U}({\overrightarrow{\mathbf{r}}}_t\odot {\overrightarrow{\mathbf{h}}}_{t-1}))\\ {\overrightarrow{\mathbf{h}}}_t=(1-{\overrightarrow{\mathbf{z}}}_t)\odot {\overrightarrow{\mathbf{h}}}_{t-1}+{\overrightarrow{\mathbf{z}}}_t\odot {\widehat{\overrightarrow{\mathbf{h}}}}_t\end{array}$$

   其中：$\odot$$\odot$ 为逐元素乘积，${\overrightarrow{\mathbf{z}}}_t$$\mathbf{\vec z}_t$ 为更新门 update gate，${\overrightarrow{\mathbf{r}}}_t$$\mathbf{\vec r}_t$ 为复位门 reset gate，$\sigma (\cdot )$$\sigma(\cdot)$ 为sigmoid 激活函数， ${\widehat{\overrightarrow{\mathbf{h}}}}_t$$\hat{\mathbf{\vec h}}_t$ 为候选激活值 candidate activation 。

2. 我们在模型中使用 GRU-based RNN 来进行 session-based 推荐。网络的输入是每个时刻会话的实际状态actual state，输出是会话中下一个事件的 item 。

   • 会话的状态可以是最新的事件（即当前事件）。此时使用 OneHot 编码，即输入向量的长度为 $N$$N$ 并且仅最新事件对应的 item 为 1 而其它位置为 0 ，其中 $N$$N$ 为 item 集合大小。

   • 会话的状态也可以是截止到当前的所有事件（即累计事件）。此时对每个事件的 OneHot 编码进行加权和，权重根据事件发生时刻距离当前时间间隔进行衰减。为了稳定性，我们对输入向量进行归一化。

     我们希望这种累计事件的方式会有所帮助，因为它增强了记忆效应 memory effect。但是实验发现，这种方式并不会带来额外的准确率增益。这毫不奇怪，因为 GRU 像 LSTM 一样，同时具有长期记忆和短期记忆。

   我们尝试添加一个额外的 embedding layer，但是发现 OneHot 编码总是表现得更好。

   如果没有 embedding layer，则 ${\mathbf{W}}_z,{\mathbf{W}}_r,\mathbf{W}$$\mathbf W_z, \mathbf W_r,\mathbf W$ 分别充当不同的 embedding 矩阵； 如果添加额外的 embedding layer，则 ${\mathbf{W}}_z,{\mathbf{W}}_r,\mathbf{W}$$\mathbf W_z,\mathbf W_r,\mathbf W$ 表示在已有的 embedding 矩阵之上的投影矩阵。

   网络的核心是 GRU layer。可以使用多层 GRU layer，其中前一层的 hidden state 是下一层 的输入。最后一个 GRU layer 和输出层之间添加了额外的前馈层 Feedforward layer （但是实验发现增加这个额外的前馈层对于效果提升没有帮助）。输出是每个 item 在当前会话中成为 next 的可能性。input 层也可以选择连接到网络中更深的 GRU layer，因为我们发现这可以提高性能。

   完整的架构如下图所示，该架构描述了事件时间序列中单个事件的 representation。

   图中包含了 embedding layer 和 feedforward layer，但是根据实验描述，这两个 layer 是无益的，需要移除。

   

2.1.2 调整

1. 由于推荐系统不是 RNN 的主要应用领域，我们修改了基础网络从而更好地适应任务。我们还考虑了实际场景，以便我们的解决方案可以应用于现场环境。

2. session-parallel mini-batch：用于 NLP 任务的 RNN 通常使用 in-sequence mini-batch 。例如，通常在句子的单词上使用滑动窗口，并将这些窗口片段彼此相邻从而形成 mini-batch。这不适合于我们的任务，因为：

   • 首先，会话之间长度的差异非常大（远远大于 NLP 中的句子）。一些会话仅包含一到两个事件，而另一些会话可能包含超过数百个事件。
   • 其次，我们的目标是捕获会话如何随时间的演变，因此将会话分解为片段是没有意义的。

   因此，我们使用 session-parallel mini-batch ，如下图所示。具体而言：

   • 首先，我们将所有会话进行排序。

     注意，这里是以会话为基本单元进行排序，而不是对会话内的事件进行排序。

   • 然后，我们使用前 X 个会话的第一个事件来构成第一个 mini-batch 的输入（所需的输出是这些会话的第二个事件）。第二个mini-batch 是由这些会话的第二个事件形成的，依次类推。

     如果任何一个会话结束了，则下一个可用的会话将填补该结束会话的位置。假设会话之间是相互独立的，因此我们在发生这种会话切换的时候重置对应的 hidden state。

     这种训练方式可以支持任意长度的 session，而无需将 session 进行长度限制（比如截断为固定长度）。

   

3. sampling on the output：当 item 集合规模太大时，在每个 step 计算每个 item 在当前会话中成为 next 的可能性是不现实的。因此我们需要负采样技术。

   我们根据 item 的流行程度进行负采样： item 越流行，那么用户就越可能知道它，那么用户未对该 item 交互则意味着用户更有可能不喜欢该流行 item 。

   我们没有为每个训练样本生成单独的负采样，而是使用来自 mini-batch 的其它训练样本的 item 作为负采样。这种方法的好处是我们可以减少计算时间、降低代码复杂性、并且也易于实现。同时，该方法也是一种基于流行程度的采样，因为一个 item 出现在 mini-batch 中的可能性与其流行程度成正比。

4. ranking loss：推荐系统的核心是 item 的 relevance-based ranking 。尽管该任务也可以解释为分类任务，但是 learning-to-rank 方法通常优于其它方法。ranking 可以是 point-wise、pair-wise、或者 list-wise 的。

   • point-wise ranking 彼此独立地估计 item 的 score 或者 ranking，并且损失函数的定义方式使得相关的 item 的排名应该靠前。
   • pair-wise ranking 比较一个 positive item 和一个 negative item 组成的 ranking pair 对，损失函数强制 positive item 的排名应该比 negative item 的排名更靠前。
   • list-wise ranking 使用所有 item 的 score 或 ranking，并将它们与完美排序进行比较。它通常在计算上代价太大，因此不经常使用。

   此外，如果仅有一个相关的 item（例如我们这里的例子），list-wise ranking 可以通过 pair-wise ranking 来解决。我们在我们的解决方案中包含了几个 point-wise ranking loss 和 pair-wise ranking loss。我们发现模型的 point-wise ranking loss 不太稳定，而 pair-wise ranking loss 表现良好，最终我们使用以下两个 pair-wise ranking loss：

   • BPR：贝叶斯个性化排名Bayesian Personalized Ranking: BPR 是一种矩阵分解方法，它使用 pair-wise ranking loss。它比较一个 positive item 和一个负采样的 negative item 的 score 。这里，我们将 positive item 的 score 和几个负采样的 negative item 的 score 进行比较，并将它们的均值作为损失。具体而言，pair-wise ranking loss 为：

     $${\mathcal{L}}_s(t)=-\frac{1}{K}\times \sum _{j=1}^K\log \left(\sigma ({\hat{r}}_{t,i}-{\hat{r}}_{t,j})\right)$$

     其中：$K$$K$ 为负采样的数量，$\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 函数，${\hat{r}}_{t,j}$$\hat r_{t,j}$ 为会话 s 中 $t$$t$ 时刻在 item $j$$j$ 上的score，$i$$i$ 为 positive item，$j$$j$ 为负采样的 negative item 。

   • TOP1：这个 ranking loss 是我们为这项任务而设计的，它是 relevant item 的相对排名relative rank 的正则化近似。relevant item $i$$i$ 的相对排名定义为：

     $$\frac{1}{K}\times \sum _{j=1}^K\mathbb{I}\{{\hat{r}}_{t,j}>{\hat{r}}_{t,i}\}$$

     其中 $\mathbb{I}(\cdot )$$\mathbb I(\cdot)$ 为示性函数。我们用 sigmoid 函数来代替示性函数，优化这个相对排名将会修改 parameter 从而使得 item $i$$i$ 的 score 会很高。

     然而，这个目标函数不稳定，因为某些 positive item 也会扮演负样本角色，因此 score 往往会变得越来越高。

     为避免这种情况，我们希望强制 negative item 的 score 在零左右，这是negative item 的 score 的自然预期。为此，我们在损失函数中添加了一个正则化项。重要的是，这一项与相对排名在同一取值区间并且作用与其相似。最终的损失函数为：

     $${\mathcal{L}}_s(t)=\frac{1}{K}\times \sum _{j=1}^K[\sigma ({\hat{s}}_{t,j}-{\hat{s}}_{t,i})+\sigma \left({\hat{r}}_{t,j}^2\right)]$$

     .

2.2 实验

1. 数据集：

   • RecSys Challenge 2015 数据集（RSC15）：该数据集包含电商网站上的click-streams ，其中某些stream 以购买事件而结束。我们仅保留点击事件，并且过滤掉长度为 1 的会话。我们使用前 6 个月的数据进行训练，使用第二天的会话进行测试。每个会话要么是训练集要么是测试集，我们不会在会话中拆分数据。

     由于协同过滤方法的性质，我们从测试集中过滤掉训练期间 unseen 的 item，并且删除测试集中长度为 1 的会话。

   • VIDEO 数据集：包含某个视频服务平台收集的视频观看事件。预处理步骤如前所述，但是也过滤掉了很长的会话，因为这些会话可能是由机器人生成的。训练数据集包含最后一天除外的所有数据，测试数据集包含最后一天的数据。

2. 评估方式：通过 one-by-one 提供会话的事件并检查下一个事件的 item 排名来完成评估。GRU 的隐状态在会话结束之后重置为零。 item 按照 score 降序排名。

   对于 RSC15数据集，我们对训练集中出现的 37483 个 item 进行排名。对于 VIDEO 数据集，因为 item 集合太大因此我们将 next item 和最流行的 30000 个 item 进行排名。这种评估的影响可以忽略不计，因为冷门的 item 通常 score 很低。此外，基于流行度的预过滤在实际推荐系统中很常见。

   • recall@20：在 top 20 排名的 item 中，召回的 next item 占所有 next item 的比例。

     召回不考虑 item 的实际排名，只要它位于 top N 的位置。这很好地建模了某些实际场景，其中绝对顺序无关紧要。此外，召回率通常还与重要的在线指标密切相关，如点击率 CTR 。

   • MRR@20：Mean Reciprocal Rank: MRR 是 next item 的排名的倒数的均值。如果排名在 20 之后则排名的倒数置为零。

     MRR 考虑 item 的排名，这在推荐顺序很重要的场景下很重要（如排名靠后的 item 仅在滚动屏幕之后才可见）。

3. baseline 方法：

   • POP：流行度的 predictor，它总是推荐训练集中的流行 item 。尽管简单，但是它通常是某些领域的强大 baseline 。

   • S-POP：推荐当前会话中最流行的 item（而不是全局最流行的 item ）。该 baseline 在具有高重复性的领域中很强。

   • Item-KNN：基于 item 相似性来推荐和当前 item 最相似的 item 。相似度定义为

     $$\text{sim}(i,j)=\frac{(i,j)\text{共}\text{现}\text{的}\text{会}\text{话}\text{数}\text{量}}{\sqrt{i\text{出}\text{现}\text{的}\text{会}\text{话}\text{数}\text{量}\times j\text{出}\text{现}\text{的}\text{会}\text{话}\text{数}\text{量}}}$$

     此外，我们还使用正则化从而避免冷门 item 的偶然发生导致的高度相似性。

     该 baseline 是实际系统中最常见的 item-to-item 解决方案之一。尽管简单，它通常也是一个强大的 baseline 。

   • BPR-MF：它通过 SGD 优化 pair-wise ranking 目标函数，是最常用的矩阵分解方法之一。矩阵分解无法直接应用于 session-based 推荐，因为新会话没有预先计算的特征向量。然而，我们可以通过使用会话中出现的 item 的特征向量的均值作为 user 特征向量来克服这个问题。换句话讲，我们对 next item 的特征向量、迄今为止会话中 item 特征向量的相似性进行平均。

   这些 baseline 的效果如下表所示，其中 item-KNN 方法显著优于其它 baseline 方法。

   

4. 参数配置：我们通过单独优化每个超参数来进行超参数调优，其中调优是在单独的验证集上进行的。然后我们在训练集和验证集上对网络进行重新训练，并最终在测试集上进行评估。下表给出了最佳的超参数。

   

   此外还有一些探索如下：

   • 权重矩阵从 $[-x,x]$$[-x,x]$ 中均匀随机初始化，其中 $x$$x$ 取决于矩阵的行数和列数。

   • 我们评估了 rmsprop 和 adagrad 优化器，发现 adagrad 效果更好。

   • 我们对 GRU 以外的其它 RNN 单元进行了简单的实验，发现常规的 RNN 单元和 LSTM 单元的效果都更差。

   • 我们尝试了几种损失函数。

     • point-wise ranking loss （如交叉熵和 MRR ）优化通常是不稳定的，即使添加正则化也是如此。我们认为：这是由于这种方法试图为 positive item 获得高分，而负样本的 negative push 太小。
     • 另一方面，pair-wise ranking loss 表现良好。

   • 我们检查了几种架构，发现：

     • 单层 GRU 表现最好。我们假设这是由于会话的生命周期通常都很短，不需要表达不同分辨率的多个时间尺度。然而，确切原因尚不明确，需要进一步研究。
     • 使用 item embedding 得到的效果稍差，因此我们仅使用 OneHot 编码。
     • 此外，将会话的所有历史事件（而不是最新的事件）作为输入并不能带来额外的准确率增益。这毫不奇怪，因为 GRU 像 LSTM 一样，同时具有长期记忆和短期记忆。
     • 在 GRU layer 之后添加额外的前馈层也没有帮助。
     • 然而，增加 GRU layer 的大小提高了性能。
     • 我们还发现使用 tanh 作为输出层的激活函数是有益的。

5. 实验结果：下表给出了性能最佳的网络的结果（括号表示相对于 item-KNN 中的提升。）。具有 1000 个隐单元的 VIDEO 数据集的交叉熵在数值上不稳定，因此我们没有提供结果。结论：

   • 即使隐单元数量为 100，GRU-based 的方法在两个数据集上都显著优于 item-KNN。增加隐单元数量进一步改善 pair-wise loss 的结果，但是降低了交叉熵损失（即 point-wise loss ）的准确率。
   • 在隐单元数量为 100 时，尽管交叉熵损失给出了更好的结果，但是随着隐单元数量的增加，pair-wise loss 超过了该结果。
   • 尽管增加隐单元数量会增加训练时间，但是我们发现 GPU 上从隐单元 100 提升到 1000 的代价不太昂贵。
   • 交叉熵损失在数值上不稳定，因为网络独立地尝试增加 positive item 的 score，而其它 item 的 negative push 相对较小。因此，我们建议使用上述两个 pair-wise loss 中的任何一个。

   

三、HRM[2015]

1. 购物篮分析 market basket analysis 可以帮助零售商更好地了解用户的购买行为，从而作出更好的决策。购物篮分析最重要的任务之一是 next basket recommendation：根据每个用户的序列交易数据来推荐用户下一次访问时可能想要购买的item 。其中，交易transaction 是在某个时刻购买的一组 item（如鞋子、包包）。该问题有两种建模范式：

   • 序列推荐器 sequential recommender：主要依赖于马尔科夫链。它根据最近的动作预测 next purchase 来探索序列交易数据。该模型的一个主要优点是它能够捕获序列行为从而用于良好的推荐。例如，对于最近购买手机的用户，它可能会推荐该用户购买手机配件，其中这些手机配件是其它用户购买手机后也来购买的。
   • 通用推荐器 general recommender：丢弃任何序列信息并学习用户感兴趣的 item 。这类方法中最成功的方法之一是基于模型的协同过滤 （如矩阵分解模型）。显然，通用推荐器擅长通过学习用户的整个购买历史来捕获用户的通用兴趣general taste 。

   next basket recommendation 的更好的解决方案是同时考虑序列行为和用户的通用兴趣。个性化的马尔科夫链personalized Markov chain: FPMC 朝着这个方向迈出了一步，它能够同时建模序列行为（通过前一个交易中的 item 与后一个交易中的 item 之间的交互）、以及用户的通用兴趣（通过用户与 next basket 中的 item 之间的交互），因此比单独的序列推荐器或者单独的通用推荐器表现更好。然而，FPMC 的一个主要问题在于它的所有组件都是线性组合的，表明它在多个因子之间做出了强独立性假设（即，每个组件都是独立地影响用户的 next purchase ）。不幸的是，根据论文《Learning Hierarchical Representation Model for Next Basket Recommendation》的分析，作者表明独立性假设不足以提供良好的推荐。

   为解决上述问题，论文《Learning Hierarchical Representation Model for Next Basket Recommendation》为 next basket recommendation 引入了一种新颖的 hierarchical representation model: HRM 。具体而言，HRM 将每个用户和每个 item 表达为连续空间中的一个向量，并使用 two-layer 结构来构建用户、以及上一次交易的 item 的hybrid representation`：

   • 第一层通过聚合上一次交易的 item 向量，从而形成 transaction representation 。
   • 第二层通过聚合用户向量和 transaction representation 从而构建 hybrid representation 。

   然后，论文使用得到的 hybrid representation 来预测 next basket 中的 item 。注意，transaction representation 对序列行为进行建模，而 user representation 捕获了用户的通用兴趣。

   HRM 允许我们在不同的层灵活地使用不同类型的聚合函数。具体而言，通过采用非线性运算（而不是线性运算），我们可以建模不同因子之间更复杂的交互，而不是独立性假设。例如，通过使用最大池化操作，我们可以比较来自不同因子的特征，并且仅选择那些最重要的特征来形成更高 level 的 representation 从而用于未来的预测。

   论文还表明，通过选择适当的聚合函数，HRM 包含了几种现有的方法，包括马尔科夫链模型、矩阵分解模型、FPMC 模型的变体。为了学习模型参数，论文使用负采样程序作为优化方法。论文对三个真实世界的交易数据集进行了实验，结果证明了HRM 与 state-of-the-art baseline 方法相比的有效性。

   主要贡献：

   • 为 next basket recommendation 引入了一个通用模型，该模型可以捕获序列行为和用户的通用兴趣，并灵活地结合多个因子之间的不同交互。
   • 在 hierarchical model 中引入了两种类型的聚合函数，即均值池化和最大池化，并研究了这些函数的不同组合的效果。
   • 理论上表明HRM 模型在选择适当聚合函数的情况下，包含了几种现有的推荐方法。
   • 实验表明，HRM 模型在 next basket recommendation 的不同评估指标下始终优于 state-of-the-art baseline 。

2. 相关工作：next basket recommendation 是基于隐式反馈的推荐系统的典型应用，其中用户没有显式的偏好（如评分），而只有正向的观察 positive observation（如购买或点击）。

   • 序列推荐器：主要基于马尔科夫链模型，通过在给定最近一个动作的情况下预测用户的下一步动作来利用序列数据。我们的工作与之前方法的主要区别在于：除了序列行为之外，我们还包含了用户的通用兴趣。以外，以前的序列推荐器很少解决因子中 item 之间的交互。

   • 通用推荐器：根据用户的整个购买历史进行推荐 ，而不考虑序列行为。通用推荐器的关键思想是协同过滤 collaborative filtering: CF ，它进一步可以分为基于内存的 CF（通过某些相似性度量找到 k 近邻的用户或 item 来进行推荐）、以及基于模型的 CF（通过分解 user-item 相关性矩阵来进行推荐）。通用推荐器擅长捕获用户的通用兴趣，但是如果没有建模序列行为，那么很难将其用于用户最近的购买行为。

   • 混合模型hybrid model ：结合了序列行为建模和用户通用兴趣建模。

     一个 state-of-the-art 模型是 FPMC，它构建了一个概率转移立方体 transition cube，其中立方体的每一项给出了用户 $u$$u$ 在最近购买了 item $i$$i$ 的条件下接着购买了 item $j$$j$ 的概率。通过分解这个立方体，该方法通过用户、 last item、 next item 之间的三个 pairwise 交互来解释这个概率。以这种方式，FPMC 通过 last item 与 next item 之间的交互来建模序列行为，通过用户与 next item 之间的交互来建模用户的通用兴趣。实验表明，这种混合模型可以比单独的序列推荐器、或者单独的通用推荐器实现更好的性能。

3.1 模型

1. 动机：next basket recommendation 的一个简单的解决方案是：线性组合序列因子sequential factor（来自序列行为模型）和通用因子 general factor（来自用户通用兴趣模型）。然而，这种线性组合假设多个因子之间是独立的。真实世界的结果表明，不同因子之间的独立性假设可能不足以提供良好的推荐。我们需要一个能够更复杂地集成多个因子之间交互的模型。这成为我们工作的主要动机。

2. 令 $\mathcal{U}=\{u_1,\cdots ,u_M\}$$\mathcal U = \{u_1,\cdots,u_{M}\}$ 为所有用户集合，$\mathcal{I}=\{i_1,\cdots ,i_N\}$$\mathcal I = \{i_1,\cdots,i_{N}\}$ 为所有 item 集合，$M$$M$ 为所有用户数量，$N$$N$ 为所有 item 数量。

   对于每个用户 $u$$u$，其交易的购买历史为 ${\mathbb{T}}^u=({\mathcal{T}}_1^u,\cdots ,{\mathcal{T}}_{t_u-1}^u)$$\mathbb T^u=\left(\mathcal T_1^u,\cdots,\mathcal T_{t_u-1}^u\right)$ ，其中 ${\mathcal{T}}_t^u\subseteq \mathcal{I}$$\mathcal T_t^u\sube \mathcal I$ 为 $t$$t$ 时刻该用户的购买 item 集合，$t_u-1$$t_u-1$ 为该用户最近一次购买的时间。所有用户的购买历史记做 $\mathbb{T}=\{{\mathbb{T}}^{u_1},\cdots ,{\mathbb{T}}^{u_M}\}$$\mathbb T = \left\{\mathbb T^{u_1},\cdots,\mathbb T^{u_M}\right\}$ 。给定 $\mathbb{T}$$\mathbb T$，next basket recommendation 任务是推荐用户 $u$$u$ 在下一个时刻（即时刻 $t_u$$t_u$ ）访问时可能会购买的 item 。

   next basket recommendation 任务可以公式化为对用户 $u$$u$ 在第 $t_u$$t_u$ 时刻的交易构建个性化的ranking ${\succ }_{u,t}\in \mathcal{I}\times \mathcal{I}$$\succ_{u,t} \in \mathcal I\times \mathcal I$ ，基于这个 ranking 我们可以向每个用户推荐 top n items 。

3. 为解决上述推荐问题，我们提出了 HRM 模型。HRM 的思想是学习一个可以同时包含序列行为和用户通用兴趣的推荐模型，同时建模这些因子之间的复杂交互。

   具体而言，HRM 将每个用户和每个 item 表达为连续空间中的一个向量，并采用两层结构来构建用户和最近一次交易的 item 的 hybrid representation ：

   • 第一层通过聚合最近一次交易的 item 向量从而形成 transaction representation 。
   • 第二层通过聚合用户向量和 transaction representation 来构建 hybrid representation。

   然后使用得到的 hybrid representation 来预测 next basket 中的 item。HRM 的整体结构如下图所示。正如我们所见，HRM 通过对连续购买进行建模从而捕获序列行为，通过在序列推荐中集成个性化的 user representation 从而建模了用户的通用兴趣。

   该模型有两个不足：

   • 首先，模型无法捕获用户的所有历史，只能“看到 “最近” 一次发生的交易，所以无法捕获用户的长期兴趣。
   • 其次，模型没有捕获用户兴趣的动态演变。

   

4. 更正式而言，令 ${\mathbf{V}}^U\in {\mathbb{R}}^{M\times d}$$\mathbf V^U\in \mathbb R^{M\times d}$ 为用户 representation 矩阵，第 $u$$u$ 行 ${\overrightarrow{\mathbf{v}}}_u^U\in {\mathbb{R}}^d$$\mathbf{\vec v}_u^U\in \mathbb R^d$ 为用户 $u$$u$ 的 representation 向量，$d$$d$ 为因子维度。令 ${\mathbf{V}}^I\in {\mathbb{R}}^{N\times d}$$\mathbf V^I\in \mathbb R^{N\times d}$ 为 item representation 矩阵，第 $i$$i$ 行 ${\overrightarrow{\mathbf{v}}}_i^I\in {\mathbb{R}}^d$$\mathbf{\vec v}_i^I\in \mathbb R^d$ 为item $i$$i$ 的 representation 向量。

   给定用户 $u$$u$ 的两个连续的交易 ${\mathcal{T}}_{t-1}^u$$\mathcal T^u_{t-1}$ 和 ${\mathcal{T}}_t^u$$\mathcal T^u_t$，HRM 通过一个 softmax 函数定义用户 $u$$u$ 在给定最近一个交易 ${\mathcal{T}}_{t-1}^u$$\mathcal T_{t-1}^u$ 的条件下购买 next item $i$$i$ 的概率：

   $$p(i\in {\mathcal{T}}_t^u\mid u,{\mathcal{T}}_{t-1}^u)=\frac{\exp ({\overrightarrow{\mathbf{v}}}_i^I\cdot {\overrightarrow{\mathbf{v}}}_{u,t-1}^H)}{\sum _{j=1}^N\exp ({\overrightarrow{\mathbf{v}}}_j^I\cdot {\overrightarrow{\mathbf{v}}}_{u,t-1}^H)}$$

   其中 ${\overrightarrow{\mathbf{v}}}_{u,t-1}^H$$\mathbf{\vec v}_{u,t-1}^H$ 为用户 $u$$u$ 在时刻 $t-1$$t-1$ 的 hybrid representation ，它被定义为：

   $${\overrightarrow{\mathbf{v}}}_{u,t-1}^H=f_2({\overrightarrow{\mathbf{v}}}_u^U,f_1\left(\{{\overrightarrow{\mathbf{v}}}_l^I\mid l\in {\mathcal{T}}_{t-1}^u\}\right))$$

   其中 $f_1(\cdot )$$f_1(\cdot)$ 和 $f_2(\cdot )$$f_2(\cdot)$ 分别表示第一层和第二层的聚合函数。

5. HRM 的一个优点是我们可以引入各种聚合函数来从 lower level 形成 higher level 的 representation。通过这种方式，我们可以对不同层的多个因子之间的不同交互进行建模，即在第一层对构成了 transaction representation 的 item 之间的交互进行建模，在第二层对 user represetnation 和 transaction representation 之间的交互进行建模。

   在这项工作中，我们研究了均值池化 average pooling 和最大池化 max pooling 这两种典型的聚合函数。显然，均值池化是一种线性运算，它假设输入的 representation 之间相互独立。相反，最大池化是一种非线性操作，它对输入的 representation 之间的交互进行建模，只有那些最重要的特征才会被保留下来。

   注意，还可以定义其它类型的聚合函数，如 top-k 均值池化或者 Hadamard product。我们可能会在将来的工作中研究这些聚合函数。此外，还可以考虑在深度神经网络中引入非线性层，然而我们求助于简单的模型，因为这样的计算复杂度较低从而可以用于非常大的数据集。

   由于 HRM 中有两个聚合，因此我们根据不同的操作组合得到四个版本的 HRM，即：${\text{HRM}}_{\text{AvgAvg}},{\text{HRM}}_{\text{MaxAvg}},{\text{HRM}}_{\text{AvgMax}},{\text{HRM}}_{\text{MaxMax}}$$\text{HRM}_\text{AvgAvg},\text{HRM}_\text{MaxAvg},\text{HRM}_\text{AvgMax},\text{HRM}_\text{MaxMax}$，其中第一个下标表示第一层的聚合函数、第二个下标表示第二层的下标操作。正如我们所看到的，这四个 HRM 版本实际上假设多个因子之间的交互程度不同。

   • 通过仅使用均值池化，${\text{HRM}}_{\text{AvgAvg}}$$\text{HRM}_\text{AvgAvg}$ 假设所有因子之间都是独立的。此外，我们稍后表明 ${\text{HRM}}_{\text{AvgAvg}}$$\text{HRM}_\text{AvgAvg}$ 可以视为 FPMC 的某种变体。
   • ${\text{HRM}}_{\text{MaxAvg}},{\text{HRM}}_{\text{AvgMax}}$$\text{HRM}_\text{MaxAvg},\text{HRM}_\text{AvgMax}$ 都引入了部分交互，要么在最近一个交易的 item 之间、要么在 user represetnation 和 transaction representation 之间。
   • ${\text{HRM}}_{\text{MaxMax}}$$\text{HRM}_\text{MaxMax}$ 同时在两层中使用非线性操作，从而假设所有因子之间完全交互。

6. HRM 的损失函数是负的对数似然：

   $${\mathcal{L}}_{\text{HRM}}=-\sum _{u\in \mathcal{U}}\sum _{{\mathcal{T}}_t^u\in {\mathbb{T}}^u}\sum _{i\in {\mathcal{T}}_t^u}\log p(i\in {\mathcal{T}}_t^u\mid u,{\mathcal{T}}_{t-1}^u)+\lambda ||\mathrm{\Theta }|{|}_F^2$$

   其中：$\lambda$$\lambda$ 为正则化系数，$\mathrm{\Theta }$$\Theta$ 为模型参数（即 $\mathrm{\Theta }=\{{\mathbf{V}}^U,{\mathbf{V}}^I\}$$\Theta=\left\{\mathbf V^U,\mathbf V^I\right\}$）。

   然而直接优化上述目标函数是不现实的，因为计算完整的 softmax 的代价与 item 数量 $N$$N$ 成正比，而这个数量通常非常大。因此我们使用负采样技术：

   $${\mathcal{L}}_{\text{NEG}}=-\sum _{u\in \mathcal{U}}\sum _{{\mathcal{T}}_t^u\in {\mathbb{T}}^u}\sum _{i\in {\mathcal{T}}_t^u}(\log \sigma ({\overrightarrow{\mathbf{v}}}_i^I\cdot {\overrightarrow{\mathbf{v}}}_{u,t-1}^H)+k\times {\mathbb{E}}_{j\in P_I}[\log \sigma (-{\overrightarrow{\mathbf{v}}}_j^I\cdot {\overrightarrow{\mathbf{v}}}_{u,t-1}^H)])+\lambda ||\mathrm{\Theta }|{|}_F^2$$

   其中：$\sigma (x)$$\sigma(x)$ 为 sigmoid 函数，$k$$k$ 为负样本数量，$j$$j$ 为被采样的负样本，$P_I$$P_I$ 为负采样的噪音分布 noise distribution 。

   正如我们所看到的的，带负采样的 HRM 的目标旨在最大化观察到的 item $i$$i$ 的概率、同时最小化未观察到的 item $j$$j$ 的概率。

   我们使用随机梯度下降算法来最小化 ${\mathcal{L}}_{\text{NEG}}$$\mathcal L_\text{NEG}$ 。此外，在学习非线性模型时，我们还采用了 Dropout 技术来避免过拟合。在我们的工作中，我们为每个单元设置了一个固定的 dropout rate （即，0.5）。

7. 一旦学到 user representation 和 item representation，则HRM 的 next basket recommendation 过程如下：

   • 给定用户 $u$$u$ 及其最近一次交易 ${\mathcal{T}}_{t_u-1}^u$$\mathcal T_{t_u-1}^u$ ，对于每个候选 item $i\in \mathcal{I}$$i\in \mathcal I$ ，计算未归一化的概率 ${\overrightarrow{\mathbf{v}}}_i^I\cdot {\overrightarrow{\mathbf{v}}}_{u,t-1}^H$$\mathbf{\vec v}_i^I \cdot \mathbf{\vec v}_{u,t-1}^{H}$ 。
   • 然后根据 item 的未归一化概率对 item 进行排序，并选择 top n 个结果来推荐给用户。

   注意，由于排序只需要考虑相对大小，因此没有必要计算完整的 softmax 值。