2010年12月16日,星期四

进一步抽样零奖励示例

关于对零奖励示例进行二次抽样,我遇到了一些很好的问题,我认为他们的回答将成为一篇不错的博客文章。

为什么这样做?

我知道我毕竟在逆势而上,``没有像其他数据一样的数据。''如果您可以轻松地处理所有数据,则请务必使用所有数据。 NIPS研讨会 在核心,集群和云上学习 都是关于扩大机器学习的。仍然在实践中,我认为即使有这样的并行性,在许多情况下也无法处理所有数据,在这种情况下,如果您知道数据非常不均衡,则有偏的子采样比统一的子采样要好。以下是一些方案:
  1. 在移动应用程序中,可能必须在本地处理数据(使用宝贵的功率)或传输数据进行集中处理(使用宝贵的带宽)之间进行选择。二次采样可以使任一选择的成本降低。
  2. 在在线学习应用程序(不是应用于离线数据集的在线学习算法,而是实际在线应用)中,当输入数据流超过学习者的吞吐量时,需要一种流量控制策略。
    1. 在具有反馈循环(例如广告)的在线学习中,我对未来最复杂的系统将如何控制回报流的猜测是主动学习。但是,有偏差的二次采样现在很容易实现:)
  3. 在进行实验时,即使可以忍受最终产品的学习延迟,人机学习专家也不希望在尝试时有很多学习延迟。在固定示例预算的情况下,有偏次抽样优于均匀抽样在保持经验风险与实际风险之间的严格界限上更好(也许:请参见下文)。我在研究生院的导师告诉我,HMM总是在语音识别中发挥神经网络的作用,这不是因为HMM本质上更好,而是因为它们可以更快地被训练,所以在实践中人们可以尝试更多的事情。 (糟糕,现在我听起来很古老)。
二次采样增益往往与并行化增益结合在一起,即,如果并行化得到两个数量级,二次采样得到两个数量级,那么一起得到四个数量级。

它行得通吗?

我有一些经验轶事。

在eHarmony,我们完成了以下实验序列,事后看来是合理而科学的。实际发生的情况是,这里的每个阶段都代表了模型构建的另一个实例,并且由于不耐烦的人们,我们一直想知道如何比上次更快地做事。但是,我们害怕搞砸了(代码甚至超过了数学),因此我们在每个阶段都对控件进行了仔细检查。
  • [阶段0]:我们如何开始:分类任务(实际上是对二进制变量的密度估计)。
    • 用于训练,校准和验证的非子采样数据。
  • [阶段1]:婴儿要解决分类问题。
    • 用于训练的二次抽样数据与用于训练的非二次抽样数据。
    • 非二次采样数据,用于校准和验证。
    • 指出,对样本外数据进行训练不会影响样本外的概括(验证)(从统计意义上来说)。
  • [阶段2]:赢得对分类问题的信心。
    • 二次采样数据进行训练。
    • 用于校准的二次采样数据与用于校准的非二次采样数据。
    • 非子采样数据进行验证。
    • 指出,对样本外数据进行训练不会影响样本外的概括(验证)(从统计意义上来说)。
  • [阶段3]:希望尽快解决分类问题。
    • 用于训练和校准的二次采样数据。
    • 用于验证的二次抽样数据与用于验证的非二次抽样数据。
    • 注意,两种验证技术都可以得出统计上相同的泛化误差估计。
  • [阶段4]:希望尽快解决回归问题。
    • 次要重新考虑了所有子样本机制,以便将其应用于回归,而不仅仅是分类。
    • 感到我们的厌倦之处:只需尝试像分类一样在任何地方进行子采样数据。
    • 喜欢结果,宣布胜利。
最终结果是,如今,我们在模型构建的所有阶段都专门处理子采样数据。

不幸的是,我从未尝试过的一件事是将统一采样与有偏向子采样进行比较,即确定示例总数。以上所有实验均未将二次采样与偏向二次采样进行比较,即保留了正向奖励示例的数量,并尝试使用了较少的零奖励示例。此外,上述所有实验都提出了一个问题``子采样的结果是否同样好''。相比之下,将统一采样数与有偏子采样与固定数量的总样本进行比较可能会问到``子采样的结果更好吗? ''

它应该工作吗?

通常,我考虑使用固定的示例预算,然后优化经验风险与实际风险之间的偏差范围。

我在一个 以前的帖子 对于AUC损失,对于给定的示例预算,当数据集的正负数相等时,经验AUC与实际AUC的偏差范围将最小化。因此,对AUC丢失问题进行二次采样是非常合理的。

对于更一般的损失,例如对应于回归或分类 以前的帖子 我讨论了 科尔特斯(Cortes)等。等 专门用于对高度偏差的集合进行二次采样的情况,\ [
R(h)\ leq \ widehat R_w(h)+ \ frac {2(\ log | H | + \ log \ frac {1} {\ delta})} {3 m} \ frac {p_0} {\ beta} + \ sqrt {\ frac {2(\ log | H | + \ log \ frac {1} {\ delta})} {m} \ left(1-\ frac {(\ beta-p_0)^ 2} {\ beta(1-\ beta)} \ right)}。
\]这里$ p_0 $是原始分布中零奖励示例的分数,$ \ beta $是二次抽样分布中零奖励示例的分数。相对于$ \ beta $(对于较小的$ m $和$ p_0 \至1 $),最小化此约束会产生\ [
\ beta ^ * = \ frac {4 \ Psi} {8 \ Psi-9 m} + O(p_0-1),
\]其中\ [
\ Psi = 2 \ left(\ log | H | + \ log \ frac {1} {\ delta} \ right)。
\]因此,对于$ m \ ll \ Psi $,建议以大致相等的比例进行二次采样是最佳选择。但是$ m \ ll \ Psi $是无趣的,因为它暗示边界是松散的。对于大$ m $,通过\ [
\ beta ^ * = p_0 + O \ left(\ frac {1} {\ sqrt {m}} \ right),
\]建议不要进行二次采样(或统一二次采样)。嘿,那不是我想要的结果...我需要一个更好的界限:)

