阿里在《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

摘要

隐式反馈（比如：用户点击）尽管在在线信息服务中非常丰富，但在用户评估系统输出方面并没有提供实质帮助。如果没有合理地进行建模，会误导模型估计，特别是在bandit learning setting中（feedback会即时获取）。在本工作中，我们会执行使用implicit feedback的contextual bandit learning，它会建模feedback作为用户结果查看（result examination）、以及相关评估（relavance evaluation）的一部分。由于用户的查看行为是观察不到的，我们会引入隐变量（latent variables）来建模它。我们会在变分贝叶斯推断（variational Bayesian inference）之上执行Thompson sampling来进行arm selection以及模型更新。我们算法的upper regert bound analysis表明了在一个bandit setting中从implicit feedback中学习的可行性。

1.介绍

contextual bandit算法为现代信息服务系统提供了一种有效解决方案，可以自适应地发现items和users间的良好匹配。这类算法会使用关于user和item的side information顺序选择items提供服务给用户，并能基于用户立即反馈（immediate user feedback）来调节选择策略（selection policy），从而最大化用户的long-term满意度。他们被广泛部署在实际系统中：内容推荐【20，5，26】和展示广告【6，22】。

然而，user feedback的最多形式是implicit feedback（比如：clicks），而它是有偏的，并且对于系统输出的用户评估是不完整的。例如：一个用户跳过一个推荐item，并不因为是他不喜欢该item，有可能是因为他没有查看（examine）那个展示位置（例如：position bias）。不幸的是，在contextual bandit应用中一个常见惯例是：简单地将未点击（no click）看成是负反馈（negative feedback）的一种形式。这会对模型更新引入不一致性（inconsistency），由于跳过的items并非真正不相关，因而它不可避免地会导致随时间的bandit算法的次优结果。

在本工作中，我们会关注使用user click feedback来学习contextual bandits、并建模这样的implicit feedback，作为用户结果查看（result examination）和相关度评估（relevance judgment）的一个部分。 查看假设(Examination hypothesis)【8】在点击建模型上是一个基础假设，会假设：在一个系统上的一个用户点击的返回结果，当且仅当结果被用户查看（examination）时，它与在该时刻的用户信息是相关的。由于一个用户的查看行为是不可观测的（unobserved），我们会建模它作为一个隐变量，并在一个概率模型中实现该查看假设。我们会通过在相应的contextual features上的logistic functions中定义结果查看（result examination）和相关评判（relevance judgement）的条件概率。为了执行模型更新，我们会采用一个变分贝叶斯方法来开发一个闭式（closed form）近似即时模型参数的后验分布。 该近似也会为在bandit learning中使用Thompson sampling策略进行arm selection来铺路。我们的有限时间分析表明，尽管在参数估计中由于引入隐式变量增加了复杂度，我们的Thompson sampling policy会基于真实后验 ，从而保证能达到一个具有高概率的sub-linear Bayesian regert。我们也会演示，基于近似后验的Thompson sampling的regret是良性有界的（well-bounded）. 另外，我们会证明：当某人在点击反馈中建模结果查看（result examination）失败时，一个线性递增的regret是可能的，因为在负反馈中模型不能区分查看驱动的跳过（examination driven skips）还是不相关驱动的跳过（relevance driven skips）。

我们会在中国的MOOC个性化教育平台上测试该算法。为了在该平台上个性化学生的学习体验，当学生正观察视频时，我们会在课程视频顶部以banner的形式推荐类似测试的问题（quiz-like quenstions）。该算法需要决定，在一个视频中在哪里向一个特定用户展示哪个问题。如果学生觉得展示的问题对他理解课程有用，他可能会点击该banner并阅读问题以及更多关于该问题的在线内容。因此，我们的目标是在选中问题上最大化CTR。该应用有多个特性，会放大bias以及点击反馈的不完整性。

