《一种通用的自动生成方案》阅读报告

本文提出并评估了一种新方案的威力，该方案通过一组函数或关系在一组有限的变量上机械地生成搜索启发式问题。启发式是从参数化的近似方案中提取出来的，称为Mini-Bucket消除，允许在计算和精度之间进行可控的权衡。启发式用于指导分支定界和最佳优先搜索。他们的性能在两个优化任务上进行比较：在确定性数据库上定义的Max-CSP任务和在概率数据库上定义的最可能解释任务。基准是随机数据集以及编码和医疗诊断问题的应用。研究结果表明，所产生的启发式方法对于两种搜索方案均有效，允许在预处理（用于启发式生成）和搜索之间进行受控的权衡。

本文提出的方法与传统的启发式机械生成工作之间的主要区别在于它的前提。 我们假定问题是由依赖模型指定的：一组函数或关于变量的关系（例如贝叶斯网络，约束网络，可分解成本函数）。从依赖模型中，可以获得为问题定义搜索空间的状态和转换规则。 相反，启发式搜索的起点仅仅是搜索空间描述（例如：状态，操作符，初始和目标状态）。

我们的方案基于Mini-Bucket方案，这是一种基于桶消除框架的参数化近似算法。 近似值使用一个控制参数，可以调整准确度和效率。 已经提出并分析了概率性任务，例如找到最可能的解释（MPE），信念更新以及找到最大后验假设。在随机生成的噪声-OR网络，医疗诊断CPCS网络和编码问题上报告了令人鼓舞的实证结果。然而，正如这些算法产生的误差所证明的那样，在某些情况下，即使使用最高的可行精度水平，近似也是非常不理想的。在这种情况下，通过搜索增加小型桶近似可能是有成本效益的。

在本文中，我们演示了两种不同类别的优化任务的方法：解决约束优化中的Max-CSP问题，并在贝叶斯网络中找到最可能的解释。 我们将证明Mini-Bucket方法产生的函数可以作为为搜索创建启发式评估函数的基础。这些启发式提供了一个下界（用于最小化问题，如Max-CSP）或上界（用于最大化 问题，如MPE）对给定部分指派的最佳扩展的成本。由于迷你桶的精确度是通过边界参数来控制的，因此它允许启发式算法具有不同程度的精度，并产生一系列搜索算法，这些搜索算法可以对启发式计算和搜索进行折衷。我们评估两种迷你桶启发式 Branch-and-Bound1和Best-First搜索。

分枝定界以深度优先的方式搜索部分分配的空间。只有启发式函数计算出的边界可能优于当前最佳解决方案的值，它才会扩展部分分配。 Branch-and-Bound的优点在于它需要有限的内存量，可以用作任何时间方案;无论何时中断，分支和绑定输出到目前为止发现的最佳解决方案。Best-First在部分实例的统一边界中探索搜索空间，每个实例具有相同的评估函数值，同时通过首先扩展具有最佳启发式值的节点进行搜索。因为，如图所示，生成的启发式是可允许的和单调的，它们在Best-First搜索中的使用产生A *型算法。其性能很好理解。算法保证以最佳解决方案终止。当提供更强大的启发式技术时，它将探索更小的搜索空间，否则就需要大量的空间。知道Best-First算法是最佳的。也就是说，当给定相同的启发式信息时，就搜索空间大小而言，Best-First搜索是最有效的算法。尽管如此，Best-First有时会因为内存需求而失败。在过去的十年中，与启发式搜索社区中为A *所提出的方法类似的混合方法显然也具有潜在的价值。

在本文中，使用小型桶启发式（BFMB）和Best-First的算法通过小型桶式启发式（BBMB）的分支定界算法以经验方式呈现并进行评估。 MPE任务就死将它们与完整的桶消除（其性能对于其他完整算法（例如，联合树聚类）的典型性），针对小型桶近似方案以及针对迭代置信传播（用于编码网络的最近流行的近似）进行比较，将它们与Max-CSP的一些本地搜索方法和专用搜索算法进行比较。基准是Max-CSP，编码网络，噪声或网络和CPCS网络在解决MPE任务时的随机测试问题。

我们表明，两种搜索方法都以类似的方式利用启发式的优势：在所有问题类别中，以总时间衡量的启发式生成和搜索之间的最佳折衷点位于启发式强度的中间范围内。 随着问题变得越来越大，这个最优点逐渐增加到更具计算要求的启发式。 我们还表明，当Best-First和Branch-and-Bound获得相同的启发式信息时，如果启发式足够强大，给予足够的时间，Best-First有时大大优于分支限制，而且内存问题没有遇到。然而，有时Max-CSP问题中，Branch-and-Bound在某种程度上胜过了Best-First，特别是当提供准确的启发式时。

该论文提出并评估了一种新机制的能力，该机制对于由一组相关性指定的问题机械地生成搜索启发式。 该框架可以捕捉许多类别的问题，例如在信念网络，影响图，约束网络上定义的问题，以及通常称为图形模型的问题。 启发式是从应用于依赖模型的小型桶近似方法中提取的。 我们的实验证明了这种方案在改进一般搜索方面的潜力，表明小型桶启发式的准确性允许用户在预处理和搜索之间进行受控的权衡。 我们证明这一点：属性在分支定界和最佳优先搜索的范围内。 尽管准确度参数的最佳阈值可能不是事先预测的，但是当给定一类不太复杂的问题时，初步的经验分析可以提供信息。

此外，实验表明，小型桶启发式可以促进相对较大的问题的最佳？首先搜索，从而扩展该搜索方案的边界，该方案在计算上是最优的（相对于具有相同启发式的搜索算法）以实现精确解。 事实上，我们表明，Best-First有时会以3-8的分数超越分支机构。 然而，在其他情况下，正如我们对Max-CSP所观察到的，分支定界优于Best-First搜索。

我们在两类优化问题中评估了我们的方案 —— 约束网络上的Max-CSP和贝叶斯网络中的最可能的解释。 我们表明，使用Mini-Bucket启发式搜索可以与最广为人知的Max-CSP算法竞争，例如SLS和PFC-MRDAC，特别是当网络相对稀疏时，BBMB优于SLS和PFC-MRDAC。 我们还表明，当小噪声较小且网络相对较小时，使用小型桶式启发式搜索可以与用于概率解码的最佳已知近似算法（如IBP）相竞争。 显然，当问题规模增加时，BBMB和BFMB通常需要更多时间。然而，和IBP一样高效，其性能不会随着时间而改善。

由于Mini-Bucket消除适用于各种任务，如概率推理和决策制定，这里提出的方案有可能被广泛应用。