显示带有标签的帖子 主动学习. 显示所有帖子
显示带有标签的帖子 主动学习. 显示所有帖子

2012年5月16日,星期三

主动最小极大值预报

这是我的延续 以前的帖子 我注意到Minimax Forecaster从积极学习的角度着迷。幸运的是,我注意到Abernethy等人的一篇论文。等叫 通过极大极小对偶性的最佳后悔随机视图。本文作者利用杠杆作用以一般方式解开在线凸优化 冯·诺依曼的极小极大定理。通过这样做,他们得出了在线游戏对对手的价值的一般公式。前一篇文章的直觉是,观察和不观察特定结果之间的游戏价值差异将是在对抗环境中做出主动学习决策的关键,因此该公式非常有趣。

Abernethy等。等首先从比上一篇文章更通用的设置入手,但是我将把它们的约定适应于上一篇文章中存在差异的地方。有一个带有$ T $回合的游戏。有一组$ \ mathcal {F} $专家。在每个回合中,每个专家$ f $产生一个预测$ f_t $,玩家产生一个预测$ p_t $,对手同时产生一个结果$ y_t $,并且玩家遭受瞬时损失$ l(p_t,y_t)$。专家是静态的(他们的预测不依赖于先前观察到的结果),因此基本上每个专家都是一个序列$ f_ {1:T} $。玩家想要生成一系列预测$ p_ {1:T} $,以最大程度地减少最坏的后悔\ [
\ sup_ {y_ {1:T} \ in \ mathcal {Y} ^ T} L(p_ {1:T},y_ {1:T})-\ inf_ {f \ in \ mathcal {F}} L( f_ {1:T},y_ {1:T}),
\] 其中$ L(p_ {1:T},y_ {1:T})= \ sum_s l(p_s,y_s)$是总损失。 (为简化表示法,除非括号中明确限制,否则极值和极小值将捕获整个表达式的其余部分。)上一篇文章的Minimax Forecaster是该问题特定情况的明确解决方案,而Abernethy等人。等通常关注表征此类游戏。他们考虑最佳玩法下游戏对对手的价值,\ [
\ begin {aligned}
R ^ *(\ mathcal {F})&= \ inf_ {p_1 \ in \ mathcal {P}} \ sup_ {y_1 \ in \ mathcal {Y}} \ ldots \ inf_ {p_T \ in \ mathcal {P}} \ sup_ {y_T \ in \ mathcal {Y}} \ sum_ {t = 1} ^ T l(p_t,y_t)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l (f_t,y_t)。
\ end {aligned}
\] 令人惊奇的结果是,这与\ [
\ begin {aligned}
R ^ *(\ mathcal {F})&= \ sup_ {Y \ in \ mathbb {P}(\ mathcal {Y} ^ T)} \ mathbb {E} _ {y_ {1:T} \ sim Y} \ left [\ sum_ {t = 1} ^ T \ inf_ {p_t \ in \ mathcal {P}} \ biggl(\ mathbb {E} _ {\ tilde y_t} \ left [l(p_t,\ tilde y_t)| y_ {1:t-1} \ right] \ biggr)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l(f_t,y_t)\ right],
\ end {aligned}
\] ,其中最高值超过结果序列$ \ mathbb {P}(\ mathcal {Y} ^ T)$的分布。换句话说,这看起来像是在遗忘(非平稳)环境下玩的游戏,但是却在最恶劣的环境下玩。这是一个不错的结果,并导致随后的工作 在IID和对抗设置之间进行插补 通过限制序列分布上的最高点。

