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

twitter在《Addressing Delayed Feedback for Continuous Training with Neural Networks in CTR prediction》提出了一种FNW的逻辑：

摘要

在展示广告中，一个挑战是特征分布和点击率（CTR）可能会因为季节性变化、广告活动的变化和其他因素而随时间发生大幅度变化。为了跟上这些变化，主要的策略是持续在新鲜数据上训练预测模型，以防止它们变得过时。然而，在许多广告系统中，正向标签（postive label）只有在可能很长且随机的延迟之后才会被观察到。这些延迟的标签对连续训练中的数据新鲜性构成了挑战：在它们被训练算法摄取时，新鲜数据可能没有完整的标签信息。

naive策略是：将任何数据点视为负例，直到正向标签变得可用，往往会低估CTR，导致用户体验不佳和广告商的性能次优。本文的重点是确定最佳loss函数和模型的组合，以便在存在延迟标签的情况下，从连续数据流中进行大规模学习。在这项工作中，我们比较了5种不同的损失函数，其中3种是首次应用于这个问题。我们在离线设置中使用浅层和深层模型架构，对公共和专有数据集进行了基准测试。我们还讨论了在生产环境中实现每种损失函数的工程成本。最后，我们对表现最佳的几种方法进行了在线实验，以验证它们在连续训练方案中的性能。在离线训练6.68亿内部数据点时，我们提出的方法比之前的最先进水平提高了3%的相对交叉熵（RCE）。在在线实验中，我们观察到每千次请求的收入（RPMq）比naive logloss增加了55%。

1.介绍

许多广告商会选择在用户执行了预定义动作(例如点击他们的广告或访问他们的网站)之前不支付任何曝光（impression）费用。这个问题在广告领域是众所周知的，并引入了诸如每次点击成本（CPC:cost-per-click）和每次转化成本（CPA:cost-per-conversion）等模型，允许广告商只对预定义的消费（engagements）进行付费。这些基于绩效的付费模型会估计一次曝光能够产生的特定消费(engagement)的概率。

在展示广告中，由于特殊事件、新活动和其他因素，特征和点击率（CTR）分布可能会经历巨大的变化。图1和图2通过时间展示了这些变化。为了解决这个问题，Twitter的广告预测模型会不断在线训练新鲜数据，即它们接收连续的数据流，并在新数据到达时更新模型（见图3）。

图1 在参照日之后每个小时的带有新广告活动ID(campaign ID)的流量百分比

在上述场景中遇到的主要挑战是用户行为反馈的延迟。一些消费（engagements），例如广告上的一次点击或广告视频的一次MRC观看，可能会在广告展示后的1分钟、1小时甚至1天后发生。相应的挑战是，在为广告曝光分配label之前（随后在该数据上进行训练），是否需要等待一个固定的时间窗口，还是根据某些启发式规则来决定label。

图2 连续特征值在3天内的分布情况。

• 早前方法的主要缺点是：在等待过程中模型可能会变得过时，以及维护数据缓存所需的额外基础设施成本。
• 随后出现的实时方法的问题是：训练涉及到错误地将样本标记为负例，导致负例数量比实际数据分布中更多。

未知的是，我们应该将理想的窗口长度设置成多少，以便在模型训练的延迟和假负例（FN）率（即由于窗口太短而错误地将示例标记为负例）之间找到平衡。

内部实证结果显示，即使模型更新延迟5分钟，也可能在性能方面造成极大的损害。在【naive的连续学习方法】中，小批量具有负标签的训练样本会立即被模型吸收，因而，模型始终是最新的，会随时间发生严重的特征分布变化（feature distribution shift）。因为不需要存储尚未被点击的实例的额外快照，从技术上讲，这种方法允许我们无限期地等待，直到观察到正向标签。然后，它可以立即引入到模型中，如图3所示。

图3 连续学习框架

这种方法的主要缺点是：所有样本初始都被标记为负例，即使用户最终可能会消费（engage）它们。或者，数据样本保持未标记状态（unlabeled）直到发生消费(engagement)行为，并且消费（engagement）概率被认为依赖于从曝光发生以来经过的时间，如[3]中所述，就需要定期收集和存储数据的快照，以捕捉消费延迟分布( engagement delay distribution)。尽管时间依赖性的假设是有效的，但鉴于需要多次存储数据点（每个快照一次）以批量模式训练模型，这将导致基础设施成本大幅增加，并且如果没有激进的下采样，训练数据会随着时间的推移而增长。最后但同样重要的是，像[13]中提出的固定时间窗口将允许我们在训练之前获得大部分正向标签，但仍然会导致那些落在固定窗口之外进行消费的FN标签。因此，处理假负例（FN）的问题仍然存在，并且模型还有变得过时的额外风险。

