ACM通信

的观点

算法与预测

作者:Michael Mitzenmacher, Sergei Vassilvitskii
ACM通信，2022年7月，第65卷第7期，第33-35页
10.1145 / 3528087
评论

算法和数据结构的理论研究得到了最坏情况分析的支持，其中我们证明了运行时间、空间、近似比、竞争比或其他度量的边界，即使在最坏情况下也成立。事实证明，最坏情况分析对于理解算法的复杂性和实用性方面都是无价的，它提供了一些有用的特性，比如能够将算法用作构建块和子程序，并清楚地了解最坏情况的性能。然而，最坏情况分析的局限性越来越明显，并带来了新的挑战。在实践中，我们通常不会面对最坏的情况，问题就来了，我们如何调整我们的算法来更好地处理我们可能看到的各种实例，同时理想地保持一个严格的形式化框架，类似于我们通过最坏情况分析开发的框架。

一个关键问题是我们如何定义“我们可能看到的实例”的子集。在这里，我们来看看利用机器学习来回答这个问题的最新研究趋势。机器学习从根本上讲就是从小样本集中进行归纳和预测，因此我们对算法的附加信息建模。”年代输入作为对我们的问题实例的“预测”，以指导并有希望改进我们的算法。当然，虽然ML性能在短时间内取得了巨大的进步，但ML预测可能容易出错，产生意想不到的结果，因此我们必须注意算法对预测器的信任程度。此外，虽然我们建议使用基于ml的预测器，但预测实际上可以来自任何地方，而且简单的预测器可能不需要复杂的机器学习技术。例如，就像昨天一样”年代天气可能是今天的一个很好的预测器。”年代天气，如果给我们一系列类似的问题要解决，上一个问题的解决方案可能对下一个问题有很好的指导作用。

因此，我们想要的只是两全其美。我们寻求增强预测的算法:

• 一致性:当预测很好时，它们在每个实例的基础上接近最优;
• 稳健:当预测很糟糕时，它们在最坏情况的基础上接近最优;
• 平滑:算法在健壮和一致的设置之间优雅地插值;而且
• 可学习的:我们可以通过足够少的例子来学习我们试图预测的任何东西。

我们的目标是一种超越最坏情况分析的新方法。¹⁴我们识别已部署算法所看到的问题空间的一部分，并相应地自动调优其性能。

作为一个自然的开始示例，让我们考虑添加预测的二分搜索。在大型排序数组中查找一个元素时，经典的二进位搜索将目标元素与中间元素进行比较，然后对适当的一半进行递归(参见图1)．然而，想想我们是如何在书店或图书馆找到一本书的。如果我们正在寻找艾萨克·阿西莫夫的小说，我们会从书架的最开始开始搜索，然后环顾四周，如果我们最初的猜测太远，我们会反复加倍搜索半径图2)．我们可以使其更精确，以表明有一种算法，其运行时间在我们最初猜测的误差(由我们距离正确位置的距离来衡量)上为对数，而不是在数组中元素的数量上为对数，这是二分搜索的标准结果。由于误差不大于数组的大小，我们得到了一致(小误差允许我们在恒定时间内找到元素)和鲁棒(大误差恢复经典的算法O(日志n)结果，尽管有一个更大的常数因子)。

图1。执行传统的二分查找。

图2。二进制搜索的执行，从一个预测开始。

许多读者可能注意到这是插值搜索思想的一个变体，只使用一个预测的起点。(插值搜索使用数据来估计下一个比较点，而不是像二进位搜索那样总是选择中间位置。)基于这种观点，带有预测功能的算法已经存在了一段时间，而ML的爆发仅仅是为扩展这种想法和开发更丰富的形式化方法提供了动力。

最近在这些方面取得的成功使“温暖的开始”的概念正式形成。当重复解决类似的优化问题时，实践者通常不会每次都从零开始，而是在以前的解决方案附近开始搜索。Dinitz et al。⁴在最小代价完全匹配的情况下，分析将这种解作为预测的性能增益。在他们的设置中，一个人在相同的图上解决许多问题，但对每个实例使用不同的边权值，其中边权值可能，例如，来自一个分布。他们证明，给定一个对应线性程序对偶解的预测，他们可以从中计算出一个可行的对偶解，提高了总体运行时间，并扩展了“使用昨天的解”的启发式。

预测也被认为是减少一些数据结构空间使用的一种方法，例如Kraska等人的开创性工作。⁷学指标。作为预测如何节省空间的一个例子，我们首先解释Hsu等人后来的工作。⁶关于使用学习进行频率估计的数据结构。