现在通过积极学习,我们选择不观察某些结果(由变量$ z_s \ in \ {0,1 \} $表示),从而使对手更加强大。我可以将游戏价值的上限设为\ [
\ begin {aligned}
R ^ *(\ mathcal {F} | z_ {1:T})&\ leq \ sup_ {Y \ in \ mathbb {P}(\ mathcal {Y} ^ T)} \ mathbb {E} _ {y_ { 1:T} \ sim Y} \ left [\ sum_ {t = 1} ^ T \ inf_ {p_t \ in \ mathcal {P}} \ biggl(\ mathbb {E} _ {\ tilde y_t} \ left [l (p_t,\ tilde y_t)| \ Omega_ {t-1} \ right] \ biggr)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l(f_t,y_t)\对],
\ end {aligned}
\] 其中$ \ Omega_t = \ {y_s | s \ leq t,z_s = 1 \} $表示观察到的结果。这是直观上令人愉悦的,因为内部条件期望值表示玩家的知识。要导出上限,请按照本文附录A中的过程进行操作,只要从\ [
\ inf_ {p_1 \ in \ mathcal {P}} \ sup_ {y_1 \ in \ mathcal {Y}} \ cdots \ inf_ {p_s \ in \ mathcal {P}} \ sup_ {y_s \ in \ mathcal {Y}} \ cdots \ inf_ {p_T \ in \ mathcal {P}} \ sup_ {y_T \ in \ mathcal {Y}} \ sum_ {t = 1} ^ T l(p_t,y_t)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l(f_t,y_t),
\] 至 \[
\ inf_ {p_1 \ in \ mathcal {P}} \ sup_ {y_1 \ in \ mathcal {Y}} \ cdots \ inf_ {p_s \ in \ mathcal {P}} \ cdots \ inf_ {p_T \ in \ mathcal {P }} \ sup_ {y_T \ in \ mathcal {Y}} \ sup_ {y_s \ in \ mathcal {Y}} \ sum_ {t = 1} ^ T l(p_t,y_t)-\ inf_ {f \ in \ mathcal {F}} \ sum_ {t = 1} ^ T l(f_t,y_t),
\] ,即让对手将未观察到的值的选择推迟到游戏结束。这只是一个上限,因为实际上对手必须在$ s $轮中选择$ s $的结果,所以我可能对对手过于慷慨。

极小极大预报

如果我们在与边界相关联的广泛形式游戏中设计Minimax Forecaster,则会得到优化边界的算法。考虑这样一种情况,其中观察到除了舍入$ s $之外的所有结果。重复原始minimax预报器论文中的向后归纳步骤,得到表达式\ [
\ begin {aligned}
p_t ^ *&= \frac{1}{2} \biggl( 1 - R^* (\mathcal{F}, y_{1:t-1}0 | z_s = 0) + R^* (\mathcal{F}, y_{1:t-1}1 | z_s = 0) \biggr). & (t > s)
\ end {aligned}
\] 和\ [
\ begin {aligned}
&R ^ *(\ mathcal {F},y_ {1:t} | z_s = 0)\\
&= \frac{T - t}{2} + \mathbb{E}_{\sigma_{t+1:T}}\left[ \sup_{y_s \in \mathcal{Y}} |p_s - y_s| - \inf_{f \in \mathcal{F}} L (f_{1:T}, y_{1:t} \sigma_{t+1:T}) \right] & (t > s) \\
&= R ^ *(\ mathcal {F},y_ {1:t})\\
&\ quad + \ mathbb {E} _ {\ sigma_ {t + 1:T}} \ left [\ left | p_s-\ frac {1} {2} \ left(1 + \ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1:T},y_ {1:s-1} 0 \ sigma_ {s + 1:T})\ right)-\ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1:T},y_ {1:s-1} 1 \ sigma_ {s + 1:T})\ right)\ right)\ right | \对]。
\ end {aligned}
\] 因此,玩过$ p_s $且未观察到结果$ s $的剩余游戏价值等于完全观测到的剩余游戏价值加上与所有Rademacher分布播出的平均预期平均损失有关的罚款。这意味着$ p_s $的最佳选择是中位数\ [
\ begin {aligned}
p_s ^ *&= \ mathop {\ operatorname {median}} \ left(\ frac {1} {2} \ left(1 + \ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1 :T},y_ {1:s-1} 0 \ sigma_ {s + 1:T})\ right)-\ inf_ {f \ in \ mathcal {F}} \ left(L(f(f_ {1:T} ,y_ {1:s-1} 1 \ sigma_ {s + 1:T})\ right)\ right)\ right)。
\ end {aligned}
\] 在$ s $和$ T $之间没有额外的下注游戏的情况下,分布中只有一个点,因此中位数是该点,因此最佳下注游戏$ p_s ^ * $与在充分观察的情况下。在$ s $和$ T $之间还有一轮下注的情况下,分布中有两个点,因此均值是中位数,并且最佳下注$ p_s ^ * $与上一遍相同。完全观察到的游戏(与以前的博客文章一致)。在$ s $和$ T $之间有多于一轮的比赛时,平均值不一定是中位数(即,不必将预期的绝对损失最小化),因此最佳比赛$ p_s ^ * $是不同的。也许这就是为什么Mathematica在我尝试解决更长版本的未观察到的游戏时``扑出''的原因。

