2010年8月4日,星期三

成本敏感的多类分类减少到回归的误差和遗憾界限

继续我的 目前的痴迷,我决定真正了解将成本敏感的多类分类(CSMC)简化为回归模型的方法。特别是,我想得出一个众所周知的错误,并对$ L ^ p $家庭中的损失感到遗憾。我的希望是,我将能够重用其中一些技术来解决更复杂的问题,这些问题包括向标准OR求解器提供估计的系数。

初赛。我正在考虑对成本敏感的多类分类的标准按示例成本设置。有一个有限的类$ K $构成决策空间。有一个分布$ D = D_x \ times D_ {c | x} $,从中绘制对$(x,c)$的IID,其中$ x $是特征,$ c:K \ to \ mathbb {R } $是与此实例选择类$ k $相关的成本向量。成本敏感的多分类器$ h:X \ to K $感到遗憾
\ [r_ {csmc}(h)= E_ {x \ sim D_x} \ left [E_ {c \ sim D_ {c | x}} [c(h(x))]-\ min_ {k \ in K} \; E_ {c \ sim D_ {c | x}} [c(k)] \ right]。 \]用于解决成本敏感型多分类器的argmax回归策略是函数$ g:X \ times K \ to \ mathbb {R} $,它定义了一个相关的成本敏感型多分类器$ h_g:X \ to K $根据\ [h_g(x)= \ underset {k \ in K} {\ operatorname {arg \,min \,}} g(x,k)。 \]我想将$ r_ {csmc}(h_g)$约束为回归问题上的$ g $误差,\ [q_ {L}(g)= E _ {(x,c)\ sim D } \ left [\ frac {1} {| K |} \ sum_ {k \ in K} L \ bigl(g(x,k),c(k)\ bigr)\ right],\]其中$ L $是回归问题的损失函数。对于$ g $对回归问题的后悔,\ [\ epsilon_ {L}(g)= q_ {L}(g)-\ min_g,$ r_ {csmc}(h_g)$的边界也很有趣\; q_ {L}(g)。 \]
错误界限 在这里,我将以$ q_ {L}(g)$表示$ r ^ p $的亏损,得出$ r_ {csmc} $的界限>1 $,其中\ [L ^ p(\ hat y,y)= | \ hat y-y | ^ p。 \]的基本思想是考虑实例$(x,c)$并假设我们的回归变量的成本估算与实际成本相差$ \ delta(x,k)$,\ [g(x,k)= c(k)+ \ delta(x,k)。 \]想象一下一个试图在此实例上创建一定数量的成本敏感型多类分类的对手,同时又将该实例的回归误差降至最低的对手。该对手面临以下问题:\ [\ begin {aligned}&\ min _ {\ delta} \; \ sum_ {k \ in K} L \ bigl(c(k)+ \ delta(x,k),c(k)\ bigr)\\ \ mathrm {s.t。} \ quad&c(h_g(x))-\ min_k \; c(k)= r。 \ end {aligned} \]显然,$ r $只能采用与$ h_g $做出的可能决定相对应的$ | K | $值之一。考虑每个这样的可能决定$ k ^ {**} $;此外,令$ k ^ * = {\ operatorname {arg \,min \,}} _ k c(k)$。然后,对手可以选择以下形式的系列:\ [\ begin {aligned}&\ min _ {\ delta} \; \ sum_ {k \ in K} | \ delta(x,k)| ^ p \\ \ mathrm {s.t。} \; \ forall k \ neq k ^ {**},\;&c(k ^ {**})+ \ delta(x,k ^ {**})\ leq c(k)+ \ delta(x,k)。 \ end {aligned} \] KKT 平稳状态意味着\ [\ begin {aligned} p \ \ Theta(\ delta(x,k))\ | \ delta(x,k)| ^ {p-1}-\ mu_k&= 0 \ quad(k \ neq k ^ {**}),\\ p \ \ Theta(\ delta(x,k ^ {**}))\ | \ delta(x,k ^ {**}) | ^ {p-1} + \ sum_ {k \ neq k ^ {**}} \ mu_k&= 0,\ end {aligned} \]其中$ \ Theta(x)$是符号函数。互补松弛度表示$ \ mu_k = \ delta(x,k)= 0 $,而不是两个正在转换的类,其余平稳条件意味着$ \ delta(x,k ^ *)=-\ delta(x,k ^ {**})$,对偶可行性则意味着$ \ delta(x,k ^ *)>0 $。直觉上,由于错误是凸状惩罚的,所以对手最好的方法是将相等和相反的错误集中在要转换的两个类别上。代入$ k ^ * $的不等式约束,得出\ [c(k ^ {**})-c(k ^ *)\ leq 2 \ delta(x,k ^ *)= 2 \ sqrt [p] { \ frac {| K |} {2} \ frac {1} {| K |} \ sum_ {k \ in K} | \ delta(x,k)| ^ p}。 \]对$ D $取期望得到结果\ [r_ {csmc}(h_g)\ leq 2 \ sqrt [p] {\ frac {| K |} {2}} \ left(E _ {(x ,c)\ sim D} \ left [\ sqrt [p] {\ frac {1} {| K |} \ sum_ {k \ in K} \ delta(x,k)^ p} \ right] \ right) \ leq 2 \ sqrt [p] {\ frac {| K |} {2} q_ {L ^ p}} \]其中最后一个不等式来自于Jensen的不等式。此公式可以在$ p到1 $的限制中正确显示 (请注意,由于缺乏连续微分,KKT不适用于$ p = 1 $),其形式为\ [r_ {csmc}(h_g)\ leq | K | q_ {L ^ 1}。 \]由于我希望实现较小的误差,因此$ p $的根源正在与我们作战,因此关于此范围的最佳选择是$ p = 1 $。 (尝试低于$ p = 1 $会消除对Jensen不等式的使用,因此上述推导将停止工作)。

