2011年12月18日,星期日

负采样:一个简单的例子

我最近读了Agarwal等人的论文。等上 万亿级学习。他们注意到数据集的统一子采样会降低分类器的性能(换言之,它有助于使用所有数据),从而激发了Terascale学习。这让我再次考虑了数据集的非均匀子采样。

我尤其对二进制分类问题中与更普遍的标签相关的数据进行二次采样感兴趣。这不同于典型的主动学习方案:我假设所有数据标签都可用并且可以免费检查,但是由于某些原因,您不想全部处理。也许数据是由分布式传感器网络收集的,您想通过在外围设备中放置数据来最大程度地降低通信成本,或者您有一个大数据集,并且想要生成一个适合笔记本电脑的样本,以便进行实验在旅行时。

我有 凭经验说好运 面对涉及非常不平衡数据的分类问题而偏向负样本时,对负样本进行二次抽样。这种做法很合理 当目标函数是AUC时,因为当数据集具有相同数量的正数和负数时,由于经验AUC与实际AUC之间存在偏差,对于给定的示例预算,该偏差会最小化。但是,尽管经验上我在分类损失和有偏的子采样方面表现不错,但我仍然没有类似的分类结果。因此,我提出了以下激励性的例子。

上下文无关分类

让我首先描述一个上下文无关分类的游戏。
  1. 对手选择$ q $。
  2. 裁判通过重复以下IID直到接受$ n $个样本来生成训练集$ S $:
    1. 选择概率为$ q $的$ y = \ mathrm {heads} $,否则选择$ y = \ mathrm {tails} $。
  3. 玩家检查训练集$ S $,通过均等随机化将$ \ {\ mathrm {heads},\ mathrm {tails \} $打破平局的经验风险降至最低,并报告$ \ hat y(S)$。
  4. 裁判员根据示例收集来自玩家的预期遗憾,定义为\ [
    | 2 q-1 | 1 _ {\ hat y(S)\ neq y ^ *(q)},
    \]其中\ [
    y ^ *(q)= \ begin {cases}
    \ mathrm {heads}& \mathrm{if}\;\; q \ geq \ frac {1} {2} \\
    \ mathrm {tails}和\ mathrm {other}
    \ end {cases}。
    \]换句话说,玩家根据平均平均比最佳常量多多少个预测错误来支付费用。
在训练集中最小化经验风险的策略归结为说出玩家在训练集中看到的头数超过$ n / 2 $的头,如果在训练集中看到少于$ n / 2 $头的头则说的尾巴,以及如果正好在训练集中$ n / 2 $的头部说出正面或反面的可能性相等。 $ n $为奇数时,玩家犯错的机会由\ [
\ mathrm {Pr}(\ hat y \ neq y ^ * | q; n)= \ begin {cases}
\ sum_ {c = 0} ^ {\ lfloor n / 2 \ rfloor} {n \ choose c} q ^ c(1-q)^ {n-c}& \mathrm{if}\;\; q \geq 1/2 \\
\ sum_ {c = \ lfloor n / 2 \ rfloor + 1} ^ n {n \ choose c} q ^ c(1-q)^ {n-c}& \mathrm{if}\;\; q < 1/2
\ end {cases}。
\]当$ n $甚至是偶数时,有一个附加项对应于给定随机值的随机数。玩家犯错的可能性最大为$ q \至1/2 $,但是预期后悔与$ | 2 q-1 | $成正比;因此,对手的最佳选择是选择一个中间$ q $。对于$ n = 21 $,它看起来如下所示:
随着$ n $的增加,对手的最佳比赛向$ q = 1/2 $移动,而对手的游戏价值也随之下降。

重要性加权的上下文自由分类

现在考虑当玩家决定对训练数据中的样本进行二次抽样,然后将重要性加权的经验风险降到最低时会发生什么。需要明确的是,游戏如下:
  1. 玩家选择正面的二次采样率$ w $。
  2. 对手选择$ q $。
  3. 裁判通过重复以下IID直到接受$ n $个样本来生成训练集$ S $:
    1. 选择概率为$ q $的$ y = \ mathrm {heads} $,否则选择$ y = \ mathrm {tails} $。
    2. 如果$ y = \ mathrm {heads} $,则以概率$ w $拒绝样本。
  4. 玩家检查训练集$ S $,通过相等随机性将$ \ {\ mathrm {heads},\ mathrm {tails \} $打破平局的重要性加权经验风险最小化,并报告$ \ hat y(S)$。
  5. 裁判按照示例从玩家那里收集预期的遗憾(如上所述)。

理论建议

二次采样有两个作用。首先是将训练中头部的概率设置为\ [
\ tilde q(q,w)= \ frac {q w} {1-q + q w}。
\]第二个方法是将猜测磁头所需的计数数量从$ n / 2 $更改为$ n w /(1 + w)$。

当$ q> 1/2$ and $0 <w \ leq 1 $,$ \ frac {w} {1 + w}<\ tilde q(q,w)$,因此不正确的概率在上方受 Azuma-Hoeffding不等式 在the $ \ sum(Y_i-\ tilde q(q,w))上$,\ [
\ begin {aligned}
\ mathrm {Pr}(\ hat y \ neq y ^ * | q; w; n)&= \mathrm{Pr} \left(Y <\ frac {n w} {1 + w} \ right)+ \ frac {1} {2} \ mathrm {Pr} \ left(Y = \ frac {n w} {1 + w} \ right)\\
&\ leq \ mathrm {Pr} \ left(Y \ leq \ frac {n w} {1 + w} \ right)\\
&= \ mathrm {Pr} \ left(Y-n \ tilde q(q,w)\ leq n \ left(\ frac {w} {1 + w}-\ tilde q(q,w)\ right)\对) \\
%&\ leq \ exp(\ frac {-n ^ 2 \ left(\ frac {w} {1 + w}-\ tilde q(q,w)\ right)^ 2} {2 n \ max \ {\波浪线q(q,w)^ 2,(1-\波浪线q(q,w))^ 2 \}}))\\
&\ leq \ exp \ left(-\ frac {n} {2 \ max \ {\ tilde q(q,w)^ 2,(1-\ tilde q(q,w))^ 2 \}} \ left (\波浪线q(q,w)-\ frac {w} {1 + w} \ right)^ 2 \ right)\\
&\ doteq \ varphi(q,n,w)。
\ end {aligned}
\]这是关于此绑定的有趣之处:当$ \ tilde q(q,w)= \ frac {1} {2} $时,由于\ [
\ begin {aligned}
\ frac {d} {dw} \ log \ varphi(q,n,w)&= \ begin {cases}
-\ frac {n w} {4(1-3 q + 2 q ^ 2)^ 2(1 + w)^ 3} < 0 & \mathrm{if}\;\; \tilde q (q, w) < \frac{1}{2} \\ \frac{n}{4 (1 - 2 q)^2 q^2 (1 + w)^3} > 0 & \mathrm{if}\;\; \tilde q (q, w) > \frac{1}{2}
\ end {cases}。
\ end {aligned}
\]因此,边界建议对均衡的标签期望值进行二次采样。考虑到熵在 大偏差理论.

请注意,如果对手选择$ q<1/2 $,我们可以重新标记硬币并重复参数(即对另一枚硬币进行二次采样)。但是,由于在游戏中是在对手选择$ q $之前选择了二次采样率,因此玩家应选择$ w = 1 $来使maxmax最优,除非对手被限制为拥有$ q>1/2 $。这个游戏太简单了,无法以这种方式限制对手,而又不会使玩家策略变得微不足道,但是在更丰富的背景下,这种约束是有道理的。

实际发生了什么

不幸的是,界限有些松散,并且在无上下文的游戏中暗示了比精确计算所保证的更具攻击性的子采样。这是当对手玩$ q = 3/4 $时,预期的后悔与$ w $对于$ n = 21 $的关系,
二次采样率是连续的,但实现是离散的,因此遗憾的是离散的跳跃,因为``收支平衡''的点击次数通过整数值(红色= $ \ epsilon $以上=``打破联系而赞成尾巴'';蓝色= $ \ epsilon $以下=``打破领带而赞成头'')。虚线是$ w = 1 $时的遗憾,绿线是界限。确实有一个最佳$ w<1 $,但这可能是由于实现的离散性质,而不是根本原因。现在让我们看一下$ n = 105 $的同一个图形。
现在很明显,有一个最佳的$ w<1 $,而且很明显,界限表明$ w $过于激进。

回到绘图板。

没意见:

发表评论