显示带有标签的帖子 数据集不平衡. 显示所有帖子
显示带有标签的帖子 数据集不平衡. 显示所有帖子

2013年7月19日,星期五

使用更少的数据

在一个 以前的帖子 我指出,在进行数据科学时,对较小的数据集进行操作是确保生产率和快速实验的最佳方法之一。在ICML 2013上,我和Nikos提出了 一般策略 使用较少的数据来解决各种各样的问题。

这个想法的灵感来自 类不平衡二次采样启发式。这是计算广告从业者中的一个众所周知的技巧,这种技术的奇特效果一直吸引着我。诀窍在于:当二元分类数据集主要由一个类别的示例组成时,可以对更频繁的类别进行二次采样而不会影响最终分类器的质量。事实证明,我们能够将这一技巧概括如下。

假设您打算通过最小化损失函数$ \ mathcal {L} $(即经验风险最小化(ERM))来从集合$ \ mathcal {H} $中选择假设$ h ^ * $。还要假设有人给您一个假设$ \ tilde h \ in \ mathcal {H} $。您可以在执行ERM之前使用$ \ tilde h $对数据集进行子采样,并且引入的超额风险是适度的(有关确切的超额风险界限,请参见本文)。可以丢弃的数据量取决于$ \ tilde h $的经验损失。如果$ \ tilde h $的经验损失较低,那么您可以主动进行子采样。该策略很简单:以与$ x $上$ \ tilde h $的损失成比例的比率对每个示例$ x $进行采样。您必须对最终子样本进行重要性加权以保持无偏,并在最后一步中将重要性加权的经验损失降至​​最低,但是许多机器学习算法可以直接合并重要性加权(如果没有,则可以使用 将重要性加权损失减少为均匀加权损失 通过拒绝采样)。

在这种解释中,类不平衡子采样启发法对应于使用$ \ tilde h $,它是一个常量预测变量,例如,$ \ forall x,\ tilde h(x)= 0 $对于在正数广告中是一个很好的选择。例子(例如点击)相对较少。但是,此技术的概括适用范围更广。首先,我们有一个非常广泛的损失概念,不仅包括分类,回归,排名和结构化预测。但是还有一些无监督的设置,这些设置可以优化逐点丢失,例如重构错误或困惑。其次,我们允许使用假设集$ \ mathcal {H} $中的任何$ \ tilde h $。通常,对于\\ tilde h $的一个很好的选择是可以容易地按比例估计但损失很小的任何假设。对于类不平衡的问题,最好的常数预测器是很好的,并且很容易按比例估计(只需对标签计数!),但是即使对于那些不平衡的问题,自由选择$ \ tilde h $的能力也具有很大的灵活性。

作为自由选择$ \ tilde h $启用的功能的示例,考虑一下我以前工作过的eHarmony。 eHarmony的一个问题是估计两个人(如果匹配)彼此交流的可能性。 eHarmony已派发约10次6 多年来每天都进行匹配,因此它们拥有庞大的数据集。尽管eHarmony使用数百种功能来预测通信,但仍有一些功能非常有用,而许多功能则非常有用。如果您在会议期间获得了Vaclav Petricek的精彩演讲 UAI 2013推荐研讨会,您知道身高差,年龄差和身体距离是三个具有较高预测价值的功能。仅基于这三个预测变量的预测变量可以轻松地仅使用Hive进行大规模组装,而并非最优的它将损失相对较低。因此,这是$ \ tilde h $的不错的选择。我没有在eHarmony的数据上尝试过此操作,因为在那儿工作时我并不了解这些事情,但是我与Vaclav进行了交谈,他愿意尝试一下。

此技术的一个重要特殊情况是对\\ tilde h $使用线性预测器,对最终ERM使用神经网络或决策树。这很有用,因为线性预测变量可以 估计规模。请注意,要满足定理的条件,您必须确保线性预测变量在$ \ mathcal {H} $中,这对于神经网络意味着从输入到最后一层的直接连接,而对于这两种技术,这意味着非线性预测变量具有访问所有线性特征(可以为最终ERM添加特征)。作为额外的效果,对于线性模型也适用的特征表示也将 也倾向于帮助非线性模型.

因此,现在您有一个原则性的方法可以对巨型数据集进行二次采样,这将在比类不平衡更一般的设置中工作。继续并丢弃一些数据!

2012年1月3日,星期二

二次采样:一个有趣的失败

假设我在i.i.d采样了一个大数据集$ \ {(X_i,Y_i)\} $。来自$ \ mathcal {X} \ times \ mathcal {Y} $的分布$ D $,其中$ \ mathcal {X} $是要素,而$ \ mathcal {Y} $是标签。数据集$ \ {(X_i,Y_i)\} $是一个随机变量,但目前认为它是固定的(即条件)。我可以使用我的大数据集来计算函数$ f的经验方法:\ mathcal {X} \ times \ mathcal {Y} \ to [-1,1] $,其中$ f $有点像一个假设的遗憾,\ [
\ frac {1} {n} \ sum_ {i = 1} ^ n f(X_i,Y_i)。
\] 但是此数据集不适用于我的笔记本电脑,因此我不想使用所有数据集;相反,我将审查一些数据点以构建替代估计量\ [
\ frac {1} {n} \ sum_ {i = 1} ^ n \ frac {Q_i} {P_i} f(X_i,Y_i)。
\] 这里的$ Q_i $是一个指示符变量,它指示我是否使用$ i ^ \ mathrm {th} $数据点和$ P_i = E [Q_i | \ {(X_i,Y_i)\}] $是使用$ i ^ \ mathrm {th} $数据点的概率,我必须按比例缩放这些值以保持无偏。