一旦我们``跳过''了未观察到的点并确定了$ p_s ^ * $,我们就可以继续向后归纳;但我认为有趣的一点是惩罚术语,它表示在给定所有先前和之后的回合的情况下,在$ s $处观察结果的价值,\ [
\ mathbb {E} _ {\ sigma_ {t + 1:T}} \ left [\ left | p_s-\ frac {1} {2} \ left(1 + \ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1:T},y_ {1:s-1} 0 \ sigma_ {s + 1:T})\ right)-\ inf_ {f \ in \ mathcal {F}} \ left(L(f_ {1:T},y_ {1:s-1} 1 \ sigma_ {s + 1:T})\ right)\ right)\ right | \对]。
\] 这个惩罚条款对于决定是否在$ s $轮查询结果非常重要。最好将其推广到未观察到某些先前结果的情况,以及涉及可能未观察到的未来结果的情况。当然,计划后者可能会成倍地困难。

为了使之可行,如果可以廉价且准确地估计出中位数和预期的绝对损失,例如使用随机播放,那将是很好的。同样也许决定是否要查询结果要在游戏价值界限上进行,例如,假设将观察所有后续观察,而不是考虑观察结果的未来决定。此外,该技术从根本上仍是可转导的,因为需要知道对规划范围$ f_ {1:T} $的专家预测。然而,即使有所有这些警告,例如在推荐系统中也可能有一个有趣的应用。



































2012年5月6日,星期日

Minimax预报器和超导主动学习

我一直在NIPS 2011论文清单上走下坡路,发现这份不错的论文 通过随机舍入进行有效的在线学习 由Cesa-Bianchi和Shamir撰写。本文是关于改进和扩展Minimax Forecaster的,在 预测,学习和游戏。 (我拥有一份副本,但我承认没有到那本书中走得太远。)Minimax Forecaster使用不同于在线学习的策略来进行在线学习。 镜面下降 实际上,这是我(以及其他所有人?)每天使用的内容。这种不同的设置提供了思考对抗性主动学习的机会。

这是基本设置。有一个带有$ T $回合的游戏。有一组$ \ mathcal {F} $专家。在每个回合中,每个专家$ f $产生一个预测$ f_t $,玩家产生一个预测$ p_t $,对手同时产生一个结果$ y_t $,并且玩家遭受瞬时损失$ l(p_t,y_t)$。专家是静态的(他们的预测不依赖于先前观察到的结果),因此基本上每个专家都是一个序列$ f_ {1:T} $。玩家想要生成一系列预测$ p_ {1:T} $,以最大程度地减少最坏的后悔\ [
\ sup_ {y_ {1:T} \ in \ mathcal {Y} ^ T} \ biggl(L(p_ {1:T},y_ {1:T})-\ inf_ {f \ in \ mathcal {F} } L(f_ {1:T},y_ {1:T})\ biggr),
\] 其中$ L(p_ {1:T},y_ {1:T})= \ sum_s l(p_s,y_s)$是总损失。当观察值为二进制$ \ mathcal {Y} = \ {0,1 \} $时,$ | p_t-y_t | $的瞬时损失对应于玩家随机决策时的预期0-1损失。令人惊讶的是,这种情况为最佳预测\ [
\ begin {aligned}
p ^ * _ t&= \ frac {1} {2} \ biggl(1 + R ^ *(\ mathcal {F},y_ {1:t-1} 1)-R ^ *(\ mathcal {F}, y_ {1:t-1} 0)\ biggr)\\
&= \ frac {1} {2} \ biggl(1 + \ mathbb {E} _ {\ sigma_ {t + 1:T}} \ left [\ inf_ {f \ in \ mathcal {F}} L(f_ {1:T},y_ {1:t-1} 0 \ sigma_ {t + 1:T})-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:T},y_ {1 :t-1} 1 \ sigma_ {t + 1:T})\ right] \ biggr),
\ end {aligned}
\] ,其中时间序列级联用词法表示,$ \ sigma_t $是$ \ mathrm {Bournelli}(1/2)$ Rademacher平均值,和$ R ^ *(\ mathcal {F},y_ {1:t})$是经过几轮游戏后的剩余游戏价值,\ [
\ begin {aligned}
R ^ *(\ mathcal {F},y_ {1:t})&= \ frac {1} {2} \ biggl(1 + R ^ *(\ mathcal {F},y_ {1:t-1} 0)+ R ^ *(\ mathcal {F},y_ {1:t-1} 1)\ biggr)\\
&= \ frac {T-t} {2}-\ mathbb {E} _ {\ sigma_ {t + 1:T}} \ left [\ inf_ {f \ in \ mathcal {F}} L(f_ {1 :T},y_ {1:t} \ sigma_ {t + 1:T})\ right]。
\ end {aligned}
\] 本质上,这里发生的事情是,玩家可以通过玩一个常数加上与玩每个选项相关的剩余游戏值之间的差,使对手在每一轮中都不会玩该选项。这将导致剩余游戏价值为常数加上在玩完每个选项后继续的平均值。递归解开游戏价值会导致Rademacher风格平均值。本文的一个观察结果是,可以通过采样来获得这种期望值,以实现高概率的后悔界限,也就是随机播放。

