2010年8月22日,星期日

随机的最短路径减少到成本敏感的多类:朝着更好的遗憾界限发展

后悔 为了 减少路径网格 不求助于成本敏感的多类分类(CSMC)的随机最短路径(SSP)可用于显示减少的一致性,即,最小后悔路径选择策略是由最小后悔成本敏感的多类分类器产生的。但是界限感觉太松了:尤其是,遗憾上的$ O(n ^ 2)$缩放因子似乎与直接 减少回归,其缩放系数为$ \ sim n ^ {3/2} $。凭直觉,感觉我应该能够通过CSMC降级到回归并具有相同的界限,这表明CSMC降低的O(n)$缩放因子。

所以我一直在努力想出类似的办法。我没有什么让我非常满意的,但是这里有一些想法。首先,这是一个定理,该条件SSP后悔由对SSP后悔最小化路径上遇到的子问题的条件成本敏感后悔加总。
定理:最佳路径后悔界限
对于固定的$ x $,让$ p ^ *(x)$表示在SSP上遇到的$(k,v)$对的集合,遗憾的是最小化了从源顶点$ s到目标顶点$ t的长度$ n $的路径$。然后对于所有SSP分布和所有成本敏感的分类器$ \ Psi $,\ [r_ {spath}(\ Psi)= E_ {x \ sim D_x} \ left [\ sum _ {(k,v)\ in p ^ * (x)} q_ {kv}(\ Psi | x)\ right],\],定义为$ \ forall v,q_ {n-1,v}(\ Psi | x)= q_ {nv}(\ Psi | x)= 0 $。

证明: 假设$ \ Upsilon ^ * _ {kv}(x)$是在SSP上遇到的$(k,v)$对的集合,遗憾的是最小化了从源顶点$ v $到目标顶点$的长度$ n-k $的路径t $。在属性$ r_ {kv}(\ Psi | x)\ leq \ sum _ {(k ^ \ prime,v ^ \ prime)\ in \ Upsilon ^ * _ {kv}(x)} q_ {kv }(\ Psi | x)$。

当$ k = n-2 $时,可以很容易地直接验证$ r_ {n-2,v}(\ Psi | x)= q_ {n-2,v}(\ Psi | x)$。
对于$ k \ in [1,n-2)$,\ [\ begin {aligned} r_ {kv}(\ Psi | x)&\ leq q_ {kv}(\ Psi | x)+ r_ {k + 1 ,w ^ *}(\ Psi | x)\\&\ leq q_ {kv}(\ Psi | x)+ \ sum _ {(k ^ \ prime,v ^ \ prime)\ in \ Upsilon ^ * _ {k + 1,w ^ *}(x)} q_ {k ^ \ prime,v ^ \ prime}(\ Psi | x)\\&= \ sum _ {(k ^ \ prime,v ^ \ prime)\ in \ Upsilon ^ * _ {kv}(x)} q_ {k ^ \ prime,v ^ \ prime}(\ Psi | x),\ end {aligned} \],其中第一步是从下一步绑定引理,第二步利用归纳假设,第三步是$ \ Upsilon ^ * _ {kv}(x)$的定义。注意$ \ Upsilon ^ * _ {1s}(x)= p ^ *(x)$的收益
\ [r_ {spath}(\ Psi | x)= r_ {1s}(\ Psi | x)\ leq \ sum _ {(k,v)\ in p ^ *(x)} q_ {kv}(\ Psi | x X)。 \]
对$ D_x $取期望值即可完成证明。
这个定理对我来说很有趣,原因有两个。首先,它涉及超过$ n $的遗憾,因此它似乎更接近于更好的界限;有关更多信息,请参见下文。其次,它表明实际上只有沿着最优路径的分类器才是重要的。重要的变量会随着$ x $的变化而变化,并且我不知道它们是哪一个(那将是我寻求的SSP解决方案!),但是尽管如此,要解决的许多子问题都是无关紧要的。也许有一种方法可以迭代调整成本向量以将其考虑在内。

回到更好的边界问题,这是从上述定理到语句\ [r_ {spath}(\ Psi)\ leq(n-2)E_ {x \ sim D_x} \ left [\ max_ { kv} \; q_ {kv}(\ Psi | x)\ right],\]具有正确的风格。例如,如果我将单个CSMC子问题简化为回归,则将获得一个额外的$ \ sqrt {2n} $前导因子,并获得$ \ sqrt {\ epsilon_ {kv}} $依赖该子问题的回归遗憾。这将使\ [\ begin {aligned} r_ {spath}(\ Psi)&\leq (n - 2) E_{x \sim D_x} \left[ \max_{kv}\;q_ {kv}(\ Psi | x)\ right] \\&\leq (n - 2) \sqrt{2 n} E_{x \sim D_x} \left[ \max_{kv}\;\ sqrt {\ epsilon_ {kv}(\ Psi | x)} \ right] \\&\leq (n - 2) \sqrt{2 n} \sqrt{ E_{x \sim D_x} \left[ \max_{kv}\;\ epsilon_ {kv} \ right]} \ end {aligned} \]其中$ \ max_a \; \ sqrt {f_a} = \ sqrt {\ max_a \; f_a} $和詹森的不等式在最后一步结合在一起。这有点像$ O(n ^ {3/2})\ sqrt {\ epsilon} $,我从直接归约到回归。但是我不满意,因为我对单个回归子问题的期望与一组回归最大值之间的``$ L ^ {\ infty} $风格''期望之间的关系没有很好的直觉子问题。

没意见:

发表评论