显示带有标签的帖子 广告投放. 显示所有帖子
显示带有标签的帖子 广告投放. 显示所有帖子

2010年12月21日,星期二

adPredictor:各种想法

我正在读 adPredictor论文 因为我最近在NIPS上看到了一个演讲。它是我所谓的``贝叶斯在线学习''系统家族的一部分,该系统(以贝叶斯学说)保持模型参数的后验分布,而不是点估计。粗略地说,这样做的好处是,某些特定模型参数对更新的敏感性低于非常不确定的模型参数。实际上,这意味着频繁出现的特征对模型更新的敏感性降低。什么时候 信心加权学习 第一次出现时,这很重要,尤其是轶事证据表明,即使使用Zipf分布的名义特征(例如单词指示符变量)也只需要传递一次训练数据即可。从那时起,非贝叶斯方法 每个参数的学习率 已经出现了 vowpal兔子的版本5 通过--adaptive标志实现此功能。根据eHarmony的经验,仅通过使用vowpal的第5版和--adaptive标志对相同的数据进行重新训练,我们看到了多个预测变量的立即改进。

但是,还有另一个方面,与系统部署的上下文强盗性质有关。引用adPredictor论文
第二个问题是勘探与开发之间的权衡。为了能够估算新广告的点击率,有必要向用户展示广告并观察他们的点击/非点击响应。同时,根据已知的情况向用户展示高点击率广告符合每个参与者的利益。探索问题可以通过利用adPredictor保持权重不确定以及任何特定广告印象的CTR保持不确定的事实来解决。当使用(2)评估预测时,系统可以从后验权重分布中采样,而不必总是将预期的点击率提供给广告拍卖,这一思想可以追溯到汤普森(Thompson,1933)。这样做的效果是使广告的点击率上升,系统的不确定性仍然很高。
这不能完全解释正在做的事情,但是也许期望具有如此商业重要性的系统的精确细节有些不切实际。他们正在做什么的一种解释是,他们从模型的后验分布中获取一个样本,然后像对待实际模型一样对待它们,使用该样本模型对所有备选方案进行评分,然后对这些评分进行贪婪的行动。我不确定该策略是否有理论上的保证,或者它是否具有启发性。凭直觉,它应该在估计值与估计值的不确定性相比具有较小估计值差异的替代方案之间分配勘探。

当我考虑必须从一堆历史数据中学习针对背景强盗问题的策略时,我希望历史探索策略的显式状态-动作密度$ \ pi(a | x)$是可用的,因此我可以重视权衡数据。如果没有的话 你可以估计一下,但如果我是从头开始设计系统,则将尝试使其显式计算$ \ pi(a | x)$并将结果记录在历史记录中。因此,有没有一种方法可以利用后验来指导勘探,同时拥有明确的$ \ pi(a | x)$?

看似简单的想法不会导致显式的$ \ pi(a | x)$。例如,考虑到每个臂$ k $用已知的累积分布函数$ F_k(\ cdot)$独立分布,并采取联合独立实现的最大值似乎是合理的,但会导致表达式[[
P(Y_i = \ max_ {k \ in K} Y_k)= \ prod_ {k \ neq i} P(Y_k<Y_i)= \ int d F_i(y)\ prod_ {k \ neq i} F_k(y)。
\]通常很难解析。如果我对adPredictor系统的工作方式是正确的,那么情况就更加复杂了,因为这些支路不是独立分布的(模型参数是采样的,并且不同的支路具有不同的重叠模型参数集,这些参数有助于它们的估算) )。

所以我怀疑adPredictor家伙在``估计历史国家行为''密度区域中。没关系,广告投放由于业务规则和外部波动而变得非常复杂,以至于``精确的''$ \ pi(a | x)$实际上可能不如估计的准确。但这仍然表明要么需要在线估计$ \ pi(a | x)$,要么需要离线进行学习。鉴于探索是通过对模型后验进行采样来进行的,因此后者似乎很危险(您将需要更新模型后验,以避免过度探索)。

关于adPredictor的另一个有趣之处:它是分类器,而不是重要性加权分类器。当然,后者可以简化为前者 成本核算,但是重要性权重为$ 1 / pi(a | x)$,这可能会变得很大,导致拒绝采样会丢弃大部分训练数据。为了避免丢弃过多的数据,可能需要$ 1 / \ max \ {\ pi(a | x),\ tau \} $裁剪技巧。但是,根据我的直觉,如果您知道$ \ pi(a | x)$,而不是进行估计,则您确实不想削减重要性权重;最好有一个重要度加权分类器,该分类器可以处理广泛的重要度动态范围。并非巧合的是,vowpal wabbit的版本5能够以封闭形式模拟具有重要重要性的单个实例与具有重要重要性的多个实例之间的等效性。 adPredictor更新可能有类似的技巧。