实际上,即使要进行随机播放,您也需要了解各种专家的$ f_ {1:T} $。将其映射到上下文预测设置时,这对应于提前知道特征序列(但不知道标签)。因此,这本质上是一种转导技术。一些推荐问题自然是转导性的,因此本文讨论了在协作过滤中的应用。

主动学习?

原则上可以修改设置以考虑主动学习。每个回合中,除了产生预测外,玩家还必须做出决定$ z_t \ in \ {0,1 \} $是否遵守$ y_t $。如果$ z_t = 0 $,则玩家无法在后续预测中使用$ y_t $的值。由于玩家观察$ y_t $总是更好,因此必须要付出一定的代价,因此每次观察都要考虑恒定的惩罚$ \ alpha $。玩家想要生成一系列预测$ p_ {1:T} $并查询$ z_ {1:T} $,这可以使\ mathcal {Y中的最坏情况后悔\ [\ sup_ {y_ {1:T} \ } ^ T} \ biggl(\ sum_s \ alpha z_s + L(p_ {1:T},y_ {1:T})-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:T} ,y_ {1:T})\ biggr)。
\] 到目前为止,简明的通用闭式表达式使我难以理解,但是有一个平凡的案例可以得出很好的答案:两回合博弈。

观察最终结果$ y_T $从来没有任何意义,因此$ z_T = 0 $。然后,在两轮游戏中,问题是是否观察$ y_1 $。如果未观察到$ y_1 $(即$ z_1 = 0 $),则玩家必须在没有中间反馈的情况下弹道计划两个预测。
\ begin {aligned}
(p_1 ^ *,p_2 ^ *)&= \ mathop {\ operatorname {arg \,inf}} \ limits_ {p_ {1:2} \ in \ mathcal {P} ^ 2} \ sup_ {y_ {1:2 } \ in \ mathcal {Y} ^ 2} \ left(| p_1-y_1 | + | p_2-y_2 |-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_ {1 :2})\ right)。
\ end {aligned}
\] 可以用Mathematica解决:这是咒语。
Minimize[{ z, 
           p1 + p2 - inf00 <= z, 
           p1 + (1 - p2) - inf01 <= z, 
           (1 - p1) + p2 - inf10 <= z, 
           (1 - p1) + (1 - p2) - inf11 <= z }, 
           { p1, p2, z }] // Simplify
这有解决方案\ [
\ begin {aligned}
p_1 ^ *&= \ frac {1} {2} \ left(1 + \ frac {1} {2} \ sum_ {y_2 = 0} ^ 1 \ left(\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},0y_2)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},1y_2)\ right)\ right)&(z_1 = 0),\\
p_2 ^ *&= \ frac {1} {2} \ left(1 + \ frac {1} {2} \ sum_ {y_1 = 0} ^ 1 \ left(\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_10)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_11)\ right)\ right)&(z_1 = 0),
\ end {aligned}
\] 具有游戏价值\ [
\ begin {aligned}
&R(\ mathcal {F},\ emptyset | z_1 = 0)\\
&= 1-\ frac {1} {2} \ min \ left \ {\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},00)+ \ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},11),\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},01)+ \ inf_ {f \ in \ mathcal {F }} L(f_ {1:2},10)\ right \}。 \\
\ end {aligned}
\] 现在将其与$ z_1 = 1 $的情况进行比较,这与完全观察到的Minimax Forecaster相同。 \ [
\ begin {aligned}
p_1 ^ *&= \ frac {1} {2} \ left(1 + \ frac {1} {2} \ sum_ {y_2 = 0} ^ 1 \ left(\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},0y_2)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},1y_2)\ right)\ right)&(z_1 = 1),\\
p_2 ^ *&= \ frac {1} {2} \ left(1 + \ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_10)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},y_11)\ right)&(z_1 = 1)。
\ end {aligned}
\] 无论$ z_1 = 0 $还是$ z_1 = 1 $,第一轮预测$ p_1 ^ * $都是相同的,但是第二轮预测$ p_2 ^ * $是不同的。如果$ z_1 = 0 $,则通过对可能的历史记录取平均值来计算$ p_2 ^ * $;而如果$ z_1 = 1 $,则$ p_2 ^ * $是使用实际观察到的历史进行计算的。 (此外:也许恒定时间的Radacher平均数将成为量子计算的杀手级应用。)

