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 and 3 violate the condition for positions 1 and 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 偏移树 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, 和 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 偏移树s 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 偏移树s 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, and 那 will be the best action in any position. Thus all the historical data would get projected forward onto the last position 和 resulting 没收的偏移树 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.

现在,使这项工作生效。

2010年9月23日,星期四

汇总没收偏移树注释

在一个 以前的帖子 我讨论了聚合没收偏移树,该树处理在反馈是聚合的情况下使用部分反馈进行学习的问题,即仅观察到部分动作的总奖励。遗憾的证明需要满足一种历史的历史政策。 ``详细余额''条件,即两套\ [
\ begin {aligned}
\ Upsilon _ {\ lambda,\ neg \ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \in \mathcal{A}, \phi \not \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}, \\
\ Upsilon _ {\ neg \ lambda,\ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \not \in \mathcal{A}, \phi \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}.
\ end {aligned}
\] had to be the same when $\lambda$ was replaced by $\phi$ in each set. Basically, if a set containing $\lambda$ and not $\phi$ is possible in the historical policy, the corresponding set with $\lambda$ replaced by $\phi$ had to be possible as well. This way, the expected contribution of the other rewards cancels 和 reward of the individual action is revealed. Also, $|\Upsilon_{\lambda, \neg \phi}| =| \ Upsilon _ {\ neg \ lambda,\ phi} ||>0 $,即需要有一些集合,且只有一个动作,而没有另一个动作。

好吧,我想提醒自己,如果历史政策不遵守该详细的平衡条件,则可以修改历史数据以创建一个有效的历史政策来遵守该条件。例如,如果$ | \ Upsilon _ {\ lambda,\ neg \ phi} |>| \ Upsilon _ {\ neg \ lambda,\ phi} ||>0 $,我可以拒绝$ \ Upsilon _ {\ lambda,\ neg \ phi} $中的一些额外集合,这样$ | \ Upsilon _ {\ lambda,\ neg \ phi} | = | \ Upsilon _ {\ neg \ lambda,\ phi} | $。当然,依赖于历史策略$ p $的所有归一化常数和因子都需要进行调整,因为现在历史策略为$ p ^ \ prime $($ p $,然后是拒绝步骤)。

2010年9月20日,星期一

通过没收来约束偏移树泛化

这是关于 偏移树:即使在历史记录策略中不支持某些操作时,即$ p(a | x)= 0 $时,该算法也已很好定义。遗憾定理没有通过,但是发生的事情很有趣。给定具有输入操作$ \ lambda $和$ \ phi $的内部节点,这些位置在历史上从未观察到$ \ phi $,则预期的重要权重差为$ \ left(r(\ lambda)-\ frac {1} {2 } \ right)$。因此,基本上,如果观察到的动作的平均回报超过中位数,则坚持下去:否则,它将切换为从未见过的动作。

当然,盲目地概括到从未被直观观察到的动作听起来像是一个危险的主意。这种直觉在 斯特雷尔等等,其中几个要素结合在一起可以避免此问题:经验性的政策估算工具,它可以缩短历史罕见事件的重要性;当比较类策略是具有足够历史支持的那些策略时,对于经验值最大化必定有很高的可能性;并且在实践中修改了上下文盗贼argmax回归,以仅考虑具有足够历史支持的那些选择。

因此,这最后一部分引起了我的注意,因为再次回归可以轻松引入约束。幸运的是,对于一组固定的历史数据和关于需要什么水平的足够历史支持的固定决策,可以计算出对于给定输入实际上“不允许”的一组动作。因此,通过使用 没收的偏移树,可以限制由此产生的学习策略获得足够的支持。

2010年9月19日,星期日

聚合没收偏移树

在一个 以前的帖子 我谈到了带有部分反馈的成本敏感型最佳m(CSBM)。想法是选择一组动作,其中该组的奖励是各个元素奖励的总和。我之前考虑过的部分反馈的性质是,只揭示了所选动作组的奖励,但是揭示了该组动作中的每个奖励。另一个可能的情况是,仅揭示所选动作组的总奖励。这比较困难,因为它既是部分反馈又是汇总反馈。但是,在我目前的工作中,存在一个问题,即要优化一组页面元素,但是用户只能通过一种方式与页面进行积极的交互,即,各个页面组件是决策的单元,而不是决策单元。用户反馈的单位。如果所讨论集合的基数很小,则可以将整个集合视为动作并直接利用偏移树。对于我在这里处理的第一个问题,有$ {9 \ choose 2} = 36 $个组合,因此这是完全可行的。占据页面的更多部分可能会将其扩大2或3个数量级,但是我有很多数据,因此也许仍然可以使用。

不过,还是有痒的感觉,我希望使用$ \ ldots $ 偏移树 方法,但对于未设置的单个动作,请使用 约束CSBM约束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]。 \]我假设历史策略在给定实例$ p(\ mathcal {A} | x,\ omega)$的情况下,在操作的力量集合上使用了已知的条件分布。我将使用缩写$ \ mathcal {A} $来指代$ \ mathcal {P}(A)$的实现。而不是包含$ \ mathcal {A} $每个元素的奖励的历史数据,而是只有$ \ sum_ {a \ in \ mathcal {A}} r(a)$。
算法:汇总没收偏移树火车
数据: 受约束的CSMC具有汇总反馈培训数据集$ S $。
输入: 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
结果: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
  1. 从叶子到根的每个$ n \ in \ Lambda(T)$:
    1. $ S_n = \ emptyset $。
    2. 对于每个示例$ \ left(x,\ omega,\ mathcal {A},\ sum_ {a \ in \ mathcal {A}}} r(a),p(\ cdot | x,\ omega)\ right)\ in带$ \ mathcal {A}的S $ \ cap \ omega = \ emptyset $:
      1. 假设$ \ lambda $和$ \ phi $是输入到$ n $的两个类(分别预测输入$(x,\ omega)$的左和右子树)。
      2. 如果$ \ lambda \ in \ omega $,预测$ \ phi $以便为父节点构建训练输入(``$ \ lambda $ forfeits'');
      3. 否则,如果$ \ phi \ in \ omega $,预测$ \ lambda $以便为父节点构建训练输入(``$ \ phi $ forfeits'');
      4. 否则(($ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $))或($ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $):
        1. 让\ [\ alpha = {| A \ setminus \ omega | -2 \ choose | \ mathcal {A} | -1} ^ {-1} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset}(1 _ {\ lambda \ in \ mathcal { A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}})\ right]} { E _ {\ mathcal {A} ^ \ prime \ sim p} [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]}。 \]
        2. 如果$ \ sum_ {a \ in \ mathcal {A}} r(a) <\ frac {| \ mathcal {A} |} {2} $,$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1 _ {\ phi \ in \ mathcal {A}},\ alpha \ left( \ frac {| \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r(a)\ right)\ right)\ right \} $;
        3. else $ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1 _ {\ lambda \ in \ mathcal {A}},\ alpha \ left(\ sum_ {a \ in \ mathcal {A}}} r(a )-\ frac {| \ mathcal {A} |} {2} \ right)\ right)\ right \} $。
    3. 令$ \ Psi_n = \ mbox {Learn}(S_n)$。
  2. 返回$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
评论: 这假设一个历史策略,其中$ | \ mathcal {A} | $几乎可以肯定是一个常数,并且所有可行集都具有正概率。
算法:汇总没收偏移树测试
输入: 带有内部节点$ \ 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 $。

