混排

发表于 更新于 分类于

NMA: Neural Multi-slot Auctions with Externalities for Online Advertising

  • 研究背景：在线广告是众多互联网平台的主要收入来源，拍卖机制的设计对平台、用户和广告商至关重要。广义第二价格（GSP）拍卖是常见机制，但存在用户点击假设与实际不符等问题。如在美团外卖平台，广告展示受多种因素影响，而GSP未考虑这些外部性。Deep Neural Auctions（DNA）虽有改进，但仍有局限，VCG及其变体WVCG在理论上可处理外部性，但在实践中面临收入下降或参数求解复杂等问题。
  • 研究目的：提出一种新的神经多槽拍卖机制（NMA），有效建模全局外部性，平衡平台收入和社会福利，同时解决现有机制的问题。
  • 方法与模型
    • 模型结构
      • 上下文感知列表式预测模块（CLPM）：采用参数共享结构，输入广告列表及相关公共信息，通过嵌入层、自注意力单元和目标注意力单元处理，输出列表式pCTR。还提出基于广告真实反馈的辅助损失，使模型能有效建模全局外部性，提高预测准确性。
      • 列表式深度排名模块（LDRM）：结合拍卖机制与深度学习，设计μ-Net子网络计算广告列表排名分数，确定支付规则，保证激励兼容性（IC）和个体理性（IR），实现端到端优化，提高排名公式表达能力。
      • 列表式可微排序模块（LDSM）：将排序操作从不可微转换为可微，通过定义排序算子和放松argmax操作，输出行随机置换矩阵表示选择概率，使复杂拍卖机制能端到端训练，解决LDRM在分配和支付处理上与深度学习不适应的问题。
      • 社会福利最大化辅助损失：基于广告列表社会福利定义，构建辅助损失，加速学习过程，减少社会福利下降，通过调整参数平衡NMA性能，确保满足社会福利约束。
    • 实验设计
      • 数据集：使用公共数据集Avito和工业数据集Meituan进行离线实验，将数据集按时间或比例划分为训练集和测试集。
      • 评估指标：包括点击率（CTR）、每千次展示收入（RPM）、每千次展示社会福利（SWPM）和社会福利最大化比率（SWMR），同时评估机制的IC属性。
      • 对比方法：与GSP、DNA、VCG和WVCG等代表性拍卖机制对比。
  • 实验结果
    • 离线实验
      • 性能比较：NMA在两个数据集上的RPM、SWPM和CTR指标上优于DNA和GSP，能有效建模全局外部性；与VCG相比，NMA在广告收入和社会福利间平衡更好；在RPM指标上明显优于WVCG，验证了NMA的强大表达和学习能力。NMA的IC-R值与VCG相当且优于GFP，满足IC约束。
      • 模块消融研究：去除CLPM、LDRM - LDSM或社会福利最大化辅助损失后的NMA变体性能均下降，证明各模块对NMA性能提升有重要作用，CLPM能有效建模全局外部性，辅助损失有助于平衡广告收入和社会福利。
      • 超参数分析：α₁增大时，SWPM增加但RPM下降，α₂在一定范围内增加可提升性能，过大则导致性能下降，说明辅助损失可帮助平衡收入和福利，且CLPM辅助损失权重需合理设置。
    • 在线A/B测试：在美团外卖平台进行为期一个月的在线A/B测试，NMA相比GSP在CTR、RPM和SWPM上分别有显著提升，证明NMA在实际应用中可实现更高平台收入和社会福利，尽管在线测试与离线实验结果在绝对值上存在差异，但趋势一致。
  • 研究结论：NMA有效建模全局外部性，通过设计的模块和辅助损失平衡平台收入和社会福利，在离线和在线实验中表现优异，已部署于美团外卖平台。未来可进一步优化，如采用列表生成模块替代全排列算法，提高工作效率。

摘要