为了决定是否观察$ y_1 $,我们需要知道这样做有多好,即游戏价值的差异。当$ z_1 = 1 $时,这与完全观察到的Minimax Forecaster相同,\ [
\ begin {aligned}
&R(\ mathcal {F},\ emptyset | z_1 = 1)\\
&= 1-\ frac {1} {4} \ left(\ inf_ {f \ in \ mathcal {F}} L(f_ {1:T},00)+ \ inf_ {f \ in \ mathcal {F} } L(f_ {1:T},01)+ \ inf_ {f \ in \ mathcal {F}} L(f_ {1:T},10)+ \ inf_ {f \ in \ mathcal {F}} L (f_ {1:T},11)\ right),
\ end {aligned}
\] 因此游戏价值的差异为\ [
\ begin {aligned}
&R ^ *(\ mathcal {F},\ emptyset | z_t = 0)-R ^ *(\ mathcal {F},\ emptyset | z_t = 1)\\
&= \ frac {1} {4} \ left | \ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},00)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},01)-\ left (\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},10)-\ inf_ {f \ in \ mathcal {F}} L(f_ {1:2},11)\ right )\ right |。 \\
\ end {aligned}
\] 看起来像是将来差异的差异。如果游戏价值差超过$ \ alpha $,那么我们应该确定$ z_1 = 1 $,否则。因此,例如,如果每个专家都在第一轮中预测相同的值,则未来差异之差将为零,我们不应观察到$ y_1 $。这听起来确实像是主动学习。

那么一般情况下的$ T $圆形解决方案应该是什么样的呢?凭直觉,人们希望,如果过去做得好的所有专家都在当前实例上预测同一件事,那么观察该实例的$ y_t $的价值将下降。这大致就是不可知主动学习在IID设置中所做的事情。在这里,未来也很重要,但是类似地,如果所有在最后阶段进行角逐的专家都同意一个值,那么观察$ y_t $的价值就应该更少。当我们接近规划阶段的末期时,这主要是由过去的出色表现所驱动。

2012年4月25日,星期三

选择性分类与主动学习

El-Yaniv和Wiener的一篇论文中有一颗宝石 不可知选择分类。本文的重点是选择性分类是主动学习的测试时间模拟。

在选择性分类中,分类器可以选择拒绝输入并放弃预测。在实现高分类精度的同时,很少会拒绝这种想法。这是 多目标优化,所以一个 帕累托边疆 出现,称为 风险覆盖曲线 在这种情况下。

可以将其形式化如下:选择性分类器是一对$(h,g)$函数$ g:X \ to \ {0,1 \} $和$ h:X \ to Y $,其中$ g $指示是否拒绝输入,如果接受输入,$ h $是分类规则,\ [
(h,g)(x)= \ begin {cases} \ mathrm {reject}& \mathrm{if}\;g(x)= 0,\\ h(x)和\ mathrm {否则} \ end {cases}。
\] 假设$ h $来自集合$ \ mathcal {H} $;该论文对于我们要与之竞争$ g $的设置尚不清楚,但最终它们的最优性概念较弱,因此无关紧要。特征$ X $和标签$ Y = \ {0,1 \} $根据$ D $联合分配。在被动批处理设置中,有人将一袋数据(例如i.i.d)交给我们。从$ D $和拒绝预算$ b $,然后我们必须产生一对$(h,g)$,理想情况下,该对是靠近Pareto边界\ [
\ begin {aligned}
\ mathop {\ operatorname {arg \,min \,}} \ limits_ {h \ in \ mathcal {H}} \ mathbb {E} _ {(x,y)\ sim D}&[1_ {g(x) = 1} 1_ {h(x)\ neq y}] \\
&\ mathrm {s.t。} \\
E _ {(x,y)\ sim D}&[1_ {g(x)= 1}] \ leq b。
\ end {aligned}
\] 这真的很难,所以El-Yaniv和Wiener考虑了另一个问题。令$ h ^ * = \ mathop {\ operatorname {arg \,min \,}} _ {h \ in \ mathcal {H}} \ mathbb {E} _ {(x,y)\ sim D} [1_ { h(x)\ neq y}] $是最佳分类器。对$(h,g)$称为a 弱最优 如果\ [
\ mathbb {E} _ {(x,y)\ sim D} [1_ {g(x)= 1} 1_ {h(x)\ neq y}] \ leq \ mathbb {E} _ {(x,y )\ sim D} [1_ {g(x)= 1} 1_ {h ^ *(x)\ neq y}],
\] ,即在选择分类器接受的输入空间区域中,它的表现至少与最优假设相同。这不如帕累托边境上的存在,但是比尖锐的棍棒要好!

