baidu在《MOBIUS: Towards the Next Generation of Query-Ad Matching in Baidu’s Sponsored Search》介绍了它们的query-ad matching策略。

摘要

为了构建一个高效的竞价搜索引擎（sponsored search engine），baidu使用一个3-layer的漏斗（funnel-shaped）结构，来从数十亿候选广告中筛选(screen)出数百万的广告并进行排序(sort)，同时需要考虑低响应时延以及计算资源限制。给定一个user query，top matching layer负责提供语义相关的ad candidates给next layer，而底层的ranking layer则会关注这些ad的商业指标（比如：CPM、ROI等等）。在matching和ranking目标(objectives)间的明显分别会产生一个更低的商业回报。Mobius项目旨在解决该问题。我们尝试训练matching layer时，除了考虑query-ad相关性外，会考虑上CPM作为一个额外的optimization目标，通过从数十亿个query-ad pairs上直接预测CTR来完成。特别的，该paper会详述：当离线训练neural click networks，如何使用active learning来克服在matching layer上click history的低效（insufficiency），以及如何使用SOTA ANN search技术来更高效地检索ads（这里的ANN表示approximate NNS）。

1.介绍

baidu每天会处理数十亿的在线用户，来处理它们的多种queries。我们都知道，广告对于所在主流商业搜索引擎来说都是主要收入来源。本paper中，主要解释在baidu search ads系统上的最新尝试和开发。如图2所示，在搜索广告中它扮演着重要角色，会与user query相关的该广告会吸引点击，当它们的广告被点击时，广告主会支付广告费。baidu竞价搜索系统的目标是，在在线用户、广告主、付费搜索平台间形成一个闭环。

图2

通常，付费搜索引擎会通过一个two-step process来展示广告。第一个step会检索给定一个query的相关广告，下一step会基于预测user engagement来对这些ads进行rank。由于在baidu中竞价搜索引擎的商用性，我们采用一个3-layer漏斗形结构的系统。如图3所示，top matching layer负责提供与一个user query以及user的profile相关的ad候选池到next layer。为了覆盖更多的语义相关广告，此处会大量使用expansion【1,3,4】以及NLP技术【2】。底层的ranking layer会更关注商业指标，比如：cost per mile（CPM=CTR x Bid），回报（ROI），等。

图3

然而，在matching和ranking objectives间的不同，出于多种原因会导致一个更低的商业回报。给定一个user query，我们必须采用复杂模型，并花费大量计算资源在对数百或数千个ad候选进行ranking。可能令人失望的是，ranking模型上报分析得到：许多相关ads并没有提供高CPM，从而不会被展示。为了解决该问题，Baidu Search Ads建立“Mobius”项目，它的目标是建立关于付费搜索引擎的next generation query-ad matching system。之项目旨在统一不同的 learning objectives，包括：query-ad相关度以及许多其它商业指标，并符合：低延迟、计算资源的限制，以及对用户体验的较小不良影响。

本paper中，我们介绍了Mobius-V1: 它会让matching layer除query-ad相关度外，采用CPM作为一个额外的optimization objective。Mobius-V1能为数十亿user query&ad pair精准和快速预测CTR。为了达到该目标，我们必须解决以下主要问题：

• 1.低效的点击历史（insufficient click history）：由ranking layer所采用的原始的neural click模型会通过高频ads和user queries进行训练。它趋向于估计一个具有更高CTR的query-ad pair来展示，尽管它们具有低相关性。
• 2.高计算/存储开销：Mobius期望预测关于数十亿user query&ad pairs的多个指标（包括：相关度、CTR、ROI等）。它天然会面对对计算资源更大开销的挑战。

为了解决上述问题，我们受active learning【34,41】的思想启发，首先设计了一个“teacher-student” framework来加大训练数据，为我们的大规模neural click model来为数十亿user query&ad pair预测CTR。特别的，一个离线数据生成器会负责要建人造query-ad pairs来给出数十亿的user queries和ad candidates。这些query-ad pairs会被一个teacher agent进行judge，它派生自原始的matching layer，并擅长于衡量关于一个query-ad pair的语义相关度。它可以在人造query-ad pairs上帮助检测bad cases（比如：高CTR但低相关度）。我们的neural click model，作为一个student，通过额外bad cases被教会（teach）来提升在长尾queries和ads上的泛化能力。为了节省计算资源，并满足低响应时延的要求，我们进一步采用大量最近的SOTA ANN search，以及MIPS（Maximum Inner Product Search）技术来高效索引和检索大量ads。

2.Baidu付费搜索的愿景（vision）

长期以来，漏斗结构是付费搜索引擎的一个经典架构。主要组件包含了：query-ad matching和ad ranking。query-ad matching通常是一个轻量级模块，它会measure一个user query与数十亿ads间的语义相关度。作为对比，ad ranking模块则关注商业指标（比如：CPM、ROI等），并使用复杂的neural模型来对数百个ad候选进行排序后展示。这种解耦结构是个明智选择，可以节约大量计算开销。另外，它可以帮助科学研究和软件工作上作为两个模块，分配给不同的团队可以最大化目标的提升。

百度的付费搜索使用一个3-layer的漏斗结构，如图3所示。top matching layer的最优化目标是最大化在所有query-ad pairs间的平均相关度：

\[O_{matching} = max \frac{1}{N} \sum\limits_{i=1}^n Relevance(query_i, ad_i)\]

…(1)

然而，根据我们在baidu付费搜索引擎表现上的长期分析，我们发现，在matching和ranking objectives间的区别/差异会导致更低的CPM（关键指标）。当在ranking layer的模型上报出：许多由matching layer提供的相关ads在搜索结果中并没有被展示，因为它们在估计时没有更高的CPM，这很令人不满意。

随着计算资源的快速增长，baidu搜索ads团队（凤巢）最近确立了Mobius项目，它的目标是baidu付费搜索的下一代query-ad matching系统。该项目的蓝图如图4所示：是统一多个学习目标，包括：query-ad相关度，以及许多其它商业指标，将它们统一到单个模块中，遵循：更低的响应延迟、有限的计算开销、以及对用户体验上较小的影响。

图4

该paper主要是Mobius的第一版，它会首先尝试teach matching layer考虑在query-ad relevance之外，将CPM作为一个额外的最优化目标。这里我们将目标公式化：

\[O_{Mobius-V1} = max \sum\limits_{i=1}^n CTR(user_i, query_i, ad_i) \times Bid_i \\ s.t. \frac{1}{n} Relevance(query_i, ad_i) \geq threshold\]

…(2)

这里，如何为数十亿的(user-queries, ad候选) pairs精准预测CTR是个挑战。

3. 系统

3.1 Active-learned CTR模型

baidu付费搜索引擎使用DNN来进行CTR模型预测（G size）具有超过6年的历史。最近Mobius-V1采用一个新的架构。构建Mobius-V1的一种简单方法是，复用在ranking layer中的original CTR模型。它是一个大规模和稀疏的DNN，擅长emmorization。然而，在CTR预测上对于长尾部的user queries和ads它也会有一个严重的 bias。如图5所示，在搜索日志中，同一用户有两个queries：”Tesla Model 3”和”White Rose”。对于过去使用的漏斗架构，在query “tesla Model 3”和ad “Mercedes-Benz”间的相关性会在matching layer中有保证。接着，在ranking layer中的neural click模型会趋向于在query-ad pair预测一个更高的CTR。

图5

根据我们在query log上的分析，ads和user queries具有长尾效应以及冷启动问题。因此，我们不能直接利用原始的neural click model来为数十亿长尾的user queries和ads精准预测CTR。解决这个问题的关键是：如何teach我们的模型学会：将”低相关但高CTR(low relevance but high CTR)”的query-ad pairs认为是bad cases。

算法1

为了解决这个问题，我们提出了使用在matching layer中的原始relevance judger作为teacher，来让我们的neural click model知道“low relevance” query-ad pairs。我们的neural click model，作为student，会以一个active learning的方式从有争议的bad cases上获得关于relevance的额外知识。图6通过一个流图展示了这种方式，算法1展示了使用active learning来teaching我们的neural click model的伪码。总之，active learning的迭代过程具有两个阶段：data augmentation和CTR model learning。特别的，我们会详细描述这两个phase。

图6

数据扩量（data augmentation）的阶段会将一个来自query logs的click history的batch加载到一个data augmenter开始。data augmenter每次会接收query-ad pairs，它会将它们split成两个sets：一个query set和一个ad set。接着，我们会对两个sets使用一个cross join操作（\otimes）以便构建更多的user query & ad pairs。假设在click history的batch中存在m个queries和n个ads，那么data augmenter可以帮助生成\(m \times n\)个synthetic query-ad pairs。在列出所有可能的query-ad pairs后，relevance judger会参与其中，并负责对这些pairs的relevance进行评分。由于我们希望发现低相关度的query-ad pairs，会设置一个threold来保留这些pairs作为candidate teaching materials。这些low relevance query-ad pairs，会作为teaching materials首次被feed到我们的neural click model，接着每个pair会通过前一迭代的updated model进行预测CTR来进行分配。为了teach我们的3-classes(例如：click、unclick和bad)的neural click model学会认识“low relevance but high CTR”的query-ad pairs，我们可能直觉上会设置另一个threshold，以便过滤出大多数low CTR query-ad pairs。然而，我们考虑另一个选项来对augmented data的exploration和exploitation进行balance。我们会采用一个data sampler，它会选择并标记augmented data，被称为这些synthetic query-ad pairs的predicted CTRs。一旦一个query-ad pair被抽样成一个bad case作为我们的neural click network，这些pair会被标记为一个额外的category，例如：bad。

在学习我们的CTR模型的阶段，click/unclick history以及labeled bad cases两者都被添加到augmented buffer中作为训练数据。我们的neural click network是一个large-scale和multi-layer sparse DNN，它由两个subnets组成，例如：user query DNN和ad DNN。如图6所示，在左侧的user query DNN，会使用丰富的user profiles和queries作为inputs，而右侧的ad DNN会将ad embeddings作为features。两个subsets会生成一个具有96维的distributed representation，每个都会被划分成三个vectors(32 x 3)。我们对user query DNN和ad DNN间的vectors 的这三个pairs使用3次inner product操作，并采用一个softmax layer进行CTR预估。