也许正确的答案是一个时间表,在该时间表中,首先对零奖励示例进行积极的子采样,然后随着示例采样中的流变得不那么积极,直到最终使用原始分布(并且在整个过程中,重要性加权与重要性一起使用-二次抽样的权重趋于统一)。

总体而言,当前对回归或分类问题进行二次抽样的理论案例比对二次抽样AUC损失问题的理论案例更具吸引力。我能说什么我一直都这样做,并且对结果感到满意。 YMMV。

猜猜食谱有多敏感?

在里面 以前的帖子 我基于对真实零奖励概率$ \ hat p_0 $的猜测给出了一个简单的方法。此猜测确定零奖励二次采样率$ l =(1-\ hat p_0)/ \ hat p_0 $,以及重要性权重$ w(x,0)= 2 \ hat p_0 $和$ w(x, y \ neq 0)= 2(1-\ hat p_0)$。猜测会有些偏离,但是,这些值仍然有效吗?

由于采样因子($ l $)是一个自由参数,因此无法使其``错误'',但是重要性权重取决于$ p_0 $和$ l $,因此可能不正确。如果真正的零奖励概率是$ p_0 $,则\ [
\ begin {aligned}
w(x,0)&= 2 \ hat p_0 + \ frac {1-2 -hat p_0} {1-\ hat p_0}(p_0-\ hat p_0),\\
w(x,y \ neq 0)&= 2(1-\ hat p_0)+ \ frac {1-2 -hat p_0} {\ hat p_0}(p_0-\ hat p_0)。
\ end {aligned}
\]后一行表示健壮性,但前一行是一个问题,因为当$ \ hat p_0 \到1 $时,零奖励重要性权重对$ \ hat p_0 $和$ p_0 $之间的差异越来越敏感。本质上发生的是,如果$ p_0 = 1 $,则正确的重要性权重为1,但是在该无意义的限制中,每个零奖励示例都被拒绝,并且没有观察到数据。从那个极端退后,因为$ p_0 \ 1 $低估了真实的零回报率,将导致超过1/2的子采样示例为零回报,这意味着$ w(x,0)$太大,并略微高估了真实的零奖励率将导致少于1/2的二次抽样示例为零奖励,这意味着$ w(x,0)$太小。

但是,通过正确的$ w(x,0)$下界为1而估计值上界为2的事实,可以缓解整个情况。因此,当使用SGD优化方法时,这等效于调整学习速率最多2倍(因为比率$ w(x,y \ neq 0)/ w(x,0)= l $是正确的)。这与使用(不正确!)权重$ \ tilde w(x,0)= l ^ {-1} $,$ \ tilde w(x,1)= 1 $形成鲜明对比,当与SGD耦合时,权重等于缩放学习率的差异因素。

因此总的来说,当使用SGD作为优化策略时,我对使用配方加速在线学习感到非常满意。另一方面,如果将非基于SGD的在线算法应用于离线数据堆,则最好将配方权重作为未归一化的权重开始,然后对权重进行归一化,如 科尔特斯(Cortes)等。等 第6节。如果在线使用基于非SGD的在线算法,我不确定该怎么做,但是也许可以使用类似于权重归一化的在线方案,例如,对最近(未采样)历史进行归一化。

知情子采样又如何呢?

在食谱中,我谈到了完全基于忽略上下文($ x $)的奖励($ y $)进行子采样。还要看$ x $呢?我认为这是个好主意,尤其是在输入空间存在明显的分割而大大影响奖励分配的情况下。在eHarmony,我们按客户类型(新用户,付费客户,以前的付费客户等)进行细分。这些客户类型很少,每个客户在历史数据中都有很多支持,并且对于我们想要建模的所有事物,它们的基准费率都非常不同。因此,在这种情况下,我们会根据客户类型来猜测$ \ hat p_0(x)$,其重要性权重和采样率由每个常量$ \ hat p_0(x)$区域中的配方值给出。完成此操作后,我最终会为每种客户类型构建完全不同的模型,但这是因为我使用的是vowpal wabbit,并且希望隐式地与其他类型交互客户类型。我认为即使将数据全部馈给一个学习者,这种方法也应该仍然有效,但是我从未尝试过完全公开。

在知道$ p_0(x)= E_P [1_ {y = 1} | x] $,二次采样将产生学习分布$ Q $,使得在每个点上零和非零奖励标签均等价。的 科尔特斯(Cortes)等。等 bound并不表示这是有利的($ d_2(P || Q)$项可能会增加,而另一个项不会得到改善)。但是,这也没有表明仅基于$ y $的有偏子采样还是有利的,除了较小的$ m $。因此,我再次凭经验看到了这项工作,但是对于YMMV,我没有很好的理论解释。

没意见:

发表评论