2010年12月10日,星期五

更多关于零的不重要

在一个 以前的帖子 我谈到了在高度偏倚的分布中对零奖励示例进行二次采样如何使学习成本降低(以实际美元计算或时下使用云计算进行演讲)。在政策估计和回归的情况下,重要性加权对于``统计上消除''有偏抽样的影响很重要。通常,我只是谈论重要性加权是如何无偏的,但是我也谈到了比率估算器,并说
该比率的期望值不是期望值的比率,因此后一个估计量可能有偏差,但希望并非如此(我应该对此有更好的理解)。
好在NIPS 2010 科尔特斯(Cortes)等。等 我已经对重要性加权进行了分析,其中除其他外,上述引证使我们得以了解,因此我认为我将把他们的分析专门用于对零奖励进行二次抽样的情况。

如果您只关心结果 食谱 对于具有零奖励子采样的在线回归,请跳到最后。

设置

我将处理在$ X \ times Y $上的分布$ P $和通过以下方式定义的零奖励二次抽样分布$ Q $的特殊情况
  1. 从$ P $绘制$(x,y)$;
  2. 如果$ y = 0 $,则以概率$(1-1)$拒绝;
  3. 输出实例$ \ left(x,y \ right)$,
一个激励性的示例是在线回归,当大多数示例的值为零时,在这种情况下,拒绝过程会增加在线估计量的吞吐量。我对正数很少见的情况特别感兴趣,即$ E_P [1_ {y = 0}] \到1 $,而``积极的''二次抽样旨在平衡数据集。如果目标是实现$ E_Q [1_ {y = 0}] = \ beta \ leq E_P [1_ {y = 0}] $,则\ [l = \ frac 广东11选五开奖号码查 beta} {1-\ beta} \ frac {(1-E_P [1_ {y = 0}])} {E_P [1_ {y = 0}]}。 \]典型的$ \ beta $是$ 1/2 $,即为实现完美平衡而进行的二次采样。
重量功能
权重函数定义为$ w(\ cdot)= P(\ cdot)/ Q(\ cdot)$,指示如何将对$ P $的期望转换为对$ Q $的期望,该期望是绝对连续的与$ P $。对于二次采样,权重函数由\ [\ begin {aligned}
w(x,y)&= \ frac {l ^ {-1} 1_ {y = 0} + 1_ {y \ neq 0}} {E _ {(x,y)\ sim Q} [l ^ {-1 } 1_ {y = 0} + 1_ {y \ neq 0}]} \\
&= \ frac {1 +(l ^ {-1}-1)1​​_ {y = 0}} {E _ {(x,y)\ sim Q} [1 +(l ^ {-1}-1)1​​_ {y = 0}]} \\
&= \ frac {1 +(l ^ {-1}-1)1​​_ {y = 0}} {1 +(l ^ {-1}-1)q_0} \\
&= \ left(1 +(l ^ {-1}-1)1​​_ {y = 0} \ right)\ left(1 +(l-1)p_0 \ right),
\ end {aligned}
\]其中$ p_0 = E_P [1_ {y = 0}] $和$ q_0 = E_Q [1 _ {y = 0}] = l p_0 /(l p_0 +1-p_0)$。注意,我实际上并不知道$ w $,因为我不知道先例出现零奖励示例的频率。但是,我可以说以下,\ [
\ underset {x,y} 广东11选五开奖号码查 operatorname {sup \;}}} w(x,y)= w(x,0)= l ^ {-1} +(1-l ^ {-1})p_0,
\]和我感兴趣的领域\ [
\ underset {x,y} 广东11选五开奖号码查 operatorname {sup \;}}} w(x,y)\ biggr | _ {l = \ frac 广东11选五开奖号码查 beta(1-p_0)} {(1-\ beta)p_0}} = \ frac {p_0} 广东11选五开奖号码查 beta} \ underset {p_0 \ to 1} 广东11选五开奖号码查 longrightarrow} \ frac {1} 广东11选五开奖号码查 beta}。
\]因此,即使在二次采样非常激进的情况下,重要性权数实际上还是有界的,因为正数非常罕见。如果这与我以前的帖子似乎矛盾,那是因为在我之前的帖子中,我没有考虑分母项$ E _ {(x,y)\ sim Q} [l ^ {-1} 1_ {y = 0} + 1_ { y \ neq 0}] $;有关此的更多信息。
Rènyi Divergences
此数量描述了分布$ Q $和绝对连续有$ Q $的分布$ P $之间的差,\ [D _ 广东11选五开奖号码查 alpha}(P || Q)= \ frac {1} 广东11选五开奖号码查 alpha-1} \ log_2 E _ {(x,y)\ sim P} \ left [\ left(\ frac {P(x,y)} {Q(x,y)} \ right)^ 广东11选五开奖号码查 alpha-1} \ right], \],并另外定义$ d _ 广东11选五开奖号码查 alpha}(P || Q)= 2 ^ {D _ 广东11选五开奖号码查 alpha}(P || Q)} $。对于二次采样,由\ [\ begin {aligned}
D _ 广东11选五开奖号码查 alpha}(P || Q)&= \ frac {1} 广东11选五开奖号码查 alpha-1} \ log_2 \ frac {E _ {(x,y)\ sim P} \ left [\ left(l ^ {- 1} 1_ {y = 0} + 1_ {y \ neq 0} \ right)^ 广东11选五开奖号码查 alpha-1} \ right]} 广东11选五开奖号码查 left(E _ {(x,y)\ sim Q} \ left [l ^ {-1} 1_ {y = 0} + 1_ {y \ neq 0} \ right] \ right)^ 广东11选五开奖号码查 alpha-1}} \\
&= \ frac {1} 广东11选五开奖号码查 alpha-1} \ log_2 \ frac {E _ {(x,y)\ sim P} \ left [l ^ {1-\ alpha} 1_ {y = 0} + 1_ {y \ neq 0} \ right]} 广东11选五开奖号码查 left(E _ {(x,y)\ sim Q} \ left [l ^ {-1} 1_ {y = 0} + 1_ {y \ neq 0} \ right] \右)^ 广东11选五开奖号码查 alpha-1}} \\
&= \ frac {1} 广东11选五开奖号码查 alpha-1} \ log_2 \ frac {E _ {(x,y)\ sim P} \ left [1 +(l ^ {1-\ alpha}-1)1​​_ {y = 0} \ right]} 广东11选五开奖号码查 left(E _ {(x,y)\ sim Q} \ left [1 +(l ^ {-1}-1)1​​_ {y = 0} \ right] \ right)^ { \ alpha-1}} \\
&= \ frac {1} 广东11选五开奖号码查 alpha-1} \ log_2 \ frac {1 +(l ^ {1-\ alpha}-1)p_0} 广东11选五开奖号码查 left(1 +(l ^ {-1}-1) q_0 \ right)^ 广东11选五开奖号码查 alpha-1}}。 \\
\ end {aligned}
\]
在引理1科尔特斯等。等节目 \[
\ begin {aligned}
E _ {(x,y)\ sim Q} [w(x,y)]&= 1,\\
E _ {(x,y)\ sim Q} [w ^ 2(x,y)]&= d_2(P || Q)\\
&= \ frac {l +(1-1)p_0} {l +(1-1)q_0} \\
&= \ frac 广东11选五开奖号码查 left(l(1-p_0)-p_0 \ right)(1-(1-l)p_0)} {l},
\ end {aligned}
\]和我感兴趣的领域\ [
E _ {(x,y)\ sim Q} [w ^ 2(x,y)] \ biggr | _ {l = \ frac 广东11选五开奖号码查 beta(1-p_0)} {(1-\ beta)p_0}} = 1 + \ frac {(\ beta-p_0)^ 2} 广东11选五开奖号码查 beta(1-\ beta)} \ underset {p_0 \ to 1} 广东11选五开奖号码查 longrightarrow} \ frac {1} 广东11选五开奖号码查 beta}。
\]

