一、FPMC [2010]

《Factorizing Personalized Markov Chains for Next-Basket Recommendation》

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的推广。

   • 为了处理转移概率估计的稀疏性，论文引入了一个可以应用于个性化概率转移矩阵的分解模型。这种分解方法导致参数更少，并且由于泛化能力导致它比完全参数化的模型更好的质量。

   • 论文的实验表明，所提出的模型在序列数据上优于其它 SOTA 方法。

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}$ 为对应的随机变量的取值。

   在非集合的推荐场景中，随机变量是在 $\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 在两个数据集上都优于它们。