2010年8月8日,星期日

随机最短路径:减少回归

最短路径问题 是一个标准问题,给定一个图形$ G =(V,E)$,两个顶点$ s,t \ in V $和一个成本函数$ f:E \ to \ mathbb {R} $,该问题是找到从$ s $到$ t'$满足\ [P ^ * = \ underset {p \ in P} {\ operatorname {arg \,min \,}} \ sum_ {e \在p} f(e)中。\]有一个 自然线性规划公式 最短路径问题,它看起来像没有容量约束的最小成本流问题,所以它与我的 目前的痴迷.

在OR中,最短路径问题的解决方案包括有效地计算给定图形和成本函数的最小成本路径。但是,从机器学习的角度来看,我们不知道成本。取而代之的是,我们知道图形的当前实现,并且具有一些历史数据,这些数据关于过去遇到的图形的成本。 OR社区将此称为随机最短路径问题(的一种变体)。

设置 我将定义随机最短路径(SSP)问题,如下所示。为简单起见,我假设以下内容:
  1. 具有固定数目的顶点$ n $的完全连接的图结构。可以想象,作为一种处理未完全连接的图(或顶点数少于$ n $的图)的工具,边上的成本过高。
  2. 任何循环路径几乎肯定具有非负权重。例如,如果所有边缘成本均为非负数,则为true。
  3. 我们一直在尝试从顶点0到顶点$ n-1 $,而$ P $是连接顶点0和顶点$ n-1 $的(非循环)路径的集合。
还请注意,$ E $表示图中的一组边,但也表示期望运算符。希望从上下文可以清楚地看出这一点。

假设分配$ D = D_x \ time D_ {f | x} $,即从中绘制图实例,其中$ D_x $是边缘实现$ X = E ^ {n \ choose 2} $和$ D_ {f | x} $是特定边际实现条件下边际成本的分布。 (这里的想法是我们的​​边缘带有一些可以用来帮助预测最佳路径的关联功能。)最短路径查找器是函数$ h:X \ to P $,它采用边缘实现并返回路径。 $ h $的遗憾是\ [r_ {spath}(h)= E_ {x \ sim D_x} \ left [E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in h(x)} f(e)\ right]-\ min_ {p \ in P} \; E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in p} f(e)\ right] \ right],\],即$ h $选择的路径与最佳路径之间的成本差。解决SSP意味着获取从$ D ^ m $采样的$ m $数据点集,并构造一个遗憾程度最低的最短路径查找器。

OR社区将这种变体称为SSP,而无需追索权,因为只有在选择路径之后才能知道电弧成本的值。其他设置也是可能的,例如在 加拿大旅客问题 在遍历图形时会显示并收取费用,而所需的是遍历策略。

与成本敏感型多类别的关系 我觉得这很有趣,因为它代表了从成本敏感的多类分类(CSMC)到更一般的OR问题的一步,因此它与我目前对理解如何进行在线性程序中使用其输出的机器学习的痴迷有关。

Consider a network with a single starting node $s$, and single destination node $t$, and set of $K$ intermediate nodes indexed by $k$ with source costs $f (s, k)$ and with sink costs $f (k, t) = 0$. In this case all paths are of the form $\{ (s, k), (k, t) \}$ for some $k$ and the optimal path is $\{ (s, k^*), (k^*, t) \}$ where \[ k^* = \underset{k}{\operatorname{arg\,min\,}} f (s, k). \] Thus CSMC is a special case of SSP where the graph structure is constrained. Viewed in this way SSP looks like a multi-step version of CSMC which is ballistically planned, suggesting that a good understanding of SSP might yield insight into problems involving selecting a subset of classes from a set (e.g., populating a slate of $m$ advertisements when there are $n > m$ eligible advertisements).

如..所示 先前,一些最先进的CSMC方法不会减少到回归。这表明,攻击SSP的最佳方法是不估计成本并将其提供给标准的最短路径查找算法。这听起来是另一个帖子的有趣话题。现在,我假设我们通过估算成本然后使用标准的最短路径查找算法来解决不确定的成本最短路径问题。

产生的误差和后悔界限与CSMC非常相似,推导也非常相似,包括可以为SSP定义的类似的单面损耗。尤其是对基础回归问题的错误或后悔的依赖具有相同的指数,但前导常数更差,例如,CSMC后悔将$ L ^ 2 $损失标度绑定为类数的平方根(对应于完全连接图中的边或正方形的顶点),但SSP遗憾地会损失$ L ^ 2 $,因为顶点数目以立方表示为相同的指数。这是因为在完全连接的SSP设置中,CSMC的约束图结构得到了放宽。关于SSP实例的图形连接性的更多限制性假设可能会改善前导常数。