现在是漂亮的部分。作者表明,可以(如下所示)构造弱最优的选择性分类器(概率很高)。令$ \ tilde h $为经验风险$ R(h)$的最小值,并通过\ [定义$ x $的经验不一致假设。
h'_x \ doteq \ mathop {\ operatorname {arg \,min \,}} \ limits _ {\ substack {h \ in \ mathcal {H},h(x)\ neq \ tilde h(x)}} R( H)。
\] 然后 怀疑指数 是经验风险$ R(h'_x)-R(\ tilde h)$与由[[
g(x)= 0 \ iff R(\ tilde h_x)-R(\ tilde h)\ leq \ Delta
\] 是弱最优的,其中$ \ Delta $是训练集大小,VC维度$ \ mathcal {H} $和概率约束$ \ delta $的函数。换句话说,如果不同意当前输入的经验最小化器在经验上并不昂贵,则拒绝对输入进行分类,否则根据经验最小化器进行分类。

如果看起来很熟悉,那是因为难以置信指数等于 阿尔威特 在确定查询标签的可能性时。这在训练时``寻求标签''和测试时``拒绝预测''之间建立了令人愉快的对应关系。

这也表明 Vowpal兔子 可以轻松地用作选择性分类器,因为它已经为主动学习目的计算了难以置信指数的快速近似值。

2012年4月22日,星期日

主动学习,漂移分布

我们现在有一个好主意该怎么做 IID设置中不可知论的主动学习.  在IID设置和完全对抗设置之间,存在环境随时间变化但忽略了我们的学习算法的情况。 这是刘洋最近发表的一篇论文的主题 主动学习,漂移分布.

被动学习与漂移分布


我对分布漂移的被动学习还不够熟悉,因此我不得不花一些时间来引用其中一项: 论漂移分布学习的复杂性 由Barve和Long撰写。

在IID设置中的被动学习中,我们可以通过经验平均值任意获得对真实期望的良好估计。这意味着对于有限VC维的假设集,我们很有可能在有足够数据的情况下任意接近最优值。

一旦世界开始随时间变化,我们可能或可能没有足够的信息来跟踪变化。 这里有多种建模选择可以形式化地描述世界的漂移方式,包括不常发生的大变化,以及方向和速度缓慢变化的大变化。 Barve和Long研究了世界变化缓慢的情况。  特别是,世界生成了可计数的训练数据序列,该序列由特征标签对$(X \ times Y)^ {\ mathbb {N}} $组成。 这些样本是独立的,但分布不同,并且$ D_t $表示$(x_t,y_t)$的分布。 $ D_t $通过总变化距离\ [
\ sup_U | D_t(U)-D_ {t + 1}(U)| \ leq \ gamma,
\] 其中$ U $遍及所有可测量事件,例如,对于可以分配概率的任何事物,连续分布$ D_t $和$ D_ {t + 1} $分配的概率最多相差$ \ γ$。 在这种情况下,如果世界要发生重大变化,则必须向我们提供与中间状态相关的训练数据,这样学习算法才能成功。 Barve和Long表明不可知论学习的充分条件是\ [
\ gamma = O \ bigl(\ frac {\ epsilon ^ 3} {d \ ln(1 / \ epsilon)} \ bigr)。
\] 其中$ d $是假设集的VC维,而$ \ epsilon $是我们的目标遗憾。 这是通过在最新示例的窗口上执行ERM来实现的,其中窗口大小由$ \ epsilon $和$ \ gamma $确定。 由于时间$ t $的后悔是相对于$ D_t $的,所以这是一个非常酷的结果。 请注意,$ X $和$ Y $的联合分布允许随时间变化,因此输入要素的分布和 有条件的标签密度(``概念'')正在变化。

不幸的是,这个结果表明我们无法使用无限的数据来任意准确。 事后看来,这并不奇怪,因为即使数据量不受限制,我们也仅将最近的历史记录用于我们的ERM。 分母中没有$ \ ln(1 / \ epsilon)$项的伴随必要条件表明此限制是基本的,而不仅仅是``窗口式ERM''策略的产物。

回到主动学习


