显示带有标签的帖子 SSP. 显示所有帖子
显示带有标签的帖子 SSP. 显示所有帖子

2010年9月2日,星期四

成本敏感的多类别的随机最短路径:迈向更好的遗憾界限II

在上一篇文章中,我介绍了在不求助于成本敏感的多类分类(CSMC)的情况下,一致减少随机最短路径(SSP)的方法,并证明了两个界限。的 第一界 路径长度是二次方的,平均CSMC在路径空间上的遗憾是线性的。这对于确定减少量的一致性很有用,但不能令人满意,因为将SSP减少至回归表明对路径长度的线性依赖性是可能的。的 第二界 在路径长度上是线性的,在最大CSMC上线性是对路径空间的遗憾。由于操作员人数最多,因此无法令人满意。由于我有一个定理说,只有沿着最佳路径的遗憾才有助于整体遗憾,所以我觉得自己可以做得更好,但是不确定如何做到,因为我不知道最佳路径(这就是我所面临的问题我试图解决)。

幸运的是,还有可能进行其他改进。 兰福德 为我指出了一篇名为 通过动态编程进行策略搜索。像我的SSP到CSMC减少一样,在本文中,他们从最后一个步骤开始向后构建有限期策略,并在未来将学习到的策略用于估计延续成本。但是,它们也利用``基本分布'',这是对良好政策在特定时间步长诱发的状态分布的猜测。然后,他们证明了对性能的限制,特别是将其转换回SSP时,其路径长度是线性的,并且平均CSMC对于基准分布而言对顶点的后悔是平均的,加上在路径长度中线性且在路径中线性的项使用的基本分布与参考策略引起的状态的实际分布之间的差异。因此,通过合理地猜测最佳路径在哪里,可以通过针对这些猜测设置CSMC子问题输入来得出合理的策略。

以这种方式来看,我的减少本质上是使用统一的基本分布(即,认为路径的每个步骤上的每个顶点都具有相同的可能性)。这种分布的任何改善都可能导致SSP任务的改善。给定我的假设设置(一组带有边成本的历史图实现),我可以在每个历史实例上运行确定性SSP求解器以生成一组历史状态访问。尽管这与最佳策略的分布不同(此技术优化了每个实例的成本,而不是有条件的预期每个实例的成本),但它可能比均匀分布更好。

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)$。
For $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} \] where the first step is from the next step bound lemma, the second step leverages the induction hypothesis, 和 the third step is the from definition of $\Upsilon^*_{kv} (x)$. Noting that $\Upsilon^*_{1s} (x) = p^* (x)$ yields
\ [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} $风格''期望之间的关系没有很好的直觉子问题。

2010年8月19日,星期四

随机最短路径:持续减少对成本敏感的多类

在以前的帖子中
  1. 介绍了我寻求提出不涉及对标准OR算法提供估计值的替代决策程序的追求;
  2. 主动求助而无需追索权的随机最短路径(SSP),这是我追求的一部分,并分析了 减少回归;
  3. 描述了 SSP到成本敏感的多类分类的错误转换 (CSMC)基于 肖恩.
  4. 注意到 SSP天真地减少到CSMC,由 过滤树 将CSMC还原为二元分类,表明无需求助于CSMC就能有效,一致地减少SSP。
我建议访问这些帖子以了解我的表示法(公认的变化)以及正在考虑的SSP的确切变体。

现在,我提出了将SSP简化为CSMC的方法,其灵感来自过滤树。这种减少是一致的,即,对诱发的CSMC问题实现零后悔意味着对原始SSP问题实现零后悔。

算法 不像 肖恩式方法在这里,我训练分类器``从后到先''。如前一篇文章所述,这仅是可能的,因为这是没有追索权的SSP,因此延续成本不依赖于路径前缀。在具有追索权的SSP中,遍历期间会显示成本,因此延续成本的确取决于路径前缀。