• 首先，基于用户体验的考虑，为了最小化讨厌度，一个banner的展示时间会限定在几秒内。
• 第二，由于该feature对于该平台来说是新引入的，许多用户可能不会意识到：他们会在该问题上点击，并且阅读更多相关内容。

作为结果，在一个问题上没有点击，并不能表示不相关。我们会在4个月周期内测试该算法，其中：总共有69个问题会用到该算法上来选择超过20个主要的视频，超过10w的学习观看session。基于无偏离线评估策略，对比起标准的contextual bandits，我们的算法会达到一个8.9%的CTR提升，它不会建模用户的查看行为（examination behavior）。

2.相关工作

略

3.问题设定

我们考虑一个contextual bandit问题，它具有有限但可能较大的arms。我们将：

• arm set：表示为A
• candidate arms子集：在每个trial t=1, …, T上，learner会观察到candidate arms的子集\(A_t \subset A\)，其中，每个arm a与一个context vector \(x^a\)有关，会对arm的side information进行归纳。
• 一旦arm \(a_t \in A_t\)根据一些policy \(\pi\)被选中后，对应的隐式二元反馈\(C_{a_t}\) （例如：user click），会由learner给出作为reward。

learner的目标是：判断它的arm selection策略来最大化它随时间的累积收益（cumulative reward）。使得该问题唯一和挑战的是：\(C_{a_t}\)不会真正影响用户关于选中arm \(a_t\)的评估。基于查看假设【13，8】:

• 当\(C_{a_t}=1\)时，选中的\(a_t\)必须与用户在time t需要的信息相关；
• 但当\(C_{a_t}=0\)时，\(a_t\)必须相关，但用户不会查看它

不幸的是，产生的查看条件对learner来说是不可观察的。

我们会通过一个二元隐变量\(E_{a_t}\)来建模一个用户的结果查看（result examination），并假设：arm a的context vector \(x_t^a\)可以被分解成：

\[(x_{C,t}^a, x_{E,t}^a)\]

• 其中：\(x_{C,t}^a\)和\(x_{E,t}^a\)分别是\(d_C\)和\(d_E\)。

相应的，用户的结果查看和相关判断决策被假设成：通过一个\((x_{C,t}^a, x_{E,t}^a)\)猜想、以及相应的bandit参数为\(\theta^* = (\theta_C^*, \theta_E^*)\)来进行管理。在本文其余部分，当没有二义性引入时，我们会drop掉index a以简化概念。作为结果，我们对在arm \(a_t\)的一个observed click \(C_t\)上做出以下的生成假设：

\[\begin{align} P(C_t = 1 | E_t = 0, x_{C,t}) & = 0 \\ P(C_t = 1 | E_t = 1, x_{C,t}) & = \rho(x_{C,t}^T \theta_C^*) \\ P(E_t = 1 | x_{E,t}) & = \rho(x_{E,t}^T \theta_E^*) \end{align}\]

其中：

• \[\rho(x) = \frac{1}{1 + e^{-x}}\]

基于该假设，我们有：

\[E[C_t \mid x_t] = \rho(x_{C,t}^T \theta_C^*) \rho(x_{E,t}^T \theta_E^*)\]

作为结果，观察到的click feedback \(C_t\)是来自该生成过程的一个样本。我们定义\(f_{\theta}(x) := E[C \mid x, \theta] = \rho(x_C^T \theta_C) \rho(x_E^T \theta_E)\)。到达time T一个policy \(\pi\)的accumulated regret的定义如下：

\[Regret(T, \pi, \theta^*) = \sum\limits_{t=1}^T \underset{\alpha \in A_t}{max} \ f_{\theta^*} (x^a) - f_{\theta^*}(x^{a_t})\]

其中：

• \(x^{a_t} := (x_C^{a_t}, x_E^{a_t})\)是arm \(a_t \in A_t\)的context vector，该arm会在time t时基于历史 \(H_t := \lbrace (A_i, x_i, C_i) \rbrace_{i=1}^{t-1}\)由policy \(\pi\) 中。