回到刘洋,第一个观察是上述``慢漂''的假设不足以进行主动学习。 在主动学习中,我们要丢弃一些(大多数!)标签,这相当于加快世界发展速度(缩放$ \ gamma $)。 特别是,如果我们想被邀请参加“主动学习俱乐部”的VIP部分,我们真的希望获得一个亚线性的标签复杂性,就像使用$ \ gamma \ to \ infty $进行被动学习一样,我们从上面可以看出,这基本上没有准确性。 (但是,由于线性标签的复杂性是IID情况下不可知论主动学习的最坏情况下限,因此上面的``缓慢漂移''条件可能仍然值得研究。)

相反,Yang假定各种$ D_t $是从一组分布彼此接近的分布$ \ mathbb {D} $中得出的。 通过$ \ mathbb {D} $的最小$ \ epsilon $ -cover $ \ mathbb {D} _ {\ epsilon} $形式化,定义为$ \ mathbb {D} $的最小子集,在$ $ \ mathbb {D} $的任何成员的\ epsilon $,以总变化距离来衡量。 特别是,Yang假定$ \ forall \ epsilon>0,| \ mathbb {D} _ {\ epsilon} ||<\ infty $,并假设$ \ forall \ epsilon得到更精确的边界>0,| \ mathbb {D} _ \ epsilon |<c \ cdot \ epsilon ^ {-m} $对于某些常数$ c,m \ in [0,\ infty)$。

本质上,Yang不允许世界随时间任意改变,而是将世界限制在以有限的一组原型分布为特征的分布空间区域内反弹。 为了达到一定的准确性,我们只需要考虑原型分布之间的差异,这反过来表明,在合适的条件下,我们最终将积累足够的信息,我们可以放弃一些标签。

Yang进一步限制了给定要素的标签的条件分布是固定的,并且仅允许要素的分布随时间变化。 第二个假设意味着谈论可实现的情况是有意义的,在可实现的情况下,称为 CAL 如果(最大)漂移,则在这种漂移环境中实现亚线性错误边界和标签复杂性 分歧系数 足够小。 CAL的快速总结是,它仅在存在可以预测每个标签的经验完美假设的情况下才查询标签。否则,它会推断出未观察到的标签是与其余经验完美假设相关联的标签。 CAL使用了整个历史记录,但是利用可实现性取得了成功,并注意条件分布(因此可实现性)在这里是恒定的。

在扩展可实现的分析之后,Yang接下来考虑严格良性的噪声情况,定义为存在一个最佳假设,该假设在条件上总是正确而不是不正确(对于$ \ mathbb {D} $中的所有分布)。 在这种情况下,称为ACAL的CAL不可知变量将实现亚线性错误界限和标签复杂性。 像CAL一样,ACAL会推断标签,但是这样做是通过误差差异而不是要求经验完善。 在Yang的论文中,ACAL使用窗口化数据,其中周期性地丢弃所有历史记录,并且窗口大小以几何方式增加,但这不是由于漂移引起的;而是由于ACAL的标准规格假定了特定的标签预算,所以在线设置了无限制的流。 因此ACAL有效地使用了``所有数据''。

一些外卖

本文(和讨论的引文)帮助我认识到,如果环境在某种程度上受到全球环境变化的限制,那么在不断变化的环境中进行主动学习只会``有效''(从标签复杂性的角度来看)。

本文举例说明的一种研究策略是,针对IID案例采用现有的主动学习算法,并将其适应于某种世界漂移模型。 我当然想看 阿尔威特 这样处理:说起来容易做起来难! 将AALwC与Barve和Long进行混搭将建议在最近的数据窗口上运行AALwC,并且在窗口填满后不增加标签计数器。 这将具有线性标签复杂性,但有时恒定因素很重要(例如在我的Mechanical Turk发票上!)。 对于我来说,尚不清楚如果在更严格的Yang对世界漂移的假设下使用AALwC会发生什么。 ACAL实际上使用了所有历史数据的事实表明,AALwC可能在这些条件下可以通过仅减慢与降低查询概率相关的计划来工作。

一种不同的研究策略是在对抗性环境中理解主动学习,然后将不同的在线应用于批处理方案,以将追溯担保转换为多个预期担保。 这种方法有望产生一种在各种不同的世界漂移场景下都可以做到的最佳算法。 如果有人做到这一点,他们将是有名的!

2012年2月29日,星期三

主动学习与情境强盗

