显示带有标签的帖子 位置效应. 显示所有帖子
显示带有标签的帖子 位置效应. 显示所有帖子

2012年6月25日,星期一

互动学习

Shivaswamy和Joachims的论文叫做 通过主动学习进行在线结构化预测ICML 2012 今年。当然,Joachims与经典的 研究 因此,我将总结一下:试图从行为数据消耗中估算绝对相关性分数是无效的,而利用注意力模型(例如,串行扫描)来估算相对偏好则更为有效。这是您可以带入许多不同情况的那些``深层技巧''之一。

因此,经典示例是当您获得搜索引擎结果时,仅在特定位置$ p $上单击一次,而注意模型假定用户考虑了该位置之前的每个结果再加上一个。因此,部分偏好$ \ forall x \ in [1,p + 1],x \ neq p:r_p>显示r_x $并将其添加到(排名)训练集中。

在我职业生涯的后期,我开始欣赏随机的背景强盗,尤其是为了获得一致的估计值而对历史国家行动密度进行偏置的重要性。这给我带来了一个矛盾:一方面,利用点击反馈优化搜索引擎无疑是必不可少的。 通过探索学习,因为您仅获得有关所显示项目(子项目)的相对偏好的信息。另一方面,当我直奔约阿希姆斯时,我并没有试图消除历史国家行动密度的偏见。

我希望本文能为我解决这个难题。做到了,但是没有达到我的预期。引言中仅提及背景强盗文学是出于比较目的。相反,作者做出以下假设:
  1. 用户损失在(线性)效用差异中凸显出来。
  2. 用户仅提出改进建议(即用户反馈始终指向``下坡'')。
  3. 用户仅建议进行重大改进(即反馈状态的效用增量至少与最佳增量成比例)。
在这种情况下,明智的做法是采用Perceptron风格的算法来实现良好的后悔约束。作者还探索了这些假设的放松(例如,改进仅在预期上有意义,或者反馈有时指向下坡)以及由此产生的后悔保证降低。

我怀疑分析看起来不像我预期的那样,因为在上一段条件的限制下,可以从对抗性方面选择用户反馈。尽管如此,考虑一种``上下文强盗风格''表述可能是有趣的,例如,不是学习与所选手臂相关的奖励,而是学习所选手臂与另一手臂的奖励之间的差异。一个好的起点是关于 具有受控辅助信息的背景强盗,但此处的主要区别在于用户反馈不受算法控制。

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} \ 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]},\\
\ 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)$完成证明。

2010年9月27日,星期一

位置影响:第二部分

在一个 以前的帖子 当我试图弄清楚如何通过单个反馈事件来优化组合内容页面时,我谈到了在存在位置效应的情况下具有部分反馈的成本敏感的最佳m(CSBM-PF)。提出了几种不同的可能性:
  1. 不用考虑位置依赖性,负外部性等问题。在这种情况下,可以将整个集合视为动作,并直接使用偏移树。这种方法的缺点包括:泛化仅限于具有历史支持的组合;训练时间的计算与组合的数量成比例。但是,如果组合的数量很少,这也许是最好的方法。
  2. 假设采用贪婪的方法构建结果向量是最佳方法,但否则不要假设任何有关位置依赖性(或负外部性?)的信息。在这种情况下 以贪婪的方式排列的偏移树序列 将CSBM-PF降低为CSMC-PF。概括仅限于单个动作位置对具有历史支持的组合,而不是整个组合。培训时间计算是$ m | A | $而不是$ {| A | \选择m} $。
    1. 理想情况下,我可以找到使贪婪方法达到最佳的必要条件,并将其用于学习算法中,但我没有找到一个条件。
  3. 承担 交换至上 (足以使贪婪的方法达到最佳) 按位置保存相对顺序 (正交于贪婪,但必须使随后的工作有效)。同样,以贪婪的方式排列的偏移树序列将CSBM-PF降低为CSMC-PF,但是数据在以后的位置被重用。概括仅限于组合,在该组合中,单个动作在使用位置之前或之前具有历史支持。我曾希望能够以这些假设在以后的位置使用数据,但进一步的思考表明没有。例如,考虑以下预期奖励分配为$ \ epsilon \ to 0 $,\ [
    \ begin {array} {| c | c | c |}
    \ mbox {动作}&r(a,1)&r(a,2)\\ \ hline
    1&1 + 1 / \ epsilon&1 + \ epsilon \\
    2&1&1
    \ end {array}
    \]遵循交换至上的原则,并按位置保留相对顺序;然而,在第二位置的小遗憾会导致在第一位置的大遗憾。基本上到目前为止,我的假设还不足以让我倒退。这是令人遗憾的,因为从较早的位置进行勘探是最昂贵的,因为它们是更高的价值点。