Bayesian regret的定义为\(E[Regret(T, \pi, \theta^*)]\)，其中采用的期望根据在\(\theta^*\)上的先验分布采用的，它可以被写成：

\[BayesRegret(T, \pi) = \sum\limits_{t=1}^T E[\underset{a \in A_t}{max} f_{\theta^*}(x^a) - f_{\theta^*}(x^{a_t})]\]

在我们的在线学习环境中，我们的目标是：发现policy \(\pi\)，并最小化在T上的accumulated regret。

4.算法

learner需要基于从click feedback \(\lbrace x_i, C_i \rbrace_{i=1}^t\)获得的随时间的互交，估计bandit参数 \(\theta_C^*\)和\(\theta_E^*\)。理想情况下，该估计可以根据bandit model参数通过最大化data likelihood来获得。然而，在我们的bandit learning setting中查看（examination）的加入作为一个隐变量，对于参数估计和arm selection来说会造成严重挑战。由于相应最优化问题的非凸性，传统的最小二乘估计、极大似然估计可以被轻易获取，更不必说计算效率。更糟的是，两个流行的bandit learning范式，UCB principle和Thompson sampling，都需要一个关于bandit参数及不确定性的精准估计。在本节中，我们提出一个有效的新解法来解决这两个挑战，它会利用variational Bayesian inference技术来近似学习即时参数，同时桥接参数估计（parameter estimaiton）和(arm selection policy)设计。

4.1 Variational Bayesian进行参数估计

为了完成在第3节中定义的生成过程，我们进一步假设\(\theta_C\)和\(\theta_E\)分别遵循高斯分布 \(N(\hat{\theta}_C, \sum_C)\)以及\(N(\hat{\theta}_E, \sum_E)\)。当一个新获得的observation \((x_C, x_E, C)\)变得可提供时，我们会对开发一个闭式近似后验感兴趣。通过在log space中使用Bayes’ rule，我们有：

\[\begin{align} log P(\theta_C, \theta_E | x_C, x_E, C) \\ &= log P(C | \theta_C, \theta_E, x_C, x_E) + log P(\theta_C, \theta_E) + log const \\ &= C log \rho(x_C^T \theta_C) \rho(x_E^T \theta_E) + (1 - C) log(1 - \rho(x_C^T \theta_C) \rho(x_E^T \theta_E)) \\ &= - \frac{1}{2} (\theta_C - \hat{\theta}_C)^T \sum_C^{-1} (\theta_C - \hat{\theta}_C) - \frac{1}{2} (\theta_E - \hat{\theta}_E)^T \sum_E^{-1} (\theta_E - \hat{\theta}_E) + log const \end{align}\]

关键思想是：我们会为似然函数开发一个\(\theta_C\)和\(\theta_E\)的二次型（quadratic form）的variational lower bound。由于 \(log \rho(x) - \frac{x}{2}\)的convexity，对应于\(x^2\)，以及logx的Jensen’s不等式，所需形式的一个lower bound是可以达到的。当C=1时，通过等式(16)，我们有：

\[l_{C=1}(x_C, x_E, \theta) := log( \rho(x_C^T \theta_C) \rho(x_E^T \theta_E)) \geq g(x_C^T\theta, \epsilon_C) + g(x_E^T \theta, \epsilon_E)\]

…(1)

其中：

• \(g(x, \epsilon) := \frac{x}{2} - \frac{\epsilon}{2} + log \rho(\epsilon) - \lambda(\epsilon)(x^2 - \epsilon^2), \lambda(\epsilon) = \frac{tanh \frac{epsilon}{2}}{4 \epsilon}, x, \epsilon \in R\)。更特别的是，\(g(x, \epsilon)\)是一个度为2的对应于x的多项式。当C=0时，通过等式（17），我们有：