激励更新

基本思想是将总奖励用作偏移树中的信号,但仅当一个节点的输入(而非全部)都在一组动作中时才进行归因。利用过滤树样式后悔约束证明策略的关键是确保内部节点上的预期重要性权重差等于对该节点的两个输入而言的策略后悔。由于总奖励是各个奖励的线性组合,因此可以通过评估与相同动作同时出现的动作值之间的差异来比较动作值。选择该更新,使得当采用期望时,仅在输入到特定节点的动作上不同的集合组合以有助于期望的重要性权重差。

对于固定的$(x,\ omega,r)$和一个内部节点,其左输入$ \ lambda \ not \ in \ omega $和右输入$ \ phi \ not \ in \ omega $, $ \ lambda $的预期重要性权重为\ [
\ begin {aligned}
w _ {\ lambda | r}&= \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal { A}} 1 _ {\ phi \ not \ in \ mathcal {A}} \ alpha _ {\ lambda,\ neg \ phi} \ left(\ sum_ {a \ in \ mathcal {A}} r(a)-\ frac {| \ mathcal {A} |} {2} \ right)_ + \ right]} {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset } 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \在\ mathcal {A}}中1 _ {\ phi \在\ mathcal {A}}中\ right]} \\
&\ quad + \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ alpha _ {\ neg \ lambda,\ phi} \ left(\ frac {| \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal { A}} r(a)\ right)_ + \ right]} {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A }} 1 _ {\ phi \ in \ mathcal {A}} \ right]},
\ end {aligned}
\]其中$(x)_ + = \ max(x,0)$和$ \ alpha _ {\ lambda,\ neg \ phi} $和$ \ alpha _ {\ neg \ lambda,\ phi} $确定比例因子。这表明\ [
\ alpha _ {\ neg \ lambda,\ phi} = \ alpha _ {\ lambda,\ neg \ phi} \ propto \ begin {cases} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} {E _ {\ mathcal {A} ^ \ prime \ sim p} [ 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]}& \mbox{if } E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A} \cap \omega = \emptyset} 1_{\mathcal{A}^\prime = \mathcal{A}} ] >0; \\ 0&\ mbox {否则},\ end {cases}
\]产生\ [
\ begin {aligned}
w _ {\ lambda | r}&\ proto \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ lambda,\ neg \ phi}} \ left(\ sum_ {a \ in \ mathcal {A}} r(a )-\ frac {| \ mathcal {A} |} {2} \ right)_ + + \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ neg \ lambda,\ phi}}} left(\ frac { | \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r(a)\ right)_ +,\\
w _ {\ phi | r}&\ propto \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ neg \ lambda,\ phi}} \ left(\ sum_ {a \ in \ mathcal {A}} r(a )-\ frac {| \ mathcal {A} |} {2} \ right)_ + + \ sum _ {\ mathcal {A} \ in \ Upsilon _ {\ lambda,\ neg \ phi}}} left(\ frac { | \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r(a)\ right)_ +,\\
\ end {aligned}
\] \\
\ begin {aligned}
\ Upsilon _ {\ lambda,\ neg \ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \in \mathcal{A}, \phi \not \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}, \\
\ Upsilon _ {\ neg \ lambda,\ phi}&= \{ \mathcal{A} | \mathcal{A} \cap \omega = \emptyset, \lambda \not \in \mathcal{A}, \phi \in \mathcal{A}, E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A}^\prime = \mathcal{A}} ] > 0 \}.
\ end {aligned}
\]现在,如果并且仅在历史策略下可能用$ \ lambda $而不是$ \ phi $的集合在历史策略下是可能的,并且只有我将用$ \ Upsilon _ {\ lambda,\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda,\ phi} $表示,那么预期的重要权重差为\ [
w _ {\ lambda | r}-w _ {\ phi | r} \ propto | \ Upsilon | \ left(r(\ lambda)-r(\ phi)\ right),
\] 和refore the proper choice when $|\Upsilon_{\lambda,\neg \phi}| =| \ Upsilon _ {\ neg \ lambda,\ phi} ||\doteq |\Upsilon| > 0$ is \ [
\ alpha _ {\ phi,\ neg \ lambda} = \ alpha _ {\ lambda,\ neg \ phi} = \ begin {cases} | \ Upsilon | ^ {-1} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} {E _ {\ mathcal {A} ^ \ prime \ sim p} [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]}& \mbox{if } E_{\mathcal{A}^\prime \sim p} [ 1_{\mathcal{A} \cap \omega = \emptyset} 1_{\mathcal{A}^\prime = \mathcal{A}} ] >0; \\ 0和\ mbox {否则}。 \ end {cases}
\]在最简单的情况下,在历史政策下所有完全可行的集合都具有正概率,并且由历史政策构造的所有集合都具有相同的$ | \ mathcal {A} | $,然后$ | \ Upsilon | = {| A \ setminus \ omega | -2 \ choose | \ mathcal {A} | -1} $。

在某些情况下,可以遵循不遵循$ \ Upsilon _ {\ lambda,\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda,\ phi} $的历史策略 通过拒绝修改 历史数据的一部分变成有效的历史策略,该策略确实遵循$ \ Upsilon _ {\ lambda,\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda,\ phi} $。

后悔分析

总计没收偏移树的后悔分析与没收偏移树的后悔分析几乎相同。

令$ \ 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(\ mathcal {A} | x,\ omega)$中绘制$ \ mathcal {A} $。
    2. 如果$ \ mathcal {A} \ cap \ omega \ neq \ emptyset $,则拒绝样本;
    3. 否则(($ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $))或($ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $):
      1. 让\ [\ alpha = | \ Upsilon | ^ {-1} \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset}(1_ { \ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A} }} \ right]} {E _ {\ mathcal {A} ^ \ prime \ sim p} [1 _ {\ mathcal {A} \ cap \ omega = \ emptyset} 1 _ {\ mathcal {A} ^ \ prime = \ mathcal {A}}]},\],其中$ | \ Upsilon | $为 以上定义.
      2. 如果$ \ sum_ {a \ in \ mathcal {A}} r(a) <\ frac {| \ mathcal {A} |} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1 _ {\ phi \ in \ mathcal {A}},\ alpha \ left( \ frac {| \ mathcal {A} |} {2}-\ sum_ {a \ in \ mathcal {A}} r(a)\ right)\ right); \]
      3. 否则(当$ \ sum_ {a \ in \ mathcal {A}} r(a)\ geq \ frac {| \ mathcal {A} |} {2} $)时,创建重要性加权的二进制示例\ [\ left( x ^ \ prime,1 _ {\ lambda \ in \ mathcal {A}},\ alpha \ left(\ sum_ {a \ in \ mathcal {A}} r(a)-\ frac {| \ mathcal {A} | } {2} \ right)\ right); \]
    4. 否则拒绝样品。
诱导分布$ 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 $,这样对于所有对动作$ \ lambda $和$ \ phi $,$ \ Upsilon _ {\ lambda,\ neg \ phi} \ sim \ Upsilon _ {\ neg \ lambda,\ phi} \ neq \ emptyset $,只要$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $,并且使得$ E _ {\ mathcal {A} \ sim p} [1_ {a \ in \ mathcal { A}} | x,\ omega]>每当$ a \ not \ in \ omega $时为0 $;以及所有合计没收的偏移树$ \ Psi $,\ [v(h ^ \ Psi)\ leq(| A |-1)q(\ Psi),\]其中$ q(\ Psi)$是重要性加权关于引起的子问题的二元遗憾。