学习保证

所以科尔特斯等。等描述假设$ h $(相对于$ P $)的真实风险之间的一些关系\ [R(h)= E _ {(x,y)\ sim P} [L(h(x),y​​)] \]和经验重要性加权风险(对于从$ Q ^ m $抽取的有限样本而言)\ [\ widehat R_w(h)= \ frac {1} {m} \ sum_ {i = 1} ^ mw( x_i,y_i)L(h(x_i),y)。 \]这里的情况略有不同,因为我的重要性权重取决于$ y $,而在本文中则不然。我应该验证这不会破坏他们的定理。

他们的定理2给出了有限假设集\ [
R(h)\ leq \ widehat R_w(h)+ \ frac {2 M(\ log | H | + \ log \ frac {1} 广东11选五开奖号码查 delta})} {3 m} + \ sqrt 广东11选五开奖号码查 frac {2 d_2(P || Q)(\ log | H | + \ log \ frac {1} 广东11选五开奖号码查 delta})} {m}},
\]其中$ M $是$ \ sup_ {x,y} w(x,y)$。使用$ l = \ frac 广东11选五开奖号码查 beta(1-p_0)} {(1-beta)p_0} $对我的情况进行专门处理,得出\ [
R(h)\ leq \ widehat R_w(h)+ \ frac {2(\ log | H | + \ log \ frac {1} 广东11选五开奖号码查 delta})} {3 m} \ frac {p_0} 广东11选五开奖号码查 beta} + \ sqrt 广东11选五开奖号码查 frac {2(\ log | H | + \ log \ frac {1} 广东11选五开奖号码查 delta})} {m} \ left(1-\ frac {(\ beta-p_0)^ 2} 广东11选五开奖号码查 beta(1-\ beta)} \ right)}。
\]如果$ \ beta $变得非常小,则此界限会变坏,但是这里的典型$ \ beta $是$ 1/2 $,因此一切看起来都合理,这会导致问题$ \ ldots $

