2011年12月20日,星期二

负采样:一些进展

在我的 以前的帖子 我用数字方法研究了无上下文分类游戏,并指出对更普遍的类标签进行二次采样是有利的。我试图使用 Azuma-Hoeffding不等式,但得出的结果表明建议对期望的均衡标签频率进行二次抽样,这在经验上过于激进。

幸好 贝内特不等式 也适用;在零均值变量$ \ left(\ tilde q(q,w)-Y_i \ right)$上,它给出\ [
\ begin {aligned}
\ mathrm {Pr} \ left(\ sum_i Y_i<\ frac {n w} {1 + w} \ right)&=
\ mathrm {Pr} \ left(n \ tilde q(q,w)-\ sum_i Y_i>n \ left(\ tilde q(q,w)-\ frac {w} {1 + w} \ right)\ right)\\
&\ leq \ exp \ left(-\ frac {n \ sigma ^ 2} {a ^ 2} h \ Bigl(\ frac {a t} {\ sigma ^ 2} \ Bigr)\ right),\\
\ sigma ^ 2&= E [\ left(\ tilde q(q,w)-Y_i \ right)^ 2] = \ tilde q(q,w)(1-\ tilde q(q,w)),\ \
a&= \ max \ {\ tilde q(q,w),1-\ tilde q(q,w)\},\\
t&= \ tilde q(q,w)-\ frac {w} {1 + w},\\
h(u)&=(1 + u)\ log(1 + u)-u。 \\
\ end {aligned}
\]该界限在捕获作为$ w $函数的后悔结构方面做得更好。
在这里,红色和蓝色点是整数截止边界上下的实际遗憾,绿色是Azuma-Hoeffding边界,橙色是Bennett边界。垂直虚线是每个边界的最小值。尽管Azuma过于激进,但Bennett过于保守,但做得更好。在给定$ p $的情况下,两个边界都预测了一个最佳$ w $,它独立于$ n $;这是它们与各种$ p $的精确计算相比的方式。 (确切的计算取决于$ n $,但是收敛为$ n \ to \ infty $; $ n = 105 $似乎接近此限制。)

概括

贝内特的不等式对更普遍的问题有何看法?假设在$ X乘以Y $的分布$ D $和一个假设$ h:X \ to Y $,我们正在根据0-1损失进行评估。实际风险为\ [
l(h)= E _ {(x,y)\ sim D} [1_ {h(x)\ neq y}]。
\]现在假设我们从$ \ tilde D_w $绘制训练数据,定义为
  1. 从$ D $中提取$(x,y)$。
  2. 如果$ y = 1 $,则以概率$(1- w)$拒绝$(x,y)$。
  3. 否则,接受$(x,y)$。
换句话说,对正样本进行二次采样。给定从$ \ tilde D_w ^ n $中抽取的样本$ S $,重要性加权经验风险为\ [
\ begin {aligned}
\ hat L(w,h)&= \ frac {1} {| S |} \ sum _ {(x,y)\ in S} \ frac {D(x,y)} {\波浪线D(x,y )} 1_ {h(x)\ neq y} \\
&= \frac{1}{|S|} \sum_{(x, y) \in S} \lambda (y;w,q)1_ {h(x)\ neq y},\\
\ lambda(y; w,q)&= \ begin {cases}
w ^ {-1}(1- q(1- w))& \mathrm{if}\;\; y = 1 \\
1-q(1-w)& \mathrm{if}\;\; y = 0
\ end {cases},
\ end {aligned}
\]其中$ q = E _ {(x,y)\ sim D} [1_ {y = 1}] $。 $ \ hat L(w,h)$是所有$ 0的$ l(h)$的无偏估计量<w \ leq 1 $。很高兴证明当$ w时发生``最佳估计''$ \ hat L(w,h)$< 1$ if $q >1/2 $。注意$ \ hat L(1,h)$只是$ D ^ n $样本中未加权的经验风险。