减少回归 SSP的回归减少量是函数$ g:E \ to \ mathbb {R} $,它定义了关联的最短路径查找器$ h_g:X \ to P $通过
\ [h_g(x)= \ underset {p \ in P} {\ operatorname {arg \,min \,}} \ sum_ {x_ {ij} \ in p} g(x_ {ij})。 \]换句话说,我们估算成本,然后使用像 贝尔曼福特。我们希望将$ r_ {spath} $绑定到基础回归问题的任一错误上,
\ [\ nu_L(g)= E _ {(x,f)\ sim D} \ left [\ frac {1} {| x |} \ sum_ {e \ in x} L(g(e),f(e ))\ right],\]或对基本回归问题\ [\ epsilon_ {L}(g)= \ nu_ {L}(g)-\ min_g \的遗憾; \ nu_ {L}(g)。 \]注意完全连接的假设意味着$ | x | = {n \ choose 2} $,但是上面关于回归误差的表达式直观地感觉可以将其推广到非完全连通的图。

错误为$ q \ geq 1 $的$ L ^ q $亏损 考虑一个实例$(x,f)$,并假设我们的回归变量的成本估算与实际成本相差$ \ delta(e)$,\ [g(e)= f(e)+ \ delta(e)。 \]想象一个对手试图在此实例上创建一定数量的SSP后悔,同时最大程度地减少此实例上的回归错误。对手面临以下问题:\ [\ begin {aligned}& \min_{\delta}\;\ sum_ {e \ in x} L \ bigl(f ^ *(e)+ \ delta(e),f(e)\ bigr)\\ \ mathrm {s.t。} \ quad & \sum_{e \in h_g (x)} f (e) - \min_{p \in P}\;\ sum_ {e \ in p} f(e)= r。 \ end {aligned} \]显然,$ r $只能采用与$ h_g $做出的可能决定相对应的$ | P | $值之一。考虑每个这样的可能决定$ p ^ {**} $。然后,对手可以选择以下形式的系列:
\[ \begin{aligned} & \min_{\delta}\; \sum_{e \in x} |\delta (e)|^q \\ \mathrm{s.t.} \; \forall p \neq p^{**}, \; & \sum_{e \in p^{**}} f (e) + \delta (e) \leq \sum_{e \in p} f (e) + \delta (e), \end{aligned} \] where we have substituted in $L^q (\hat y, y) = |y - \hat y|^q$ loss. For $q > 1$, the KKT 平稳性条件表示\ [q \ \ 的ta(\ delta(e))\ | \ delta(e)| ^ {q-1} + \ sum_ {p \ neq p ^ {**}}(1_ {e \ in p ^ {**}}-1_ {e \ in p})\ mu_p =0。\]补充松弛表示$ \ mu_p = 0 $,除非$ p $的约束处于活动状态。令$ p ^ * = \ operatorname {arg \,min \,} _ {p \ in P} \ sum_ {e \ in p} f(e)$是真正的最佳路径选择,在这种情况下,只有$ \ mu_ {p ^ *} $必须为非零。平稳性条件简化为\ [q \ \ 的ta(\ delta(e))\ | \ delta(e)| ^ {q-1} +(1_ {e \ in p ^ {**}}-1_ {e \ in p ^ *})\ mu_ {p ^ *} = 0,\]更清楚地表示为\ [\ delta(e)= \ begin {cases} \ alpha& \mbox{if } e \in p^* \mbox{ and } e \not \in p^{**} ; \\ -\alpha & \mbox{if } e \not \in p^* \mbox{ and } e \in p^{**} ;\\ 0&\ mbox {否则,} \ end {cases} \]其中$ \ alpha =(\ mu_ {p ^ *} / q)^ {q-1} $。直觉上,由于错误是凸状惩罚的,所以对手最好的方法是将相等和相反的错误集中在仅位于$ p ^ {**} $或$ p ^ * $的那些边上。令$ \ kappa(p ^ *,p ^ {**})= | p ^ * | + | p ^ {**} | -2 | p ^ * \ cap p ^ {**} | $。代入不等式约束产生\ [\ begin {aligned} \ sum_ {e \ in p ^ {**}} f ^ *(e)-\ sum_ {e \ in p ^ *} f ^ *(e)& \ leq \ sum_ {e \ in p ^ *} \ delta(e)-\ sumq {e \ in p ^ {**}} \ delta(e)\\&= \ kappa(p ^ *,p ^ { **})\ sqrt [q] {\ frac {| x |} {\ kappa(p ^ *,p ^ {**})}} \ frac {1} {| x |} \ sum_ {e \ in x } | \ delta(e)| ^ q} \\&\ leq(2 | V |-2)^ {1-1 / q} \ sqrt [q] {| x |} \ sqrt [q] {\ frac {1} {| x |} \ sum_ {e \ in x} | \ delta(e)| ^ q},\ end {aligned} \],最后一步利用$ \ kappa(p ^ *,p ^ { **})\ leq 2 | V | -2美元。 对$ D $取期望会得出结果\ [\ begin {aligned} r_ {spath}(h_g)&\ leq(2 | V |-2)^ {1-1 / q} \ sqrt [q] { | x |} \ E_ {x \ sim D} \ left [\ sqrt [q] {\ frac {1} {| x |} \ sum_ {e \ in x} \ delta(e)^ q} \ right] \\&\ leq(2 | V |-2)^ {1-1 / q} \ sqrt [q] {| x |} \ sqrt [q] {\ nu_ {L ^ q}(g)},\ end {aligned} \],其中最后一步归因于詹森的不等式。这类似于CSMC的对应范围,除了前导项是$ \ sim n ^ {1 + 1 / q} $。对CSMC错误的$ \ sqrt [q] {| K |} $依赖会导致$ L ^ q $的损失,这可能会导致先验直觉$ \ sim n ^ {2 / q} $(注意类与边缘)。额外的$ \ sim n ^ {1-1-/ q} $项是因为在CSMC的约束图结构中,$ \ kappa(p ^ *,p ^ {**})= 2 $,即独立于$ n $。

