2010年8月12日,星期四

通过Searn的随机最短路径

在一个 以前的帖子 我讨论了无追索权的随机最短路径(SSP),并分析了回归的减少量(即分析了估算边际广东11选五开奖号码查的策略,然后对估计使用标准的确定性最短路径求解器)。分析是根据最短路径选择器$ 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} $是边的条件分布边际广东11选五开奖号码查(请参阅 以前的帖子 以获得更完整的符号说明以及所分析的SSP精确变体的说明)。

我还注意到,广东11选五开奖号码查敏感的多类分类(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 $定义决策问题的广东11选五开奖号码查向量。 ,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 $处选择边的广东11选五开奖号码查定义为当前边广东11选五开奖号码查加上遍历该边后可能的最低总广东11选五开奖号码查,再减去从该顶点开始的最低总广东11选五开奖号码查。

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

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

令$ \ pi ^ {(n)} $为由$ n $广东11选五开奖号码查敏感分类器的组合定义的最短路径选择器,\ [\ pi ^ {(n)}(X)= \ bigodot_ {k = 1} ^ n \ rho_k(X),\]其中$ \ rho_k:(X,P_ {k-1})\ to E $是$ k ^ \ mathrm {th} $广东11选五开奖号码查敏感分类器,将输入边缘实现和从起始顶点开始的长度为$ k-1 $的路径,并输出边缘,该边缘是部分路径的确定扩展。考虑固定图形实现$(x,f)$和生成路径中固定位置$ k $的广东11选五开奖号码查敏感误差,\ [\ 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]。 \]因此,对随机最短路径的遗憾由每个生成的子问题的广东11选五开奖号码查敏感误差之和所限制。不幸的是,由于这是一个误差范围,因此它不能直接与为简化回归而得出的遗憾范围相提并论。

错误界限不如后悔界限可取,因为在使界限虚空的嘈杂问题上,最大可能的错误可能很高。这里一定有遗憾吗?是的,没有。如果我们通过\ [\ 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],\]然后与上述类似的参数可以显示最短路径后悔是相同的加上对广东11选五开奖号码查敏感的遗憾。不幸的是,计算$ \ tilde c $需要解决SSP的问题,这正是我们所追求的。在Searn术语中,我们可以使用良好的初始策略,但不能使用最佳初始策略。

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

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

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


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

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

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

没意见:

发表评论