2010年10月3日,星期日

位置偏移树

我的 以前的帖子 总结了我最近关于在考虑到位置影响的情况下对具有部分反馈的成本敏感型最佳客户(CSBM-PF)的想法。一个主要的启发性应用程序是优化内容(或广告)元素集,对于这些元素而言,位置效果通常很重要。经过一番尝试之后,我决定挥舞理论上的白旗,并简化了将奖励因素分解为特定于动作的位置独立因素和特定于位置的动作独立因素的假设。但是,事实证明,即使这样,我也无法很好地利用来自较新职位的数据来告知较早职位的遗憾。我开始怀疑从以后的位置使用数据存在根本性的错误。

该方法包括两个部分。第一部分是对偏移树的修改,其中包含了位置效应,这就是本文的内容。第二部分是对从CSBM还原为CSMC以构建整个集合的略微修改。我将专注于这篇文章的第一部分。最重要的是,通过规范每个动作的位置呈现历史,我可以使用先前位置的数据来告知当前位置的遗憾。

设置如下。有一个分布$ D = D_x \ times D _ {\ omega | x} \ times D_ {r | \ omega,x} $,其中$ r:A \ times [1,m] \ to [0,1] \ cup \ {-\ infty \} $以单位间隔中的值加上$-\ infty $,并且将$ r $的特定实例中$-\ infty $值的分量显示为问题的一部分通过$ \ omega \ in \ mathcal {P}(A \ times [1,m])$中的实例(即$ \ omega $是$ A \ times [1,m] $的子集)。响应问题实例所允许的输出是$ A $上的$ m $-矢量,没有重复,表示为\ [\ Xi_m = \ {\ xi \ in A ^ m | \ xi_i = \ xi_j \ iff i = j \}。\]特定确定性策略$ h的遗憾:X \ times \ mathcal {P}(A)\ to \ Xi_m $由\ [v(h)给出= E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [\ max_ {s \ in \ Xi_m} \; E_ {r \ sim D_ {r | \ omega,x}} \ left [\ sum_ {n = 1} ^ mr(\ xi_n,n)\ right]-E_ {r \ sim D_ {r | \ omega,x }} \ left [\ sum_ {n = 1} ^ mr(h_n(x,\ omega),n)\ right] \ right]。 \]我假定历史策略在给定实例$ p(\ xi | x,\ omega)$的情况下对$ \ Xi_m $使用已知的条件分布。注意,对于某些$ \ omega $,可能没有$ \ Xi_m $可行的元素,即获得有限奖励的元素;在这种情况下,后悔永远是零。因此,问题空间中有趣的部分是那些$ \ xi_m $可行的$ \ omega $。

简化的假设是,动作位置对因子的奖励为\ [r(a,i)= \ kappa(i)\ tilde r(a)\]其中$ i>j \暗示\ kappa(i)<\ kappa(j)$和$ \ kappa(i)\ geq 0 $表示所有$ i $。注意$ \ kappa $是一个随机变量(例如$ \ tilde r $)。尽管我被迫假设$ \ kappa $和$ \ tilde r $独立变化,但我不假定位置因子是已知的或固定的。我将不再谈论$ D_ {r | x,\ omega} $谈论$ D _ {\ tilde r | x,\ omega} \ times D _ {\ kappa | x,\ omega} $。

