2010年10月26日,星期二

为什么广告服务器使用回归?

帖子标题有点冒昧,因为1)我不知道所有广告服务器都使用回归,以及2)即使它们做到了,也很难推测原因。所以这确实是,``过去为什么要在广告投放中使用回归?''但这并不那么吸引人。

为什么还要问这个问题?因为广告投放看起来像是对成本敏感的多类分类,而将对成本敏感的多类分类减少到回归会导致遗憾的界限,而后悔的界限要比减少成二进制的分类更为糟糕。

因此,这里列出了我过去遇到的问题,回归减少如何处理以及二进制分类的减少如何处理这些问题。

一整套行动正在发生变化

首先,让我说,即使在一组动作并没有真正迅速改变的情况下,我也使用了回归。例如,我参与了一个域货币化产品,其中的操作是一个出价关键字短语列表(通过驱动到搜索引擎结果页面来货币化)。这样的列表很少(例如每月)更改并且适度(每单位时间制作的``Lady Gaga''数量不多)。真的,我在那里没有任何借口。

如果这组操作确实确实会随着时间发生显着变化(例如,以赞助商搜索广告为背景的目标定位,其中新广告频繁出现),则很容易想到,接受过先前数据训练的回归器会合理地推广到一个新实例,毕竟,新实例将与现有实例(例如单词和单词短语)共享许多功能,并在相似的上下文(例如网页)中显示。这很诱人,但很危险。我学到了一种艰难的方式,即必须谨慎对待从勘探到开发流量的操作。 (``学习艰难的方式''是对``我建立了行不通的东西''的很好委婉说法)。尽管如此,即使承认从勘探政策过渡到开采政策所需的谨慎,也可以说回归使``混合新行动''变得容易。

鉴于从勘探到开采的过渡是受控过程,它如何在简化为二分类的过程中起作用?这些减少中的一些被组织为以二叉树形式组织的锦标赛。考虑添加一个动作。在这种情况下,可以创建一个新的根节点,其子节点是旧的根节点和新的动作。这个新的根节点本质上必须学习:``在什么情况下我应该采取新的行动,而不是在不采取新行动时做我之前会做的事?''以这种方式构建树会导致非常不平衡的树。由于可以在新的根节点下缝合整棵树,因此一次扫描中添加许多动作将稍微缓解该问题,但是除非动作数量加倍,否则仍将导致缺乏平衡。但是,使用$ | A_ {new} |作为增量操作可能是一个不错的选择。 + 1 $个新颖的二进制分类子问题,可训练包含$ \ log_2(| A_ {new} |)$个连续步骤的子问题。

另一种策略是在叶级添加新操作(或删除旧操作)。将现有叶子转换为内部子节点,并将子节点作为新动作,而在前一个叶子上的动作将需要$ 1 + \ log_2(| A_ {old} |)$新的二进制分类子问题来进行训练,因为到根的整个路径必须重新学习。保守地,如果对一组新动作执行此操作,则重新训练的总数将按$ | A_ {new} | $进行缩放,但是实际上,如果替换项在树中彼此靠近,则将共享许多到根的路径。我怀疑实际费用约为$ | A_ {new} | + \ log_2(| A_ {old} | / | A_ {new} |)$,即$ | A_ {new} | $分类符的完整树,加上一条长度为$ \ log_2(| A_ {old}的共享路径| / | A_ {new} |)$到根。我还怀疑可以在$ \ log_2(| A_ {old} |)$连续步骤中完成这些重新训练。

在某些情况下,简单地考虑对整个树进行重新训练并不是没有道理的。每个级别都可以并行训练,因此连续步骤的数量为$ \ log_2(| A |)$,再训练的总数为$ | A | $。考虑到非平稳性,功能创新等,无论如何都必须定期进行全面的重新培训。

查询内约束

这类似于一组动作的变化,但是上一节是关于如何改变可能的动作的范围,而本节是关于在单个实例上如何不允许某些动作。

两种不同的情况 我已经确定第一种,我称为``平均约束CSMC'',涉及到的约束变化非常缓慢(如果有的话),因此可以使用训练和测试数据绘制的IID将它们建模为问题实例的一部分。这些是``不允许在带有色情内容的网页上刊登此广告''之类的事情,在广告的生命周期内几乎永远都不会发生变化(可能由于广告活动说明错误而在一开始)。

第二种,我称为``极小约束CSMC'',涉及快速变化的约束,因此训练集上约束的分布与测试集上约束的分布无关。这些就像``这位广告客户用尽了预算''之类的东西一样,因为广告客户尝试预算的方式可能非常不稳定。这里的约束是对抗性建模的,需要一种解决方案才能对所有可能的约束设置都感到遗憾。

一个有趣的结果是argmax回归减少具有 同样的遗憾 适用于无约束,平均约束和极小约束的CSMC。这可以通过对该实例允许的一组操作上的回归得分简单地使用argmax来实现。

在一般受限的情况下,可以修改基于树的缩减量,以使不允许的动作丧失其锦标赛资格,并且 类似的遗憾 可以得出无约束的情况。对于基于树的约简的minimax约束案例,我没有任何结果,尽管我有一个小的问题示例,表明仅放弃一项并不能取得良好的结果。

我强烈怀疑必须充分了解minimax约束的CSMC,才能将回归从广告中淘汰。

查询间约束