通过随着时间的推移衰减似然项来处理非平稳性的adPredictor策略似乎比较干净。像CW一样,在线贝叶斯Probit的属性是,随着每次观察,(均值)估计方差总是在减小,因此它最终会停顿下来(就像在vowpal中实施的Adagrad一样)。这在固定环境中是适当的,但在非固定环境中,常见的破解方法是在移动的最近数据窗口上进行训练,并且adPredictor可能性衰减在本质上是相似的。看到用于稀疏高维上下文的在线贝叶斯分类器很酷,该分类器试图检测非平稳性并实际上允许估计的方差以数据相关的方式增加(例如,受困惑驱动)。也许一旦展示出窍门,非贝叶斯主义者便会证明使用后代完全相同的更新来最大程度地减少后悔的结果:)开个玩笑。

2010年11月22日,星期一

Minimax受约束的CSMC:进展不大

在一个 以前的帖子 我谈到了广告投放,以及为什么基于回归的方法仍然占主导地位,即使其他针对成本敏感的多类分类(CSMC)的方法具有较低的遗憾界限。我认为,这归结为实际问题,而广告投放中的一个重要的实际问题是,给定决策实例(广告投放请求)所允许的一组操作(广告)可能是易变的。此外,在许多情况下,例如,由于广告商尝试预算,没有理由相信训练集和测试集之间的约束模式在统计上是稳定的。因此,我认为最好以对抗性方式建模约束,这种情况称为minimax约束CSMC。

我将对minimax受约束的CSMC重复设置。有一个分布$ D = D_x \ times D _ {\ tilde c | x} $,其中$ \ tilde c:K \ to \ mathbb {R} $的取值以正实数$ \ mathbb {R} $为单位。然后,一个对手进入,并通过将某些成分设置为$ \ infty $,在扩展实数$ \ mathbf {R} $中制造成本向量$ c $;在做出决定之前,这些选择会通过$ \ omega $显示出来。在这种情况下,特定分类器$ h的遗憾:X \ times \ mathcal {P}(K)\ to K $由\ [\ nu(h)= E_ {x \ sim D_x} \ left [\ max_ {\ omega \ in \ mathcal {P}(K)} \ left \ {E _ {\ tilde c \ sim D _ {\ tilde c | x}} \ left [c(h(x,\ omega))\ right] -\ min_ {k \ in K} \; E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c(k)\ right] \ right \} \ right]。 \]与平均受约束的CSMC相反,后者的约束分布($ \ omega $)从训练到测试数据都是稳定的。对于受约束的普通CSMC,基于树的减少量在经过修改以禁止其选择放弃其锦标赛时起作用。但是,这对于minimax约束的CSMC不起作用,如下面的简单反例所示。假设$ X = \ emptyset $,$ K = \ {1、2、3 \} $和$ \ tilde c $是确定性的,使得$ \ tilde c(1) < \tilde c (3) < \tilde c (2)$, and suppose the tree first pairs $\{1, 2\}$ while giving 3 a pass, and then pairs $\{1, 3\}$. Suppose the classifier used 在 each tree node is $1_{f (a) > f(b)} $用于某些函数$ f:K \ to \ mathbb {R} $。如果仅使用$ \ omega = \ emptyset $的数据进行训练,则在$ f(1)= 1 $,$ f(3)= 3 $和$ f的情况下,对训练数据的后悔可以归零。 (2)= 2 $。但是,当$ \ omega = \ {1 \} $在测试时会感到遗憾。

这里发生了什么?这种情况类似于分类的降级,其中$ f $引起元素的线性排序。在那种情况下,在输入对上平均的分类误差为在输入集上平均的AUC误差提供了界限。当然,AUC对于目标函数而言过于粗糙,因为它仅对排序误差敏感,而对幅度不敏感。但是,这的确表明除了在过滤树的一次通过期间进行的$(| K |-1)$比较之外,还需要在训练期间比较更多对元素。如果必须在训练期间比较每对,则可能需要$ | K | / 2 $通过过滤树。