总之，我们贡献了一种learning范式来离线训练我们的neural click model。为了提升在CTR预测上对于长尾上数十亿query-ad pairs的泛化能力，neural click model(student)可以actively query到relevence model (teacher)来进行labels。这种迭代式监督学习被称为active learning。

3.2 Fast Ads Retrieval

在baidu付费广告搜索中，我们使用如图6的DNN（例如：user query DNN和ad DNN）来各自获取queries和ads的embeddings。给定一个query embedding，Mobius必须从数十亿ad candidates中检索最相关并且最高CPM值的ads，如等式(2)。当然，为每个query穷举式地计算它不实际，尽管brute-force search理论上可以发现我们要找的所有ads（例如：100% ad recall）。online services通常具有严格的latency限制，ad retrieval必须在一个短时间内完成。因此，我们采用ANN search技术来加速retrieval过程，如图7所示。

图7

3.2.1 ANN Search

如图6所示，mapping function会结合user vectors和ad vectors来计算cosine相似度，接着该cosine值传给softmax layer来生成最终的CTR。这种方式下，cosine值和CTR是线性相关的。在模型被学到之后，它很明显是正相关或负相关的。如果它是负相关，我们可以很轻易地将它转换成正相关，需要对ad vector加个负号就行。这样，我们可以将CTR预测问题reduce成一个cosine ranking问题，它是一个典型的ANN search setting。

ANN search的目标是：对于一个给定的query object，从一个大语料中检索到“最相似”的对象集合，只需要扫描corpus中的一小部分对象就行。这是个基础问题，已经在CS界广泛研究。通常，ANN的最流行算法是基于space-partitioning的思想，包括：tree-based方法、random hashing方法、quantiztion-based方法、random partition tree方法等。对于这类问题，我们发现，random partition tree方法相当高效。random partition tree方法的一个已知实现是：”ANNOY”。

3.2.2 MIPS （Maximum Inner Product Search）

在上面的解决方案中，business-related weight信息在user vector和ad vector matching之后被考虑。实际上，这个weight在ads ranking很重要。为了解释在ranking之前的这个weight信息，我们通过一个weighted cosine问题公式化成fast ranking过程，如下：

\[cos(x, y) \times w = \frac{x^T y \times x}{||x|| ||y||} = (\frac{x}{||x||})^T (\frac{y \times w}{||y||})\]

…(3)

其中：

• w是business related weight
• x是user-query embedding
• y是ad vector

注意，weighted cosine会造成一个inner product seraching问题，通常被称为MIPS。

3.2.3 向量压缩（Vector Compression）

为数十亿ads存储一个高维浮点feature vector会花费大量的disk space，如果这些features需要在内存中进行fast ranking时会造成很多问题。一个常见的解法是，将浮点feature vectors压缩成random binary（或integer） hash codes，或者quantized codes。压缩过程可以减小检索召回到一个范围内，但它会带来具大的存储优势。对于当前实现，我们会采用一外quantization-based方法（像K-Means）来将index vectors进行聚类，而非对index中的所有ad vectors进行ranking。当一个query到来时，我们首先会寻找query vector所分配的cluster，接着获取来自index属于相同cluster的ads。PQ的思路是，将vectors分割成许多subvectors，每个split独立进行cluster。在我们的CTR模型中，我们会将query embeddings和ad embeddings同时split成三个subvectors。接着每个vector被分配到一个关于cluster centroids的triplet上。例如，对于一个billion-scale ads的multi-index，可以使用\(10^9\)可能的cluster centroids。在Mobious-V1中，我们使用OPQ（Optimized Product Quantization）变种。

4.实验

略

参考

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

1.摘要

我们描述了一个实时竞价算法，来进行基于效果的展示广告分配。在效果展示广告中的核心问题是：匹配campaigns到广告曝光，它可以公式化成一个受限最优化问题（constrained optimization problem）：在有限的预算和库存下，可以最大化收益目标。当前实践是，在一个曝光粒度的可追踪级别上，离线求解最优化问题（例如：placement level），并且在预计算的静态分发模式下，基于online的方式服务广告。尽管离线方法会以全局视角来达到最优目标，但它不能扩展到以单个曝光级别上进行广告分发决策。因此，我们提出一个实时竞价算法，它可以细粒度地进行曝光评估（例如，使用实时转化数据来定向用户），并且根据实时约束（例如：预算消耗级别）来调整value-based的竞价。因此，我们展示了在一个LP（线性规划：linear programming ）的primal-dual公式，这种简单实时竞价算法确实是个在线解法，通过将dual problem的该最优解作为input，可以解决原始的主问题。换句话说，在给定与一个离线最优化的相同级别的经验下，在线算法会保障离线达到的最优化。经验上，我们会开发和实验两个实时竞价算法，来自适应市场的非稳态：一个方法会根据实时约束满意级别，使用控制理论方法来调整竞价；另一个方法则会基于历史竞价静态建模来调整竞价。最后，我们展示了实验结果。

1.介绍

略

2.背景

略

3.效果展示最优化：一个LP公式

为了为在线竞价生成基本算法形式，并且确立它的最优化（optimality），我们通过对基本效果展示广告最优化看成是一个LP问题。在基础设定中，曝光会被评估，并且单独分配，在demand-side侧约束下（例如：预算限制），会以曝光分发目标的形式给出。该公式会捕获所有的理论本质，并且实际的细微差异会在第6节被讨论。假设：我们首先定义以下概念：

• 1. i会索引n个曝光，j会索引m个campaigns
• 2.\(p_{ij}\)表示曝光i分配到campaign j上的CTR，\(q_j\)表示campaign j的CPC；\(v_{ij}=p_{ij}q_{j}\)是这种assignment的eCPI
• 3.\(g_j\)是campaign j的曝光分发目标
• 4.\(x_{ij}\)是决策变量，它表示曝光i是否分配到campaign j（\(x_{ij}=1\)）或不是（\(x_{ij}=0\)）

我们将如下LP公式化成primal：

\[max \sum_{ij} v_{ij} x_{ij} \\ s.t. \forall j, \sum_i x_{ij} \leq g_j, \\ \forall i, \sum_j x_{ij} \leq 1, \\ x_{ij} \leq 0\]

…(6)

dual problem接着：

\[min_{\alpha, \beta} \sum_j g_j \alpha_j + \sum_i \beta_i \\ s.t. \forall i, j, \alpha_j + \beta_i \gt v_{ij} \\ \alpha_j, \beta_i \gt 0\]

…(7)

重点注意的是：由于一个曝光，

5.1 基于控制论的竞价调整（bid adjustment）

基于经典控制理论的一个简单控制设计是，使用PI controller（proportialnal-intergral controller），这是proportional-integral-derivative (PID) controller的一种常用形式。据我们所知，在缺少低层过程的先验知识时，PID controller是最好的controller【3】。正式的，假设t表示time，\(r_j(t)\)和\(r'_j(t)\)分别是winning bids在time t上的期望概率（desired probabilities）和真实概率（observed probabilities）; \(e_j(t) = r_j(t) - r'_j(t)\)是在time t时的measure error。PI controller会采用如下形式：

\[\alpha_j(t+1) \leftarrow \alpha_j(t) - k_1 e_j(t) - k_2 \int_0^t e_j(\tau) d\tau\]

…(9)

这里:

• \(k_1\)是P项（比例增益：proportional gain）
• \(k_2\)是I项（积分增益：integeral gain）

两者都是待调参数。实际中，出于在线计算效率和曝光到达的离散性，time t不需要实时跟踪。假设：\(t \in [1, \cdots, T]\)会索引足够小的时间间隔（time intervals），其中T是在online bidding的整个duration内的intervals数目；在每个interval之后只会更新\(\alpha_j\)。

另一个更简单的控制方法：受水位标（Waterlevel）【4】的启发，在资源分配问题（resource allocation problems，比如：在保留位置上分发展示广告）上，有一个在线/快速近拟算法。waterlevel-based方法的更新公式：

\[\alpha_j(t+1) \leftarrow a_j(t) e^(\gamma (\frac{x_j(t)}{g_j} - \frac{1}{T})), /forall j\]

…(10) 其中：

• \(x_j(t)\)表示获胜的campaign j在time interval t期间的曝光数；
• 指数因子\(\gamma\)：是一个可调参数，它控制着算法根据erroe meaured \(\frac{x_j(t)}{g_j} - \frac{1}{T}\)来控制有多快。如果初始的\(\alpha_j\)（例如：由offline dual求解得到）对于未来的运行来说确实是最优的，我们希望将\(\gamma\)变为0

注意，在error项\(\frac{x_j(t)}{g_j} - \frac{1}{T}\)中，我们假设知道在time intervals上具有一个均匀的曝光流（impression stream）。该假设并不重要，因为它可以通过添加一个时间依赖先验（time-dependent prior）来被很容易地移除。另外，Water-based方法的更新具有一个很nice的链条特性：

\[\alhpa_j(t+1) = \alpha_j(t) exp(\gamma(x_j(t) / g_j - 1/T)) \\ = \alpha_j(t-1) exp(\gamma ( \sum\limits_{\tau=t-1}^t x_j(\tau) / g_j - 2/T)) \\ = ... \\ = a_j(1) exp(\gamma(\sum\limits_{\tau=1}^t x_j(\tau) / g_j - t/T))\]

…(11)

5.2 Model-based的竞价调整（Bid Adjustment）

我们的model-based方法从现代控制理论【9】中抽理出来，其中系统（在我们的case中是竞价市场）状态的一个数学模型是，用于生成一个控制信号（在我们的case为：竞价调整\(\alpha_j\)）。更正式的，我们会假设：在胜选竞价（winning bids）上有一个参数分布P：

\[w \sim P(\theta)\]

…(12)