在训练的每个阶段,我都在学习从任何顶点到特定长度的目标顶点的路径。最初的长度为1,因此从任何顶点到目标顶点只有一条可能的路径,并且不需要学习。为了学习长度为$ k $的路径,我使用先前学习的长度为$ k-1 $的路径分类器来定义从特定顶点中选择特定第一步的延续成本。一旦到达长度为$ n $的路径,就完成了。此公式利用了先前文章的简化,其中每个节点的自连接成本为零,路径的长度必须为$ n $。作为最后的后处理步骤,我可以删除路径中的任何循环以获取最大长度为$ n $的路径。

算法:路径网格火车
数据: 具有$ n $个顶点的完全连通图;目标顶点$ t $;源顶点$ s $。
数据: 训练数据集$ S $。
输入: 成本敏感的分类例程$ \ mbox {Learn} $。
结果: 经过训练的分类器$ \ {\ Psi_k | k \ in [1,n-2] \} $。
  1. 在[1,n] $中为$ v \定义$ \ gamma_ {n-1,v} = \ {\ {v,t \} \} $。
  2. 对于从$ n-2 $到1的路径中的每个步骤$ k $:
    1. $ S_k = \ emptyset $。
    2. 让$ \ {\ gamma_ {k + 1,v} | v \ in [1,n] \} $是从顶点$ v $开始到目标顶点$ t $的长度$ n-k-1 $的预测最佳路径。
    3. 对于每个示例$(x,f)\ in S $:
      1. 对于每个顶点$ v $从1到$ n $;或当$ k = 1 $时,只有$ v = s $:
        1. 将继续通过顶点$ w $的估计成本定义为$ c_w(k,v)= f(e_ {vw})+ \ sum_ {e \ in \ gamma_ {k + 1,w}} f(e)$。
        2. 将最低成本定义为$ w ^ *(k,v)= \ operatorname {arg \,min \,} _ w c_w(k,v)$。
        3. $ S_k \ leftarrow S_k \ cup \ left \ {\ bigl((x,v),w ^ *(k,v),c_w(k,v)\ bigr)\ right \} $。
      2. 令$ \ Psi_k = \ mbox {Learn}(S_k)$。
      3. 令$ \ gamma_ {k,v} = \ Psi_k(x,v)\ odot \ gamma_ {k + 1,\ Psi_k(x,v)} $。
  3. 返回$ \ {\ Psi_k | k \ in [1,n-2] \} $。
为了在一个新颖的例子上使用分类器,我折叠了从源顶点$ s $开始的预测变量。我提早停止了一步,并强迫最后一步到达目标顶点$ t $。实际上,我将删除生成路径中的任何循环,但是为了简化分析,我将其保留。
算法:路径网格测试
数据: 具有$ n $个顶点的完全连通图;目标顶点$ t $;源顶点$ s $。
数据: 图形实现$ x $。
结果: 路径$ \ pi:X \至V ^ n $。
  1. $ \ pi_1(x)= s $。
  2. $ \ pi_n(x)= t $。
  3. $ \ pi_ {k + 1}(x)= \ Psi_k(x,\ pi_k(x))$。
  4. 实际上,删除$ \ pi $中的所有循环;为了进行分析,请将它们留在里面。
分析 我的目标是限制最短的后悔\\ r_ {spath}(\ Psi)= E_ {x \ sim D_x} \ left [E_ {f \ sim D_ {f | x}} \ left [\ sum_ {k = 1} ^ {n-1} f(e _ {\ pi_k,\ pi_ {k + 1}})\ right]-\ min_ {p \ in P} \\; E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in p} f(e)\ right] \ right],\]其中$ \ pi:X \ to V ^ n $由“路径网格测试”给出算法。 (这个遗憾的定义与以前的文章约定略有不同,首先是因为路径定义为一系列顶点而不是一系列边,其次是因为路径必须长度为$ n $。我也介绍了符号$ e_ {ab} $表示顶点$ a $和$ b $之间的边。)