据观察 涂林,因为$ \ delta(x,k ^ *)>0 $和$ \ delta(x,k ^ {**})<0 $在单边$ L ^ p $丢失的情况下也适用上述界限,定义为\ [L _ {(1)} ^ p(\ hat y,y)= \ lfloor(2 \ 1_ {k = k ^ *}-1)(y-\ hat y)| y-\ hat y | ^ {p-1} \ rfloor,\]其中$ \ lfloor x \ rfloor = \ max(x,0)$。基本上,不会低估每个实例的最低成本类别的价值,而高估每个实例的非最低成本类别的价值也不会受到惩罚。在这种情况下,我还有\ [r_ {csmc}(h_g)\ leq 2 \ sqrt [p] {\ frac {| K |} {2} q_ {L _ {(1)} ^ p}} \] \ p \ geq 1 $。由于单边$ L ^ p $的损失以$ L ^ p $的损失为界,因此该界限是一种改进。

遗憾的结界 在一个困难的问题上,由于成本估算的内在可变性,可能无法实现小的误差。通过对基本回归问题的后悔来限制CSMC的后悔更好,因为即使在难题上也可以实现低后悔。

从上述错误界限推导中可以看出,对手具有太多的自由度:回归者仅被定义为$ x $的函数,但是允许对手选择$ \ delta(x,k)$每个$ c $不同。在推导出遗憾后,我将消除这个问题。

考虑单个实例特征$ x $和相关的按实例成本向量分布$ D_ {c | x} $,并假设我们的回归器的成本估算与最小误差回归器的估算$ c ^ *(x,k )$ by $ \ delta(x,k)$,\ [g(x,k)= c ^ *(x,k)+ \ delta(x,k)。 \]想象一下一个对手,它试图在这种情况下创建一定数量的对成本敏感的多类分类遗憾,同时最小化这种情况下的回归遗憾。该对手面临以下问题:\ [\ begin {aligned}&\ min _ {\ delta} \; E_ {c \ sim D_ {c | x}} \ left [\ sum_ {k \ in K} L \ bigl(c ^ *(x,k)+ \ delta(x,k),c(k)\ bigr )-L \ bigl(c ^ *(x,k),c(k)\ bigr)\ right] \\ \ mathrm {st} \ quad&E_ {c \ sim D_ {c | x}} \ left [c(h_g(x))\ right]-\ min_k \; E_ {c \ sim D_ {c | x}} \ left [c(k)\ right] = r。 \ end {aligned} \]同样,$ r $只能采用与$ h_g $做出的可能决定相对应的$ | K | $值之一。考虑每个这样的可能决定$ k ^ {**} $;那么对手可以选择以下形式的系列:\ [\ begin {aligned}&\ min _ {\ delta} \; E_ {c \ sim D_ {c | x}} \ left [\ sum_ {k \ in K} L \ bigl(c ^ *(x,k)+ \ delta(x,k),c(k)\ bigr )-L \ bigl(c ^ *(x,k),c(k)\ bigr)\ right] \\ \ mathrm {st} \; \ forall k \ neq k ^ {**},\;&c ^ *(x,k ^ {**})+ \ delta(x,k ^ {**})\ leq c ^ *(x,k)+ \ delta(x,k)。 \ end {aligned} \]通常很难解决,但是对于$ p = 2 $来说,发生了一些神奇的事情。考虑一下目标函数(即$ | K | \ epsilon_L $)\ [\ begin {aligned}&\ quad E_ {c \ sim D_ {c | x}} \ left [\ sum_ {k \ in K} \ bigl(c ^ *(x,k)+ \ delta(x,k)-c(k)\ bigr)^ 2-\ bigl(c ^ *(x,k)-c(k)\ bigr)^ 2 \ right] \\&= \ sum_ {k \ in K} 2 \ delta(x,k)\ left(c ^ *(x,k)-E_ {c \ sim D_ {c | x}} \ left [c(k)\ right ] \ right)+ \ delta(x,k)^ 2 \\&= \ sum_ {k \ in K} \ delta(x,k)^ 2,\ end {aligned} \]其中我使用了$ L ^ 2 $的属性,即$ c ^ *(x,k)= E_ {c \ sim D_ {c | x}} \ left [c(k)\ right] $。现在,我有与上述误差范围相同的$ L ^ 2 $损失目标函数。应用类似的推理,最后得到\ [r_ {csmc}(h_g)\ leq \ sqrt {2 | K | \ epsilon_ {L ^ 2}(h_g)},\]看起来与$ L ^ 2 $的错误界限相似,但右侧是后悔。那其他损失呢,例如$ p \ neq 2 $的$ L ^ p $损失或单面变量呢?简单的反例表明,对这些损失的回归问题零后悔并不意味着对CSMC的零后悔。因为关键条件$ c ^ *(x,k)= E_ {c \ sim D_ {c | x}} \ left [c(k)\ right] $仅适用于$ L ^ 2 $,所以我希望其他条件出现在对手问题的目标函数中,从而改变结果。

最后,应该注意的是,将CMSC简化为二进制分类,从而在二进制后悔中实现了线性的后悔界限,例如, 所有对过滤树.

没意见:

发表评论