阿里在《Revisit Recommender System in the Permutation Prospective》中提出了PRS：
1.介绍
。。。
不同于在matching和ranking stages中采用的point-wise方法，通常在reranking阶段会采用许多list-wise的方法。广泛使用的listwise方法的pipeline通常具有三个关键组件：
- 1）Ranking：会根据基础的ranking model的scores生成initial list
- 2) Refining：initial list的list-wise feature分布通常会通过一个设计良好的模型（LSTM&self-attention等）来refine它的rating scores
- 3) Re-ranking：通过refined list-wise rating scores以贪婪方式对候选items进行rerank
总之，已经存在的list-wise方法在推荐中达到效果提升，主要是通过建模list-wise feature分布来聚焦对item rating scores进行refining。
然而，以排列（permutation）的视角看，流行的reranking pipeline不能帮助当前的RS来达到排列最优（permutation-optimal），因为会忽略推荐结果内的排列变化影响（permutation-variant influence）。如图1(1)所示，这里是从真实数据集中收集到的两个推荐结果。它们由相同的items组成并且展示给相同的用户，令人吃惊的是，用户会对排列2做出响应而非1。一个可能的原因是：将更昂贵的item B放置在前，可以促进用户希望去购买更便宜的item A。我们将这种由排列变化造成用户决策的影响称为：在推荐结果内的“排列变化影响（permutation-variant influence）”。通过解决这样的排列变化影响，理想的方法会推荐排列2给用户，它从排列角度上来说是更优的结果。而在排列2中的item A的监督训练，图1(2)所使用的list-wise模型只能获得当遇到共享initial list（比如：item B,A,C）时的item A的优先级。毕竟，list-wise模型会以贪婪的方式通过refined rating scores（例如：排列1）对items进行rerank，从而忽略掉更好的排列2。理想的，图1(3)中permutation-wise方法，通过将item B放置在A之前（从排列1变为排列2），item A的预测的交互概率会获得极大提升，这主要有助于更好地对排列2做出正确判断。相应的，这样包含在lists中的排列变化影响的完整考虑和使用，扮演着重要的角色来近似permutation-optimal推荐结果、以及更好的用户体验。
图1 (1）真实case (2) 和(3)表示在该case下list-wise和permutation-wise方法的对比
实验上，这样的排列会对当前RS潜在带来新挑战，它可以归纳为两个部分：
- 1) 指数级解。假设从size m=100的initial list中需要推荐n=10个items。当前RS会将它看成是一个检索任务，在re-ranking阶段部署list-wise模型会搜索在O(m)的解空间。然而，以排列的角度，解空间会从O(m)膨胀\(O(A_m^n)\)（接近\(O(100^{10})\)）。考虑到在最终item lists中的排列变化影响，用户会对每个list做出不同的响应。实际上，只有一个list会最终推荐给用户，因而如何有效且高效地达到permutation-optimal list会给当前RS带来新挑战。
- 2) permutation-wise evaluation。当前RS使用的大多数方法，会尝试point-wise的方式预测user-item交互概率（例如：CTR和转化率）。如上所述，它需要提供一个统一的permutation-wise ranking准则，来从大量合规的lists中选取permutation-optimal的list，在当前的许多工作中均没有涉及到。
图2
在本工作中，如图2所示，我们进一步将list-wise方法发展到一个新的permutation-wise框架，称为PRS（Permutation Retrieve System）。特别的，PRS会包含：PMatch（permutation-Matching）和PRank（Permutation-Ranking）：
- PMatch阶段会关注于以高效并行方式生成多个候选列表（candidate lists），目标是考虑上排列变化影响以及减轻指数解空间问题。这里我们提出了FPSA（Fast Permutation Searching Algrithm），一个permutation-wise和面向目标（goal-oriented）的beam search算法，来以一种高效方式生成candidate lists。
- PRank stage会提供一个统一的ranking criterion来解决permutation-wise evaluation的挑战。我们会在提出的模型DPWN（Deep Permutation-Wise Network）上使用Bi-LSTM，有了它，排列变化影响可以完全解决。另外，我们提出LR（List Reward）metric来对candidate lists进行排序，它可以通过添加在candidate list中每个item的DPWN的rating scores来进行计算。最后，具有最高LR score的list会被推荐给用户。
为了演示PRS的效果，我们在alimama数据集和taobao数据集上执行一系列实验。实验结果表明它可以胜过SOTA的方法。另外，PRS成功部署到taobao应用场景上，并获得了11%的PV（Page）效果提升、在IPV（Item Page View）获得8.7%的提升。
2.相关工作
。。。
3.准备工作
通常，一个web-scale推荐系统（例如：电商和新闻）由三个stages组成：matching、ranking、reranking。在本paper中，我们关注最终的re-ranking阶段，它的input为由前两stage生成的ranking list（例如：matching和ranking）。reranking的任务是：会精心选择来自input ranking list的候选，并将它们进行重新安排（rearrange）到final item list中，接着展示给用户。数学上，有了user set U和item set I后，我们将list交互记录（list interaction records）标记成：
\[R = \lbrace (u, C, V, y^{CTR}, y^{NEXT} | u \in U, V \subset C \subset I) \rbrace\]这里：
- C：表示的是记录的具有m个items的input ranking list，用于reranking stage，
- V：表示的是具有n个items的final item list，它会最终展示给user u，通常：\(n <= m\)
- \(y_t^{CTR} \in y^{CTR}\)：是user u 对于第t个item \(v_t \in V\)的implicit feedback，其中：当交互（例如：click）被观察到后\(y_t^{CTR} = 1\)，否则：\(y_t^{CTR}=0\)。
- \(y_t^{NEXT}=1\)：表示用户在该item之后的持续浏览，否则\(y_t^{NEXT}=0\)。
在真实工业推荐系统中：
- 每个user u会与一个user profile \(x_u\)相关，它包含了sparse features \(x_s^u\)（例如：user id和gender）和dense features \(x_d^u\)（例如：age）
- 每个item i也会与一个item profile \(x_i\)相关，它包含了sparse features \(x_i^s\)（例如：item id和brand）和dense features \(x_i^d\)（例如：price）
给定上述定义，我们现在将reranking任务公式化为：
定义1: 任务描述
通常的，工业RS的目标是：使得用户消费更多浏览（PV: page view）和interactions（IPV: item page view），对于reranking任务也相同。给定一个特定用户u，以及他的input ranking list C，该任务是学习一个reranking strategy \(\pi: C \xrightarrow{\pi} P\)，它的目标是：从C中对items进行选择和重安排，接着推荐一个final item list P。
4.提出的框架
在本节中，我们介绍permutation-wise框架PRS，它的目标是有效和高效地利用排列变化影响（permutation-variant influence）以便更好地在RS的reranking环节进行item重安排（rearrangements）。为了解决指数解空间，以及permutation-wise evaluation挑战，我们将reranking任务转换成两个后继stages：Permutation-Matching（PMatch）和Permutation-Ranking（PRank）。在PMatch阶段，多个有效算法可以并行方式部署以便考虑上排列变化影响，并从指数解空间中有效搜索candidate item lists。接着，PRank阶段提出了LR metric作为一个统一的permutation-wise ranking规则来进行评估candidate item list set，其中具有最高的LR score的list会被最终推荐。关键概念会归纳在表1中。
表1
首先，我们从users和items的representations开始，它是我们提出的框架的基础inputs。从之前的工作中，我们会为users和items将可提供的profiles参数化成vector representations。给定一个user u，它相关的sparse features \(x_u^s\)和dense features \(x_u^d\)，我们将每个sparse feature value嵌入到d维空间中。接着，每个user可以表示成：
\[x_u \in R^{\mid x_u^s \mid \times d + \mid x_u^d \mid}\]其中：
- \(\mid x_u^s \mid\)和\(\mid x_u^d \mid\)分别表示user u的sparse和dense feature space的size。
相似的，我们将每个item i表示成：
\[x_i \in R^{\mid x_i^s \mid \times d + \mid x_i^d \mid}\]天然的，我们将input ranking list C记录成：
\[C = [x_c^1, \cdots, x_c^m]\]以及将final item list V标记成：
\[V = [x_v^1, \cdots, x_v^n]\]其中：
- m和n：分别是在input ranking list和final item list中的items数目。
在下面章节中，我们会放大到PMatch。对于每个stage，我们将介绍划分成两部分：一个是offline training（preparation），另一个是online serving（inference）。这两部分的主要不同是：R中的\(V, y^{CTR}, y^{NEXT}\)是在offline training给出，而不是在online serving中。
4.1 PMatch阶段
PMatch stage提出是为了以一个更高效方式获得多个有效的candidate lists。如图3所示，有许多算法【1，25，26，35】可以并行部署来生成item lists，接着通过list merge操作合并成candidate list set。尽管有管，当前努力会忽略在最终item list中的排列变化影响，我们提出了一个permutation-wise和goal-oriented beam search算法，称为FPSA（Fast Permutation Searching Algorithm）。
图3 PRS框架的整体架构
4.1.1 offline training
为了使得用户进行更多的浏览和交互，除了常规使用的CTR score外，我们首先设计NEXT score，它会预测：用户在这个item之后是否持续浏览的概率。具有更高NEXT scores的items可以增加用户持续浏览的动力，它会提升后续items被浏览和点击的概率。
特别的，有了labeled interaction记录R，我们会详细说明两个point-wise models：
- CTR预估模型：\(M^{CTR}(v \mid u; \theta^{CTR})\)
- NEXT预估模型：\(M^{NEXT}(v \mid u; \theta^{NEXT})\)
它们的计算如下：
\[\begin{align} \hat{y}_t^{CTR} & = M^{CTR}(v | u; \theta^{CTR}) \\ & = \sigma(f(f(f(x_v \oplus x_u)))) \\ \hat{y}_t^{NEXT} & = M^{NEXT}(v | u; \theta^{NEXT}) \\ & = \sigma(f(f(f(x_v \oplus x_u)))) \end{align}\]…(1)
其中：\(f(x) = ReLU(Wx+b)\)，\(\sigma(\dot)\)是logistic function。两个模型可以通过binary cross-entropy loss function进行优化，定义如下：
\[\begin{align} L^{CTR} & = - \frac{1}{N} \sum\limits_{(u,V) \in R} \sum\limits_{x_0^t \in V} (y_t^{CTR} log \hat{y}_t^{CTR} + (1 - y_t^{CTR}) log(1 - \hat{y}_t^{CTR})) \\ L^{NEXT} & = - \frac{1}{N} \sum\limits_{(u,V) \in R} \sum\limits_{x_0^t \in V} (y_t^{NEXT} log \hat{y}_t^{NEXT} + (1 - y_t^{NEXT}) log(1 - \hat{y}_t^{NEXT})) \end{align}\]…(2)
我们会训练\(\theta^{CTR}\)和\(\theta^{NEXT}\)，直到根据等式(2)收敛。
4.1.2 Online serving
在本工作中，我们将reranking task看成是：从input ranking list中顺序的选择items，直接达到预定义长度。Beam search【21，30】是一种常用的技术，它通过在一个有限集合中探索和扩展最可能的candidates，来生成多个有效lists。在FPSA算法中，我们以一种goal-oriented方式实现了beam search算法，也就是说：我们会在每个step选择具有最高estimated reward的lists。
图4 FPSA算法说明
我们会在图4和算法1中清楚展示和说明提出的FPSA算法。
- 首先，我们会在input ranking list C中，通过收敛的CTR预估模型\(M^{CTR}(v \mid u; \theta^{CTR})\)和NEXT prediction 模型\(M^{NEXT}(v \mid u;\theta^{NEXT})\)分别得到：点击概率为\(P_{c_i}^{CTR}\)和持续浏览概率\(P_{c_i}^{NEXT}\)，并将两个predicted scores绑定到每个item \(c_i\)上。
-
接着，在每一步我们会为在set S中的每个list穷举扩展剩余candidates，并根据它们 calculated estimated reward（第1-17行）保留top k的candidate lists。
在第18-28行，在每个step中，当迭代经过在list中的每个item时，我们会计算：transitive expose probability \(p^{Expose}\)乘以前面items的NEXT scores。受\(p^{Expose}\)的影响，我们会计算PV reward \(r^{PV}\)以及IPV reward \(r^{IPV}\)，并在迭代的终点将它们的求和表示为reward \(r^{sum}\)。这里：\(r^{PV}， r^{IPV}, r^{sum}\)分别表示estimated PV、IPV以及该list的混合收益。
算法1
在算法的结尾，我们会获得candidate list set \(S= \lbrace O_1, \cdots, O_t \rbrace_{size=k}\)，它可以根据reward \(r^{sum}\)来直接选择top list。另外，从其它方法生成（例如：DLCM和PRM）的final item lists也可以合并到S中，并进一步通过后续的PRank stage来进行排序。
4.1.3 有效性研究
我们尝试改善FPSA算法的效率。特别的，我们会在ranking stage以并行方式部署CTR和NEXT prediction模型来对每个item的 CTR和NEXT scores进行打分（rate），它的算法复杂度是O(1)。对于算法1中的算法，我们会以并行方式执行6-15行的循环，并采用最小最大堆（min-max heaps）的排序算法来选择第16行的top-k结果。总之，当是算法1时，我们会将算法复杂度减小为\(O(n(n+k logk))\)。
总之，FPSA的算法复杂度是\(a O(1) + b O(n(n+ k logk))\)。它要比已存在的list-wise方法（比如：DLCM【1】和PRM【26】）更高效，它们的复杂度为\(a O(n) + b O(n log n)\)。这里\(a >> b\)表示在深度模型中的矩阵计算开销要比数值型计算开销要多很多。(注：这里的n是final item list的size)
4.2 PRank stage
PRank stage为由PMatch stage生成的candidate list set提供了一个统一的permutation-wise ranking规则。当前RS的大多数方法，主要遵循基于rating scores的greedy strategy。尽管有效，但策略本身忽略了在final item list中的排列变化影响，因而不能评估排列。出于该目的，如图3的右边所示，我们提出了LR（List Reward）指标来从由PMatch stage中提供的candidate list set中选择permutation-optimal list，它通过对精心设计的permutation-wise模型DPWN（Deep Permutation-Wise Network）的rating scores计算得到。
4.2.1 Offline training
图5 DPWN模型的技术架构
DPWN的总架构如图5所示。DPWN是为了捕获和建模由final item list包含的排列变化影响。通过考虑这样的动机，DPWN \(M(x_v^t \mid u, V; \theta^D)\)，通过\(\theta^D\)进行参数化，来预测user u和第t个item \(x_v^t\)在final item list V中的permutation-wise交互概率。Bi_LSTM可以非常好地捕获这样的时间依赖（time-dependent）和在排列中的long-short term信息。数学上，对于第t个item \(x_v^t\)的forward output state可以如下进行计算：
\[i_t = \sigma(W_{xi} x_v^t + W_{hi} h_{t-1} + W_{ci}c_{t-1} + b_i) \\ f_t = \sigma(W_{xf} x_v^t + W_{hf} h_{t-1} + W_{cf}c_{t-1} + b_f) \\ c_t = f_t x_v^t + i_t tanh(W_{xc}x_v^t + W_{hc} h_{t-1} + b_c) \\ o_t = \sigma(W_{xo} x_v^t + W_{ho} h_{t-1} + W_{co} c_t + b_o) \\ \overrightarrow{h_t} = o_t tanh(c_t)\]…(3)
其中：
- \(\sigma(\cdot)\)是logistic function
- i, f, o和c是input gate、forget gate、output gage以及cell vectors，它们具有相同的size为\(x_v^t\)。权重矩阵的shapes可以通过下标进行表示。相似的，我们可以得到backward output state \(\leftarrow{h_t}\)。接着，我们会将两个output states \(h_t = \rightarrow{h_t} \odot \leftarrow{h_t}\)进行拼接，并将\(h_t\)表示为序列表示\(x_v^t\)。
由于在CTR预估领域，建模复杂交互的强大能力，我们将MLP集成到DPWN中以获得更好的特征交叉。这里，我们将Bi-LSTM公式化为：
\[M(x_v^t | u, V; \theta^D) = \sigma(f(f(f(x_u \oplus x_v^t h_t))))\]…(4)
其中：
- \[f(x) = ReLU(Wx+b)\]
- \(\sigma(\cdot)\)是logistic function
DPWN的参数集合是\(\theta^D = \lbrace W_*, b_* \rbrace\)，例如：是Bi-LSTM和MLP的参数的union。
很明显，DPWN可以通过binary cross-entropy loss function来进一步优化，它的定义如下：
\[L^D = - \frac{1}{N} \sum\limits_{(u,V) \in R} \sum\limits_{x_v^t \in V} (y_{uv}^t log \hat{y}_{uv}^t + (1 - y_{uv}^t) log(1 - \hat{y}_{uv}^t))\]…(5)
其中，D是训练dataset。出于便利性，我们将\(\hat{y}_{uv}^t\)看成是\(M(x_v^t \mid u, V; \theta^D)\)，\(y_{uv}^t \in \lbrace 0, 1 \rbrace\)是ground truth。我们可以通过最小化\(L^D\)来对参数\(\theta^D\)最优化。
注意，DPWN与当前list-wise方法的主要不同点是：DPWN会建模final item list，而非input ranking list。实际上，用户会更受展示的final item list的排列信息的影响。
4.2.2 Online serving
如上所述，我们基于DPWN模型提出了一个统一的permutation-wise LR metric，它被应用于：在PMatch stage生成的candidate list set达到最优的permutation-optimal list解。特别的，我们会计算：在candidate list set S中的每个list \(O_t\)的LR（list reward）score：
\[LR(O_t) = \sum\limits_{x_o^i \in O_t} M (x_o^i | u, O_t)\]…(6)
之后，具有最高LR score的list P会被最终选中并推荐给该user，获得permutation-optimal list的希望，最可能满足用户的需求。
最终，我们将PRS framework中的PMatch和PRank的online serving部分称为学到的reranking startegy \(\pi\)，来从input ranking list C中生成permutation-optimal list P。
5.实验
在本节中，会开展许多在线和离线实验来验证PRS的有效性，目标是回答以下问题：
- RQ1: 在PRank stage中提出的LR metric是如何准备评估permutations的收益（profits）的？
- RQ2: 在PMatch stage中的FPSA算法，是如何以有效方式从指数级解空间中生成candidate list set的？
- RQ3: 在真实推荐系统中PRS的效果如何？
5.1 实验设置
5.1.1 Datasets
。。。
5.2 效果对比（RQ1）
5.3 FPSA算法研究（RQ2）
5.4 在线AB测试（RQ3）
6.结论
略