2010年9月12日,星期日

没收的偏移树

因此,在我寻求从OR清除回归的过程中,到目前为止我一直在考虑的问题有一个不现实的方面。例如,在没有追索权的SSP中,我假设历史数据中的每个图都可以使用与每个边相关的成本。假设只知道与历史上实际经过的边线相关的成本,这似乎更为现实。这是一个例子 通过探索学习 ,尤其是热启动问题,其中存在具有部分信息的历史数据可用于学习策略。

偏移树 是从具有部分反馈的成本敏感型多类分类(CSMC)减少到二进制分类。它用于在固定类(例如香草CSMC)和历史数据中只有一个决策的情况下,其中仅揭示了所选决策的价值(不同于香草CSMC)。附带说明一下,这种区别是根本的,因为从CSMC到二进制分类都有减少,而遗憾的是与类数无关。而偏移树后悔界限(与$ | A |-1 $成比例)是可证明的下界。

因此,自然要问的一个问题是:我是否可以简化问题的完整信息版本(例如, SSP无追索权)到CSMC子问题集,是否可以将问题的部分信息版本简化为带有部分反馈子问题的CSMC集(并利用偏移树)?我不确定,但我怀疑。

但是,为了建立直觉,我将从一些简单的事情开始。由于我实际上是想减少约束CSMC的问题,因此我需要一些可以处理带有部分反馈的约束CSMC的东西。这建议定义类似于 没收过滤树.

设置如下。有一个分布$ D = D_x \ times D _ {\ omega | x} \ times D_ {r | \ omega,x} $其中$ r:A \ to [0,1] \ cup \ {-\ infty \} $以单位间隔上增加$-\ infty $的值,并通过$ \ omega \ in \ mathcal将特定实例的$ r $的分量作为$-\ infty $的值作为问题实例的一部分进行显示。 {P}(A)$(即$ \ omega $是$ A $的子集)。特定确定性策略$ h的遗憾:X \ times \ mathcal {P}(A)\ to A $是\ [v(h)= E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [\ max_ {k \ in A} \\; E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(h(x, \ omega))\ right] \ right]。 \]到目前为止,这与CSMC相同,只是进行了外观上的更改以与强化学习文献保持一致:成本(现称为“奖励”)已被抵消,并压缩为单位间隔;和类现在称为``动作''。这是因为唯一真正的区别在于训练数据的部分性质,其仅通过子问题的诱导分布来体现出来。为了定义归纳分布,我将假定历史策略在给定实例$ p(a | x,\ omega)$的情况下对操作使用已知的条件分布;在实践中,有一些方法可以 放松这个假设.
算法:没收偏移树火车
数据: 部分标记的受限CSMC训练数据集$ S $。
输入: 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
结果: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
  1. 从叶子到根的每个$ n \ in \ Lambda(T)$:
    1. $ S_n = \ emptyset $。
    2. 对于每个示例$(x,\ omega,a,r(a),p(\ cdot | x,\ omega))\ in S $:
      1. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类(分别预测输入$(x,\ omega)$的左和右子树)。
      2. 如果$ \ lambda \ in \ omega $,预测$ \ phi $以便为父节点构建训练输入(``$ \ lambda $ forfeits'');
      3. 否则,如果$ \ phi \ in \ omega $,预测$ \ lambda $以便为父节点构建训练输入(``$ \ phi $ forfeits'');
      4. 否则(当$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $时)如果$ a = \ lambda $或$ a = \ phi $:
        1. 如果$ a = \ lambda $,则$ a ^ \ prime = \ phi $;否则$ a ^ \ prime = \ lambda $。
        2. 设$ y = 1_ {a ^ \ prime = \ lambda} $,即$ a ^ \ prime $来自$ n $的左子树。
        3. 如果$ r(a)<\ frac {1} {2} $,$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,y,\ frac {p(a | x,\ omega)+ p(a ^ \ prime | x, \ omega)} {p(a | x,\ omega)} \ left(\ frac {1} {2}-r(a)\ right)\ right)\ right \} $;
        4. 其他$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1-y,\ frac {p(a | x,\ omega)+ p(a ^ \ prime | x,\ omega)}} p( a | x,\ omega)} \ left(r(a)-\ frac {1} {2} \ right)\ right)\ right \} $。
    3. 令$ \ Psi_n = \ mbox {Learn}(S_n)$。
  2. 返回$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