由于最佳对抗性$ \ delta $在$ p ^ * $上为正,在$ p ^ {**} $上为负,因此上述界限也适用于单边$ L ^ q $损失,定义为\ [L ^ q _ {(1)}(\ hat y,y)= \ lfloor(2 \ 1_ {e \ in p ^ *}-1)(y-\ hat y)| y-\ hat y | ^ {q-1 } \ rfloor,\]其中$ \ lfloor x \ rfloor = \ max(x,0)$。下 单方面损失,不会低估最优路径上的边缘值,也不会高估不在最优路径上的边缘值。因为$ L ^ q _ {(1)} $损失的上限是$ L ^ q $损失,所以此损失函数可改善界限。

将$ q \减至1 $(即单面绝对损失)可得出该族中的最佳边界\\ r [{spath}(h_g)\ leq | x | \ nu_ {L ^ 1 _ {(1)}}(g),\]尽管应注意,这种推导技术在$ q = 1 $时无效(由于缺乏连续微分,因此不适用KKT)。但是,可以直接在$ q = 1 $处显示边界有效。

遗憾的是,损失$ L ^ 2 $ 为了推导出后悔界限,我们在错误界限推导中放宽了给予对手不必要的自由度。特别是,由于将回归变量仅定义为$ x $的函数,因此不应允许对手为每对$(x,f)$选择一个单独的$ \ delta $。