在这项工作中，我们设计了一个模型，用于预测特定用户在Twitter平台上点击视频广告的概率（pCTR）。通过这一努力，我们在两个不同的数据集上离线比较了两类不同的模型架构和五种不同的损失函数。随后，我们选择了表现最佳的架构和损失函数，并通过在线实验对它们进行评估。

• 第一种模型架构是一个简单的逻辑回归模型，由于其简单性、良好性能以及在线训练中容易摄取和处理新训练示例的特点，在展示广告行业中得到了广泛使用[3, 13]。
• 第二种模型采用了deep&wide的架构[5]，旨在应对推荐系统中使用的复杂和多样化的特征。

我们测试的五种损失函数，包括：

• 对数损失（log loss）
• 假负例加权损失（FN weighted loss）
• 假负例校准（FN calibration）
• 正未标记损失[7, 8]（positive unlabeled loss）
• 延迟反馈损失[3]（delayed feedback loss）

在这些中，对数损失通常用于CTR预测[14]。

在线实验中使用了连续学习，我们认为这在基础设施成本、生产化便利性方面提供了最佳权衡，并且具有显著优势，即模型始终在新鲜数据上进行训练。

虽然通过在线梯度下降的连续或在线训练在浅层（线性或基于核的）模型中得到了广泛应用[12]，但关于深度神经网络的连续学习的研究相对较少[21]。这尤其具有挑战性，因为目标函数是非凸的，并且已经提出了替代方法，如对冲策略[24]，来解决这个问题。据我们所知，这是第一次使用深度学习模型来估计展示广告中的pCTR，同时解决延迟反馈问题。鉴于在线训练对深度神经网络来说难以采用，这项工作旨在对延迟反馈问题进行基准测试，并提出可行的解决方案，而不增加额外的工程成本。我们考虑的三种损失函数，正未标记（PU：positive unlabeled）、假负例加权（FN weighted）和假负例校准（FN calibration），是首次应用于这个问题，而后两种基于重要性采样。我们的结果表明，线性模型和小数据集上的好性能并不一定能转化为深度模型的同等性能。例如，延迟反馈损失在使用公共数据集的线性模型上导致了最佳的相对交叉熵（RCE），但在Twitter数据上使用深度模型时，却被所有提出的损失函数超越（RCE增加了2.99%）。损失函数的有效性也随着可用数据量的变化而变化。我们希望这篇论文能作为在连续方式下训练深度学习模型进行广告点击预测任务时使用哪种损失函数的指南。

2 相关工作

为了确保模型始终在新鲜数据流上进行训练，一些示例被错误地标记为负例或保持未标记状态（unlabeled）。一旦用户对广告产生消费，相同的数据点将以正标签呈现给模型。在[13]中，他们声称使用了一个足够长的时间窗口，以显著减少经验CTR与真实情况之间的偏差（仍然一部分曝光被错误地标记为负例）。尽管大多数方法忽视了可用的时间延迟信息（即自曝光以来经过的时间以及用户与广告交互前的时间），但其中一些方法通过联合训练延迟模型以及CPC或CPA模型来利用时间延迟[3, 28]。在以下各节中，我们描述了五种不同的方法，这些方法构成了解决FN问题的潜在解决方案。我们进一步讨论了它们各自的挑战。

2.1 重要性采样（Importance Sampling）

模型相对于数据分布$ \mathbf{p} $的交叉熵由下式给出：

\[L(\theta) = -\mathbb{E}_{\mathbf{p}}[\log f_{\theta}(y|x)] = -\sum_{x,y} \mathbf{p}(x, y) \log f_{\theta}(y|x) \quad (1)\]

其中：

• $ x $是与特定请求（与用户和广告相关）相关的特征，
• $ y $是表示用户是否消费（engagement）的二元label
• $ f_{\theta} $是试图预估$ \mathbf{p} $的模型。
• $\theta$：模型参数

如前所述，在在线训练场景中，直到观察到正标签，否则样本被引入当成负例。这导致模型观察到一个有偏的分布$ \mathbf{b} $，而不是实际的数据分布。因此，我们不能从$ \mathbf{p} $中采样，只能访问来自不同分布$ \mathbf{b} $的样本。通过应用适当的加权方案，我们可以使用以下公式获得公式(1)中期望的无偏估计：

