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：

…(6)

dual problem接着：

…(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会采用如下形式：

…(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方法的更新公式：

…(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的链条特性：

…(11)

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

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

…(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\)生成获胜概率：

假设：对于所有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学到的知识。竞价调整的公式如下：

…(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变为：

接着该dual problem是：

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^{(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定义如下：

…(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\)的值，以便以下的测算是最优的：

…(2)

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

…(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预估是：

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

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

那么，每个layer的spending为：

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

图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最小。

…(4)

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

…(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。

…(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)所示：

…(1)

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

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

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

…(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被定义成：

…(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的影响会分别被隐式学到。

…(4)

…(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上的距离，如下所示：

…(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)定义：

…(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的线性组合。假设：

…(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:

…(2)

noisy loss:

…(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\)。

…(4)

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

…(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\)会从两个不同但重合的正态分布上生成，根据：

其中，我们设置\(\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

介绍

共享账号的推荐，很早就有人发paper，我们看下先人的一些探索《Top-N Recommendation for Shared Accounts》：

介绍

一般的推荐系统假设：每个用户账号(user account)表示单个用户(user)。然而，多个用户(user)经常共享单个账号(account)。一个示例是：一个家庭中的所有人会共享同一个在线视频账号、同一个在线音乐流账号、同一个在线电商账号、同一个商店的购物卡。

当多个用户共享账号时会引出三个问题。

首先，dominance problem。当所有推荐项（recommendations）只与共享账号的部分用户有关，至少一个用户不会获得任何相关推荐项，此时会引起“主导问题（dominance problem）”。我们会说：只有少量用户的兴趣会主宰该账号的推荐。另外，考虑一个经常购物的家庭。他们通常会在购买家庭用品时偶尔也会为孩子购买玩具。现在，很有可能所有推荐项会基于更多的家庭用品来生成，该推荐系统对孩子来说是基本没啥用。

第二，generality problem。当推荐项不仅与共享账号下所有用户兴趣都有些相关，并且又不仅仅与任一个用户相关时，会引发“generality problem”。当多个用户的不同品味兴趣被合到同一个账户上时，推荐系统更可能会推荐被大多数人喜欢的通用items（general items），忽略掉私人的品味。

第三，如果推荐系统可以为共享账号上的每个用户生成相关的推荐项，每个用户如何知道哪个推荐项是为你推荐的呢？我们称这为“presentation problem”。

如果有提供上下文信息（比如：time、location、购买意图、item内容、session logs等），context-aware推荐系统是SOTA的解决方案，它可以将accounts划分成多个用户，并检测在推荐时活跃用户的身份。

然而，通常对于划分账号来说通常没有提供这么多上下文信息：

• 第一种情况是：许多公司不会保存过往的上下文信息日志，同时也不保存timestamps
• 第二个情况是：家庭会在一个超市里进行一起购买，他们只有一个信用卡账户，当访问商店时会将购物进行放在一起。在这种情况下，context信息对于每个家庭成员来说是相同的，不能用来将家庭账号划分成各自成员。

因此，我们会介绍：在缺失上下文信息下的共享账号的top-N推荐，上面的关于共享账号的三个问题会在不使用任意上下文信息的情况下得到解决。

正式的，我们先考虑使用二元（binary）、positive-only的偏好反馈的CF的setting。我们将可提供数据表示成一个偏好矩阵，其中：行表示用户，列表示items。偏好矩阵中的每个值是1或0，其中1表示一个已知偏好，0表示未知。[12]称这种setting为one-class CF（OCCF），但它也被称为基于binary、postive-only偏好数据的top-N推荐。这种数据通常与implicit feedback有关。然而，它也是explicit feedback的结果。这不同于社交网站的例子（explicit）。其它相关的应用有：照片标签、文档的words、一个顾客购买的物品。

尽管在缺失上下文信息下共享账号的top-N推荐很重要，我们没有先前研究解决过该挑战。我们通过提出一个解决方案来解决所有item-based topN CF推荐系统的该case，基于binary、postive-only feedback来生成推荐。在这种情况下，我们覆盖了大多数应用，因为ICF很流行。大多数作者将ICF的流行性归结为：多个特性的组合（简洁、稳定、高效、准确），可以直觉性解释它们的推荐，并且能立即解释新进来的feedback。

我们展示了新的item-based top-N CF推荐系统，它允许我们在O(nlogn)下计算推荐分（非指数时间内）。

主要贡献如下：

• 正式介绍缺失上下文信息下的共享账号top-N推荐
• 提出解决方案
• 一个必要特性
• 实验表明：多个数据集上，可以检测共享账号下独立用户的偏好

2.问题定义

假设：U是用户集合，A是账号集合，I是items集合。更进一下，假设：

• \(U(a) \subseteq U\)是具有共享账号a的用户的集合（例如：账号a的用户集合）
• \(a(u) \in A\)是用户u属于的账号

注意：在该问题设定中，每个用户会属于一个账号。

首先，考虑用户评分矩阵（user-rating-matrix）\(T \in \lbrace 0, 1 \rbrace^{\mid U \mid \times \mid I \mid}\)。其中：

• \(T_{ui}=1\)表示存在用户\(u \in U\)对于item \(i \in I\)的偏好
• \(T_{ui}=0\)表示没有这样的偏好

我们给定：一个相关的推荐系统\(R_{ref}\)会产生在给定T下的期望推荐。因此，我们会说：通过相关推荐系统\(R_{ref}(T)\)在用户评分矩阵（user-rating-matrix）T上计算，如果i在u的top-N推荐中，则一个item i与一个user u相关。

不幸的是，在我们的问题设定中，T是未知的。因此，我们会给出账号评分评阵（account-rating-matrix） \(R \in \lbrace 0, 1 \rbrace^{\|A\| \times \|I\|}\)。其中：

• \(R_{ai}=1\)表示账号\(a \in A\)对于\(i \in I\)是存在一个已知偏好的
• \(R_{ai}=0\)表示不存在这样的信息

现在，缺失上下文信息的共享账号的top-N推荐，会设计一个共享账号推荐系统\(R_{sa}(R)\)，它基于账号评分评阵（account-rating-matrix）R，计算每个账号a的top \(N_a\)的推荐，如下：

• top \(N_a\)包含了在账号a的用户集合下每个用户的top-N items，有：\(N = \frac{N_a}{\mid U(a) \mid}\)。实际上，这里目标是：通过最大化在topN中具有至少一个item的用户的数目（用户多，兴趣也多），来避免dominance问题和generality问题。
• 账户a的用户集合中的某一用户，在top-Na中的哪个items是对他有意义的，这是很清楚的，presentation problem会得到解决

注意：在上面的定义中，共享账号的推荐系统不会获得共享每个账号的用户数目作为输入。更进一步，关于共享一个账号的用户的共享兴趣，不会做出任何假设。他们可以具有完全不同的兴趣，或者部分重叠的兴趣，或者完全重合的兴趣。

最后，注意该问题定义与一个典型的group推荐问题【10】正交。

• 首先，在group推荐中，在共享账号下的用户的个体profiles通常都是已知的。而在这里，他们是未知的。
• 第二：在group推荐中，通常会假设，推荐内容会被在共享账号中的所有用户所消费；而在这里，共享账号的每个用户可以区别对它有意义的推荐，并单独消费这些推荐。

3.相关推荐系统

通常，对于一个用户u的top-N推荐，推荐系统会先为每个候选推荐项i计算推荐得分 s(u,i)，接着从中选择按最高分排序的top-N推荐项。

对于binary、postive-only feedback，大多数流行的推荐系统的其中之一是，item-based CF推荐系统【2】。这些item-based推荐系统根源于这样的意图：好的推荐会与target user偏好的目标items相似，其中在两个items间的相似性会通过使用在用户喜欢的items的各自集合间的任意相似度measure进行衡量。因此，对于一个target user u，这种推荐系统：

• 首先会发现KNN(j)：这是对j的k个最相似items，其中：每个喜欢的item j（\(T_{uj}=1\)）通过使用一个相似measure \(sim(j,i)\)进行衡量。
• 接着，用户u对候选推荐项i的item-based推荐得分给定如下：

…(1)

其中：

• \(I(u) = \lbrace j \in I \mid T_{uj} = 1 \rbrace\)，这是u喜欢的items集合。

sim(j,i)的一个常见选择是cosine相似度。更进一步，归一化相似度得分可以提升表现【2】。sim(j,i)的定义如下：

我们可以使用这种推荐系统作为相关推荐系统\(R_{ref}\)。

4.相关推荐系统的共享账号问题

简单将相关推荐系统（reference recommender system）应用到account-rating-matrix R上会导致次优结果，因为RRS会有三个共享账号问题。我们使用两个示例进行说明。在两个示例中，我们考虑：

• 两个用户\(u_a\)和\(u_b\)会共享账号s
• 用户\(u_a\)对于items \(a_1\)和\(a_2\)具有一个已知偏好（相当于推荐里面的trigger item list）
• 用户\(u_b\)对于items \(b_1\), \(b_2\), \(b_3\)具有一个已知偏好（相当于推荐里面的trigger item list）
• 存在5个候候选推荐：\(r_a^1, r_a^2, r_b^1, r_b^2, r_g\)

其中：

• \(r_a^1\)和\(r_a^2\)是对于\(u_a\)来说的好推荐；
• \(r_b^1\)和\(r_b^2\)是对于\(u_b\)来说的好推荐。
• \(r_g\)是一个完全通用的推荐，对两个用户都是中性

表1、2

表1和2给出了前两个示例一些立即计算。两表左侧都是每个候选推荐项（行）与共享账号s（列）的已知偏好间的相似度。两表的右侧都是每个候选推荐项（行）的三个推荐得分（列）。这些得分使用等式（1）计算而来，分别根据左侧的相似度值得到。前两个得分分别对应于\(u_a\)和\(u_b\)，如果他们没有共享一个账号。第三个得分是对于s（两者共享）的得分。

• 第一个示例中（对应于表1）中的IB RRS会有genreality问题。对于表1，我们可以学到：如果\(u_a\)与\(u_b\)不共享账号，item-based RRS会为\(u_a\)正确安排最好的得分给\(r_a^1\)和\(r_a^2\)，为\(u_b\)安排\(r_b^1\)和\(r_b^2\)。然而，如果\(u_a\)和\(u_b\)会共享账号s，那么完全通用的item \(r_g\)会得到最高得分。在本例中，item-based RRS会具有genreality问题，因为它不会区别推荐得分（少量大值的求和，而是许多小值的总和）。

• 第二个示例（对应于表2）展示了item-based RRS会有dominance问题。从表2看到，我们学到，如果\(u_a\)不会与\(u_b\)共享一个账号，item-based RRS会为\(u_a\)正确安排最高分\(r_a^1\)和\(r_a^2\)，为\(u_b\)分配\(r_b^1\)和\(b_b^2\)。然而，即使\(u_a\)和\(u_b\)会共享账号s，\(u_b\)的所有推荐项会接收到一个比\(u_a\)的任意推荐项更高的得分。因而，\(u_b\)的推荐项会主宰账号。在这种情况下，item-based RRS会具有dominance问题，因为它不会解释：\(u_b\)具有比\(u_a\)更多的偏好。

• 两个示例都适合说明RRS存在的presentation问题。例如，考虑表1的第一行。推荐得分\(s(s, r_a^1) = 11\)是以下三项\(sim(a_1, r_a^1)=5, sim(a_2, r_a^1) = 5, s(b_1, r_a^1) = 1\)的总和。因此，它可以通过\(a_1, a_2, b_1\)来进行解释。然而这是一个坏的解释，因为由于\(b_1\)的存在，\(u_a\)会难于区分解释，会错误下结论成该推荐项对\(u_b\)来说也是有意义的。

5.解决genreality问题

前面章节表明，由于item-based RRS不会区分：一个得分是少量大相似得分的求和，还是许多小相似分得分的求程。因此会出现generality问题。因而，我们的第一步是采用item-based的推荐得分（等式1）到length-adjusted item-based（LIB）推荐得分上：

…(2)

其中，超参数\(p \in [0,1]\)。尽管这种adjustment不会立即解决genreality问题，它会提供一种方式，来区分是：在少量大相似得分的求和，还是许多小得分求和的问题。通过选择p > 0，我们可以创建一个bias，它偏向于少量大相似得分的求程。p值越大，该bias就越大。

由于因子\(\frac{1}{\mid I(u) \mid^P}\)对于所有候选推荐i来说是相同的，对于用户u根据\(S_{LIB}\)和\(S_{IB}\)的top N items是相同的。然而，当我们计算两个不同用户间的得分时，\(S_{LIB}\)也会解释用户喜欢的items总量。

为了避免generality问题，我们理想地希望：为共享账号a中的某个用户推荐与他高度相关的推荐项i。因此，我们会计算item i与每个个体用户\(u \in U(a)\)的推荐得分。正式的，我们希望根据它的推荐得分对所有item i进行排序：

不幸的是，我们不能计算理想的推荐得分，因为\(U(a)\)和I(u)是未知的。相似的，我们只知道账号a的偏好：\(I(a) = \lbrace j \in I \mid R_{aj} = 1 \rbrace\), 它表示账号a喜欢的items集合。

然而，我们可以使用它的上界对理想的推荐得分进行近似：

其中，\(2^{I(a)}\)是\(I(a)\)的幂（power）（该集合包含了所在I(a)的可能子集）。提出的近似是一个理想得分的上界，因为I(u)的每个集合对于\(u \in U(a)\)来说是\(2^{I(a)}\)的一个元素。该近似是基于假设：所有I(a)的子集，它们对应于用户更可能生成最高的推荐得分，而非将它们随机地放在一起。

相应的，我们提出使用disambiguating item-based(DAMIB)推荐系统，关于账号a对于item i的推荐得分如下：

…(3)

每个得分\(s_{DAMIB}(a, i)\)对应于一个最优的子集\(S_i^* \subseteq I(a)\)：

…(4)

因而，\(s_{DAMIB}(a, i) = s_{LIB}(S_i^*, i)\)。这样，DAMIB推荐系统不仅会计算推荐得分，也会发现账号a对于i的最大化length-adjuested item-based推荐得分的最优子集\(S_i^*\)。

换句话说，DAMIB推荐系统会基于直觉和task-specific准则，隐式地（implicitly）将共享账号a划分成子集\(S_i^*\)，每个\(S_i^*\)会对于候选推荐项i之一来最大化\(S_{LIB}\)。

• 当\(S_{LIB}(S_i^*, i)\)很高时，我们希望，\(S_i^*\)能很好地对应一个个体用户。
• 当\(S_{LIB}(S_i^*, i)\)很低时，在共享账号上没有用户对于i是一个强推荐，我们希望\(S_i^*\)是一个随机子集。

这样，我们会避免容易出错的（error prone）任务：估计在共享账号上的用户数目、并基于一个通用的聚类准则，显式地将账号a划分成它的个体用户。

更进一步，由于子集可以是潜在重合，DAMIB推荐系统不会关注在共享账号上的用户的已知偏好是否强重合、微重合、或者根本不重合。

最终，注意，对于p=0来说，它总是有：\(s_{DAMIB} = s_{LIB} = s_{IB}\)。因此，item-based推荐系统是DAMIB推荐系统的一个特例。

6.高效计算

可以发现，在等式(3)中的最大化，需要以指数时间复杂度来直接计算\(S_{LIB}\)，称为\(2^{\mid I(a) \mid}\)。相应的，直接计算\(s_{DAMIB}\)是很难的。

幸运的是，我们表明：\(S_{LIB}\)会允许我们来以O(nlogn)来计算\(s_{DAMIB}\)，其中：\(n = \mid I(a) \mid\)。该特性由定理6.1给出。

定理6.1 ： 假设a是一个账号，它喜欢items I(a)的集合。i是一个候选推荐。如果我们将所有items \(j,l \in I(a)\)进行排序，\(rank(j) < rank(l) \Leftrightarrow sim(j,i) > sim(l,i)\)，这样，子集\(S_i^* \subseteq I(a)\)会在所有\(S \in 2^{I(a)}\)上最大化\(S_{LIB}(S, i)\)，它是ranking的一个prefix。

证明：给定任意的\(S \subseteq I(a)\)。初始化P=S。当P不是一个prefix时，从P中移除最差的ranked item r，并添加最好的ranked item a到P中（它不在P中）。只要P还不是一个prefix，它会持有: \(sim(a, i) \geq sim(r, i)\)。因此，每个这样的item安排会增加\(s_{LIB}(P, i)\)（或至少等于），因为因子\(\frac{1}{\mid I(a) \mid^P}\)不会变化，在求和项\(\sum_{j \in I(a)} sim(j,i) \cdot \mid KNN(j) \cap \lbrace i \rbrace \mid\)中的一个较小项会被更一个更大的项所替代。因而，对于每个\(S \subseteq I(a)\)，它不是ranking的一个prefix，我们也可以总是找到一个prefix \(P \subseteq I(a)\)，满足：\(s_{LIB}(P,i) \geq s_{LIB}(S, i)\)。因此，子集\(S_i^*\)会最大化在所有\(S \in 2^{I(a)}\)上的\(s_{LIB}(S, i)\)，必须总是ranking的一个prefix。

由于最优的subset是一个prefix，我们可以发现，它在ranked items I(a)上的一次遍历是线性时间的。时间复杂度上的log因子会来自于对\(\mid I(a) \mid\)上进行排序。

该理论是我们方法的核心，因为它允许我们在O(nlogn)上计算\(s_{DAMIB}\)。

7.解决Dominance问题

DAMIB推荐系统允许我们检测：什么时候(when)发生domainance问题。这是因为：由DAMIB提供的每个推荐项i会伴随着一个清晰的解释，形式为：最优子集\(S_i^* \subseteq I(a)\)。因此，如果union \(U_{i \in top-N_a} S_i^*\)只是I(a)的一个小子集时，我们知道：这个小子集会在账号a的top \(N_a\)推荐中占统治地位。

可以通过选择在算法1中的ALG=DAMIB（我们称为COVER）来解决dominance问题。例如，我们为共享账号推荐的最终算法是DAMIB-COVER，其中：DAMIB-COVER(a) = COVER(a, DAMIB)。

算法1

该DAMIB-COVAER算法会使用DAMIB得分来找出\(N_a\)的最高得分候选推荐，如果它的解释(explanation)\(S_c^*\)与更高排序的候选的解释不容易区分，我们就从top \(N_a\)中移除该候选推荐项c。\(D(S_c^*, C(a)) \geq \theta_D\)的解释区分性条件，会衡量一个候选(\(S_c^*\))以及更高排序候选（ranked candidates）C(a)的explanations的union是否足够不同。

8.求解presentation问题

对于一个共享账号a，使用DAMIB-COVEAR生成top-Na推荐项是不够的，因为共享账号的用户不知道哪个推荐项属于哪个用户。这被称为presentation问题。

我们的解决方案是，将每个推荐项 \(i \in top-N_a\)、与它的解释(explanation)\(S_i^*\)表示在一起。我们期望：对于在top-Na中的items i的绝大多数，explanation \(S_i^*\)是u（共享账号a的某一用户）的偏好I(u)的一个子集。我们会在第9节进行验证该假设。

因此，我们将该推荐表示为item r推荐给喜欢s1, s2, s3的用户。接着，一个会用户认为s1, s2, s3是他的偏好，并知道r是推荐给他的。

9.实验评估

所有数所集都是公开提供的。另外，我们的源代码和数据集链接在：https://bitbucket.org/BlindReview/rsa 上有提供。该网站包含了脚本来自动化运营每个实验。另外，所有结果可以复现。

9.1 数据集

我们使用一个包含了真实的共享账号信息的数据集。CAMRa 2011数据集，它包含了家庭成员信息，关于用户对电影评分的一个子集。这样，我们可以使用该数据集构建真实共享账号。不幸的是，owner不希望分发该数据集，我们没有其它包含共享信息的数据集。然而，从CAMRa 2011数据集上，我们可以学到，大多数家庭账号包含了两个用户（290个家庭有272个），一些包含了三个（14/290），四个（4/290）。因此，我们会根据Zhang[15]的方法，来创建“人工伪造（synthetic）”的共享账号，随机将用户分成2个、3个、4个的组。尽管该方法并不完美，[15]表明‘synthetic’的共享账号会与CAMRa 2011数据集的真实共享账号特性相似。

我们在4个数据集中对解决方案进行评估：Yahoo!Music[13]、Movielens1M[4]，Book-Crossing[16]以及Wiki10+[17]数据集上。

YahooMusic: 14382个用户在1000首歌上进行评分：1-5分。由于我们会考虑binary、postive-only数据的问题设定。我们将4-5的评分转成1，忽略其它评分。平均的，一个用户具有8.7个偏好。

Movielens1M：包含了6038个用户在3533电影上，评分：1-5分。另外，我们会将4-5的评分转化为1. 平均一个用户具有95.3个偏好。

Book-Crossing：包含了两种信息。首先，用户在books上的评分：1-10分。与前2个数据集类似，我们会将评分8, 9, 10分转成偏好并忽略所有的其它评分。第二，也存在二元偏好，我们会添加到偏好列表中。总之，存在87835个用户，300695本书，每个user具有平均11个偏好。

wiki10+：包含了99162个tags，分配给20751个wikipedia文章。在本case中，我们考虑文章的标签推荐，文章看成是“users”的角色，tags看成是”items”的角色。如果一个文章a被打上至少一次的tag t标签，我们认为文章a具有tag t 的一个”perference”。在该context下，一个共享账号是一个大文章，它具有广泛主题，包含了多个更小在子主题下的“articles”。平均，每个article具有22.1个tags。

由于空间限制，我们只展示了在Yahoo!Music dataset上的数值结果。然而，对于其它三个数据集，可以在https://bitbucket.org/BlindReview/rsa上下结论，并导致相同的结论。

9.2 对比算法

我们比较了新算法：DAMIB-COVER，以及另两种算法。第一个对比算法是IB，是item-based RRS在account-rating-matrix上的应用，它忽略了shared account问题的存在。这是我们的baseline。第二个对比算法是IB-COVER，它被定义成IB-COVER(a) = COVER(a, IB). IB-COVER是与【14】的算法相似。

9.3 效果

理想的，在共享账号中所有用户的recall是1，这意味着，对于共享账号的top-Na是个体top-5的union，共有\(\|U(a)\|\)个用户共享账号。

现在，为了研究有多少用户会有共享账号的问题，我们会衡量用户没有获得任何相关推荐的比例，例如：不会发现单个的top-5个体推荐项在共享账号的top-Na推荐项。我们将该数目表示成\(rec_0^u\)，召回为0的用户占比。正式的，我们定义如下：

一个具有共享账号问题的用户的示例如表3所示。该表展示了两个来自Movielens1M数据集的两个真实用户，它们各自已知的偏好I(u)，以及item-based个体top-5推荐。它们item-based个体top-5推荐项看起来合理给出它们的已知偏好，这两个用户是同一家庭的一部分并且共享账号看起来是不现实的。相应的，表3也展示了对于’synthetic’账号的推荐项，它们会在两个cases中（ \(R_{sa} = IB\)以及\(R_{sa} = DAMIB-COVER\)）被两个用户共享。在case \(R_{sa} = IB, rec(562) = 0\)中，例如：user 56

1

2不会获得单个推荐，它会存在共享一个账号的问题。

图1展示了Yahoo!Music数据集的\(rec_0^u\)。最近邻的数目k，是一个item-based RRS的参数。存在多种方式来选择k。在这些方法中，样本是以一个offline实验的accuracy，推荐的主观质量调整；在线A/B的accuracy，计算效率，等。因此，我们会呈现关于RRS的变化带来的结果，例如：ICF RS会与其它k种选择不同。相应的，图1的每个plot会展示一个不同k的结果。

对于每种k的选择，以及单独的top-5推荐，对应于4个实验：一个账号被1、2、3、4个用户共享。注意，一个账号如果由一个用户共享，这种实际并不是共享。每个水平轴表示共享该账号的用户数目，每个垂直轴表示产生的\(rec_0^u\)。4种不同的标记表明，4种不同的共享账号推荐系统\(R_{sa}\)：

• baseline 算法IB
• IB-COVER
• 提出的DAMIB-COVER算法的两个变种

这两个变种会根据参数选择的不同有所区别：p=0.5和p=0.75。由于我们会随机重复每个实验5次，每个plot包含了5x4=20个相似的标记。然而，由于低传播、大多数标记会在相互的top上被绘制，形成dense的maker云。更进一步，由于95%的置信区间，意味着5个数据集的maker-clounds会更窄，我们没有进行绘制。相应的，两个maker-clouds会进行单独可视化，也会在5%的显著级别上具有显著不同。

我们从图1中做出4个观察：

• 首先，我们观察到，baseline的效果并不好。当他们相互共享账号时，接近19%的用户获得不相关推荐。这表明，共享账号会对于推荐系统引起极大问题

• 第二，我们提出的解法，DAMIB-COVER算法，可以提大提升\(rec_0^u\)。在一些情况下，提交是剧烈的。一个示例是$$| U(a)

  = 2\(，个体top-5会使用k=200进行生成。在本case中，当使用baseline IR算法时，12%的用户不会获得相关推荐。通过使用DAMIB-COVER(p=0.75)，该数目会减小到因子4（\)rec_0^U = 0.03$$）。

• 第三，一些IB-COVER已经在IB上进行了提升。存在多个cases，其中DAMIB-COVER会进一步在IB-COVER上提升。另外，DAMIB-COVER会胜过IB-COVER会变得在评估presentation问题时更清晰。
• 最后，当\(\| U(a) \| = 1\)，例如，当账号并不共享时，\(rec_0^u=0\)，是为baseline算法IB进行定义。然而，我们观察到，对于IB-COVER以及DAMIB算法的变种，\(rec_0^u\)可以足够低。因而，当账号不共享时，提出的DAMIB算法不会失败。

9.4 有限的trade-off

为了强调这一点：当没有账号共享时，DAMIB-COVER算法仍在传统设定下表现良好，我们也讨论了DAMIB-COVER的结果会在一个【2】使用的更确定的实验设定下。为了避免所有的困惑：该实验设定不会做关于共享账号的任何事。在该实验设定下，每个用户的一个偏好会被随机选中作为该用户的测试偏好\(h_u\)。如果一个用户只有一个偏好，不会有测试偏好被选中。剩余偏好会被在training matrix R中表示成1（由于没有账号会被共享，它在该case中是完全相同的）。R的所有其它条目都为0。我们将\(U_t\)定义成具有一个测试偏好的用户集合。对于每个user \(u \in U_t\)，每个算法会基于R对items \(\lbrace i \in I \| R_{ui} = 0 \rbrace\)进行排序。根据[2]，我们会使用hitrate@5来评估每个ranking。hitrate@5的给定如下：

其中，top5(u)是用户u的5个最高的ranked items。因而，HR@5给出了测试偏好在top5 推荐中的测试用户百分比。Yahoo!Music数据集的实验结果如图2所示。除了早前讨论的算法外，图2也包含了baseline算法POP的结果，非个性化算法会根据它们的流行度对所有items进行排序；例如：用户在training set中的用户会偏向于该item的数目。在该case中，我们会重复实验5次，使用一个不同的随机分。另外，由于低传播性，5个数据点通常会绘制在互相的顶部。图2展示了DAMIB-COVER和IB在HR@5上非常相似。因此，以HR@5作为全局accuracy几乎没有trade-off。

9.5 Presentation

在第8节中，我们提出解通过将每个推荐项与它的explanation放在一起进行presenting，来解决presentation问题。如果这样，共享账号中的一个用户可以将一个explanation看成是他的偏好的一个子集，该用户会区分该推荐项，因此可以知道推荐项对它是有意义的。对于这种解决方案，很重要的是推荐项是可辨别的，例如：它的explanation是共享账号中某一用户的偏好子集。对于一个共享账号a，我们可以使用explanation \(S_i^*\)来测量一个推荐项i的可辨识性：

理想的，ident(S_i^*) = 1，例如，explanation中的每个item是某个用户一个偏好。在最坏的情况下，\(ident(S_i^*) = 1/ \| U(a) \|\)，例如：explanation包含了一个在共享账号中所有用户的一个等量偏好，因此没有用户可以使用推荐进行区分。

图3展示了对于多个共享账号推荐系统\(R_{sa}\)，在Yahoo!Music数据集上 \(\| U(a) \| = 2\)的top10推荐的identifiability的直方图。从图3a所示，我们可以学到，如果某个用户简单地将item-based reference算法应用到Yahoo的共享账号数据集上，会发生presentation问题：很少的推荐项可以被在共享账号中的某一用户所区分出，例如：\(ident(S_i^*) = 1\)只有10%的explanations。图3b展示了使用IB-COVER来替代IB，不会对情况带来改善。然而，图3c展示了使用DAMIB-COVER可以弹性增加推荐项的区分性，例如：\(ident(S_i^*) = 1\)有近似60%的explanations。因而，DAMIB的explanations会优于iitem-based explanations。

参考

• 1.https://uploads-ssl.webflow.com/5ee118733109492e193e63d2/5f068f4e6b396d7536c1bdbc_190823%20-%20Research%20Paper%20-%20Top-N%20Recommendation%20for%20Shared%20Accounts.pdf