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} $的专家预测。然而,即使有所有这些警告,例如在推荐系统中也可能有一个有趣的应用。



































没意见:

发表评论