其中，\(\theta\)是模型参数。我们使用泛化形式，因为一个合适参数选择应通过数据来进行经验调节，并且可能是domain-dependent的。一些合理的选择是：在winning bids【13】的square-root（均方根）上有一个log-normal分布【7】以及一个Gaussian分布，但两者都不可以天然处理negative bids。在我们竞价调整的加法形式如等式（3），一个negative bid \(b_{ij} = v_{ij} - \alpha_j < 0\)意味着：竞价者（bidder）不能满足由acquiring impression i的最小间隔，因而展示了整个value book的一个hidden part。我们：

• 将概率分布函数PDF表示成\(f(w;\theta)\)
• 将累积分布函数CDF表示成\(F(w;\theta)\)
• inverse CDF(逆函数)表示为\(F^{-1}(p; \theta)\)。
• 分布参数\(\theta\)的MLE由历史胜选竞价{w}的充分统计得到，它可以在线更新可读（例如：第一，第二时刻）。有了bidding landscape的静态模型后，我们可以通过使用bidding \(b_{ij} = v_{ij} - \alpha_j\)生成获胜概率：

\[p(w \leq b_{ij}) = \int_{-\inf}^{b_{ij}} f(w;\theta) dw = F(b_{ij}; \theta)\]

假设：对于所有impression i来说，winning bids会遵循一个单一分布是不现实的（通常是一个mixture model）。因此对于来自一个位置（placement）的一组同质曝光（homogeneous impressions）来说，会满足分布\(P(\theta)\)。实际上，我们会使用impression granularity level来安排\(P(\theta)\)，它同时具有supply-side和demand-side的拘束。现在假设我们只关注异构曝光（homogeneous impressions）。

我们希望将学到的胜选概率（winning probability）与未来的竞价行为相联系，来达到分发目标。假设：\(r_j\)是赢得剩余曝光的期望概率，表示campaign j满足目标\(g_j\)。在未来曝光i上，会尝试使用\(b_{ij} = F^{-1}(r_j;\theta)\)来竞价。然而，这种纯基于目标的方法，在使用feedback来显式控制future bids时会失败，因为会丢掉closed-loop controller（PID controller）上具有的稳定性、健壮性等优点来建模不确定性。换句话说，纯目标驱动的方法不会学到过往竞价（past bidding）做出的errors。我们提出一个model-based controller来解决该限制，并且利用由bidding landscape学到的知识。竞价调整的公式如下：

\[\alpha_j(t+1) \leftarrow \alpha_j(t) - \gamma(F^{-1}(r_j(t)) - F^{-1}(r_j^' (t))), \forall j\]

…(14)

其中，\(r_j(t)\)和\(r_j^'(t)\)分别是在time t上的期望胜选概率和真实胜选概率。乘法因子\(\gamma\)是一个可调参数，它控制着在对应于errors的一次更新上做出的rate。对于经典方法，model-based方法不会直接操作measured errors；作为替代，它会通过一个compact model \((P(\theta))\)来将一个error signal（获胜概率error）转换成一个control signal（updated \(\alpha_j\)）。

当缺少一个好的参数时这种方式不好，一个非参数模型在也可以使用。我们需要维护一个empirical CDF作为一个two-way lookup table \((F(w;D)和F^{-1}(p;D))\)来进行online inference。

6.效果展示广告优化：一个实际公式

我们已经开发了在算法1中的基本算法形式，并确定了在给定稳定曝光到达假设下的最优解。在基本的LP公式下，constraints会被编码成impression分发目标，曝光会被单独进行分配和评估。我们将LP问题直接使用商业约束进行公式化，主要是：demand-side预算限制以及supply-side的库存量；接着讨论在真实系统中要考虑的几个方面。假设我们首先更新以下概念：

• 1.i表示索引n个impression groups（比如：placements），在一个group中的impressions会被看成是不可区分的，因而对于给定一个campaign来说会生成一个相同的CTR估计。
• 2.\(g_j\)是对于campaign j的预算最高限额（budget cap）
• 3.\(h_i\)表示对于group i来说的曝光量限制或预测
• 4.\(x_{ij}\)表示：来自group i分配给campaign j的曝光数
• 5.\(w_i\)：表示来自group i的每次曝光的（traffic acquisition）开销（cost），例如：在Vickrey acution中的第二价格

注意：我们会在同一个解法中做出CTR预测和supply constraint。避免刮脂效应(cream-skimming)问题很重要。如果CTR预估比起即时的supply constraint来说更细粒度，一个optimization方法是，在每个impression group总是分配impressions更高的CTR机会，这很明显是不现实的。我们会引入cost term \(w_i\)来泛化生成optimization给其它players，例如：参与到一个second-prece auction的一个ad network或者demand-side平台。primal LP变为：

\[max_x \sum_{i,j} (v_{ij} - w_{i}) x_{ij} \\ s.t. \forall j, \sum_j v_{ij} x_{ij} \leq g_j, \\ \forall i, \sum_j x_{ij} \leq h_i, \\ x_{ij} \gt 0\]

接着该dual problem是：

\[min_{\alpha, \beta} \sum_j g_j \alpha_j + \sum_i h_i \beta_i \\\]

6.实验评估

参考

• 1.https://www.nikhildevanur.com/pubs/rtb-perf.pdf

2015年yahoo在《Smart Pacing for Effective Online Ad Campaign Optimization》提出了一种smart pacing的策略。

0.摘要

在定向广告中，广告主会在预算范围内在分发约束的情况下最大化竞价效果。大多数广告主通常喜欢引入分发约束（delivery constraint）来随时间平滑地花费预算，以便触达更广范围的受众，并具有持续性的影响。对于在线广告，由于许多曝光会通过公开竞拍(public auctions)来进行交易，流动性（liquidity）使得价格更具弹性，在需求方和供给方间的投标景观（bid landscape）会动态变化。因此，对于同时执行平滑步调控制（smooth pacing control）并且最大化竞价效果很具挑战。本文中提出了一种smart pacing方法，它会同时从离线和在线数据中学习每个campaign的分发步调（delivery pace），来达到平滑分发和最优化效果目标。我们也在真实DSP系统中实现了该方法。实验表明，在线广告活动（online ad campaign）和离线模拟都表明我们的方法可以有效提升campaign效果，并能达到分布目标。

1.介绍

在线广告是一个数十亿美金的产业，并且在最近几年持续两位数增长。市场见证了搜索广告（search advertising）、上下文广告（ contextual advertising）、保证展示广告(guaranteed display advertising)、以及最近的基于竞价的广告的出现。我们主要关注基于竞价的广告（auction-based），它具有最高的流动性，例如：每次ad曝光可以通过一个公开竞价使用一个不同的价格来交易。在市场中，DSPs（Demand-Side Platforms ）是个关键角色，它扮演着大量广告主的代理，并通过许多direct ad-network 或者RTB（实时竞价）广告交换来获得不同的广告曝光，来管理ad campaigns的整个welfare。一个广告主在一个DSP上的目标可以归为：

• 达到分发和效果目标：对于品牌活动（branding campaigns），目标通常是花费预算来达到一个广泛受众、同时使得活动效果尽可能好；对于效果活动（performance campaigns），目标通常是达到一个performance目标（比如：eCPC <= 2美元），并同时尽可能花费越多预算。其它campaigns的目标通常在这两个极端之内。

• 执行预算花费计划(budget spending plan)：广告主通常期望它们的广告会在购买周期内平滑展示，以便达到一个更广的受众，可以有持续性影响，并在其它媒介上（TV和杂志）增加活动。因此，广告主可以定制自己的预算花费计划（budget spending plans）。图1给出了budget spending plan的两个示例：平均步调（even pacing）和基于流量的步调（traffic based pacing）。

图1 不同的预算花费计划

• 减少创意服务开销（creative serving cost）：除了通过由DSPs负责的开销外，也存在由第3方创意服务提供商负责的creative serving cost。现在，越来越多的广告活动会以视频或富媒体的形式出现。这种类型的曝光的creative serving cost可以与优质存货开销（premium inventory cost）一样多，因此，广告主总是愿意减少这样的开销，并且来高效和有效地分发曝光给合适的用户。

3.问题公式化

我们关注两个campaign类型： 1) 品牌广告（branding campaigns） 2) 效果广告（performance campaigns）。其它campaign类型位于两个之间。这些类型的campaign可以具有它自己唯一的budget spending plan。我们首先将该问题公式化来解决，接着给出我们的解法。

3.1 前提

假设Ad是一个ad campaign，B是Ad的预算，G是Ad的效果目标。spending plan是一个随着由K个time slots构成的预算序列，表示在每个time slot上待花费的期望预算数目。我们将AD的spending plan表示为：

\[B = (B^{(1)}, \cdots, B^{(K)})\]

其中，\(B^{(t)} >= 0\)并且 \(\sum_{t=1,\cdots,K} B^{(k)} = B\)。假设\(Req_i\)是由一个DSP接受到的第i个ad request。如第2节所述，我们使用概率节流（probabilistic throttling）来进行budget pacing control。我们表示为：

• \(s_i \sim Bern(r_i)\)：该变量表示：在\(Req_i\)上Ad是否参与竞价。其中：\(r_i\)是在\(Req_i\)上的point pacing rate。\(r_i \in [0, 1]\)表示Ad参与\(Req_i\)上竞价的概率。

• \(w_i\)：该变量表示在\(Req_i\)上参与该次竞价时是否赢得该Ad。它会依赖于通过竞价最优化模块（bid optimization module）给出的竞价\(bid_i\)

• \(c_i\)：当Ad服务于\(Req_i\)时的广告主开销。注意：开销包括inventory cost和creative serving cost。

• \(q_i \sim Bern(p_i)\)：该变量表示当Ad服务于\(Req_i\)时，用户是否会执行一些期望的响应（例如：click）。其中\(p_i = Pr(respond \mid Req_i, Ad)\)是这些响应的概率。

• \(C = \sum_i s_i \times w_i \times c_i\)是ad campaign Ad的总开销。

• \(P=C/\sum_i s_i \times w_i \times q_i\)：ad campaign Ad的效果（performance）（例如：当期望响应是点击时的eCPC）

• \(C = (C^{(1)}, \cdots, C^{(k)})\)：在K个time slots上的spending pattern，其中\(C^{(t)}\)是第t个time slot的开销，\(C^{(t)} >= 0\)并且\(\sum_{t=1,\cdots,K} C^{(k)} = C\)

给定一个广告活动Ad，我们定义：\(\Omega\)是penalty(error) function，它会捕获spending pattern C是如何偏离spending plan B。值越小表示对齐（alignment）越好。作为示例，我们会将penalty定义如下：

\[\Omega (C, B) = \sqrt \frac{1}{K} \sum\limits_{t=1}^K (C^{(t)} - B^{(t)})^2\]

…(1)

3.2 在线广告campaign最优化的Smart Pacing问题

广告主会花费预算，执行spending plan，并同时最优化campaign效果。然而，这样的一个抽象的多目标最优化问题，会有多个帕累托最优解（Pareto optimal solutions）。在真实场景中，广告主通常会为不同campaigns对这些目标定制优化级。对于品牌广告（branding campaigns），广告主通常会将花费预算放在最高优化级，接着是spending plan，而对效果并不很关注。在serving time时（例如：ad request time），由于我们使用概率节流（probabilistic throttling），我们完全可以控制的唯一东西是\(r_i\)。因而，对于没有指定效果目标的ad campaigns的smart pacing问题(smart pacing for ad campaigns without specific performance goals)定义为：决定\(r_i\)的值，以便以下的测算是最优的：

\[\underset{r_i}{min} P \\ s.t. C = B, \Omega (C,B) \leq \epsilon\]

…(2)

其中，\(\epsilon\)定义了违背spending plan的容忍度。相反的，对于效果广告（performance campaigns）具有指定的效果目标，达成效果目标是top优先级。此时坚持spending plan通常是低优先的。我们将smart pacing for ad campaigns with specific performance goals的问题定义为：决定\(r_i\)的值，以便以下测算是最优的：

\[\underset{r_i}{min} \Omega(C, B) \\ s.t. P <= G, B - C \leq \epsilon\]

…(3)

其中，\(\epsilon\)定义了没有花光所有预算的容忍度。由于市场的动态性，对于两个单目标最优化问题很难解决。在工业界已存在被广泛使用的方法，只会捕获效果目标，或者只会捕获预算花完目标。达到效果目标的一个示例是：对retargeting beacon触发ad requests，总是竞价。不幸的是，避免过度消费（overspending）或者欠消费（underspending）是无保障的。对于平滑步调控制（smooth pacing control）的另一个示例是，引入一个全局pacing rate，以便ad requests具有相同的概率被一个campaign竞价。然而，这些已经存在的方法没有一个可以解决我们公式化的smart pacing问题。为了解决该问题，我们研究了流行的campaign setups，并做出一些关键观察（可以启发我们的解法）：

• CPM campaigns：广告主对于每个曝光会会付定固定数目的钱。对于品牌广告主（branding advertisers），campaign最优化的定义如公式2所示。只要预算可以被花费，并且spending pattern会随plan安排，高响应广告请求会比低响应的具有一个更高的point pacing rate，以便效果可以被最优化。对于效果广告主（performance advertisers，例如：eCPC、eCPA为目标），campaign最优化的定义如公式3所示。很明显，高响应的ad requerest应具有更高的point pacing rate来达到performance目标。

• CPC/CPA campaigns：广告主会基于clicks/actions的绝对数目进行付费。显式效果目标是，保证当代表广告主进行竞价时，DSP不会损失钱。因此，这种optimzation的定义为等式(3)。授于高responding ad request以高point pacing rates，从广告主和DSP的视角来说会更有效：广告主会在creative serving cost上花费更少，而DSP可以节省更多ad机会来服务其它campaigns。

• 动态CPM campaigns：DSP会为每个曝光花费一个动态数目的钱，而非固定。这些campaigns通常具有指定效目的目标，以便最优化问题会落在等式(3) 中。与CPC/CPA campaigns相似，高responding ad requests会更受偏爱，以便减少creative serving cost以及节约ad机会。

3.4 解法汇总

受这些观察的启发，我们开发了新的heuristics来求解smart pacing问题。该heuristics尝试找到一个可行解，它会满足如等式2或3定义的所有constraints，接着进一步通过feedback control来最优化目标。

• 首先从离线服务日志中构建一个response prediction模型来估计\(p_i = Pr(respond \mid Req_i, Ad)\)，它会帮助我们区分高响应广告请求 和 低响应广告请求。
• 第二，我们会通过将相似的响应请求group在一起来减小solution space，并且在相同group中的请求会共享相同的group pacing rate。使用高responding rates的groups会具有高的pacing rates（比如图2(a)中的蓝色箭头）。
• 第三，我们会开发一个新的control-based的方法来从在线feedback data中学习，并能动态调整group pacing rates来逼近最优解。

不失一般性，我们假设campaign setup是具有/没有一个eCPC目标的CPM计费。我们的方法可以应用到其它计费（billing）方法上 ，效果广告或者其它grouping策略，比如：基于\(p_i/c_i\)的grouping。（期望的response per cost）

图2 概率节流（Probabilistic Throttling） vs. 竞价修改（Bid Modification）的因子依赖图。灰色的因子涉及到budget pacing control。在pacing rate和response rate间添加依赖是其中一个关键点.

4.response预测

我们的解法依赖于一个准确的response prediction模型来预估\(p_i\)。如第2节，有许多文献解决该问题。这里我们简单描述了如何执行该预估。我们会使用在(2,11)中的方法，并基于它做出一些改进。在这种方法中，我们首先利用在数据中的层次结构来收集具有不同间隔的response feedback features。例如，在ad侧，从root开始，接着一层接一层是：advertiser category，advertiser，campaign，最后是ad。在层次结构的不同levels上的历史响应率（historical response rates）可以当作features来使用机器学习模型（LR、gbdt等）来给出一个\(p_i\)的原始预估（raw estimation），称为\(\hat{p}_i\)。接着我们使用属性（比如：用户的age、gender）来构建一个shallow tree。树的每个叶子节点标识一个关于ad requests的不相交集合，它可以进一步划分成具有不同平均响应率的子集。最后，我们会在叶子节点\(Req_i\)内对\(\hat{p}_i\)进行微调，使用一个piecewise linear regression来估计最终的\(p_i\)。该scheme会生成一个公平的accurate response prediction。

5.control-based的解法

在一个在线环境中，很难达到完全最优解来解决等式（2）和等式（3）的问题。我们采用启发法来减小原始问题的解空间。更特别的，使用第4节中描述的response prediction模型，相似的，responding ad requests会分组到一起，他们会共享相同的group pacing rate。不同分组会具有不同的group pacing rates来影响在高responding ad request groups上的偏好。原始问题（求解每个\(r_i\)的point pacing rate）会简化成求解一个group pacing rates的集合。我们会采用control-based的方法来调节group pacing rates以便online feedback data可以立即用于campaign最优化。换句话说，group pacing rates会通过campaign的生命周期动态调节。出于简洁性，在本文其它地方，pacing rate和group pacing rate会相通，我们会在第l个group的group pacing rate表示为\(r_l\)。

5.1 层级表示（Layered Presentation）

对于每个ad campaign，我们会维护一个层级数据结构，其中每层对应于一个ad request group。我们会以层级数据结构来保存每个ad request group的以下信息：

• 平均响应率（通常是：CTR、AR等，它来自response prediction模型）
• ad request group的优先级
• pacing rate（例如：在ad request group中对一个ad request的竞价概率）
• campaign在该ad request group中在最新time slot上的花费

这里的原则是：

• 1) 对应于高响应ad request groups的layers应具有高优先级
• 2) 高优先级layer的pacing rate应会比一个低优先级layer要更小