到目前为止,我已经描述了 重要性加权主动学习 框架。但是,假设我很懒惰,而不是使用真正的主动学习算法,而是要考虑两种缩小数据集的策略:第一种是统一子采样,第二种是对与更普遍的标签相关联的数据进行子采样(只是假设标签为0)。我希望我的估算值很好,所以我会尽量减少\ [
\ mathrm {Pr} \ left(\ left | \ frac {1} {n} \ sum_ {i = 1} ^ n \ frac {Q_i} {P_i} f(X_i,Y_i)-\ frac {1} {n } \ sum_ {i = 1} ^ nf(X_i,Y_i)\ right | \ geq \ delta \ right)。
\] 霍夫丁不等式 在统一采样$ P_i = p_u $适用于序列\ [
\ begin {aligned}
A_i&= \ frac {Q_i} {P_i} f(X_i,Y_i)-f(X_i,Y_i),\\
\ max(A_i)-\ min(A_i)&= \ left(\ frac {1} {p_u}-1 \ right)| f(X_i,Y_i)| \ leq \ left(\ frac {1} {p_u}-1 \ right),
\ end {aligned}
\] 并产生边界,\ [
\ mathrm {Pr} \ left(\ left | \ frac {1} {n} \ sum_ {i = 1} ^ n \ frac {Q_i} {P_i} f(X_i,Y_i)-\ frac {1} {n } \ sum_ {i = 1} ^ nf(X_i,Y_i)\ right | \ geq \ delta \ right)\ leq 2 \ exp \ left(-\ frac {2 \ delta ^ 2 n} {\ left(\ frac {1} {p_u}-1 \ right)^ 2} \ right)。
\] 类似地,对于单标签二次抽样$ P_i = p_o 1_ {Y_i = 0} + 1_ {Y_i = 1} $,\ [
\ begin {aligned}
A_i&= \ frac {Q_i} {P_i} f(X_i,Y_i)-f(X_i,Y_i),\\
\ max(A_i)-\ min(A_i)&= \ left(\ frac {1} {p_o}-1 \ right)| f(X_i,Y_i)| 1_ {Y_i = 0} \ leq \ left(\ frac {1} {p_o}-1 \ right)1_ {Y_i = 0},
\ end {aligned}
\] 产生\ [
\ mathrm {Pr} \ left(\ left | \ frac {1} {n} \ sum_ {i = 1} ^ n \ frac {Q_i} {P_i} f(X_i,Y_i)-\ frac {1} {n } \ sum_ {i = 1} ^ nf(X_i,Y_i)\ right | \ geq \ delta \ right)\ leq 2 \ exp \ left(-\ frac {2 \ delta ^ 2 n ^ 2} {\ left( \ frac {1} {p_o}-1 \ right)^ 2 \ sum_ {i = 1} ^ n 1_ {Y_i = 0}} \ right)。
\] 将两个边界都最小化为$ p \至1 $,这只是一种说法:“非二次采样是最准确的。”为了获得更有趣的陈述,我将通过等同于它们的预期数据集来比较它们大小,\ [
p_u = p_o \ sum_ {i = 1} ^ n I_ {Y_i = 0} +(1-\ sum_ {i = 1} ^ n I_ {Y_i = 0}),
\] ,然后我将采用更好的策略,\ [
\ begin {aligned}
\ log \ left(\ frac {\ mathrm {uniform}} {\ mathrm {onelabel}} \ right)&= -2 \ delta ^ 2 n \ left(n-\ sum_ {i = 1} ^ n I_ {Y_i = 0} \ right)\ frac {n-(1-p_o)^ 2 \ sum_ {i = 1} ^ n I_ {Y_i = 0}} {(1-p_o)^ 2(\ sum_ {i = 1} ^ n I_ {Y_i = 0})^ 2} \\
&\ leq 0。
\ end {aligned}
\] kes!统一的二次采样范围总是更好。

我认为这并不意味着对更普遍的标签进行抽样并不是一个坏主意, 我已经看到它在实践中有效。但是我认为这确实意味着要评估的$ f $的细节很重要。在上述范围内,我仅使用$ | f | \ leq 1 $,但是结果太悲观了。特别是我真正关心的$ f $是经验最小化假设和真实风险最小化假设之间的瞬时遗憾,因此我必须加倍努力,并理解诸如 分歧系数。我怀疑合并该标签将使我能够利用一种假设,即在上述分析中,一个标签比另一个标签的流行程度高得多,我认为这是至关重要的。

2011年12月28日,星期三

标签不平衡的二进制上下文

在我的 以前的帖子 我注意到,在对正样本进行二次抽样时,重要性加权经验风险的方差低于对正样本而非负样本进行检验时的实证风险的方差(在非抽样分布上)。我希望这可以扩展到更广泛的假设集,因为``好''假设在肯定中更可能是正确的,因为它们更普遍。不幸的是,当一个标签盛行($ q>1/2 $)有一些非常好的假设(损失$ l(h)= \ rho $)可以完美地将不太普遍的标签实例分类($ r_0 = 1 $),并在更普遍的标签实例上犯一些错误标签实例($ r_1 = 1-\ rho / q $)。这种假设的重要性加权经验风险方差将在二次抽样下增加($ r_1<r_0 $),这似乎是一件坏事。因此,我决定退后一步并进行一些模拟,以确保我没有发疯。