证明: 看到 附录.
尽管这很整洁,但仍然存在缺陷:在以前的情况下,确定对特定动作进行惩罚的约束似乎很自然,但是在这里,更合理的情况是对特定动作组合进行惩罚。它开始看起来像是随机最短路径(SSP),而没有求助于部分(汇总?)反馈和未完全连接的图。在OR中,它们减少了SSP的许多问题,因此,既然我对偏移树有了更好的命令,也许是时候重新访问SSP了。

附录

这就是后悔的证明。

考虑一个固定的$(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 $为条件的期望重要性权重满足\ [| 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)$完成证明。

2010年9月15日,星期三

具有部分反馈的受限成本敏感型最佳M

在一个 以前的帖子 I talked about constrained 成本敏感性最佳 (CSBM) and one way to reduce to constrained cost-sensitive multiclass classification (CSMC). CSBM is about choosing the best set of choices when the rewards of a set is the sum of the rewards of the elements, 和 reduction to 华润上华 works by ``选择最佳选择,然后选择下一个最佳选择,依此类推''. Since then I've played with the 偏移树,这是针对历史数据包含部分反馈的问题而设计的(即,仅针对所采取的措施才显示奖励)。现在该进行混搭了,即使用部分反馈约束CSBM。

约束CSBM定义如下。有一个分布$ D = D_x \ times D _ {\\ omega | x} \ times D_ {r | \ omega,x} $,其中$ r:A \ to [0,1] \ cup \ {-\ infty \ } $以单位间隔中的值加上$-\ infty $来获取值,并且通过$ \ omega \ in将特定实例的$ r $的分量作为$-\ infty $值显示为问题实例的一部分。 \ mathcal {P}(A)$(即$ \ omega $是$ A $的子集)。响应问题实例所允许的输出是大小为$ m $的$ A $子集,表示为\ [S_m = \ {S | S \ subseteq A,| S | = m \}。\]特定确定性策略$ h的遗憾:X \ times \ mathcal {P}(A)\ to S_m $由\ [v(h)= E _ {(x,\ omega) \ sim D_x \ times D _ {\ omega | x}} \ left [\ max_ {s \ in S_m} \; E_ {r \ sim D_ {r | \ omega,x}} \ left [\ sum_ {a \ in s} r(a)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \左[\ sum_ {a \ in h(x,\ omega)} r(a)\ right] \ right]。 \]注意$ | A \ setminus \ omega |时<m $,任何策略都实现零遗憾(通过$-\ infty $奖励);因此,问题空间的“有趣”部分是当$ | A \ setminus \ omega |时。 \ geq m $。

对于带有部分反馈的CSBM,存在两种可能的情况。
  1. 仅观察到与所选动作集相关的总奖励。在我当前的工作中,实际上存在此问题的一个版本,因为网站上有一个页面,其各个元素旨在共同作用以引起单个响应。
  2. 观察与选择的每个动作相关的奖励。例如,广告通常是在一组中选择的,但是会提供个性化的反馈。
好吧,我想了解第一种情况,但是我需要建立一些直觉,因此我将专注于第二种(容易的)情况。我假设历史策略在给定实例$ p(\ mathcal {A} | x,\ omega)$的情况下,在操作的幂集上使用了已知的条件分布。我将使用缩写$ \ mathcal {A} $来指代$ \ mathcal {P}(A)$的实现。

减少的过程如下:首先选择最高的奖励选择,然后将其奖励调整为$-\ infty $,然后重复此过程,直到获得一组大小$ m $。各个步骤都被认为是具有部分反馈(CSMC-PF)问题的约束CSMC,本质上是$ m = 1 $的CSBM。的 没用的滤波偏移树 是为受限的CSMC-PF设计的,尤其可以用作下面的$ \ mbox {Learn} $ oracle。没用的滤波偏移树具有始终获得有限遗憾的特性,即,只要有可能,就选择可行的类。在这种情况下,这意味着子问题将永远不会创建重复项。
算法:部分反馈集选择火车
输入: 动作标签$ A $,(用于选择的最大大小)$ m \ leq | A | / 2 $。
输入: 受约束的CSMC-PF分类器$ \ mbox {Learn} $。
数据: 训练数据集$ S $。
结果: 经过训练的分类器$ \ {\ Psi_n | n \ in [1,m] \} $。
  1. 定义$ \ gamma_0(\ cdot,\ cdot)= \ emptyset $。
  2. 对于从$到$ m $的每个$ n $:
    1. $ S_n = \ emptyset $。
    2. 对于每个示例$ \ bigl(x,\ omega,\ mathcal {A},\ {r(a)| a \ in \ mathcal {A} \},p(\ cdot | x,\ omega)\ bigr)\以S $为单位,使得$ | A \ setminus \ omega | \ geq m $:
      1. 令$ \ gamma_ {n-1}(x,\ omega)$为上一次迭代的最佳预测集。
      2. 对于每个动作$ a $:
        1. 如果$ a \ in \ gamma_ {n-1}(x,\ omega)$,$ r(n,a)=-\ infty $;
        2. 否则$ r(n,a)= r(a)$。
      3. $ S_n \ leftarrow S_n \ cup \ left \ {\ bigl(x,\ omega \ cup \ gamma_ {n-1}(x),\ mathcal {A},\ {r(n,a)| a \ in \ mathcal {A} \},p(\ cdot | x,\ omega)\ bigr)\ right \} $。
    3. 令$ \ Psi_n = \ mbox {Learn}(S_n)$。
    4. 令$ \ gamma_n(x)= \ Psi_n(x)\ cup \ gamma_ {n-1}(x)$。
  3. 返回$ \ {\ Psi_n | n \ in [1,m] \} $。
评论: 如果$ m>| A | / 2 $,取反所有有限奖励,并选择大小为|| A |的补数-m $。
算法:设置选择测试
数据: 类标签$ A $,要填充的位置数$ l \ leq m \ leq | A | / 2 $。
数据: 实例特征实现$(x,\ omega)$。
数据: 经过训练的分类器$ \ {\ Psi_n | n \ in [1,m] \} $。
结果: 将$ h ^ \ Psi:X \设置为S_l $。
  1. $ \ gamma_0 ^ \ Psi(x,\ omega)= \ emptyset $。
  2. 对于$ n $从1到$ l $:
    1. $ \ gamma_n ^ \ Psi(x,\ omega)= \ gamma_ {n-1} ^ \ Psi(x,\ omega)\ cup \ Psi_n(x,\ omega \ cup \ gamma_ {n-1} ^ \ Psi (x,\ omega))$。
  3. 如果$ | \ gamma_l ^ \ Psi(x,\ omega)| = l $,$ h ^ \ Psi(x,\ omega)= \ gamma_l ^ \ Psi(x,\ omega)$;
  4. 否则将$ h ^ \ Psi(x,\ omega)$设置为$ S_l $的任意元素。
评论: 如果$ l \ geq m>| A | / 2 $,否定所有有限成本,并选择大小为|| A |的补数-l $。
部分反馈集选择训练算法会忽略$ | A \ setminus \ omega |中的训练数据<m $,但是对于这样的输入,任何策略都会获得负的无限回报和零后悔,因此学习毫无意义。同样,当$ | A \ setminus \ omega |时,也不会定义Set Select Test算法。<l \ leq m $,但是对于这样的输入,任何策略都会获得负的无限奖励和零后悔,因此出于后续分析的目的,我假设我们在$ S_l $中选择一个任意元素。

我的目标是约束受约束的平均CSBM后悔\ [v(h)= E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [\ max_ {s \ in S_m} \ ; E_ {r \ sim D_ {r | \ omega,x}} \ left [\ sum_ {a \ in s} r(a)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \左[\ sum_ {a \ in h(x,\ omega)} r(a)\ right] \ right] \]的平均约束CSMC对引起的子问题的遗憾。我将再次利用过滤器树派生的技巧,通过定义归纳分布将多个子问题折叠为一个子问题。令$ D $为平均约束CSBM实例$(x,\ omega,r)$的分布。定义归纳分布$ D ^ \ prime(\ Psi,l)$,其中$ l \ leq m $受约束的CSMC-PF实例$ {x ^ \ prime,\ omega ^ \ prime,\ mathcal {A},\ { r ^ \ prime(a)| a \ in \ mathcal {A} \},p ^ \ prime(\ cdot | x ^ \ prime,\ omega ^ \ prime))$。
  1. 从$ D $绘制$(x,\ omega,r)$。
  2. 在$ [1,l] $上绘制$ n $制服。
  3. 设$ x ^ \ prime =(x,n)$。
  4. 令$ \ omega ^ \ prime = \ omega \ cup \ gamma_ {n-1}(x,\ omega)$。
  5. 对于每个动作$ a $:
    1. 如果$ a \ in \ gamma_ {n-1}(x,\ omega)$,$ r ^ \ prime(a)=-\ infty $;
    2. 否则$ r ^ \ prime(a)= r(a)$。
  6. 令$ p ^ \ prime(\ cdot | x ^ \ prime,\ omega ^ \ prime)= p(\ cdot | x,\ omega)$。
  7. 创建受约束的CSMC-PF示例$(x ^ \ prime,\ omega ^ \ prime,\ mathcal {A},\ {r ^ \ prime(a)| a \ in \ mathcal {A} \},p ^ \ prime (\ cdot | x ^ \ prime,\ omega ^ \ prime))$。
注意$ D ^ \ prime(\ Psi,l)$通过重复惩罚取决于分类器,但是对于任何固定的分类器来说,定义都很好。最终,我想将平均约束CSBM后悔$ v(h ^ \ Psi)$与诱发的CSMC后悔\ [\ begin {align} q(\ Psi,l)相关联&= E_{(x^\prime, \omega^\prime) \sim D^\prime_{x^\prime, \omega^\prime} (\Psi, l) } \left[ \max_{a \in A}\;E_ {r ^ \ prime \ sim D ^ \ prime_ {r ^ \ prime | \ omega ^ \ prime,x ^ \ prime}(\ Psi,l)} \ left [r(a)\ right]-E_ {r ^ \ prime \ sim D ^ \ prime_ {r ^ \ prime | \ omega ^ \ prime,x ^ \ prime}(\ Psi,l)} \ left [r({\ Psi(x ^ \ prime,\ omega ^ \\ prime)})\ right] \ right] \\&= \frac{1}{l} \sum_{n=1}^l q_n (\Psi), \ end {aligned} \] \\ \ begin {aligned} q_n (\Psi) &= E_{(x, \omega) \sim D_{x,\omega}} [ q_n (\Psi | x, \omega) ], \\ q_n (\Psi | x, \omega) &= \max_{a \in A}\;E_ {r \ sim D_ {r | \ omega,x}} \ left [\ tilde r_n(a)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \ left [\ tilde r_n \ bigl(\ Psi_n(x,\ gamma_ {n-1}(x,\ omega))\ bigr)\ right],\\ \ tilde r_n(a)&= \begin{cases} -\infty & \mbox{if } a \in\gamma_{n-1} (x, \omega);\\ r(a)和\ mbox {否则}。 \ end {cases} \ end {aligned} \]
定理:遗憾的结界
对于所有平均约束CSBM分布$ D $和所有平均约束CSMC分类器$ \ Psi $,\ [v(h ^ \ Psi)\ leq l \,q(\ Psi,l)。 \] 证明: 看到 附录.
历史策略$ p $不会进入该定理,因为它作为``黑匣子''传递给CSMC-PF子问题。当然,当对子问题使用没用的过滤偏移量树时,为了根据子问题上引起的重要性加权二元后悔的遗憾来约束子问题后悔,历史策略必须服从$ E _ {\ mathcal {A} \ sim p} [1_ {a \ in \ mathcal {A}} | x,\ omega]>每当$ a \ not \ in \ omega $时为0 $。

此缩减的先前版本中的说明仍然适用。

当直接比较归约与回归($ \ sqrt {m} \ sqrt {| A |} \ sqrt {\ epsilon_ {L ^ 2}} $)与通过CSMC归纳还原($ m \ sqrt { | A |} \ sqrt {\ epsilon_ {L ^ 2}} $)。这表明有一种方法可以减少此问题,该方法仅利用$ \ sqrt {m} $ 华润上华子问题。效率低下的一种可能来源:减少是按顺序检索元素,而目标函数对顺序无动于衷。

后悔界限表示以下属性:一旦我训练了选择大小为$ m $的集合,对于任何$ l \ leq m $选择大小为$ l $的集合,我都会感到遗憾。这表明可以使用$ m = | A | $的变体将minimax约束的CSMC-PF减小为平均约束的CSMC-PF。我将在以后的博客文章中对此进行探讨。

附录


这就是后悔的证明。

如果$ \ Psi $在引起的子问题上获得无限的后悔,则界限将微不足道。因此,考虑达到有限遗憾的$ \ Psi $。

如果$ | A \ setminus \ omega |<l $,然后$ v = 0 $(对于$ S_l $中的任何选择),并且该边界有条件地成立。因此考虑$ | A \ setminus \ omega | \ geq l $:由于$ \ Psi $获得有限的遗憾,因此任何子分类器均不会生成重复项,并且$ h ^ \ Psi(x,\ omega)= \ gamma ^ \ Psi_1(x,\ omega)$。

考虑带有$ | A \ setminus \ omega |的固定$(x,\ omega)$ \ geq l $。讨论\ [v(h | x,\ omega,n)= \ max_ {s \ in S_m} \很方便; E_ {r \ sim D_ {r | \ omega,x}} \ left [\ sum_ {a \ in s} r(a)\ right]-E_ {r \ sim D_ {r | \ omega,x}} \左[\ sum_ {a \ in \ gamma ^ \ Psi_n(x,\ omega)} r(a)\ right],\]该实例在部分$ n ^ \ mathrm {th} $步骤中的条件后悔反馈集选择测试。令\ [s ^ *(x,\ omega,n)= \ underset {s \ in S_m} {\ operatorname {arg \,max \,}} E_ {r \ sim D_ {r | \ omega,x}} \ left [\ sum_ {a \ in s} r(a)\ right] \]是第一项的任何最大化器(在关系中是唯一的);注意,任何$ s ^ *(x,\ omega,n)$都会选择$ n $个类别,以提供最大的条件期望奖励。

证明是通过证明属性$ v(h ^ \ Psi | x,\ omega,n)\ leq \ sum_ {r = 1} ^ n q_r(\ Psi,l)$。该属性相等地持有$ n = 1 $。对于$ n >1 $ note \ [\ begin {aligned} v(h ^ \ Psi | x,\ omega,n)-v(h ^ \ Psi | x,\ omega,n-1)&= \ max_ {a \ in A \ setminus s ^ *(x,\ omega,n-1)} E_ {r \ sim D_ {r | \ omega,x}} \ left [r(a)\ right] \\&\ quad-E_ {r \ sim D_ {r | \ omega,x}} \ left [r \ left(\ Psi_n \ left(x,\ omega \ cup \ gamma ^ \ Psi_ {n-1}(x,\ omega)\ right)\ right)\ right],\\&\ leq \ max_ {a \ in A \ setminus \ gamma ^ \ Psi_ {n-1}(x,\ omega)} E_ {r \ sim D_ {r | \ omega,x }} \ left [r(a)\ right] \\&\ quad-E_ {r \ sim D_ {r | \ omega,x}} \ left [r \ left(\ Psi_n \ left(x,\ omega \ cup \ gamma ^ \ Psi_ {n-1}(x,\ omega)\ right)\ right)\ right],\\\&\ leq \ max_ {a \ in A \ setminus \ gamma ^ \ Psi_ {n- 1}(x,\ omega)} E_ {r \ sim D_ {r | \ omega,x}} \ left [\ tilde r_n(a)\ right] \\&\ quad-E_ {r \ sim D_ {r | \ omega,x}} \ left [\ tilde r_n \ left(\ Psi_n \ left(x,\ omega \ cup \ gamma ^ \ Psi_ {n-1}(x,\ omega)\ right)\ right)\右],\\&= q_n(\ Psi,l | x,\ omega),\ end {aligned} \]其中第二个不等式是由于$ s ^ *(x,\ omega,n-1 )$和第三个不等式是beca如果$ a \ not \ in \ gamma ^ \ Psi_ {n-1}(x,\ omega)$,则使用$ \ tilde r_n(a)\ leq r(a)$等价。对伸缩级数求和建立\ [v(h ^ \ Psi | x,\ omega)= v(h ^ \ Psi | x,\ omega,l)\ leq \ sum_ {r = 1} ^ l q_r(\ Psi, l | x,\ omega)= l \,q(\ Psi,l | x,\ omega)。 \]对$ D_ {x,\ omega} $取期望值即可完成证明。

2010年9月13日,星期一

没收的滤波器偏移树

他们说,随着描述中形容词数量的减少,互联网公司的价值也随之上升。我希望在机器学习中并非如此!

所以当我尝试减少时,我遇到的第一件事 平均约束成本敏感最佳 将部分反馈转换为带有部分反馈的平均受限成本敏感型多类分类(CSMC-PF)的原因是,鉴于我设置子问题的方式,每个历史实例通常揭示的奖励向量中不止一个元素。需要的是将 没收过滤树没收的偏移树,当内部节点的两个输入都显示了值时,它将使用丧失的过滤树更新,否则,只有内部节点的一个输入被揭示时,将使用丧失的偏移树更新。

平均受限CSMC-PF设置如下。有一个分布$ 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]。 \]在训练数据中,只有部分反馈可用,但与 以前的帖子 我假设奖励向量的潜在多个元素被揭示。我假设历史策略在给定实例$ p(\ mathcal {A} | x,\ omega)$的情况下,在操作的幂集上使用了已知的条件分布。我将使用缩写$ \ mathcal {A} $来指代$ \ mathcal {P}(A)$的实现。
算法:没收滤胶偏移树火车
数据: 受约束的CSMC-PF训练数据集$ S $。
输入: 重要性加权的二进制分类程序$ \ mbox {Learn} $。
输入: 带有内部节点$ \ Lambda(T)$的标签上的二叉树$ T $。
结果: 经过训练的分类器$ \ {\ Psi_n | n \ in \ Lambda(T)\} $。
  1. 从叶子到根的每个$ n \ in \ Lambda(T)$:
    1. $ S_n = \ emptyset $。
    2. 对于每个示例$(x,\ omega,\ mathcal {A},\ {r(a)| a \ in \ mathcal {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 \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $
        1. $ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1_ {r(\ lambda)>r(\ phi)},| r(\ lambda)-r(\ phi)| \ right)\ right \} $。
      5. 否则,如果$ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $:
        1. 如果$ r(\ lambda)<\ frac {1} {2} $,$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,0,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}]} \ left(\ frac {1} {2} -r(\ lambda)\ right)\ right)\ right \} $;
        2. else $ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p } [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}]} \ left(r(\ lambda)-\ frac {1} {2} \ right) \ right)\ right \} $。
      6. 否则,如果\\ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $:
        1. 如果$ r(\ phi)<\ frac {1} {2} $,$ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,1,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} \ left(\ frac {1} {2} -r(\ phi)\ right)\ right)\ right \} $;
        2. else $ S_n \ leftarrow S_n \ cup \ left \ {\ left(x,0,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p } [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} \ left(r(\ phi)-\ 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 $。

激励更新

利用过滤树样式后悔约束证明策略的关键是确保内部节点上的预期重要性权重差等于对该节点的两个输入而言的策略后悔。当两个奖励值都已知时,过滤器树更新通过区别输入直接完成工作。当仅知道一个奖励值时,偏移树更新将根据观察的相对概率进行加权,从而得出正确的结果。想象一下两者的结合,以$(x,\ omega,r)$和$ \ lambda \ not \ in \ omega $和$ \ phi \ not \ in \ omega $为条件的左输入的预期重要性权重为\ [\ begin {aligned} w _ {\ lambda | r}&= E_{\mathcal{A}\sim p} \biggl[ 1_{\lambda \in \mathcal{A}} 1_{\phi \not \in \mathcal{A}} 1_{r (\lambda) \geq \frac{1}{2}} \alpha_{\lambda, \neg \phi} \left( r (\lambda) - \frac{1}{2} \right) \\ &\quad \quad \quad \quad + 1_{\lambda \not \in \mathcal{A}} 1_{\phi \in \mathcal{A}} 1_{r (\phi) <\ frac {1} {2}} \ alpha _ {\ neg \ lambda,\ phi} \ left(\ frac {1} {2}-r(\ phi)\ right)\\&\quad \quad \quad \quad + 1_{\lambda \in \mathcal{A}} 1_{\phi \in \mathcal{A}} 1_{r (\lambda) >r(\ phi)} \ alpha _ {\ lambda,\ phi} \ bigl(r(\ lambda)-r(\ phi)\ bigr)\ biggr] \ biggl / \\&\quad \quad E_{\mathcal{A} \sim p} \left[ 1_{\lambda \in \mathcal{A}} + 1_{\phi \in \mathcal{A}} - 1_{\lambda \in \mathcal{A}} 1_{\phi \in \mathcal{A}} \right], \ end {aligned} \] where $\alpha_{\lambda,\neg \phi}$ is a (to be determined) scaling factor for when only $\lambda$ is observed and exceeds $\frac{1}{2}$ or when only $\phi$ is observed and does not exceed $\frac{1}{2}$;$ \ alpha _ {\ neg \ lambda,\ phi} $用于仅观察到$ \ phi $并且超过$ \ frac {1} {2} $,或者仅观察到$ \ lambda $并且不超过$ \ frac {1} {2} $;和$ \ alpha _ {\ lambda,\ phi} $适用于同时观察到$ \ lambda $和$ \ phi $的情况。检查表明\ [\ begin {aligned} \ alpha _ {\ lambda,\ neg \ phi}&=(1- -gamma)\ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ lambda \在\ mathcal {A}} + 1 _ {\ phi \ in \ mathcal {A}}中-1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} { E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}]},\\ \ alpha _ {\ neg \ lambda ,\ phi}&=(1- -gamma)\ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ lambda \ in \ mathcal {A}} + 1 _ {\ phi \ in \ mathcal {A}}-1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}} \ right]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]},\\ \ alpha _ {\ lambda,\ phi}&= \ gamma \ frac {E _ {\ mathcal {A} \ sim p} \ left [1 _ {\ lambda \ in \ mathcal {A}} + 1 _ {\ phi \ in \ mathcal {A}}-1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \在\ mathcal {A}} \ right]}中{E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} ,\ end {aligned} \]对于任何$ \ gamma \ in [0,1] $,将导致\ [\ begin {aligned} w _ {\ lambda | r}&=(1-\ gam ma)\ left(r(\ lambda)-\ frac {1} {2} \ right)_ + +(1-\ gamma)\ left(\ frac {1} {2}-r(\ phi)\ right )_ + + \ gamma \ bigl(r(\ lambda)-r(\ phi)\ bigr)_ +,\\ w _ {\ phi | r}&=(1-\ gamma)\ left(r(\ phi )-\ frac {1} {2} \ right)_ + +(1-\ gamma)\ left(\ frac {1} {2}-r(\ lambda)\ right)_ + + \ gamma \ bigl( r(\ phi)-r(\ lambda)\ bigr)_ +,\\ w _ {\ lambda | r}-w _ {\ phi | r}&= r(\ lambda)-r(\ phi)。 \ end {aligned} \] $ \ gamma $呢?我没有选择任何理论上的理由,我只是想将$ \ gamma $设置为过滤器更新的相对概率将给出正确的限制行为(即,在给出相应$ p的情况下,精确地重现偏移量或过滤树( \ mathcal {A} | x,\ omega)$)。这意味着\ [\ gamma = \ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} \ left [1 _ {\ lambda \ in \ mathcal {A}} + 1 _ {\ phi \ in \ mathcal {A}}-1 _ {\ lambda \ in \ mathcal {A} } 1 _ {\ phi \ in \ mathcal {A}} \ right]},\]和\ [\ begin {aligned} \ alpha _ {\ lambda,\ neg \ phi}&= \ frac {E _ {\ mathcal {A } \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} ]},\\ \ alpha _ {\ neg \ lambda,\ phi}&= \ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}}} 1 _ {\ phi \不是\ in \ mathcal {A}} + 1 _ {\ lambda \不是\ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]},\\ \ alpha _ {\ lambda,\ phi}&=1。\ end {aligned} \]另一个想法是选择$ \ gamma $以使期望的重要性权重最小化,但是我没有任何结果e行。