\[\mathbb{E}_{\mathbf{p}}[\log f_{\theta}(y|x)] = \mathbb{E}_{\mathbf{b}}\left[ \frac{\mathbf{p}(x, y)}{\mathbf{b}(x, y)} \log f_{\theta}(y|x) \right] \quad (2)\]

权重 $ w(x, y) = \frac{p(x,y)}{b(x,y)} $ 对应于重要性权重，旨在纠正在不同分布上进行平均的事实。使用来自不同、有偏的分布 $ b $ 的样本，可以通过以下方式估计等式(2)中的期望值：

\[\frac{1}{N} \sum_{n} w(x_n, y_n) \log f_{\theta}(y_n | x_n)\]

使用一个分布中的样本来估计另一个分布的期望值这种方法称为重要性采样。重要性采样已在不同情境中得到广泛使用，包括反事实分析，在[2]中作者讨论了涉及的假设以及如何将这种技术应用于计算广告中以估计任何量的反事实期望。在这种情况下使用重要性采样的最大挑战是我们需要估计权重 $ w(x, y) $。从此处开始，出于简洁性，我们使用 $ f_{\theta}(x) $ 来表示 $ f_{\theta}(y = 1 \mid x) $。

2.2 逆倾向性加权（Inverse Propensity Weighting）

逆倾向性加权在因果推断中得到了广泛应用，其中某些总体中的样本可能被低估。通过在estimator中对个别样本使用适当权重，可以调整实际总体与样本之间的差异[1]。当抽样概率已知时，就使用这个概率的倒数来加权观察结果。倾向性得分，记作:

\[p(x) = P(T = 1 \mid X = x)\]

是给定一组协变量时样本将被分配特定处理的概率。在假设处理不是随机分配的情况下，反事实相当于假设所有总体样本都以等概率被分配任何处理的等效估计。在点击率预估的背景下可以采用类似的方法，其中treatment相当于广告被赋予一个真实label。在任何问题中应用这种技术时需要考虑的一个要求是，倾向性权重需要通过一个单独的参考模型来估计。

2.3 PU learning(Positive - Unlabeled Learning)

另一种方法集不会明确识别带有负标签的数据，而只从正例（P）和未标记（U）样本中学习，这与传统的分类设置不同，在传统分类设置中，正例和负例都是可用的。当获取已标记样本不可能或成本非常高时，就会出现这种设置，例如在文本分类[10]、分子生物学[9]中，但这种方法也被应用于异常值检测[25]和时间序列分类[23]。

这种情况下，可用的训练数据由一组不完整（随机抽样）的正例和一组unlabeled样本组成，这些样本可能是正例或负例，导致需要一种不同的训练过程。关于训练数据的一个关键假设是，它们是从$p(x, y, s)$ 中随机抽取的，对于每个抽取的元组 <x,y,s>，只会记录 <x, s>。这里:

• s是观察到的label
• y是实际label，可能尚未发生

与此同时，假设：已标记的正例是从所有正例中以完全随机的方式选中，例如:

\[p(s = 1 \mid x, y = 1) = p(s = 1 \mid y = 1)\]

这种情况下，我们首先训练一个分类器 $ g(x) = p(s = 1 \mid x) $ ，来估计：给定一条样本的原始标签为正例（y = 1）时，该样本被标记为正例（s=1）的概率[9]，因为

\[p(s = 1 | y = 1) = \frac{1}{n_P} \sum_{x \in P} g(x)\]

其中：

• $ n_P $ 是正例 P 的基数。

接下来，每个unlabel样本可以被看成是以下两者的组合：

• 一个正例，它的权重与$ p(y = 1 \mid x, s = 0) $ 成比例 （观察是unlabeled，实际是个正例）
• 一个负例，它的权重与互补权重 $ 1 - p(y = 1 \mid x, s = 0) $成比例（观察是unlabeled，实际是个负例）

而所有正例都有单位权重。该weight可以表示为：

\[p(y = 1 | x, s = 0) = \frac{1 - p(s = 1 | y = 1)}{p(s = 1 | y = 1)} \times \frac{p(s = 1 | x)}{1 - p(s = 1 | x)}\]