好吧,我试着去幻想,这是有益的,但是最终我要遵循一个共同的假设:位置依赖和动作依赖是因式分解的,即$ r(a,i)= \ kappa(i) \ tilde r(a)$,其中$ \ kappa $和$ \ tilde r $是独立随机变量。如果$ kappa(i)$是非负的并且单调递减,则意味着交换至上和按位置保留相对顺序。不同之处在于,它给出了将头寸从$ i $更改为$ j $,$ E _ {\ kappa | x,\ omega} [\ kappa(j)] / E _ {\ kappa | x,\ omega} [\ kappa(i)] $,这将(希望)使我能够跨职位归纳并减轻历史支持要求。

现在就做 工作。

2010年9月24日,星期五

位置效应

在一个 以前的帖子 我讨论了带有部分反馈的约束成本敏感的最佳m(CSBM-PF)和减少为带有部分反馈的约束成本敏感的多类分类的一种方法(CSMC-PF)。我所考虑的CSBM变体是关于选择最佳选择集的,当一组的奖励是元素的奖励的总和时,“选择最佳选择,然后选择下一个最佳选择,依此类推”。一个鼓舞人心的主要应用程序是优化内容(或广告)元素集,的确,我目前的演出确实想到了内容优化问题。在实际应用中,位置效应很重要,因此我想尝试将它们合并。

我的减少工作如下:首先选择最高的奖励选择,然后将其奖励调整为$-\ infty $,然后重复该过程,直到获得一组大小为$ m $的集合为止。从本质上讲,这是我过去经常看到的方式(例如,构造一个回归器,并按排序的顺序填充职位),但是对于这种贪婪的工作方式,位置依赖不能是任意的:必须是\ [\ sum_ {i = 1} ^ m \ max_ {a_i \ in A \ setminus \ {a ^ * _ 1,\ ldots,a ^ * _ {i-1} \}} r(a_i,i)= \ max_ {a \ in \ tilde A ^ m} \; \ sum_ {i = 1} ^ m r(a_i,i)。 \]这里$ r:A \ times [1,m] \ to [0,1] $是(有条件地期望的)奖励,$ A $是动作,$ [1,m] $是位置,并且右侧最大值是没有重复的动作$ \ tilde A ^ m $的向量(即,不能在多个位置选择相同的动作)。这种``贪婪的工作''条件实际上比我以前假设的要弱得多。例如,这是贪婪适用的一组预期奖励示例: \ [
\ begin {array} {| c | c | c | c |}
\ mbox {动作}&r(a,1)&r(a,2)&r(a,3)\\ \ hline
1&10&5&1 \\
2&2&4&1 \\
3&1&2&3
\ end {array}
\]第一个动作的位置奖励递减,而第二个动作更喜欢特定位置,第三个动作的位置奖励递加。所以我以为探索上面的``贪婪作品''条件会很有趣。

引理:位置最大化器
如果至少有一个$ \ sum_ {j = 1} ^ mr(a_j,j)$的最大化器,则存在一个$ \ sum_ {j = 1} ^ mr的$ \ tilde a ^ * $的最大化器( a_j,j)$,它对[1,m] $中的所有$ i使用每个单独的位置最大化器$ a ^ * _ i $,其中$ a ^ * _ i $使$ r(a,i)$最大化。