在线广告拍卖为社交网络服务和电子商务平台带来了数十亿美元的收入。对于广告商来说简单易懂的广义第二价格（GSP）拍卖，几乎已成为行业中广告拍卖机制的基准。然而，大多数基于GSP的行业实践都假定用户点击仅依赖于广告本身，而忽略了外部项目的影响，即外部性。最近，深度神经网络拍卖（DNA）尝试用深度神经网络升级GSP，并在一定程度上对局部外部性进行建模。然而，它仅考虑了拍卖中的集合级上下文，而忽略了广告的顺序和展示位置，这仍然不是最优的。尽管基于维克里 - 克拉克 - 格罗夫斯（VCG）的多槽拍卖（如VCG、加权VCG（WVCG））使得对全局外部性（如广告的顺序和位置等）进行建模在理论上成为可能，但它们缺乏对收入和社会福利的有效平衡。

在本文中，我们提出了名为神经多槽拍卖（NMA）的新型拍卖机制，以应对上述挑战。具体而言，我们使用上下文感知列表式预测模块对全局外部性进行有效建模，以实现更好的性能。我们设计了一个列表式深度排名模块，以保证端到端学习中的激励兼容性。此外，我们提出了一个社会福利辅助损失，以在最大化收入的同时有效地减少社会福利的下降。在离线大规模数据集和在线A/B测试中的实验结果表明，NMA在工业实践中比其他现有拍卖机制（即GSP、DNA、WVCG）获得了更高的收入，同时平衡了社会福利，并且我们已成功将NMA部署在美团外卖平台上。

