2012年5月21日,星期一

教学理论?

在学习理论中,我们经常谈论一种环境,它会忽略我们的算法,或者会完全意识到我们的算法并试图使其表现不佳。如果环境完全意识到我们的算法并试图帮助它成功,那该怎么办?

这是一个具体的例子。假设您正在尝试将消息传递给接收方,并且该消息是一组有限的假设之一。通过发送一系列特征标签对$(X \ times Y)^ * $,您不得不与接收器进行通信。接收方将使用提供的数据,通过假设集上的ERM对消息进行解码。它需要多少个示例,您应该如何选择它们?如果这听起来很老套,则认为进化是通过重用来实现的,因此,如果由于其他选择压力而从经验中学习的能力,可以选择将其用于服务交流 认知语言学.

直观地讲,即使从经验中学到了要传达的假设,但重新传输用于学习假设的确切数据也不是一个好策略。实际上,最好的策略似乎是根本不使用真实数据。通过构建一组人工的训练示例,可以引入有利的结构,例如,可以实现该问题。 (有趣的是:我曾经教授一位教授,他坦言他有时会向本科生开设入门课程,以使他们``更接近真相'';这个想法是,如果他们上了高年级班,他会有能力加深他们的理解,如果不是这样,他们实际上比学习简化的失真更好。

学习理论中的某些概念在此设置中是落后的。例如, 小石城的维度 表示当对抗性地选择示例时,在可实现的顺序预测方案中发生的最大错误数(和 概括到不可知论的情况)。我们可以在这里帮助选择示例(adversarial的反义词是什么?),但实际上 错误,因此许多假设是不正确的,可以迅速消除。不幸的是,我们可能会遇到这样一种情况,即希望传达的假设在任何一点上最多与另一个假设不符。小石城认为这一条件是有利的,因为一个错误会消除除一个假设之外的所有假设,否则就不会造成伤害。但是在我们的情况下,这是最坏的情况,因为这很难通过示例来分离目标假设。换句话说,我们可以有帮助地选择数据,但是如果对抗性地选择假设集,这可能仍然非常困难。

对于发送者而言,发明一个最佳的虚拟数据序列可能在计算上过于困难。在这种情况下,主动学习算法可能会提供良好的启发式解决方案。在此,标签复杂度对应于用于学习假设的原始数据序列与用于传输假设的简化数据序列之间的数据压缩。

有各种各样的变化的沃土,例如,通信信道嘈杂,接收器确实估计了ERM,或者根据通信假设和接收假设之间的损失差异而不是假设的0-1损失对通信进行评分。

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