后悔分析

没收滤波器偏移树的后悔分析与没收偏移树的后悔分析几乎相同。

令$ \ 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(\ mathcal {A} | x,\ omega)$中绘制$ \ mathcal {A} $。
    2. 如果$ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $,则拒绝样本;
    3. 否则,如果$ \ lambda \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $,则创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1_ {r(\ lambda)>r(\ phi)},| r(\ lambda)-r(\ phi)| \对);\]
    4. 否则,如果$ \ lambda \ in \ mathcal {A} $和$ \ phi \ not \ in \ mathcal {A} $:
      1. 如果$ r(\ lambda)<\ frac {1} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,0,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}]} \ left(\ frac {1} {2} -r(\ lambda)\ right)\ right); \]
      2. 否则(当$ r(\ lambda)\ geq \ frac {1} {2} $)时,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}}] } \ left(r(\ lambda)-\ frac {1} {2} \ right)\ right); \]
    5. 其他(当$ \ lambda \ not \ in \ mathcal {A} $和$ \ phi \ in \ mathcal {A} $中时):
      1. 如果$ r(\ phi)<\ frac {1} {2} $,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,1,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E_ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} \ left(\ frac {1} {2} -r(\ phi)\ right)\ right); \]
      2. 否则(当$ r(\ phi)\ geq \ frac {1} {2} $)时,创建重要性加权的二进制示例\ [\ left(x ^ \ prime,0,\ frac {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ in \ mathcal {A}} 1 _ {\ phi \ not \ in \ mathcal {A}} + 1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}]} {E _ {\ mathcal {A} \ sim p} [1 _ {\ lambda \ not \ in \ mathcal {A}} 1 _ {\ phi \ in \ mathcal {A}}] } \ left(r(\ phi)-\ 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 $,例如$ E _ {\ mathcal {A} \ sim p} [1_ {a \ in \ mathcal {A}} | x,\ omega] >每当$ a \ not \ in \ omega $时为0 $;以及所有没收的滤波器偏移树$ \ Psi $,\ [v(h ^ \ Psi)\ leq(| A |-1)q(\ Psi)\]其中$ q(\ Psi)$是重要性加权关于引起的子问题的二元遗憾。
证明: 看到 附录.

对于偏移树设置,每个实例仅显示一个奖励成分,$(| A |-1)$依赖性很严格。另一方面,如果每个实例都显示了所有奖励组成部分,则减少的结果会令人遗憾,与操作数无关。我怀疑偏移量树纸的下限可以概括为$ | \ mathcal {A} | $的分布的函数。实际上,这意味着当每个历史实例显示多于1个奖励时,与没收的偏移树不同的是,没收的过滤器偏移树不会``尽其所能''。

好了,现在我准备看一下具有部分反馈的对成本敏感的最佳产品。

附录

这就是后悔的证明。

考虑一个固定的$(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 $为条件的期望重要性权重满足\ [| 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)$完成证明。

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)$完成证明。

2010年9月8日,星期三

受约束的最佳M:减少受约束的CSMC

在上一篇文章中,我谈到了 广告选择问题,我现在更喜欢将其称为成本敏感的最佳m(CSBM),因为实际的广告选择要复杂得多。 CSBM类似于成本敏感的多类分类(CSMC),在该类中必须选择$ m $个唯一类,目标是使总成本最小化。在之前的文章中,我将CSBM降低为CSMC,但是这种降低有些折磨:首先,所有成本都必须以一个常数为上限。其次,该算法可能仍会生成重复项,因此包括一个随机步骤以增强可行性。第三,分析的混乱之处在于随机化步骤的含义。

从那以后我介绍了 受约束的CSMC,就像香草CSMC一样,但是某些类被禁止作为实例规范的一部分。约束CSMC的设计目标是简化CSBM的减少,但是它的作用要稍微多一些。实际上,它使我可以定义从平均约束CSBM减少到平均约束CSMC的减少,并且由于CSBM是平均约束CSBM的特例,因此可以实现我最初的目标以及加成。

平均约束CSBM定义如下。有一个分布$ D = D_x \ times D _ {\\ omega | x} \ times D_ {c | \ omega,x} $,其中$ c:K \ to \ mathbf {R} $取扩展实数$中的值\ mathbf {R} = \ mathbb {R} \ cup \ {\ infty \} $,并且对于特定实例,$ c $的值是$ \ infty $的分量作为问题实例的一部分通过$显示出来。 \ omega \ in \ mathcal {P}(K)$(即$ \ omega $是$ K $的子集)。响应问题实例所允许的输出是大小为$ m $的$ K $子集,表示为\ [S_m = \ {S | S \ subseteq K,| S | = m \}。\]特定分类器$ h的遗憾:X \ times \ mathcal {P}(K)\ to S_m $由\ [r_ {csbm}(h)= E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [E_ {c \ sim D_ {c | \ omega,x}} \ left [\ sum_ {k \ in h(x,\ omega)} c(k)\ right]-\ min_ {h \ in S_m} \,E_ {c \ sim D_ {c | \ omega,x}} \ left [\ sum_ {k \ in h} c(k)\ right ] \对]。 \]注意当$ | K \ setminus \ omega |<m $,任何策略都实现零后悔(通过$ \ infty $成本);因此,问题空间的“有趣”部分是$ | K \ setminus \ omega | \ geq m $。

减少处理了一个平均约束CSBM问题,并将其转换为一组平均约束CSMC问题。平均受约束的CSMC定义如下。有一个分布$ D = D_x \ times D _ {\\ omega | x} \ times D_ {c | \ omega,x} $,其中$ c:K \ to \ mathbf {R} $取扩展实数$中的值\ mathbf {R} = \ mathbb {R} \ cup \ {\ infty \} $,并且对于特定实例,$ c $的值是$ \ infty $的分量作为问题实例的一部分通过$显示出来。 \ omega \ in \ mathcal {P}(K)$(即$ \ omega $是$ K $的子集)。特定分类器$ h的遗憾:X \ times \ mathcal {P}(K)\ to K $由\ [r_ {av}(h)= E _ {(x,\ omega)\ sim D_x \ times给出D _ {\ omega | x}} \ left [E_ {c \ sim D_ {c | \ omega,x}} \ left [c(h(x,\ omega))-\ min_ {k \ in K} \ ,, E_ {c \ sim D_ {c | \ omega,x}} \ left [c(k)\ right] \ right] \ right]。 \]可以使用为不受约束的CSMC设计的减少量变体来攻击受约束的平均CSMC,例如 argmax回归 或者 过滤树。这些减少的性质是它们总是会感到有限的遗憾,即,只要有可能,他们都会选择可行的类别。在这种情况下,这意味着子问题将永远不会创建重复项。

减少的工作方式如下:首先选择成本最低的选项,然后将其成本调整为$ \ infty $,然后重复该过程,直到获得一组大小$ m $。减少幅度基本上与 以前的帖子,但将其限制为平均约束CSMC而不是不受约束的CSMC会带来一些好处:成本不必超出上述限制,并且可以自然地强制执行可行性。

算法:设置选择火车
输入: 类标签$ K $,用于选择$ m的(最大)集合的大小\ leq | K | / 2 $。
输入: 受约束的平均CSMC分类器$ \ mbox {Learn} $。
数据: 训练数据集$ S $。
结果: 经过训练的分类器$ \ {\ Psi_n | n \ in [1,m] \} $。
  1. 定义$ \ gamma_0(\ cdot,\ cdot)= \ emptyset $。
  2. 对于从$到$ m $的每个$ n $:
    1. $ S_n = \ emptyset $。
    2. 对于每个示例$(x,\ omega,c)\ in S $使得$ | K \ setminus \ omega | \ geq m $:
      1. 令$ \ gamma_ {n-1}(x,\ omega)$为上一次迭代的最佳预测集。
      2. 对于每个课程$ k $:
        1. 如果$ k \ in \ gamma_ {n-1}(x,\ omega)$,$ c(n,k)= \ infty $;
        2. 否则$ c(n,k)= c(k)$。
      3. $ S_n \ leftarrow S_n \ cup \ left \ {\ bigl(x,\ omega \ cup \ gamma_ {n-1}(x),c(n,\ cdot)\ bigr)\ right \} $。
    3. 令$ \ Psi_n = \ mbox {Learn}(S_n)$。
    4. 令$ \ gamma_n(x)= \ Psi_n(x)\ cup \ gamma_ {n-1}(x)$。
  3. 返回$ \ {\ Psi_n | n \ in [1,m] \} $。
评论: 如果$ m>| K | / 2 $,否定所有有限成本并选择大小为|| K |的补数-m $。

算法:设置选择测试
数据: 类标签$ K $,要填充的位置数$ l \ leq m \ leq | K | / 2 $。
数据: 实例特征实现$(x,\ omega)$。
数据: 经过训练的分类器$ \ {\ Psi_n | n \ in [1,m] \} $。
结果: 将$ h ^ \ Psi:X \设置为S_l $。
  1. $ \ gamma_0 ^ \ Psi(x,\ omega)= \ emptyset $。
  2. 对于$ n $从1到$ l $:
    1. $ \ gamma_n ^ \ Psi(x,\ omega)= \ gamma_ {n-1} ^ \ Psi(x,\ omega)\ cup \ Psi_n(x,\ omega \ cup \ gamma_ {n-1} ^ \ Psi (x,\ omega))$。
  3. 如果$ | \ gamma_l ^ \ Psi(x,\ omega)| = l $,$ h ^ \ Psi(x,\ omega)= \ gamma_l ^ \ Psi(x,\ omega)$;
  4. 否则将$ h ^ \ Psi(x,\ omega)$设置为$ S_l $的任意元素。
评论: 如果$ l \ geq m>| K | / 2 $,否定所有有限成本,并选择大小为|| K |的补数。 -l $。

设置选择训练算法会忽略训练数据,其中$ | K \ setminus \ omega |<m $,但是对于这样的输入,任何策略都可以实现无限的成本和零后悔,因此学习毫无意义。同样,当$ | K \ setminus \ omega |时,也不会定义Set Select Test算法。<l \ leq m $,但是对于这样的输入,任何策略都可以实现无限的成本和零后悔,因此出于后续分析的目的,我假设我们在$ S_l $中选择一个任意元素。

我的目标是约束受约束的平均CSBM后悔\ [r_ {csbm}(h)= E _ {(x,\ omega)\ sim D_x \ times D _ {\ omega | x}} \ left [E_ {c \ sim D_ {c | \ omega,x}} \ left [\ sum_ {k \ in h(x,\ omega)} c(k)\ right]-\ min_ {h \ in S_m} \,E_ {c \ sim D_ {c | \ omega,x}} \ left [\ sum_ {k \ in h} c(k)\ right] \ right] \]就受约束的CSMC对后继子问题的平均约束感到遗憾。我将再次利用过滤器树派生的技巧,通过定义归纳分布将多个子问题折叠为一个子问题。设$ D $为平均约束CSBM实例$(x,\ omega,c)$的分布。定义归纳分布$ D ^ \ prime(\ Psi,l)$,其中平均受约束的CSMC实例$(x ^ \ prime,\ omega ^ \ prime,c ^ \ prime)$$ l \ leq m $,如下所示:
  1. 从$ D $绘制$(x,\ omega,c)$。
  2. 在$ [1,l] $上绘制$ n $制服。
  3. 设$ x ^ \ prime =(x,n)$。
  4. 令$ \ omega ^ \ prime = \ omega \ cup \ gamma_ {n-1}(x,\ omega)$。
  5. 对于每个课程$ k $:
    1. 如果$ k \ in \ gamma_ {n-1}(x,\ omega)$,$ c ^ \ prime(k)= \ infty $;
    2. 否则$ c ^ \ prime(k)= c(k)$。
  6. 创建成本敏感的示例$(x ^ \ prime,\ omega ^ \ prime,c ^ \ prime)$。
注意$ D ^ \ prime(\ Psi,l)$通过重复惩罚取决于分类器,但是对于任何固定的分类器来说,定义都很好。最终,我想将平均约束CSBM后悔$ r_ {csbm}(h ^ \ Psi)$与引起的成本敏感后悔\ [\ begin {aligned} q(\ Psi,l)相关联&= E_{(x^\prime, \omega^\prime) \sim D^\prime_{x^\prime, \omega^\prime} (\Psi, l) } \left[ E_{c^\prime \sim D^\prime_{c^\prime|\omega^\prime,x^\prime} (\Psi, l)} \left[ c ({\Psi (x^\prime, \omega^\prime)}) \right] - \min_{k \in K}\, E_{c^\prime \sim D^\prime_{c^\prime|\omega^\prime,x^\prime} (\Psi, l)} \left[ c (k) \right] \right] \\ &= \frac{1}{l} \sum_{n=1}^l q_n (\Psi), \ end {aligned} \] \\ \ begin {aligned} q_n (\Psi) &= E_{(x, \omega) \sim D_{x,\omega}} [ q_n (\Psi | x, \omega) ], \\ q_n (\Psi | x, \omega) &= E_{c \sim D_{c|\omega,x}} \left[ \tilde c_n \bigl(\Psi_n (x, \gamma_{n-1} (x, \omega)) \bigr) \right] - \min_{k \in K}\, E_{c \sim D_{c|\omega,x}} \left[ \tilde c_n (k) \right] \\ \tilde c_n (k) &= \begin{cases} \infty & \mbox{if } k \in \gamma_{n-1} (x, \omega);\\ c(k)和\ mbox {否则}。 \ end {cases} \ end {aligned} \]
定理:遗憾的结界
对于所有平均约束CSBM分布$ D $和平均约束CMSC分类器$ \ Psi $,\ [r_ {csbm}(h ^ \ Psi)\ leq l \,q(\ Psi,l)。 \] 证明: 看到 附录.
先前版本的此简化中的某些说明仍然适用,而另一些则不适用。