这是指需要在一组查询中强制执行的属性。预算约束就是一个典型的例子,其中贪婪的交付具有最坏情况的竞争比率\\ frac {1} {2} $。再次,没有理由(除了缺乏知识),即使在没有查询间约束的情况下,我也使用了回归:一种用于上下文定位eBay联盟广告的系统。会员计划仅在获得付款时才向您付款,因此从本质上讲它们有无限的预算。

但是,通常必须解决这些限制。 要么 数十年来一直在处理此类约束,并且OR普遍减少到回归。如果预算以美元指定,并且回归估计声称是预期收入,则可以使用网络流算法来攻击某些预算受限的广告投放问题。这样的算法足够快,可以在实际流量流入时定期重新运行,以克服流量估算中不可避免的大误差。 (随着CPU和内存的价格降低,可以利用此方法的广告网络的规模会随之增加)。

通过使用诸如动态编程的策略学习之类的方法将广告投放减少到对成本敏感的多类分类中,似乎有可能在这种情况下拒绝回归。对于某些人来说,这可能是一个不错的博士学位论文(有点实用,所以也许没有什么生气)。在此期间,我会坚持下去:我已经提高了 我对随机最短路径的直觉 并最终希望减少流向CSMC的流量。

我还想知道在预算约束条件下进行优化的近似在线方法是否也适用于其他CSMC降低,这些方法涉及在调整后的回归估算中使用argmax。例如与 梅塔(Mehta)等的 $ \ psi(x)= 1-e ^ {x-1} $剩余预算折现函数,可以使用剩余预算折现的观察报酬而不是实际的观察报酬训练基于树的减少量。这是否有意义还需要进一步思考:我对此类算法的分析的理解是,他们认为回归是完美的,而性能限制是由于查询序列的在线性质所致。有趣的是,在回归分析中增加了其他表示遗憾的术语,这样可以说基于树的方法可以做得更好。

选择一套

华润上华减少是从一组操作中选择一个操作,但是在投放广告时,通常会一次选择多个广告。但是,并非总是如此:展示广告通常是单个广告展示,并且移动屏幕的空间可能很稀缺。对于赞助搜索(或赞助搜索广告的上下文广告投放),填充多个职位是常态。

如果与集合相关的奖励是各个动作奖励的总和,则回归将很自然地处理集合选择:仅通过估计值选择前$ m $个动作,而不是第一个。的 后悔 几乎与单一操作情况相同,只是有一个额外的$ \ sqrt {\ min \ {m,| A | -m \}} $。保留了对回归者后悔的(不希望的)平方根依赖性。幸运的是,这个问题也可以 减少到平均受限CSMC。基本策略是“选择最佳操作,然后选择下一个最佳操作,等等。”后悔有一个额外的因素,即$ m $(更糟),但保留了对CSMC后悔的线性依赖关系(更好)。

但是,对于广告投放而言,实践中通常认为线性奖励的假设过于强烈,因为通常会产生重大的排名影响。幸运的是,如果奖励依赖于位置 交换至上和维持相对秩序 (如独立于单调动作的乘法位置调制所暗示),则 相似的技术 当与集合相关联的奖励是通过减少到平均约束CSMC来获得单个动作位置奖励的总和时,可以用于解决选择最佳动作的问题。

如果一组动作的报酬不是单个动作报酬的总和,则一种选择是将整个组视为动作。在广告投放中,这通常是不可行的,但在内容优化(例如,自适应用户界面)中,这是可行的。如果动作之间的外部性仅按位置排列(例如,垂直显示中的串行扫描模型),则直观上感觉像是随机的最短路径问题,但我尚未对此进行验证。

在我工作过的每台广告服务器中,都将一组动作的奖励假定为与单个动作奖励呈线性关系,并且可能会进行位置校正。因此,仅仅因为问题涉及选择集合,使用回归实际上就没有任何借口。

概要

总体而言,我认为阻止从广告投放中淘汰回归的两个主要问题是:1)对抗性强加的查询内约束和2)查询间约束。任何不具有这些属性的广告投放问题都应该是扣篮,以进一步降低CSMC的数量。例如,任何通过搜索引擎目标网页获利的广告投放问题(例如,动作是出价的短语)都不会表现出这些属性;元货币化问题(例如,在多个广告网络之间动态选择)也没有。

我将在业余时间讨论CSMC的查询内和查询间约束。

2条评论:

  1. I'对于ML的学习减少和广告服务器应用而言,这是相当新的。就是说,我 '最近,我一直在研究强盗算法,并着眼于它们在广告投放中的应用(实际上是内容优化)。为什么不'您考虑使用强盗算法吗?似乎他们比分类更好地模拟了真实情况(反馈有限)。

    回复删除
  2. 嘿,诺埃尔。

    偏移树是针对上下文强盗问题的离线策略构造函数(处理"warm start"问题),也可以在线进行更新。实际上,它与探索策略结合在一起,在这里我根本不会讨论。

    所以这里的讨论大概是关于:我'我已经以某种方式对新广告进行了一些探索,并决定将其纳入我的开发策略中(即,我希望离线策略构建者与现在包括此新操作的更大类别的策略竞争)。我可以向偏移树增量添加操作,还是需要从头开始完全训练?由于如果不更改一组动作就可以增量地维护偏移量树,因此在引入或删除新动作的(常见)事件中必须完全重新训练似乎很浪费。

    回复删除