对于每个campaign，当DSP接收到一个合格的ad request时，它会首先决定：该ad request 会落在哪个ad request group上，指的是相应的layer来获得该pacing rate。DSP接着会代表campaign来竞价，它的概率会等于由一个preceding bid 最优化模块给出的retrieved pacing rate。

5.2 Online Pacing Rate调节

我们基于实时反馈，来采用一个control-based方法来调节每层的pacing rate。假设我们具有L个layers。对于每个layer，由response prediction model给出的response rate预估是：

\[p=(p_1, \cdots, p_L)\]

这里，如果期望的response是click，那么预估的每层的eCPC是:

\[e(e_1, \cdots, e_L)\]

其中：\(e_i = \frac{CPM}{ 1000 \times p_i}\)。假设每层的pacing rate在第t-1个time slot上是：

\[r^{(t-1)} = (r_1^{(t-1)}, \cdots, r_L^{(t-1)})\]

那么，每个layer的spending为：

\[c^{(t-1)} = (c_1^{(t-1)}, \cdots, c_L^{(t-1)})\]

对于将要到来的第t个 time slot会基于campaign目标，control-based的方法会预估：

\[r^{(t)} = (r_1^{(t)}, , \cdots, r_L^{(t)})\]

图3 加速budget spending的一个示例

5.2.1 没有performance目标的Campaigns

我们首先描述对于没有指定效果目标的ad campaigns的微调算法。对于这种campaign类型，首要目标是花费预算，并根据budget spending plan进行安排。因而，在每个time slot的end，算法需要决定在下一个time slot中的预算量，并调整layered pacing rates来花费该量。

在下一time slot中的待花费预算，由当前预算花费状态来决定。给定一个ad campaign，假设它的总预算是B，budget spending plan是\(B = (B^{(1)}, \cdots, B^{(K)})\)，在运行m个time slots后，剩余预算变为\(B_m\)。我们需要决定在每个剩余time slots中的花费，表示为\(\hat{C}^{m+1}, \cdots, \hat{C}^{(K)}\)，以便总预算可以花完，penalty最小。

\[\underset{\hat{C}^{(m+1)}, \cdots, \hat{C}^{(K)}}{arg min \Omega} \\ s.t. \sum\limits_{t=m+1}^k \hat{C}^{(t)} = B_m\]

…(4)

其中，如果我们采用等式（1）的\(\Omega\)定义，我们具有以下的最优化公式：