我想根据对诱导子问题的成本敏感后悔的角度来限制它,并遵循过滤树派生的技巧,通过定义如下诱导分布,将多个子问题折叠为一个子问题。设$ D = D_x \ times D_ {f | x} $为$(x,f)$的分布。定义成本敏感示例$ {x ^ \ prime,c)$的归纳分布$ D ^ \ prime_ \ Psi $,如下所示:
  1. 从$ D $中提取$(x,f)$。
  2. 在$ [1,n-2] $上绘制$ k $制服。
  3. 如果$ k = 1 $,$ v = s $;否则在$ [1,n] $上绘制$ v $制服。
  4. 设$ x ^ \ prime =(x,k,v)$。
  5. 令$ c_w(k,v)= f(e_ {vw})+ \ sum_ {e \ in \ gamma_ {k + 1,w}} f(e)$对于$ w \ in [1,n] $。
  6. 创建成本敏感的示例$ \ bigl(x ^ \ prime,c \ bigr)$。
注意$ D ^ \ prime_ \ Psi $取决于分类符的延续成本,因此取决于下标。最终,我想将最短路径后悔$ r_ {spath}(\ Psi)$与引起的成本敏感后悔\ [\ begin {aligned} q(\ Psi)&= E_{x^\prime \sim D^\prime_{\Psi,x}} \left[ E_{c \sim D^\prime_{\Psi,c|x}} \left[ c_{\Psi_k (x, v)} (k, v) \right] - \min_w\;E_ {c \ sim D ^ \ prime _ {\ Psi,c | x}} \ left [c_w(k,v)\ right] \ right] \\&= \frac{1}{1 + n (n - 3)} \left( q_{1s} (\Psi) + \sum_{k=2}^{n-2} \sum_{v=1}^n q_{kv} (\Psi) \right), \end{aligned} \] where \[ \begin{aligned} q_{kv} (\Psi) &= E_{x \sim D_x} \left[ q_{kv} (\Psi | x) \right], \\ q_{kv} (\Psi | x) &= E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{kv} (x)} f (e) \right] - \min_w\;E_ {f \ sim D_ {f | x}} \ left [f(e_ {vw})+ \ sum_ {e \ in \ gamma_ {k + 1,w}(x)} f(e)\ right]。 \ end {aligned} \]讨论$ r_ {kv}(\ Psi | x)$是有用的,这是长度为$ n-k $的路径$ P_ {kv} $从顶点开始的最短路径遗憾$ v $并以顶点$ t $结尾,\ [r_ {kv}(\ Psi | x)= E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in \ gamma_ {kv} } f(e)\ right]-\ min_ {p \ in P_ {kv}} \\; E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in p} f(e)\ right]。 \]按定义注意$ r_ {spath}(\ Psi)= E_ {x \ sim D_x} [r_ {1s}(\ Psi | x)] $。我可以将$ r_ {kv}(\ Psi | x)$与$ q_ {kv}(\ Psi | x)$关联起来,其方式类似于过滤树的推导。

引理:下一步绑定
令$ w ^ * $是后悔最小化路径\ [\ underset {p \ in P_ {kv}} {\ operatorname {arg \,min \,}}} E_ {f \ sim D_ {f | x }} \ left [\ sum_ {e \ in p} f(e)\ right]。\]然后对于所有$(k,v)\ in \ {(1,s)\} \ cup \ {(k ^ \ prime,v ^ \ prime)| k ^ \ prime \ in [2,n-2],v ^ \ prime \ in [1,n] \} $,或者
  1. $ r_ {kv}(\ Psi | x)= r_ {k + 1,w ^ *}(\ Psi | x)$如果$ \ Psi_k(x,v)= w ^ * $;要么
  2. $ r_ {kv}(\ Psi | x)\ leq q_ {kv}(\ Psi | x)+ r_ {k + 1,w ^ *}(\ Psi | x)$如果$ \ Psi_k(x,v) \ neq w ^ * $。
