阿里在KDD 2020《Maximizing Cumulative User Engagement in Sequential Recommendation: An Online Optimization Perspective》提出了MDP-SSP。

摘要

为了在序列推荐（sequential recommendation）中最大化累积用户参与度(cumulative user engagement 例如：cumulative clicks)，通常需要对潜在的两个冲突目标进行tradeoff，也就是说：追求更高的即时用户参与度（immediate user engagement，例如：click-through rate）和鼓励用户浏览（例如：更多的items曝光）。现存的工作通常分开考虑这两个任务。因而会导致次优的结果。在本paper中，我们从在线最优化的视角，研究了该问题，并提出了一个灵活并且实际的框架来对更长的用户浏览长度和更高的即时用户参与度间进行tradeoff。特别的，我们将：

• items：看成是actions
• 用户请求（user requests）：看成是states
• 用户离开(user leaving)：看成是一个吸收态（absorbing state）
• 每个用户的序列行为：看成是一个个性化的马尔可夫决策过程Markov decision process（MDP）

因此，最大化cumulative user engagement的问题可以转化成一个随机最短路径（SSP：stochastic shortest path）问题。同时，有了immediate user engegement和退出概率估计，可以看到：SSP问题可以通过动态规划（DP）进行有效求解。在实际数据集上的实验表明了该方法的有效性。另外，该方法被部署到大型电商平台上，达到了7%的cumulative clicks的提升。

1.介绍

最近些年，sequential recommendation在许多场景在使用。比如：头条，tiktok等。

不同于传统的推荐系统（通常推荐items的数目的固定的），sequential recommendation的最重要特性是：它会迭代式推荐items，直到用户退出（如图1）。这意味着，用户可以浏览无尽的items。我们针对此的目标是：最大化在每个session内的累积用户参与度（cumulative user engagement)，比如：累积点击（cumulative clicks）、累积停留时间（cumulative dwell time）等。为了该目的，推荐系统需要同时达成两个目标：

• a) 吸引用户具有一个更长的session，比如：浏览更多items
• b) 捕获user interests，比如：达到更高的immediate user engagement

图1

在传统的推荐系统中，由于推荐item的数目是固定的，大多数努力都花在提升immediaite user engagement上，它通常通过CTR进行衡量，等。然而，当这样的一个策略被用到sequential recommendation中时，会趋向于产生次优的cumulative user engagement，这是因为浏览items的数目有限。另外，由于它们间的内在冲突，想要同时达到一个更长session和更高immediate user engagement是一个trivial任务（可以通过实验进行演示）。例如，为了达到一个更长的session，它通常需要探索更多样的推荐结果；这会牺牲immediate user engagement。因此，如何对一个一个更长的session和更高的immediate user engagement进行tradeoff变得非常重要，可以达到一个更高的cumulative user engagement，这对于sequential recommendation来说是个非常重要的问题。

通常来说，在sequential recommendation中存在的工作划成两派。派系1尝试利用sequential information（例如：用户的交互行为）来更准地估计user engagement（例如：CTR）的概率【8，11，12，16，22】。例如，通过使用RNN或它的变种【8，11，25】。通过利用sequential行为模式，这些方法关注于更准地捕获用户兴趣，但没有考虑扩展session length，因而会导致次优结果。基于多样结果的观查，趋向于吸引用户浏览更多的items，第二派的方法显式考虑推荐结果多样性【7，9，23】。然而，在多样性和用户浏览长度间的关系是非常经验性的；因而，直接优化多样性并没有充分理由，特别是存在这样的事实：目前不存在被广泛接受的meartures。因此，在sequential recommendation中最优化cumulative user engagement仍是个挑战。

在本paper中，我们从在线最优化（online optimization）的角度，考虑在sequential recommendation中最大化cumulative user engagement的问题，并提出了一个灵活和实际的框架来解决它。特别的，当将不同的items看成是不同的actions时，用户不同的请求看成是states，用户离开看成是一个absorbing state，在MDP框架中的用户浏览过程，是一个最大化cumulative user engagement的问题，可以看成是一个随机最短路径问题（SSP）问题。为了让该框架可行，在每个state（除了absorbing state），我们需要知道对于每个可能action的两个概率，例如：达到user engagement（例如：click）的概率以及转换成absorbing state的概率（这意味着用户退出浏览过程）。很明显，估计user engagement的概率已经被广泛研究，许多已经存在的机器学习方法可以被采用。同时，我们提出了一个multi-instance learning方法来估计将absorbing state的转移概率（例如：用户退出）。有了该框架以及相应的概率被有效估计，SSP问题可以通过动态规划（DP）进行有效求解。在真实datasets中的实验表明了该方法的有效性。

2.相关工作

2.1 Sequential Recommendation

在最近几年，常规推荐方法，例如：RNN models，使用attention的memory network，被广泛应用于Sequential Recommendation场景。为了找到应推荐的next item，RNN models会通过使用历史序列信息捕获用户的sequence模式。可以训练一个memory network并引入attention机制来加权某些sequential elements。【11，22】表明：这些方法可以极大胜过经典方法（它们会忽略sequential信息）。本质上，他们仍会估计next item的immediate user engagement（），不会考虑上quit probability。因此，进一步的提升必须最大化cumulative user engagement。

2.2 MDP and SSP

随机最短路径（SSP）是一个关于经典最短路径问题的随机版本：对于一个graph的每个node，我们必须选择一个关于在后继节点集合上的概率分布，以便达到一个特定目标节点具有最小的期望开销【4，21】。SSP问题通常是一个MDP问题，具有以下假设：存在一个absorbing state和一个合适的策略。一些动态规划的变种可以被用来求解该问题。RTDP是一个算法，用来求解non-deterministic planning问题，它可以看成是一个启发式搜索或者一个动态规划过程。Labeled RTDP是RTDP的一个变种，关键思想是：如果它的后继节点已经收全省，将一个state标记为sloved，sloved states不会进一步更新。

2.3 Multi-Instance Learning

在MIL任务中，每个样本可以通过一个实例包进行表示【10】。如果它包含了至少一个正实例，则该包（bag）是正向（positive）；否则为负。根据[1] 该方法可以分成三个范式：

• instance-space paradigm
• bag-space paradigm
• embedded-space paradigm

对于我们的sequential recommendation设定，建模转移概率与instance-space paradigm一致。在instance-level MIL任务上，一些SVM-based的方法被提出来。MI-SVM是一个SVM-like MIL方法的变种，主要思想是：在每次迭代中，它会强制远离决策超平面（decision hyperplane，它具有最大间隔）的instance为postive。

3.问题声明

我们将每个浏览过程建模成一个个性化的MDP过程，它包括：一个absorbing state，我们将最大化cumulative user engagement的问题看成是一个SSP问题。

3.1 个性化MDP模型

MDP包含了4个元素的tuple （S, A, R, P)：