\[l_{C=0} (x_C, x_E, \theta) := log( 1-\rho(x_C^T \theta_C) \rho(x_E^T \theta_E)) \\ \geq H(q) + qg(-x_C^T \theta, \epsilon) + qg(x_E^T \theta, \epsilon_{E,1}) + (1 - q) g(-x_E^T\theta, \epsilon_{E,2})\]

…(2)

其中，\(H(q) := - qlog q - (1 - q) log(1-q)\)。一旦在quadratic form中的lower bound确定后，我们可以使用一个Gaussian分布来近似我们的target后验，它的均值和covariance matrix由以下等式确定：

\[\begin{align} \sum_{C, post}^{-1} & = \sum_C^{-1} + 2q ^{1-C} \lambda (\epsilon) x_C x_C^T \\ \hat{\theta}_{C, post} & = \sum_{C,post} (\sum_{C}^{-1} \hat{\theta}_C + \frac{1}{2} (-q)^{1-C} x_C) \\ \sum_{E,post}^{-1} & = \sum_{E}^{-1} + 2 \lambda(\epsilon_E) x_E x_E^T \\ \hat{\theta}_{E,post} & = \sum_{E,post} (\sum_E^{-1} \hat{\theta}_E + \frac{1}{2}(2q-1)^{1-C} x_E) \end{align}\]

…(3)(4)(5)(6)

其中，下标“post”表示在高斯分布中的参数，它逼近期望的后验。连续的观测可以被顺序包含到近似后验。还剩一件事件需要决策，例如：变化参数\((\epsilon_C, \epsilon_E, q)\)的选择。一个选这些值的常用准则是，在observations上的似然是最大化的，与【12】相似的选择，我们会选择这些变分参数的闭式更新公式：

\[\epsilon_C = \sqrt{E_{\theta_C} [x_C^T \theta_C]^2} \\ \epsilon_E = \sqrt{E_{\theta_E} [x_E^T \theta_E]^2} \\ q = \frac{exp(g(x_C^T \theta_C, \epsilon_C) + g(x_E^T\theta_E, \epsilon_E) - g(-x_E^T \theta_E, \epsilon_E))}{ 1 + exp(g(x_C^T \theta_C, \epsilon_C) + g(x_E^T \theta_E, \epsilon_E) - g(-x_E^T \theta_E, \epsilon_E))}\]

其中，所有期望都在近似后验下采用。经验上，我们发现，近似后验和变分参数的迭代式更新收敛相当快，以致于它通常只需要少量迭代就可以获得一个满意的局部最大值。

4.2 使用近似lower bound的Thompson sampling