二进制上下文分类

因此,让我描述一个二进制上下文分类的游戏。有两个由$ X = \ {0,1 \} $索引的硬币。每个硬币都有由对手选择的正面$ q_ {1 | x} $的概率,并且对手也选择了硬币零$ q_0 $的概率。玩家可以观察到$ n $ IID训练示例$(x,y)$,包括选择硬币和抛硬币。然后玩家必须将每个硬币分类为``正面硬币''$(\ hat y = 1 | x)$或``尾硬币''$(\ hat y = 0 | x)$。然后,玩家根据每个示例向对手支付预期的遗憾,即,平均而言,与最佳常量对相比,玩家犯下的预测错误要多多少倍。玩家将再次在训练集上使用经验风险最小化策略,并随机断开联系。现在玩游戏的方法如下:
  1. 裁判宣布训练套装大小$ n $。
  2. 对手选择$ q_0 $,$ q_ {1 | 0} $和$ q_ {1 | 1} $。
  3. 裁判通过重复以下IID生成大小为$ n $的训练集:
    1. 当概率$ q_0 $时选择$ x = 0 $;否则$ x = 1 $。
    2. 选择概率为$ q_ {1 | x} $的$ y = \ mathrm {heads $},否则选择$ y = \ mathrm {tails} $。
  4. 玩家将经验风险降至最低,并报告$(\ hat y | 0,\ hat y | 1)$。
  5. 对手会从Player收集每个示例的预期遗憾。
预期的遗憾由\ [
q_0 \ Psi(q_0,q_ {1 | 0},n)+(1-q_0)\ Psi(1- q_0,q_ {1 | 1},n)
\] 其中\ [
\ begin {aligned}
\ Psi(s,q,n)&= \ sum_ {c = 0} ^ n {n \选择c} s ^ c(1-s)^ {n-c} \ Phi(q,c),\\
\披(q,n)&= \bigl|2 q - 1\bigr| \;p(\ hat y \ neq y ^ * | q; n)。
\ end {aligned}
\] $ \ Phi $是上下文无关游戏的遗憾,它必须在与每个硬币相关的(现在是随机的)训练示例数上取平均。

有一个分析上可证明的局部最优形式,其期望后悔形式为$ q ^ * _ 0 = 1/2 $,$ q ^ * _ {1 | 0} = q ^ * _ {1 | 1} $成为全局最优值:其中有四个对应于硬币的对称性,约为$ 1/2 $。换句话说,对对手来说,最好的选择是选择每个硬币具有相同的概率,并为每个硬币选择相同的中间偏差。这是$ q ^ * _ {1 | 0} = q ^ * _ {1 | 1}的最佳选择>1/2 $代表$ n $的变化,以及游戏对对手的价值,

标签不平衡

现在,我将修改二进制上下文分类的游戏,以便对手必须选择与$ E [1_ {y = 1}] \ geq \ rho一致的参数>1/2 $,即,对手必须总体上有利于正面反面。给定设置,这意味着$ q_0 q_ {1 | 0} +(1-q_0)q_ {1 | 1} \ geq \ rho>1/2 $。现在玩游戏的方法如下:
  1. 裁判员宣布训练集合大小$ n $,最小无条件头部概率$ \ rho> 1/2$.
  2. 对手选择$ q_0 $,$ q_ {1 | 0} $和$ q_ {1 | 1} $,这样$ q_0 q_ {1 | 0} +(1-q_0)q_ {1 | 1} \ geq \ rho $。在不失一般性的前提下,我将标记硬币,使得$ q_ {1 | 1} \ geq q_ {1 | 0} $。
  3. 裁判通过重复以下IID生成大小为$ n $的训练集:
    1. 当概率$ q_0 $时选择$ x = 0 $;否则$ x = 1 $。
    2. 选择概率为$ q_ {1 | x} $的$ y = \ mathrm {heads $},否则选择$ y = \ mathrm {tails} $。
  4. 玩家将经验风险降至最低,并报告$(\ hat y | 0,\ hat y | 1)$。
  5. 对手会从Player收集每个示例的预期遗憾。
这将通过两种方式降低游戏对对手的价值。首先,对手的选择越来越多地限制为$ \ rho \至1 $,因此最佳可用游戏将不是很好。其次,如果玩家知道限制条件,则可以排除(``tails'',``tails'')的答案,因为这是不可能的。在剩余假设上将经验风险最小化将导致玩家说出(``heads'',``tails'')或(``tails'',``heads''),即使两个上下文都不占多数在训练集中。

