腾讯广告X中科院计算所WWW2021论文：在线广告中的探索与优化

• 2021 年 5 月 19 日
• AI

01

​让人头疼的赌博机

未来的某一天，疫情终于结束了，大家都开开心心地出门旅游。如果你是去澳门和拉斯维加斯的赌场，一定会看到这样的成排的老虎机。

每台老虎机都可以投币，按下按钮或者拉一下拉杆之后屏幕上的几列图案就会滚动起来，如果停下来的时候刚好对齐了一列一样的图案，你就能赢走一小把硬币。但每台老虎机也不完全一样，除了机器的外观、滚动的图案不一样，对齐图案让你赢钱的概率也不一样大。

也许一个区域的十几台老虎机里赢钱概率有高有低都不一样，试过三四台以后我们就会遇到这样的状况：已经差不多知道前面这几台里哪一台最容易赢钱了，但还没试的里不知道有没有更容易的，要是有，再找一阵子也值得；要是没有更容易的，那我在已经找到的机子上玩就好，继续试后面的反而浪费时间浪费币了。

但很可惜，我们没办法知道后面的机子的情况，赌场的工作人员是无论如何都不会告诉你的。而越是我们时间不多、不想浪费钱，就越难抉择要不要继续试更多的机子。

02

推荐系统也受E&E 问题的困扰

刚才这样的老虎机难题可以总结得更普遍一点：在“更多地进行尝试、获取更全面的信息之后再重新决策”和“利用当前已有的部分信息和经验做决策”之间做平衡，探索带来的好处是以后可能能做出更好的决策，坏处是需要牺牲当下的收益。这就是探索&利用 exploration & exploitation，E&E 问题。而且越是资源有限的时候，这样的问题就越难解决。

E&E 问题在较为贴近实际的机器学习任务中出现的时候往往会更复杂。我们都知道如今各个网络购物平台都有推荐算法，根据每个用户的购买记录、浏览记录、搜索记录推荐最有可能感兴趣（最有可能购买）的商品给他。购物平台会不断有新的商品加入，既有已有品类的新款式，比如新款的衣服、包包、手机，也可能连品类都是全新的，比如冲牙器、新风空调、扫地机器人、外卖料理包。新商品应该选用怎样的推荐策略就是一个典型的E&E 问题，直接用现有的类似商品的推荐策略基本上不会销量很差，但谁也没法确定尝试新的策略以后会不会更好、具体哪种新策略最好。平台都希望能有一些好的算法，在沿用已有策略（利用）和尝试新的策略（探索）之间取得平衡，得到更高的总体收益。

学术界尝试提出过一些方法体系化的方法来处理E&E 问题，一类方法是贝叶斯方法 ，相当于根据广告推荐后的用户反馈的结果猜测他可能本来喜欢的是什么，逐步寻找根本因素、逐步优化推荐结果。贝叶斯方法的主要缺点是，只有推荐模型比较简单的时候才能用明确的公式表示出推荐所需的后验概率，在如今规模的数据量和模型规模下很难求解。而且，一些人类可以用逻辑判断推理出的结论，通过算法来学习推断可能非常困难，比如对于新风空调这个新品类，它和空调类似，我们人类可以用逻辑判断出需要新风的人实际需要更好的空气质量，购买人群可能和空气净化器比较接近；但想要通过算法完全从商品信息和历史数据中得到这样的结论、并且把符合程度量化就非常困难。即便用一些近似办法求解，计算过程也代价高、速度慢，没法用在在线广告推荐中。

另一类方法是非贝叶斯方法，比如重采样+集成，从全部的训练数据（用户行为数据）抽取出几个有所不同的子集，在每个子集上分别训练推荐模型，可以得到几个各有不同的模型，对于同样的新商品可以得出不同的策略；最后综合使用这几个模型，每次都随机选用其中的一个推荐结果，可以达到一定的探索效果。但同贝叶斯方法相比，这种方法缺乏理论保证、缺乏引导性，每个分出来的模型仍然分别存在E&E 问题，也仍然无法改善从很少的数据开始的冷启动问题。

03

用GuideBoot解决E&E 问题

今年，在线广告推荐任务中的E&E 问题迎来了一种新的解决思路。腾讯广告和中科院计算所合作的论文《GuideBoot: Guided Bootstrap for Deep Contextual Bandits in Online Advertising》创新型地提出了一种探索与利用算法GuideBoot，在广告推荐场景下相比于主流算法取得了更好的探索与利用效果，并被WWW2021会议接收。

WWW（The International Conference of World Wide Web）会议是互联网和数据挖掘交叉领域的顶级会议，有悠久历史，在计算机科学的学术界和工业界中都有重大影响力，中国计算机学会（CCF）也把它评为A级会议。WWW2021、也是第30届WWW会议即将于4月在线上召开，主会从4月19日到4月23日，会议在1736 篇投稿中共接收 357 篇论文，接受率仅为 20.6%。

和传统的重采样+集成方法类似，GuideBoot算法也会分出不同的数据、训练多个不同的推荐模型，然后在需要输出结果的时候从其中随机选用一个。不同之处在于，GuideBoot增加了明确的引导性，会根据不确定性程度以一定的概率生成一小部分带有随机伪标签的数据样本，把它们也用于这些模型的训练。

