2010年11月22日,星期一

Minimax受约束的CSMC:进展不大

在一个 以前的帖子 我谈到了广告投放,以及为什么基于回归的方法仍然占主导地位,即使其他针对成本敏感的多类分类(CSMC)的方法具有较低的遗憾界限。我认为,这归结为实际问题,而广告投放中的一个重要的实际问题是,给定决策实例(广告投放请求)所允许的一组操作(广告)可能是易变的。此外,在许多情况下,例如,由于广告商尝试预算,没有理由相信训练集和测试集之间的约束模式在统计上是稳定的。因此,我认为最好以对抗性方式建模约束,这种情况称为minimax约束CSMC。

我将对minimax受约束的CSMC重复设置。有一个分布$ D = D_x \ times D _ {\ tilde c | x} $,其中$ \ tilde c:K \ to \ mathbb {R} $的取值以正实数$ \ mathbb {R} $为单位。然后,一个对手进入,并通过将某些成分设置为$ \ infty $,在扩展实数$ \ mathbf {R} $中制造成本向量$ c $;在做出决定之前,这些选择会通过$ \ omega $显示出来。在这种情况下,特定分类器$ h的遗憾:X \ times \ mathcal {P}(K)\ to K $由\ [\ nu(h)= E_ {x \ sim D_x} \ left [\ max_ {\ omega \ in \ mathcal {P}(K)} \ left \ {E _ {\ tilde c \ sim D _ {\ tilde c | x}} \ left [c(h(x,\ omega))\ right] -\ min_ {k \ in K} \; E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c(k)\ right] \ right \} \ right]。 \]与平均受约束的CSMC相反,后者的约束分布($ \ omega $)从训练到测试数据都是稳定的。对于受约束的普通CSMC,基于树的减少量在经过修改以禁止其选择放弃其锦标赛时起作用。但是,这对于minimax约束的CSMC不起作用,如下面的简单反例所示。假设$ X = \ emptyset $,$ K = \ {1、2、3 \} $和$ \ tilde c $是确定性的,使得$ \ tilde c(1) < \tilde c (3) < \tilde c (2)$, and suppose the tree first pairs $\{1, 2\}$ while giving 3 a pass, and then pairs $\{1, 3\}$. Suppose the classifier used 在 each tree node is $1_{f (a) > f(b)} $用于某些函数$ f:K \ to \ mathbb {R} $。如果仅使用$ \ omega = \ emptyset $的数据进行训练,则在$ f(1)= 1 $,$ f(3)= 3 $和$ f的情况下,对训练数据的后悔可以归零。 (2)= 2 $。但是,当$ \ omega = \ {1 \} $在测试时会感到遗憾。

这里发生了什么?这种情况类似于分类的降级,其中$ f $引起元素的线性排序。在那种情况下,在输入对上平均的分类误差为在输入集上平均的AUC误差提供了界限。当然,AUC对于目标函数而言过于粗糙,因为它仅对排序误差敏感,而对幅度不敏感。但是,这的确表明除了在过滤树的一次通过期间进行的$(| K |-1)$比较之外,还需要在训练期间比较更多对元素。如果必须在训练期间比较每对,则可能需要$ | K | / 2 $通过过滤树。

因此,请考虑在[1,| K |] $中由$ n \索引的平均约束CSMC分类器$ \ Psi_n $的序列。这些会诱发一个序列$ \ {\ tilde \ omega_n | n \ in [0,| K |] \} $通过\ [
\ begin {aligned}
\ tilde \ omega_0&= \ emptyset,\\
\ tilde \ omega_n&= \ tilde \ omega_ {n-1} \ cup \ {\ Psi_n(x,\ tilde \ omega_ {n-1})\}。
\ end {aligned}
\]本质上,这是一系列平均约束CSMC分类器,它们确定最佳动作,次佳动作等(以与减少 成本敏感的最佳m到成本敏感的多类)。接下来考虑索引\ [
\ eta(x,\ omega)= \ min \ {n \ in [1,| K |] | \ Psi_n(x,\ tilde \ omega_ {n-1})\ not \ in \ omega \}。 \]如果$ \ omega \ neq K $,则此索引始终存在。当$ \ omega \ neq K $通过\ [h(x,\ omega)= \ Psi _ {\ eta(x,\ omega)}(x,\ tilde \ omega _ {\ eta(x, \ omega)-1})。
\](当$ \ omega = K $时,无论分类器做出何种选择,遗憾总是为零,因此我将忽略这种情况)。特定$(x,\ omega)$的遗憾由\ [
\ begin {aligned}
\ nu(x,\ omega)&= E_{\tilde c \sim D_{\tilde c|x}} \left[ c (h (x, \omega)) \right] - \min_{k \in K}\;E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c(k)\ right] \\
&= E _ {\波浪线c \ sim D _ {\波浪线c | x}} \ left [c(h(x,\ omega))\ right]-\ min_ {k \ in K \ setminus \ tilde \ omega _ {\ eta(x,\ omega)-1}} E _ {\波浪线c \ sim D _ {\波浪线c | x}} \ left [c(k)\ right] \\
&= E _ {\\ t​​ilde c \ sim D _ {\\ t​​ilde c | x}} \ left [c \ left(\ Psi _ {\ eta(x,\ omega)}(x,\ tilde \ omega _ {\ eta(x, \ omega)-1})\ right)\ right]-\ min_ {k \ in K \ setminus \ tilde \ omega _ {\ eta(x,\ omega)-1}}} E _ {\ tilde c \ sim D _ {\代字号c | x}} \ left [c(k)\ right],\\
\ end {aligned}
\],其中第二行从$ \ tilde \ omega _ {\ eta(x,\ omega)-1} \ subseteq \ omega $开始,第三行从$ h $的定义开始。现在,最后一行是针对每个实例的$ \ eta(x,\ omega)^ {\ textrm {th}} $平均受约束CSMC分类器的遗憾,该CSMC分类器是根据第一个$(\ eta(x,\ omega)-1)$个分类器。因此\ [
\ max _ {\ omega \ in \ mathcal {P}(K)} \ nu(x,\ omega)= \ max_n \ left \ {E _ {\ tilde c \ sim D _ {\ tilde c | x}} \ left [ c(\ Psi_n(x,\ tilde \ omega_n))\ right]-\ min_ {k \ in K \ setminus \ tilde \ omega_ {n-1}} E _ {\ tilde c \ sim D _ {\ tilde c | x }} \ left [c(k)\ right] \ right \}。
\]这建议一个过程,其中每个实例完成$ | K | $个没用的过滤树通过;虽然这似乎是2的太多,但注意没收不会生成分类实例,从而消除了一半的比较。 minimax限制了CSMC的遗憾是“ [
\ nu(h)\ leq(| K |-1)E_ {x \ sim D_x} \ left [\ max_n \; q_n(x,\ tilde \ omega_ {n-1})\ right]
\]其中$ q_n(x,\ tilde \ omega_ {n-1})$是在分配诱导下训练的$ n ^ {\ textrm {th}} $没收过滤树的平均每节点重要性加权后悔被第一个$(n-1)$没收的过滤树。

乍一看,这看起来实在太笨拙,无法在实践中使用,但是有两种修改可能使其实用。第一种是为每个$ \ Psi_n $重用同一棵树,而不是将$ n $个树分开。尽管正确的训练程序对我来说不是立即显而易见的,但遗憾的束缚依然存在。第二种是考虑约束数量(即$ | \ omega |)有界的情况。 \ leq z \ ll | K | $,这样培训和测试成本仅增加$ z $。实际上,这似乎是合理的。

没意见:

发表评论