根据以上假设,可以发现,以贪婪的方式按位置选择动作是最佳的。位置偏移树的要点是使用来自多个位置的数据来通知对特定位置上的动作的选择。我将转向谈论选择单个动作$ h的遗憾:X \ times \ mathcal {P}(A)\ to a $在特定的固定位置$ z $,\ [
\ begin {aligned}
v_z(小时)&= E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ \max_{a \in A}\;E_ {r \ sim D_ {r | x,\ omega}} \ left [r(a,z)\ right]-E_ {r \ sim D_ {r | x,\ omega}} \ left [r(h(x,\ omega),z)\ right] \ right] \\
&= E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ E_{\kappa \sim D_{\kappa|x,\omega}} \left[ \kappa (z) \right] \left( \max_{a \in A}\;E _ {\\ t​​ilde r \ sim D _ {\ tilde r | \ omega,x}} \ left [\ tilde r(a)\ right]-E _ {\ tilde r \ sim D _ {\ tilde r | \ omega,x} } \ left [\ tilde r(h(x,\ omega))\ right] \ right)\ right]。
\ end {aligned}
\]不能在单个位置看到重复的约束,但是在实践中通过将$ \ omega $减少为按位置的单个动作选择,可以通过操作$ \ omega $来满足。
算法:位置没收偏移树火车
数据: 部分标记的约束位置CSMC训练数据集$ S $。
输入: 为其创建分类器的位置$ z $。
输入: 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
结果: 经过训练的分类器$ \ {\ Psi_ \ nu | \ nu \ in \ Lambda(T)\} $。
对于从叶到根的每个\\ nu \ in \ Lambda(T)$:
  1. $ S_ \ nu = \ emptyset $。
  2. 对于每个示例$(x,\ omega,\ xi,\ {r(a,i)|(a,i)\ in \ xi \},p(\ cdot | x,\ omega))\ in S $:
    1. 假设$ \ lambda $和$ \ phi $是输入到$ \ nu $的两个类(分别针对输入$(x,\ omega)$的左和右子树的预测)。
    2. 如果$(\ lambda,z)\ in \ omega $,预测$ \ phi $以便为父节点构建训练输入(``$ \ lambda $遗忘'');
    3. 否则,如果$(\ phi,z)\ in \ omega $,预测$ \ lambda $以便为父节点构建训练输入(``$ \ phi $遗忘'');
    4. 否则foreach $ n $ in $ \ Upsilon _ {\ lambda,\ phi} = \ {n \ in [1,z] | E _ {\ xi \ sim p} \ left [1 _ {\ xi_n = \ lambda} 1 _ {(\ lambda,n)\ not \ in \ omega} \ right] E _ {\ xi \ sim p} \ left [1_ { \ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]> 0 \}$:
      1. 假设$ \ alpha = | \ Upsilon _ {\ lambda,\ phi} | ^ {-1} \ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi} } 1 _ {\ xi_n = \ lambda} 1 _ {(\ lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right ]} {E _ {\ xi ^ \ prime \ sim p} \ left [1 _ {\ xi ^ \ prime_n = \ xi_n} 1 _ {(\ xi_n,n)\ not \ in \ omega} \ right]} $
      2. 令$ y = 1 _ {\ xi_n = \ lambda} $。
      3. 如果$ r(\ xi_n,n)<\ frac {1} {2} $,$ S_ \ nu \ leftarrow S_ \ nu \ cup \ left \ {\ left(x,1-y,\ alpha \ left(\ frac {1} {2}-r( \ xi_n,n)\ right)\ right)\ right \} $;
      4. 其他$ S_ \ nu \ leftarrow S_ \ nu \ cup \ left \ {\ left(x,y,\ alpha \ left(r(\ xi_n,n)-\ frac {1} {2} \ right)\ right) \ right \} $。
  3. 令$ \ Psi_ \ nu = \ mbox {Learn}(S_ \ nu)$。
返回$ \ {\ Psi_ \ nu | \ nu \ in \ Lambda(T)\} $。

算法:位置没收偏移树测试
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
输入: 经过训练的分类器$ \ {\ Psi_ \ nu | \ nu \ in \ Lambda(T)\} $。
输入: 实例实现$ {x,\ omega)$。
结果: 预测标签$ k $。
  1. 令$ \ nu $为根节点。
  2. 重复直到$ \ nu $是叶节点:
    1. 如果$ \ nu $左子树中所有叶子的标签都在$ \ omega $中,则遍历右孩子;
    2. 否则,如果$ \ nu $右子树中所有叶子的标签都在$ \ omega $中,则遍历到左孩子;
    3. 否则,如果$ \ Psi_ \ nu(x)= 1 $,则遍历到左孩子;
    4. 否则(当$ \ Psi_ \ nu(x)= 0 $并且每个子树中至少有一个标签不在$ \ omega $中时),遍历到正确的孩子。
  3. 返回叶子标签$ k $。

激励更新

基本思想是对历史数据进行重要性加权,以使要比较的每对广告都得到相同的预期位置处理。这将对历史政策的要求从``一般化是不安全的,除非一个动作有机会在特定位置展示''到``一般化是不安全的,除非每对动作都有机会在特定位置展示''在考虑中的一个或之前的特定职位''。 (好吧,也许有点让人难以理解)。