频率估计算法用于近似地计算事物，例如路由器看到从每个IP地址发送的数据包的数量。由于为每个地址保留一个单独的计数器在空间和时间上都很昂贵，因此估计算法使用一些技术，例如将每个地址散列到共享计数器的表中(通常将每个地址散列到几个位置以获得健壮性)，然后在从其关联计数器查询IP地址时得到一个估计。当计数小的地址散列到与计数大的地址相同的位置时，会出现最大的计数估计错误，因为这时地址本身的计数应该很高。如果我们提前知道数量大的地址，我们可以给它们分配自己的计数器，并将它们与草图分开处理，避免了这样大的错误，并在更小的总体空间中获得更好的频率估计。Hsu等人的论文。⁶介绍了使用机器学习来预测哪些对象(在本例中是IP地址)拥有大量计数，并以这种方式将它们分离出来的思想。它们证明了特定情况的边界，并从经验上证明了高计数元素是可预测的，而且使用这种预测可以提高实际性能。

作为预测如何节省空间的另一个例子，Kraska等人。⁷提出一个学习布卢姆滤波器的框架。Bloom过滤器是集合隶属度的压缩数据结构;一组X， Bloom过滤器对任何一个都正确返回yesx这是真正的X，但对于不在集合中的键可能会给出假阳性。布卢姆过滤器有一个空间准确度权衡，更多的空间允许更少的假阳性。克拉斯卡等人的工作。⁷表明，如果一个集合可以被学习，也就是说，一个预测器可以不完美地预测一个元素是否在集合中，这可以用来推导一个学习的布鲁姆过滤器，该过滤器将预测器与标准布鲁姆过滤器结合在一起，以一种提高空间精度权衡的方式。我们把各种改进的学习过的布鲁姆过滤器的细节留给相关的论文。^7，9，17

也许毫不奇怪，使用预测有巨大影响的一个领域是在线算法，算法对传入的数据流作出响应，而未来是未知的。竞争分析的理论框架将在线算法的性能与最优算法之间的最坏情况之比作为衡量标准，因此“双竞争”算法总是在最优的2倍以内。应对可能发生的最坏情况通常是困难的，因此在这种情况下利用预测往往是非常强大的。例如，最近的一些结果考虑了调度问题。作业随着时间的推移到达一台服务器，必须对其进行调度;每个作业的成本是它到达和完成之间的时间，我们希望最小化所有作业的总成本。如果一份工作年代所需的处理时间在到达时已知，那么按最短剩余处理时间(SRPT)进行调度是最优的。但是，如果只知道工作时间的估计呢?最近的研究表明，如果每个工作都有真正的规模年代估计在[废话，作为为常量一个，b0 <b< 1 <一个，有一个具有竞争比的算法O（(a / b)日志²（a / b))，即使算法不知道一个而且b提前。也就是说，可以实现接近最优的性能，而性能会随着估计质量而优雅地下降。²在排队理论的背景下，类似地研究了带有预测的调度，其中模型具有概率假设，如泊松到达和独立和同分布的服务时间。在这种设置下，当使用估算时，SRPT可能执行得相当糟糕，即使估算再次限制在[废话，作为对于一个大的工作年代，但使用估计的SRPT的变体收敛于SRPT在完整信息为时的性能一个而且b见第1节，在里面O（a / b)的SRPT总是，再次在不知情的情况下一个而且b提前。¹⁵其他研究排队设置的工作表明，即使是一个小建议，预测一个工作是长还是短，对于一些合适的短或长的概念，也可以极大地提高性能。¹⁰一些其他的在线问题已经用预测进行了研究，包括缓存，⁸在线集群，和历史上有趣和有启发性的滑雪租赁¹³和部长的问题。^1，5

---

预测也被建议作为减少几种数据结构的空间使用的一种方法。

---

值得注意的是，在与数据驱动算法设计密切相关的领域，最近也有大量的工作。在较高的层次上，这一领域通常研究算法的调优。年代超参数，例如梯度下降的步长，或许多可能的初始化中的哪一个k-表示聚类最好。(Balcan的调查^3.提供了对这一领域的深入研究。)

带有预测的算法的研究领域才刚刚开始，但它似乎正在蓬勃发展，因为研究人员重新检查经典算法，看看当有良好的预测时，它们可以在哪些方面得到改进。这种经典算法和数据结构与机器学习的结合可能会在未来带来系统的显著改进，当有良好的预测时(就像在现实世界中一样)会带来好处，但当预测出错时(这在现实世界中似乎也会不可避免地发生)也会限制性能下降。

对于那些对更多技术细节感兴趣的人，我们有一个简短的调查，¹¹最近也有相关的在线研讨会。^12，16

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2022 ACM, Inc.

---

没有发现记录