首先假设约束对对手选择的影响,假设玩家仍然在不考虑约束的情况下进行经验风险最小化。据我所知,共有三种制度:
  1. 如果$ \ rho $足够接近1/2,则不会影响对手的最佳玩法(除非它必须选择与$ q ^ * _ {y | x}相对应的模式>1/2 $):分别通过$ q ^ * _ 0 = 1/2 $和$ q ^ * _ {1 | 0} = q ^ * _ {1 | 1} = \ theta $对待每个硬币。
  2. 当$ \ rho $增加到$ \ theta $以上时,最初的最佳操作仍然是通过$ q ^ * _ 0 = 1/2 $相同地对待每个硬币,但要调整$ q ^ * _ {1 | 0} = q ^ * _ {1 | 1} = \ rho $符合约束。
  3. 最终会有一个相变,选择$ q_0 $来满足约束条件使$ q ^ * _ {1 | 1} \ neq q ^ * _ {1 | 0} $变得更好。非常快地将$ q ^ * _ {1 | 1} \转换为1 $,尽管它仍然具有减少与另一枚硬币关联的训练数据量并使另一枚硬币保持在$ 1/2 $附近的双重目的。当$ \ rho $增加$ q ^ * _ {1 | 1} = 1 $时,$ q ^ * _ {1 | 0} \至1 $,而$ q ^ * _ 0 \至0 $。
现在,我将结合玩家意识到的约束条件,并因此在减少的假设集上进行经验风险最小化,即从不选择(``尾巴'',``尾巴'')。边界和最佳位置略有变动,但这并没有从根本上改变对手的策略;但是,它确实会明显降低$ q_ {1 | 1}中对手的游戏价值<1美元制度(出于比较目的,我在下图中复制了上图的预期遗憾)。
在$ q_ {1 | 1} = 1 $的情况下,玩家进行无约束的经验风险最小化时选择的机会(“尾巴”,“尾巴”)很小,以至于基本上没有影响游戏价值。

二次采样

现在,我将修改游戏,以便对训练数据进行二次采样。由于对手被迫在总体上偏向于正面而不是正面,因此我们将对正面进行子采样。现在玩游戏的方法如下:
  1. 裁判员宣布训练集合大小$ n $,最小无条件头部概率$ \ rho> 1/2$.
  2. 玩家宣布$ w $。
  3. 对手选择$ q_0 $,$ q_ {1 | 0} $和$ q_ {1 | 1} $,这样$ q_0 q_ {1 | 0} +(1-q_0)q_ {1 | 1} \ geq \ rho $。在不失一般性的前提下,我将标记硬币,使得$ q_ {1 | 1} \ geq q_ {1 | 0} $。
  4. 裁判通过重复以下IID直到生成$ n $个样本来生成训练集:
    1. 当概率$ q_0 $时选择$ x = 0 $;否则$ x = 1 $。
    2. 选择概率为$ q_ {1 | x} $的$ y = \ mathrm {heads $},否则选择$ y = \ mathrm {tails} $。
    3. 如果$ y = \ mathrm {heads} $,则以概率$ w $拒绝样本。
  5. 玩家将重要性加权的经验风险降至最低,并报告$(\ hat y | 0,\ hat y | 1)$。玩家将所有假设最小化,包括(``tails'',``tails'')。
  6. 对手会从Player收集每个示例的预期遗憾。
二次采样在此游戏中具有三种效果。
  1. 它改变了训练数据中出现的上下文的分布,从而导致更可能产生拖尾的上下文更加频繁地出现。特别是训练集的有效$ q_0 $为\ [
    \ tilde q_0(q_0,q_ {1 | 0},q_ {1 | 1},w)= \ frac {q_0(q_ {1 | 0} w +1-q_ {1 | 0})} {q_0(q_ {1 | 0} w +1-q_ {1 | 0})+(1-q_0)(q_ {1 | 1} w +1-q_ {1 | 1})}。
    \] 实际上可能会引起问题:如果Player没有针对特定上下文的任何训练数据,则对该上下文的预测是随机的,并且在$ q_ {1 | 0}时进行极端子采样<1 $和$ q_ {1 | 1} = 1 $将消除上下文1的所有训练数据,从而增加遗憾。但是,中等量的二次采样将避免在“显而易见”的$ q_ {1 | 1} = 1 $上下文中“浪费”训练数据,因为只需要一个观察就可以使该上下文正确。
  2. 上下文中头与尾的分布被修改,\ [
    \ tilde q_ {1 | x}(q_ {1 | x},w)= \ frac {q_ {1 | x} w} {q_ {1 | x} w +(1-q_ {1 | x})} 。
    \]
  3. 它将说出``正面''的阈值从看到训练数据中的$ n / 2 $正面更改为$ n w /(1 + w)$。如果有特殊要求,价格为$ w <1美元,非零的关系被打破,有利于团长。 (如果没有针对特定情况的训练数据,则对于每种选择,重要性加权的经验风险都相同,因此,玩家平均分配随机数)。
