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} $取期望值即可完成证明。

2条评论:

  1. 由于我仍然是还原方法的新手,因此我的问题可能无关紧要。

    1.我发现所有关于归约方法的论文都试图保证后悔或错误的约束,但这是唯一重要的吗?考虑用回归方法解决二元分类问题的最简单例子,并证明后悔界限和误差界限,如果回归方法在转换后的数据集上工作良好,那么归约方法的最终结果也应该很好。但是不应该'我们是否证明回归方法确实可以在转换后的数据集上很好地工作?

    2.我对有关CSMC和CSBM的主题特别感兴趣,因为它们与我当前的项目直接相关。我认为将CSMC和CSBM简化为回归模型与Thorsten Joachims的工作非常相似(分别是SVM_Perf和SVM_MAP,当然需要一些扩展),那么应该如何比较它们?

    回复 删除
  2. 减少是关于将一​​些鲜为人知的问题(例如,CSMC)与某个更好地被理解的问题(例如,二进制分类或回归)相关联。它'的确,如果我们简化为一个子问题,然后对子问题做不好的事情,那么对原始问题我们将做不好的事情。但是,我们的想法是,我们觉得我们在诸如二进制分类之类的基本子问题上有丰富的经验,因此我们希望做得不错。

    有时最糟糕的情况分析可能会引起欺骗,但是对于CSMC,尤其是在困难(嘈杂)数据集上,经验表现的确遵循了最坏情况的界限。

    回复:SVM_Perf或SVM_MAP。减少是关于通过转化为现有解决方案来解决问题。另一种方法是直接解决原始问题。 SVM_Perf采用直接方法对损耗进行排序,例如AUC和k精度。 SVM_MAP采用直接方法来排名损失平均平均精度。

    排名损失(AUC,prec @ k,MAP)都假定存在"good results" and "bad results"并定义将值分配给代表排名的大位字符串(最佳位字符串为00000 .... 01 ... 11111)的不同方法。 CSBM 之所以不同,是因为假定决策具有与之关联的标量值,并且希望最大化集合的总和值。特别是在广告中,当显示不同的广告时会产生不同的收入,因此注意这一点可能会提高实践效果。

    如果对问题的简化方法和对问题的直接方法都基于相同的损失函数,则我建议进行经验评估,尤其是在像Jochaims这样的人提供高质量软件的情况下。下载并试用。

    什么时候攻击一个没有问题的地方'如果没有引起文献的关注,我建议您寻求一种简化算法,而不是直接算法,因为前一种算法通常看起来更容易提出,并且更容易证明它的确合理。作为奖励,您可以重用出色的软件来减少学习量。

    回复 删除