现在,主动学习是 越来越好理解,背景强盗(CB)是理所当然的下一个焦点。我对随机CB的最新技术的了解如下:
  1. 我们拥有在计算上可行的算法,这些算法在经验上可以很好地发挥作用(例如, 汤普森采样),但不能提供强有力的不可知论的理论保证。 (这是一个很好的说法 青年汽车)。
  2. 我们提供的算法可提供强有力的不可知论的理论保证(例如, 取消政策),但在计算上不可行。
这里取得的进展超出了理论上的兴趣:随机的CB设置描述了我多年来试图解决的许多问题。

所以我最近(天真?)认为:“嘿,主动学习算法真的很好,它们正在做出类似于探索/利用的决策,所以也许我可以将其用于随机CB解决方案。”事实证明,这是这不是一个好主意,但是理解为什么很有趣。

为了说明起见,请考虑具有二进制奖励的2臂式上下文强盗(注意:以上下文为条件的预期奖励不一定是二进制的;仅奖励的任何特定实现都是二进制的)。在这种情况下,二进制分类器和随机CB策略之间存在自然的对应关系。这表明以下将两臂式随机CB减少为二进制主动学习。
算法:主动学习随机强盗
利用主动学习二进制Oracle $ \ mathcal {O} $的两臂上下文强盗算法。
  1. 获取上下文$ X_k $。
  2. 将上下文$ X_k $作为未标记的数据传递到$ \ mathcal {O} $,并接收决策$ Q_k \ in \ {0,1 \} $来查询标签和预测类$ \ hat Y_k \ in \ {0, 1 \} $。
  3. 如果$ Q_k = 0 $,拉动手臂$ \ hat Y_k $并在\ {0,1 \} $中获得奖励$ R _ {\ hat Y_k} \ in。
  4. 如果$ Q_k = 1 $,
    1. 以相等的概率(即50-50)选择$ A_k \ in \ {0,1 \} $。
    2. 拉动手臂$ A_k $并观察\ $ 0,1 \} $中的奖励$ R_ {A_k}。
    3. 让\ [
      Y_k:= \ begin {cases} A_k&R_ {A_k} = 1 \\ 1-A_k&R_ {A_k} = 0 \ end {cases}。
      \]
    4. 当$ Q_k = 1 $时,按预期将$(X_k,Y_k)$传递给$ \ mathcal {O} $。
基本思想如下:当主动学习算法请求标签时,通过使动作随机化来``探索'';当主动学习算法不请求标签时,通过执行基础分类器想要的操作来``利用''。问题解决了!

当然不是。让我们分析一下算法。首先,说服自己,呈现给基础oracle的数据的0-1分类损失与基础分类器定义的策略损失成正比。由于主动学习算法的学习速度与被动学习算法的学习速度基本相同(但不消耗所有标签),这意味着``剥削策略''将立即产生$ O的遗憾(\ sqrt {\ log(T)/ T})$。但是,在上下文强盗中,重要的是由学习算法引起的策略的遗憾。当主动学习算法请求标签时,遗憾是$ O(1)$,并且由于标签复杂性不可知论主动学习的下限,可以在一定时间内请求标签;这意味着由学习算法引起的策略的最坏情况瞬时遗憾是$ O(1)$。这种遗憾不会让您在上下文强盗理论爱好者垂青的那种聚会上受到欢迎。

现在也许在实践中利用主动学习来实现随机CB确实有效。当然,如果做出适当的低噪声假设,则可以限制主动学习算法的标签复杂度,并且可以使总体遗憾看起来可观。但是,这使我们回到了``在计算上可行的启发式''区域,而不是``不可知论随机CB算法的圣杯''区域。

这是特别有趣的事情:主动学习从根本上比随机CB困难。我之所以这样说是因为标签复杂性下界问题不会困扰直接解决随机CB问题。来自的惊人结果 杜迪克等等 对于学习算法产生的策略,总是有可能实现$ O(\ sqrt {\ log(T)/ T})$后悔。当前,如何以有效的计算方式进行操作是一个悬而未决的问题,但是我们已经可以说以下几点:必须选择是否接收任何奖励信息(主动学习)与被迫仅接受奖励之间存在很大差异。有关所选动作的信息(背景匪徒)。就上述算法而言,问题在于只要$ Q_k = 0 $,我们就``丢弃''信息;并利用该信息是恒定的最坏情况瞬时遗憾与随时间衰减的最坏情况瞬时遗憾之间的差异。

非常感谢John Langford耐心地向我解释了这一点。现在,我迷上了背景强盗!到目前为止,很自然地,我在不可知论的情况下实现$ O(\ sqrt {\ log(T)/ T})$遗憾的尝试并没有成功,但这确实很有趣。

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