证明: 首先假设$ \ Psi_k(x,v)= w ^ * $。然后\ [\ begin {aligned} r_ {kv}(\ Psi | x)&= E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{k+1,w^*}} f (e) \right] - \min_{p \in P_{k+1,w^*}}\; E_{f \sim D_{f|x}} \left[\ sum_ {e \ in p} f(e)\ right] \\&= r_ {k + 1,w ^ *}(\ Psi | x)。 \ end {aligned} \]接下来假设$ \ Psi_k(x,v)\ neq w ^ * $。然后\ [\ begin {aligned} r_ {kv}(\ Psi | x)&= E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{kv}} f (e) \right] - \min_{p \in P_{kv}}\; E_{f \sim D_{f|x}} \left[\ sum_ {e \ in p} f(e)\ right] \\&= E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in \ gamma_ {kv}} f(e)\ right]-E_ {f \ sim D_ {f | x}} \ left [f(e_ {vw ^ *})+ \ sum_ {e \ in \ gamma_ {k + 1,w ^ *}} f(e)\ right] \\ &\quad + E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{k+1,w^*}} f (e) \right] - \min_{p \in P_{k+1,w^*}}\; E_{f \sim D_{f|x}} \left[\ sum_ {e \ in p} f(e)\ right] \\&\ leq E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in \ gamma_ {kv}} f(e)\ right]-\ min_w \; E_ {f \ sim D_ {f | x}} \ left [f(e_ {vw})+ \ sum_ {e \ in \ gamma_ {k + 1,w}} f(e)\ right] \\&\quad + E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{k+1,w^*}} f (e) \right] - \min_{p \in P_{k+1,w^*}}\; E_{f \sim D_{f|x}} \left[\ sum_ {e \ in p} f(e)\ right] \\&= q_ {kv}(\ Psi | x)+ r_ {k + 1,w ^ *}(\ Psi | x)。 \ end {aligned} \]
有了这个引理,我可以轻松证明以下定理。

定理:遗憾的结界
对于所有SSP发行版$ D $和所有成本敏感分类器$ \ Psi $,\ [r_ {spath}(\ Psi)\ leq(1 + n(n-3))q(\ Psi)。\]证明: 考虑一个固定的$ x $。通过$ r_ {kv}(\ Psi | x)\ leq \ sum _ {(k ^ \ prime,v ^ \ prime)\ in \ Omega_ {kv}} q_ {k ^ \ prime,v ^ \ prime}(\ Psi | x)$,其中$ \ Omega_ {kv} = \ {(k,v)\} \ cup \ {(k ^ \ prime,v ^ \ prime)| k ^ \ prime \ in [k + 1,n-2],v ^ \ prime \ in [1,n] \} $是路径长度和顶点对的集合,它们位于任何以$(k ,v)$。

当$ 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 \ Omega_ {k + 1,w ^ *}} q_ {k ^ \ prime,v ^ \ prime}(\ Psi | x)\\ &\ leq \ sum _ {(k ^ \ prime,v ^ \ prime)\ in \ Omega_ {kv}} q_ {k ^ \ prime,v ^ \ prime}(\ Psi | x),\ end {aligned} \]其中第一步来自引理,第二步利用归纳假设,第三步归因于遗憾的非负性。归纳终止于\ [r_ {1s}(\ Psi | x)\ leq \ sum _ {(k,v)\ in \ Omega_ {1s}} q_ {kv}(\ Psi | x)=(1 + n(n-3))q(\ Psi | x)。\]取双方对$ D_x $的期望即可完成证明。

与减少回归的比较 分析 通过回归降低SSP 损失$ L_2 $会产生$ \ sqrt {r} $依赖回归遗憾,其缩放因子为$ \ sim n ^ {3/2} $。对CSMC的减少导致对CSMC后悔的线性依赖,但比例因子为$ O(n ^ 2)$。不幸的是,界限并不能直接比较。

如果我进一步将CSMC简化为回归模型,则最终会得到$ O(n ^ {5/2})$缩放因子和对回归遗憾的$ \ sqrt {r} $依赖性。从直觉上来说,我应该能够通过CSMC还原为回归并获得与直接还原为回归相同的结果;这表明可以使用$ O(n)$比例因子。实际上,我从定理中分离出了引理,因为我希望证明使用引理(一个涉及$ n $数量,而不是$ n ^ 2 $的东西)的更严格的约束;但这是另一天。

2010年8月17日,星期二

通过过滤树的随机最短路径:思路

