显示带有标签的帖子 制约因素 . 显示所有帖子
显示带有标签的帖子 制约因素 . 显示所有帖子

2010年12月5日,星期日

成本敏感的最佳M的SFF树

约翰·兰福德 最近向我发送了一个有用的建议。
另一种方法是引入代表性的hack。假设我们将成对分类器定义为:$ w_ {left} x_ {left}-w_ {right} x_ {right} $。然后,过滤树的输出为$ \ underset {a} {\ operatorname {arg \,max \,}} w_a x_a $,其形式与回归相同。但是,我们以不同的方式训练事物,以实现较低的后悔$ \ ldots $
与该建议相关的探索方向很多。这是我的一些曲折。

SFF树:定义

我将此建议称为计分没收过滤器(SFF)树。类比是当使用评分功能定义线性排序以减少对分类的排名时。这是一个更精确的定义。
定义: SFF树
SFF树是 没收过滤树 $\Psi$ where 在 each internal node $\nu$ the importance-weighted classifier is of the form \[ \Psi_\nu (x) = 1_{f (x; \lambda) > f (x; \phi)}
\]其中$ \ lambda $和$ \ phi $是输入到$ \ nu $的两个类(分别是左和右子树的预测)。函数$ f $称为计分函数,并且在每个内部节点处都相同(但对于每个操作而言都不同)。

John的建议的妙处在于,可以在测试时通过$ h ^ \ Psi(x,\ omega)= \ underset {k \ in K \ setminus \ omega} {\ operatorname {arg \,max \,}} f(x; k)$看起来就像如何计算输出以进行回归归约。但是后悔的界限更好,因为训练的过程是不同的。

SFF树 平均约束CSMC

