2010年9月2日,星期四

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

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

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

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

没意见:

发表评论