两阶段拍卖中精细广告质量度量和子集选择度量的设计

90通过从快速和粗略的ctr估计器M相乘来计算，然后⟨⟩网络广告的两阶段拍卖设计王一清1、刘翔宇2、郑振哲1 *、张志林2、徐苗2、于川2、吴凡11上海交通大学，中国2阿里巴巴集团，中国{wangyiqing_2015， zhengzhenzhe}@sjtu.edu.cn，fwu@cs.sjtu.edu.cn{qilin.lxy，zhangzhilin.pt，xumiao.xm，yuchuan.yc}@ alibaba-inc.com摘要对于工业在线广告系统的可扩展性，两阶段拍卖架构被广泛用于在有限的响应时间内在大的语料库集合上实现高效的广告分配。目前采用的两阶段广告拍卖通常在拍卖前阶段通过粗略的广告质量度量来获取广告子集，然后在后续阶段通过细化的度量来确定拍卖结果。然而，这种简单且贪婪的解决方案遭受性能降级，因为它单独考虑每个阶段中的决策，导致用于拍卖前阶段的不适当的广告选择度量。 在这项工作中，我们明确调查的粗糙和精细的广告质量指标之间的关系，并设计了一个两阶段的广告拍卖，考虑到这两个阶段之间的决策相互作用。通过在拍卖前阶段解决随机子集选择问题，并在第二阶段进行一般第二价格（GSP）拍卖，我们解耦了两阶段拍卖的设计 我们证明，这种解耦仍然保留了拍卖机制的激励相容性。由于拍卖前阶段的建议制定是一个NP-困难的问题，我们提出了一个可扩展的近似解决方案，通过定义一个新的子集选择度量，即拍卖前评分（PAS）。在公共数据集和行业数据集上的实验结果表明，与传统的贪婪两阶段拍卖和其他基准拍卖相比，两阶段拍卖在社会福利和收益方面都有明显的改善。CCS概念• 信息系统→计算广告。关键词网络广告，广告拍卖，两阶段拍卖本工作部分得到了科技创新2030 -“新一代人工智能”重大专项（编号2018 AAA0100905）的支持61902248、62025204、62072303、61972252和61972254，以及部分由阿里巴巴集团通过阿里巴巴创新研究计划资助，部分由上海市科学技术基金20PJ1407900资助。本文中表达的观点，发现，结论和建议是作者的观点，不一定反映资助机构或政府的观点* 郑振哲为通讯作者。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。版权的组成部分，这项工作所拥有的其他人比ACM必须尊重。允许使用学分进行摘要 以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。请求权限请发邮件至permissions@acm.org。WWW©2022计算机协会ACM ISBN 978-1-4503-9096-5/22/04。. . 十五块https://doi.org/10.1145/3485447.3512054ACM参考格式：Yiqing Wang，Xiangyu Liu，Zhenzhe Zheng，Zhilin Zhang，Miao Xu，ChuanYu and Fan Wu. 2022年网上广告的两阶段拍卖设计。 在ACM WebConference 2022（WWW '22）的会议记录中，2022年4月25日至29日，虚拟活动 ， 法 国 里 昂 。 ACM ， 美 国 纽 约 州 纽 约 市 ， 10 页 。https://doi.org/10.1145/3485447.35120541介绍在线广告是互联网行业的主要收入来源[14]。 现代在线广告平台通过实时运行广告拍卖机制来进行广告分配。 为了实现广告分配的有效性和效率，广告拍卖机制共同考虑来自广告商的出价以及向用户显示广告的质量。例如，在著名的GSP拍卖[14，33]中，广告分配决策是基于出价乘以广告质量的度量做出的。广告质量是通过潜在的动作（例如，点击和购买），例如点击率（CTR）[8，19，42]和转化率（CVR）[24]，其可以通过学习模型来估计用户和广告的丰富特征以及用户-广告交互的丰富数据1。因此，广告分配的性能不仅取决于拍卖机制的规则，而且还取决于学习模型的准确性。在实践中，直接实行这种一阶段广告拍卖机制面临可扩展性问题，并且使用两阶段拍卖架构来在系统可扩展性和广告分配性能之间进行权衡。单阶段广告拍卖机制必须在几十毫秒内决定一组数千个广告的拍卖结果[19，43]。然而，复杂的学习模型，如Wide Deep [8]和DIN [42]，无法在有限的响应时间内完成所有候选广告的CTR估计 为了缓解性能和可扩展性之间的这种困境，我们转向在线广告拍卖的两阶段架构，这也适用于大规模在线广告商[9，15]。这种两阶段广告拍卖的直观和贪婪设计如图1a所示：在第一阶段，称为预拍卖阶段，我们对N个广告的全集AN进行排名，并选择M个广告的子集AM比德中心在被称为拍卖阶段的第二阶段中，我们通过仅对所选择的广告子集进行评估来确定最终的广告分配结果，所述评估是经由投标乘以来自复杂且精细的ctr估计器Mr的ctr。 虽然这种贪婪的两阶段拍卖机制已经在行业中广泛部署[19，35]，但它在广告分配性能上遭受严重损失。由于两种ctr估计器之间的能力差距，对于同一广告用户对，粗ctr和精ctr有时会有很大差异 一些精细点击率高而粗糙点击率低的广告可能会被第一阶段过滤掉，失去进入第二阶段并赢得广告位的机会。1不失一般性，我们将CTR视为本作品中的广告质量91×∈A（）下一页A {}（）下一页拍卖前���i×���������i拍卖���i×���������iCIMM&MMC= & （+i，. ）$Mr=（i，）拍卖前Pr[adis top]拍卖���i×���������i$K$中国拍卖前评分PASMr=（i，）WWWWang等人(a) （b）考绩制度设计图1：（a）广泛采用的两阶段拍卖的贪婪设计（b）我们采用拍卖前评分（PAS）的设计这种贪婪的设计反映了在应用在线广告的两阶段架构在优化两阶段拍卖的广告分配性能时，仅将每个阶段视为单独的优化问题，例如，在每一阶段中以用于广告选择的投标CTR的相同度量进行个别GSP拍卖将遭受性能降级。拍卖设计师应考虑两个阶段之间的相互作用（即第二阶段将在由第一阶段传递的子集上细化估计和选择），并且为每个阶段计算出适当的选择度量。在这项工作中，我们专注于设计一个两阶段拍卖的在线广告的问题，联合考虑大规模在线系统的可扩展性和广告分配的性能保证。这项工作面临两大挑战第一个挑战是描述两阶段调整的条件，以满足激励相容（IC）的经济特性，即广告商被鼓励向用户报告他们的真实价值作为出价，并且个体理性（IR），即， 对于广告商的效用总是非负的。 第二个挑战是大的决策空间，然后设计两阶段拍卖，即高计算复杂性。，如何才能将两个阶段的拍卖设计解耦，针对每个阶段提出具体的拍卖方案，使整个两阶段拍卖在有限的响应时间内有性能保证。虽然有许多设计广告拍卖机制的工作，以优化性能指标的方差，如社会福利和收入[23，33]，他们都没有考虑两阶段拍卖架构。与此同时，虽然两阶段推荐系统最近逐渐引起人们的关注[9，15，20]，但在线广告的两阶段问题与推荐系统的问题不同，因为在广告拍卖中存在支付转移以及对IC和IR的经济属性的要求，而这两个问题在推荐系统中都没有出现。我们提出的两阶段广告拍卖解决方案背后的直觉如下。首先，我们将广告商的效用模型指定为价值最大化者，这是一个捕捉在线广告中广告商目标的合适模型[25，36]，然后在此模型下获得两阶段拍卖的特征为IC和IR。然后，为了减少设计空间，我们将第二阶段拍卖固定为著名的一般第二价格（GSP）拍卖，并证明了这种解耦保持了价格的最优性和IC和IR的性质的两阶段拍卖。接下来，我们将重点放在第一阶段的设计，即。在预拍卖阶段，将其转化为一个随机子集选择问题，即当考虑未实现的拍卖时，选择M个随机元素使已实现的前K个元素的期望和最大化。广告在拍卖前阶段的点击率作为随机变量。然而，这个子集选择问题是一个具有基数约束的子模最大化问题，可以证明是NP-困难的。 为了得到一个可扩展的预拍卖，我们转向一个密切相关的问题，选择M随机元素，最大限度地提高预期的召回上实现的前K个元素，基于此，我们可以定义一个新的广告明智的选择度量，即预拍卖分数（PAS）。我们进一步设计了一个学习为基础的实现这个PAS度量，它可以训练与监督的改进ctr估计MR。由于PAS是一个更合适的度量拍卖前阶段，我们的解决方案优于广泛采用的贪婪设计。我们在图1b中说明了两阶段拍卖的详细过程。我们总结这项工作的主要贡献如下。提出了一种新的在线广告两阶段拍卖机制设计问题，该机制综合考虑了系统的可扩展性和性能保证。我们还证明了性能退化的一个广泛采用的两阶段的广告拍卖，忽略了优化问题之间的相互作用，在这两个阶段。我们提出了一个解决方案，设计一个两阶段的广告拍卖社会福利最大化。我们解耦两阶段拍卖作为一个随机子集选择问题在拍卖前阶段和普惠制拍卖在第二阶段。我们提出了一个新的广告明智的选择度量预拍卖分数（PAS）来解决子集的选择。本文提出的两阶段广告拍卖仍然满足IC和IR的性质。在公共数据和工业数据上的大量实验证明了我们的解决方案的有效性。在工业数据上，我们的解决方案比贪婪两阶段拍卖的社会福利和收入分别高出+4.35%和+4.59%2预赛在这一节中，我们描述了广告拍卖模型，广告商的效用模型，以及广告拍卖的期望经济属性对于在线广告平台，来自用户的页面查看请求将被发送到进行广告拍卖，其中N个广告商的集合N= 1，. . .，N竞争页面上的K个广告位。在广告拍卖中，每个广告客户iN基于她的私人值Vi提交出价Bi，该私人值Vi测量从用户点击广告中提取的潜在利益。除了广告主的出价b = b1，. . . ，bN，拍卖机制还取决于广告客户/广告特征a = a1，. . . ，aN和用户特征u。这里，广告商/广告特征可以是广告id、类别id等。用户特征u可以是用户id、点击历史等。应用广告和用户的特征来评估向特定用户显示某个广告的质量的···92≤≤⟨⟩（）下一页（）下一页˜()（）下一页（×/（））（）（）下一页≤Rc|D（ai，u）|×ctr（ai，u）=是最大化预期的社会福利，这是显示广告的预期点击值与用户的sto的总和|为|=ctr（ai，u）|D（ai，u）|、我=E[我，u）|a，u]。3.1一阶段广告拍卖在设计一个两阶段拍卖在线广告WWW '22，2022年4月25日至29日，虚拟活动，里昂，法国。拍卖机制x，p通过分配方案x确定广告分配结果，并通过支付规则p确定K个广告位的价格。分配方案xib，a，u=k表示广告i赢得第k个最高的广告位，或者对于k=0失去拍卖;支付规则pib，a，u是广告i如果被显示和点击需要支付接下来我们描述广告商的效用模型广告商希望最大化其产品的广告效果，仅要求成本满足某些约束，例如预算约束、每次点击成本约束和投资回报约束[37，39]。根据[3，25]的行业观察，价值最大化模型[36]捕获了广告商的这种优化目标，而传统的准线性效用最大化模型[30]（即每个广告商i最大化vi-pi）不再适用于这种情况。定义2.1. （价值最大化者[36]）如果广告主i偏好具有较高广告位的拍卖结果，同时保持支付满足约束pi vi，则她是价值最大化者;对于相同的广告位，她偏好较低的支付pi。在广告拍卖中，广告主可能会策略性地误报他们的价值，即。投标人操纵拍卖结果是为了自己的利益。为了避免这种行为，广告拍卖机制需要满足以下经济性质：激励相容性（IC）：如实报告私人价值，即b i = vi是每个广告客户i的最佳策略。个人合理性（IR）：广告客户i的付款不会超过报告的价值，即如果广告i被显示和点击，则广告商i支付Pi bi;否则不支付任何费用。有了这两个属性，广告客户不需要花费精力在计算投标策略，并鼓励参与拍卖没有赤字的风险线上平台也获得了广告主真实可靠对于具有效用模型作为价值最大化者的广告主在[36]中已经证明，如果满足以下两个条件，则拍卖机制满足IC和IR单调性：广告客户将赢得相同的广告位或更高的一个，如果她报告一个更高的出价。关键价格：获胜广告客户的付款是最低出价，她需要保持相同的广告位。这个等级。在插槽k的获胜广告的付款 K是bk+1ctrk+1bk，其中下标k表示具有第k个最高预期点击值的广告。 GSP拍卖是价值最大化广告商的IC和IR，因为它满足上面提到的单调性和临界价格条件[36]。因此，在GSP拍卖中，对于每个广告i，我们有bi= vi。 当存在无偏ctr估计量2时，GSP拍卖可以最大化期望的社会福利[33]，即 ，K个获胜广告的总期望点击值：SumTopK（{vi×ctri}i∈A）=SumTopK（{bi× ctri}i∈A）。这里，SumTopK（S）是输出集合S中最大的K个元素的和的集合函数。3.2广告拍卖中的点击率估算广告拍卖的效果在很大程度上取决于点击率估计的准确性在文献中开发了各种机器学习模型来估计不同场景下的ctr我们将这些模型分为两类：粗但快速的ctr估计表示为Mc和精细但沉重的ctr估计表示为Mr。 粗略ctr估计器Mc = ctr a i，u使用轻量级学习模型[19，35]，并且仅利用部分广告特征a i和部分用户特征ui。改进的ctr s估计器Mr = ctr ai，u可以是复杂的学习模型[41，42]，并且有效地利用完整的广告特征ai和用户特征u。例如，完整的用户特征u可以是用户配置文件以及用户行为的长期历史[ 41]，而部分用户特征u只是一些基本的用户配置文件。改进的估计器Mr可以具有复杂的神经网络架构，例如基于注意力和序列建模组件，以产生丰富的用户-广告交叉特征[38，41，42]。相比之下，粗略估计器Mc可能简单地遵循双塔架构[19]或嵌入层后跟全连接层[35]。有了这些差异，MR估计消耗更长的推理时间，但产生更准确的ctr比MC估计。接下来，我们研究粗估计量Mc和精估计量Mr之间的关系。假设Mc和Mr的模型都用相同的数据集D进行了充分训练，该数据集D是独立且相同地从真实分布中抽样的。对于具有对应的部分特征（ai，u）的完整特征（ai，u）的输入，Mc和Mr的输出如下收敛ctr（ai，u）=|D+（ai，u）|/|D（ai，u）|、在这项工作中考虑的广告拍卖机制的目标˜˜ ˜|.|.|D(ai,u)|（一）随机点击行为。 社会福利是在线广告的一个重要指标，因为它衡量了广告商和用户的匹配效率，也是广告平台总收入的上限。其中，D（k，k）是其部分或全部特征被限制为（k，k）的样本的子集，并且D+是正样本的子集，即，，点击的样本。以来|D（ai，u）|Pr [ai，u |ai，u]，M和M在输入上的关系（表示为ai，u）可以近似为3问题公式化ctr（ai，u）=.一|一个人，我们|uctr（ai，u）×Pr[ai，u|ai，u]（二更）最广泛使用的广告拍卖机制之一是GSP auc-ctr（ai i[14，33]。 给定每个广告商i的出价b i和用户的出价b i，对于用户单击根据这一关系，服务于一阶段普惠制拍卖，Mc和Mr估计量导致（3a）中的预期社会福利，ctri到广告i，GSP拍卖排名所有广告其预期的显示点击值，即，，bictri，并且将K个ad时隙从最高到最低分配，2可以应用各种校准算法来增强基本ctr估计值，以进一步降低偏差[10]。····a我|我们|u93M.公司简介≤E [SumTopK（{bi× ctr（ai，u）}i ∈AN）].（3b）SumTopK（{bi×ctri}i∈AM）=i∈AKbi×ctri. 在第一阶段，我们（3b）中的不等式是由于凸函数的Jensen不等式引起的Iu我MWWWWang等人（3b）分别：E[SumTopK（{bi×c<$tr（a<$i，u<$）}i∈AN）]（3a）以期望社会福利最大化为目标，进行普惠制拍卖。在候选广告设置为AM的情况下，显示GSP拍卖前K个广告，表示为集合AK，具有最高期望= E [SumTopK（{E [bi×ctr（ai，u）|a<$i，u<$]}i∈A ）的情况下]点击价值，b×ctr（a，u），产生预期的社会福利我是我 。不能访问细化的ctr（a，M），而只能访问（a，u），因此事实上，这里的SumTopK可以被看作是一个凸RN上的函数我们看到，一阶段普惠制拍卖，改进的Mr估计实现了严格更高的期望社会福利预拍卖（PA）的优化问题是一个随机问题，优化问题：(PA) max Ea|一个人，我们|u∈ [SumTopK（{bi × ctri（ai，u）}i∈AM）]与粗估计器Mc相比，xppS. t.ApM=x（b，a，u），（四）3.3两阶段广告拍卖由于在几十毫秒确定数千个广告的拍卖分配和支付的可伸缩性要求xi（b，a，u）在bi，b−i，a，u上单调，其中b−i是从b=（bi，b−i）中移除bi后的出价向量。4贪婪解在本节中，我们展示了一个在工业中广泛使用的原生贪婪两阶段广告拍卖（GDY）的性能下降。GDY拍卖有一个简单直观的定义，资源在社会的最优性和福利和及时响应时间，两阶段的架构r=ctr（ai，u）和Mc=ctr（ai，u）.定义4.1.在GDY中，拍卖前阶段对所有广告进行排名阶段，称为与分配AN乘以bi×ctr（ai，u），并给出最高的MadsA<$ 到方案xp选择MN个广告的子集，即，xp（AN）=AMN0是一个很大的数，使得bj×t×ctrj>˜˜m≤M，ctrm=ctrm。广告具有两种可能的CTR实现，××我我们主要研究第一阶段的拍卖设计，即拍卖方案的设计。前，={1i=1在预拍卖阶段，我们只需要保证分配方案xp满足单调性y，i。e. ，xp（b，a∈，u∈）是单调的设计拍卖在这两个阶段是巨大的，如何脱钩，设计的两阶段拍卖，并仍然保证最终拍卖业绩。我们记得，（一）普惠制拍卖是IC和IR对于价值最大化的广告客户，和（ii）普惠制拍卖可以最大化当有一个改进的ctr估计时，期望的社会福利由于普惠制拍卖的这两个优点，我们可以确定第二阶段作为普惠制拍卖，既不引入暴力的IC选择具有bictri的最大M值的广告以形成M在这种情况下，GDY是最佳的对于M>K的情形，我们用一个简单的例子来解释GDY的次优性实施例4.2. 有N个广告的b1 × ctr 1>。. . > bN × ctr N.ctrj=t×ctrj，概率为1/t，ctrj= 1/2，概率为1/tbKctrK=bKctrK. GDY首先在预拍卖阶段选择前M个广告（不包括广告j），然后在第二阶段向用户显示前K个广告预期的社会和IR也不是期望社会福利的最优性损失埃尔法是。Kbi×ctri. 然而，如果预拍卖阶段选择–95拍卖阶段，在这项工作中。首先，我们协调拍卖前一96M，. . . ，M971K−1˜.K˜=>t（i=1bi× ctri+bj× t × ctrj）+（1 −t）i=1bi× ctri。i=1bi×ctri预期社会福利优于GDY：98和普惠制拍卖，以满足两个条件（单调性和临界价格）的IC和IR性能 。由于没有付99款，E[S.umTopK（{bi×ctri}i∈AM）]1001 .一、K增加放松与休息，以达到最佳效果。通过这样做，我们可以保证两阶段拍卖的单调性特性，即当广告商i增加她的出价时，她在预拍卖中获胜并进入第二阶段的概率更高，在第二阶段中，她获得不差的广告时段。其次，我们制定的优化问题在拍卖前阶段。预拍卖的目标是提名一个好的候选广告集AM为第二个101贪婪两阶段拍卖会遇到的情况类似于实施例4.2，导致性能下降，102实践一些广告（如广告j的例子）得到一个低粗ctr但与Mr相比，其精化ctr较高。如果拍卖前阶段意识到第二阶段GSP拍卖将进一步细化ctr估计，拍卖前阶段可以做出更好的决定，选择一些具有潜在高细化ctr的广告，以实现103104˜× ×一个随机变量的平均值（，）。KANN我. ΣO（）一NN一−一一AN[|]Ect r[SumTopK（{bi×ctri}i∈AM）]=i∈AMPrct r[i∈ AN]，在设计一个两阶段拍卖在线广告WWW '22，2022年4月25日至29日，虚拟活动，里昂，法国。更高的社会福利。 该示例使用（2）中所示的粗略估计器Mc和精细估计器Mr之间的关系，即 ，拍卖前阶段可以将未实现的细化ctr（ai，u）视为ctr aiu这个问题在文献中是一个随机变量集上的子集选择问题，理论分析已经在团队选择问题[22]和其他一般背景[29]中考虑过。我们在这里要传达的主要观点是，广泛部署的贪婪解决方案，将两个阶段中的每个阶段的设计分别视为社会福利最大化，并在两个阶段中使用相同的选择度量（b ctr或b ctr），反而会遭受次优的社会福利。当我们设计一个两阶段拍卖时，我们应该考虑两个阶段之间的相互作用即第二阶段对第一阶段投放的广告子集进行评估和分配，并为每个阶段设计合适的选择指标，以保证整体广告投放。有了这个ad-wise度量，我们可以以并行的方式评估每个ad，并避免评估子模集函数。 为了解决ctr缺乏显式分布的问题，我们在第5.3节中提出了基于学习的广告度量实现。5.2拍卖前评分我们设计了一个易于处理和可扩展的广告明智的指标，在拍卖前阶段的子集选择，它支持每个广告的并行由于预拍卖的社会福利最大化是一个NP-难问题，直接获得广告度量作为社会福利最大化的精确解是不可能的这里的关键见解是，我们可以转向与社会福利最大化密切相关的目标，然后导出相应的广告度量。密切相关的目标，称为召回最大化（PA-R），是在拍卖前阶段选择广告集合AM，以覆盖拍卖阶段中AN的尽可能多的最终前K个广告两阶段广告拍卖的表现（PA-R）maxE [SumTopK（{1[i∈ AK]}）]，5拍卖前设计AMANc trNi∈AM（五）我们首先展示了解决预-其中，AN的最后前K个广告，表示为AK，是具有在（4）中定义的拍卖问题。为了降低复杂度，我们N在拍卖阶段，从AN中得到最高的Kbi× ctr（ai，u）. 如果提出了一种称为拍卖前评分（PAS）的广告明智的度量，用于在拍卖前阶段进行可缩放的广告选择在实践中，我们还设计了一个基于学习的PAS实现本节中的详细证明可以在附录B中找到。5.1拍卖前问题我们首先证明，即使我们放松（4）中问题PA的分配xp上的单调性约束，所得的简化（SimPA）max覆盖了所有的前K广告，实现了一阶段拍卖的社会福利最大化，即两阶段广告拍卖的社会福利上界。我们现在导出精确的广告度量，使得预拍卖可以根据该度量来排名和检索前M个广告AM，以优化PA-R。考虑任何固定子集AM，AK上的期望召回率为E. ctr[SumTopK（{1[i∈AK]}i∈AM）]PA版本（SimPA）仍然是棘手的。= .i∈AMECTR[1][i]KN∈AKN]]（六）AMANS. t.|≤M，|≤M,其中ctri是随机变量。建议我在5.1。 SimPA问题是NP难的。其中第一个等式是由于期望的线性，第二个等式是由于指示函数的定义上面的等式表明，选择M最大的广告Pr ct r [i ∈ AK]，即，在AK中的概率，最大化NKN事实上，SimPA是一个具有基数的子模最大化约束。对于基集A，集函数<$：2A→R为亚模的如果<$S<$T<$A且<$j∈A\T，<$（S<${j}）−<$（S）≥<$（T <${j}）−<$（T）。建议我在5.2。在SimPA中，目标Ectr[SumTopK（{bi×ctri} i ∈S）]是关于集合S的子模集函数。在拍卖前阶段的设置中，对于这种子模块优化没有明显的易处理和可扩展的解决方案：（i）在集合尺度上评估选择M的蛮力算法导致难以处理的N 计算(ii)的经典应用优化算法[4，3M1]按顺序选择广告基于它们的边际贡献，不能以广告方式并行运行，因此在实践中仍然不可扩展（iii）我们强调，从拍卖前阶段的角度来看，ctr及其显式分布是未知的，这甚至给评估目标子模函数带来了困难。因此，即使是依赖于子模函数求值的并行近似算法[1，2，6]也不适合这里。考虑到拍卖前阶段在线服务的可扩展性，我们在5.2节中提出了一个用于子集选择的广告度量。预期的召回。因此，我们获得了一个广告方面的指标，预拍卖中的子集选择，对于每个广告i，表示为fi：（PAS）fi（b，a∈，u∈）= Prct r [i ∈ AK].（七）我们称之为拍卖前评分（PAS）。 注意，尽管PAS是广告方面的度量，但是仍然允许在拍卖前阶段使用整个广告集合N的信息，即，，b，a，b，u，以便于概率的计算。 根据（7）中的集合K和PAS的定义，对于任何广告商i、部分广告特征ai、用户特征u i和其他广告商的出价bi，广告商i的PAS相对于bi单调增加。因此，如果预拍卖用度量PAS对所有广告N进行排名并选择前M个广告，则满足预拍卖中分配的单调性，因此满足两阶段拍卖的IC5.3基于学习的拍卖前评分计算度量PAS需要分布Pr_ctr_b，a_ctr，u_ctr的显式形式，这在未知和相互依赖的在线环境中可能是复杂的。 为了克服这个困难，我们使用参数化的神经网络来实现学习基于PASfθ，使得通过fθ的排序的置换可以我我M105我（）下一页A∈（）下一页（）A×（）（）A\A×（）⟨⟩⟨⟩⟨⟩⟨⟩⟨⟩˜()（）×（）（）下一页.˜（−）/Pr [i]是前1 |y]=./N˜×（）˜()当AKAM同样的1：1负采样。[19]故，ctr=p，其中p是训练估计器的输出，NN[i|F我（b，a，u）]=1600个项目和1600个类别我们将评论视为用户点击，j∈AK召回uK=i∈AK1[iNKN.WWWWang等人通过（7）中的原始PAS fi近似排序的置换。 我们使用监督学习来确定神经网络f θ的参数θ。 对于每个训练样本，特征是b，a，u，即，N个出价、部分广告特征和部分用户特征;并且标签是N-dim向量y，其中对于每个广告i，元素是yi=bictrai，u。在训练过程中，我们需要来自N中所有广告的精细估计量Mr的ctr ai，u来计算样本的标签 但我们只获得了在线服务期间广告iM的ctr ai，u，因为只有广告M进入第二拍卖阶段并由改进估计器评估。因此，我们需要离线细化估计器Mr来产生N M中的广告的ctr ai，u。遵循Plackett-Luce概率模型，该模型被广泛使用在学习排列的分布[5，17]时，我们假设排列为yi=bictr ai，u的排列π是由N个参数{yi}i∈A定义的排列分布的样本，如下所示.Ni=1NK=Iyπ（k）以及用户的审阅项目的列表以及历史中的类别，即， ，u =user_id、hist_items_id、hist_cate_id。每个用户的项目列表的长度至少为5。完整的广告功能是ai=item_id，cate_id。我们将部分用户特征u_id定义为u_id = user_id，hist_items_id[：3]，hist_cate_id[：3]，即，仅用户历史记录中的前三个项目在u中使用。部分广告的特点是一个字母i被定义为与完整的字母i相同。基于此数据集，我们模拟了两阶段拍卖的过程，并生成了40，000个拍卖。在每次拍卖中，有1000个随机选择的广告。每个广告的出价是从均匀分布中独立采样的。为了模拟第二阶段GSP拍卖，我们使用广告和用户 为了模拟GDY以进行比较，我们使用ad和用户的部分特征ai，u来训练一个模型，该模型具有嵌入，然后是全连接层（FCN）[35]，作为粗略和快速的估计器Mc，以生成每个ad的ctrai，u。MrDIN和McFCN的训练样本相同，Pr [π |y]=yπ（i），（8）即，相同的数据集，来自数据集的用户数据集对作为阳性样本，其中π k是秩为k的ad。我们可以很容易地证实，概率的定义满足两个期望的性质：（i）它是标准化，即，π Pr [π |y]= 1;（ii）前1个概率是：p+1 pηη是负下采样率。CTR的区别而ctr随着η的减小而变大，因为原始来自Mr和Mc的输出p被近似放大一个因子yik=1yk.（九）1η。我们考虑两个设置，Public-1和Public-5，其η为0。01和0。05，分别。Public-1模拟真实世界中的ctr引理5.3. 当yi>yj且K> 1时，Pr [i ∈AK]>Pr [j ∈AK].在线广告我们想验证我们的解决方案利用引理5.3，我们可以使用yi的秩来表示PAS Pr[i∈ AK]的秩。让神经网络直接输出fθ作为近似yi的logits。广告的前1概率是其中ctr和ctr之间的差异较小，并且GDY能够相对更好地执行。iθ6.2工业数据集的设置由logits{fi}i∈AN确定，计算为工业数据集来自两阶段广告拍卖的日志PR 是最高的1θ θexp（fθ）在国内领先的电子商务平台淘宝，运行GDY定义θk∈AN exp（fk）给定样本集Df，我们通过fθ最小化样本分布和参数分布之间的交叉熵，因此损失函数为2021年1月8日记录的数据每个拍卖实例中有700个广告。 对于每个广告，特征是：（i）来自Mc的ctr a_i，u_i，一些历史统计数据，诸如该广告的历史平均细化ctr和cvr。我们把这些估计值作为交叉特征1 . .NJ广告和用户L= −|Df|fi=1Pr [i]是前1 |y]、（十）如广告中产品的出价B1、类别和销售价格使用来自Mr的估计ctr（ai，u）来生成标签×logP r[i]为前1|fθ（bj，aj，uj）]其中上标j表示Df中的第j个样本。6实验我们评估了我们提出的两阶段拍卖解决方案在公共和工业数据集上的有效性。6.1公共数据集的设置bi ctr ai，u. 请注意，在我们的价值最大化假设广告主，GDY满足IC和IR。因此，我们可以将记录的出价视为广告商对用户点击的真实价值。然后，我们可以在模拟其他IC和IR拍卖机制时使用记录的出价来计算社会福利和收入。6.3评估指标我们考虑以下常用的广告拍卖评估指标我们回想一下，AK才是真正的全K广告公共数据集Amazon Dataset [27]包含产品评论设置N是所选子集中的顶部广告。M和亚马逊的元数据[18，28]。我们进行实验，NMK.i∈AKbi×ctriJJ名为Books的子集，包含603K用户评论，367K• 社会福利率：SWr @ K =.Mb×ctr.把物品当作广告。用户的全部特征包括user_id，• TopK Recall：@.N ∈ AK]/..在Public-5模拟的场景中仍然可以胜过GDY，.定义4.1。 我们随机抽取了3万份拍卖记录，106±•REVrK = REV（A）/修订版（A）对于ad，GDY的乘积简单地为×，其中re为输出⟨⟩•×ט×ט×设置，REV（A）=而r d点的y轴是x的标准化d值。Kk=1在设计一个两阶段拍卖在线广告WWW '22，2022年4月25日至29日，虚拟活动，里昂，法国。表1：不同方法对数据设置Public-1的结果。N=1000，M= 50。表格单元格中的符号：20次运行的平均标准召回@1召回@5召回@10SWr@5版本r@5GDY0.8383 ±0.0022，（0%）0.7378 ±0.0024，（0%）0.6597 ±0.0029，（0%）0.9252 ±0.0007，（0%）0.9028 ±0.0010，（0%）REGCTR0.8440± 0.0058，（+0.57%）0.7469± 0.0079，（+0.91%）0.6698± 0.0079，（+1.01%）0.9234± 0.0048，（-0.18%）0.9026± 0.0050，（-0.02%）REG0.8506± 0.0068，（+1.23%）0.7483± 0.0109，（+1.05%）0.6709± 0.0112，（+1.12%）0.9274± 0.0041，（+0.22%）0.9058± 0.0050，（+0.30%）PAS0.9093± 0.0021，（+7.10%）0.8639± 0.0045，（+12.61%）0.8246± 0.0057，（+16.49%）0.9613± 0.0011，（+3.61%）0.9519± 0.0015，（+4.91%）表2：不同方法对数据设置Public-5的结果 N = 1000，M = 50。 符号与表1相同。召回@1召回@5召回@10SWr@5版本r@5GDY0.8359 ±0.0023，（0%）0.7390 ±0.0026，（0%）0.6623 ±0.0025，（0%）0.9389 ±0.0006，（0%）0.9213 ±0.0008，（0%）REGCTR0.9073± 0.0029，（+7.14%）0.8502± 0.0028，（+11.12%）0.7972± 0.0032，（+13.49%）0.9669± 0.0008，（+2.80%）0.9578± 0.0010，（+3.65%）REG0.9094± 0.0037，（+7.35%）0.8521± 0.0051，（+11.31%）0.7982± 0.0057，（+13.59%）0.9673± 0.0016，（+2.84%）0.9583± 0.0018，（+3.70%）PAS0.9155± 0.0071，（+7.96%）0.8745± 0.0075，（+13.55%）0.8363± 0.0080，（+17.40%）0.9720± 0.0022，（+3.31%）0.9651± 0.0027，（+4.38%）表3：不同方法对数据设置的结果工业。 N = 700，M = 30。 符号与表1相同。召回@1召回@5召回@10SWr@5版本r@5GDY0.4745 ±0.0046，（0%）0.3740 ±0.0019，（0%）0.3175 ±0.0013，（0%）0.7808 ±0.0013，（0%）0.7483 ±0.0010，（0%）REGCTR0.5156± 0.0047，（+4.11%）0.4043± 0.0028，（+3.03%）0.3451± 0.0024，（+2.76%）0.8081± 0.0017，（+2.73%）0.7764± 0.0022，（+2.81%）REG0.5118± 0.0059，（+3.73%）0.4048± 0.0033，（+3.08%）0.3474± 0.0027，（+2.99%）0.8089± 0.0022，（+2.81%）0.7783± 0.0025，（+3.00%）PAS0.5351± 0.0035，（+6.06%）0.4226± 0.0024，（+4.86%）0.3635± 0.0017，（+4.60%）0.8243± 0.0013，（+4.35%）0.7942± 0.0007，（+4.59%）收益率：@K K，其中收益率REV在GSP拍卖下，且subscrNipt（k）表示带K的广告词。-correspond中的第二高b×ctr-我们可以从表1-3中得到下列观察结果. （i）我们可以看到，我们提出的PAS在每个数据设