对于固定的$(x,\ omega,\ kappa,\ tilde r)$和内部节点为左输入$ \ lambda $和右输入$ \ phi $的情况,$ \ lambda $的预期重要性权重为\ [
\ begin {aligned}
w _ {\ lambda | \ tilde r,\ kappa} = \ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}}} 1 _ {\ xi_n = \ lambda } 1 _ {(\ lambda,n)\ not \ in \ omega} \ alpha _ {\ lambda,n} \ left(\ kappa(n)\ tilde r(\ xi_n)-\ frac {1} {2} \ right )_ + + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ alpha _ {\ phi,n} \ left(\ frac {1} {2}-\ kappa( n)\ tilde r(\ xi_n)\ right)_ + \ right]} {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} 1 _ {\ xi_n = \ lambda} 1 _ {((lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]},
\ end {aligned} \]其中$ \ alpha _ {\ lambda,n} $和$ \ alpha _ {\ phi,n} $要确定比例因子,而\ [\ Upsilon _ {\ lambda,\ phi} = \ {n \ in [1,z] | E _ {\ xi \ sim p} \ left [1 _ {\ xi_n = \ lambda} 1 _ {(\ lambda,n)\ not \ in \ omega} \ right] E _ {\ xi \ sim p} \ left [1_ { \ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]>0 \} \]是在当前位置或之前获得共享支持的可行位置的集合。这表明\ [
\ alpha _ {\ lambda,n} \ propto
\ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} 1 _ {\ xi_n = \ lambda} 1 _ {((lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]} {E _ {\ xi \ sim p} \ left [1 _ {\ xi_n = \ lambda } 1 _ {(\ lambda,n)\ not \ in \ omega} \ right]},
\]产生\ [
\ begin {aligned}
w _ {\ lambda | \ tilde r,\ kappa}&\ propto \ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ left(\ kappa(n)\ tilde r(\ lambda)-\ frac { 1} {2} \ right)_ + + \ left(\ frac {1} {2}-\ kappa(n)\ tilde r(\ phi)\ right)_ +,\\
w _ {\ phi | \ tilde r,\ kappa}&\ propto \ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ left(\ kappa(n)\ tilde r(\ phi)-\ frac { 1} {2} \ right)_ + + \ left(\ frac {1} {2}-\ kappa(n)\ tilde r(\ lambda)\ right)_ +,\\
w _ {\ lambda | \ tilde r,\ kappa}-w _ {\ phi | \ tilde r,\ kappa}&\ propto \ left(\ tilde r(\ lambda)-\ tilde r(\ phi)\ right)\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ kappa(n)。
\ end {aligned}
\]由于位置因素是未知的随机变量,因此无法使其完全等于策略遗憾差异,但是单调性约束意味着$ \ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ kappa( n)\ geq | \ Upsilon _ {\ lambda,\ phi} | \ kappa(z)$。因此,选择\ [
\ begin {aligned}
\ alpha _ {\ lambda,n}&=
| \ Upsilon _ {\ lambda,\ phi} | ^ {-1} \\
\ alpha _ {\ phi,n}&=
| \ Upsilon _ {\ lambda,\ phi} | ^ {-1} \ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} 1 _ {\ xi_n = \ lambda} 1 _ {((\ lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]} {E_ { \ xi \ sim p} \ left [1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right]},
\ end {aligned}
\]我们得到一个预期的重要权重差,该权重差既有正确的符号,又具有至少等于位置$ z $的政策遗憾的幅度,
\ begin {aligned}
E_ {D _ {\ tilde r | x,\ omega} \ times D _ {\ kappa | x,\ omega}} \ left [w _ {\ lambda | \ tilde r,\ kappa}-w _ {\ phi | \ tilde r,\ kappa} \ right]&= E_ {D _ {\ tilde r | x,\ omega}} \ left [\ tilde r(\ lambda)-\ tilde r(\ phi)\ right] E_ {D _ {\ kappa | x,\ omega}} \ left [\ frac {1} {| \ Upsilon _ {\ lambda,\ phi} |} \ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi}} \ kappa(n)\ right ],\\
\ mbox {sgn} \ left(E_ {D _ {\ tilde r | x,\ omega} \ times D _ {\ kappa | x,\ omega}} \ left [w _ {\ lambda | \ tilde r,\ kappa}- w _ {\ phi | \ tilde r,\ kappa} \ right] \ right)&= \ mbox {sgn} \ left(E_ {D _ {\ kappa | x,\ omega}} [[\ kappa(z)] E_ { D _ {\\ t​​ilde r | x,\ omega}} \ left [\ tilde r(\ lambda)-\ tilde r(\ phi)\ right] \ right),\\
\ left | E_ {D _ {\ tilde r | x,\ omega} \ times D _ {\ kappa | x,\ omega}} \ left [w _ {\ lambda | \ tilde r,\ kappa}-w _ {\ phi | \ tilde r,\ kappa} \ right] \ right | &\ geq E_ {D _ {\ kappa | x,\ omega}} [\ kappa(z)] \ left | E_ {D _ {\ tilde r | x,\ omega}} \ left [\ tilde r(\ lambda)-\ tilde r(\ phi)\ right] \ right |。
\ end {aligned}
\]这足以使后悔的证明策略起作用。相反,如果我尝试在共享支持下使用所有位置的数据,最终我将$ E_ {D _ {\ kappa | x,\ omega}} [\ kappa(m)] $作为最后一个不平等的主要因素,太小$ E_ {D _ {\ kappa | x,\ omega}} [\ kappa(z)] / E_ {D _ {\ kappa | x,\ omega}} [\ kappa(m)] $ 。我可以扩展条件后悔的范围,并提出另一个证明界限,但是该界限对我没有用,因为在实践中我无法计算$ \ kapp $的比率。