在之前的文章中,我谈到了带有追索权的随机最短路径(SSP),并分析了 减少回归 和一个 简化成本敏感的多类分类 (CSMC)通过 肖恩。后者之所以令人难以置信,是因为它仅导致潜在的CSMC问题的错误导致SSP后悔的局限,而回归的减少导致潜在的CSMC问题的遗憾导致了SSP后悔的局限。 (请参阅之前的文章 回归减少肖恩式还原 以讨论所分析的SSP的确切变体以及所使用的符号)。

我有充分的理由相信,基于潜在的CSMC遗憾而将CSMC减少到一定程度是可能的。我还没有完全解决这个问题,但是我的灵感来自于思考将SSP天真的还原为CSMC是什么样子。

首先,对以前的帖子进行了进一步的简化。和以前一样,我将要求所有路径的长度为$ n $,但是现在,我将允许任何节点以零成本连接到自身(不仅仅是目标节点)。这意味着我可以将每个潜在路径与以$ n $为基数的$(n-2)$位数字关联。有$ n ^ {n-2} $这样的路径,而直接简化为CSMC会将每个路径等同于一个类。通过这种天真的减少,最短路径后悔和对成本敏感的后悔是相同的。当然,我在这里忽略了很多结构,因为这些类没有独立的成本:它们是相关的,因为它们只是$ n ^ 2 $个数量上的不同总和。

由于这种朴素的归约方法有很多类,因此我将选择 过滤树 将CSMC简化为二进制分类。它的优点是,运行时计算的类数或$(n-2)\ log_2(n)$是对数的,这实际上看起来很合理。训练时间是另一回事:我将不得不在过滤树的所有内部节点训练$ n ^ {n-2} $个二进制分类器。

但是,等等,过滤器树让我们修复标签上的任何树。假设下面的$ n = 2 ^ m $,因此我不必考虑在树上缺少两个孩子的父母。我可以选择一棵树,使$ k ^ \ mathrm {th} $叶是$(n-2)$位数字$ n $,其值为$ k $。在这种情况下,在内部节点的第一级,所有要比较的路径将共享除最后一位以外的所有其他路径,因此不必学习$ n ^ n / 2 $二进制分类器,我只需学习$ n ^ 2/2 $二进制分类器。这是因为共享除最后一位以外的所有路径的两条路径的成本仅取决于最后两位,而不取决于路径前缀的其余部分。 (这是重要的部分,仅因为这是没有追索权的SSP,所以是正确的:如果这是有追索权的SSP,则在遍历路径时会显示成本,而剩余边际成本的条件分布将是路径的函数)。在内部节点的第二层,我只需要学习$ n ^ 2/4 $分类器;对于内部节点的第一个$ \ log_2(n)$级别,我只需要总共学习$ n ^ 2 $个分类器。

在内部节点的$(\ log_2(n)+1)^ \ mathrm {th} $级别上,正在比较的路径共享除最后三个数字外的所有数字;最后一位由第二位最后一位通过较低级别的内部节点确定。这意味着对于下一个内部节点的$ \ log_2(n)$级别,我仍然只需要总共学习$ n ^ 2 $个分类器。

按照这种逻辑,我必须在训练时学习总计$ n ^ 2(n-2)\ log(n)$个二进制分类器,并在测试时进行$(n-2)\ log(n)$分类。过滤树的后悔是内部节点后悔的总和,这表明$ n ^ {n-2} $领先的因素,但因为只有$ n ^ 2(n-2)\ log_2(n实际的不同内部节点可能希望后悔会随着数量的减少而扩大。

现在,我必须深入研究过滤器树并真正理解它,并将其转化为SSP的特定简化。

2010年8月12日,星期四

通过Searn的随机最短路径

在一个 以前的帖子 我讨论了无追索权的随机最短路径(SSP),并分析了回归的减少量(即分析了估算边际成本的策略,然后对估计使用标准的确定性最短路径求解器)。分析是根据最短路径选择器$ h的遗憾进行的:X \到P $将边实现$ X $映射到(希望是短的)路径$ P $,\ [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],\]其中$ D_x $是边的分布,$ D_ {f | x} $是边的条件分布边际成本(请参阅 以前的帖子 以获得更完整的符号说明以及所分析的SSP精确变体的说明)。