算法:没收偏移树测试
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
输入: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
输入: 实例实现$ {x,\ omega)$。
结果: 预测标签$ k $。
  1. 令$ n $为根节点。
  2. 重复直到$ n $是叶节点:
    1. 如果$ n $左子树中所有叶子的标签都在$ \ omega $中,则遍历右孩子;
    2. 否则,如果$ n $的右子树中所有叶子的标签都在$ \ omega $中,则遍历到左孩子;
    3. 否则,如果$ \ Psi_n(x)= 1 $,则遍历左孩子;
    4. 否则(当$ \ Psi_n(x)= 0 $并且每个子树中至少有一个标签不在$ \ omega $中时),遍历右孩子。
  3. 返回叶子标签$ k $。
没收偏移树几乎与无约束的部分标记的CSMC的偏移树减少相同,此外,不可行的选择会自动失去他们参加的任何锦标赛(如果两个参赛者都不可行,则可以任意选择)。由于该规则,仅调用底层的二进制分类器来区分可行的选择,而后悔分析本质上是相同的。请注意,即使历史探索政策$ p(a | x,\ omega)$从未选择不可行的行动,但在训练内部节点时没收对于确定``替代行动''仍然很重要。如果历史探索政策实际上选择了不可行的措施,那么将跳过那些训练示例。

后悔分析

对于没收的偏移树的后悔分析与对偏移树的后悔分析非常相似,只是没收案件的附加论据。

令$ \ Psi =(T,\ {\ Psi_n | n \ in \ Lambda(T)\})$表示特定的没用偏移树(即,选择二叉树和一组特定的节点分类器),并且令$ h ^ \ Psi $表示因没收偏移树而产生的策略。后悔分析利用三元组(x ^ \ prime,y,w)$上的诱导重要性加权二元分布$ D ^ \ prime(\ Psi)$,定义如下:
  1. 从$ D $绘制$(x,\ omega,r)$。
  2. 在二叉树的内部节点$ \ Lambda(T)$上绘制均匀的$ n $。
  3. 设$ x ^ \ prime =(x,n)$。
  4. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类(分别预测输入$ x $的左和右子树)。
  5. 如果$ \ lambda \ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,0,0)$;
  6. 否则,如果$ \ phi \ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,1,0)$;
  7. 其他(当$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $时):
    1. 从$ p(a | x,\ omega)$中提取$ a $。
    2. 如果$ a \ neq \ lambda $和$ a \ neq \ phi $,则拒绝样本;
    3. 其他(当$ a = \ lambda $或$ a = \ phi $时):
      1. 如果$ a = \ lambda $,则$ a ^ \ prime = \ phi $;否则$ a = \ phi $,$ a ^ \ prime = \ lambda $。
      2. 设$ y = 1_ {a ^ \ prime = \ lambda} $
      3. 如果$ r(a)<\ frac {1} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,y,\ frac {p(a | x,\ omega)+ p(a ^ \ prime | x, \ omega)} {p(a | x,\ omega)} \ left(\ frac {1} {2}-r(a)\ right)\ right); \]
      4. 否则,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1-y,\ frac {p(a | x,\ omega)+ p(a ^ \ prime | x,\ omega)} {p (a | x,\ omega)} \ left(r(a)-\ frac {1} {2} \ right)\ right)。 \]