Thompson sampling, 通常称为“概率匹配（probability matching）”，会被广泛用于bandit learning中来平衡exploration和exploitation，并且它展示了极大的经验效率。Thompson sampling需要一个模型参数的分布来采样。在标准的Thompson sampling中，我们需要从模型参数的真实后验中进行采样。但由于logistic regression不会具有一个共轭先验（conjugate prior），在我们的问题中定义的模型不会具有一个准确的后验。我们决定，根据从等式（3）到等式（6）从近似后验中抽样。之后，我们会表明：这是一个非常紧凑的后验近似。一旦\((\bar{\theta}_C, \bar{\theta}_E)\)的采样完成，我们可以选择相应的arm \(a_t \in A_t\)，它会最大化\(\rho(x_C^T \bar{\theta}_C) \rho(x_E^T \bar{\theta}_E\)。我们将生成的bandit算法命名为examination-click bandit，或者E-C bandit，如算法1所示。

算法1 E-C Bandit

5.Regret Analysis

略

6.实验

略

7.结论

• 1.https://keg.cs.tsinghua.edu.cn/jietang/publications/NIPS18-Qi-et-al-Bandit-Learning-with-Implicit-Feedback.pdf

huawei在《Personalized Re-ranking for Improving Diversity in Live Recommender Systems》提出了personalized DPP方法。

摘要

2.reranking模型

2.1 DPP-based re-ranking

如【13】，DPP-based model要比MMR-based model要更有效且高效。因此，我们选择研究如何在我们的推荐系统中使用DPP-based reranking model。在本节，我们会讲述DPP-based reranking model，并讨论它的局限性，这激发我们在一下节中使用personalized DPP-based reranking模型。

我们将[13, 14, 20]的一些关键结果进行归纳，让读者更好地理解该模型。在一个关于items的集合（\(M=1,2,\cdots, \mid M \mid\)）上的一个点过程（point process）P，是一个在M的幂集（powerset）的概率分布。也就是说，\(\forall Y \subseteq M\)，P会分配一个概率分布\(P(Y)\)，使得\(\sum_{Y \subseteq M} P(Y)=1\)。如【20】中所述，我们的目标是：从整个item set M中选择一个合适的relevant和diverse的k个subset，使得集合满足\(max_{Y:\mid Y \mid = k, Y \subseteq M} P(Y)\)。再者，P可以通过一个\(M \times M\)的半正定kernal matrix L进行紧密参数化（compactly parameterzied），比如：\(P(Y) \propto det(L_Y)\)，其中\(det(L)\)是矩阵L的行列式（determinants），\(L_Y\)是一个L投影到只有Y的行和列上的子矩阵。因此，发现满足\(max_{Y:\mid Y \mid = k, Y \subseteq M} P(Y)\)的集合等价于发现这样的集合：\(max_{Y:\mid Y \mid = k, Y \subseteq M} det(L_Y)\)。

该半正定kernal matrix L定义如下：

\[L_{ii} = q_i^2 \\ L_{ij} = \alpha q_i q_j S_{ij}\]

…(1) (2)

其中：

• \(q_i ( i \in [1, \mid M \mid ])\)表示从ranking function生成的item i的relevance score
• S表示一个关于items间的user-defined 相似矩阵，
• \(\alpha\)是一个关于对relevance 和 diversity间进行tradeoff的超参数

如之前所述，我们需要从整个item set M中选择一个items集合Y，使得：

\[\underset{Y:\mid Y \mid = k, Y \subseteq M}{max} det(L_Y)\]

这是一个NP-hard问题【20】，具有复杂度\(O(C_{\mid M \mid}^{\mid Y \mid})\)时间来发现最优集合。为了使得DPP-based reranking model可以应用到工业界推荐系统中，我们选择使用一个高效&有效的近似算法，Fast Greedy Map Inference【21】，来在一个可接受的时延中执行reranking。这样的一个近似算法可以解决组合优化问题，时间复杂度只有\(O(\mid Y \mid^2 \mid M \mid)\)。尽管在【21】中没有提供理论上更低边界，在线A/B test测试验证了它的优越性。

算法1

为了更正式地表示它，我们将DPP-based reranking model以算法1方式进行归纳。每个round，FastGreedyMap会贪婪地选择一个item（如算法1中的第3行），也就是说，选中的item会最大程度提升updated submatrix的行列式。正式地，它会选择这样的item：

\[y = argmax_{i \in M} (log det(L_{Y \cup \lbrace i \rbrace}) - log det(L_Y))\]

2.2 Personalized DPP

在DPP中，\(\alpha\)是一个可调的超参数，用来对relevance和diversity进行trade-off平衡。DPP假设：每个人都有相同的diversity degree的倾向分（propensity），由于当构建kernel matrix L时会应用相同的\(\alpha\)值，当执行reranking时对所有用户是共享的。然而，如第1节所讨论，不同的个人具有对多样性不同的倾向（propensity），因此DPP需要进行个性化。

在DPP中实现个性化的一种简单方法是，为每个user u设置一个唯一的超参数\(\alpha_u\)。不幸的是，该方法不可行，因为超参数的个性\(\alpha_u\)太大，不可能针对个人去调参。在本paper中，提出了一咱有效的方法来达到personalized DPP（简称：pDPP）。我们会将user-wise超参数\(\alpha_u\)进行factorize成两个因子：

\[\alpha_u = f_u \times \alpha_0\]

…(4)

其中:

• \(\alpha_0\)：是一个可调共享的超参数，用来控制在所有用户上的relevance和diversity（在DPP中，与\(\alpha\)具有相同的功能)
• \(f_u\)：是一个user-wise factor，用来表示user u的多样性倾向（diversity propensity）