最后，可以使用这些权重和标准训练过程在可用数据上训练分类器。 在之前的研究中，[19] 通过执行逻辑回归，并优化线性函数的squared weights求和和以及weighted logit loss的和，学习了给定输入观察到正标签的条件概率。在这种设置中，unlabeled样本具有单位权重，而正样本的权重由 $ n_U / n_P $ 的比值确定。PU问题也通过对分类器进行聚合来解决，这些分类器被训练以区分P数据和U数据的随机子样本[22]。

在文献[8]和[7]中，du Plessis等人首次提出了一个无偏的非凸风险估计器，并分析了从数据中估计类先验时的超额风险。在标准二分类中，分类风险（classification risk）由下式给出：

\[\widehat{R}_{PN}(f_{\theta}) = p(y = 1)E_{p(x|y=1)}[l(f_{\theta}(x))] + p(y = 0)E_{p(x|y=0)}[l(1 - f_{\theta}(x))]\]

其中：

• $ l $ 是损失函数。

由于：

\[p(x) = p(y = 1)p(x \mid y = 1) + p(y = 0)p(x \mid y = 0)\]

最后一项可以表示为：

\[p(y = 0)E_{p(x|y=0)}[l(1 - f_{\theta}(x))] =\\ E_{p(x)}[l(1 - f_{\theta}(x))] - p(y = 1)E_{p(x|y=1)}[l(1 - f_{\theta}(x))]\]

因此，分类风险可以用以下表达式近似：

\[\widehat{R}_{PU}(f_{\theta}) = p(y = 1)E_{p(x|y=1)}[l(f_{\theta}(x))] \\ - p(y = 1)E_{p(x|y=1)}[l(1 - f_{\theta}(x))] \\ + E_{p(x)}[l(1 - f_{\theta}(x))] \quad (3)\]

其中：

• $ p(x) $ 对应于所有未标记示例的边际分布。

根据文献[18]，这个无偏风险估计器如果训练的模型过于灵活，可能会产生负的经验风险，这使得这个损失函数更难以用神经网络优化，并容易过拟合。

2.4 延迟反馈模型

文献[3]中提出的方法对CPA（每次行动成本）进行建模，并考虑了自广告点击以来经过的时间，并且不涉及匹配窗口。在这种情况下，延迟反馈问题的处理方式如下：只有当实际观察到正标签(positive labels)时，训练样本才被标记为正向，否则被视为unlabeled，类似于PU learning方法。在模拟点击后归因的情况下，这意味着负标签不可能发生，因为转化可能在任何未来的时间内发生。大多数只从正样本和unlabeled样本中学习的方法[9, 19]假设缺失标签的正样本的概率是恒定的。然而，根据[3]的说法，最近的点击不太可能被赋予真实label，因为经过的时间不够长，即正样本的概率是与时间相关的。因此，他们使用第二个模型，该模型非常类似于生存时间分析模型[15]，以捕捉点击和转化之间的预期延迟。这与预测用户最终是否会转化的模型是分开的，但两个模型是联合训练的。在这种方法中，

• 随机变量 $ Y \in \lbrace 0, 1 \rbrace $ 表示一次转化是否已经发生
• 另一个独立的随机变量 $C \in \lbrace 0, 1\rbrace$ 表示用户最终是否会真实转化

一旦训练了两个模型，只会保留预估转化率的模型，即 $ P(c = 1 \mid x) $，而转化延迟模型 $ P(d \mid x, c = 1) $ 则被丢弃。标准逻辑回归模型代表点击率（CTR），而延迟则假设为指数（非负）分布，即：

\[P(d|x, c = 1) = \lambda(x) \exp(-\lambda(x)d) \quad (4)\]

因此，$ y = 0 $ 可能发生在两种不同的情况下：

• 经过的时间$e$比转化时间$d$短，即 $ e < d $
• 用户永远不会转化，即 $ c = 0 $

尽管该模型被应用于CPA（cost-per-conversion）模型，它也适用于本文的CPC(cost-per-click)模型。图4说明了点击时间也遵循指数分布，这使得这个模型成为一个适当的解决方案。作为[3]中呈现模型的扩展，[28]建议了一个非参数延迟反馈模型（NoDeF），以在不假设任何参数分布（如指数或威布尔分布）的情况下捕捉时间延迟。该模型假设每个样本都有一个隐藏变量，这表明这个动作最终是否会导致转化。对于参数估计，使用了期望最大化（EM）算法[6]。然而，采用这些方法将需要用一个单独的模型来估计时间延迟，并显著增加基础设施成本和将这样一个系统投入生产的复杂性。

图4 训练广告的点击延迟时间分布（超过5分钟）。对应于在纠正了审查分布的累积分布函数（CDF）之后的分布