我还注意到,成本敏感的多类分类(CSMC)看起来像浅表上的SSP。这种对应关系表明,通过减少一系列CSMC问题,可以攻击SSP。理论上探索了顺序决策问题与CSMC之间的一般对应关系 兰福德和扎德罗兹尼 并实际上被 杜安(Duame)等。等 通过 肖恩 算法。将SSP减少到CSMC是Searn的特例。

就我而言 目前的痴迷 这种减少非常令人兴奋,因为它提供了一种替代机制来解决非平凡问题,而不是直观的``让我们估算系数并使用标准求解器''策略。此技巧是否适用于我遇到的更复杂的问题,以及在实践中是否能带来良好的解决方案,还有待观察。

最佳子结构 一千英里(最短路径)的旅程从一个(最佳最短)步骤开始。特别是,给定任何起始顶点$ s $,中间顶点$ v $和目标顶点$ t $,从$ s $到$ t $的最短路径$ p ^ * _ {st; v} $包括$ v $通过\ [p ^ * _ {与$ s $和$ v $之间的最短路径$ p ^ * _ {sv} $和$ v $和$ t $之间的最短路径$ p ^ * _ {vt} $相关。 st; v} = p ^ * _ {sv} \ odot p ^ * _ {vt},\]其中$ \ odot $表示路径串联。通过将$ v $作为$ s $的相邻顶点的集合,这建议通过\ [c(v; s,t)= f(\ {s)为顶点$ s $定义决策问题的成本向量。 ,v \})+ \ min_ {p_ {vt} \ in P_ {vt}} \\; \ sum_ {e \ in p_ {vt}} f(e)-\ min_ {p_ {st} \ in P_ {st}} \; \ sum_ {e \ in p_ {st}} f(e)。 \]基本上,在顶点$ s $处选择边的成本定义为当前边成本加上遍历该边后可能的最低总成本,再减去从该顶点开始的最低总成本。

由于我们的SSP变体始终从相同的起始顶点开始,因此很清楚如何开始此过程:对于每个训练实例,计算从与起始顶点相邻的每个顶点到目标的最短路径,并从中添加边缘成本。起始节点,并使用最喜欢的CSMC算法生成``第一步''策略。接下来的步骤呢? 兰福德和Zadrozny的一个主要见解是,可以通过使用在前$ k $步骤中学习到的分类器序列产生的测试实例分布来训练步骤$ k + 1 $的分类器,即子分类器可以是学到了``至上''。

遗憾的结界 为了简化分析,我将约束所有长度为$ n $的路径;对于在实践中可能遇到的较短路径,我可以添加从目标节点到其自身的零成本连接,并强制任何路径生成算法在目标处包括一定数量的自连接。