当直接比较减少与回归($ \ sqrt {m} \ sqrt {| K |} \ sqrt {\ epsilon_ {L ^ 2}} $)与通过CSMC进行减少($ m \ sqrt { | K |} \ sqrt {\ epsilon_ {L ^ 2}} $)。这表明有一种方法可以减少此问题,该方法仅利用$ \ sqrt {m} $ 华润上华子问题。效率低下的一种可能来源:减少是按顺序检索元素,而目标函数对顺序无动于衷。

后悔界限表示以下属性:一旦我训练了选择大小为$ m $的集合,对于任何$ l \ leq m $选择大小为$ l $的集合,我都会感到遗憾。这表明可以使用$ m = | K | $的变体将minimax约束的CSMC减少为平均约束的CSMC。我将在以后的博客文章中对此进行探讨。


附录

这就是后悔的证明。

如果$ \ Psi $在引起的子问题上获得无限的后悔,则界限将微不足道。因此,考虑达到有限遗憾的$ \ Psi $。

如果$ | K \ setminus \ omega | <l $,然后$ S_l $中的任何选择$ r_ {csbm} = 0 $,并且该边界有条件地成立。因此考虑$ | K \ setminus \ omega | \ geq l $:由于$ \ Psi $获得有限的遗憾,因此任何子分类器均不会生成重复项,并且$ h ^ \ Psi(x,\ omega)= \ gamma ^ \ Psi_1(x,\ omega)$。