接着，我们详细说明定义\(f_u\)的意图。如第1节所解释，用户的多样性倾向（diversity propensity）可能受他们的历史行为的影响。作为一种可能的选择，我们可以使用该用户交互过的不同genres分布上的香农熵（shannon entropy），如下：

\[H(u) = - \sum\limits_{g \in G} P(g | u) log(P(g | u))\]

…(5)

其中：

• \(P(g \mid u)\)表示user u对某类别g感兴趣的概率
• user u交互过的items之一是genre g

如【18】所示，一个user u具有更高的H(u)，表明该用户具有更高的diversity propensity，反之亦然。由于该直觉，我们将\(f_u\)定义为 normalized H(u)。正式的，我们提出使用一个parameterized min-max normalization，如下：

\[f_u = \frac{H(u) - H_{min} + l}{H_{max} - H_{min} + l} \ (l \geq 0)\]

…(6)

其中：

• \(H_{max} = max_u H(u)\)表示在所有users上的最大熵值，
• \(H_{min}\)表示最小值

超参数l控制着\(f_u\)的个性化程度。如图3所示，一个更大的l值表示在所有用户间具有更小的个性化\(f_u\)值，例如：\(l \rightarrow \infty\)，它可以看成是\(f_u = 1\)，此时pDPP就降级为DPP。实际上，我们选择使用两个特例：当\(l=0\)时，\(f_u\)是标准的min-max normalized H(u); 其中当\(l = H_{min}\)时，\(f_u\)是max normalized H(u)。

图3

为了归一化，pDPP是DPP的一个个性化版本，无需引入额外的超参数进行调参。尽管公式很简单，第4节的实验结果表明它的有效性。

3.系统实现

3.1 框架修改

使用pDPP re-ranking 模型的推荐系统总览如图4所示。我们首先展示不考虑reranking model的模块（绿色框），接着展示了如何在pDPP中采用这些modules。

图4

一个推荐系统的架构包含了三个模块：

• (1) 离线训练模块（offline training module）：会处理user-item交互数据，抽取features（包括：user features、item features、context features），训练模型，以及上传模型。
• (2) 在线预测模块（online prediction module）会接收用户请求并返回一个关于items的列表。通常存在两步，称为：retrieval和ranking。由于存在数百万的items，有一个正常时延内对所有item进行排序很困难。retrieval step会返回一个符合用衣在该context下的较短的list。在减小候选size后，raking step会使用offline trained model为每个items计算relevance scores。
• (3) 近期更新模块（Nearline updating module）：它会更新user features、item features以及使用真实交互数据的离线训练模型。

我们提出的pDPP reranking model可以很轻易地集成到以上的架构中。接着，我们会描述如何采用三个模块来部分该reranking model。

• 在离线训练模块中，有个initializer会为每个user u计算\(\alpha_u\)值，并上传这样的值到online Indexer中
• 在在线预估模块中，会通过由任意ranking function计算得到的候选items的相关得分（relevance scores）以及从在线Indexer中的个性化\(\alpha_u\)，pDPP reranking model会综合考虑relevance和diversity来生成最终的推荐列表。
• 在近线更新模块中，个性化\(\alpha_u\)值是基于实时user-item交互数据进行更新的，更新后的\(\alpha_u\)值会被发送到online Indexer上。

图4