\ i ^ \ mathrm {th} $样本的瞬时损失由\ [
\ begin {aligned}
L_i(w,h)&= \lambda (Y_i;w,q)1_ {h(X_i)\ neq Y_i},\\
&= \ begin {cases}
0 & \mathrm{with\;可能性}\;\; \ tilde q(q,w)r_1 +(1-\ tilde q(q,w))r_0 \\
\ lambda(0; w,q)& \mathrm{with\;可能性}\;\; (1-\波浪线q(q,w))(1-r_0)\\
\ lambda(1; w,q)& \mathrm{with\;可能性}\;\; \ tilde q(q,w)(1-r_1)
\ end {cases},\\
\ tilde q(q,w)&= \ frac {q w} {q w +1-q},
\ end {aligned}
\]其中$ r_z = E _ {(x,y)\ sim D} [1_ {h(x)= z} | y = z] $。 (注意$ r_z $不受子采样的影响。)序列$ \ sum_i \ left(L_i(w,h)-l(h)\ right)$是a,因此Azuma-Hoeffding不等式成立。但是,Azuma-Hoeffding是由相邻序列成员之间的最大可能偏差驱动的,当$ w = 1 $时偏差最小,因此它并不表示二次采样有帮助。但是Bennett的不等式也适用,并且受方差驱动,有时会更好。 \ [
\ begin {aligned}
E [L_i(w,h)^ 2]&= (1 - \tilde q (q, w)) (1 - r_0) \lambda (0;w,q)^ 2 + \ tilde q(q,w)(1-r_1)\ lambda(1; w,q)^ 2,\\
\ frac {d} {dw} E [L_i(w,h)^ 2]&=-\ frac {(1- q)q(1- r_1-(1- r_0)w ^ 2)} {w ^ 2 },\\
\剩下。 \ frac {d} {d w} E [L_i(w,h)^ 2] \ right | _ {w = 1}&=(1-q)q(r_1-r_0),\\
\frac{d^2}{d w^2} E [L_i(w,h)^ 2]&= \frac{2 (1 - q) q (1 - r_1)}{w^3} > 0.
\ end {aligned}
\]的意思是:如果$ r_1>r_0 $的取值范围为$ w<1 $,估计量的方差低于$ w = 1 $时。这表明,只要要评估的假设在阳性实例上比阴性实例更可能正确时,对阳性样本进行一定程度的子采样是有益的,例如琐碎的假设$ h(\ cdot)= 1 $。有趣的是,即使$ q也是如此< 1/2$.

目前尚不清楚如何使用此结果,因为通常一个人想对一组假设限制经验风险的偏差,其中一些假设不能满足$ r_1>r_0 $。这是一个主意:因为我们知道$ q = E _ {(x,y)\ sim D} [1_ {y = 1}]>1/2 $,假设我们有某种方式(很有可能?)仅考虑以下假设:$ E _ {(x,y)\ sim D} [1_ {h(x)= 1}] \ geq \ rho \ geq q $。在这种情况下,解决方案\ [
\ begin {aligned}
\ min \;&r_1-r_0 \\
&s.t。 \\
0&\ leq r_1 \ leq 1 \\
0&\ leq r_0 \ leq 1 \\
\ frac {1} {2}&<q \ leq \ rho \ leq 1 \\
E _ {(x,y)\ sim D} [1_ {h(x)= 1}]&= q r_1 +(1- q)(1-r_0)\ geq \ rho,\\
\ end {aligned}
\]由$(r_1-r_0)=(\ rho-q)/(1-q)\ geq 0 $给出,即,这样的假设集将受益于二次采样。这个约束与我在机器学习软件中见过的任何东西都不对应。但是,假设$ E _ {(x,y)\ sim D} [1_ {h(x)= 1}] \ leq \ chi \ leq q $。然后解\
\ begin {aligned}
\ min \;&l(h)=(1-q)(1-r0)+ q(1-r1)\\
&s.t。 \\
0&\ leq r_1 \ leq 1 \\
0&\ leq r_0 \ leq 1 \\
\ frac {1} {2}&< q \leq 1 \\
E _ {(x,y)\ sim D} [1_ {h(x)= 1}]&= q r_1 +(1-q)(1-r_0)\ leq \ chi \\
0&\ leq \ chi \ leq q,\\
\ end {aligned}
\]由$ l(h)= q-\ chi $给出。由于常数假设$ h(\ cdot)= 1 $损失了$ 1-q $,因此它比$ \ chi的任何假设都好<2 q-1 $。因此,当数据集非常不平衡($ q \ to 1 $)时,可能的情况是,其估计量因二次抽样而退化的假设远非最小值,因此不太可能使经验风险最小化器混淆。这个论点显然需要改进,但它确实与在非常不平衡的数据集上进行在线学习时发生的情况相对应:首先,该模型迅速学会说一切都是主导类,然后开始找出各种例外情况。

没意见:

发表评论