由于我不使用以后的数据,因此我怀疑我可以放宽我的假设并仅假设 交换至上保持相对秩序 而且仍然可以解决问题。

后悔分析

位置没收偏移树的后悔分析与没收偏移树的后悔分析非常相似。主要区别在于,预期重要性权重差不等于策略遗憾,而只是策略遗憾。这足以使证明策略起作用,并且在其他情况下最好注意,即可以做的最好的事情就是限制策略后悔。

令$ \ Psi =(T,\ {\ Psi_ \ nu | \ nu \ in \ Lambda(T)\})$表示特定的位置丧失补偿树(即,选择二叉树和特定的节点集)分类器),令$ z $表示训练树的固定位置,令$ h ^ \ Psi $表示从树得到的策略。后悔分析利用三元组(x ^ \ prime,y,w)$上的诱导重要性加权二元分布$ D ^ \ prime(\ Psi)$,定义如下:
  1. 从$ D $绘制$(x,\ omega,\ kappa,\ tilde r)$。
  2. 在二叉树的内部节点$ \ Lambda(T)$上绘制$ \ nu $制服。
  3. 令$ x ^ \ prime =(x,\ nu)$。
  4. 假设$ \ lambda $和$ \ phi $是输入到$ \ nu $的两个类(分别针对输入$ x $的左和右子树的预测)。
  5. 如果$(\ lambda,z)\ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,0,0)$;
  6. 否则,如果$(\ phi,z)\ in \ omega $,则创建重要性加权的二进制示例$(x ^ \ prime,1,0)$;
  7. 其他(当$ {\ lambda,z)\ not \ in \ omega $和$ {\\ phi,z)\ not \ in \ omega $时):
    1. 在$ \ Upsilon _ {\ lambda,\ phi} $上绘制$ n $制服。
    2. 从$ p(\ xi | x,\ omega)$中绘制$ \ xi $。
    3. 如果$ \ xi_n \ neq \ lambda $和$ \ xi_n \ neq \ phi $,则拒绝样本;
    4. 否则,如果$(\ xi_n,n)\ in \ omega $,则拒绝样本;
    5. 其他(当($ \ xi_n = \ lambda $或$ \ xi_n = \ phi $)和$(\ xi_n,n)\ not \ in \ omega $时:
      1. 假设$ \ alpha = | \ Upsilon _ {\ lambda,\ phi} | ^ {-1} \ frac {E _ {\ xi \ sim p} \ left [\ sum_ {n \ in \ Upsilon _ {\ lambda,\ phi} } 1 _ {\ xi_n = \ lambda} 1 _ {(\ lambda,n)\ not \ in \ omega} + 1 _ {\ xi_n = \ phi} 1 _ {(\ phi,n)\ not \ in \ omega} \ right ]} {E _ {\ xi ^ \ prime \ sim p} \ left [1 _ {\ xi ^ \ prime_n = \ xi_n} 1 _ {(\ xi_n,n)\ not \ in \ omega} \ right]} $
      2. 设$ y = 1 _ {\ xi_n = \ lambda} $
      3. 如果$ r(\ xi_n,n)<\ frac {1} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1-y,\ alpha \ left(\ frac {1} {2}-r(\ xi_n,n ) \是的是的);\]
      4. 否则,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,y,\ alpha \ left(r(\ xi_n,n)-\ 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_{\nu \in \Lambda (T)} E_{(x, \omega) \sim D_x \times D_{\omega|x}} \left[ q_\nu (\Psi | x, \omega) \right], \ end {aligned} \] where \[ q_\nu (\Psi | x, \omega) = \begin{cases} 0 & \mbox{if } \Gamma (\nu_\lambda) \setminus \omega_z = \emptyset \mbox{ or } \Gamma (\nu_\phi) \setminus \omega_z = \emptyset; \\ 0 & \mbox{if } \Psi_\nu (x) = 1_{w_\lambda >w_ \ phi}; \\ \左| w_ \ lambda-w_ \ phi \ right | &\ mbox {otherwise},\ end {cases} \]是内部节点$ \ nu $,$ \ Gamma(\ nu)$的重要性加权后悔的重要性,它是指根于$ \的子树中的一组标签(叶)。 nu $,$ \ nu_ \ lambda $表示$ n $的左子代,$ \ nu_ \ phi $表示$ n $的右子代,$ \ omega_z = \ {a | (a,z)\ in \ omega \} $是在此位置不可行的操作集合,$ w_ \ lambda $是以$(x,\ omega)$和$ w_为条件的左孩子的预期重要性权重\ phi $是以$(x,\ omega)$为条件的正确孩子的预期重要性权重。