\[\hat{C}^{(t)} = B^{(t)} + \frac{B_m - \sum_{t=m+1}^K B^{(t)}}{K - m}\]

…(5)

其中，\(t=m+1, \cdots, K\)。我们会触发该细节：由于页面限制，如何估计\(\hat{C}^{(t)}\)。在在线环境中，假设在最新的time slot中的实际花费是\(C^{(t-1)}\)，我们定义\(R=\hat{C}^{(t)} - C^{(t-1)}\)是residual，它可以帮助我们来做出调整决策。

算法1

算法1给出了adujstment是如何完成的。假设：index L表示最高优先级，index 1表示最低优先级，假设\(l'\)是具有非零pacing rate的最后一层。

• 如果R=0, 则不需要做adjustment。
• 如果R>0，这意味着需要加速分发，pacing rates会以一种自上而下的方式进行调整。

从第L层开始，每一层的pacing rate会随层数一层层增加，直到第\(l'\)层。第5行会计算当前层的期望pacing rate，为了offset R。当第\(l' \neq 1\)时并且它的updated pacing rate \(r_{l'}^{(t)} > trial \ rate\)时，我们给第\(l' - 1\)层一个trial rate来准备进一步加速，如果R< 0，这意味着分发会变慢，每一层的pacing rate会以自底向上的方式减小，直接R是offset。第11行会生成当前layer到offset R的期望的pacing rate。假设l是最后要调的layer，\(l \neq 1\)和它的新的pacing rate \(r_l^{(t)} > trial \ rate\)，我们会给出第\(l-1\)层的trail rate来准备进一步加速。图4是一个分发如何变慢 的示例。

图4 一个减少budget spending的示例

我们注意到，在在线环境中，该greedy策略会尝试达到等式（2）的最优解。在每个time slot内，它会努力投资inventories，并在总预算和speding plan约束下具有最好的效果。

5.2.2 具有效果目标的Campaigns

对于指定效果目标的campaigns（例如：eCPC <=2美元），pacing rate adjustment是有点复杂。很难预见在所有未来time slots内的ad request traffic，并且response rate分布可以随时间变化。因此，给定预算花费目标，利用在当前time slot中的所有ad requests，它们满足效果目标，不是等式（3）的最优解。算法2描述了对于这种类型的campaigns如何来完成adjustment。我们采用heuristic来进一步基于效果目标进行adjustment，它会添加到算法1中。

算法2

如果在算法1后的期望效果不满足效果目标，pacing rates会从低优先级layers one-by-one的减少，直到期望效果满足目标。第7行会生成current layer的期望pacing rate，并使整体期望eCPC满足目标。在第2行，第4行的函数\(ExpPerf(c^{(t-1), r^{(t-1)}, r^{(t)}, e, i}\)会估计layers \(i, cdots, L\)的期望联合eCPC，如果pacing rates会从\(r^{(t-1)}\)调整到\(r^{(t)}\)，其中，\(e_j\)是layer j的eCPC。

\[ExpPerf(c^{(t-1)}, r^{(t-1)}, r^{(t)}, e, i) = \frac{\sum\limits_{j=i}^L \frac{c_j^{(t-1) \times r_j^{(t)}}{r_j^{(t-1)}}}}{\sum\limits_{j=i}^L} \frac{c_j^{(t-1)} \times r_j^{(t)}}{ r_j^{(t-1)} \times e_j }}\]

…(6)

5.3 Layers的数目，初始化和Trial Rates

设置layers的数目，intial和trial pacing rates很重要。对于一个新的ad campaign，它没有任何分发数据，我们在DSP中标识出最相似的最已存在ad campaigns，并估计一个合适的全局pacing rate \(r_G\)，我们期望新的campaign可以花完它的预算。接着layers的数目设置为\(L = [\frac{1}{r_G}]\)。我们表示：一个合适数目的layers要比过多数目的layer更重要：

• 1) 如果有许多层，每个layer的分发统计并不重要
• 2) 从系统角度看，过多数目的layers会使用更多宽带和内存

一旦layers的数目决定后，我们会在第一个time slot上运行全局pacing rate \(r_G\)。我们将该step称为一个intialization phase，这里分发数据可以被收集。我们将相同数目的曝光，基于它们的预测response rate来来标识layer分界，将它们分组（group）到期望数目的layers上。在下一time slot上，每一layer的pacing rate会基于在下一time slot的计划预算来重新分配，高响应layers会具有1.0的rates，而低响应layers将会具有0.0的rates。

在adjustment算法中，具有非零pacing rate相互挨着的直接连续的layer，会分配一个trial pacing rate。目标是在该layer收集分发数据，并准备将来加速。该trial rate假设相当低。我们通过保留预算的一个特定比例\(\lambda, e.g. \lambda=1%\)，生成这样一个rate，来在下一time slot中花费。假设trial layer是第l层，下一time slot上的预算是\(\hat{C}^{(t)}\)，我们会在至少一个time slot（初始阶段）上具有该layer的历史花费和pacing rate，trial pacing rate会生成：\(trial \ rate = r_l^{(*)} \times \frac{\lambda \times \hat{C}^{(t)}}{c_l^{(*)}}\)，其中：\(c_l^{(*)}\)和\(r_l^{(*)}\)是第l层的历史花费，以及pacing rate。

快速总结下，我们采用一个基于predicted response rate生成的关于所有ad requests的分层表示，并在每个layer level上执行budget pacing control来达到分发和效果目标。在当前time slot上的预算，以及剩余预算会被考虑来计算在下一time slot上的layered pacing rates。我们也尝试另一种方法来控制一个threshold，以便超过该threshold的predicted response rate的ad requests可以竞价。这种方法的缺点是不能令人满意。主要 原因是，ad requests通常不随response rate平滑分布，因此，在单个threshold上很难实现平滑控制。

6.实验评估

参考

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

华为在《PAL: a position-bias aware learning framework for CTR prediction in live recommender systems》提出了一种解决position-bias方法。

摘要

在推荐系统中精准预测CTR很重要。CTR模型通常基于来自traffic logs收集得到的feedback训练得到。然而，在user feedback中存在position bias，因为用户在一个item上的点击(clicks)不仅仅只因为用户喜欢这个item，还有可能是因为它具有一个较好的position。解决该问题的一种方式是：在训练数据中将position建模成一个feature。由于很简单，这种方法在工作界被广泛应用。然而，使用不同的default position值可能会导型完全不同的推荐结果。因些，该方法会导致次优(sub-optimal)的线上效果。为了解决该问题，在该paper中，我们提出了一种Position Aware Learning framework（PAL）来解决该问题。它可以建模在offline training中的position-bias，并在online inference时不使用position information。我们在一个三周的AB test上进行实验，结果表明，PAL的效果在CTR和CVR（转化率ConVersion Rate）指标上要比baseline好3%-35%。

1.介绍

实际生产环境中的推荐系统包含两个过程：offline training和online inference，如图2所示。在offline training中，会基于从traffic logs中收集到的user-item interaction信息训练一个CTR预估模型。在online inference中，训练好的模型会部署到真实线上来做出预测。

图2 不同position上的CTR

有个问题是：user-item interaction是受展示该item的positions影响的。在[14]中，CTR会随着display position而快速下降。相似的，我们也在华为maintream APP store上观察到了这样的现象。如图1所示，不管是整体的App Store (图1(a))，或是单个特定App（图1(b)），我们可以观察到：normalized CTR会随着position显著下降。

图1 生成推荐的workflow

这样的观察表明，用户点击某个item可能不仅仅是因为喜欢这个item，还有可能是因为在一个好的position上。因此，从traffic logs中收集得到的training data包含了positional bias。我们将该现象称为“position-bias”。作为CTR信号的一个重要因子，在offline training中将position-bias建模到CTR预测模型中是很必要的。

尽管提出了许多click models来建模training data中的position-bias【1-3】，在现实问题中（在online inference中position信息是不提供的）这样的研究很有限。一个实用（practical）的方法是逆倾向加权（inverse propensity weighting）【15】。在该方法中，在position信息使用一个用户定义的转换，接着该转换后的值固定。然而，如【10】所述，对于position信息很难设计一个好的转换，这会产生比自动学到的转换更差的效果。因此，【10】的作者提出在训练数据中将position建模成一个feature，这种方法在工业界广泛使用。特别的，在online inference中使用一个default position value来预测CTR，因为actual position information在那时并没提供。不幸的是，使用不同的default position values可能会导致完全不同的推荐效果，这会导致生成一个次优的online performance。

在本paper中，我们提出了PAL来建模position-bias。PAL的思想基于以下假设：一个item被用户点击基于两个因素（假设item被user看到）：

• a) item被用户看到的概率
• b) 用户在该item上点击的概率

上面的每个factor在PAL中会被建模块“as a module”，这两个modules的outputs是一个item被用户点击的概率。如果两个modules单独进行optimzied，它会导致整个系统达到一个次优的状态，因为两个modules的training objectves间不一致性（inconsistency），正如[18]中所述。为了避免这样的限制，并生成更好的CTR预测效果，PAL中的两个modules会同时进行jointly optimized。一旦这两个modules在offline training下训练完全成，第二个module可以部署到online inference上来预测CTR。

2.方法

2.1 概念

我们假设：offline的点击数据集为 ：\(S = \lbrace (x_i, pos_i \rightarrow y_i) \rbrace_{i=1}^N\)

其中：

• N：是总样本数
• \(x_i\)：是样本i的feature vector，它包含了：user profile, item features和context信息
• \(pos_i\)：是样本i的position信息
• \(y_i\)：是user feedback（如果user在该item进行点击，则\(y_i=1\)；否则\(y_i=0\)）

我们会使用x，pos，和y来分别表示feature vector、position信息和label。

2.2 Preliminary

有两种方法对在offline training中的position-bias进行建模，称为“as a feature”和”as a module”。

As a feature

该方法会将position信息建模成一个feature。在offline training中，CTR模型的input feature vector是x和pos的concatenation，例如：\(\hat{x} = [x, pos]\)。然后基于该concatenated feature vector训练一个CTR预测模型。