考虑具有相关条件边缘成本分布$ D_ {f |的边缘实现$ x $。 x} $,并假设我们的回归器是根据最小误差回归器的估计$ f ^ *(e)$减去$ \ delta(e)$,\ [g(e)= f ^ *(e)+ \ delta(e) 。 \]想象一个对手试图在这种情况下创建一定数量的SSP后悔,同时将这种情况下的回归后悔最小化。该对手面临以下问题:\ [\ begin {aligned}& \min_{\delta}\;E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in x} L \ bigl(f ^ *(e)+ \ delta(e),f(e)\ bigr)-L \ bigl(f ^ *(e),f(e)\ bigr)\ right] \\ \ mathrm {st} \ quad& E_{f \sim D_{f|x}} \left[ \sum_{e \in h_g (x)} f (e) \right] - \min_{p \in P}\;E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in}} f(e)\ right] = r。 \ end {aligned} \]显然,$ r $只能采用与$ h_g $做出的可能决定相对应的$ | P | $值之一。考虑每个这样的可能决定$ p ^ {**} $。然后,对手可以选择以下形式的系列:\ [\ begin {aligned}&\min_{\delta}\;E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in x} L \ bigl(f ^ *(e)+ \ delta(e),f(e)\ bigr)-L \ bigl(f ^ *(e),f(e)\ bigr)\ right] \\ \ mathrm {st} \; \ forall p \ neq p ^ {**},\;& \sum_{e \in p^{**}} f^* (e) + \delta (e) \leq \sum_{e \in p} f^* (e) + \delta (e). \end{aligned} \] For $L^2 (\hat y, y) = |y - \hat y|^2$ loss specifically, the objective function simplifies \[ \begin{aligned} & E_{f \sim D_{f|x}} \left[ \sum_{e \in x} L^2 \bigl (f^* (e) + \delta (e), f (e) \bigr) - L^2 \bigl (f^* (e), f (e) \bigr) \right] \\ &= \sum_{e \in x} 2 \delta (e) \left(f^* (e) - E_{f \sim D_{f|x}} [ f (e) ] \right) + \delta (e)^2 \\ &= \sum_{e \in x} \delta (e)^2, \end{aligned} \] since $f^*(e) = E_{f \sim D_{f|x}} [ f (e) ]$. 的refore the adversary's family of choices is given by \[ \begin{aligned} &\min_{\delta}\;\ sum_ {e \ in x} \ delta(e)^ 2 \\ \ mathrm {s.t。} \; \ forall p \ neq p ^ {**},\;& \sum_{e \in p^{**}} f^* (e) + \delta (e) \leq \sum_{e \in p} f^* (e) + \delta (e). \end{aligned} \] 的 KKT stationarity condition implies \[ 2 \delta (e) + \sum_{p \neq p^{**}} (1_{e \in p^{**}} - 1_{e \in p}) \mu_p = 0. \] Complementary slackness indicates $\mu_p = 0$ unless the constraint for $p$ is active. Let $p^* = \operatorname{arg\,min\,}_{p \in P} E_{f \sim D_{f|x}} [ \sum_{e \in p} f (e) ]$ be the true optimal path choice, in which case only $\mu_{p^*}$ need be non-zero. 的 stationarity condition simplifies to \[ 2 \delta (e) = (1_{e \in p^*} - 1_{e \in p^{**}}) \mu_{p^*}, \] which is more clearly stated as \[ \delta (e) = \begin{cases} \mu_{p^*} / 2 & \mbox{if } e \in p^* \mbox{ and } e \not \in p^{**} ; \\ -\mu_{p^*} / 2 & \mbox{if } e \not \in p^* \mbox{ and } e \in p^{**} ;\\ 0&\ mbox {否则。} \ end {cases} \]直观地讲,由于错误是凸状惩罚的,所以对手最好的方法是将相等和相反的错误集中在$ p ^ {**}中的那些边上$或$ p ^ * $。令$ \ kappa(p ^ *,p ^ {**})= | p ^ * | + | p ^ {**} | -2 | p ^ * \ cap p ^ {**} | $。代入不等式约束产生\ [\ begin {aligned} \ sum_ {e \ in p ^ {**}} f ^ *(e)-\ sum_ {e \ in p ^ *} f ^ *(e)& \ leq \ sum_ {e \ in p ^ *} \ delta(e)-\ sumq {e \ in p ^ {**}} \ delta(e)\\&= \ kappa(p ^ *,p ^ { **})\ sqrt {\ frac {| x |} {\ kappa(p ^ *,p ^ {**})}} \ frac {1} {| x |} \ sum_ {e \ in x} \ delta (e)^ 2} \\&\ leq \ sqrt {2 | V | -2} \ sqrt {| x |} \ sqrt {\ frac {1} {| x |} \ sum_ {e \ in x} \ delta(e)^ 2},\ end {aligned} \]最后步骤利用$ \ kappa(p ^ *,p ^ {**})\ leq 2 | V | -2美元。 对$ D_x $取期望会得出结果\ [\ begin {aligned} r_ {spath}(h_g)&\ leq \ sqrt {2 | V | -2} \ sqrt {| x |} \ E_ {x \ sim D_x} \ left [\ sqrt {\ frac {1} {| x |} \ sum_ {e \ in x} \ delta(e)^ 2} \ right] \\&\ leq \ sqrt {2 | V | -2} \ sqrt {| x |} \ sqrt {\ epsilon_ {L ^ 2}(g)},\ end {aligned} \],最后一步归因于詹森的不等式。后悔界限是回归后悔的平方根,缩放因子为$ \ sim n ^ {3/2} $。这比预期的先验要差一点,因为从CSMC在受限图结构上作为SSP的角度来看,对于$ L ^ 2 $回归的$ \ sqrt {| K |} $依赖性可能会使CSMC感到遗憾激发像$ \ sim n $这样的先验直觉(注意类与边之间的对应关系)。额外的$ n ^ {1/2} $是因为在CSMC的约束图结构中,$ \ kappa(p ^ *,p ^ {**}})= 2 $,即与$ n $无关。

没意见:

发表评论