以下是$ n = 21 $发生的情况:
  1. 当$ \ rho $接近1/2时,播放器会选择少量的二次采样$ w ^ * = 1-\ epsilon $,从本质上讲,这种关系会导致有利于头的关系破裂。对手通过打一个正面硬币和一个反面硬币来缓解平局的效果。
  2. 随着$ \ rho $的增加,满足一枚正面硬币和一枚反面硬币的约束变得太昂贵了,因此,对手打出两个相同的正面硬币,玩家获得决胜局优势。
  3. 随着$ \ rho $进一步增加,对手将设置$ q_ {1 | 1} = 1 $。此时,玩家选择一个$ w ^ * $,这会使对手无视播放$ q ^ * _ {1 | 0}<1/2 $与$ q ^ * _ {1 | 0}>1/2 $。 (该图似乎在此间隔内在这两个解决方案之间随机切换:因此,我选择了$ q ^ * _ {1 | 0}<1/2 $点使图表更清晰可见)。
  4. 随着$ \ rho $的进一步增加,玩家有时会切换到$ w ^ * = 1/2-\ epsilon $。对手通过选择$ q ^ * _ {1 | 0}进行响应>1/2 $。 $ w ^ * $的这种选择打破了2 / 3rd的平局,转为正面。
  5. 随着$ \ rho $进一步增加,玩家有时会切换回选择$ w ^ * $,这会使对手无视播放$ q ^ * _ {1 | 0}<1/2 $与$ q ^ * _ {1 | 0}>1/2 $。 (同样,为了清晰起见,我选择了$ q ^ * _ {1 | 0}< 1/2$ points).
  6. 作为$ \ rho \ uparrow 1 $,$ w ^ * \ uparrow 1 $,而对手则扮演$ q_ {1 | 0}>1/2 $。二次抽样的好处再次由决胜局效应控制。

评论

负采样消除确实有助于简化设置。但是,打破非零关系(即,在特定情况下训练头部和尾部的次数相等)是举升机的主要组成部分。这可能是基本的东西,也可能是设置的产物。在$ \ rho $的某些值中,子采样似乎以打破平局的方式起作用,但是选择的子采样量很小。
特别是我看不到$ w ^ * \ to 0 $就像$ \ rho \ to 1 $。这可能是因为每当$ q_ {1 | 0}<1 $和$ q_ {1 | 1} = 1 $,因为$ w ^ * \ to $$ 0对于上下文1没有训练数据的机会趋于统一,然后随机化规则引起一些遗憾。如果Player在没有训练数据的情况下预测上下文,我可能会得到不同的结果。

总体而言,该示例不支持对与更频繁出现的标签相关联的数据进行积极的子采样以减小分类训练集的大小的想法。回到绘图板!

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 $)时,可能的情况是,其估计量因二次抽样而退化的假设远非最小值,因此不太可能使经验风险最小化器混淆。这个论点显然需要改进,但它确实与在非常不平衡的数据集上进行在线学习时发生的情况相对应:首先,该模型迅速学会说一切都是主导类,然后开始找出各种例外情况。

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 $过于激进。