2.5 Delayed Bandits

延迟反馈在马尔可夫决策过程（MDPs）[16, 27]的背景下已得到广泛考虑，但当延迟不受限制时，其应用变得更加具有挑战性。在[26]中，作者提出了离散时间随机多臂老虎机模型，来解决可能存在审查反馈的长延迟问题，即不可观察的反馈。他们涵盖了这两种模型的两个不同版本：

• 未审查模型（uncensored model）：允许在任意长的延迟后观察转化；
• 审查模型（censored model）：它在行动后施加了$m$个时间步长的限制，在此之后，转化不再可观察。

在每一轮中，agent收到的reward对应于在时间 $ t $ 观察到的转化数量。然而，与之前的方法不同，这些模型假设已知延迟分布。他们认为这是一个有效的假设，因为分布可以从历史数据中估计，并且还声称可以在线方式在不增加成本的情况下估计延迟分布，前提是它被所有行动共享。

3 提出的方法

在本工作中，我们采用了一种连续训练方案，它建议：我们可以潜在等待从广告曝光以后的无限时间，直到最终观察到真实正向消费。从历史上看，这是通过摄取所有带有负标签的样本来处理的，直到用户记录了正向消费。因此，有偏的数据分布（即观察到的分布），包含了所有从实际数据分布中标记为负的样本。相应地，在有偏分布中的正样本对应于原始数据分布中的所有正样本。

3.1 模型架构

本节描述了正在考虑的模型的架构细节。

3.1.1 逻辑回归

我们使用了一个标准逻辑回归模型，该模型在展示广告领域得到了非常广泛的应用[3, 13]：

\[f_{\theta}(x) = \frac{1}{1 + \exp(-w_c \cdot x)} = \sigma(w_c \cdot x)\]

其中：

• $ \sigma(\cdot) $ 对应于sigmoid函数
• 输入 x 是与特定请求相关的用户和广告候选的成千上万个特征的稀疏表示。

3.1.2 Wide&deep模型

这个深度模型由一个宽组件组成，对应于一个广义线性模型，以及一个深组件，对应于一个标准前馈神经网络。宽组件处理原始输入特征和转换后的特征，例如交叉乘积特征，为广义线性模型添加非线性。深组件将高维稀疏特征转换为嵌入向量，将分类特征转换为密集的、低维的表示形式。 与前一个模型类似，特征包括用户特征、上下文特征和广告特征。模型对CTR的预测由下式给出：

\[f_{\theta}(x) = \sigma(w_{wide}^T \cdot [x, \phi(x)] + w_{deep}^T \cdot {\alpha^{(l_f)}} + b)\]

其中：

• $ w_{wide} $ 对应于wide组件的权重，
• $ w_{deep} $ 对应于deep组件的权重，
• $ \phi(x) $ 是交叉乘积变换，
• $ \alpha^{(l_f)} $ 是deep分支的最终层的激活

3.2 损失函数

3.2.1 延迟反馈损失（Delayed feedback loss）

在这个版本的损失函数中，假设时间延迟遵循指数分布，并且这个模型与逻辑回归模型或深度模型联合训练。假设:

• $ \lambda(x) = \exp(w_d \cdot x) $
• $ w_d $ 是pCTR模型的参数

我们针对参数 $ \theta $ 和 $ w_d $ 优化正则化对数似然：

\[\underset{\theta, w_d}{\text{arg min}} \ L_{DF}(\theta, w_d) + \alpha (\| \theta \|^2_2 + \| w_d \|^2_2)\]

其中：

• $ \alpha $ 是正则化参数，
• $ L_{DF} $ 是延迟反馈损失函数，其定义如下：

\[L_{DF}(\theta, w_d) = -\sum_{x,y=1} \log f_{\theta}(x) + \log \lambda(x) - \lambda(x)d \\ - \sum_{x,y=0} \log[1 - f_{\theta}(x) + f_{\theta}(x) \exp(-\lambda(x)e)] \quad (5)\]

其中：

• $ f_{\theta}(x) $ 对应于pCTR模型的输出，
• $ d $ 对应于正样本的点击时间
• $ e $ 表示自广告曝光以来经过的时间

这个损失函数可以以更数值稳定的方式计算如下：

\[L_{DF}(\theta, w_d) = -\sum_{x,y} \log f_{\theta}(x) - \sum_{x,y=1} w_d \cdot x - \lambda(x)d \\ - \sum_{x,y=0} \log[\exp(-f_{\theta} (x)) + \exp(-\lambda(x)e)]\]

