假期里我真的很喜欢
不受约束的不可知主动学习 由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}] $。如果我们在估计此预期后悔的错误很小，那么这意味着我们的经验最小化器将几乎与真实最小化器一样好。
请注意，在经验最小化器和真实最小化器一致的任何输入上，此函数都为零。所以理想情况下，我们将有一个方案
- 每当$ h_k（X_k）\ neq h ^ *（X_k）$，$ P_k $为``large''且
- 每当$ 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$一样好。这是因为
- $ h ^ * $是$ h ^ \ prime_k $的候选者，因此$ h ^ \ prime_k $的经验风险最多为$ h ^ * $的经验风险，并且
- $ 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 $。因此，我们从估计的角度包括了``重要点''，并且在相同的数据集上，我们的主动学习者将具有与被动学习者相当的误差范围，只是主动学习者可能使用的标签明显更少。
标签复杂度
从表面上看，主动学习者可以通过两种方式频繁查询标签。
- （``许多要点''）：如果经验最小化器$ h_k$经常不同意$ h ^ * $，则活动学习者将频繁查询标签，因为经验最小化器的期望后悔函数中有很多非零。
- （``许多误报''）：如果$ 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}
\] 好消息和坏消息：
- 坏消息（无法实现）：如果$ \ mathrm {err}（h ^ *）>0 $，在最坏的情况下，我们将以与$ \ mathrm {err}（h ^ *）$成正比的采样率进行平衡。虽然令人失望， 这个限制似乎很重要.
- 好消息：如果$ \ mathrm {err}（h ^ *）= 0 $，我们大致利用$（\ sqrt {n / \ log n}）$作为被动学习者的数据点数。不是指数级的加速，而是比眼前的锐利棒好。
如果对假设空间的结构进行进一步假设，则甚至可能具有更好的标签复杂性范围。
[1] 到此为止，解释变得不那么``直观''了。我认为这是我也不太了解的标志。我会尽力保持清晰度。