为什么过去有麻烦?

权重函数的上界是有界的,因此Cortes等。等建议我应该在学习上没有问题;但实际上在进行在线二次抽样时,我的重要性加权了回归,因为如果我过于积极地进行二次抽样,就会变得不稳定。如何解决这个矛盾?简单: 我做错了。这是我过去所做的事情:决定使用参数$ l $对零奖励进行二次采样,然后使用\ [给定的重要性加权$ \ tilde w $
\ begin {aligned}
\ tilde w(x,0)&= l ^ {-1}&\ mbox {(invalid!)},\\
\ tilde w(x,y \ neq 0)&= 1&\ mbox {(不正确!)}。
\ end {aligned}
\]我(有缺陷的)推理是,由于二次采样,每个观察到的零奖励示例都像$ l ^ {-1} $个实际的零奖励示例。不幸的是,当二次采样率变为0时,这些权重的上限不受限制。实际权重函数的上限受$ 1 /β限制。由于我正确设置了两个重要权重的比率,因此好像在提高学习速度,这导致失败。

对于我的情况,适当的选择由\ [
\ begin {aligned}
w(x,0)&= \ frac {p_0} 广东11选五开奖号码查 beta},\\
w(x,1)&= \ frac {l p_0} 广东11选五开奖号码查 beta} = \ frac {1-p_0} {1-\ beta},
\ end {aligned}
\],特别是对于$ \ beta = 1/2 $,$ w(x,0)= 2 p_0 $和$ w(x,1)= 2(1-p_0)$。实际上,我不知道$ p_0 $,但我通常有一个不错的猜测(例如,平均点击率约为0.5%,因此$ p_0 \ approx 0.995 $),我也可以使用它来设置$ l = \ beta( 1-p_0)/((1-beta)p_0)$。

为什么我过去没有麻烦

过去,我曾在没有重要性加权的情况下对回归采样器进行二次采样数据的训练,然后使用校准阶段来校正二次采样的影响,从而获得了很好的经验。即使在非常激进的子采样级别上,该方法也非常有效。以上考虑是否可以说明这一点?

答案是肯定的。关键见解是,在离线校准期间,我有效地计算了\ [
\ widehat w(x_i,y_i)= \ frac 广东11选五开奖号码查 tilde w(x_i,y_i)} 广东11选五开奖号码查 sum_i \ tilde w(x_i,y_i)}
\]并将这些权重用作重要权重。科尔特斯(Cortes)等。等称这些$ \ widehat w $为``标准​​化重要性权重''。他们表明归一化权重很有可能接近真实权重\ [
\ left | \ widehat w(x_i,y_i)-\ frac {w(x_i,y_i)} {m} \ right | \ leq 2 ^ {5/4} \ max \ {d_2(P || Q),d_2(P || \ widehat Q)\} \ sqrt [\ frac {3} {8}] 广东11选五开奖号码查 frac 广东11选五开奖号码查 log 2我+ \ log \ frac {4} 广东11选五开奖号码查 delta}} {m}}。
\]这说明了为什么基于校准的程序对主动子采样的鲁棒性要强得多。这也是我对上一篇文章中自我提出的问题的答案,即通过用期望值的比率替换比率的期望值会引入多少偏差。

最后,它表明,在线过程可以保持对归一化常数的在线估计,以便消除猜测真正的零奖励概率(例如,指数加权移动平均值)的需要。

一个食谱

这是处理零收益示例极为普遍的在线回归或分类问题的处方。它减少了学习算法必须考虑的数据量,从而提高了计算吞吐量。
食谱:零回报二次抽样的在线回归或分类
  1. 猜猜真正的零奖励概率是多少,称为$ \ hat p_0 \ geq 1/2 $。
  2. 定义$ l =(1-\ hat p_0)/ \ hat p_0 $。
  3. 显然拒绝概率为$(1-1)$的零奖励示例。
  4. 接受所有非零奖励示例。
  5. 重要性权重零奖励示例为$ 2 \ hat p_0 $。
  6. 重要性权重非零奖励示例为$ 2(1-\ hat p_0)$。

没意见:

发表评论