根据作者们的设计，随机伪样本可以有效地引导改善E&E 问题。随机伪样本的来源实际上是真实数据换了标签，比如某用户实际上买了某商品，但这里变成没买。在模型训练过程中会持续计算模型对不同样本的不确定性，这个不确定性越高，就会让训练数据中随机伪样本的比例越高，明确地引导模型有针对性地探索，多尝试和之前不同的推荐策略；反过来，不确定性低时，模型很可能已经找到了一个不错的推荐策略，就减小随机样本比例，鼓励算法更多地利用好当前模型的预测。这种设计为不同的模型之间增加了更多的随机性，从而可以引导进行有针对性的探索，可以降低模型对不充足数据的过拟合程度。

根据不确定性选择训练方向的这个设计和贝叶斯方法有不少的联系，都考虑到了不确定度对模型的影响。作者们也做了理论分析，表明这个设计是一种贝叶斯方法的近似，从理论角度说明了方法的可靠性。而实际的运行中，本来的贝叶斯方法即便在模型部署之后也需要在每次预测（广告推荐）之后都计算不确定性，而且计算的开销通常较大，GuideBoot算法只需要在训练时执行这个操作，模型预测和在线决策时代价小、速度快，非常适用于高吞吐量、低延迟的广告在线推荐场景。

可以说，GuideBoot兼具了两种传统方法的优点，而且还方便用于实际应用。

作者们进行了充分的实验，用数据展现GuideBoot的优势。首先为了验证算法在理论上的正确性和效果，作者在经典的生成数据环境中进行了测试。生成数据上常用的评价指标是“平均遗憾值“，即算法做出的选择和理论上最佳选择之间收益期望的差距。总体的平均遗憾值越小说明算法做出的选择越好。在生成数据的测试中，GuideBoot（图中黑线）取得了最少的遗憾值，体现了算法高效的探索能力和对探索利用平衡的准确把握。

针对于广告推荐场景，作者也在基于腾讯广告真实业务场景下的数据进行了测试，评价指标为总体平均收益。GuideBoot（表格最后一行）在测试中取得了最高的平均收益，且重复实验表明算法收益本身的波动较小，其效果能得到稳定的提升。

04

在线版本的GuideBoot

除了标准的训练、测试流程之外，作者们还花了功夫对GuideBoot做了衍生改进。

在真实的在线广告推荐中，数据是持续产生的，广告推荐策略也是需要持续优化的。比如腾讯广告的业务规模已经达到了每天都有百亿级的曝光、亿级的点击转化，广告推荐系统最好能够紧跟变化、持续地利用新增数据优化推荐策略。但这样规模的数据是传统的批处理式训练解决不了的。

所以如果想要在真实业务中使用GuideBoot，就必须做一些改进，让它更多地采取在线学习的训练方式，以便对应百亿级数据、秒级延迟持续产生的数据流。

针对在线学习改进的Online GuideBoot，主要区别在于把实时的数据流存成一包包的缓存，然后打乱、随机分割，交给不同的模型学习。由于在训练过程中，该改进版本不再能对所有的历史数据进行采样，而只能使用实时的数据流，在经典的生成数据环境下Online GuideBoot（图中红线）效果不如原版的 GuideBoot（图中黑线），但其表现仍超过了其他主流的方法。

而在腾讯广告数据的测试显示，由于 online 版本能更好地紧跟在线环境的变化，在真实的在线数据中，online 版本能取得更好的效果，而且也同样相比其他方法能获得稳定的效果提升。

结束语

在论文《GuideBoot: Guided Bootstrap for Deep Contextual Bandits in Online Advertising》中，作者们提出了一种针对广告推荐系统中的探索与利用问题的新方法，并且设计了适用于大规模在线学习下的衍生版算法实现，在经典生成数据环境和广告推荐真实业务数据上测试都取得了稳定的提升效果。除了在线广告推荐之外，GuideBoot算法也可以广泛用于解决各种研究领域和行业应用中的探索-利用问题。

目前腾讯广告正在热招广告策略算法高级工程师，欢迎点击“阅读原文”踊跃投递简历

广告策略算法高级工程师（深圳）

岗位职责：

参与以下一到多项工作：
1. 广告竞价排序机制的设计与优化， 包括但不限于粗选召回策略优化、精选排序公式和auction机制设计、排序全链路目标一致性等工作；
2. 设计适用于广告业务线上场景，满足高精度、高吞吐量、低延迟约束的大规模点击率/转化率粗选模型；
3. 广告冷启动机制设计；以及相关算法策略如模型冷启动预估/Explore-Exploit算法设计等工作;
4. 设计可以帮助广告主更好度过冷启动的起量、拿量产品工具；
5. 以广告系统全链路视角，解决广告主在投放效果、体验上的其他问题，比如稳定性、成本达成;建设排序问题分析系统，解决各种疑难杂症;

我们希望你：

1. 有扎实的编程功底，掌握算法/数据结构等基本知识，能熟练使用C/C++/Java/Python中至少一门语言，熟悉linux开发环境
2. 深入掌握两种以上机器学习算法(包括但不限于逻辑回归，FM, 决策树，svm，最大熵，神经网络)， 具备相应的数学功底；
3. 有强大的自驱力、有激情；能主动思考，解决问题；
4. 有良好的团队合作意识；
5. 有强烈的业务导向意识，以业务目标引导技术优化；
6. 有推荐/广告/搜索系统排序相关，点击/转化率模型预估，大规模机器学习系统等工作经验优先

封面图来自 rstudiogstock – //www.freepik.com