开发accurate ranking function是一个必要的研究主题。可以看到，我们的pDPP reranking model与任意高级的ranking function是兼容的，无需修改ranking function。

3.2 实践要点

为了帮助更好理解和实现我们的模型，我们归纳了一些实践要点：

• 在【21】中，kernel matrix L会被预计算并存储在内存中，如算法1所示。然而，这样的方法不能在真实推荐系统中执行，因为以下的原因：第一，relevance score \(q_i\)会被一个ranking function计算得到，会实时更新并且是个性化的。这种工业界方式的ranking function会对不同用户对相同item做出不同的relevance，另外，一个user-item pair的relevance score会在几秒后更新，因为user feature会发生变化。第二：我们的pDPP模型当构建L时具有一个个性化因子\(f_u\)，因此不同的users会具有不同的L。如果我们需要预计算并存储它们，我们需要花费大量时间和存储资源来处理这样的L。由于这两点，当该user触发请求推荐时，我们会为一个user即时（on-the-fly）计算个性化kernel matrix L。

• 在我们的实验中，我们尝试了两种不同方法来构建相似的矩阵S：一个会使用item features，另一个会使用user-item交互信息。使用user-item交互的该方法要比其它方法稍微更差些。原因是，user-item交叉通常非常稀疏，这使得：基于这些信息表示的item不是非常可靠。不管使用哪种方法，我们发现，当\(S_{ij}\)在[0, 1]间效果最好。

• 冷启问题：在我们的系统中，如果u是一个新用户，我们设置\(\alpha_u=\alpha_0\)。另外，只有少量交互的用户也会被我们的系统认为是新用户。我们会做出这样的决策：由于\(\alpha_0\)是一个对于exploration来说相对安全的值，可以较好地对relevance和diversity进行trade-off。

4.实验评估

4.1

4.2 在线评估

在离线评估中，展示pDPP的良好accuracy与diversity的tradeoff，我们部署pDPP到真实线上系统中来验定它的有效性。

4.2.1 实验设定

对于在线评估，我们会进行A/B test。我们会对比三种不同的模型族：base、DPP、pDPP。我们将所有用户随机分成成百上千个bins，每个bin包含了超过10w用户。一个bin的用户会通过三者之一进行服务。在我们的真实推荐系统中，DPP的超参数\(\alpha\)以及\(pDPP\)的\(\alpha_0\)设置为0.6，因为当\(\alpha=6\)时avg(P@5, ILD@5)的效果是最好的。

4.2.2 评估指标

为了比较这些方法的优点，我们在两个metrics上（accuracy和diversity）上进行评估。第一个accuracy指标通过下载率（download ratio）来评估，定义如下：

\[DR = \frac{total \ number \ of \ downloads}{total \ number \ of \ impressions}\]

除此之外，我们会评估users的engagement。更特别的，我们会研究每个用户的平均下载数目(AD)，如下：

\[AD = \frac{total \ number \ of \ downloads}{total \ number \ of \ users}\]

除了这两个accuracy指标，我们采用ILD来评估diversity，它在离线评估中也相同使用。

表3

4.2.3 在线效果

A/B在线测试如表3所示。考虑商业机密，我们只会在DR、AR和IDL上表示DPP、pDPP和Base模型的相对提升。

我们可以观察到，DPP和pDPP会比Base要在这三个评估指标上好很多。它建议我们提升diversity来增强推荐效果。在DPP和pDPP之间，我们观察到，pDPP要优于DPP，这表明：对diversity的个性化倾向比相同的倾向setting要更合适。我们观察到：pDPP要比DPP的线上提升，不会有离线评估那么大。通过详细分析，我们发现：大约35%的用户在它们的行为中只有一个下载记录，因此它很难定义它们的多样性倾向，这是未获得大提升的主要原因。然而，每天我们的APP store转化是数百万美金，因此这样的不大提升每年能带来额外的美金收入。

参考

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