今天分享一篇最新研究探索与利用的文章，是阿里妈妈发表在KDD2022的文章， Adversarial Gradient Driven Exploration for Deep Click-Through Rate Prediction (AGE)，研究了如何在精排CTR模型中研究探索与利用问题(Exploration-Exploitation)。 与以往工作不同的是，AGE可以在不改变 CTR预估分布 的前提下进行有效的探索，能够显著提升模型收敛速度和CTR等指标，也能够解决长尾和冷启动item的CTR准确预估。
- Motivation =============
现有的精排模型主要在收集的曝光数据上进行训练，大多面临着严重的 feedback-loop 问题：即：模型在曝光数据上进行训练，然后展示items给用户，收集到的曝光item数据又会作为模型的输入进行更新，长此以往曝光偏差和马太效应会越来越严重，模型很容易陷入“自嗨”状态，只对头部ITEM学习充分，造成大量 新ITEM 或 长尾ITEM 无法被正常学习，预估置信度低，得不到正常的曝光机会。很可能推荐用户已经不感兴趣的item，影响用户体验。
为了证明 曝光量 和 模型预估 分之间的关系，作者画了一幅图，画出真实点击率和曝光量之间的关系。可以看出，在阿里这个场景下，一个新的item需要平均1W次曝光点击率才会收敛。换句话说，曝光在1W次以下，点击率可能都不是置信的，存在低估的可能，和其真实点击率相去甚远。
这实际上引出了现有推荐/搜索等系统普遍存在的一个困境 ：关于 曝光资源分配 和 预估置信度 之间的权衡，即：如何给用户展示其感兴趣并曝光足够的item (曝光量足够时预估点击率才更准)，同时还能为新item或长尾item预留足够的曝光资源(资源充分利用 ，不浪费 )。
工业界面对这种问题，常见的方法是通过冷启动、多样性、探索与利用(EE)等策略。本文主要研究EE问题。对于探索与利用，常见的比如UCB，汤普森采样等，其本质原理在于，给予模型 预测值不确定性大 (比如预测值置信区分宽度)的item曝光机会，再基于用户的行为反馈快速筛选出高价值的item，淘汰低价值的item，最终item的模型预测值会收敛到其期望值附近。实际上是在模型预测 准确率 和预测 不确定 之间做权衡。
由于引入了不确定性，item最终的预估值分布会和真实分布存在 较大的diff 。比如在UCB方法中，预估的不确定性上限值会加到原始模型预测值上，形成最终的预测分。而 预估分布的变化 可能会影响 广告 等真实业务。
为了解决 预估分布偏移较大 的问题，作者提出可以将探索模块嵌入到CTR模型中，在 输入侧 进行不确定性的建模和扰动，而不是在 预估输出侧 进行扰动。这样的好处是可以保证探索后的预估分布和原始预估分布较为一致和对齐。
本文的 主要贡献 包括：
- 精排EE&不改变预估分布 ：作者提出了一种对抗梯度探索策略（Adversarial Gradient driven Exploration，AGE）来处理探索与利用问题。在AGE中，作者引入了一种伪探索模块在精排模型中模拟探索，且能够保证探索后CTR预估值和未探索时的CTR预估值分布一致；
- EE效率&曝光资源充分利用 ：提出了一种动态阈值单元（Dynamic Threshold Unit ，DTU）来决定需要探索哪些有价值的Item，过滤低价值的item，避免将资源浪费在低价值item的探索上，能够有效提升探索效率和指标；
- 在离线评估 ：在学术数据集做离线评估，在阿里在线展示广告平台中做A/B测试，验证了AGE的有效性，同时能够加快精排模型的收敛速度。
- Solution ===========
整体的方法一言以蔽之。在精排CTR模型中，引入一种 伪探索模块 进行探索，会基于CTR预估的 不确定性 和 对抗梯度 在输入侧做扰动，不确定性越大，则扰动越大，代表探索程度越大。同时引入了一个 动态阈值单元 来建模item的期望CTR值，输入是item的特征，输出是doc的CTR值，衡量了item的 潜力 ，若精排模型的CTR值小于动态阈值单元的CTR值，则认为该item是低潜力的，就不进行扰动做EE，否则进行扰动。
下面来分别介绍探索模块和动态阈值单元。
2.1 伪探索模块：Pseudo-Exploration Module
伪探索模块的目标是：
即：控制扰动在一定范围内，最小化扰动后的CTR预估值和真实之间的损失。是超参数，即：每次扰动L2范数会小于该值。
但不是所有的item都有label 。为了解决这个问题，作者认为伪探索模块 的目标是提升CTR低估item的曝光概率，因此默认被探索item的。但1是CTR值的上界，真实CTR值肯定是小于1的。为了解决这个gap，会在扰动上界的基础上继续乘个降权系数。CTR 低估的越严重 (不确定性越大)，其扰动上界也越大，让其CTR优化越逼近1，越有机会做探索；未低估时，则尽量不进行扰动，也即扰动的上限逼近0。因此扰动上界的系数应该与CTR预估的 不确定性程度 正相关，给不确定性大的item 更多的扰动机会 。因此新的目标是：（原paper此处是argmax个人认为是笔误，等正式camera ready了）
上述目标的解是：
其中，衡量了CTR预估值的不确定性，作为扰动大小的步长。是对抗梯度，是扰动的方向。是超参数。下面介绍和的计算方法。
2.1.1 不确定性计算方法
参考 SIGIR2021 关于汤普森采样和梯度下降结合做EE的工作[3]，采用蒙特卡罗-dropout (MC-Dropout[4])策略来计算不确定性。
首先简单介绍下MC-dropout，一种衡量模型预测不确定性的方法，核心思想是需要对同一个输入进行 多次前向传播过程 ，这样在 dropout 的加持下可以得到“不同网络结构”的输出，将这些输出进行平均和统计方差，即可得到模型的预测结果及 uncertainty 。这个过程是可以并行的，时间上可以等于进行一次前向传播。实现起来其实就是dropout，唯一的区别在于MC-dropout在infer/test阶段也要打开dropout，把Dropout当作一个天然的随机发生器，通过多次前向传播来计算不确定性。实现起来形如：
其中，就是通过伯努利分布采样得到的mask，shape和一样，是element-wise的乘法，等价于在上做随机丢弃，这样不同的mask就能够产生不同的输出值，每个可以理解为是从 真实CTR分布 上 采样 得到的。MC-dropout的好处在于不需要改造原来的精排模型，实现起来非常方便。得到了MC-dropout采样的多种后，就可以计算不确定性了。一种方式是UCB中的多次采样并计算的方差/标准差。
不添加扰动的预测值可以理解为CTR预估的期望值，是具体某个sample，上述就是 预估的标准差 。
还有一种是汤普森采样中的单次采样 ，直接拿单个采样的deviation衡量不确定性，即：
2.1.2 对抗梯度计算方法
第一种是快速梯度法(Fast Gradient Method)，也即单步梯度下降，即：
可以看到，求的是未扰动时对的梯度。也即扰动的方向是跟着y对x的梯度方向走的 。用数学的方式就是沿着曲线的切线或一阶导数的方向移动，这样能够尽可能保证扰动不会影响整体值的分布，同时扰动是沿着y值增长的方向 ，使得探索后的CTR值会大于原始CTR值，达到探索的目的 。如下图红色箭头部分所示：
再做个梯度的归一化，得到单位梯度，重点关注的是 梯度的方向 ，而不是大小：
上述单步梯度可能不能准确地计算好对抗梯度(没有解释)。作者提出采用投影梯度下降法(project gradient descent)，采用T步梯度更新(原文公式2有笔误)：
上述第二个递推式的意思是先对做扰动后，再计算扰动后的预测值对的梯度，然后更新，共执行T步。
有了扰动的大小和方向的计算方法后，就能够得到伪探索预测分数 ，即：
以往的工作[5]可以证明这种 对抗梯度扰动 能够衡量模型的 泛化性 。换一种视角来理解，这种对抗干扰本质上是探索发现哪些samples在输入空间泛化性很差，泛化性差就做扰动和探索，并保留在训练样本中做继续训练，直到泛化性变好或不确定性变小为止。
2.2 动态阈值单元：Dynamic Threshold Unit
从前文图1我们可以看到，item的CTR会随着曝光的增长而增长，直到收敛。因此，如果某个item的CTR没有随着曝光有增长的趋势，实际上就不是潜力item，没有必要做探索了。因此，如果 探索后的CTR值小于未探索前的CTR ，那实际上就没必要做探索了。应该把探索的机会给那些高潜的item。
为此，探索系统需要一个 动态阈值单元 来过滤低CTR的样本。所谓的动态阈值是指不同item有不同的阈值，大于该阈值则认为有探索价值。这本质上类似一个潜力预测模型。作者的做法是使用一个简单的网络，输入的特征只包括item侧的特征(类似item单塔网络)，来预测item的期望CTR。即：
即为阈值，当探索模块的预测值小于该值时，则不进行探索，否则进行探索。则最终探索精排分为：
加了一个0/1的指示函数，小于阈值时，扰动项未0，即不进行扰动。
到此为止，我们可以看一下 整体的模型架构 ：输入侧1条样本包括了user侧特征、item侧特征，经过embeddinng后：
- 探索CTR预估 ：全部特征concat后经过多层DNN后，得到特征向量，进入伪探索模块。伪探索模块会基于MC-dropout参数对特征向量做mask，并进行单多次前向传播，然后计算CTR预估方差衡量预估不确定性，计算出扰动大小(预估不确定性)；基于 对 的梯度得到扰动梯度，最终得到扰动项；
- ITEM期望CTR预估 ：item侧的特征concat后进入动态阈值单元，输出该item的期望CTR值，作为阈值，如果探索CTR预估值大于该阈值则进行扰动，否则不进行扰动。 根据上述的扰动项以及探索的CTR门槛值，对 做扰动，并继续做一次前向传播，输出探索后的预测值。
AGE整体架构
整体实现思路其实还是比较清晰的。有个单独的探索模块做多次前向传播和不确定性预测；有个单独DTU模块来决策是否要进行探索。得到扰动项后，过1次前向传播得到最终探索后的CTR预测值。
2.3 学习目标
学习目标有2个，包括探索CTR预估目标和动态阈值单元目标。
第一个损失即带MC-dropout进行探索的CTR预估损失；第二个是item维度全局的CTR期望，即：DTU模块的损失。
- Evaluation =============
采用著名的LinUCB[6]的数据集：Yahoo! R6B dataset，2800W条数据，总共涉及652篇文章，是一个无偏数据集，具体数据收集上，用户每次访问时，有38个候选文章，每次随机从其中选择1个文章曝光给用户，并收集用户反馈。能够避免系统固有偏差导致的 评估有偏 。个人理解这是使用随机流量做的一个全观测数据集，652篇文章几乎能够收集到所有用户的反馈行为。这样离线时可以通过日志replay方式来评估点击数等指标。【此处原文写的实在太难懂，欢迎指教】
评估指标：点击数(无偏数据集，有真实点击数据)，参考了[3]和[8]的方式。
网络实现上，设置为0.001，MC-Drop为0.01，采用PGD。根据不确定性计算分为：AGE-TS和AGE-UCB(N=20次，20次前向传播来计算不确定性)。训练时在前8W条日志上进行初始化CTR模型训练，然后在剩余的数据上进行不确定性AGE模型的训练。
3.1 对比实验
- DNN-greedy strategy ：完全基于DNN训练的，无探索策略，可以作为benchmark；
- Random Strategy ：随机探索；
- 𝜖-greedy strategy ：的概率选择DNN预测结果；概率选择随机探索；
- Ensemble-TS and Ensemble-UCB ：训练5个DNN模型。然后用所有模型的预估方差来衡量不确定性，使用汤普森采样或UCB来做探索；
- Gradient-TS and Gradient-UCB ：上述Ensemble-TS和Ensemble-UCB基础上，使用梯度norm来衡量不确定性，而不是预估值方差；
- GP-TS and GP-UCB [8]：使用高斯过程来推断不确定性；
- UR-gradient-TS and UR-gradient-UCB [3]：采用低估调整方法(underestimation refinement methods)来做探索。
对比实验
3.2 消融实验
评估不确定性中的大小和对抗梯度方向、DTU的影响。
还做了梯度优化的对比以及DTU和固定阈值的比较：
3.3 在线A/B测试
在阿里的 展示广告平台 部署，实验时间是2021年4月这一整个月。实验细节：
- base是6层DIEN，在这个基础上加入AGE探索；
- DTU的模型是2层的MLP；
- 探索不确定计算时：，UCB中的N=20；
- 新Item定义为曝光次数小于3000次的items。
采用的指标：CTR、PV、PCOC(预估CTR/真实观测CTR，衡量了CTR预估是否有偏，越接近1越准，大于1高估，小于1低估)、AFR(广告follow-up率)。
下表是对 新item 做探索后的指标，ensemble-UCB相比于base模型负向；汤普森采样是正向的；其中AGE-TS最为显著。包括PCOC也更接近1。做了 预估不确定性的探索 ，CTR指标上能取得 正向效果 还是很厉害的！
作者还画出了AGE-TS 在线预估CTR 和 曝光数 的关系。可以看出收敛性提升了非常多。 曝光很小的时候 ，CTR就基本 收敛到了均值 。这能够说明AGE-TS一方面能够使得整体CTR预估的更准，另一方面对于长尾、冷启的item也能够 预测的更准 。
- Conclusion =============
这篇文章整体上还是非常有意思的，在精排模型里直接加入这种探索模块做EE，相较于以往在精排后置链路中做EE策略有很大的不同。既能够保证CTR预估精准，还能够显著解决长尾、冷启动item的推荐，同时探索机制能够缓解系统的feedback loop问题。未来实际上可以考虑在召回、粗排等链路也加入这种探索机制。
[1] 阿里妈妈技术团队5篇论文入选 KDD 2022: https://zhuanlan.zhihu.com/p/5187829902
[2] Song Y, Wang L, Dang H, et al. Underestimation Refinement: A General Enhancement Strategy for Exploration in Recommendation Systems [C]//Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2021: 1818-1822.
[3] Yuhai Song, Lu Wang, Haoming Dang, Weiwei Zhou, Jing Guan, Xiwei Zhao, Changping Peng, Yongjun Bao, and Jingping Shao. 2021. Underestimation Refinement: A General Enhancement Strategy for Exploration in Recommendation Systems . In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. 1818–1822.
[4] Yarin Gal and Zoubin Ghahramani. 2016. Dropout as a bayesian approximation: Representing model uncertainty in deep learning . In international conference on machine learning. PMLR, 1050–1059.
[5] Andras Rozsa, Manuel Günther, and Terrance E Boult. 2016. Are accuracy and robustness correlated . In 2016 15th IEEE international conference on machine learning and applications (ICMLA). IEEE, 227–232.
[6] Lihong Li, Wei Chu, John Langford, and Xuanhui Wang. 2011. Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms . In Proceedings of the fourth ACM international conference on Web search and data mining. 297–306.7
[7] Kevin P Murphy. 2012. Machine learning: a probabilistic perspective . MIT press.
[8] Chao Du, Zhifeng Gao, Shuo Yuan, Lining Gao, Ziyan Li, Yifan Zeng, Xiaoqiang Zhu, Jian Xu, Kun Gai, and Kuang-Chih Lee. 2021. Exploration in Online Advertising Systems with Deep Uncertainty-Aware Learning . In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.
交流群：点击“联系作者”--备注“研究方向-公司或学校”
欢迎|论文宣传|合作交流
往期推荐
[【资源分享】还在找学习资源吗？
2022-06-27
[如何在跨域推荐中使用对比学习？
2022-06-26
[「快手+中科大」全曝光推荐数据集KuaiRec 2.0版本
2022-06-25
长按关注，更多精彩
点个在看你最好看