回到绘图板。

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,我没有很好的理论解释。

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 {\ 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} {\ operatorname {sup \;}}} w(x,y)= w(x,0)= l ^ {-1} +(1-l ^ {-1})p_0,
\] 和我感兴趣的领域\ [
\ underset {x,y} {\ operatorname {sup \;}}} w(x,y)\ biggr | _ {l = \ frac {\ beta(1-p_0)} {(1-\ beta)p_0}} = \ frac {p_0} {\ beta} \ underset {p_0 \ to 1} {\ longrightarrow} \ frac {1} {\ beta}。
\] 因此,即使在二次采样非常激进的情况下,重要性权数实际上还是有界的,因为正数非常罕见。如果这与我以前的帖子似乎矛盾,那是因为在我之前的帖子中,我没有考虑分母项$ E _ {(x,y)\ sim Q} [l ^ {-1} 1_ {y = 0} + 1_ { y \ neq 0}] $;有关此的更多信息。
Rènyi Divergences
此数量描述了分布$ Q $和绝对连续有$ Q $的分布$ P $之间的差,\ [D _ {\ alpha}(P || Q)= \ frac {1} {\ alpha-1} \ log_2 E _ {(x,y)\ sim P} \ left [\ left(\ frac {P(x,y)} {Q(x,y)} \ right)^ {\ alpha-1} \ right], \] ,并另外定义$ d _ {\ alpha}(P || Q)= 2 ^ {D _ {\ alpha}(P || Q)} $。对于二次采样,由\ [\ begin {aligned}
D _ {\ alpha}(P || Q)&= \ frac {1} {\ alpha-1} \ log_2 \ frac {E _ {(x,y)\ sim P} \ left [\ left(l ^ {- 1} 1_ {y = 0} + 1_ {y \ neq 0} \ right)^ {\ alpha-1} \ right]} {\ left(E _ {(x,y)\ sim Q} \ left [l ^ {-1} 1_ {y = 0} + 1_ {y \ neq 0} \ right] \ right)^ {\ alpha-1}} \\
&= \ frac {1} {\ alpha-1} \ log_2 \ frac {E _ {(x,y)\ sim P} \ left [l ^ {1-\ alpha} 1_ {y = 0} + 1_ {y \ neq 0} \ right]} {\ left(E _ {(x,y)\ sim Q} \ left [l ^ {-1} 1_ {y = 0} + 1_ {y \ neq 0} \ right] \右)^ {\ alpha-1}} \\
&= \ frac {1} {\ alpha-1} \ log_2 \ frac {E _ {(x,y)\ sim P} \ left [1 +(l ^ {1-\ alpha}-1)1​​_ {y = 0} \ right]} {\ left(E _ {(x,y)\ sim Q} \ left [1 +(l ^ {-1}-1)1​​_ {y = 0} \ right] \ right)^ { \ alpha-1}} \\
&= \ frac {1} {\ alpha-1} \ log_2 \ frac {1 +(l ^ {1-\ alpha}-1)p_0} {\ left(1 +(l ^ {-1}-1) q_0 \ right)^ {\ 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 {\ 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 {\ beta(1-p_0)} {(1-\ beta)p_0}} = 1 + \ frac {(\ beta-p_0)^ 2} {\ beta(1-\ beta)} \ underset {p_0 \ to 1} {\ longrightarrow} \ frac {1} {\ 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} {\ delta})} {3 m} + \ sqrt {\ frac {2 d_2(P || Q)(\ log | H | + \ log \ frac {1} {\ delta})} {m}},
\] 其中$ M $是$ \ sup_ {x,y} w(x,y)$。使用$ l = \ frac {\ beta(1-p_0)} {(1-beta)p_0} $对我的情况进行专门处理,得出\ [
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)}。
\] 如果$ \ 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} {\ beta},\\
w(x,1)&= \ frac {l p_0} {\ 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 {\ tilde w(x_i,y_i)} {\ 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}] {\ frac {\ log 2我+ \ log \ frac {4} {\ 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)$。

2010年11月13日,星期六

关于零的不重要

在大多数广告网络上,广告的大多数展示都不会导致任何用户交互(例如,未点击)。同样,在在线婚介中,大多数介绍都不会引起人们的兴趣。因此,任何尽职尽责地记录每个行动和每个结果的系统都将包含历史数据,这些历史数据主要由零值奖励组成。在广告投放中,零与非零的比率很容易达到100:1或更高,因此,舍弃零就是舒适地放在笔记本电脑上的数据集与需要映射缩减的数据集之间的差。或者$ 100 EC2票据和$ 10,000 EC2票据之间的差额。

直观地,如果零示例是常见的,而非零示例很少,那么非零示例每个样本包含的信息要比零示例多得多。这表明对零奖励示例进行二次采样,例如合成大约1:1比例的数据集,在泛化方面可能并不那么昂贵。这里简要讨论一些可以完成的情况。

政策价值估算

假设我正在尝试根据根据已知策略生成的历史数据来估计与新颖的确定性策略相关的预期收益。当绘制示例IID时,可以使用离线策略估计器来评估静态策略。假设分布$ D = D_x \ times D_ {r | x} $,其中$ x $是与实例关联的特征向量,而$ r:A \ to [0,1] $是与每个动作关联的奖励。我有一个建议的策略$ \ pi:X \ to A $,我想估计$ D $,$ E _ {(x,r)\ sim D} \ left [r \ left(\ pi( x)\ right)\ right] $。进一步假设历史策略在给定实例$ p(a | x)$的情况下对操作使用已知的条件分布。历史策略定义了由定义的历史数据的分布$ S $
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(a | x)$中提取$ a $。
  3. 输出实例$ \ left(x,a,r(a),p(a | x)\ right)$。
很容易证明\ [
\ begin {aligned}
E _ {(x,a,r(a),p)\ sim S} \ left [r(\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x )| x)} \ right]&= E _ {((x,r)\ sim D} \ left [r \ left(\ pi(x)\ right)\ right],
\ end {aligned}
\] 在给定历史数据集$ H $的情况下使用经验策略估计量进行证明,\ [\ frac {1} {| H |} \ sum _ {(x,a,r(a),p)\ in H} r (\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x)| x)}。
\] 这是经验政策估算器的有趣之处:任何观察到的历史奖励为零的实例都可以在不更改总和的情况下丢弃。为了正确地获得标准化常数,需要知道零示例的数量,但是关于零示例的任何其他详细信息对于计算策略估计器都是完全不必要的。这意味着数据集只需要一个常数因数,该常数要大于存储所有非零示例所需的空间。

有时,我遇到的系统具有已知的日志记录策略,该系统很早就对零个示例进行了子采样,而总的零奖励示例计数并未保留。定义了一个新的分布$ \ tilde S $通过
  1. 从$ D $中提取$(x,r)$。
  2. 从$ p(a | x)$中提取$ a $。
  3. 观察$ r(a)$。
  4. 如果$ r(a)= 0 $,则以概率$(1-1)$拒绝。
  5. 输出实例$ \ left(x,a,r(a),p(a | x),l \ right)$。
在这种情况下,$ S $和$ \ tilde S $由\ [
E _ {(x,a,r(a),p,l)\ sim S} \ left [f \ right] = \ frac {E _ {(x,a,r(a),p)\ sim \ tilde S } \ left [\ left(l ^ {-1} 1_ {r(\ pi(x))= 0} + 1_ {r(\ pi(x))\ neq 0} \ right)f \ right]} { E _ {(x,a,r(a),p)\ sim \ tilde S} \ left [\ left(l ^ {-1} 1_ {r(\ pi(x))= 0} + 1_ {r( \ pi(x))\ neq 0} \ right)\ right]},
\] 建议使用给定的历史数据集$ \ tilde H $,\ [\ frac {1} {\ eta(\ tilde H)} \ sum _ {(x,a,r(a), p,l)\ in \ tilde H} r(\ pi(x))\ frac {1 _ {\ pi(x)= a}} {p(\ pi(x)| x)},\]其中$ \ eta(\ tilde H)$是有效的历史数据集大小,\ [
\ eta(\ tilde H)= \ sum _ {(x,a,r(a),p,l)\ in \ tilde H} \ left(l ^ {-1} 1_ {r(a)= 0} + 1_ {r(a)\ neq 0} \ right),
\] ,例如,零奖励示例会将有效集合大小增加$ 1 / l $。注意分子不受影响,因为零奖励示例不起作用。