• State space S： \(S = \lbrace s_1, s_2, s_3, \cdots, s_t, \cdots, s_T, s_A \rbrace\)。这里我们将推荐序列中的每个step看成是一个单独的state，并定义\(s_t = t\)，其中t是step index。由于每个step中只有一个item会被展示给用户，t也是浏览items的顺序数（sequence number）。T是浏览session length的上限，它对于推荐场景来说是足够大的。\(s_A\)被定义成absorb state，意味着用户离开。
• Action space A：\(A = \lbrace 1,2,3,\cdots, K\rbrace\)。Action space A包含了所有candidates，它可以在当前session中被推荐
• Reward R：\(R \in R^{(T+1) \times K}\)。将S中的state表示成s，将在A中的action表示a，那么\(R_{s,a}\)表示在state s上采用action a的reward。特别的，\(R_{s_t, a_t}\)是在第t个step的immediate user engagement（例如：CTR）。
• 转移概率（Transition probability） P： \(P \in R^{(T+1) \times K \times (T+1)}\)，并且\(P_{s,a,s'} \in [0, 1]\)是在采用action a后，从state s转移到state \(s'\)的概率。

由于在S中的states是顺序的，我们在P上引入一个regulation，它来自所有states（除了\(s_T, s_A\)），用户可以转移到下一个state（继续浏览），或者跳到absorbing state（退出）。另外，从最后的浏览step来看，用户只会进到absorbing state。正式的，我们有：

\[\begin{cases} P_{s_i, a_i, s_{i+1}} + P_{s_i, a_i, s_A} = 1, i < T \\[2ex] P_{s_T, a_t, s_A} = 1, i=T \end{cases}\]

…(1)

该过程的有限状态机如图2所示。再者，强调的是，提出的MDP模型是个性化的，我们需要为每个online session来infer一个新的MDP模型。生成MDP models的一个有效算法会在后面呈现。

图2

3.2 SSP问题

基于MDP模型，在sequantial recommendation中的累积回报（cumulative rewards）可以公式化为一个SSP问题：给定一个MDP，目标是寻找一个policy \(\pi^*: S \rightarrow A\)，它可以帮助我们规划一个具有最大累计回报的path：

\[\pi^* = argmax_{\pi} E(\sum\limits_{t=1}^{\tau} R_{s_t, a_t})\]

…(2)

其中，\(\tau\)是实际浏览长度。\(\tau\)的分布可以被导出：

\[P(\tau \geq t) = \prod_{i < t} P_{s_i, a_i, s_{i+1}}\]

…(3)

因而，等式(2)的expected cumulative reward可以被表示为：

\[E(\sum\limits_{t=1}^{\tau} R_{s_t, a_t}) = \sum_{t \leq T} R_{s_t, a_t} P(\tau \geq t)\]

…(4)

最终，通过将等式(1)引入到等式(4)中，我们有：

\[E(\sum\limits_{t=1}^{\tau} R_{s_t, a_t}) = \sum\limits_{t=1}^T R_{s_t, a_t} \times \prod\limits_{i < t} (1 - P_{s_i, a_i, s_A})\]

…(5)

3.2.1 Remark 1

最大化等式（5）的目标是共同最优化以下两个点：

• 1）用户浏览长度（\(\tau\)）
• 2）immediate user engagement （例如：\(R_{s_t, a_t}\)）

根据该公式，我们应首先估计等式（5）中的\(R_{s_t, a_t}\)和\(P_{s_i, a_i, s_A}\)，它本质上会生成一个个性化的MDP模型。接着我们通过最大化等式(5)来最优化一个policy，它可以用来为相应用户规划一个推荐序列\([a_1, \cdots, a_T]\)（或者称为 在SSP中的Path）。

4.提出的方法

为了最大化expected cumulative rewards，我们会从personlized MDP model中学习一个MDP generator，它可以在线生成，接着使用personized MDP模型来规划推荐序列。因此，提出的MDP-SSP框架包含了两部分：一个离线MDP Generator和一个在线SSP Planer，它如图3所示。

图3 MDP-SSP框架

4.1.1 MDP Generator

它被设计成用来为每个online session生成personalized MDPs。在该部分中存在两个子模块：Model Worker和Calibration Worker。Model Worker被用来从离线历史数据中生成一个模型，目标是提供个性化MDP的必要元素。特别的，等式（5）中需要的reward function \(R_{s_t, a_t}\)和退出概率（quit probability） \(P_{s_i, a_i, s_A}\)。这里：

• \(R_{s_t, a_t}\)可以是一个immediate user engagement，例如：immediate click，因而，Model Worker包含了相应的estimation model，例如：click model。
• \(P_{s_i, a_i, s_A}\)与一个quit model相关，它决定着浏览session长度，是一个关于Model Worker的重要组件。

再者，由于SSP planing的效率依赖于生成的MDP model的accuracy，我们引入一个额外的Calibration Worker来对从学到的模型中获得的ranking scores进行calibrate到real value【14， 18， 20】。

4.1.2 SSP Planer

它会规划一个最短路径（具有最大cumulative rewards），它包含了顺序的推荐items。它也包含了两个submodules：MDP Producer和SSP Solver。基于通过离线MDP Generator算法学到的该generator，MDP Producer 会为用户的当前session生成一个个性化的MDP。接着SSP Solver会计算一个基于个性化MDP的最优路径给该用户。

4.2 Offline MDP Generator算法

在本节中，我们描述了一个离线算法来学习reward function \(R_{s_t, a_t}\)以及quit probability \(P_{s_i, a_i, s_A}\)，它对生成online个性化MDPs是必需的。我们将看到建模\(P_{s_i, a_i, s_A}\)的问题会更严格和困难。实际上，我们获得的历史数据通常是一个item set，它包含了该用户看到过的items，直到session结束（它会做出用户退出或者继续浏览）。然而，很难知道item set中的哪个item是准确的主因。为了估计每个item的退出概率，我们会采用MIL框架，通过采用item set作为bag，将item作为instance。详细的，如果该item set会造成一个quit，那么该用户会不喜欢在该set中的所有items；如果该item set会造成一个持续的浏览，那么在item set中至少有一个item会被该用户接受，它与MIL setting是一致的。

4.2.1 Remark 2

标准的MIL猜想声明：所有negative bags只包含negative instances，positive bags包含至少一个postive instance。

通过使用一些经典的MIL技术，我们可以获得如下user quit model。

4.2.2 User Quit Model

基于用户的浏览历史，我们可以获得包含了bags \(B_i\)的序列，你可以验证在浏览session中只有最后的bag不会让users继续浏览。我们假设：该bag会继续保持该用户是一个postive bag，写成\(B_i^+\)，并且最后一个是negative bag，写成“\(B_{leave}^-\)”，因此，一个浏览session 为：\(B=(B_1^+, \cdots, B_i^+, \cdots, B_{leave}^-)\)。我们的任务是构建一个模型来预测每个new instance \(B_{*,j}\)的quit probability。然而，存在一个gap，我们的training labels是bag level，而predictions是instance level。为了处理该问题，我们引入MI-SVM【2】来帮助我们训练一个instance level model，它具有bag level data，据我们所知，它对推荐来说是一个MIL的新应用。quit model的训练过程如算法1所示。

4.2.3 Model Calibration

在工业界推荐系统中，由click model和quit model提供的ranking scores，并不等于MDPs中的reward \(R_{s_t, a_t}\)以及转移概率\(P_{s_i, a_i, s_A}\)。因而，它必须对模型的output进行calibrate到真实概率上。对该话题感兴趣的读者可以去【14，18，20】进行详细阅读。在本paper中，我们将predicted score表示成\(f(B_{i,j})\)，真实概率值可以如下进行表示：

\[P(y=1 | B_{i,j}) = \frac{1}{1 + exp(A * f(B_{i,j}) + B)}\]

…(6)

其中，A和B是两个scalar参数，可以从历史数据中学习到.

4.3 Online SSP Planner算法

基于最近子节中提到的MDP Generator，我们会正式介绍SSP Planer，它包含了MDP Producer和SSP Slover。

4.3.1 MDP Producer

当一个新的session来的时候，MDP Producer接受来自server的关于user和items的在线信息，接着feeds它们到从MDP Generator中genreators中。接着，可以获得reward和转移概率并实时生成一个个性化MDP。值得注意的是，关于以下的信息：用户已经浏览了多少items，有多少item的类目已经被展示给用户，该用户点击了多少次等，都应该被考虑。这些交互features会扮演着重要的角色，造成用户继续浏览或退出。

4.3.2 SSP Solver

从MDP Producer中，我们可以为当前session获得一个个性化MDP，下一个工作是，寻找一个路径\([a_1, \cdots, a_T]\)，它具有最大cumulative rewards。除了absorbing state外，相应的MDP具有T个states，接着最优的state value function可以使用在T-steps交互的动态规划进行求解。接着，很容易验证，我们特定设计的MDP的transition matrix会保持一个上三角结构，如等式(7)所示。

(7)

基于特殊的结构化转移矩阵，很容易发现：当我们更新当前的state value function，后者的state value function不会变化。因此，向后归纳（backwards induction）会被采纳。我们可以从absorbing state开始，迭代式获取最优的policy以及相关的最优state value function。我们正式地将该过程归纳如下：

\[V^*(s_A) = 0\]

…(8)

再者，当i = T时，我们有：

\[\pi^*(s_T) = argmax_{a_T} \lbrace R_{s_T, a_T} + P_{s_T, a_T, s_A} V^*(s_A) \rbrace \\ = argmax_{a_T} \lbrace R_{s_T, a_T} \rbrace, \\ V^*(s_T) = max_{a_T} \lbrace R_{s_T, a_T} \rbrace\]

…(8)(9)(10)

当 i < T时，我们有：

\[\pi^*(s_t) = argmax_{a_t} \lbrace R_{s_t, a_t} + P_{s_t, a_t, s_{t+1}} V^*(s_{t+1}) + P_{s_t, a_t, s_A} V^*(s_A)\ rbrace \\ = argmax_{a_t} \lbrace R_{s_t, a_t} + P_{s_t,a_t,s_{t+1}} V^*(s_{t+1})\rbrace \\ V^*(s_t) = max_{a_t} \lbrace R_{s_t, a_t} + P_{s_t,a_t,s_{t+1}} V^*(s_{t+1}) \rbrace\]

…(11)(12)

基于等式(8)(12），我们可以计算一个最优的路径 \([a_1, \cdots, a_T]\)。最优化过程如算法2所示。我们可以看到：整个planing过程相当简单和清晰，它有利于提出方法的在线应用。特别的，假设存在K个候选，SSP的复杂度为O(TK)个。

5.实验

我们在一个大型电商平台上开展实验。首先分析了数据特性：表明使用SSP的必要性，接着在离线和在线评估SSP。

5.1 数据集

Dataset 1: MDP Generator的数据集。它包含了15天关于user item交互的历史数据，基于此，我们可以学习模型来预测ctr以及任意user item pair的退出概率（quit probability）

Dataset 2: 该dataset用于SSP offline evaluation。我们收集活跃用户以及它们相应的浏览sessions，并丢弃掉那么不活跃用户或过度活跃用户。根据规则：是否浏览session length在50个items到100个items间进行采样。最终，我们得到1000个users以及相应的浏览sessions。浏览sessions的平均长度是57.

Dataset 3: 该dataset用于SSP online evaluation。它实际上是线上环境，每天具有1000w用户和1亿items。

许多策略（包括SSP）将被部署，会对Dataset 2和Dataset 3中的每个用户进行rerank个性化的候选items，来验证它们在最大化cumulative user engagement上的效果。在那之前，我们应首先验证：该datasets会与如下特性一致：

• 歧视（Discrimination）: 不同的items会提供不同的quit概率，他们会具有一个明显的歧视。否则，当做出推荐时没必要考虑quit概率。
• 弱相关（Weakly related）： 对于一个用户来说，一个item的退出概率会与CTR弱相关。否则SSP和Greedy会是相同的。

5.2 Evaluation Measures

在该实验中，我们会考虑cumulative clicks作为cumulative user engagement。更者，我们将cumulative clicks命名为IPV，这意味着Item Page View，常用于工业界。浏览深度（Browse length：BL）也是一个measurement，因为IPV可以通过让用户浏览更多的items来进行最大化。

在离线评估中，假设：推荐的sequence length是T，根据等式(1)-(5)，我们有：

\[IPV = \sum\limits_{t=1}^T R_{s_t, a_t} \times \prod\limits_{i<t} (1 - P_{s_i, a_i, s_A}) \\ BL = \sum\limits_{t=1}^T \prod_{i < t} (1 - P_{s_i, a_i, A})\]

…(13)(14)

再者，推荐序列的CTR的定义如下：

\[CTR = \frac{IPV}{BL}\]

…(15)

在每个evaluation中，IPV可以根据实际在线情况进行统计，根据：

\[IPV = \sum\limits_{t=1}^{\tau} c_t\]

…(16)

其中：\(c_t \in \lbrace 0, 1\rbrace\)表示在t step上的click行为，而\(\tau\)是浏览深度，例如：\(BL=\tau\)。

5.3 对比策略

• Greedy：在我们的方法与传统方法间的关键不同点是：我们会考虑user的退出概率，并计划着一个可以直接最大化IPV的path，而大多数其它方法尝试尽可能准地估计每个step的reward \(R_{s_t, a_t}\)。然而，当计划着根据\(R_{s_t, a_t}\)贪婪地对items进行排序时，会忽略掉\(P_{s_i, a_i, s_A}\)对于IPV来说很关键。Greedy是第一个对比策略，它的quit概率\(P_{s_i, a_i, s_A}\)不涉及。假设：存在K个侯选，planning path的长度为T，则复杂度是\(O(TK)\)。
• Beam Search：这是一个search算法，可以对效果（performance）和消耗（consumption）进行平衡。它的目的是：将相对最优的路径以序列方式解码。它会被选择作为对比策略，因为退出概率\(P_{s_i, a_i, s_A}\)会被涉及。我们会根据等式（13）计算beam search score，因此，Beam Search会直接应用到这来最优化IPV。假设：存在K个候选，planning path的长度是T，复杂度是O(STK)，其中S是beam size。

5.4 MDP Generator Learning

我们首先会描述MDP Generator learning如第5.4节所示。

5.4.1 Model Learning

在模型学习中，我们会充分利用user属性和item属性。再者，我们会添加interactive features，例如：该item的类目已经被展示给该user多少次、被给user点击多少次，它直觉上对于用户是否做继续浏览动作扮演着一个很重要的角色。AUC，是一个频繁使用的metric，被用来measure 学到的模型，结果如表1所示。

这里我们简短声明下：关于Quit Model的测试方法。由于我们确实不知道哪个item使得用户做出继续浏览行为，因而AUC不能在instance level被直接计算。在bag level中使用instance prediction来计算AUC更合理，因为我们可以假设：如果该bag包含了至少一个postive instance，该bag是positive的；如果所有instance是negative的，则该bag是negative的。

再者，我们会在Quit Model上开展一个对比实验来表明：采用MIL的必要性。由于bag labels是已知的，最直觉的想法是：使用bag的label来表示 instance的label。基于此想法，我们获取了一个\(QuitModel_{no\_MIL}\)，并且AUC也在bag level进行计算。结果如表2所示，从中我们看到，采用MIL对于Quit Model learning来说可以给出一个提升。

5.4.2 Model Calibration

Calibration尝试将从models的ranking scores映mtdf到real value中。这里非常重要，error会累积，见等式(11)(12)。我们会使用普拉特扩展(platt scaling)，并采用RMSE（Root Mean Square Error）作为measurement。结果如表3所示。

从表3中，可以看到，在Calibration后可以达到极大提升，接着real value和calibrated value的曲线在图4和图5中。横坐标是通过predicted scores进行排序的items，纵坐标是calibrated score和real score。real score可以从items bin中获得。

图4

图5

5.4.3 Discrimination

在dataset 2中，对于每个user我们会从MDP Generator（，例如：items的用户浏览session）中获得相应候选的quit probability。接着，可以获取一个user的quit probability list \(l_u = (q_1, \cdots, q_i, \cdots, q_n)\)，其中\(q_i\)是当推荐item i给user u的quit probability。每个list会计算标准差（STD）和MEAN，接着dataset的统计数据如表4所示。从表中，它可以表明：对每个user，不同的candidates会做出不同的贡献来保持用户浏览（user browsing），接着他们具有一个极大的discrimination。

表4

5.4.4 弱相关

我们进一步研究：在quit probability和immediate user engagement（例如：每个step的reward）间的相关性。对于每个user，我们会获得两个item lists \(l_{u1}\)和\(l_{u2}\)，它具有长度L=20. 其中，\(l_{u1}\)和\(l_{u2}\)会根据\(R_{s_t, a_t}\)以及\((1- P_{s_i, a_i, s_A}\)分别被贪婪生成。如果\((1- P_{s_i, a_i, s_A}\)和\(R_{s_t, a_t}\)完全正相关，\(l_{u1}\)和\(l_{u2}\)会是相同的，它会导致SSP和Greedy的equality。我们会使用Jaccard Index和NDCG来measure \(l_{u1}\)和\(l_{u2}\)间的相似度，dataset的平均结果如表5所示。从表中可知，我们会发现：在dataset中，quit probability和immediate user engagement会被弱相关。

表5

5.5 SSP Planner: 离线评估

5.5.1 SSP Plan。

我们会根据上面的每个策略，计算一个具有T step的序列list：\(L_{T} = (a_1, a_2, \cdots, a_T)\)。\(L_T\)的收益可以根据等式(13)-(15)进行计算。

详情如表6所示，我们可以发现：

• Greedy会达到最佳的CTR，而SSP会达到最佳的IPV和BL。这会展示我们的思想：IPV可以通过使得用户浏览更多内容来进行提升。SSP不会最优化每一step的效率（effectiveness），它的目的是提升累积点击（cumulative clicks）的总数。
• step数越长，IPV和BL的优化越大。见：T=20和T=50，当T乘以2.5时，从20到50，IPV和BL两者的提升会超过2.5倍（1347.57 vs. 392.97, 4045.47 vs. 1066.08）。这会产生与我们期望一致的结果：计算越多的step会导致在users中的quit probability越大。

表6

5.5.2 SSP Plan具有Duplicate Removal

在一些实践场景中，items会禁止重复展示。我们需要在三个策略上做出一个折中：

• Greedy：在前t steps中选中的items会被移除出step t+1中的candidate set。
• Beam Search：在前t steps中选中的items会在第step t+1中的candidate set中移除
• SSP：当planing时，我们会根据每步\(V^*(s_t)\)的上界，从step T到step 1进行计划（plan），并在每一step保持最优的T个items作为step的候选。当进行选择时，我们会从step 1到step N做出选择。特别的，我们会选择最优的一个item并从剩余step的候选中同步移除它

从表7的详细结果看出，我们可以发现：尽管折中会伤害理想效果，但SSP仍要胜过Greedy和Beam Search。

表7

5.5.3 SSP plan with Noise

由于存在一些在offline environment和online enviroment间的一个gap，它会做出predicted ctr以及quit probability 在离线不会绝对等价于real value online，我们会在部署MDP-SSP online之前，引入一个noise 实验的集合。

实验会以如下方式开展：我们会在CTR上添加随机噪声（random noises），通过离线环境给出quit probability。假设：noise \(e \sim U(a, b)\)，其中U(a, b)是一个均匀分布，我们会定义 \(a = -0.02m, b = 0.02m\)，其中m是一个从0到10的整数范围。我们会根据具有noise的value进行计划，并计算具有real value的最终收益。结果如图6所示，水平轴表示noise，例如：U(a, b)中的b，竖直轴是revenue，例如：cumulative clicks。

图6

从图6中，我们可以发现，尽管SSP会对noise更敏感，它的效果会好于Greedy和Beam Search。它表明：考虑上quit probability会在IPV问题上扮演着一个十分重要的角色。

SSP Planner：在线评估

对于在线评估，我们会在真实电商APP中部署SSP和Greedy策略。对于进一步对比，我们会做一个实验，它具有quit model，它不会引入MIL，该策略命名为\(SSP_{no \_ MIL}\)。三种策略会在线运行相同的流量各一周，表8展示了结果：

• 对于cumulative clicks，quit brobability在sequential recommendations中不会被忽略，详见SSP和Greedy
• quit probability的accuracy会直接影响着结果，详见：SSP和\(SSP_{no\_MIL}\)

表8

6.结论

略

参考

• 1.https://arxiv.org/pdf/2006.04520.pdf

华为在《AutoFIS: Automatic Feature Interaction Selection in Factorization Models for Click-Through Rate Prediction》提出了AutoFIS

摘要

学习特征交叉对于CTR预估来说非常重要。在大多数已经存在的深度学习模型中，特征交叉是人工设计或者简单枚举的。然而，枚举所有的特征交叉会带来很大的内容和计算开销。更糟的是，无用的交叉会在训练过程中引入噪声和复杂度[28]。在本工作中，我们提出了一个two-stage算法称为Automiaitc Feature Interaction Selection（AutoFIS）。AutoFIS可以为FM自动标识出重要的特征交叉，有一定计算开销。在search stage中，通过替代搜索候选特征交叉的离散集合，我们会通过引入结构参数将从离线变成连续进行选择。通过在结构参数上实现一个regularized optimizer，模型可以在训练过程中自动标识并移除冗余的特征交叉。在retrain stage，我们会保存结构参数，将它们作为一个attention unit来进一步增强效果。在三个大规模数据集上的离线实验表明，AutoFIS可以极大提升多个FM-based模型。AutoFIS被成功部署在Huawei APP store推荐服务中，10天数据看，可以在CTR/CVR上分别提升20.3%和20.1%。

3.方法

在本节中，我们描述了提出的AutoFIS，它可以自动选择在FM中重要的特征交叉。

3.1 FM（Base Model）

首先，我们定义FM：

定义3.1: FM是这样的模型：来自不同features的多个embeddings的交叉会通过一些内积/neural network的操作来建模成一个实数（real number）。

图1

我们采用FM、DeepFM、IPNN作为实例来公式化我们的算法，并探索在多个数据集上的效果。图1表示了：FM、DeepFM和IPNN模型的结构。FM包含了一个feature embedding layer和一个feature interaction layer。除了这两个layers外，DeepFM和IPNN模型会包含一个额外的layer：MLP layer。在DeepFM和IPNN间的不同之处是：feature interaction layer和MLP layer会在DeepFM中并列工作，而在IPNN中则是顺序的。

在后续章节上，我们将简要描述FM中的feature embedding layer和feature interaction layer。为了与DeepFM和IPNN模型一起工作，MLP layer和output layer也会被公式化。接着，我们提出的AutoFIS是如何在feature interaction layers上工作的会被详述，例如：基于结构参数选择重要的特征交叉。

Feature Embedding Layer。在大多数CTR预估任务中，数据会以multi-field categorical的形式采集。一个典型的数据预处理，会通过one-hot或multi-hot encoding会将每个数据样本转化成一个高维稀疏向量。当一个field是多变量时，会被表示成一个multi-hot encoding vector。一个数据样本可以表示成：

\[x = [x_1, x_2, \cdots, x_m]\]

其中，m是fields数目，\(x_i\)是第i个field的one-hot或multi-hot encoding vector。一个feature embedding layer被用于将一个encoding vector转换成一个低维向量：

\[e_i = V_i x_i\]

…(1)

其中：\(V_i \in R^{d \times n}\)是一个matrix，\(n_i\)是在第i个field中的。

• 如果\(x_i\)是一个具有第j个元素\(x_i[j]=1\)的one-hot vector，那么\(x_i\)的representation是\(V_i^j\)
• 如果\(x_i\)是一个multi-hot vector，对于\(j=i_1, i_2, \cdots, i_k\)，具有\(x_i[j]=1\)，那么这些元素的embeddings是\(\lbrace V_i^{i1}, V_i^{i2}, \cdots, V_i^{ik}\rbrace\)，接着\(x_i\)的representation是这些embeddings的sum或average。

feature embedding layer的output是多个embedding vectors的concatenation：

\[E= [e_1, e_2, \cdots, e_m]\]

Feature Interction Layer

在将features转换成低维空间之后，feature interactions可以使用feature interaction layer被建模到这样的一个空间。首先，pairwise feature interactions的inner product会被计算如下：

\[[\langle e_1, e_2 \rangle, \langlee_1, e_3 \rangle, \cdots, \langle e_{m-1}, e_m \rangle]\]

…(2)

其中：

• \(e_i\)是第i个field的feature embedding，
• \(\langle \cdot, \cdot \langle\)是两个vectors的inner product

在该layer中的pair-wise feature interactions的数目是\(C_m^2\)：

\[l_{fm} = \langle w, x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>i}^m \langle e_i, e_j \rangle\]

…(3)

这里，所有的feature interactions会等贡献地被传给下一layer。如第1节和第4节，不是所有的特征交叉都有相等的预见性，无效交叉可能会影响效果退化。因此，我们提出了AutoFIS算法来有效选择重要的特征交叉。

为了研究我们的方法是否可以被用来识别重要的高阶交叉，我们将具有3rd-order交叉（例如：三个fields的组合）的feature interaction layer定义为：

\[l_{rm}^{3rd} = \langle w, x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>i}^m \langlee_i, e_j \rangle + \sum\limits_{i=1}^m \sum\limits_{j<i}^m \sum\limits_{t>j}^m \langle e_i, e_j, e_t \rangle\]

…(4)

MLP Layer。MLP Layer会包含许多具有activation functions的FC layers，它会学到features的关系和组合。一个这样的layer的output是：

\[a^{(l+1)} = relu(W^{(l)} a^{(l)} + b^{(l)})\]

…(5)

其中：

• \(a^{(l)}, W^{(l)}, b^{(l)}\)分别是第l层的input、model weight、bias。
• \(relu(z) =max(0, z)\)：为Activation
• \(a^{(0)}\)是input layer
• \(MLP(a^{(0)}) = a^{(h)}\)：其中h是MLP layer MLP的depth

Output Layer

FM模型没有MLP layer，并直接将feature interaction layer与prediction layer连接：

\[\hat{y}_{FM} = sigmoid(l_{fm}) = \frac{1}{1 + exp(-l_{fm})}\]

…(6)

其中，\(\hat{y}_{FM}\)是predicted CTR。

DeepFM会将feature interaction layer与MLP layers并行进行组合：

\[\hat{y}_{DeepFM} = sigmoid(l_{fm} + MLP(E))\]

…(7)

当在IPNN中时，MLP layer会跟在feature interaction layer之后：

\[\hat{y}_{IPNN} = sigmoid(MLP([E, l_{fm}]))\]

…(8)

注意，IPNN的MLP layer可以对不同feature interactions进行reweighting，来捕获它们的相对重要性。这也是为啥IPNN要比FM和DeepFM具有更高能力的原因。然而，有了IPNN的公式，我们不能检索对应于每个feature interaction的相对贡献的准确值。因此，在IPNN中的feature interactions会带来噪声和计算开销。下面，我们展示了AutoFIS是如何改进IPNN的。

Objective Function

FM、DeepFM、IPNN会共享相同的objective function，例如：最小化predicted values和labels间的cross-entropy：

\[L(y, \hat{y}_M) = - y log\hat{y}_M - (1-y) log(1 - \hat{y}_M)\]

…(9)

其中：

• \(y \in \lbrace 0, 1 \rbrace\)是label
• \(\hat{y}_M \in [0, 1]\)是y=1的预估概率。

3.2 AutoFIS

AutoFIS会自动选择有用的特征交叉，它可以补用于任意FM模型的feature interaction layer。在本节中，我们会详述它是如何工作的。AutoFIS可以分成两个阶段：search stage和re-train stage。在search stage中，AutoFIS会检测有用的特征交叉；而在re-train stage中，具有选中的feature interactions的模型会被重新训练。

Search Stage

为了让该算法更好地呈现，我们引入gate操作来控制是否选择一个feature interaction：一个open gate对应于选中一个feature interaction，而一个closed gate会导致一个dropped interaction。对应于所有二阶特征交叉的gates的总数是：\(C_m^2\)。以brute-force方式寻找open gates的最优集合非常挑战，因为我们会面对一个非常大的搜索空间（\(2^{C_m^2}\)）。在本工作中，我们会从一个不同的视角去处理该问题：作为在open gates的一个离散集合上进行搜索的替代，我们会通过引入结构参数\(\alpha\)可以选择连续方式，以便每个feature interaction的相对重要性可以通过梯度下降进行学习。提出的AutoFIS的总览如图2所示。

图2 AutoFIS总览

这种通过梯度学习的结构选择scheme受DARTS【20】的启发，在DARTS中，目标是从在CNN结构中的候选操作集合中选择一个操作（operation）。

特别说明的是，我们会将在FM中的interaction layer重新公式化为：

\[l_{AutoFIS} = \langle w, x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>i}^m \alpha_{(i,j)} \langle e_i, e_j \rangle\]

…(10)

其中：

\(\alpha = \lbrace \alpha_{(1,2)}, \cdots, \alpha_{(m-1,m)} \rbrace\)是结构参数。在AutoFIS的search stage，\(\alpha_{(i,j)}\)值会以这样的方式学习：\(\alpha_{(i,j)}\)可以表示每个feature interaction到final prediction的相对贡献。接着，我们可以通过设置那些不重要的gates关闭决定每个feature interaction的gate状态。

Batch Normalization

从整体neural network的角度看，一个feature interaction的贡献可以通过\(\alpha_{(i,j)} \cdot \langle e_i, e_j \rangle\)来进行测算。相同的贡献可以通过对该项rescaling成\((\frac{\alpha_{(i,j)}}{\eta}) \cdot (\eta \cdot \langle e_i, e_j\rangle )\)，其中\(\eta\)是一个真实值。

由于\(\langle e_i, e_j \rangle\)的值可以与\(\alpha_{(i,j)}\)联合学习，它们的scale组合会导致对\(\alpha_{(i,j)}\)的不稳定估计，比如：\(\alpha_{(i,j)}\)不再表示\(<e_i, e_j>\)相对重要性。为了解决该问题，我们在\(\langle e_i, e_j \rangle\)上使用Batch Normalization来取除它的scale问题。BN已经作为一个标准方法被用来训练DNN来达成快速收敛和更好的效果。

原始的BN会使用一个mini-batch的统计信息来对activated output进行归一化。特别的，

\[\hat{z} = \frac{z_{in} - \mu_B}{\sqrt{\sigma_B^2 + \epsilon}} \\ z_{out} = \theta \cdot \hat{z} + \beta\]

…(11)

其中：

• \(z_{in}, \hat{z}, \hat{z_{out}}\)是input、BN的归一化值、BN的output值
• \(\mu_B, \sigma_B\)是\(z_{in}\)在一个mini-batch B上的均值和标准差；
• \(\theta, \beta\)分别是BN的trainable scale和shift参数
• \(\epsilon\)是数值稳定性的一个常数

为了得到\(\alpha_{(i,j)}\)的稳定估计，我们分别将scale和shift参数设置为1和0. 在每个feature interaction \(<e_i, e_j>\)上的BN操作可以被计算成：

\[\langle e_i, e_j\rangle_{BN} = \frac{\langle e_i, e_j\rangle - \mu_B(\langle e_i, e_j \rangle)}{\sqrt{\sigma^2_B(\langle e_i, e_j\rangle)} + \epsilon}\]

…(12)

其中：

• \(\mu_B\)和\(\sigma_B\)是在mini-batch B中的\(\langle e_i, e_j \rangle\)的均值和标准差。

GRDA Optimizer

GRDA optimizer的目标是：获得一个sparse DNN。为了在每个gradident step t上使用数据\(Z_t\)来更新\(\alpha\)，我们使用以下的等式：

\[\alpha_{t+1} = \underset{argmin}{\alpha} \lbrace \alpha^T(-\alpha_0 + \gamma \sum\limits_{i=0}^t \nabla L(\alpha_t; Z_{i+1}) + g(t, \gamma) \| \alpha \|_1 + 1/2\| \alpha \|_2^2 \rbrace\]

其中：

• \(g(t,\gamma) = c\gamma^{1/2} (t\gamma)^u\),
• \(\gamma\)是learning rate
• c和\(\mu\)是可调超参数，用于对accuracy和sparsity做tradeoff

在搜索阶段，我们使用GRDA optimizer来学习结构参数\(\alpha\)，并获得一个sparse解。这些不重要的特征交叉（例如：具有零值的\(\alpha_{i,j}\)值）会被自动丢弃。其它参数可以通过Adam optimzier进行学习。

One-level优化

为了在AutoFIS的search stage上学习结构参数\(\alpha_{i,j}\)，我们提出\(\alpha\)与其它所有network权重v进行联合最优化（比如：等式3中的w，和等式5中的\(W^{(l)}\)和\(b^{(l)}\)）。这与DARTS不同。DARTS会将\(\alpha\)看成是更高lebel的决策变量，将network weights看成是更低level的变量，接着使用一个bi-level最优化算法来对它们进行最优化。在DARTS中，假设：当只有network weights被合理学习时，以使\(\alpha\)可以“做出合适决策”，模型可以选择operation。在AutoFIS公式的上下文中，这意味着，我们可以决定：在network weights被合理训练时，一个gate是否会是open或closed，这会导致我们会回到对\(2^{C_m^2}\)个模型完全训练的问题。为了避免这个问题，DARTS提出，只在一个gradient descent step上对network weights的最优值进行逼近，并迭代训练\(\alpha\)和\(v\)。

我们会讨论这种近似的不准确性可能对效果有损。因此，通过对bi-level optimization进行替代，我们提出使用one-level optimization对\(\alpha\)和\(v\)进行联合优化。特别的，参数\(\alpha\)和\(v\)会与gradient descent一起更新：

\[\partial_v L_{train}(v_{t-1}, \alpha_{t-1}) = \partial_{\alpha} L_{train}(v_{t-1}, \alpha_{t-1})\]

…(14)

在该setting中，\(\alpha\)和\(v\)可以探索它们的设计空间直到收敛，\(\alpha\)可以被学习用来作为独立feature interactions的贡献。在第4节中，我们展示了one-level optimization要优于two-level optimization。

Re-train Stage

在search stage的训练之后，一些不重要的交叉会根据架构参数\(\alpha^*\)被自动抛弃。我们使用\(G_{(i,j)}\)来表示特征交叉\(\langle e_i, e_j \rangle\)的gate status，当\(\alpha_{(i,j)}^*=0\)时会\(G_{(i,j)}\)将并设置为0；否则，我们设置为1. 在retrain阶段，这些不重要的feature interactions的gate status被确定永久关闭。

在移除这些不重要的交叉后，我们会使用在模型中保存的\(\alpha\)来对新模型进行retrain。特别的，我们会将等式(3)的feature interaction layer进行替换：

\[l_{rm}^{re} = \langle w,x \rangle + \sum\limits_{i=1}^m \sum\limits_{j>1}^m \alpha_{(i,j)} G_{(i,j)} \langle e_i, e_j \rangle\]

…(15)

注意，这里\(\alpha_{(i,j)}\)不再作为一个indicator来决定是否一个交叉该包含在模型内（比如：在search stage）。作为替代，它会当成是结构的一个attention unit来学习保持特征交叉的相对重要性。在该stage中，我们不必选择feature interactions。因此，所有参数会通过Adam optimizaer来学习。

4.实验

略

• 1.https://arxiv.org/pdf/2003.11235.pdf

阿里在《Personalized Re-ranking for Recommendation》中提出了PRM算法：

1.介绍

ranking对推荐系统很重要。由ranking算法给出的ranked list的quality对于用户满意度以及推荐系统收益来说具有很大影响。大量的ranking算法被提出来优化ranking的效果。在推荐系统中，ranking通常只考虑user-item pair features，并没有考虑在list中的其它items，特别是那些在旁边的items【8，35】。尽管pairwise和listwise的L2R方法尝试通过将item-pair或者item-list作为input来解决该问题，他们只关注于最优化loss function以便更好地利用labels，例如：click-through data。他们不会显式建模在feature space中的items间的相互影响。

一些工作【1，34，37】尝试显式建模在items间的相互影响，来对之前ranking算法给出的initial list进行refine，这被称为“re-ranking”。主要思想是，通过对intra-item patterns进行编码到feature space的方式来构建scoring function。进行feature vectors编码的SOTA方法有：RNN-based（比如：GlobalRerank，或者DLCM）。他们会将initial list来顺序feed给RNN-based结构，在每个time step输出encoded vector。然而，RNN-based方法对于建模在list间的交互来说具有局限性。之前编码的item的特征信息会随着编码距离降低。受transformer的启发，我们提出使用transformer架构来建模items间的相互影响。transformer结构使用self-attention机制，其中：任意两个items可以直接相互交叉，不会随着编码距离降级。同时，由于并行化，Transformer的encoding过程要比RNN-based方法更高效。

除了items间的交互外，对于交叉的个性化encoding功能，也要在推荐系统中的re-ranking中被考虑。推荐系统的re-ranking是user-specific的，依赖于用户偏好和意图。对于一个对价格很敏感的用户，“price”特征间的交叉对于re-ranking model来说很重要。例如，当用户关于价格对比时，具有不同价格的相似items趋向于在list中会更集中。当用户没有明显的购买意图时，在推荐列表中的items趋向于更分散。因此，我们会引入一个个性化模块到Transformer结构来表示在item交互上的用户偏好和意图。在list中的items与user间的交互，可以在PRM中被并行捕获。

该paper的主要贡献如下：

• 问题。我们提出一个个性化re-ranking问题：并且首次显式地引入个性化信息到reranking任务中。实验结果表明，在list representation中引入用户表示（users’ representation）的效果。
• 模型: 我们使用Transformer并且带上个性化embedding来计算initial input ranking list的representations，并输出re-ranking score。对比起RNN-based方法，self-attention机制允许我们以一个高效地方式来建模user-specific在任意两个items间的交互影响。
• 评估：我们在离线和在线实验上，展示了我们的方法极大地胜过SOTA方法。online A/B测试表明了它能达到更高的CTR和收益。

2.相关工作

略

3.Reranking模型公式化

在本节中，我们首先给出一些关于l2r的前置知识，以及推荐系统的reranking方法。接着，我们将问题进行公式化来求解。概念如表1所示。

Learning to Rank（也称为LTR）方法在IR和推荐的排序中被广泛使用，用来生成一个有序列表。LTR方法会基于items的feature vector学习一个全局的scoring function。有了这个全局函数，LTR方法会通过对candidate set中的每个item进行打分输出一个有序列表。该全局scoring function通常通过最小化以下的loss function L来学到：

\[L = \sum\limits_{r \in R} l (\lbrace y_i, P(y_i | x_i;\theta) | i \in I_r \rbrace)\]

…(1)

这里：

• R：推荐的所有用户请求的集合。
• \(I_r\)：对于请求 \(r \in R\)的items的候选集合。
• \(x_i\)：表示item i的feature space。
• \(P(y_i \mid x_i; \theta)\)是在给定参数\(\theta\)的ranking model对item i的预估点击概率。
• l是由\(y_i\)和\(P(y_i \mid x_i; \theta)\)计算的loss

然而，\(x_i\)对于学习一个好的scoring function来说是不够的。我们发现：对推荐系统来说ranking需要考虑以下额外信息：

• a) 在item pairs间的相互影响（mutual influence）
• b) users和items间的交叉（interaction）

