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可能性衰减在本质上是相似的。看到用于稀疏高维上下文的在线贝叶斯分类器很酷,该分类器试图检测非平稳性并实际上允许估计的方差以数据相关的方式增加(例如,受困惑驱动)。也许一旦展示出窍门,非贝叶斯主义者便会证明使用后代完全相同的更新来最大程度地减少后悔的结果:)开个玩笑。

没意见:

发表评论