令$ \ pi ^ {(n)} $为由$ n $成本敏感分类器的组合定义的最短路径选择器,\ [\ pi ^ {(n)}(X)= \ bigodot_ {k = 1} ^ n \ rho_k(X),\]其中$ \ rho_k:(X,P_ {k-1})\ to E $是$ k ^ \ mathrm {th} $成本敏感分类器,将输入边缘实现和从起始顶点开始的长度为$ k-1 $的路径,并输出边缘,该边缘是部分路径的确定扩展。考虑固定图形实现$(x,f)$和生成路径中固定位置$ k $的成本敏感误差,\ [\ epsilon_k(x,f)= f \ left(\ rho_k(x,\ pi ^ {(k-1)}(x))\ right)+ \ sum_ {e \ in \ Psi_k(x,f)} f(e)-\ sum_ {e \ in \ Psi_ {k-1}( x,f)} f(e),\]其中$ \ Psi_k(x,f)$是将$ \ rho_k $选择的顶点连接到目标顶点的路径的最佳扩展,其中$ \ Psi_0(x ,f)$是图形实现的最短路径。如果我们对最后两个项望远镜的所有$ k $求和,并且由于$ \ Psi_n(x,f)$是空路径,我们得到\ [\ sum_ {k = 1} ^ n \ epsilon_k(x,f )= \ sum_ {e \ in \ pi ^ {(n)}} f(e)-\ min_ {p \ in P} \; \ sum_ {e \ in p} f(e)。 \]取双方对$ D_ {f | x} $的期望得出\ [\ begin {aligned} \ sum_ {k = 1} ^ n E_ {f \ sim D_ {f | x}} \ left [\ epsilon_k(x,f)\ right]&= E_{f \sim D_{f|x}} \left[ \sum_{e \in \pi^{(n)}} f (e) \right] - E_{f \sim D_{f|x}} \left[ \min_{p \in P}\;\ sum_ {e \ in p} f(e)\ right] \\&\geq E_{f \sim D_{f|x}} \left[ \sum_{e \in \pi^{(n)}} f (e) \right] - \min_{p \in P}\;E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in p} f(e)\ right]。 \ end {aligned} \]取双方对$ D_x $的期望,得到边界\ [r_ {spath}(\ pi ^ {(n)})\ leq \ sum_ {k = 1} ^ n E_ {(x,f)\ sim D} \ left [\ epsilon_k(x,f)\ right]。 \]因此,对随机最短路径的遗憾由每个生成的子问题的成本敏感误差之和所限制。不幸的是,由于这是一个误差范围,因此它不能直接与为简化回归而得出的遗憾范围相提并论。

错误界限不如后悔界限可取,因为在使界限虚空的嘈杂问题上,最大可能的错误可能很高。这里一定有遗憾吗?是的,没有。如果我们通过\ [\ tilde c(v; s,t)= f(\ {s,v \})+ \ min_ {p_ {vt} \ in P_ {vt}} \; E_ {f \ sim D_ {f | x}} \ left [\ sum_ {e \ in p_ {vt}} f(e)\ right],\]然后与上述类似的参数可以显示最短路径后悔是相同的加上对成本敏感的遗憾。不幸的是,计算$ \ tilde c $需要解决SSP的问题,这正是我们所追求的。在Searn术语中,我们可以使用良好的初始策略,但不能使用最佳初始策略。

策略迭代 虽然我们在路径选择器的后悔和分类子问题的错误之间存在某种关系,但还是可以改进的:子问题中使用的成本向量对与每个决策相关的成本持乐观态度。在实践中,后续的分类器会犯错误,这从根本上来说是因为它们无法访问边缘成本信息,而实际上是因为我们在每一步都没有实现最佳的成本敏感型分类器。用对后续分类器将要犯的错误类型敏感的成本来训练较早的分类器应该会导致改进,但这是鸡与蛋:成本向量定义了分类器,分类器定义了策略,而策略定义了成本-向量。训练子问题``最后到第一个''无济于事,因为较早的分类器为较晚的分类器定义了训练样本的分布,再次导致了循环依赖(并且这种策略无法像``第一个那样''进行分析-至最后'')。

一种想法是使用分类器的先前迭代来定义延续成本,然后训练另一次迭代,从而创建一系列有望改善的路径选择功能。 肖恩调整了保守策略迭代的框架,该框架还使用当前策略来定义延续成本,但通过在旧策略和新策略之间进行插值来形成下一个策略,这比仅使用新策略更强大。这种插值是随机的,因此我们将转向谈论路径选择策略。