由于position信息被建模成offline training中的一个feature，在online inference中也应包含一个表示“position”的feature，如图3的右侧所示。然而当执行online inference时，position信息是不提供的。一种解决该问题(在inference时缺失该position)的方法是：为每个position，按top-most position到bottom-most position顺序，判断最适合的item。可以分析得到，brute-force方法具有\(O(l n T)\)的时间复杂度（其中：l是ranking list的长度，n是candidate items的数目，T是inference的latency），它对于一个低延迟的在线环境来说是不可接受的。

图3 PAL framework vs. BASE

为了减短延时，可选择一种【10】中描述的具有O(nT)复杂度的方法，它会为所有items选择一个position来作为position feature的值。然而，不同的position value会产生完全不同的推荐结果。因此，我们需要寻找一个合适的position值来达到好的online performance。这里有两种方法来比较使用不同position values进行inference的效果： online experiment和offline evaluation。前者很好，但代价高。因此，我们必须采用offline evaluation来选择合适的position value。另外，不管是使用online experiment或offline evaluation来选择position value，它都不具备良好的泛化特性，因为对于某一个应用场景的online inferenece的position value并不适用于另一个场景。

As a module

为了解决将position信息作为一个feature的上述缺陷，我们提出了一个新的框架来将position信息作为一个module，因此，我们可以在offline training中建模position-bias，并在没有position信息的online inferenece中使用。

3.PAL Framework

我们的framework受以下假设的启发：一个item被一个用户点击，只因为被该用户看到了。更特别的，给定item被用户看到，那么我们认为用户点击一个item的概率依赖于两个因素：

• a) item被用户看到的概率
• b) 用户在该item上被点击的概率

如等式(1)所示：

\[p(y=1 | x, pos) = p(seen | x, pos) p(y = 1 | x, pos, seen)\]

…(1)

如果我们进一步假设（注意：此处为PAL的关键假设）：

• a) 一个item已经被看到(seen)的概率只与该相关position被观察到的概率相关
• b) 一个item被点击(click)的概率与该position是否被看到(seen)相互独立

那么，等式(1)被简化成等式(2) ：

\[p(y=1 | x, pos) = p(seen | pos) p(y=1 | x, seen)\]

…(2)

如图3左侧所示，我们的PAL框架基于等式(2)设计，并包含了两个modules：

• ProbSeen：第一个module会对概率\(p(seen \mid pos)\)建模，它通过图3中的”ProbSeen”进行表示，将position信息pos作为input
• pCTR：第二个module会对概率\(p(y=1 \mid x, seen)\)进行建模，它表示了图3中的”pCTR”，表示该模型predicted CTR。它的输入是training data中的feature vector x。

任意CTR预测模型（比如：linear models和deep learning models）都可以应用于这两个modules上。

接着，学到的CTR被表示成图3中的”bCTR”，它会将在offline training中的position bias认为是这两个modules的输出的乘积。如【18】所示，如果两个modules被单独进行优化，不同的training objectives间的不一致（inconsistency）会导致整体系统达到一个次优（sub-optimal）的状态。为了避免这样的次优（sub-optimal）效果，我们在该framework中会对这两个modules进行jointly和simultaneously训练。更特别的，PAL的loss function被定义成：

\[L(\theta_{ps}, \theta_{pCTR}) = \frac{1}{N} \sum\limits_{i=1}^N l(y_i, bCTR_i) = \frac{1}{N} \sum\limits_{i=1}^N l(y_i, ProbSeen_i \times pCTR_i)\]

…(3)

其中，\(\theta_{ps}\)和\(\theta_{pCTR}\)分别是ProbSeen module和pCTR module的参数，其中\(l(\cdot)\)是cross-entropy loss function。pCTR module，被用于online inference过程，并不会被直接最优化。实际上，当label和predicted bCTR间的logloss最小化时，ProbSeen和pCTR modules的参数可以如等式(4)和等式(5)通过SGD进行最优化，以便position-bias和user preference的影响会分别被隐式学到。

\[\theta_{ps} = \theta_{ps} - \eta \cdot \frac{1}{N} \sum\limits_{i=1}^N (bCTR_i - y_i) \cdot pCTR_i \cdot \frac{\partial ProbSeen_i}{\partial \theta_{ps}}\]

…(4)

\[\theta_{pCTR} = \theta_{pCTR} - \eta \cdot \frac{1}{N} \sum\limits_{i=1}^N (bCTR_i - y_i) \cdot ProbSeen_i \cdot \frac{\partial pCTR_i}{\partial \theta_{pCTR}}\]

…(5)

在offline training过程中，与[5,13,16]相似，early stop策略被用在训练过程中来获得well-trained model。一旦PAL被well-trained，module pCTR可以被部署到线上进行CTR inference。很容易观察到：position在PAL中的pCTR module并不需要，因此，我们不需要像“as a feature”那样在online inference时分配position values。

3.在线实验

在真实推荐系统中设计在线实验来验证PAL的效果。特别的，我们使用一个三周的AB test来验证PAL vs. “as a feature”的baseline方式。AB test在Company X的app Store的游戏中心的游戏推荐场景进行。

3.1 Datasets

在CompanyX的AppStore生产环境中，我们从traffic logs中抽样了10亿样本作为offline training dataset。为了更新我们的模型，training dataset以一个sliding time-window style的方式进行refresh。training的features包含了app features（例如：app id, category 等）、user features（比如：downloaded、click history等）、context features（例如：操作时间等）。

3.2 Baseline

baseline framework指的是“as a feature”策略。实际上，该baseline采用的是在[10]中的方法。正如所声明的，我们需要选择一个合适的position value作为online inference。然而，由于资源有限，对于使用所有可能positions来评估baseline framework是不可能的。因此，我们会选择合适的positions来进行offline experiment。

Settings。为了选择合适的position(s)，我们收集了两个场景的数据集(dataset 1和dataset 2)。test dataset通过next day的traffic logs中收集得到。我们在test dataset中使用不同的position values，范围从position 1到position 10. 与[5,11,13,16]相似，采用AUC和LogLoss来作为metrics对离线效果进行评估。

结果和分析。offline实验的结果如图5所示，其中Base_pk是具有position value k的baseline framework，它会为test data中的所有items分配该值。PAL框架所使用的test data没有position values。从图5看到，分配不同position values，AUC和LogLoss值在test data上变化很大。另外，BASE_p9可以达到最高的AUC，BASE_p5可以达到最低的LogLoss，Base_p1可以在AUC和LogLoss上同时达到最差的效果。我们选择最好的（BASE_p5和BASE_p9）以及最差的（BASE_p1）这两个作为baselines来做与PAL做online ABtest。值得注意的是，PAL在offline experiment中对于AUC或LogLoss均不会达到最好的效果。

图5 offline实验结果

3.3 AB test

Settings。对于control group，2%的用户被随机选中，并使用baseline framework生成的推荐结果进行呈现。对于experimental group，2%的users使用PAL生成的推荐结果进行呈现。在baseline和PAL中使用的模型是DeepFM，并使用相同的网络结构和相同的特征集。由于资源限制，我们不会在同一时间部署三个baseline（BASE_p1, BASE_p5和BASE_p9）。相反的，他们只会一个接一个地部署，每个轮流一周时间，来对比PAL。更特别的，我们会在每周分别对比PAL vs. BASE_p1､ PAL vs. BASE_p5､PAL vs. BASE_p9.

Metrics

我们采用两种metrics来对比PAL和baselines的在线效果，称为：