对于请求r，在item pairs间的相互影响，可以通过由给定的已经存在的LTR model中，直接从intial list \(S_r = [i_1, i_2, \cdots, i_n]\)中直接学到。【1，37，2，3】提出了更好的方法使用item-pairs间的互信息（mutual information）。然而，少量工作则会考虑在users和items间的交叉。在本paper中，我们引入一个个性化matrix PV来学习user-specific encoding function，它可以建模在item-pairs间的个性化相互影响。该模型的loss function可以公式化为等式2.

\[L = \sum\limits_{r \in R} l (\lbrace y_i, P(y_i | X, PV; \hat{\theta}) | i \in S_r \rbrace)\]

…(2)

其中：

• \(S_r\)：是在给定前面的ranking model时的intial list
• \(\hat{\theta}\)：是我们的re-ranking model的参数
• X：是在list中所有items的fearture matrix

4.个性化reranking model

在本节中，我们首先给定：我们提出的个性化reranking Model(PRM)的一个总览。接着，我们引入：我们模型的每个组件。

4.1 模型结构

PRM的结构如图1所示。模型包含了三个部分：

• input layer
• encoding layer
• output layer

它会将由前面ranking模型生成的关于items的initial list作为input，并输出一个rerank后的list。

图1 PRM（个性化reranking model）的详细网络结构以及它的子模块