Contextual Generative Auction with Permutation-level Externalities for Online Advertising

  1. 研究背景
    • 在线广告的重要性与拍卖机制：在线广告是互联网行业的核心收入来源，广告拍卖在确保平台收入和激励广告商方面起着关键作用。传统拍卖机制如GSP存在局限性，其独立CTR假设忽略了其他展示广告的影响，即外部性。
    • 学习型拍卖的进展与局限：学习型拍卖如Deep Neural Auction（DNA）和Score Weighted VCG（SW-VCG）虽能更好地捕捉外部性，但受“分配后预测”设计范式限制，仅考虑候选广告集内的外部性（集合级外部性），未考虑最终分配中影响每个广告CTR的顺序上下文（排列级外部性），导致分配非最优。
  2. 方法设计
    • 理论基础与问题建模
      • 多槽拍卖与排列级外部性：将在线广告拍卖抽象为多槽拍卖问题，考虑广告商出价、广告特征、用户特征等因素，定义分配规则和支付规则。引入排列级外部性，即广告的CTR受其他展示广告影响，且不同排列会导致外部影响的差异。
      • 最优多槽拍卖：基于Myerson拍卖理论，推导适应排列级外部性的最优拍卖机制，证明在满足一定条件下，该机制能最大化平台预期收入并满足激励兼容性（IC）和个体理性（IR）约束。
      • 拍卖设计为学习问题：由于直接实现最优分配规则计算复杂，将拍卖机制参数化，通过学习确定参数。引入事后遗憾（ex-post regret）概念，以量化广告商偏离IC条件的程度，将拍卖设计问题转化为最小化预期负收入并满足事后遗憾为零的约束优化问题。
    • CGA框架设计
      • 生成器（Generator）：采用自回归生成模块，包括排列不变集级编码器和排列等变自回归解码器。编码器通过自注意力层和求和池化增强广告表示，解码器基于上下文嵌入学习条件概率，以生成最大化预期虚拟福利的广告序列。
      • 评估器（Evaluator）：预测每个广告的排列感知CTR，通过对广告序列嵌入进行双向LSTM和多头自注意力编码，结合预测阶段的逐点CTR，估计个性化外部性感知校准向量，与逐点CTR元素相乘得到排列感知CTR。
      • 支付计算（Payment Computation）：受神经网络在多物品拍卖中有效近似最优机制的启发，引入PaymentNet学习最优支付规则。PaymentNet的输入包括分配嵌入、自排除出价配置文件和预期价值配置文件，通过sigmoidal激活函数计算支付率，以满足IR约束并输出支付。
    • 优化与训练
      • G-E框架优化：先训练Evaluator至收敛，然后冻结其参数，使用Evaluator估计的排列感知奖励通过策略梯度训练Generator，以最大化虚拟福利。
      • PaymentNet优化：在Generator和Evaluator收敛后，冻结它们的参数，应用增广拉格朗日方法解决约束优化问题，优化PaymentNet，尽管问题非凸，但实验表明优化后的CGA能接近最优收入且遗憾极小。
  3. 实验验证
    • 实验设置
      • 数据集：使用来自淘宝的真实日志数据，包括训练集和测试集，每个样本涉及多个广告商竞争广告槽位，实验设置广告槽位数为3。
      • 基线方法：对比GSP、DNA、SW-VCG、VCG Auction with Permutation-level Externalities（VCG）、EdgeNet和Optimal等方法，根据外部性建模粒度分类。
      • 性能指标：考虑每千次展示收入（RPM）、点击率（CTR）和IC度量（衡量广告商操纵出价可获得的效用相对增加）。
      • 实现细节：设置CGA的特征嵌入大小、注意力机制、隐藏层大小等参数，通过Adam优化器训练，学习型基线方法通过网格搜索调优超参数。
    • 离线比较结果
      • CGA在平台收入（RPM）和CTR方面优于现有方法，且事后遗憾较低，表明CGA能有效近似最优拍卖机制。
      • 随着外部性建模从无到集合级再到排列级的改进，拍卖性能在三个指标上均有提升，突出了精细建模外部性在拍卖设计中的重要性。
    • 消融研究
      • CGA的各设计考虑有效，去除Evaluator或改变训练方式会导致性能下降，证明了G-E框架、外部奖励建模和虚拟价值使用的重要性。
      • 去除价值分布对CGA性能影响较小，可能是因为CGA对外部性的建模通过捕捉广告间相关性，部分反映了缺失的价值分布信息。
    • 在线A/B测试结果
      • CGA在淘宝广告系统的在线A/B测试中表现良好，与DNA相比，RPM提升3.2%，平均响应时间仅增加3ms（相对增加1.6%），同时提高了广告商的投资回报率（ROI）、CTR和商品交易总额（GMV），表明CGA能通过生成模型有效探索分配空间，提升平台收入。
  4. 研究结论
    • 提出CGA框架，用于在线多槽广告拍卖中考虑排列级外部性，理论上证明了经典Myerson拍卖在适应排列级外部性时的最优性，为CGA框架设计提供依据。
    • CGA通过自回归生成模型和G-E学习范式优化分配，通过量化IC约束为预期事后遗憾学习最优支付规则，经离线和在线实验验证有效。
    • 未来研究将扩展上下文生成机制，以整合来自不同渠道的异构项目。
      alt text
      alt text
      alt text
      alt text
      alt text
      alt text
      使用真实监督信号的方式虽然简单直接，但是此类方法只考虑了初始排序这一种排列方式上的物品间关系和用户反馈。假设有序列中有n个物品，其余n!-1种排列方式都被模型忽略，不利于寻找最优排序。
      refer

基于listwise模型的rerank的实现方法。而在listwise模型中根据做法的不同又可以分为序列生成式、基于序列表征pointwise式、半生成式、两段式和强化学习等几种不同的方案。

model方法

基于序列表征，pointwise打分

这一大类有一个共同的特点，都是以上层精排的输出序列作为输入，在模型结构上借助RNN等序列结构来引入item序列之间的影响。进一步的通过attention的方式来捕捉item之间的相互影响。典型的如DLCM模型。而在阿里的PRM中进一步地将用户的个性化向量通过和item结合的方式引入模型中。这些模型第二个共同特点是最终线上对item的打分还是pointwise的，直接输出序列中每个item的分数，根据分数从高到低排序。