由于SFF树是没用的过滤树,因此 后悔 上的“没收过滤器”树 平均约束CSMC 问题成立,即\ [r_ {av}(h ^ \ Psi)\ leq(| K |-1)q(\ Psi),\]其中$ q(\ Psi)$是重要性加权二元遗憾引起的子问题。这与 回归遗憾,\ [r_ {av}(h_g)\ leq \ sqrt {2 | K | \ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是基础回归问题的损失$ L ^ 2 $。

因此,一开始这似乎很神奇(即,可以将其视为获得更好的回归指标的一种方法),但是我将其理解为训练过程,将子问题预言集中在重要的问题上(例如,区分best和$ 2 ^ \ mathrm { nd} $每个实例的最佳操作),而忽略不存在的问题(例如,准确估计$(n-1)^ \ mathrm {th} $和$ n ^ \ mathrm {th} $最差的选择的值)。

在实践中,强制SFF树中的分类器基于评分函数可能会导致难以学习对诱导子问题的低遗憾解决方案。评分函数在所有内部节点上共享的事实是简化输出计算的关键,但与普通的没收树不同。在原始情况下,很容易设想通过$ \ log_2(| K |)$顺序遍历以从下到上的方式训练树,每次遍历定义内部节点的下一级别的训练数据,并且每次遍历在特定深度训练一组内部节点。但是,现在不同级别的分类器是交织在一起的。

我实际上不确定如何处理这个问题,并且直到尝试尝试时我才知道。凭直觉,如果我要在线上逐步更新热模型,我会尝试忽略依赖关系,而仅应用更新。动机是我每次更新都会进行微小的更改,所以我忽略的是``高阶微小''。当然,决策边界处的大量非线性有点令人不安(并且不是很小)。从冷开始但仍使用在线学习算法(针对脱机数据),我尝试从下到上的方式通过$ \ log_2(| K |)$,在一定深度前热启动整个树在下一个更高的深度训练任何内部节点。与普通情况不同,每次通过都会训练所有内部节点达到一定深度,而不仅仅是训练特定深度的内部节点。希望能奏效,但如果失败了,我会考虑使用softmax风格的方法来减轻决策边界的非线性,例如$ p(\ Psi_ \ nu = 1 | x)= 1 /(1 + e ^ {-\ beta(f(x; \ lambda)-f(x; \ psi))})$并将$ \ beta $退火为$ \ infty $。

SFF树 平均约束CSBM

平均约束CSBM 是在给定实例的情况下选择前$ m $个操作的问题。通过构造分类器列表$ \ {\ Psi_n | |,可以将其减少到受约束的平均CSMC。 n \ in [1,m] \} $每个都经过训练,以选择最佳动作,下一个最佳动作等。

所以这是一个有趣的事情:如果我们在分类器列表中设置$ \ Psi_n = \ Psi $,并且如果我们的平均约束CSMC分类器是SFF树,那么我们可以通过\ [h ^ \ Psi(x, \ omega)= \ underset {k \ in K \ setminus \ omega} {\ operatorname {arg \,max \,^ m}} f(x; k),\]在这里我用符号$ \ operatorname {arg \,max \,^ m} $代表选择前$ m $个元素。同样,这正是在测试时将采用基于回归约简的方法的方式。但是遗憾的界限还是不同的。当将平均约束CSBM减小为平均约束CSMC时, 后悔 是\ [r_ {csbm}(h ^ \ Psi)\ leq m \,q(\ Psi,m),\]其中$ q(\ Psi,m)$是对$ m $的平均成本敏感后悔平均约束CSMC子问题(这些问题又可以简化为重要性加权分类,从而保持对后悔的线性依赖)。相反,当简化为回归 后悔 是\ [r_ {csbm}(h_g)\ leq \ sqrt {2 \ min \ {m,| K | -m \}} \ sqrt {| K |} \ sqrt {\ epsilon_ {L ^ 2}(g)},\]其中$ \ epsilon_ {L ^ 2}(g)$是$ L ^ 2 $的损失关于潜在的回归问题。

因此,我们再次保证可以采用不同的训练程序来获得更好的回归值,但是子问题之间的依存关系也存在类似的问题,使训练画面复杂化。在将CSBM简化为CSMC的典型情况下,每个分类器将按顺序进行训练,并为下一个分类器定义训练输入分布。现在所有分类器都相同,因此需要一些技巧。

再说一次,我实际上不确定如何处理这个问题,直到尝试了一些事情,我才知道。凭直觉,我将再次尝试在线上逐步更新热模型,而忽略依赖关系。对于将离线模型应用于在线模型的冷启动,我将首先针对top-1问题,然后针对top-2问题进行培训,直到达到top- $ m $。有趣的是,如何看待我的两个直观过程的组成如何进行完整的冷启动:
  1. 对于$ n $ in $ [1,m] $
    1. 为$ l $ in $ [\ log_2(| K |),1] $
      1. 更新$ l ^ \ mathrm {th} $和更低级别的内部节点,以解决同时选择顶部$ n $动作的问题
      2. 更新$ l ^ \ mathrm {th} + 1 $和更高级别的内部节点,以解决选择前$(n-1)$个操作的问题。
总共$ m \ log_2(| K |)$通过了数据,这很合理。外循环用于减轻由$ \ Psi_n = \ Psi $创建的依赖关系,而内循环用于减轻在所有内部节点之间共享$ f $所创建的依赖关系。

现在,我想我应该在一些实际数据上尝试一下。

2010年9月15日,星期三

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

在一个 以前的帖子 我讨论了受约束的成本敏感最佳分类(CSBM),以及一种简化为受约束的成本敏感多类分类(CSMC)的方法。当一套的奖励是元素的奖励的总和时,CSBM就是选择最佳的选择,而对CSMC的简化则是``先选择最佳选择,然后再选择下一个最佳选择,依此类推'' 。从那时起,我开始玩 偏移树 ,这是针对历史数据包含部分反馈的问题而设计的(即,仅针对所采取的措施才显示奖励)。现在该进行混搭了,即使用部分反馈约束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} \] where \[ \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} $ CSMC子问题。效率低下的一种可能来源:减少是按顺序检索元素,而目标函数对顺序无动于衷。

后悔界限表示以下属性:一旦我训练了选择大小为$ 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月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} \] where \[ \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} $ CSMC子问题。效率低下的一种可能来源:减少是按顺序检索元素,而目标函数对顺序无动于衷。

后悔界限表示以下属性:一旦我训练了选择大小为$ 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} $取期望值即可完成证明。