当然,比率的期望值不是期望值的比率,因此后者的估计值可能有偏差,但希望并非如此(我应该对此有更好的理解)。

AUC

假设我正在尝试估计排名模型的AUC。我假设奖励是二进制值,具有条件要素实例分布$ D_ {x | 0} $和$ D_ {x | 1} $。为简单起见,我假设我的模型通过评分函数$ \ phi:X \ to \ mathbb {R} $引发线性排序。在这种情况下,AUC由\ [
\mbox{AUC} (\phi) = E_{(x_+, x_-) \sim D_{x|1} \times D_{x|0}} \left[ 1_{\phi (x_+) > \phi (x_-)} + \ frac {1} {2}1_{\phi (x_+) = \phi (x_-)} \right].
\] 这是AUC的``正确成对比较的概率''形式,等同于``曲线下面积''公式。现在,我可以将$ D_ {x | 0} $替换为新的分布$ \ tilde D_ {x | 0} $,定义为
  1. 从$ D_ {x | 0} $中提取$ x $。
  2. 以恒定概率$ p $拒绝$ x $。
  3. 否则,发出$ x $。
希望明确的是,对于$ D_ {x | 0} $和$ \ tilde D_ {x | 0} $的期望是相同的。因此\ [
\mbox{AUC} (\phi) = E_{(x_+, x_-) \sim D_{x|1} \times \tilde D_{x|0}} \left[ 1_{\phi (x_+) > \phi (x_-)} + \ frac {1} {2}1_{\phi (x_+) = \phi (x_-)} \right],
\] ,即使用历史数据集(其中负面示例已被明显地二次抽样)不会带来偏差。

当然,我可以对肯定因素重复此论点,得出荒谬的结论,即仅用一个肯定的例子和一个否定的例子就可以构造一个很好的AUC估计量。好吧,这样的AUC估算器将是 无偏见的 (根据历史记录中可能的单例对的集合进行平均),但事实并非如此 。要理解这一点,如Agarwal等人所探讨的那样,有助于研究将经验AUC与实际AUC相关联的偏差范围。在 这篇报告。定理3是金钱,其中\
P_ {T \ sim D ^ N} \ left \ {\ left | \ mbox {AUC} _e(\ phi,T)-\ mbox {AUC}(\ phi)\ right | \ geq \ sqrt {\ frac {\ ln(\ frac {2} {\ delta})} {2 \ rho(T)(1-\ rho(T))N}} \ right \} \ leq \ delta,
\] 其中$ \ mbox {AUC} _e $是训练数据集$ T $上的经验AUC,而$ \ rho(T)$衡量训练集标签中的不平衡量,\ [
\ rho(T)= \ frac {1} {N} \ sum _ {(x,y)\ in T} 1_ {y = 1}。
\] 此处有两个条件驱动偏差范围。首先是评估经验AUC估计量时使用的示例数:越多越好。但是,第二个度量了所使用示例的不平衡程度。如果数据集中的正样本比负样本多得多,反之亦然,则偏差范围会降低。这正式化了这样的直觉,即结果很少的例子比一般的结果携带更多的信息。

这是一个有趣的问题:对于固定总数的示例$ N $,使偏差范围最小化的正例与负例之比是多少?答案是$ \ rho(T)= 1/2 $,即正例与负例的1:1比率,这表明如果评估$ \ phi $昂贵,或者您只有一定数量的硬盘空间或通过网络提取数据是一个瓶颈等,为实现奇偶校验而进行二次采样是评估AUC丢失的好策略。

到目前为止,讨论都是在评估方面进行的,但是在培训过程中,一些策略有效地归结为针对经验AUC进行优化(可能与其他术语一起使用以提高泛化性)。培训通常比评估贵,因此在这里固定数据预算的想法非常合理。上方的偏差自然建议对平衡数据集进行训练。这是根据经验探索的 一篇论文 由Weiss和Provost撰写,他们在使用C4.5作为学习算法的多个数据集中发现,``当使用ROC曲线下方的面积评估分类器性能时,显示出均衡的分布表现良好。''还提出了一种更复杂的技术,称为``预算敏感''渐进采样,以进一步提高分类器的性能。

当数据预算不成问题时,也有可能对少数类进行过度采样以形成平衡的数据集,并且可能会提高通用性。这个和其他想法在 一篇论文 由Batista等撰写。等

回归