DLCM

alt text
refer
DLCM模型主要包含3个步骤：

  1. 使用传统的LTR模型检索Top N个doc，具体做法将查询-文档对 $(q,d)$ 转化特征向量 $\mathbf{x}_{(q,d)}$，然后使用全局排序函数 $f$ 计算查询 $q$ 的Top N个doc的列表 $R_q^n$

  2. 使用GRU对Top N个doc的特征向量 $\mathbf{x}_{(q,d)}$ 进行编码，从低位置到高位置，一步一步地输入进GRU中，最终产生一个隐向量 $s_n$ 和n个隐层输出 $o_i$， $i \in [1,n]$。这个局部模型被称为local context model - $I(R_q,X_q)$，输出被称为local ranking context

  3. 该步为对Top N个doc进行重排序，使用的是local ranking function (局部排序函数) $\phi$，并且该函数的输入为 $s_n$ 和 $o$

PRM

alt text

  • 用transformer来克服RNN距离遗忘的问题，从而显式建模item之间的相互影响
  • 在transformer中加入用户兴趣的建模 (Transformer equipped with personalized embedding)
  • 其中个性化LTR Loss形式:

$$\mathcal{L} = \sum_{r\in\mathcal{R}} \ell({y_i, P(y_i|X,PV;\hat{\theta})|i\in\mathcal{S}_r})$$

PV矩阵会和输入模型的初始item特征矩阵拼接，PV矩阵由预训练模型(CTR预估模型)产生

Challenges

  • 重排序后的评分困难：无法为每个反事实列表获取反馈
  • 指数级时间复杂度：组合优化问题，存在n!种可行排列

评估生成范式

  • 评估器(Evaluator)：Evaluate listwise utility
  • 生成器(Generator)：Generate feasible permutations

SetRank

序列生成

上面的那些方法都是基于预估分数重排，而下面的这些方法主要利用 RNN 直接生成重排序。

seq2slate

考虑了前序信息，通过 RNN 来提取前序信息，再通过 pointer network 来从输入商品列表中一步步地生成最终推荐列表。训练时采用 REINFORCE 算法去训练，并且用的是监督式的方法去训练。
ptrnet：比如求第一个位置，就和encoder部分的都求一遍权重，和第一个关系最大，就输出1，没有词汇表，输出从输入里面选

alt text

GRN

Two-Stage

SetToSeq

PIER

alt text

RL

从action space的角度出发，基于RL的混排模型可以分为以下两类:

离散action space

  • 以不同类型结果的mix pattern为action space
  • 代表工作: Cross DQN: Cross Deep Q Network for Ads Allocation in Feed
  • 实现方式:
    • 每种内容的结果经过精排后形成内部有序队列，如:
      • A=(a1,a2,a3,a4)
      • B=(b1,b2,b3,b4)
      • C=(c1,c2,c3,c4)
    • RL model的action space是不同类型内容的混排pattern
    • 每种混排结果对应一种结果类型的mix pattern
    • 示例:mix pattern = AABCB，输出mix list=a1-a2-b1-c1-b2
    • action space size = x^N (x为结果类型数,N为混排list长度)
    • state包含user side info和当前各队列候选list等context
    • 特例:某些场景需要决定是否在首位透出广告/直播,此时action space简化为透出/不透出

连续action space

  • 以多目标融合公式的加权系数作为action space
  • 代表工作: Multi-Task Fusion via Reinforcement Learning for Long-Term User Satisfaction in Recommender Systems
  • 实现方式:
    • 精排后每种内容的混排分由统一的多目标融合公式给出
    • 示例:mix_score = w1 * ctr + w2 * wtr + w3 * ltr
    • RL学习个性化权重wi
    • 采用non-Deterministic Policy Gradient时,w由学习的均值mu和方差sigma决定
    • state包含user side和context信息