诱导分布$ D ^ \ prime(\ Psi)$取决于特定的没收偏移树,但是对于任何固定的没收偏移树都是很好定义的。现在,我想将$ h ^ \ Psi $的政策遗憾与$ \ Psi $的重要性加权二进制遗憾联系起来,\ [\ begin {aligned} q(\ Psi)&= E_{(x^\prime, y, w) \sim D^\prime (\Psi)} \left[ w 1_{y \neq \Psi (x^\prime)} \right] \\ &= \frac{1}{|\Lambda (T)|} \sum_{n \in \Lambda (T)} E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ q_n (\Psi | x, \omega) \right], \end{aligned} \] where \[ q_n (\Psi | x, \omega) = \begin{cases} 0 & \mbox{if } \Gamma (n_\lambda) \setminus \omega = \emptyset \mbox{ or } \Gamma (n_\phi) \setminus \omega = \emptyset; \\ 0 & \mbox{if } \Psi_n (x) = 1_{w_\lambda >w_ \ phi}; \\ \左| w_ \ lambda-w_ \ phi \ right | &\ mbox {otherwise},\ end {cases} \]是内部节点$ n $上的重要性加权后悔,$ \ Gamma(n)$指的是根于$ n $的子树中的一组标签(叶), $ n_ \ lambda $表示$ n $的左子代,$ n_ \ phi $表示$ n $的右子代,$ w_ \ lambda $是在$(x, \ omega)$和$ w_ \ phi $是以$(x,\ omega)$为条件的正确孩子的预期重要性权重。
定理:没收偏移树后悔绑定
对于所有部分标记的CSMC分布$ D $;所有历史政策$ p $,例如$ p(a | x,\ omega)>每当$ a \ not \ in \ omega $时为0 $;和所有没收的偏移树$ \ Psi $,\ [v(h ^ \ Psi)\ leq(| A |-1)q(\ Psi)\]其中$ q(\ Psi)$是重要性加权二元遗憾关于诱导的子问题。

证明: 看到 附录.
这与偏移树的界限相同,这表明引入约束不会改变问题设置的基本属性。顺带说一句,为了理解$ \ frac {1} {2} $因子的起源,必须简化到二元分类的所有方式,在这种情况下,预期重要性的最坏情况成为一个因子,并且通过选择$ \ frac {1} {2} $(或每个内部节点的中位数奖励(如果可以先验))将其最小化。

自然的下一步就是看 成本敏感性最佳 有部分反馈;在这种情况下,也许没用的补偿树会很有用。

附录

这就是后悔定理的证明。

考虑一个固定的$(x,\ omega)$。讨论内部节点$ n $,\ [v(h ^ \ Psi | x,\ omega,n)= \ max_ {k \ in \ Gamma(n)} E_ { r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(h ^ \ Psi_n(x ,\ omega))\ right]。 \]其中$ h_n ^ \ Psi $是内部节点$ n $的预测。当$ n $是树的根时,$ v(h ^ \ Psi | x,\ omega,n)$是后悔的,以$(x,\ omega)$为条件的抵消树策略。

证明策略是通过感应绑定$ v(h ^ \ Psi | x,\ omega,n)\ leq \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)$。对于只有一片叶子(没有内部节点)的树,基本情况很容易满足,因为它的值为$ 0 \ leq 0 $。为了显示在特定内部节点$ n $上的递归,让$ \ lambda $和$ \ phi $为左子树($ n_ \ lambda $)和右子树($ n_ \ phi $)的预测。