• 实际CTR（realistic CTR）：\(rCTR = \frac{\#downloads}{\#impressions}\)
• 实际转化率（realistic Conversion Rate）：\(rCVR = \frac{\#downloads}{\#users}\)

其中：#downloads, #impressions 以及 #users分别表示天级别的下载数、曝光数、访问用户数。

这与predicted CTR不同（例如图3中的“pCTR”），”rCTR”是我们在线观察到的realistic CTR。

结果

图4表示了online experiements的结果。蓝色和红色的histograms展示了PAL对比baseline在rCTR和rCVR上的提升。首先，rCTR和rCVR的metrics在整个三周的AB test上均获得提升，验证了PAL要比baselines要好。第二，我们也观察到，首周中（baseline使用BASE_p1）rCTR和rCVR（图4虚线）的平均提升是最高的，第二周最低（baseline使用BASE_p5）。该现象告诉我们，baseline的效果对于分配不同的position values区别很大，因为推荐可能与所分配的不同的position values完全不同。

图4 Online AB test的结果

3.4 在线分析

为了完全理解AB test，并验证我们提出的框架在online inference上消除，我们分析了PAL和baselines的推荐结果。

第一个实验是为了对比与ground truth ranking之间的ranking distance。我们将ground truth ranking定义成一个关于items的list，它通过\(f(rCTR, bid)\)的值降序排列。会采用Spearman’s Footrule来measure在两个rankings中的位移 (displacement)，它被广泛用于measure两个rankings间的距离。我们定义了【ground truth ranking】与【由PAL或baselines生成的ranking \(\delta_M\)】在top-L上的距离，如下所示：

\[D(\delta_M, L) = \frac{1}{|U|} \sum\limits_{u \in U} (\sum\limits_{i=1}^L |i - \delta_{M,u}(i)| )\]

…(6)

其中：

• u是在user group U中的一个具有popularity \(\mid U \mid\)的user
• \(\delta_{M,u}\)是由model M为user u生成的推荐列表
• \(\delta_{M,u}(i)\)：在ground truth ranking中的第i个item在推荐\(\delta_{M,u}\)中的position 处

我们对比了\(M \in \lbrace PAL, BASE_{p1}, BASE_{p5}, BASE_{p9} \rbrace\)以及\(L \in [1, 20]\)的\(D(\delta_M, L)\)，如图6(a)所示，其中，线色实线是PAL的结果，其它线是baselines的结果。我们可以看到，PAL会生成对比ground truth ranking最短的距离，这意味着由PAL生成的推荐与我们在线观察到的real ranking最相似。这通过PAL在offline training中使用position-bias建模、并在online inference中消除position-bias来完成，这可以解释，PAL的效果要好于baselines。

图6 online分析

第二个实验对比了PAL和baselines间的个性化（personalization）。Personalization@L 可以mearure 在一个跨不同users的ranking中top-L的inter-user diversity（推荐结果的一个重要因子）。Personalization@L由等式(7)定义：

\[Personlization@L = \frac{1}{ |U| \times (|U|-1)} \sum\limits_{a \in U} \sum\limits_{b \in U} (1 - \frac{q_{ab}(L)}{L})\]

…(7)

其中，\(\mid U \mid\)是user group U的size，\(q_{ab}(L)\)是user a和user b在top-L中公共items的数目。Personlization@L 越高表明，跨不同users在top-L positions上更diverse的推荐items。

我们分别计算了关于PAL 以及baselines的personalization@L。图6(b)表明，在top-5(L=5）、top-10(L=10)以及top-20(L=20)上不同frameworks关于推荐的的personalization。我们可以看到在推荐中由PAL生成的的top items会比baselines生成的更多样一些。由于PAL能在消除position-bias影响后更好地捕获到不同users的特定兴趣、以及根据用户个性化兴趣生成的推荐items。

参考

• 1.https://www.researchgate.net/publication/335771749_PAL_a_position-bias_aware_learning_framework_for_CTR_prediction_in_live_recommender_systems

microsoft在《Modeling and Simultaneously Removing Bias via Adversarial Neural Networks》paper中提出了一种使用adversarial network解决position bias的方法：

介绍

在online广告系统中，需要对给定一个query估计一个ad的ctr，或PClick。通过结合该PClick估计以及一个广告主的bid，我们可以运行一个auction来决定在一个页面上的哪个位置放置ads。这些ad的曝光(impressions)以及他们相应的features被用来训练新的PClick模型。这里，在线广告会存在feedback loop问题，其中：之前看到过的ads会占据着training set，在页面上越高位置的ads会由大部分正样本(clicks)组成。该bias使得在所有ads、queries以及positions（或D）上估计一个好的PClick很难，因为features的比例过高（overrepresentation）与高CTR占据feature space有关。

我们假设：在一个page上的position（例如：mainline、sidebar或bottom）可以概括PClick bias的一大部分。实际上，我们的目标是学习这样的一个PClick表示：它对于一个ad展示的position是不变的（invariant），也就是说，所有potential ads对于给定页面上的一个位置，仍然会是单一的相对排序。尽管我们可以很容易地使用一个linear function来强制在position features，但其它features的intrinsic bias相对于position来说更难被移除。

为了学习这种位置不变特性（position invariant feature）的PClick模型，我们使用ANNs（adversarial neural networks）。ANNs会使用competing loss functions来进行建模，它在tandem（[6]）下进行最优化，最近的工作[1,9]有使用它们进隐藏或加密数据。我们的ANN representation包括了4个networks：Base、Prediction、Bias、以及Bypass Networks（图1）。最终在线使用的PClick prediction是来自Bypass和Prediction networks的outputs的一个线性组合的结果，它用来预测\(\hat{y}\)。然而，在训练这些predictors期间，会使用Bias network adversary(对手)进行竞争。该Bias network只使用由Base network生成的low rank vector \(Z_A\)，尝试对position做出预测。相应的，Prediction、Bypass和Base networks会最优化一个augmented loss function，它会对Bias network进行惩罚。结果是，在传给Prediction network之前，vector \(Z_A\)与position无关。

克服position/display biases的另一个方法是：使用multi-armed bandit方法来帮助生成更少的无偏训练数据以及covariate shift。然而，两者都需要来自一个exploration set中的大量样本来生成更好的估计。实际上，很难获得足够量的exploration data，因为它通常会极大影响收益。我们的ANN方法无需exploration，可以应用于已存在的dataset。

为了测试模型的有效性，我们会在真实数据集和伪造实验上进行评估。我们会生成两个伪造数据集集合，并模拟online ads系统的feedback loop，并展示systematic和user position biases可以通过ANN进行处理，并生成更精准的估计。

我们也展示了：当在CTR上进行最优化时，在模型中移除bias间的一个tradeoff。我们展示了：在评估时通过使用该tradeoff，ANN架构可以在无偏数据集上恢复一个更精准的估计。

我们的贡献如下：

• 一个新的ANN表示，用于移除在线广告的position bias
• 指定一个不同的squard covariance loss，在bias组件上进行对抗最优化（adversarial optimization）
• 引入一个bypass结构来独立和线性建模position
• 详细的人工数据生成评估，演示了在在线广告系统中的feedback问题

2.在付费搜索中的position bias

ML应用中的feedback问题是常见的。为了演示它，我们主要关注付费广告搜索中的CTR或PClick问题。一个标准的Ad selection stack包括了：

• 选择系统（selection system）：selection system会决定ads的一个子集来传给model
• 模型阶段（model phase）：model会尝试估计在分布D上的完全概率密度函数，它是整个Ads、Queries、Positions space。特别的，我们会估计\(P(Click \mid Ad, Queries, Positions\ space)\) 。
• 竞价阶段（auction phase）[7]：在auction阶段，广告主会对关键词竞价（bid）并对queries进行匹配。Ads和他们的positions会最终由PClicks和广告主bids所选择。我们主要关注model phase或PClick model。

出于许多原因，很难估计D。首先，一个在线Ads系统会从D中抽样一个小量的有偏部分。机器学习模型会使用许多features跨<Ad,Query>上进行估计PClick。许多丰富的features是counting features，它会会跨<Ad,QUERY>的过往进行统计信息（比如：该Ad/Query组合在过去的点击百分比）。Query Ad pairs经常出现在Ad stack中，它们具有丰富的informative feature信息：然而，从未见过或者很少见过的Query Ad pairs并没有这些丰富的信息。因而，对于一个模型来说，保证一个Query Ad pair在online之前没有展示过很难进行ranking，这会导致feedback loop。

第二，一个feedback loop会在training data和PClick model间形成。新的training data或ads会由之前的model的ranking顺序展示，一个新的PClick model会从之前的training data中生成。因而，产生的Feedback Loop(FL)会偏向于过往的模型和训练数据。

Position CTR，\(P(y \mid Position = p)\)是一个ad在一个页面上的给定位置p的点击概率。这可以通过对在给定位置中展示的ads的CTRs做平均计算得到。具有越高ranked positions的Ads一般也会生成更高的CTRs。之前的工作尝试建模或解释为什么存在position bias【5】。在我们的setting中，我们假设：过往ads的\(P(y \mid Position = p)\)会总结在一个在线广告系统中存在的这些issues，因为具有越高Position CTR的ads，也越可能具有与high PClicks更强相关的特性。

在理想情况下，一个PClick模型只会使用来自D中的一个大量的随机且均匀抽样数据（RUS数据：randomly and uniformly sampled data）。一个在线Ads stack的核心目标是：广告收入（ad revenue）。实际上，不可能获得一个大的随机抽样数据集，因为online展示许多随机的Ads和queries pair在代价太高。

3.背景

3.1 在线广告

biased FL的训练数据问题，可以通过multi-armed bandits来缓解。multi-armed bandits问题的核心是：寻找一个合理的Exploration & Exploitation的trade off。

在付费搜索广告的context中，会拉取一个arm，它对应的会选择一个ad进行展示。

• Exploration实际上意味着具有较低点击概率估计的ads，会导致在short-term revenue上的一个潜在损失（potential loss）。
• Exploitation偏向于那些具有最高概率估计的ads，会产生一个立即的广告收入的增益。

Bandit算法已经成功出现在展示广告文献、以及其它新闻推荐等领域。由于简洁、表现好，Thompson sampling是一个流行的方法，它对应的会根据最优的概率抽取一个arm。

这些方法在该假设下工作良好，可以探索足够的广告。在在线机器学习系统中，medium-term和short-term revenue的损失是不可接受的。我们可以获取exploration data的一个小抽样，但通常获得足够多的exploration data开销很大，它们受训练数据极大影响。因此，大量biased FL data仍然会被用于训练一个模型，这个问题仍存在。

另一种解决该问题的方法是：回答一个反事实的问题（answering the conterfactual question）[2]。Bottou et al.展示了如何使用反事实方法。该方法不会直接尝试最优化从D上的抽样数据的效果，而是估计PCLick models在过往表现有何不同。作者开发了importance sampling技术来估计具有置信区间的关于兴趣的conterfactual expectations。

Covariate shi‰ft是另一个相关问题，假设：\(P(Y \mid X)\)对于训练和测试分布是相同的，其中：Y是labels，X是features。然而，p(X)会随着training到testing分布发生shifts或者changes。与counterfactual文献相似，它会对loss function进行rebalance，通过在每个实例上乘以\(w(x)=\frac{p_{test}(x)}{p_{train}(x)}\)，以便影响在test set上的变化。然而，决定w(x)何时test set上不会具有足够样本变得非常困难。在我们的setting中RUS dataset不足够大来表示整个分布D。

3.2 Adversarial Networks

对抗网络（Adversarial networks）在最近变得流行，特别是在GANs中作为generative models的一部分。在GANs中，目标是构建一个generative model，它可以通过同时对在一个generator和discriminator network间的两个loss functions进行最优化，从一些domain中可以创建真实示例。

Adversarial networks也会用于其它目的。[1]提出使用Adversarial networks来生成某些级别的加密数据。目标是隐藏来自一个adversary的信息，。。。略

4.方法描述

给定一个biased Feedback Loop的training set我们描述了一种ANN结构来生成精准的PClick预测 \(\hat{y}\)。我们假设一个连续值特征b，它会对该bias进行归纳。我们将b定义成在Ads context中的position CTR或\(P(y \mid Position=p)\)。一个input features集合X通常与b弱相关。

4.1 网络结构

图1

ANN表示包括了如图1所示的4部分：Base network、Predction network、Bias network、以及一个Bypass Network，该networks的每一部分具有参数：\(\theta_A, \theta_Y, \theta_B, \theta_{BY}\)。

• 第一个组件，Base和Prediction networks，会独立地对b进行最优化；
• 第二个组件，Bypass network，只依赖于b。

通过以这种方式解耦模型，ANN可以从bias存在时的data进行学习。

Bypass结构会直接使用b，它通过包含它的最后的hidden state \(Z_{BY}\)作为在等式1的最后sigmoid prediction函数中的一个linear term。最终的hidden states的集合用于预测\(\hat{y}\)将包含一个来自Prediction和Bypass Network的线性组合。假设：

\[\hat{y} = sigmoid(W_Y Z_Y + W_{BY} Z_{BY} + c)\]

…(1)

其中：

• \(Z_y\)：表示在prediction network中最后的hidden activations
• \(W_Y\)：表示weights，用来乘以\(Z_Y\)
• \(W_{BY}\)：它的定义类似
• c：标准线性offset bias项

在b上的linear bypass strategy，当直接包含b时，允许ANN独立建模b，并保留在b上相对排序（relative ranking）

给定X，Base Network会输出一个hidden activations的集合，\(Z_A\)会将输入feed给Prediction和Bias networks，如图1所示。\(Z_A\)用于预测y效果很好，而预测b很差。

4.2 Loss functions

为了完成hidden activations的期望集合，我们会最小化两个competing loss函数：

• bias loss: \(Loss_B\)
• noisy loss：\(Loss_N\)

其定义分别如下：

bias loss:

\[Loss_B(b, \hat{b}; \theta_B) = \sum\limits_{i=0}^n (b_i - \hat{b}_i)^2\]

…(2)

noisy loss:

\[Loss_N(y, \hat{y}, b, \hat{b}; \theta_A, \theta_{BY}, \theta_Y) = (1-\lambda) Loss_Y(y, \hat{y}) + \lambda \cdot Cov_B(b, \hat{b})^2\]

…(3)

bias loss函数在等式2中定义。loss function会衡量在给定\(Z_A\)时Bias network是否可以较好预测b。在图1中，只有Bias network(orange)和\(\theta_B\)会分别根据该loss function进行最优化，从而保持所有其它参数为常数。

等式3描述了noisy loss function，它会在\(\theta_A, \theta_{BY}, \theta_Y\)上进行最优化，而保持\(\theta_B\)为常数。该loss包含了\(Loss_Y(y, \hat{y})\)来表示prediction loss，可以以多种方式定义。本工作中，我们使用binary cross entropy来定义\(Loss_Y\)。

\[Loss_Y(y, \hat{y}) = \frac{1}{n} \sum\limits_{i=0}^n y_i log(\hat{y}_i) + (1-y_i) log(\hat{y}_i)\]

…(4)

\(Cov_B(b, \hat{b})\)是一个sample covariance的函数，它通过在一个给定minibatch中计算跨b和\(\hat{b}\)均值来计算：

\[Cov_B(b, \hat{b})^2 = (\frac{1}{n-1} \sum\limits_{i=0}^n (b_i - \bar{b})(\hat{b}_i - \bar{\hat{b}})^2\]

…(5)

\(Cov_B(b, \hat{b})^2\)表示来自预测噪声的距离\(\hat{b}\)。squared covariance是0，当\(\hat{b}\)与b非正相关或负相关。当存在高相关性时，只要\(\lambda\)足够大，\(Loss_N\)会被高度惩罚。

产生的\(Loss_N\)的objective function会对两种差的预测对模型进行惩罚，X用于恢复b。\(\lambda\)控制着每个项与其它有多强相关。

4.3 学习

实际上，covariance function会跨每个mini-batch进行独立计算，其中会从每个minibatch进行计算。两个loss function \(Loss_N\)和\(Loss_B\)会通过在相同的minibatch上使用SGD进行交替最优化(alternatively optimized)。

4.4 在线inference

为了在一个online setting上预测，我们会忽略Bias network，并使用其它三个networks来生成predictions： \(\hat{y}\) . 在在线广告系统中，对于在过去在线没有看到过的数据，我们将b设置为Position 1 CTR，接着它们会feed到Bypass Network中。

5.系统级bias的人工评估

我们会生成人造数据来展示自然的feedback loop或者在在线广告stack中出现的system level bias。我们首先根据一个bernoulli（概率为：\(P(Y=1)=0.1\)）生成click labels，其中Y=1表示一个点击的ad。接着，feature vectors \(x_j\)会从两个不同但重合的正态分布上生成，根据：

\[x_j = \begin{cases} N(0, \sigma), & \text{if $Y=0$} \\ N(1, \sigma), & \text{if $Y=1$} \end{cases}\]

其中，我们设置\(\sigma=3\)。

这会构成一个完全分布D，会采用10w样本来构建一个大的Reservoir dataset。我们接着表示通过仿真一个迭代过程来表示feedback loop，其中之前的top ranked \(x_j\)（或ads）被用于训练数据来对下一个ads进行排序。图2和3展示了这个feedback loop过程，算法2演示了该仿真。

图2

图3

根据第i-1天的Reservoir数据集中的10000个实例的\(\frac{K}{2}\)候选集合使用无放回抽样随机抽取，其中K=500.模型\(M_{i-1}\)会在第i-1天上训练，并在每个候选集合上对top 2 ads进行排序，在第i天展示给用户。labels会在第i天展示，它随后会形成对可提供的\(topk_i\)训练数据供下一次迭代。

我们会重复该过程，直到迭代了T=100轮. 每次迭代中，我们会记录对于每个top 2 positions的平均position CTR \(P(y \mid Position=p)\)。p=1表示top ranked ads，p=2表示2nd top ranked ads。我们会将position CTRs看成是连续bias term b。为了启动该过程，我们会从Reservoir中抽取K个实例来构成\(topk_0\)。在一个在线Ads系统中，多天的训练数据通常被用来减小systermatic bias。后续评估中，我们会利用最近两天的训练数据（例如：\(M_i\)只在\(topk_i\)和\(topk_{i-1}\)上训练）。每个模型\(M_i\)是一个logistic regression classifier，它具有l2正则。我们在算法2的13行上设置参数r=0，来展示一个系统级的feedback loop bias。我们构成了testing data，从该feedback loop过程中独立，或从D中抽取10w样本来进行HeldOut RUS评估。

表1

在过去两天的每个position的CTR如表1所示，整个CTRs的计算在所有天上计算。所有的4 CTR values可能相等，因为他们每个都与250个训练样本相关。因此，一种naive方法是预测平均CTR values。这会构建对一个adversarial Bais Network如何来预测b的一个上界。我们会在表2中记录过去最近两天数据(4 values)的average CTR，并使用该值来计算MSE。

表2

5.1 setup

当在FL data上训练模型时，可以生成D或RUS HeldOut data。对于该FL data，我们它使用不同的\(\lambda\)来训练一个ANNs的集合，并将b设置为它的Position CTR。除了last layers外，所有hidden activations会使用hyperbolic tangent function。Prediction network的output activation function是一个sigmoid，并且Bias Network的output activation是线性的。Bypass network包含了具有1个node的1个hidden layer，而Base、Prediction、Bias networks每个都包含了带有10个nodes的1个ideen layer。我们会执行SGD，它具有minibatch size=100以及一个learning rate=0.01. 我们会在FL data上训练100个epochs。在这个主训练过程之后，我们允许Bias network在\(Loss_B\)上训练100个epochs。理想的，在给定从Base network生成的\(Z_A\)上，这会允许Bias network来预测b。

根据对比，我们会为一个带有\(\lambda=0\)的ANN执行相同的评估。该模型可以看成是一个完全独立的vanilla neural network，它在y上进行最优化，而一个独立的Bias network可以观察和最优化\(Loss_B\)，无需对Base Network进行变更。我们会对每个模型运行10个具有不同weight initialization的实验，并上报关于y的AUC以及在b上的MSEs。

5.2 主要结果

为了评估来自D的一个无偏样本，我们会使用position 1 CTR, 0.464, 它从最近一天\(topk_{T-1}\)得到。

表3展示了从D中抽取的HeldOut data的AUC和LogLoss，它会在该dataset上训练一个logistic regression模型。这是构成在AUC的一个上界的理想情况。

表3

除了使用Bypass network的ANN架构外，我们也展示了不带Bypass network的ANN的一个变种。图4展示了在FL和RUS datasets上AUCs和MSEs。x-aixs是一个reverse log scale，\(\lambda\)从0到0.99999.随着 \(\lambda\)的增大，MSE大多数会增加FL AUC error的开销。使用Bypass network的ANN的FL MSE error会下降到0.00078(如表2所示)，它与只有平均CTR的naive方法具有相同的表现。

图4

我们注意到，随着\(\lambda\)达到1，在\(Loss_N\)中的\(Loss_Y\)项变得无足轻重，因此可以是\(\lambda\)的一个集合，可以在D的AUC项上进行最优化，它在图4c上可以看到。

ANN模型从\(\lambda=0.9999\)到\(\lambda=0\)在RUS set上的AUC上会有12.6%增益，而在RUS set上只训练一个模型10%的off。

5.3 Bypass vs. non Bypass的结果

图4中的结果展示了使用Bypass vs. non-Bypass ANN在AUC上的微小提升，以及在RUS dataset上具有更高MSEs。我们也分析了根据给定不同的position CTRs在bypass network预测中的不同。我们会在第\(day_{T-1}\)天feed Position 1 CTR作为input到Bypass network中，和features一起做预测，\(\hat{y}_1\)，并在\(day_{T-1}\)feed Position 2 CTR来创建\(\hat{y}_2\)。

我们会计算average prediction。图4e展示了这些结果。随着MSE的增加，会在预测上有所不同。因此，我们会假设：Bypass network可以快速解释在ANN表示中的position CTR。

6.在user level bias上的人工评估

另一个造成position bias的factor可能是一个user level bias。用户可能会偏向于不会点在Position 1下的ads，除非是相关和用户感兴趣。我们会模拟一个额外的User level Bias信息，通过在之前的人工评估中截取position 2 ranked ad的labels来进行。算法2的12-14行的，通过使用概率r来切换observed click label从1到0.

。。。

参考

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