三、方案比较

  1. A方案(离散action space)特点:

    • 一般采用double-DQN等模型
    • action space不宜过大(需要对离散空间取max)
    • 便于控制不同类型结果比例
    • 适合流量调控(根据mix pattern修正reward)

  2. B方案(连续action space)特点:

    • 基于多目标融合公式进行混排
    • RL用于动态调整系数,实现个性化
    • 需要处理不同内容pxtr的量纲不一致问题
    • non-Deterministic Policy的方差可提供探索能力

京东

refer
基于强化学习的序列优化
alt text

alt text
序列生成和评估模型结构包含两个主要部分:

  1. 序列评估模型
  • 底层进行特征抽取,使用Point DNN结构对每个item单独抽取特征
  • Point DNN将稀疏的embedding转化为dense feature,得到item的特征向量
  • 在序列评估模型中,将序列对应的向量抽取组成序列
  • 对序列进行attention操作,突出最相关的特征
  • 输出每个item的预估点击率,与出价、多样性等业务指标融合得到最终得分
  1. 序列生成模型
  • 输入:将整个候选集合作为生成模型的输入
  • 特征处理:
    • 对候选集中所有item特征做max pooling得到候选集合的特征向量
    • 将集合特征向量与每个item的特征向量拼接得到新特征
    • 新特征经过多层DNN处理得到概率矩阵

如图举例，假设一共有五个item，序列长度是四。如上图左上的表格，按行来看表示的是每一个item出现在当前这个位置的概率，按列来看表示的是item出现在不同位置的概率。模型训练使用2D softmax的交叉熵loss。如果一个item在候选集里被选中了，并且是出现在第一个位置，它的第一个位置的label就是1。如图，SKU1在第一个位置label是1，SKU2在第三个位置label是1。训练完成的模型在线上预测过程中预测采样频率，用一个受控的temperature参数来控制这个采样频率。按照这个表去生成序列，逐个位置去采样多次生成多个序列。举例来说，生成第一个位置需要的SKU，类似扔一个骰子，如果小于0.9，SKU1被选中，如果是0.9到1，SKU2被选中。第二个位置去除第一个位置已经出现过的SKU，进行重新归一化，再采样一次，这样可以生成多个候选序列。再把这些候选序列与启发式的或者随机生成的序列融合起来，变成一个序列的候选集，统一交给序列的评估模型去评估，选出一个最好的序列。

美团

（页面级序列建模）Deep Page-Level Interest Network in Reinforcement Learning for Ads Allocation.

Accepted by SIGIR2022
alt text

（多通道建模）Cross DQN: Cross Deep Q Network for Ads Allocation in Feed

alt text

Reinforcement Learning to Rank with Pairwise Policy Gradient

这篇论文关注的是信息检索（IR）中的文档排序模型的强化学习（RL）。其中一个分支的方法是将排序过程形式化为马尔可夫决策过程（MDP），并通过策略梯度来确定模型参数。尽管这些方法已经取得了一些初步的成功，但它们仍未完全实现其潜力。现有的策略梯度方法直接使用采样文档列表的绝对性能分数（回报）在其梯度估计中，这可能导致两个限制：1) 无法反映同一查询内文档之间的相对优劣，而这通常与信息检索排序的本质更接近；2) 产生高方差的梯度估计，导致学习速度慢和排序准确性低。为了解决这些问题，本文提出了一种新的策略梯度算法，即成对策略梯度（Pairwise Policy Gradient, PPG），该算法使用同一查询下采样的两个文档列表进行成对比较来确定梯度。PPG算法重复采样文档列表对，通过成对比较估计梯度，并最终更新模型参数。理论分析表明，PPG能够做出无偏且低方差的梯度估计。实验结果也证明了在搜索结果多样化和文本检索方面，相比现有最先进基线方法，PPG有显著的性能提升。

