2012年1月6日,星期五

成本敏感型二进制分类和主动学习

现在,出现了多种针对二进制分类的主动学习算法,现在是时候问什么 机器学习减少 可以说关于其他类型学习问题的主动学习。现在,我将重点介绍对成本敏感的二进制分类,其目标是与\ [
h ^ * = \ mathop {\ operatorname {arg \,min \;}} _ {h \ in H} E _ {(X,Y,\ Upsilon)\ sim D} [\ Upsilon 1_ {h(X)\ neq Y}],
\] 其中$ X $是要素,$ Y \ in \ {0,1 \} $是标签,$ \ Upsilon \ in [0,c_ {max}] $是成本,$ D $是未知的分布。

成本可见

首先,我假设我们可以在未标记的数据中看到费用,即无需查询标签。这在实践中并不常见,因为成本通常取决于标签(例如,误报要比误报要贵)。但是,这将为可能的情况提供一些直觉。

我可以使用拒绝采样来 将对成本敏感的分类降低为二进制分类 然后应用主动学习二进制分类器。具体来说,我可以以接受概率$ \ Upsilon_k / c_ {max} $拒绝输入流的样本,如果样本被接受,它将丢弃成本并使用二进制分类。这是后悔变换,其将所引起的二进制后悔按比例缩放$ E [$]。因此,如果我们很有可能后悔在给定$ n $个示例的情况下将$ r_b(n)$绑定到基础活动二进制分类器中,则大概替换$ n \ rightarrow(E [\ Upsilon] / c_ {max})n + O( \ frac {1} {n} \ log \ frac {1} {\ delta})$并按$ E [\ Upsilon] $缩放会给我们带来很大的可能性$ r_c(n)$问题,\ [
r_c(n)= E [\ Upsilon] r_b \ left(\ frac {E [\ Upsilon]} {c_ {max}} n + O(\ frac {1} {n} \ log \ frac {1} {\ delta})\ right)。
\]
同时,在拒绝的情况下,我们绝对不会查询标签$ Y_k $。在不拒绝的情况下,我们可以查询标签$ Y_k $,具体取决于在诱导的主动二进制分类器中使用标签的可能性。如果在给定$ n $实例的情况下,在诱导二进制分类器$ l_b(n)$的标签复杂度上具有较高的概率界限,则大概替换$ n \ rightarrow(E [\ Upsilon / c_ {max})n + O (\ frac {1} {n} \ log \ frac {1} {\ delta})$将给标签复杂度$ l_c(n)$带来高的概率边界,该复杂度是原始成本敏感问题\ [
l_c(n)= l_b \ left(\ frac {E [\ Upsilon]} {c_ {max}} n + O(\ frac {1} {n} \ log \ frac {1} {\ delta})\ right )。
\] 这是一种用于主动学习的元算法,具有成本敏感的二进制分类和可见的成本。
算法: 可见成本案例
具有可见成本和主动学习二进制oracle $ \ mathcal {O} $的主动成本敏感型二进制分类的拒绝采样。
  1. 以成本$ \ Upsilon_k $获得未标记的数据点$ X_k $。
  2. 用$ \ mathrm {Pr}(\ mathrm {heads))=(\ Upsilon_k / c_ {max})$掷一个偏向硬币。
    1. 如果是正面,请将未标记的特征$ X_k $传递给$ \ mathcal {O} $。
    2. 如果有尾巴,则丢弃未标记的数据点。

如果二进制oracle使用 不受约束的不可知主动学习,这种推理暗示了类似\ [
\ mathrm {err} _c(h_n)\ leq \ mathrm {err} _c(h ^ *)+ O \ left(\ sqrt {c_ {max} E [\ Upsilon] \ frac {\ log n} {n}} \对)
\] 是可能的,其中\ [
\ mathrm {err} _c(h)= E _ {(X,Y,\ Upsilon)\ sim D} [\ Upsilon 1_ {h(X)\ neq Y}],
\] 和诸如[[
\ mbox {要求标签} \ leq 1 + \ theta \ cdot \ frac {2} {c_ {max}} \ mathrm {err} _c(h ^ *)n + O \ left(\ theta \ sqrt {\ frac { E [\ Upsilon]} {c_ {max}} n \ log n} \ right)
\] 是可能的。这里的$ \ theta $是引起的二进制子问题的分歧系数。

费用不可见

现在,我假设仅在查询标签时才可以使用成本。假设我们决定通过首先根据底层主动学习算法接受或拒绝,然后再查询标签并观察到成本$ \ Upsilon_k $,然后掷出另一枚硬币并以概率$(\ Upsilon_k接受,来实施上述拒绝抽样程序/ c_ {max})$。这将与无形成本约束相一致,但在结果方面相同。如果成本可见,这将是愚蠢的,但如果成本不可见,这是可行的策略。后悔的界限仍然是相同的,但是不幸的是,现在引起的二元问题的标签复杂度通过未经修改的$ l_c(n)= l_b(n)$。当然,标签的复杂性 游戏中的主动学习,否则我们将查询每个标签并获得金标准的被动学习后悔。因此,对于一个特定的后悔界限,具有更差的标签复杂性是非常不希望的。

算法: 无形成本案
具有不可见成本和主动学习二进制oracle $ \ mathcal {O} $的主动成本敏感型二进制分类的拒绝采样。
  1. 获取未标记的数据点$ X_k $。
  2. 将未标记的数据点$ X_k $传递到$ \ mathcal {O} $,并拦截\ {0,1 \} $中的决策$ Q_k \ in查询标签。
    1. 如果$ Q_k = 0 $,则不执行任何操作。
    2. 如果$ Q_k = 1 $,
      1. 查询标签并观察$ \ Upsilon_k $和$ Y_k $。
      2. 用$ \ mathrm {Pr}(\ mathrm {heads))=(\ Upsilon_k / c_ {max})$掷一个偏向硬币。
        1. 如果是正面,将标签$ Y_k $传递给$ \ mathcal {O} $,这在$ Q_k = 1 $时可以预期。
        2. 如果有尾巴,则丢弃标签并将$ X_k $的表示``撤消''到$ \ mathcal {O} $。

特别是对于使用不受约束的不可知主动学习的基础学习者,这种推理建议何时看不到成本,\ [
\ mbox {要求标签} \ leq 1 + \ theta \ cdot \ frac {2} {E [\ Upsilon]} \ mathrm {err} _c(h ^ *)n + O \ left(\ theta \ sqrt {n \ log n} \ right)。
\] 两种标签复杂度的比较表明,在“智能”成本敏感型主动学习算法和“智能”成本不可实现的情况下,我们可能会获得$(E [\ Upsilon] / c_ {max})$的改进。这里勾勒出的``哑巴''。

2012年1月4日,星期三

不受约束的不可知主动学习,解释

假期里我真的很喜欢 不受约束的不可知主动学习 由Beygelzimer等撰写。等,并且我对这种方法有了直觉,觉得自己很喜欢分享。

这种方法的好处是,它可以与任何可以将经验风险最小化的分类器一起使用:线性预测器,神经网络,决策树等。一致性甚至可以保证多类0-1损失(尽管标签复杂性保证不);实际上,由于重要性加权,即使您没有以上述方式精确计算采样概率(例如,Vowpal Wabbit计算近似值),一致性保证仍然成立。因此,这是一项非常实用的技术。

最佳顺序标签检查

假设我们有一些函数$ f:\ mathcal {X} \ times \ mathcal {Y} \ to [-1,1] $我们想要估计$ E_D [f(X,Y)] $,而我们没有不知道$ D $,但我们可以从中取样。将$ X $视为特征,将$ Y $视为标签,将$ f $视为告诉我们假设的良好程度的事物。因此,我们获取$ n $个样本$ Z_k =(X_k,Y_k)$并计算\ [
\ hat f_p(Z_ {1:n})= \ frac {1} {n} \ sum_ {k = 1} ^ n f(X_k,Y_k),
\] ,即经验样本均值(例如,通过 霍夫丁不等式 因为$ f $是有界的。很好,但是需要$ n $个样本,我们希望减少使用。上面的估计器类似于被动学习者,通过使用较少的样本,我们得到了主动学习者。如果我们可以通过使用较少的样本以高概率接近$ \ hat f_p $,则通过三角不等式,我们将以很高的概率接近$ E_D [f(X,Y)] $。

假设$ Q_k \ in \ {0,1 \} $是一个指示符变量,它指示是否检查集合中的特定数据点。我们将向我们展示被动学习者一次利用的$ n $样本:看到$ k ^ \ mathrm {th} $具有$ X_k $特征之后,我们将看一下所有先前的$ X_ {1:k-1} $以及之前的任何$ Y_i $,使得$ Q_i = 1 $。使用所有这些信息,我们将选择一个$ P_k$。一旦我们有了$ P_k$,我们将通过翻转带有偏倚$ P_k$的硬币来从$ Q_k $中采样。如果$ Q_k = 1 $,则我们使用$ Y_k $,否则不会显示。请注意,查看功能是免费的,因此我们始终可以在当前实例上执行此操作,但是查看标签需要付费。我们的主动估算器是\ [
\ hat f_a(Z_ {1:n})= \ frac {1} {n} \ sum_ {k = 1} ^ n \ frac {Q_k} {P_k} f(X_k,Y_k)。
\] 我们必须将我们使用的值按$ 1 / P_k$进行缩放才能无偏。希望很直观,如果$ P_k$非常小,则$ \ hat f_a $更有可能与$ \ hat f_p $相差很大,因为我们是否审查数据点会在估计(当然证明这是一个很酷的技巧,因为$ Q_k $不是iid)。但是,有一个重要警告。如果$ f(X_k,Y_k)= 0 $,则是否检查数据点无关紧要,$ P_k$是什么也无关紧要,因为估计不变。

利用漏洞是关键,因为事实证明,我们要估计其期望的功能是瞬时遗憾\ [
1_ {h(X_k)\ neq Y_k}-1_ {h ^ *(X_k)\ neq Y_k},
\] 当前经验风险最小化器\ [
\ begin {aligned}
h_n&= \ mathop {\ operatorname {arg \,min \;}} _ {h \ in H} \ hat r_a(Z_ {1:n}; h)\\
&= \ mathop {\ operatorname {arg \,min \;}} _ {h \ in H} \ frac {1} {n} \ sum_ {k = 1} ^ n \ frac {Q_k} {P_k} 1_ {h (X_k)\ neq Y_k},
\ end {aligned}
\] 和真实的最佳假设$ h ^ * = \ operatorname {arg \,min} _ {h \ in H} E_D [1_ {h ^ *(X)= Y}] $。如果我们在估计此预期后悔的错误很小,那么这意味着我们的经验最小化器将几乎与真实最小化器一样好。 请注意,在经验最小化器和真实最小化器一致的任何输入上,此函数都为零。所以理想情况下,我们将有一个方案
  1. 每当$ h_k(X_k)\ neq h ^ *(X_k)$,$ P_k $为``large''且
  2. 每当$ h_k(X_k)= h ^ *(X_k)$时,$ P_k $为``small''。
第一个条件确保我们的估算器准确无误,第二个条件确保我们正在审查不必要的数据点。

(在继续之前了解这一点)

抽样方案

假设我们消耗了$ k-1 $个样本,并根据尚未定义的某种方案对某些标签进行了审查,现在我们来看下一组特征$ X_k $。当前的经验风险最小化器为$ h_k$。显然,真正的风险最小化工具$ h ^ * $与$ X_k $上的$ h_k$不一致。假设后者:凭直觉,由于经验平均值正在收敛到其真实均值,因此我们期望\ [
\ begin {aligned}
h_k(X_k)\ neq h ^ *(X_k) &\隐含h ^ * \ in \ {h \ in H | h(X_k)\ neq h_k(X_k)\} \\
&\ mathop {\ implies} _ {\ mathrm {Pr}>1-\ delta} \ hat r_a(Z_ {1:k-1}; h ^ \ prime_k)-\ hat r_a(Z_ {1:k-1}; h_k)<O(\ frac {1} {\ sqrt {k}} \ log \ frac {1} {\ delta}),\\
h ^ \ prime_k&= \ mathop {\ operatorname {arg \,min \;}} _ {h \ in H | h(X_k)\ neq h_k(X_k)} \ hat r_a(Z_ {1:n}; h),
\ end {aligned}
\] ,即与$ X_k $上的$ h_k$不同的最佳假设$ h ^ \ prime_k $的经验风险估计几率几乎与$ h_k$一样好。这是因为
  1. $ h ^ * $是$ h ^ \ prime_k $的候选者,因此$ h ^ \ prime_k $的经验风险最多为$ h ^ * $的经验风险,并且
  2. $ h_k$的经验风险很可能会收敛到$ h ^ * $的经验风险。

相反,如果$ h ^ \ prime_k $的经验风险远比$ h_k$的经验风险差,则表明$ h_k(X_k)= h ^ *(X_k)$的可能性很高。回想点$ h_k(X_k)= h ^ *(X_k)$正是我们可以安全地检查的点,因此基本思想是更积极地检查$ h ^ \ prime_k $在经验上比$ h_k差的实例$。当然,$ P_k$的确切公式取决于偏差范围的细节,并且计算出的细节是令人印象深刻的部分,但是直觉表明$ P_k$在$ \ hat r_a中单调递减(Z_ {1:k -1}; h ^ \ prime_k)-\ hat r_a(Z_ {1:k-1}; h_k)$。


(在继续之前了解这一点)

现在这个方案没有``假阴性'',从某种意义上说,每当$ h_k(X_k)\ neq h ^ *(X_k)$时,Beygelzimer等。等高概率地安排$ P_k\ geq 1/2 $。因此,我们从估计的角度包括了``重要点'',并且在相同的数据集上,我们的主动学习者将具有与被动学习者相当的误差范围,只是主动学习者可能使用的标签明显更少。

标签复杂度

从表面上看,主动学习者可以通过两种方式频繁查询标签。
  1. (``许多要点''):如果经验最小化器$ h_k$经常不同意$ h ^ * $,则活动学习者将频繁查询标签,因为经验最小化器的期望后悔函数中有很多非零。
  2. (``许多误报''):如果$ h ^ \ prime_k $和$ h_k$之间的经验风险差异很小,即使$ h_k(X_k)= h ^ *(X_k)$,主动学习者也将无法检测到可以安全检查一个点。
经过一番反思,可以看出这些是同一根本原因的两个症状:存在许多经常接近最优假设的近乎最优的假设。

进一步探索这种见解[1],请考虑我们利用$ k ^ \ mathrm {th} $数据点的概率是$ k $的某个函数$ g $,以及经验风险最小化器$ h_k$与经验不同的风险最小化器$之间的经验误差差h ^ \ prime_k $,\ [
\ begin {aligned}
P_k&= g \ bigl(\ hat r_a(Z_ {1:k-1},h ^ \ prime_k)-\ hat r_a(Z_ {1:k-1},h_k),k \ bigr)。
\ end {aligned}
\] 如果可以绑定$ P_k$,则可以通过期望的线性度,可以将迭代$ k $使用的样本的期望数量与$ P_k$的总和绑定。

如果我们知道$ \ hat r_a(Z_ {1:k-1},h ^ \ prime_k)-\ hat r_a(Z_ {1:k-1},h_k)$的累积分布$ F_k $,那么我们可以说\ [
P_k= \int_0^1 d\gamma\; \frac{d F_k (\gamma)}{d\gamma} g (\gamma, k).
\] 可惜,此累积分布$ F_k $很难直接固定下来。谈论假设与真实最优之间的真实后悔和杠杆作用更方便 分歧系数。因此,策略是将第一个参数的下界限制为$ \ mathrm {err}(\ tilde h)-\ mathrm {err}(h ^ *)$的函数,以选择合适的$ \ tilde h $,并利用$ g $在第一个参数中减小的事实来获得$ P_k$的上限。

如果$ h_k(X_k)= h ^ *(X_k)$,那么$ h_k$的经验最优性将使我们能够使用$ \ hat r_a(Z_ {1:k-1}将第一个参数的下界限制为$ g $。 h ^ \ prime_k)-\ hat r_a(Z_ {1:k-1},h ^ *)$,之后我们可以减去$ O(\ frac {1} {\ sqrt {k}} \ log \ frac {1} {\ delta})$到经验误差差,以基于真实误差差$ \ mathrm {err}(h ^ \ prime_k)-\ mathrm {err}(h ^ *)获得高概率下限$,因此获得了$ g $的上限,因为两个参数都使$ g $减小。如果$ h ^ \ prime_k(X_k)= h ^ *(X_k)$,则推理更为复杂但类似,最终结果是通过选择\ [
\tilde h_k=
\ begin {cases}
h_k&\mathrm{if}\; h_k(X_k)\ neq h ^ *(X_k) \\
h ^ \ prime_k&\mathrm{if}\; h ^ \ prime_k(X_k) \neq h^* (X_k)
\ end {cases},
\] ,然后$ P_k $可以被\ [
P_k\leq \tilde g \bigl(\mathrm{err} (\tilde h_k) - \mathrm{err} (h^*), k \bigl),
\] 稍微不同的$ \ tilde g $,这两个参数也都在减少。

现在我们关注的累积分布是$ \ mathrm {Pr}(\ mathrm {err}(\ tilde h_k)-\ mathrm {err}(h)\ leq \ gamma)$,上限看起来像\ [
\ begin {aligned}
P_k&\ leq \ int_0 ^ 1 d \ gamma \; \ frac {d \ mathrm {Pr}(\ mathrm {err}(\ tilde h_k)-\ mathrm {err}(h)\ leq \ gamma)} {d \ gamma} \ tilde g(\ gamma,k)\ \
&= \ tilde g(1,k)-\ int_0 ^ 1 d \ gamma \; \ mathrm {Pr}(\ mathrm {err}(\ tilde h_k)-\ mathrm {err}(h)\ leq \ gamma)\ frac {d \ tilde g(\ gamma,k)} {d \ gamma} \ \
&= \ tilde g(1,k)+ \ int_0 ^ 1 d \ gamma \; \ mathrm {Pr}(\ mathrm {err}(\ tilde h_k)-\ mathrm {err}(h)\ leq \ gamma)\ left | \ frac {d \ tilde g(\ gamma,k)} {d \ gamma} \ right | \\
\ end {aligned}
\] 第二行是按部分积分(!!),第三行使用$ \ tilde g $在第一个参数中递减的事实。

下一步是绑定$ \ mathrm {Pr}(\ mathrm {err}(\ tilde h_k)-\ mathrm {err}(h)\ leq \ gamma)$。如果$ \ mathrm {err}(\ tilde h_k)-\ mathrm {err}(h ^ *)\ leq \ gamma $,则在最坏的情况下,$ \ tilde h_k$在所有情况下都是正确的,其中$ h ^ * $会产生错误,并且可能另外产生$ \ mathrm {err}(h ^ *)+ \ gamma $错误,并且仍然会后悔$ \ gamma $,即\ [
\ mathrm {Pr}(\ tilde h_k(X_k)\ neq h_k^ *(X_k))\ leq 2 \ mathrm {err}(h ^ *)+ \ gamma。
\] 但是,对于我们的$ \ tilde h_k$,实际上确实发生了这种情况(返回并查看定义!)。在这一点上,我们可以利用 分歧系数 $ \ theta $限制了选择存在某些后悔假设的输入的概率,\ [
\ mathrm {Pr}(X \ in \ {x \ mid \ exists h \:\ mathrm {st} \; h(x)\ neq h ^ *(x)\ land \ mathrm {err}(h)-\ mathrm {err}(h ^ *)\ leq r \})\ leq \ theta r。
\] 因此,\ [
\ mathrm {Pr}(\ mathrm {err}(\ tilde h_k)-\ mathrm {err}(h)\ leq \ gamma)\ leq \ theta(2 \ mathrm {err}(h ^ *)+ \ gamma) ,
\] 代入界限得到\ [
P_k\ leq \ tilde g(1,k)+ 2 \ theta \; \ mathrm {err}(h ^ *)\ left(\ int_0 ^ 1 d \ gamma \; \ left | \ frac {d \ tilde g(\ gamma,k)} {d \ gamma} \ right | \ right) + \ theta \ int_0 ^ 1 d \ gamma \; \ gamma \ left | \ frac {d \ tilde g(\ gamma; k)} {d \ gamma} \ right |。
\] 现在从我的论述中还不清楚,但是事实证明,这是使用的$ \ tilde g $,\ [
\ begin {aligned}
\ left(\ int_0 ^ 1 d \ gamma \; \ left | \ frac {d \ tilde g(\ gamma,k)} {d \ gamma} \ right | \ right)&\ leq 1 + O \ left(\ sqrt {\ frac {\ log k} {k-1}} \ right),\\
\ int_0 ^ 1 d \ gamma \; \ gamma \ left | \ frac {d \ tilde g(\ gamma; k)} {d \ gamma} \ right |&\ leq O \ left(\ frac {\ log ^ 2 k} {k-1} \ right)。
\ end {aligned}
\] 好消息和坏消息:
  1. 坏消息(无法实现):如果$ \ mathrm {err}(h ^ *)>0 $,在最坏的情况下,我们将以与$ \ mathrm {err}(h ^ *)$成正比的采样率进行平衡。虽然令人失望, 这个限制似乎很重要.
  2. 好消息:如果$ \ mathrm {err}(h ^ *)= 0 $,我们大致利用$(\ sqrt {n / \ log n})$作为被动学习者的数据点数。不是指数级的加速,而是比眼前的锐利棒好。
如果对假设空间的结构进行进一步假设,则甚至可能具有更好的标签复杂性范围。

[1] 到此为止,解释变得不那么``直观''了。我认为这是我也不太了解的标志。我会尽力保持清晰度。

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 $是经验最小化假设和真实风险最小化假设之间的瞬时遗憾,因此我必须加倍努力,并理解诸如 分歧系数。我怀疑合并该标签将使我能够利用一种假设,即在上述分析中,一个标签比另一个标签的流行程度高得多,我认为这是至关重要的。