考虑带有$ | K \ setminus \ omega |的固定$(x,\ omega)$ \ geq l $。谈论\ [r_ {csbm}(h ^ \ Psi | x,\ omega,n)= E_ {c \ sim D_ {c | \ omega,x}} \ left [\ sum_ {k \ in \ gamma ^ \ Psi_n(x,\ omega)} c(k)\ right]-\ min_ {h \ in S_n} \,E_ {c \ sim D_ {c | \ omega,x}} \ left [\ sum_ {k \ in h} c(k)\ right],\]在Set Select Test的$ n ^ \ mathrm {th} $步骤中,此实例的条件后悔。令\ [h ^ *(x,\ omega,n)= \ underset {h \ in S_n} {\ operatorname {arg \,min \,}} E_ {c \ sim D_ {c | \ omega,x}} \ left [\ sum_ {k \ in h} c(k)\ right] \]是第二项的任何最小化项(在关系上是唯一的);注意,任何$ h ^ *(x,\ omega,n)$都将选择$ n $类,以最小的条件期望成本为条件。

证明是通过证明属性$ r_ {csbm}(h ^ \ Psi | x,\ omega,n)\ leq \ sum_ {r = 1} ^ n q_r(\ Psi,l)$。该属性相等地持有$ n = 1 $。对于$ n>1 $ note \ [\ begin {aligned} r_ {csbm}(h ^ \ Psi | x,\ omega,n)-r_ {csbm}(h ^ \ Psi | x,\ omega,n-1)&= E_ {c \ sim D_ {c | \ omega,x}} \ left [c(\ Psi_n(x,\ omega \ cup \ gamma ^ \ Psi_ {n-1}(x,\ omega)))\ right] \ \&\ quad-\ min_ {k \ in K \ setminus h ^ *(x,\ omega,n-1)} E_ {c \ sim D_ {c | \ omega,x}} \ left [c(k) \ right] \\&\ leq E_ {c \ sim D_ {c | \ omega,x}} \ left [c(\ Psi_n(x,\ omega \ cup \ gamma ^ \ Psi_ {n-1}(x, \ omega)))\ right] \\&\ quad-\ min_ {k \ in K \ setminus \ gamma ^ \ Psi_ {n-1}(x,\ omega)} E_ {c \ sim D_ {c | \ omega,x}} \ left [c(k)\ right] \\&\ leq E_ {c \ sim D_ {c | \ omega,x}} \ left [\ tilde c_n(\ Psi_n(x,\ omega \ cup \ gamma ^ \ Psi_ {n-1}(x,\ omega)))\ right] \\&\ quad-\ min_ {k \ in K \ setminus \ gamma ^ \ Psi_ {n-1}(x, \ omega)} E_ {c \ sim D_ {c | \ omega,x}} \ left [\ tilde c_n(k)\ right] \\&= q_n(\ Psi,l | x,\ omega),\ end {aligned \ \]其中第二个不等式是由于$ h ^ *(x,\ omega,n-1)$的最优性而第三个不等式是因为$ \ tilde c_n(k)\ geq c(k)$如果$ k \ not \ in \ gam相等ma ^ \ Psi_ {n-1}(x,\ omega)$。对伸缩级数求和建立\ [r_ {csbm}(h ^ \ Psi | x,\ omega)= r_ {csbm}(h ^ \ Psi | x,\ omega,l)\ leq \ sum_ {r = 1} ^ l q_r(\ Psi,l | x,\ omega)= l \,q(\ Psi,l | x,\ omega)。 \]对$ D_ {x,\ omega} $取期望值即可完成证明。