个性化

Multi-Level Interaction Reranking with User Behavior History

该研究关注的是多阶段推荐系统（MRS）的最终阶段——重排序（reranking），其直接关系到用户的体验和满意度，在MRS中扮演着关键角色。尽管现有工作已经取得了一定的进步，但仍有三个问题尚未得到解决：

  1. 用户历史行为中的偏好信息未被充分利用：用户的历史行为包含丰富的偏好信息，例如用户的长期和短期兴趣，但在重排序过程中并未被充分挖掘。以往的工作通常将历史记录中的项目视为同等重要，忽略了历史与候选项目之间的动态交互。
  2. 现有的重排序模型主要关注项目级别的交互，而忽略了特征级别的细粒度交互：这导致了对项目之间细微影响的捕捉不足，从而影响了重排序的效果。
  3. 在重排序前对初始有序列表进行评分可能导致过早评分问题：这种做法可能会产生次优的重排序性能，因为评分是在固定顺序下进行的，未能充分考虑到不同排列可能带来的不同效果。

为了解决上述问题，本文提出了一种名为多层次交互重排序（Multi-level Interaction Reranking, MIR）的框架。MIR结合了低级别的跨项目交互和高级别的集到列表交互，其中将待重排序的候选项目视为一个集合，而将用户按时间顺序的行为历史视为一个列表。我们设计了一个新颖的SLAttention结构来建模集到列表的交互，并融合个性化长短期兴趣。此外，为了捕捉项目之间的细粒度影响，我们还引入了特征级别的交互。MIR的设计确保了输入项目的任何排列不会改变输出排名，这一点我们在理论上也进行了证明。

具体模型

PRM具体模型

4.2 Input Layer (输入层)

  • **Personalized Vector (PV)**：个性化向量

    • 尽管精排队列给出的列表已经有部分个性化结果了，但对于整个用户的个性化结果来说，还不够
    • 本文拼接原始的特征向量X与用户个性化的向量PV(图1b)，从而重排阶段引入用户个性化

  • **Position Embedding (PE)**：位置向量

    • 为了利用精排队列中的items的序列信息，本文引入位置编码向量PE(可学习)
    • 使用方式与[X;PV]+PE
    • 在输入向量之后使用FFN进行编码与维度转换，得到图1b中输入层最后的e

4.3 Encoding Layer(编码层)

  • 编码层目的是学习items对与额外信息(用户偏好、items初始列表)之间的交互(图1a)
  • 本文使用N层Transformer进行编码，主要考虑到了:
    • TRM的并行
    • self-attention不会依赖item之间的距离等因素
  • 从图1a可以看出，本文使用的Transformer block与原论文基本一致，也是用到了Multi-head Self-Attention，FFN等结构

4.4 Output Layer(输出层)

  • 输出层目标是为每个item打出一个重排得分
  • 此处最终使用softmax函数进行输出
  • 输出结果为点击每个item的概率
  • 训练模型时，本文使用点击相关数据完成训练，最终损失函数为交叉熵
    $$\mathcal{L} = \sum_{r\in\mathcal{R}} \ell({y_i, P(y_i|X,PV;\hat{\theta})|i\in\mathcal{S}_r})$$

4.5 Personalized Module(个性化模块)

  • 直观来说，可以直接用PRM来端到端学习用户个性化向量PV
  • 然而在重排阶段学习PV，缺少了用户的通用偏好信息
  • 因此本文使用预训练模型生成用户个性化向量(图1c)
    • 输入为用户的点击序列items(H)，当前item与用户user的信息(性别、年龄、购买力等)
    • 训练数据仍然使用点击数据
    • 损失函数为二分类交叉熵
    • 最终取sigmoid之前层网络的输出结果作为用户个性化向量PV
  • 由于是CTR任务，作者也建议使用FM、FFM、DeepFM、DCN、FFN、PNN等用来学习PV