4.2 Input layer

input layer的目标是：为在intial list中所有items准备综合representations，并将它feed到encoding layer。首先，我们有：

• 一个固定长度的intial sequential list \(S=[i_1, i_2, \cdots, i_n]\)，它由之前的ranking方法给出。
• 有一个raw feature matrix \(X \in R^{n \times d_{feature}}\)，与之前的ranking方法相同。X中的每一行表示对于每个item \(i \in S\)的raw feature vector \(x_i\)

个性化向量（Personalized Vector（PV））

两个items的feature vectors的encoding可以建模两者间的相互影响，但这种influences对于用户来说影响有多深是未知的。需要学习一个user-specific encoding function。尽管整个initial list的representation可以部分影响用户的偏好，但对于一个强大的personalized encoding function来说是不够的。如图1(b)所示，我们：

将raw feature matrix \(X \in R^{n \times d_{feature}}\)与一个个性化矩阵\(PV \in R^{d \times d_{pv}}\)进行concat，以便获得intermediate embedding矩阵\(E' \in R^{n \times (d_{feature} + d_{pv})}\)，如等式（3）所示。PV通过一个预训练模型生成，它会在以下章节中介绍。PV的效果增益会在evaluation部分介绍。

\[E' = \left[\begin{array} x_{i_1}; pv_{i_1} \\ x_{i_2}; pv_{i_2} \\ \cdots \\ x_{i_n}; pv_{i_n} \end{array} \right]\]

…(3)

Position Embedding(PE)

为了利用在initial list中的顺序信息，我们会注入一个position embedding： \(PE \in R^{n \times (d_{feature} + d_{pv}})\)到input embedding中。接着，使用等式(4)计算encoding layer的embedding matrix。在本paper中，一个可学习的PE会被使用，我们发现它的效果要比【24】中使用的固定的position embedding效果稍好些。

\[E'' = \left[ \begin{array} x_{i_1}; pv_{i_1} \\ x_{i_2}; pv_{i_2} \\ \cdots \\ x_{i_n}; pv_{i_n} \end{array} \right] + \left[\begin{array} pe_{i_1} \\ pe_{i_2} \\ \cdots \\ pe_{i_n} \end{array} \right]\]

…(4)

最后，我们会使用一个简单的feed-forward network来将feature matrix \(E'' \in R^{n \times (d_{feature} + d_{pv})}\)转换成\(E \in R^{n \times d}\)，其中d是encoding layer的每个input vector的隐维度（latent dimensionality）。E可以公式化为等式5。

\[E = EW^E + b^E\]

…(5)

其中:

• \(W^E \in R^{(d_{feature} + d_{pv}) \times d}\)是投影矩阵
• \(b^E\)是d维向量

4.3 Encoding Layer

图1(a)中的encoding layer的目标是：将item-pairs的相互影响与其它额外信息进行集成，包括：用户偏好、initial list S的ranking顺序等。为了达到该目标，我们采用Transformer-like encoder，因为Transformer已经被证明在许多NLP任务中很有效，特别的是在机器翻译中具有强大的encoding和decoding能力。Transformer中的self-attention机制非常适合在我们的re-ranking任务中，因为它会直接建模任意两个items间的相互影响，并且忽略它们间的实际距离。没有了距离衰减（distance decay），Transformer可以捕获那些在initial list中相互相隔较远的items间的更多交互。如图1(b)所示，我们的encoding module包含了Transformer encoder的\(N_x\)个块。每个块（图1(a)）包含了一个attention layer和一个Feed-Froward Network（FFN） layer。

Attention Layer

attention function如等式（6）所示：

\[Attention(Q, K, V) = softmax(\frac{QK^T}{\sqrt{d}}) V\]

…（6）

其中，矩阵Q, K, V分别表示queries、keys和values。d是矩阵K的维度，为了避免inner product 的大值。softmax被用来将inner product 的值转化成value vector V的adding weight。在本paper中，我们使用self-attention，其中：Q, K, V来自相同的矩阵进行投影。

为了建模复杂的mutual influences，我们使用multi-head attention，如等式7所示：

\[S' = MH(E) = Concat(head_1, \cdots, head_h) W^0 \\ head_i = Attention(EW^Q, EW^K, EW^V)\]

…(7)

其中：

• \(W^Q, W^K, W^V \in R^{d \times d}\)。\(W^O \in R^{hd \times d_{model}}\)是投影矩阵。h是headers的数目。h的不同值的影响，会在下部分进行研究

Feed-Forward Network

该position-wise FFN主要是使用非线性和在input vectors的不同维度间的交叉来增强模型

对Encoding Layer进行Stacking

在position-wise FFN后，这里我们接着使用attention module作为Transformer encoder的一个block。通过将多个blocks进行stacking，我们可以获得更复杂和高阶的mutual information

4.4 Output Layer

output layer的function主要目的是，为在图1(b)中的每个item \(i=i_1, \cdots, i_n\)生成一个score（标记为Score(i)）。我们会使用一个linear layer，后接一个softmax layer来实现。softmax layer的输出为：每个item的点击概率，它被标记为\(P(y_i \mid X, PV; \hat{\theta})\)。我们使用\(P(y_i \mid X, PV; \hat{\theta})\)作为Score(i)来对items在one-step中进行rerank。Score(i)公式为：

\[Score(i) = P(y_i \mid X, PV; \hat{\theta}) = softmax(F^{N_x} W^F + b^F), b \in S_r\]

…(8)

其中：

• \(F^{(N_x)}\)是Transformer encoder的\(N_x\)块（blocks）的output。
• \(W^F\)是可学习的投影矩阵
• \(b^F\)是bias项
• n：在initial list中的items数目

在训练过程中，我们会使用click through数据作为label，并最小化以下的loss function：

\[L = - \sum\limits_{r \in R} \sum\limits_{i \in S_r} y_i log(p(y_i | X, PV; \hat{\theta}))\]

…(9)

4.5 Personalized Module

在本节中，我们会介绍该方法来计算个性化矩阵（personlized matrix: PV），它表示user与items间的交互。直接方法是：使用PRM model以end-to-end的方式通过reranking loss来学习PV。然而，如第3节所示，reranking task任务是：对之前的ranking方法的output进行refine。在reranking task上学到的task-specific representation会缺乏用户的泛化偏好（generic perferences）。因此，我们会利用一个pre-trained neural network来生产用户的personalized embeddings PV，它接着会被用于PRM model中的额外features。预训练的neural network从平台的整体click-through logs学习到。图1(c)展示了在我们paper中使用的per-trained model的结构。sigmoid layer会输出user u在item i在给定用户所有行为历史\(H_u\)以及用户的side information下的点击概率\((P(y_i \mid H_u, u; \theta'))\)。用户的side information包括：gender、age、purchasing level等。该model的loss通过一个point-wise cross entropy function来计算，如等式（4）所示：

\[L = \sum\limits_{i \in D} (y_i log (P(y_i | H_u, u; \theta'))) + (1 - y_i) log(1 - P(y_i | H_u, u; \theta'))\]

…(10)

其中:

• D是user u在该平台上展示的items集合。
• \(\theta'\)：是pre-trained model的参数矩阵
• \(y_i\)是在item i上的label（点 or 不点）

受[13]的启发，我们在sigmoid layer之前采用hidden vector作为personalized vector \(pv_i\)（图1(c)）feed给我们的PRM model。

图1(c)展示了pre-trained model的一个可能架构，其它模型(如：FM、DeepFM、DCN等)也可以作为选择用于生成PV。

5.实验

5.3 Evaluation Metrics

对于离线评估，我们使用Precision和MAP来对比不同的方法。更特别的，我们使用:

• Precision@5，Precision@10作为precision
• MAP@5，MAP@10, MAP@30作为MAP

。。。

略

• 1.https://arxiv.org/pdf/1904.06813.pdf

在《Learning a Deep Listwise Context Model for Ranking Refinement》提出了DLCM.

4.DEEP LISTWISE CONTEXT MODE

在该paper中，我们提出了一个DNN模型，它会包含local ranking context到LTR框架中。该模型的整体思想是：使用一个RNN网络为每个query对应的top retrieved documents进行编码，并且基于编码后的local context model来对ranked list进行refine。我们将该模型称为DLCM（Deep Listwise Context Model）。

使用DLCM的document ranking的pipeline包括三个steps。

• 第一个step是：一个初始检索（initial retrieval），它使用标准的LTR算法。在该step中，每个query-document pair(q, d)是可以被转化成一个feature vector \(x_{(q,d)}\)以及一个size=n的ranked list \(R_q^n\)，它会基于一个全局的ranking function f为query q生成。
• 第二个step是：一个编码过程，它使用一个GRU的RNN对top retrieved documents的feature vectors \(X_q^n\)进行编码。RNN会一个接一个地方式从最低位置到最高位置获取documents，并生成一个latent vector \(s_n\)来表示编码后的local context model： \(I(R_q^n, X_q^n)\)。
• 第三个step是：一个re-ranking过程，其中，top documents会使用一个local ranking function \(\phi\)（它基于\(s_n\)以及RNN的hidden outputs \(o\)）来进行rerank。DLCM的整体结构如图1所示。

图1

4.1 Input Document Representations

第3节所示，大多数L2R算法使用一个feature vector来表示每个query-document pair。在我们提出的框架中，DLCM使用相同的feature vectors。我们在模型输出侧不会包括其它额外的features。

直接将原始的feature vectors进行feed到我们的模型中，并不是使用NN的完整能力的最好方法。另一方法，原始features的维度会受限，并使用低维表示会限制neural encoders的表达能力。另一方面，高级feature抽象对于neural models的健壮性来说是有益的，特别是当原始input features有噪声时。受Wide&Deep模型的启发，我们使用一个two-step方法来获得DLCM的高级input表示。我们首先使用一个two-layer feed-forward network来学习原始features的抽象：

\[z_i^{(0)} = x_{(q,d_i)} \\ z_i^{(l)} = elu(W_z^{(l-1)} \cdot z_i^{(l-1)} + b_z^{(l-1)}, l=1, 2)\]

其中：

• \(W_z^{(l)}\)和\(b_z^{(l)}\)是在第l个layer的weight matrix和bias。
• elu是非线性激活函数，当x>=0时，它等于x；否则为 \(e^x - 1\)。我们接着将\(z_i^{(2)}\)与原始的feature vector \(x_{(qq, d_i)}\)进行concatenate来形成一个新的input vector \(x_{(q, d_i)}'\)

假设：\(\alpha\)和\(\beta\)是\(x_{(q,d_i)}\)和\(z_i^{(2)}\)的维度。当\(beta\)等于零时，我们不会进行区分，因为\(x'(q,d_i)\)可以被缩减为\(x_{(q, d_i)}\)。

4.2 编码Listwise Local Context

给定由一个global ranking function f给出的top n个检索结果，以及它们的feature vectors \(X_q^n = \lbrace x_{(q,d_i)} \mid d_i \in R_q^n\rbrace\)，DLCM中的local context model I会使用一个RNN来实现。RNN是一种deep network，在顺序数据建模中常用。一个标准的RNN包括一个输入序列，一个输出序列，以及一个state vector。由于我们会一个接一个地feed input实例（每个实例会使用一个feature vector进行表示），RNN会根据当前input进行更新它的state vector，并在每个step生成一个新的output vector。最终的state vector可以被看成是一个关于所有信息的编码（会feed到该网络中）。

在DLCM中，我们使用GRU的RNN。GRU network是一个由Cho[10]提出的技术，用于解决RNN中的梯度消失问题。它的基本思想是：使用一个update gate和一个reset gate来控制网络的states的更新。正式的，假设\(x_t \in R^{\alpha}\)是在第t个step的input vector，\(\alpha\)是\(x_t\)的维度。output vector（也是在GRU中的activation vector）\(o_t \in R^{\alpha}\)，network state \(s_t \in R^{\alpha}\)会被计算为：

\[o_t = (1-u_t) \odot o_{t-1} + u_t \odot s_t \\ u_t = \sigma(W_u^x \cdot x_t + W_u^s \cdot o_{t-1}) \\ s_t = tanh(W^x \cdot x_t + W^s \cdot (r_t \odot o_{t-1})) \\ r_t = \sigma(W_r^x \cdot x_t + W_r^s \cdot o_{t-1})\]

…(4)

其中：

• \(\odot\)是element-wise product
• \(\sigma(x) = \frac{1}{1+e^{-x}}\)是一个sigmoid function
• \(u_t \in R^{\alpha}\)是update gate
• \(r_t \in R^{\alpha}\)是reset gate
• 所有的weight矩阵\(W^x, W^s, W_u^x, W_u^s, W_r^x, W_r^s \in R^{\alpha \times \alpha}\)是在训练过程中学到的
• encoded context 模型\(I(R_q^n, X_q^n)\)是final network state \(s_n\)

在DLCM中使用GRU的RNN天然满足一个local context model的两个需求。RNN的inputs是一个vectors序列，它可以是从LTR系统中是scalar features。由于RNN会天然地学习将current input与在network state中编码的previous input进行结合，我们不会需要人工定义heuristics来建模local ranking context。同时，RNN的结果使得它能够捕获在encoding process中的位置效果。当我们使用input data一个接一个地输入到network中时，current input会趋向于比之前的inputs具有对当前network state更多的影响。

由于我们会输入排完序的top结果（从最低到最高position），在高位置的documents会对最终network state具有更多的影响。

图一的单向RNN部分，另一个可选方法是，我们也会测试双向RNN。尽管它被认为是在NLP中的高级能力，我们观察到在检索实验中没有提升。这表明，反方向的编码信息没啥用。实际上，如果我们只使用反向方式的uni-directional RNN，DLCM的效果会更差。

4.3 Local context的reranking

DLCM的最后一个step是，，它通过使用一个local ranking function \(\phi\)对documents进行排序来生成一个新的ranked list。当预测一个ranking score时，function \(\phi\)同时会考虑RNN的hidden outputs，以及关于local ranking context的编码后的latent表示：假设：\(o_{n+1-i}\)是document \(d_i \in R_q^n\)的output表示，我们将local ranking function \(\phi\)定义为：

\[\phi(o_{n+1-i, s_n}) = v_{\phi} \cdot ( o_{n+1-i} \cdot tanh(W_{\phi}\cdot s_n + b_{\phi}))\]

…(5)

其中：

• \(W_{\phi} \in R^{\alpha \times k \times \alpha}, b_{\phi} \in R^{\alpha \times k}, V_{\phi} \in R^k\)，
• k是超参数，它控制着hidden units的数目。

我们的local ranking function的定义是，与RNN中广泛使用的attention function相似。在许多机器学习应用中（例如：机器翻译），一个RNN decoder需要对不同steps的input data的不同部分进行attention。例如，我们需要关注一个句子的不同部分，当我们生成一个接一个的翻译时。attention function常被用于计算在input data上的一个attention分布，并生成一个attention vector来指导一个RNN的decode过程。在DLCM中，我们直接使用\(\phi\)的output值来对input文档进行排序。

我们尝试其它设置：比如：将o使用x进行替代，并使用一个3-layer的FFN来实现\(\phi\)，或者一个neural tensor network。然而，它们的效果会更差，或者不明显，因此，我们只汇报了等式5.

4.4 Loss function

为了训练DLCM，我们实现了两个已存在的listwise loss function（ListMLE【36】和SoftRank【34】），也提出了一个新的listwise loss function称为Attention Rank。

ListMLE是一个listwise loss function，它会将LTR公式化成一个最小化likelihood loss的问题。它将ranking看成是一个顺序选择过程，并将概率定义为：从\(\phi_{m}^n=\lbrace d_j \mid j \in [m, n] \rbrace\)选择文档：

\[P(d_i | \pi_m^n) = \frac{e^{S_i}}{\sum_{j=m}^n e^{S_j}}\]

其中：

• \(S_i\)和\(S_j\)是\(d_i\)的\(d_j\)的ranking scores

如果我们从一个ranked list \(R_q^n\)的top开始进行选择，并在每个step后从candidate set中移除选中的document，在给定ranking scores S下，我们具有\(R_q^n\)的概率：

\[P(R_q^n | S) = \prod_{i=1}^n P(d_i | \pi_i^n) = \prod_{i=1}^n \frac{e^{S_i}}{\sum_{j=1}^n e^{S_j}}\]

假设：\(R_q^*\)是对于query q最可能的ranked list，接着ListMLE loss会定义为：在给定S下\(R_q^*\)的log似然的较小者。

SoftRank：

首先在[34]中提出，是一个listwise loss function，它直接最优化关于信息检索（比如：NDCG）的ranking metrics。假设：\(S_i\)和\(S_j\)是document \(d_i\)和\(d_j\)对于query \(q_i\)的ranking scores。SoftRank function假设：文档\(d_i\)的”real” score \(S_i'\)从一个Gaussian分布中抽出，定义为：\(N(S_i, \sigma_s^2)\)，其中，\(\sigma_s\)是一个共享平滑variance。给定该假设，\(d_i\)高于\(d_j\)的概率为：

\[\pi_{ij} = Pr(S_i' - S_j' > 0) = \int_0^{\inf} N(S | S_i - S_j, 2 \sigma_s^2) dS\]

…(8)

其中，\(P_j^{(1)}(r)\)是\(d_j\)的初始rank分布，当\(d_j\)是在ranked list中的唯一文档时，接着\(p_j^{(i)}(r)\)会在添加第i个文档后被计算：

\[p_j^{(i)}(r) = p_j^{(i-1)}(r-1) \pi_{ij} + p_j^{(i-1)}(r)(1 - \pi_{ij})\]

其中，有了最终的rank分布\(p_j^{(n)}(r)\)以及所有n个documents的label，我们可以计算在每个rank上的期望相关值，并定义一个loss function作为一个期望metric score的减法。

在本paper中，我们使用NDCG作为SoftRank的objective metric。在SoftRank中的唯一超参数是共享的smoothing variance \(\sigma_s\)。我们尝试0.1, 1.0，并观察对应的效果没有变化。这里我们统一使用0.1.

Attention Rank

受attention-based NN的影响，我们提出了一个Attention Rank loss function，它会对一个ranked list的评估公式化为一个attention分配过程。假设：在文档中包含的信息是相互排斥的，一个ranked list的总信息增益是每个文档的增益的累积。如果我们进一步假设：

一个文档的相关评估得分，直接受它的信息增益的影响，最好的策略是：在有限时间内，通过分配更多attention给最好的结果、更低的attention给fair结果、以及不给不相关的结果分配attention，来最大化它的总信息增益。Attention Rank的思想是：使用我们模型的ranking scores来计算一个attention分布，并使用attention策略（通过相关评估计算）来计算它。假设：relevance label \(y_{(q,d_i)}\)表示对于query q的文档\(d_i\)的信息增益。在一个ranked list \(R_q^n\)上的最好的attention分配策略定义如下：

\[a_i^y = \frac{\phi(y(q,d_i))}{\sum\limits_{d_k \in R_q^n} \phi(y(q, d_k))}\]

其中：

• \(\phi(x)\)是一个修正的指数函数，当x>0时为\(e^x\)，否则为0.

相似的，我们会计算我们的模型\(a_i^S\)的attention分布，它使用ranking score \(S_i\)，并使用cross entropy来计算attention策略与最好的attention策略间的loss：

\[l(R_q^n) = - \sum\limits_{d_i \in R_q^n} (a_i^y log(a_i^S) + (1-a_i^y)log(1-a_i^S))\]

…(11)

Attention Rank不会直接预测文档的relevance labels，但会关注在ranked list中的每个结果的relative importance。因为，一个在不相关结果中的list中的fair document，会比在好结果中的list中的一个好文档会接受更多的attention。由于它会基于ranked lists来计算ranking loss，Attention Rank是一个listwise function，它不是一个 pointwise function。Attention Rank的主要优化是：它的简单和高效。通过使用修正的指数函数\(\phi(x)\)，我们可以显式分配更多的精力来最优化在训练过程中的高相关结果。使用Attention Rank的DLCM的训练，要比使用ListMLE和SoftRank的更快2倍和20倍。因而，它可以直接被用于无偏的LTR框架中。

• 1.https://dl.acm.org/doi/pdf/10.1145/3209978.3209985

阿里在《Diversified Interactive Recommendation with Implicit Feedback》提出了D2CB。

摘要

交互式推荐系统（Interactive recommender systems）允许用户与推荐系统间的交互，吸引了许多研究关注。之前的许多方法主要关注于优化推荐的accuracy。然而，他们通常会忽略推荐结果的多样性（diversity），因而，通常会产生不令人满意的用户体验。在本paper中，我们提出了一个新的diversified recommendation model，命名为“Diversified Contextual Combinatorial Bandit (DC2B)”，它会使用用户的隐式反馈来进行交互推荐。特别的，DC2B会在推荐过程中采用DPP来提升推荐结果的多样性。为了学到模型参数，提出了一个Thompson sampling类型的算法，它基于 variational Bayesian inference来实现。另外，理论上的regret分析也提供了对DC2B的效果保证。在真实数据集上的大量实验表明，提出的方法可以对推荐的accuracy和diversity进行balance。

介绍

常见的推荐系统通常是以非交互的方式开发，并从日志中的用户行为数据中进行学习。这种系统的一个缺点是，不能及时捕获用户偏好的变化。因而发展为允许交互的交互推荐系统。在文献中，contextual bandit learning已经表明是交互推荐问题的一个满意解法(Li et al. 2010; Zhao, Zhang, and Wang 2013; Tang et al. 2015; Wang, Wu, and Wang 2017; Qi et al. 2018)。在这些方法中，推荐系统给一个用户顺序推荐items的一个集合，并采用用户的立即反馈（immediate feedback）来提升推荐策略（recommendation policy）.

实际上，用户的隐式反馈（implicit feedback）（例如：点击历史）通常会用来构建推荐系统，由于隐式反馈是以用户为主心的（user centric），可以很容易收集到。然而，implicit feedback通常会带来偏差信号，会让推荐问题变得更具挑战。这种bias来自到：implicit feedback只能捕捉正向用户偏好（例如：观察到的user-item交互），所有的负向用户偏好会错过。尽管在该user和一个item间的无交互（non-interaction）通常会看成是负向用户偏好，但它不能显式表示用户不喜欢该item，因为无交互可能是因为该item没有被曝光给用户所造成。

另外，之前的交互式推荐方法主要关注于优化推荐accuracy。他们通常会忽略其它推荐结果的重要特性，例如：推荐的item set的多样性。因此，通过这些方法生成的推荐列表的items会非常相似，推荐结果可能只cover了很小部分的items。这会造成次优的用户体验，因而会减小推荐系统的商业价值。直观上，要达到高accuracy和diversity是非常具有挑战的。只关注diversity的方法会让accuracy受损。由于对于不流行items缺少数据，在推荐中考虑这些items会导致在推荐效果上的减弱（Adomavicius 2011）。因此，多样化推荐方法的主要目标是，在accuracy和diversity间的tradeoff进行最优化，这通常指的是“accuracy-diversity dilemma”。

在本paper中，我们提出了一种新的bandit learning framework，它基于用户的implicit feedback进行交互式推荐系统，它会尝试在推荐结果中对accuracy和diversity间努力达到一个balance。为了解决由implicit feedback引起的bias问题，我们会从两方面建模用户与推荐系统间的交互：

• i) 多样化Item的曝光（Exposure）：推荐系统会选择一个相关并且多样的items集合曝光给用户
• ii) User Engagement：用户实际中会与一些曝光的items进行engage（比如：点击一些items）

特别的，DPP会用来选择一个多样性items集合曝光给用户，考虑上所选中items集合的qualities和diversity。DPP的优点是，显式建模一个item set被选中给用户的概率，因而可以帮助解决由implicit feedback造成的bias问题。另外，items的contextual features可以用来建模在推荐items上观察到的user engagements。

总结下，在本paper中的主要贡献如下：

• 1) 我们提出了一种新的bandit learning方法：DC2B，来提升交互式推荐系统的推荐多样性
• 2) 我们提出了在Thompson sampling framework的variantional Bayesian inference来学习模型参数
• 3) 我们也为DC2B提供了理论性regret analysis
• 4) 实验表明有效

2.相关工作

交互式推荐

3.问题公式化

我们采用contextual bandit来构建多样性交互推荐系统。该推荐系统被看成是一个agent，每个item被看成是一个arm。假设：

• \(A = \lbrace a_i \rbrace_{i=1}^N\)表示是N arms的集合（例如：items）

我们假设：每个arm \(a_i\)具有一个contextual feature vector \(x_i\):

\[x_i \in R^{1 \times d}\]

它会对side information进行归纳，所有arms的features X表示为：

\[X \in R^{N \times d}\]

在每次尝试时，推荐agent会首先从A中选择一个关于arms的子集S，同时考虑上被选中arms的qualities和diversity。S通常称为是一个“super arm”。这里，我们经验性将一个arm \(a_i\)的quality \(r_i\)定义如下：

\[r_i = exp(\theta x_i^T)\]

…(1)

其中：

• \(\theta\)是bandit参数，它描述了用户偏好（user preferences）

选中的super arm S的diversity可以通过intra-list distance metric（Zhang&Hurley 2008）进行measure。一旦一个多样性的super arm S根据一个policy \(\pi\)被选中并展示给用户，该用户在展示items的engagements（例如：在items上的点击）会用来作为推荐agent的rewards，用来最优化它的推荐policy。通过与用户交互，推荐agent的目标是：调整它的super arm选择策略来最大化它的随时间的累积回报（cumulative reward over time）。

3.1 多样化Item曝光

DPP是一个优雅的概率模型，它可以建模在许多机器学习问题中的多样性。在本文中，我们利用DPP来建模一个相关且多样的super arm S的选择概率。正式的，一个在候选arms A集合上的DPP P，是一个在\(2^A\)上的概率测量，它可以描述A的所有子集的概率。如果P在空集合\(\emptyset\)上分配非零概率，则存在一个真实、半正定kernal matrix \(L \in R^{N \times N}\)，这样，super arm S的概率\(p(S)\)可以定义如下：

\[p(S) = \frac{det(L_{[S]})}{det(L+I)}\]

…(2)

其中：

• I是单位矩阵
• \(L_{[S]} \equiv [L_{ij}]_{a_i, a_j \in S}\)是L的子矩阵。如(Kulesza 2012)所示，L可以被写成一个Gram matrix，\(L = V V^T\)，其中V的行是表示arms的vectors。

根据【Chen 2018; wilhelm 2018】，我们经验性地设置 \(V_i = (r_i)^{\alpha} x_i\)，其中\(\alpha > 0\)是一个参数，它控制着item qualities的影响。接着，L的元素被定义成：\(L_{ij} = (r_i r_j)^{\alpha} x_i x_j^T\)。如果\(x_i\)是归一化的，例如：\(\| x_i \|_2 = 1\)，则在\(a_i\)和\(a_j\)间的Cosine相似度可以通过\(C_{ij} = x_i x_j^T\)进行计算。我们可以将L重写为：

\[L = Diag \lbrace exp(\alpha \bar{r})\rbrace \cdot C \cdot Diag \lbrace exp(\alpha \bar{r}) \rbrace\]

…(3)

其中，\(Diag(\bar{r})\)是一个对角矩阵，它的第i个对角元素是：\(\bar{r}_i = \theta x_i^T\)，C是相似度矩阵。接着，super arm S的log概率为：

\[log p(S) \propto 2 \alpha \sum\limits_{a_i \in S} \bar{r}_i + log det(C_{[S]})\]

…(4)

其中，当在S中的arms的features是正交时，最后一项是最大的，它可以帮助提升推荐的diversity【Chen 2018】。另外，等式(4)也表明参数\(\alpha\)可以帮助对推荐的相关性和多样性进行balance。

3.2 User Engagements

用户在展示items上的engagements通过它的implicit feedback（比如：在items上的点击）进行表示，它通常可以通过一个二元变量的集合进行描述。如果用户在arm \(a_i\)上具有engagments，则我们设置为\(y_i=1\)；否则设\(y_i=0\)。一旦一个arm \(a_i \in S\)已经展示给用户，我们假设：用户在\(a_i\)上的engagements只由它的quality来决定。从而，观测到的user在\(a_i\)上的engagements（例如：\(y_i=1\)）的概率\(p_i\)可以定义如下：

\[p_i \triangleq \rho (\theta x_i^T) = \frac{exp(\theta x_i^T)}{1+exp(\theta x_i^T)} = \frac{r_i}{1 + r_i}\]

…(5)

这可以被解释成：当一个arm \(a_i\)被提供给该用户时，在该arm或一个virtual arm \(a_0\)上的user engages具有一个相关分（relevance score）1。基于该假设，我们可以定义observed user engagements的联合概率 \(Y = \lbrace y_i \mid a_i \in S \rbrace\)如下：

\[p(Y, S, \theta) = p(\theta) p(S | \theta) p(Y | S, \theta) \\ = p(\theta) \frac{det(L_{[S]})}{det(L+I)} \prod\limits_{a_i \in S} p_i^{y_i} (1 - p_i)^{1-y_i}\]

…(6)

其中：

• \(p(\theta)\)会预先分配给bandit参数。另外，我们假设\(p(\theta)\)服从一个高斯分布\(N(m, \Sigma)\)，其中\(m, \Sigma\)是有边界的。该假设通常会被用于实际情况中。

4.参数推断（Parameter Inference）

一旦一个新的observation (S, Y)提供，我们会采用variational Bayesian inference【Blei 2017】来开发一个闭合形式近似\(\theta\)的后验概率。根据(Blei 2017)，\(\theta\)的近似后验\(q(\theta)\)可以表示成：

\[log q^*(\theta) = E_{param \neq \theta} [log \ p(Y, S, \theta)] + const\]

再者，基于线性代数的知识，我们有：

\[det(L_{[S]}) = \prod_{a_i \in S ^{r_i^{2\alpha}}} det(X_{[S]} X_{[S]}^T)\]

以及

\[det(L+I) = exp(tr(log(L+I)))\]

接着，我们可以有以下的似然函数：

\[log p(Y, S | \theta) = \sum_{a_i \in S} (\phi_i + 2\alpha log r_i) + log det(X_{[S]} X_{[S]}^T) - \sum\limits_{j=1}^N log (1 + r_j^{2 \alpha} x_j x_j^T)\]

…(7)

其中：

• \[\phi_i = y_i log p_i + (1+y_i) log(1 + p_i)\]

在等式(7)中，似然函数是一个logistic function，它与在\(\theta\)上的高斯先验是共轭的。为了解决该问题，以下在logistic function上的高斯下界（lower bound）被用来近似似然（jaakkola 1997）：

\[\rho(x) \geq \rho(\epsilon) e^{\frac{x-\epsilon}{2} - \lambda (\epsilon)(x^2 - \epsilon^2)}\]

其中：

• \[\lambda(\epsilon) = \frac{1}{2 \epsilon} ( \rho(\epsilon) - \frac{1}{2})\]
• \(\epsilon\)是一个辅助变量，需要进行调整使得bound在\(x = \pm \epsilon\)附近。

再者，通过假设：

• \[\| \theta \|_2 \leq A\]
• \[\| x_j \|_2 \leq B\]

我们有：

\[- log[1 + exp(2 \alpha \theta x_j^T) x_j x_j^T] \geq - exp(2 \alpha \theta x_j^T) x_j x_j^T \geq -exp(2 \alpha A B) B^2\]

由于我们假设m和\(\Sigma\)是有界的，因而推断\(\theta\)是有界是合理的。通过对\(x_j\)进行归一化，我们可以做出\(x_j\)也是有界的。接着，我们有似然函数的下界，如等式（7）所示：

\[log p(Y, S | \theta) \geq const. + \sum\limits_{a_i \in S} [\frac{2y_i - 1 + 4 \alpha) \theta x_i^T}{2} - \lambda(\epsilon_i)(\theta (x_i^T x_i) \theta^T) + \phi(\epsilon_i)]\]

…(8)

其中，\(\phi(\epsilon_i) = log \rho(\epsilon_i) - \frac{\epsilon_i}{2} + \lambda(\epsilon_i) \epsilon_i^2\)。\(\theta\)的最优variational分布如下：

\[log q^*(\theta) \approx E[ log h(\theta, \epsilon)] + E[log p(\theta)] + const\]

由于模型的共轭性，我们可以知道：\(q(\theta)\)会遵循高斯分布\(N(m_{post}, \Sigma_{post})\)，其中均值和方差如下：

\[\sum_{post}^{-1} = \sum^{-1} + 2 \sum\limits_{a_i \in S} \lambda(\epsilon_i) x_i^T x_i \\ m_{post} = \sum_{post} [\sum^{-1} m + \sum\limits{a_i \in S}(y_i + 2 \alpha - \frac{1}{2}) x_i]\]

…(9)(10)

由于没有先验分配给\(\epsilon_i\)，\(\epsilon_i\)的最优值可以通过最大化期望似然函数来生成：\(l(\epsilon_i) = E[log p(Y, S \mid \theta, \epsilon_i)])\)。对\(l(\epsilon_i)\)根据\(\epsilon_i\)进行求导并将它设置为0，可以获得\(\epsilon_i\)的最优值：

\[\epsilon_i = \sqrt(x_i (\sum_{post} + m_{post}^T m_{post}) x_i^T)\]

…(11)

我们采用Thompson sampling(TS)更新模型参数来对exploration和exploitation进行balance。TS算法的详情见算法1.

算法1

在标准TS方法中，它需要从模型参数\(\theta\)中进行抽样。由于logistic似然函数与高斯先验不共轭，我们提出从近似后验分布\(q(\theta)\)中进行抽样。一旦完成了\(\theta\)的抽样，DPP kernel matrix L就固定了，我们可以通过最大化\(f_{\theta}(S) = \prod_{a_i \in S} p_i det(L_{\mid S \mid})\)来选择最优的super arm S。我们采用fast gready MAP inference算法（Chen 2018）来获得最优的super arm。greedy算法的详情如算法2所示。

算法2

4.Regret分析

我们考虑一个模型，它涉及：

• 一个actions的集合S
• 一个函数集合 \(F = \lbrace f_{\theta}: S \rightarrow \mid \theta \in \Theta \rbrace\)，它通过一个随机变量\(\theta\)进行索引，它属于一个索引集合\(\Theta\)。

在每个时间t时，一个随机子集\(S_t \subseteq S\)会被展示，一个action \(S_t \in S_t\)会被选中，之后会获得reward \(R_t\)。我们定义了reward function如下：

\[E[R_t] \triangleq f_{\theta}(S_t) = \prod_{a_i \in S_t} p_i det(L_{[S_t]}) = \prod_{a_i \in S_t} p_i r_i^{2\alpha} det(X_{[S_t]} X_{[S_t]}^T\]

并且定义了在第t次试验时的reward：

\[R_t = f_{\theta}(S_t) + \epsilon_t\]

因此，我们有\(E[\epsilon_t] = 0\)。另外，我们假设：

\[\forall f_{\theta} \in F, \forall S_t \in S, f_{\theta} (S_t) \in [0, C]\]

对于一个推荐policy \(\pi\)，我们可以定义Bayesian risk bound如下：

\[Regret(T, \pi) = \sum\limits_{t=1}^T E[max_{s \in S_t} f_{\theta}(s) - f_{\theta}(S_t)]\]

…(12)

为了执行regret analysis，我们首先介绍以下两个辅助定理，它根据【Russo 2014】的观点9和观点10被证明。不同之处是，这种方法的变量是一个arms集合\(S_t\)，它替代了单个arm a，证明相似，出于篇幅此处省去。我们根据定理7设置\(\sigma=1\)，它表明\(f_{\theta}\)满足假设2.

引理1: 对于所有\(T \in N, \alpha_0 > 0, \sigma \leq 1/2T\)，有：

\[Regret(T, \pi^{TS}) \leq 4 \sqrt{dim_M(F, T^{-1}) \beta_T^*(F, \alpha_0, \sigma)T} + 1 + [dim_M(F, T^{-1}) + 1] C\]

其中：

。。。

5.实验

实验设定

数据集：该实验会在以下数据集上执行：Movielens-100K, Movielens-1M, Anime.

Setup和Metrics

对于交互式推荐方法，最合适的是使用一个具有实时的用户交互的在线实验setting进行评估。然而，通常在学术研究中不可能具有这样的environment。因而，根据（Zhao 2017），我们假设，用户在items上的ratings记录在我们的实验数据集中，它们是无偏 的，这些记录可以被 看成是无偏的用户反馈（unbiased user feedback）。无偏离线评估策略（Li 2011）被 用于评估推荐方法。在实验中，我们随机将每个dataset划分成两个非重合的集合，通过随机采样了80%的用户用于训练，并使用剩余20%的用户用于测试。接着，我们会基于训练数据采用BPRMF来学习items的embeddings，它会被用来做为arms的contextual features。经验性的，我们会将item embeddings的维度设置为10。由于用户通常对少量的top-ranked推荐items感兴趣，我们会采用Precision@N来评估推荐accuracy（SHi 2014），通过在 \(\lfloor N/ \mid S \mid \rfloor\)次试验（trials）的推荐items进行聚合，并计算precision。特别的，N设置 为10， 30， 50。我们也会评估每个方法在所有推荐实验 中的平均推荐diversity，通过ILD metric（intra-list distance）：

\[\frac{1}{T} \sum\limits_{t=1}^T [ \frac{2}{|S_t| (|S_t| -1)} \sum\limits_{a_i \in S_t} \sum\limits_{a_j \in S_{t,i \neq j} } ( 1- sim_{ij})]\]

其中：

• \(S_t\)：是在trail t的推荐item set
• \(\mid S_t \mid\)：表示\(S_t\)的size
• T：是推荐实验的总数目
• \(sim_{ij}\)：表示在\(a_i\)和\(a_j\)中的相似度

由于一个item可能会属于多个item类目，我们会通过使用两个items的类目的jaccard相似度来定义成item相似度\(sim_{ij}\)。对于这些accuracy和diversity metrics来说，我们首先会计算每个user的value，接着会上报在所有users上的平均值。根据CHeng 2017，我们会采用F-measure来评估不同方法在accuracy和diversity的tradeoff上的表现，其中：

\[F-measure = 2 * accuracy * diversity / (accuracy + diversity)\]

由于训练users与测试users是非重合的，为warm-start settings设计的推荐算法并不适合作为baselines。在本paper中，我们会将DC2B与以下推荐方法进行对比：

• 1）LogRank：在该方法中，我们会定义每个arm \(a_i\)的quality score为：\(r_i = 1/(1+ exp(-\bar{u}x_i^T))\)，其中：\(\bar{u}\)是从训练数据中学到user embeddings的平均。接着，会选中\(\mid S_t \mid\)个具有最高quality scores的arms作为一个super arm \(S_t\)来进行第t次trail的推荐
• 2) MMR：该方法采用MMR策略来提升推荐多样性。在第t次trial时，该方法会顺序选择一个具有最大MMR score的arm到\(S_t\)中。MMR score的定义如下：\(\bar{r}_i = \alpha r_i - \frac{(1-\alpha)}{\mid S_t \mid} \sum_{j \in S_t} sim(x_i, x_j)\)，其中：\(r_i\)是在LogRank方法中定义的arm quality，\(sim(x_i, x_j)\)是在\(x_i\)和\(x_j\)间的cosine相似度
• 3）e-greedy：该方法会以\(\epsilon\)的概率随机添加一个可提供的arm到\(S_t\)中，以\(1-\epsilon\)的概率添加具有最高quality的arm到\(S_t\)中，item quality的定义与LogRank方法相同
• 4) \(DPP^{map}\)（CHen 2018）：该非交互式方法会使用DPP来提升推荐多样性。item quanlity的定义与在LogRank中的相同
• 5) \(C^2 UCB\)（Qin 2014）：该方法会集成LinUCB框架，使用一个entropy regularizer来为交互式推荐提升diversity
• 6) EC-Bandit（Qi 2018）：该bandit方法基于Thompson sampling框架，并为使用用户隐式负反馈的交互式推荐进行开发。在本方法中，用户需要与 recommender交互 \(S_t\)次，并在第t次实验生成推荐item集合

对于所有方法，我们经验性地将每次实验的\(S_t\)的size设置为10。一个validation set会从training data中采用来选择超参数。每个方法的最佳参数设置如下。

• MMR的\(\alpha\)会设置为0.9
• e-greedy的\(\epsilon\)会设置为0.1
• \(DPP^{map}\)的\(\theta\)会设置为0.6
• 在\(C^2UCB\)中，我们会设置\(\lambda_0 = 100, \lambda=0.1, \sigma = 1\)
• 在EC-Bandit中，我们会设置参数\(\lambda=1\)
• 对于DC2B，我们经验性地将\(alpha=3, \lambda=1\)

效果对比

不同算法的推荐的accuracy和diversity如表2所示。在表2中，提出的DC2B方法，在ML-1M和Anime datasets上会达到最佳的推荐accuracy（例如：Precision@N），在ML-100K dataset上达到第二好的accuracy。例如，在Anime dataset上，DC2B的效果要极大胜过C2UCB和EC-Bandit：59.35%和107.11%，。。。

略

参考

• 1.https://ojs.aaai.org/index.php/AAAI/article/view/5931