3.2.2 PU-loss（Positive-Unlabeled loss）

在这一部分中，我们考虑在假负例（FN）设定下使用PU损失，通过将有偏训练数据中的所有负样本视为未标记。根据等式(3)，可以推导出以下损失函数：

\[L_{PU}(\theta) = -\sum_{x,y=1} [\log f_{\theta}(x) - \log(1 - f_{\theta}(x))] - \sum_{x,y=0} \log(1 - f_{\theta}(x)) \quad (6)\]

从经验上看，这可以被看成是：对正样本和负样本都使用传统的log loss。另外，当观察到正例时，都会朝着负梯度的相反方向迈出一步。这个假设是合理的，因为对于每个正样本，都会基于在一个假负样本的梯度上进行参数更新。

3.2.3 假负例加权（Fake Negative Weighted loss）

该损失函数依赖于重要性采样。在我们的训练设置中，样本会被标记为负例，并被引入到训练pipeline中，接着当用户发生消费时会复制出一个正标签。为了对该损失函数进行公式化，我们依赖以下假设：

\[b(x|y = 0) = p(x) \\ b(x|y = 1) = p(x|y = 1)\]

其中：

• $b$：是有偏的观察到的分布
• $p$：是实际的数据分布

我们知道：

\[b(y = 0) = \frac{1}{1+p(y=1)}\]

因为：所有样本最初都被标记为负例。

(1)中的损失函数可以写成：

\[-\sum_{x,y} p(y = 1|x) \log f_{\theta}(x) + p(y = 0|x) \log f_{\theta}(y = 0|x) \\ = -\sum_{x,y} \frac{b(y = 1|x)}{p(y = 1|x)} \log f_{\theta}(x) + \frac{b(y = 0|x)}{p(y = 0|x)} \log f_{\theta}(y = 0|x) \quad (7)\]

在有偏分布中观察到用户正向消费的概率是：

\[b(y = 1|x) = \frac{b(y = 1)b(x|y = 1)}{b(y = 1)b(x|y = 1) + b(y = 0)b(x|y = 0)}\]

利用上述假设，并分配 $ w(x) := \frac{1}{1+p(y=1 \mid x)} $，可以表示为：

\[b(y = 1|x) = \frac{w(x)p(y = 1)p(x|y = 1)}{w(x)p(y = 1)p(x|y = 1) + w(x)p(x)} \\ = \frac{p(y = 1|x)p(x)}{p(y = 1|x)p(x) + p(x)} \\ = \frac{p(y = 1|x)}{1 + p(y = 1|x)} \quad (8)\]

类似地，用户不消费的概率是：

\[b(y = 0|x) = 1 - b(y = 1|x) = \frac{1}{1 + p(y = 1|x)} \quad (9)\]

通过将(8)和(9)替换到等式7中，我们得到以下表达式：

\[L_{IS}(\theta) = -\sum_{x,y} b(y = 1|x) (1 + p(y = 1|x)) \log f_{\theta}(x) \\ + b(y = 0|x)p(y = 0|x) (1 + p(y = 1|x)) \log f_{\theta}(y = 0|x) \quad (10)\]

因此，我们可以：

• 用 $ (1 + p(y = 1 \mid x)) $ 来加权正样本
• 用 $ (1 - p(y = 1 \mid x)) \cdot (1 + p(y = 1 \mid x)) $ 来加权负样本

由于我们不能直接获取 $ p $，我们可以用模型估计 $ f_{\theta} $ 来替代它，只要 $ f_{\theta} $ 收敛于 $ p $，这在以下段落中将得到证明。

依赖于(8)和(9)，并通过在重要性权重中用 $ f_{\theta} $ 替代 $ p $，(10)可以重写为：

\[L_{IS}(\theta) = -\sum_{x,y} \frac{p(y = 1|x)}{1 + p(y = 1|x)} [(1 + f_{\theta}(x))]\log f_{\theta}(x) \\ + \frac{1}{1 + p(y = 1|x)} [(1 - f_{\theta}(x))(1 + f_{\theta}(x))] \log(1 - f_{\theta}(x))\]

$[\cdot]$括号中的项在计算loss对输入的梯度时不予考虑。最后，$ L_{IS}(\theta) $ 相对于 $ f_{\theta} $ 的梯度可以写成：

