ACM通信

的观点

算法与预测

作者:迈克尔·米岑马赫，谢尔盖·瓦西里维茨基
ACM通信，2022年7月，第65卷第7期，33-35页
10.1145 / 3528087
评论

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

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

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

• 一致性:当预测良好时，它们在每个实例的基础上接近最优;
• 鲁棒性:当预测结果不好时，它们在最坏情况下接近最优;
• 平滑:算法在稳健一致的设置之间进行优雅的插值;和
• 可学习性:我们可以通过足够少的例子来学习我们试图预测的任何东西。

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

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

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

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

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

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

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

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

作为预测如何节省空间的另一个例子，Kraska等人。⁷提出一个学习布鲁姆过滤器的框架。Bloom过滤器是集成员关系的压缩数据结构;一组X， Bloom过滤器正确地为any返回yesx这是真正的X，但对于不在集合中的键可能会给出假阳性。布卢姆过滤器有一个空间精度权衡，其中更多的空间允许更少的误报。Kraska等人的工作。⁷这表明，如果一个集合是可以学习的，也就是说，一个预测器可以不完美地预测一个元素是否在集合中，那就可以用来导出一个学习的布卢姆过滤器，该过滤器将预测器与标准的布卢姆过滤器结合在一起，以一种提高空间精度权衡的方式。我们把各种改进的布鲁姆过滤器的细节留给相关的论文。^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股份有限公司

---

没有发现记录