因此,请考虑在[1,| K |] $中由$ n \索引的平均约束CSMC分类器$ \ Psi_n $的序列。这些会诱发一个序列$ \ {\ tilde \ omega_n | n \ in [0,| K |] \} $通过\ [
\ begin {aligned}
\ tilde \ omega_0&= \ emptyset,\\
\ tilde \ omega_n&= \ tilde \ omega_ {n-1} \ cup \ {\ Psi_n(x,\ tilde \ omega_ {n-1})\}。
\ end {aligned}
\]本质上,这是一系列平均约束CSMC分类器,它们确定最佳动作,次佳动作等(以与减少 成本敏感的最佳m到成本敏感的多类)。接下来考虑索引\ [
\ eta(x,\ omega)= \ min \ {n \ in [1,| K |] | \ Psi_n(x,\ tilde \ omega_ {n-1})\ not \ in \ omega \}。 \]如果$ \ omega \ neq K $,则此索引始终存在。当$ \ omega \ neq K $通过\ [h(x,\ omega)= \ Psi _ {\ eta(x,\ omega)}(x,\ tilde \ omega _ {\ eta(x, \ omega)-1})。
\](当$ \ omega = K $时,无论分类器做出何种选择,遗憾总是为零,因此我将忽略这种情况)。特定$(x,\ omega)$的遗憾由\ [
\ begin {aligned}
\ nu(x,\ omega)&= E_{\tilde c \sim D_{\tilde c|x}} \left[ c (h (x, \omega)) \right] - \min_{k \in K}\;E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c(k)\ right] \\
&= E _ {\波浪线c \ sim D _ {\波浪线c | x}} \ left [c(h(x,\ omega))\ right]-\ min_ {k \ in K \ setminus \ tilde \ omega _ {\ eta(x,\ omega)-1}} E _ {\波浪线c \ sim D _ {\波浪线c | x}} \ left [c(k)\ right] \\
&= E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c \ left(\ Psi _ {\ eta(x,\ omega)}(x,\ tilde \ omega _ {\ eta(x, \ omega)-1})\ right)\ right]-\ min_ {k \ in K \ setminus \ tilde \ omega _ {\ eta(x,\ omega)-1}}} E _ {\ tilde c \ sim D _ {\代字号c | x}} \ left [c(k)\ right],\\
\ end {aligned}
\],其中第二行从$ \ tilde \ omega _ {\ eta(x,\ omega)-1} \ subseteq \ omega $开始,第三行从$ h $的定义开始。现在,最后一行是针对每个实例的$ \ eta(x,\ omega)^ {\ textrm {th}} $平均受约束CSMC分类器的遗憾,该CSMC分类器是根据第一个$(\ eta(x,\ omega)-1)$个分类器。因此\ [
\ max _ {\ omega \ in \ mathcal {P}(K)} \ nu(x,\ omega)= \ max_n \ left \ {E _ {\ tilde c \ sim D _ {\ tilde c | x}} \ left [ c(\ Psi_n(x,\ tilde \ omega_n))\ right]-\ min_ {k \ in K \ setminus \ tilde \ omega_ {n-1}} E _ {\ tilde c \ sim D _ {\ tilde c | x }} \ left [c(k)\ right] \ right \}。
\]这建议一个过程,其中每个实例完成$ | K | $个没用的过滤树通过;虽然这似乎是2的太多,但注意没收不会生成分类实例,从而消除了一半的比较。 minimax限制了CSMC的遗憾是“ [
\ nu(h)\ leq(| K |-1)E_ {x \ sim D_x} \ left [\ max_n \; q_n(x,\ tilde \ omega_ {n-1})\ right]
\]其中$ q_n(x,\ tilde \ omega_ {n-1})$是在分配诱导下训练的$ n ^ {\ textrm {th}} $没收过滤树的平均每节点重要性加权后悔被第一个$(n-1)$没收的过滤树。

乍一看,这看起来实在太笨拙,无法在实践中使用,但是有两种修改可能使其实用。第一种是为每个$ \ Psi_n $重用同一棵树,而不是将$ n $个树分开。尽管正确的训练程序对我来说不是立即显而易见的,但遗憾的束缚依然存在。第二种是考虑约束数量(即$ | \ omega |)有界的情况。 \ leq z \ ll | K | $,这样培训和测试成本仅增加$ z $。实际上,这似乎是合理的。

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的查询内和查询间约束。