\[\frac{\partial L_{IS}}{\partial f_{\theta}} = -\frac{p(y = 1|x)}{1 + p(y = 1|x)} \frac{1 + f_{\theta}(x)}{f_{\theta}(x)} + \frac{1 + f_{\theta}(x)}{1 + p(y = 1|x)} \\ = \frac{(1 + f_{\theta}(x))(f_{\theta}(x) - p(y = 1|x))}{(1 + p(y = 1|x))f_{\theta}(x)} \quad (11)\]

注意，对于 $ p(y = 1 \mid x) \in (0, 1] $：

• 当 $ \frac{\partial L_{IS}}{\partial f_{\theta}} = 0 $ 时，那么 $ f_{\theta}(x) = p(y = 1 \mid x) $，即只要 $ f_{\theta}(x) > 0 $，$ f_{\theta}(x) $ 就收敛于 $ p(y = 1 \mid x) $
• 当 $ f_{\theta}(x) > p(y = 1 \mid x) $ 时，$ \frac{\partial L_{IS}}{\partial f_{\theta}} > 0 $
• 当 $ f_{\theta}(x) < p(y = 1 \mid x) $ 时，$ \frac{\partial L_{IS}}{\partial f_{\theta}} < 0 $。

这表明FN weighted loss导致 $ f_{\theta}(x) = p(y = 1 \mid x) $，并且梯度始终指向正确的方向。

3.2.4 假负例校准(Fake negative calibration)

在该方法中，模型会估计有偏分布$b$，接着，在解等式8求 $ p(y = 1 \mid x) $ 后使用以下变换：

\[p(y = 1|x) = \frac{b(y = 1|x)}{1 - b(y = 1|x)}\]

这总是一个有效的分布，因为，对于在有偏分布中的每个正例，都会观察到一个FN，即 $ b(y = 1 \mid x) \leq 0.5 $ 且 $ p(y = 1 \mid x) \leq 1 $。为简洁起见，我们称这种方法为FN校准。

4.实验

4.1 Setup

4.1.1 离线指标

为了比较正在考虑的不同模型架构和loss函数，我们首先进行了离线实验。离线实验被用来验证所提出的损失函数是否适用于CTR预测问题，并且使用了两个不同的数据集进行模型的训练和测试，一个内部数据集和一个公共数据集。在离线设置中，我们在本文中关注并报告的指标包括：评估集上的logloss（其中不包含假负例）、相对交叉熵（RCE）和准确率-召回率曲线下面积（PR-AUC）。RCE对应于相对于稻草人预测，或者说是naive预测的改进，通过交叉熵（CE）来衡量。naive预测对应于不考虑用户和广告特征的情况，例如，它总是预测训练集的平均CTR。假设naive预测的平均CE是 $ C_{\text{naive}} $ ，要评估的预测的平均CE是 $ C_{\text{pred}} $ ，那么RCE定义为 $ (\text{CE}{\text{naive}} - \text{CE}{\text{pred}}) \times 100/\text{CE}_{\text{naive}} $ 。请注意，CE越低，预测的质量越好，因此RCE越高。使用RCE的好处是，我们可以确信地估计模型是在低估还是高估了天真预测的性能。PR-AUC是一个更常用的指标，并且在数据倾斜的情况下比AUC更敏感。

4.1.2 在线指标。

最有希望的离线结果的模型和损失函数在线上环境中进行了进一步评估，因为期望的应用是连续训练。线上环境反映了实际性能，这决定了哪种方法最适合处理延迟反馈问题。然后，在Twitter数据的保留评估数据集上执行评估，以比较“对照”方法和“A/B测试框架中的处理”方法的性能。通过在评估日期结束后等待最多9小时以获取消费标签，已从这个保留数据集中移除了假负例。在这种设置中报告了两个关键指标：汇总相对交叉熵（汇总RCE）和每千次请求的收入（RPMq）[20]。汇总RCE用于在控制和实验之间进行RCE的公平比较，否则每个模型都将在自己的流量上进行验证，并且是通过评估两个模型生成的汇总流量来衡量模型泛化能力的一个指标。RPMq代表每1000次广告请求产生的收入。通过展示更高质量的广告来增加用户消费可能会导致RPMq增加，但RPMq也可能仅通过每次请求提供更多广告而上升，而不考虑其质量。因此，更高的RPMq是可取的，但这个指标需要与CTR一起考虑，因为高RPMq与低CTR可能会损害用户体验并导致负面的长期影响。

4.1.3 超参数。