假设我正在尝试维护回归器$ \ phi:X \ to \ mathbb {R} $,其目的是估计上下文的条件期望回报(为简单起见,假定此处没有任何操作;仅包含一系列上下文,其中包含相关的标量奖励)。在这种情况下,我有一个根据$ D = D_x \ times D_ {r | x} $绘制的IID数据,并且我正在尝试最小化平方损失\ [
E _ {((x,r)\ sim D} \ left [(r-\ phi(x))^ 2 \ right]。
\] 我处于在线状态,恐怕我的回归器会被数据量淹没,所以我正在考虑对零奖励示例进行二次抽样。我正在有效地定义一个新的分布$ \ tilde D $
  1. 从$ D $中提取$(x,r)$。
  2. 如果$ r = 0 $,则以概率$(1-1)$拒绝。
  3. 输出实例$ \ left(x,r,l \ right)$。
这两个分布通过\ [
E _ {((x,r)\ sim D} \ left [f \ right] = \ frac {E _ {(x,r)\ sim \ tilde D} \ left [(l ^ {-1} 1_ {r = 0 } + 1_ {r \ neq 0})f \ right]} {E _ {(x,r)\ sim \ tilde D} \ left [(l ^ {-1} 1_ {r = 0} + 1_ {r \ neq 0})\ right]}。
\] 如果回归变量实际上是重要性加权回归算法(例如GD),则使用重要性加权$ w(l,r)=(l ^ {-1} 1_ {r = 0} + 1_ {r \ neq 0})$在二次采样数据上导致\ [
E _ {((x,r)\ sim D} \ left [(r-\ phi(x))^ 2 \ right] = \ frac {E _ {(x,r)\ sim \ tilde D} \ left [w( l,r)(r-\ phi(x))^ 2 \ right]} {E _ {(x,r)\ sim \ tilde D} \ left [w(l,r)\ right]},
\] ,即原始分布中的平方损失与子采样分布中的重要性加权平方损失成正比。在实践中,如果子采样过于激进,则零奖励示例的重要性权重将太大而性能将很差,但这是将数据量降低10倍的明智方法。 (要真正扩大规模,需要采用大规模的并行学习策略,因此,我对 在NIPS 2010上学习集群 今年。)

在离线环境中,我发现校准通常可以改善估计量(也许也在在线环境中?我没有尝试过,但是我要描述的过程也可以在线实现)。表示确保估计器的输出接近奖励的条件期望值。最近,我通过获取校准样本$ \ {(x_i,r_i)\} \ sim D ^ * $来进行此操作,并使用未经校准的估算器对其进行处理,以获得原始估算$ \ {(x_i,\ phi(x_i ),r_i)\} $,并将其汇总到$ J $箱中,以使相等数量的样本落入每个范围$ b_ {j-1} \ leq \ phi(x_i) < b_j$, with $b_0$ and $b_J$ being the smallest and largest possible output of the uncalibrated estimator. I then define control points via \[
\ begin {aligned}
\ hat \ phi_j&= E _ {(x,r)\ sim D} \ left [\ phi(x)| b_ {j-1} \ leq \ phi(x) < b_j \right] \approx \frac{\sum_{\{ x_i, \phi (x_i), r_i \}} \phi (x_i) 1_{b_{j-1} \leq \phi (x_i) < b_j}}{\sum_{\{ x_i, \phi (x_i), r_i \}} 1_{b_{j-1} \leq \phi (x_i) < b_j}}, \\
\ hat r_j&= E _ {(x,r)\ sim D} \ left [r | b_ {j-1} \ leq \ phi(x) < b_j \right] \approx \frac{\sum_{\{ x_i, \phi (x_i), r_i \}} r_i 1_{b_{j-1} \leq \phi (x_i) < b_j}}{\sum_{\{ x_i, \phi (x_i), r_i \}} 1_{b_{j-1} \leq \phi (x_i) < b_j}}.
\ end {aligned}
\] 集合$ \ {\ hat \ phi_j,\ hat r_j \} $,并增加了点$ \ {\ min \ phi,\ min r \} $和$ \ {\ max \ phi,\ max r \} $代表未校准估计器的最小和最大可能输出以及奖励的最小和最大可能估计,定义了线性样条线$ \ psi:[\ min \ phi,\ max \ phi] \ to [\ min r, \ max r] $可以用来对未校准估计器的输出进行后处理,以改善校准效果。

现在假设事实证明不是从$ D ^ * $提取校准样本,而是从零回报子采样$ \ tilde D ^ * $提取。与上面的经验值估算器类似,该调整包括在控制点的计算中将$ r_i = 0 $的任何示例等同于$ r_i \ neq 0 $的$ 1 / l $个示例。
\ begin {aligned}
\ hat \ phi_j&\ approx \ frac {\ sum _ {\ {x_i,\ phi(x_i),r_i \}} \ left(l ^ {-1} 1_ {r_i = 0} + 1_ {r_i \ neq 0} \ right)\ phi(x_i)1_ {b_ {j-1} \ leq \ phi(x_i)\ leq b_j}} {\ sum _ {\ {x_i,\ phi(x_i),r_i \}}} left(l ^ {-1} 1_ {r_i = 0} + 1_ {r_i \ neq 0} \ right)1_ {b_ {j-1} \ leq \ phi(x_i)\ leq b_j}},\\
\ hat r_j&\ approx \ frac {\ sum _ {\ {x_i,\ phi(x_i),r_i \}} \ left(l ^ {-1} 1_ {r_i = 0} + 1_ {r_i \ neq 0} \右)r_i 1_ {b_ {j-1} \ leq \ phi(x_i)\ leq b_j}} {\ sum _ {\ {x_i,\ phi(x_i),r_i \}} \ left(l ^ {-1} 1_ {r_i = 0} + 1_ {r_i \ neq 0} \ right)1_ {b_ {j-1} \ leq \ phi(x_i)\ leq b_j}},
\ end {aligned}
\] ,然后按照上述步骤进行操作。但是,这很酷:如果您要校准估计量,则训练数据是否为零奖励二次采样且未使用重要性加权似乎并不重要。估计量最终有偏差,但是校准可以对其进行校正,并且在实践中,与重要度加权回归相比,该校准过程对较大的零奖励子采样率不敏感。例如,通过重要性加权技巧尝试$ l = 1/100 $是很危险的,但实际上在上面的校准过程中效果很好。