搜索广告与广告网络Demand技术-探索与利用

探索与利用(Explore and exploit)

点击率预测中还有一个重要的问题,就是探索与利用,它在工程中解决的并不好,我这章把现在论文中的常见的几种方法介绍一下。探索与利用它是所有互联网应用都要面对的一个问题,形式化一些,可以解释为:整体的效果是无法通过采样得到的,因为观察到的数据只是投放过的广告,而很多还没有投放的广告,想得到它们的效果,就很困难。

计算广告领域的探索与利用要解决的问题是:因为长尾(a,u,c)组合极大部分在系统中并没有出现过,所以没有这些长尾(a,u,c)的统计量,所以要探索性地创造合适的展示机会以积累统计量,从而更准确地估计其CTR。但探索性的展示的过程是没有按当前的eCPM最大化方法进行广告投放,即探索的展示会让收入下降,那么如何控制探索的量和探索的有效性,使得系统长期的,整体的收入增加,就是探索与利用的核心问题。

如果实践中做过广告系统,对于这一点应该有比较深的感触。因为无论是搜索广告,还是联盟广告,在广告主比较多的情况下,会有相当大的一批广告主是永远没有机会展示的,但我们也没有办法让他们得到一些展示的机会,因为要给他们展示的机会,是要付出相当大的代价的,有必要从算法的角度来讨论探索与利用的问题。Explore就是探索未知世界,Exploit就是利用从未知世界得到的少部分统计量,去提高eCPM统计的准确性。

这个问题在学术界讨论的比较多,它是Reinforcement Learning中的一个具体问题,学术界通常把它描述成为一个Multi-arm Bandit(MAB)问题。这个名字的起源来*laohuji上的扳手,扳哪个Arm赢的概率比较大,在开始的时候是不知道的,所以要用钱去探索,看哪个扳手能提供的收益最高,但试的过程是在损失自己的钱,所以用这个名字很形象地来称这个E&E问题。

Multi-arm Bandit通常描述为:有限个arms(或称收益提供者)a(即上例中,laohuji的扳手是有限的,在广告系统中它就是广告),每个有确定有限的期望收益E(rt,a),在每个时刻t,我们必须从arms中选择一个,最终目标是优化整体收益。MAB最基本的方法学术界称为ε-greedy,它是一个很简单的方法,就是将ε比例的小部分流量用于随机探索。如果提出一种新的E&E算法,当然首先要和这种方法进行比较。

广告问题中有两个主要挑战,但它们不一定能很好地在这个框架下解决。1. 海量的组合空间需要被探索,因为要探索的是(a,u,c)这个组合空间,甚至不能认为是一个有限的空间(不是指数学上的无限),2. 因为在MAB问题中假设了各个arm的期望收益是确定的,但对于广告来讲,每个arm的收益绝对不是确定的,比如在双11促销前的ROI与其它时间的ROI相比,差的就很远了。这两个问题,我自己体会,在工程上需要研究者在以后进一步解决。

E&E算法-UCB

关于E&E算法,我介绍两个基本思路,大家不要把它认为是一篇论文或是一个具体的算法,我介绍的是两个非常有借鉴意义的思路。这个领域大家比较认可的是UCB方法。

UCB方法的思路从直觉上非常合理,它是在时间t,通过以往观测值以及某种概率模型,计算每个arm的期望收益的upper confidence bound(UCB),并选择UCB最大的arm。先不关注这句话中的术语,它其实也是一个bayesian的理念,在估计某个arm收益的时候,不再把它认为是一个确定的数,而是把它认为是一个分布。UCB的意思是在选择的时候,并不是按照期望收益最大的一点去选择,而是按照分布的收益上界去选择。在体会这个策略的过程中,会发现它是一个很聪明的策略,它对每个arm都是选择它最有可能达到的收益点来进行投放,随着时间的推移,随着观察值的增加,分布曲线会越来越窄,最终收敛成一个固定的值。假设一个广告的期望收益并不高,换言之,它的表现可能不是最优的,我们在UCB方法下不会永远出这个广告,因为经过几次探索,它就分布曲线会迅速收敛,当发现有别的广告比它更好的时候,就不会再出这个广告了,但这种方法不会漏掉真正好的广告,因为好的广告在没有观察的时候,它是非常宽的一个函数分布,它的upper confidence是一个很大的值,所以总是有机会选中它,选中之后,分布会迅速收敛到实际的确定的收益。Paper中主要探讨的是具体的UCB策略,比如β-UCB策略,它是证明选择非最优的arms存在着一个上界,该上界与总的选择次数无关。还有一个改进的策略,UCB-tuned,它证明了如果已经选择的次数越多,就越可能自信地抛弃不太有前途(但仍可能最优)的arm。

介绍UCB方法是因为它是一个很符合人直觉的E&E算法,其它也有很多变形的算法,大家可以看一下相关的资料。

上一篇:Python Flask学习知识点(一)


下一篇:Python Flask学习知识点(二)