定理:遗憾的结界
对于所有部分标记的CSMC分布$ D $,使得$ r = \ kappa \ tilde r $如上所述;所有历史策略$ p(\ xi | x,\ omega)$,以便对于所有对动作$ \ lambda,\ phi $,$ \ Upsilon _ {\ lambda,\ phi} \ neq \ emptyset $每当$(\ lambda ,z)\ not \ in \ omega $和$(\ phi,z)\ not \ in \ omega $;和所有位置丧失的偏移树$ \ Psi $,\ [v_z(h ^ \ Psi)\ leq(| A |-1)q(\ Psi)\]其中$ q(\ Psi)$是重要性加权二进制对引起的子问题感到遗憾。

证明: 看到 附录.
因此,使用来自$ z $和先前位置的数据针对位置$ z $训练的特定位置没收偏移树可以用于选择特定$ z $处的最佳动作。下一步是通过将CSBM简化为CSMC,并稍加修改,将位置$ z $传递给每个子问题,将单个位置丧失的偏移树组合成集合选择器。

由于结果有点让人不知所措,因此最好将其转过头再说如下:按位置归一化演示历史记录不足以证明使用较晚位置的数据来告知较早位置的遗憾,即使给出了非常强的结构假设奖励如何随职位而变化如果确实使用了所有位置的数据,则结果将以\ [v_z(h ^ \ Psi)\ leq(| A |-1)E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [\ frac {E _ {\ kappa \ sim D _ {\ kappa | x,\ omega}}} \ left [\ kappa(z)\ right]} {E _ {\ kappa \ sim D _ {\ kappa | x,\ omega}} \ left [\ kappa(m)\ right]} q(\ Psi | x,\ omega)\ right],\]尽管足以建立简化的一致性,对我而言尚不清楚如何在实践中加以利用:我不知道如何管理不同$(x,\ omega)$之间的优化权衡,因为我不知道$ \ frac {E _ {\ kappa \ sim D_ {\ kappa | x,\ omega}} \ left [\ kappa(z)\ right]} {E _ {\ kappa \ sim D _ {\ kappa | x,\ omega}} \ left [\ kappa(m)\ right ]} $。

附录

这就是后悔的证明。它是根据$ r $而不是$ \ kappa \ tilde r $来完成的,因此我可以轻松地将其适应于较弱的假设 交换至上保持相对秩序.