用于离线实验的超参数包括：随机梯度下降（SGD）优化器，学习率0.02；衰减率0.000001；批量大小128；用于延迟反馈损失的学习率是0.005，延迟反馈模型的L2正则化参数是2。我们使用了固定数量的箱位将分类和连续特征进行离散化。宽与深模型的深度部分由4层组成，大小为[400, 300, 200, 100]，并且采用泄漏的修正线性单元（ReLU）作为中间层的激活函数。权重是使用Glorot [11]初始化的。相同的超参数被用来初始化线上模型。

4.2 数据

4.2.2 离线Twitter数据。

对于基于内部数据(in-house data)的实验，我们离线训练了4天的数据。并在随后一天的数据上执行评估。鉴于实际上只有一小部分曝光给用户的广告会被点击，数据标签不平衡构成了特别的挑战。在我们的训练设置中，为了解决这种不平衡问题，负样本被下采样到原始数据集的5%，并且在loss函数中为负样本采用了更高的权重来解释这种修改。经过这些步骤，训练数据的总数达到了6.68亿视频广告，而测试数据达到了700万广告。对于评估数据集，如果在曝光时间之后的9小时内发生了消费，则给样本分配一个正标签。否则，样本被分配一个负标签。随后，正例和负例都被下采样到它们原始大小的5%。

为了获得经过的时间和点击时间信息，在每个日期结束时对数据进行了快照捕捉。因此:

• 对于尚未观察到消费的样本：分配了一个负标签，并将从曝光时间到快照时间经过的时间作为特征添加。
• 对于在快照时间之前观察到消费的样本：除了经过的时间外，消费时间和曝光时间之间的差异被记录为点击时间。

这些时间特征仅用于估计时间延迟模型，这是延迟反馈损失（delayed feedback loss）所必需的。值得一提的是，由于大多数假负例（FN）已从这个派生的数据集中清除，正例/负例比例最终比以前更高。

4.2.3 在线Twitter数据

在在线实验中，所有模型都训练于实时生成的曝光回调数据的连续数据流。向用户展示广告曝光，并且每个样本的标签是根据当前的点击信息决定的（这就是假负例进入训练数据的地方）。然后，每个训练样本被发布到数据流中，模型的训练服务订阅了这个数据流。连续训练过程每10分钟输出一次模型，这些模型被预测服务获取以服务在线流量。在计算pooled RCE时，我们使用与生成离线评估数据相同的数据源，这意味着：通过在给每个广告曝光分配标签之前等待9小时，我们才会移除假负例。

需要注意的是，每个在线实验只服务于1%的生产流量，这意味着训练流量主要由我们当前的生产模型主导。我们还在这个参考生产流量上计算我们的在线这pooled RCE指标，这个流量不受任何模型的影响，以确保通过使用每个模型相同的评估数据集来保证公平性。

4.3 结果

4.3.1 离线评估

表2

在Twitter数据上的结果显示在表2和表3中，分别对应逻辑回归模型和Deep&Wide模型。这些对应于每个模型使用不同初始化进行的8次评估的中位性能。总体上，我们可以观察到，深度学习模型在所有loss函数上的表现都优于逻辑回归模型，这在预料之中。就RCE而言，

• logloss在两种模型中表现最差，而FN校准损失为线性模型带来了最佳性能（RCE为12.41，损失为0.5641）。
• PU loss和FN校准在深度模型上表现最佳，产生了几乎等效的结果（RCE分别为13.57和13.58），并且与FNW loss的性能非常相似（RCE为13.54）。因此，这三种损失函数与logloss在线上环境中进行了比较。

延迟反馈损失在两类模型中都优于logloss（线性模型的RCE分别为10.59和5.48，深度模型的RCE分别为12.11和7.81）。PR-AUC可能不像RCE那样变化大，但其在表现最佳的方法之间（使用非配对t检验在第1名和第2名方法之间）的差异仍然在统计上对线性模型显著。

4.3.2 在线评估

应该提到，以下结果对应于一个不考虑预算的实验，即在决定展示特定请求的广告时不考虑广告主的预算，该实验运行了1周。表4显示了使用Deep&Wide模型的顶级loss函数的在线结果。FN加权和FN校准与传统的logloss相比，都产生了更高的RPMq（分别增加了+55.10%和+54.37%）。同样地，对于货币化的CTR，增长也是显著的（FN加权为+23.01%，FN校准为23.19%）。我们观察到，尽管PU loss在离线表现良好，但在2天后出现分歧，并在分歧之前报告了在线指标。

附录：

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