情况1:$ \ Gamma(n_ \ lambda)\ setminus \ omega = \ emptyset $。在这种情况下,\ omega $中的$ \ lambda \和为假,因此选择了$ \ phi $。右子树中必须有一个最大化器,因为左子树中的所有值都是$-\ infty $。此外,对于$ m = n $和$ m \ in \ Lambda(n_ \ lambda)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&=
\ max_ {k \ in \ Gamma(n)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega, x}} \ left [r(\ phi)\ right] \\&= \ max_ {k \ in \ Gamma(n_ \ phi)} E_ {r \ sim D_ {r | \ omega,x}} \ left [ r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ phi)\ right] \\&= v(h ^ \ Psi | x,\ omega, n_ \ phi)\\&\ leq \ sum_ {m \ in \ Lambda(n_ \ phi)} q_m(\ Psi | x,\ omega)\\&= \ sum_ {m \ in \ Lambda(n)} q_m (\ Psi | x,\ omega)。 \ end {aligned} \]
情况2:$ \ Gamma(n_ \ lambda)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_ \ phi)\ setminus \ omega = \ emptyset $。在这种情况下,\ omega $中的$ \ phi \和\\ omega $中的$ \ lambda \,而不是\ omega $中的$ \ phi $,因此选择了$ \ phi $充公和$ \ lambda $。左子树中必须有一个最大化器,因为右子树中的所有值都是$-\ infty $。此外,对于$ m = n $和$ m \ in \ Lambda(n_ \ phi)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&=
\ max_ {k \ in \ Gamma(n)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega, x}} \ left [r(\ lambda)\ right] \\&= \ max_ {k \ in \ Gamma(n_ \ lambda)} E_ {r \ sim D_ {r | \ omega,x}} \ left [ r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ lambda)\ right] \\&= v(h ^ \ Psi | x,\ omega, n_ \ lambda)\\&\ leq \ sum_ {m \ in \ Lambda(n_ \ lambda)} q_m(\ Psi | x,\ omega)\\&= \ sum_ {m \ in \ Lambda(n)} q_m (\ Psi | x,\ omega)。 \ end {aligned} \]
情况3:$ \ Gamma(n_ \ lambda)\ setminus \ omega \ neq \ emptyset $和$ \ Gamma(n_ \ phi)\ setminus \ omega \ neq \ emptyset $。这是``正常''偏移树情况,其中$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $都没有,所以没收没收。以$(x,\ omega,r)$和$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $为条件的预期重要性权重为\ [\ begin {aligned} w _ {\ lambda | r}&= E_{a \sim p} \biggl[ 1_{a = \lambda} 1_{r (a) \geq \frac{1}{2}}\frac{p (\lambda | x, \omega) + p (\phi | x, \omega)}{p (\lambda | x, \omega)} \left(r (\lambda) - \frac{1}{2}\right) \\ &\quad \quad \quad \quad + 1_{a = \phi} 1_{r (a) <\ frac {1} {2}} \ frac {p(\ lambda | x,\ omega)+ p(\ phi | x,\ omega)} {p(\ phi | x,\ omega)} \ left(\ frac {1} {2}-r(\ phi)\ right)\ biggr] \ biggl / \\&\ quad \ quad E_ {a \ sim p} \ left [1_ {a = \ lambda} + 1_ {a = \ phi} \ right] \\&= \ left(r(\ lambda)-\ frac {1} {2} \ right)_ + + \ left(\ frac {1} {2}-r(\ phi )\ right)_ +,\\ w _ {\ phi | r}&= \ left(r(\ phi)-\ frac {1} {2} \ right)_ + + \ left(\ frac {1} { 2}-r(\ lambda)\ right)_ +,\\ \ end {aligned} \]其中$ \ left(x \ right)_ + = \ max(x,0)$。因此\ [| w_ \ lambda-w_ \ phi | = \ left | E_ {r \ sim D_ {r | \ omega,x}} \ left [w _ {\ lambda | r}-w _ {\ phi | r} \ right] \ right | = \ left | E_ {r \ sim D_ {r | \ omega,x}} [r(\ lambda)-r(\ phi)] \ right |,\],即内部节点的重要性加权后悔等于策略对于输入到该节点的两个动作感到遗憾。

不失一般性地假设分类器选择$ \ phi $。如果最大化器来自右边的子树,则\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&= \ max_ {k \ in \ Gamma(n_ \ phi)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ phi)\ right] \ \&= v(h ^ \ Psi | x,\ omega,n_ \ phi)\\&\ leq \ sum_ {m \ in \ Lambda(n_ \ phi)} q_m(\ Psi | x,\ omega)\\ &\ leq \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]如果最大化器来自左子树,则\ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)&= \ max_ {k \ in \ Gamma(n_ \ lambda)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r( \ phi)\ right] \\&= E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ lambda)-r(\ phi)\ right] + v(h ^ \ Psi | x,\ omega,n_ \ lambda)\\&= q_n(\ Psi | x,\ omega)+ v(h ^ \ Psi | x,\ omega,n_ \ lambda)\\&\ leq q_n(\ Psi | x,\ omega)+ \ sum_ {m \ in \ Lambda(n_ \ lambda)} q_m(\ Psi | x,\ omega)\\&\ leq \ sum_ {m \ in \ Lambda(n)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]在根处终止归纳会产生\ [v(h ^ \ Psi | x,\ omega)\ leq \ sum_ {n \ in \ Lambda(T)} q_n(\ Psi | x,\ Ω)= | \ Lambda(T)| q(\ Psi | x,\ omega)。 \]考虑双方对$ D_x \ times D _ {\ omega | x} $的期望,并注意$ | \ Lambda(T)| =(| A |-1)$完成证明。

没意见:

发表评论