证明: 假设$ a ^ * _ i $是$ r(a,i)$的最大化子,并假定$ \ tilde a ^ * $是$ \ sum_ {j = 1} ^ mr(a_j,j)$的最大化子,不会在任何位置使用$ a ^ * _ i $。将$ a ^ \ prime $定义为$ \ tilde a ^ * $,位置$ i $替换为$ a ^ * _ i $。由于$ a ^ * _ i $是$ r(a,i)$的最大化子,因此总奖励不会减少,因此$ a ^ \ prime $也是$ \ sum_ {j = 1} ^ mr的最大化子。 (a_j,j)$。对于每个头寸$ i $重复此参数最终会在每个头寸中使用一个单独的头寸最大化器。
现在,这是贪婪作品的充分条件。
充分条件:交换至上
如果\ [
r (a, i) \geq r (a^\prime, i) \implies \forall j > i: r (a, i) + r (a^\prime, j) \geq r (a, j) + r (a^\prime, i),
\] 然后 \ [
\ sum_ {i = 1} ^ m \ max_ {a_i \ in A \ setminus \ {a ^ * _ 1,\ ldots,a ^ * _ {i-1} \}}} r(a_i,i)= \ max_ { \ in \ tilde A ^ m} \; \ sum_ {i = 1} ^ m r(a_i,i)。
\] 证明: 证明是归纳法。基本情况是$ m = 1 $,在这种情况下,贪婪总是有效的。

要显示$ m-1 \ Rightarrow m $,请从引理中注意到,右边有一个最大化器,该最大化器在某些位置使用$ a ^ * _ 1 $。如果该位置是$ j \ neq 1 $,则通过交换位置1和$ j $来构造右侧的新最大化器:由于定理的前提,可以保证不会减少总奖励。由于期望结果的左手侧和右手侧在位置1都使用$ a ^ * _ 1 $,因此可以从两侧减去它,得出\ [
\ sum_ {i ^ \ prime = 1} ^ {m-1} \ max_ {a ^ \ prime_ {i ^ \ prime} \ in A_1 \ setminus \ {{a ^ \ prime} ^ * _ 1,\ ldots,{ a ^ \ prime} ^ * _ {i ^ \ prime-1} \}} r(a ^ \ prime_ {i ^ \ prime},i ^ \ prime)= \ max_ {a \ in \ tilde A_1 ^ m} \; \ sum_ {i ^ \ prime = 1} ^ {m-1} r(a_ {i ^ \ prime},i ^ \ prime),
\]其中$ A_1 = A \ setminus a ^ * _ 1 $和$ i ^ \ prime = i-1 $。
玩具实例 above is sufficient to show 那 the condition in the above theorem is not necessary: actions 2 和 3 violate the condition for positions 1 和 2, yet greedy still works. This is because they are not used in position 1 due to action 1. It is an interesting assumption, however, because when rearranging a bit, \ [ r (a, i) - r (a^\prime, i) \geq 0 \implies \forall j > i: r (a, i) - r (a^\prime, i) \geq r (a, j) - r (a^\prime, j), \] it suggests 那 the policy regret 在 a later position can be upper bounded by the policy regret 在 an earlier position. This is almost good enough to let an offset tree style regret bound proof go through. It turns out what is needed is two-fold: the expected importance weight difference 在 a particular node has to be a upper bound on the policy regret, 和 the sign of the expected importance weight difference 在 a particular node has to be the same as the sign of the policy regret (so 那, the correct importance-weighted decision is the correct policy decision). So I could add one additional condition, \ [ r (a, i) - r (a^\prime, i) \geq 0 \implies \forall j > i: r (a, j) - r (a^\prime, j) \geq 0, \] i.e. the relative order of the actions does not change as position increases. With this assumption I could use historical instances from previous positions to train offset trees for later positions, mitigating the requirements on historical data (without some kind of structural assumption, every action has to have some chance of being tried 在 every position for the regret bound to go through). What about training offset trees for earlier positions? Well if the relative order of the actions does not change as position increases, I can always find the best action in the last position, 和 那 will be the best action in any position. Thus all the historical data would get projected forward onto the last position 和 the resulting forfeit offset tree would be rebuilt with the constraint set increasing over time. 的 historical policy need only have some chance of trying every action pair 在 an overlapping set of positions in order for the regret bound to go through.

现在,使这项工作生效。