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 $的价值就应该更少。当我们接近规划阶段的末期时,这主要是由过去的出色表现所驱动。

没意见:

发表评论