考虑一个固定的$(x,\ omega)$。讨论内部节点$ \ nu $,\ [v_z(h ^ \ Psi | x,\ omega,\ nu)= \ max_ {k \ in \ Gamma(\ nu)中遇到的条件策略后悔是很有用的} E_ {r \ sim D_ {r | x,\ omega}} \ left [r(a,z)\ right]-E_ {r \ sim D_ {r | x,\ omega}} \ left [r(h_ \ nu ^ \ Psi(x,\ omega),z)\ right]。 \]其中$ h_ \ nu ^ \ Psi $是内部节点$ \ nu $的预测。当$ \ nu $是树的根时,$ v_z(h ^ \ Psi | x,\ omega,\ nu)$是有条件的抵消树策略,遗憾地以$(x,\ omega)$为条件。

证明策略是通过归纳绑定$ v_z(h ^ \ Psi | x,\ omega,\ nu)\ leq \ sum_ {m \ in \ Lambda(\ nu)} q_m(\ Psi | x,\ omega)$ 。对于只有一片叶子(没有内部节点)的树,基本情况很容易满足,因为它的值为$ 0 \ leq 0 $。为了显示在特定内部节点$ \ nu $上的递归,让$ \ lambda $和$ \ phi $是左子树($ \ nu_ \ lambda $)和右子树($ \ nu_ \ phi $)的预测。
情况1:$ \ Gamma(\ nu_ \ lambda)\ setminus \ omega_z = \ emptyset $。在这种情况下,$(\ lambda,z)\在\ omega $中并没有收益,因此选择了$ \ phi $。右子树中必须有一个最大化器,因为左子树中的所有值都是$-\ infty $。此外,对于$ m = \ nu $和$ m \ in \ Lambda(\ nu_ \ lambda)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v_z(h ^ \ Psi | x,\ omega,\ nu)&= \ max_ {k \ in \ Gamma(\ nu)} E_ {r \ sim D_ {r | \ omega, x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ phi,z)\ right] \\&= \ max_ {k \ in \ Gamma(\ nu_ \ phi)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ phi,z)\ right] \\&= v_z(h ^ \ Psi | x,\ omega,\ nu_ \ phi)\\&\ leq \ sum_ {m \在\ Lambda(\ nu_ \ phi)} q_m(\ Psi | x,\ omega)\\&= \ sum_ {m \ in \ Lambda(\ nu)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况2:$ \ Gamma(\ nu_ \ lambda)\ setminus \ omega_z \ neq \ emptyset $和$ \ Gamma(\ nu_ \ phi)\ setminus \ omega_z = \ emptyset $。在这种情况下,$(\ phi,z)\ in \ omega $和$(\\ lambda,z)\ not \ in \ omega $,因此选择了$ \ phi $充公和$ \ lambda $。左子树中必须有一个最大化器,因为右子树中的所有值都是$-\ infty $。此外,对于$ m = \ nu $和$ m \ in \ Lambda(\ nu_ \ phi)$,$ q_m(\ Psi | x,\ omega)= 0 $。因此\ [\ begin {aligned} v_z(h ^ \ Psi | x,\ omega,\ nu)&= \ max_ {k \ in \ Gamma(\ nu)} E_ {r \ sim D_ {r | \ omega, x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ lambda,z)\ right] \\&= \ max_ {k \ in \ Gamma(\ nu_ \ lambda)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(k,z)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [r(\ lambda,z)\ right] \\&= v_z(h ^ \ Psi | x,\ omega,\ nu_ \ lambda)\\&\ leq \ sum_ {m \在\ Lambda(\ nu_ \ lambda)} q_m(\ Psi | x,\ omega)\\&= \ sum_ {m \ in \ Lambda(\ nu)} q_m(\ Psi | x,\ omega)。 \ end {aligned} \]
情况3:$ \ Gamma(\ nu_ \ lambda)\ setminus \ omega_z \ neq \ emptyset $和$ \ Gamma(\ nu_ \ phi)\ setminus \ omega_z \ neq \ emptyset $。这是``正常''偏移树情况,其中$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $都没有,所以没收没收。如 如上所示,以$(x,\ omega)$为条件的预期重要性权重差与$(\ lambda,z)$和$(\ phi,z)$之间的政策遗憾具有相同的符号,并且幅度为至少等于$(\ lambda,z)$和$(\ phi,z)$之间的策略遗憾。

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

没意见:

发表评论