假设我们有一条当前路径来选择策略$ \ psi:X \ times E ^ * \ to \ mathbb {P}(E ^ *)$ $ \ ldots $这里的符号被严重破坏了,但是基本上$ \ psi $映射了边缘实现和通往目标的连续路径上的概率分布的部分路径。最初,我们的$ \ psi $将是由上面定义的成本敏感分类器序列给出的(确定性)路径选择策略。给定$ \ psi $和训练实例$(x,f)$,我们可以通过\ [c(x,\ zeta)= f为$ k ^ \ mathrm {th} $步骤生成决策问题的成本向量(\ {s,v \})+ E_ {p \ sim \ psi(x,\ zeta)} \ left [\ sum_ {e \ in p} f(e)\ right]-\ min_v \; E_ {p \ sim \ psi(x,\ zeta \ odot \ {s,v \})} \ left [\ sum_ {e \ in \ {s,v \} \ odot p} f(e)\ right] ,\]其中$ \ zeta $(长度为$ k-1 $的部分路径)是一个随机变量,其分布是通过在训练实例上运行当前策略来给出的(我们可以通过Monte-Carlo在实践中实现), $ s $是$ \ zeta $的最终顶点,$ v $是$ s $的相邻顶点。训练成本敏感的分类器集会产生一个新的(确定性)策略$ \ varphi $,该策略通过随机插值与现有策略结合,\ [\ psi_ {new} =(1-\ beta)\ psi + \ beta \ varphi,\]和$ \ beta \ in [0,1] $。随机插值意味着以概率$(1- -beta)$使用$ \ psi $,以概率$ \ beta $使用$ \ varphi $。可以选择具有理论保证的$ \ beta $,但Searn作者建议在$ [0,1] $中进行行搜索,以获得最佳的每次迭代$ \ beta $(以及策略迭代的停止点)使用开发集,即与用于训练成本敏感分类器的数据不同的标记数据集。经过$ m $次训练后,我们将得出以下格式的策略:\ [\ psi = \ sum_m \ alpha_m \ pi ^ {(n)} _ m,\]其中$ \ alpha_m \ geq 0 $和$ \ sum_m \ alpha_m = 1 $,即在路径中的每个步骤$ k $,我们都有概率敏感的分类器的概率组合。


非完全连通图 为了简化以上讨论,我假设图形实现是完全连接的。对于回归减少,很容易看到如何修改策略以解决未完全连接的图。首先,在训练时,当前实现中不可行的边不会合并到训练数据集中。其次,在测试时,argmax的范围仅限于当前实现中可行的那些范围。这里的可行性是指边存在,并且通过遍历获得的顶点在剩余路径长度内具有到目标节点的路径。从本质上讲,回归器尝试了解边缘可行的条件预期成本,并且仅在边缘可行的情况下进行查询。 (由于这是没有追索权的SSP,因此,边实现$ X $必须包含有关存在或不存在边的显式信息:对于图结构,不存在探索和反馈)。

对于这种减少CSMC的方法,正确的方法对我来说还不太清楚。如果图形结构不是完全连接而是固定的,那么就没有困难:只需在CMSC分类器中使用较少的类即可。问题在于图形结构是可变的。一种想法是使用与不可行的边缘相关的非常大的成本,因为下降的CSMC学习者应该学习``边缘可行性特征''与非常大的成本之间的关系;如果仍然在测试时选择了不可行的边,则可以用随机的可行边代替。如果图连通性结构主要由几种情况组成,那么针对每种连通性条件训练多个分类器可能是一个不错的策略。在那种情况下,可以通过随机选择一个可行的边缘来完成对新型连接结构的推广。也许这两种策略可以与``大笔成本''培训策略结合起来用作备用。

如果将CSMC子问题本身简化为回归,则可以使用与直接简化为回归来管理变量图结构相同的技巧。这表明减少回归的优势和劣势:它解决了一个更棘手的问题,即从允许的类别的任何子集中选择最佳类别的能力。如果只对最好的课程感兴趣,那么这种额外的功能就是浪费的。确实,当扮演对手的角色时,通过使无关类别的估计完美,可以实现减少回归的遗憾。

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$, 和 single destination node $t$, 和 set of $K$ intermediate nodes indexed by $k$ with source costs $f (s, k)$ 和 with sink costs $f (k, t) = 0$. In this case all paths are of the form $\{ (s, k), (k, t) \}$ for some $k$ 和 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{ 和 } e \not \in p^{**} ; \\ -\alpha & \mbox{if } e \not \in p^* \mbox{ 和 } 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{ 和 } e \not \in p^{**} ; \\ -\mu_{p^*} / 2 & \mbox{if } e \not \in p^* \mbox{ 和 } 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 $无关。