ICLR 2022 | 利用预测信息的在线设施选址算法

本文是 ICLR 2022 入选论文《Online Facility Location with Predictions》的解读。该论文由北京大学前沿计算研究中心姜少峰课题组与上海财经大学，上海交通大学合作完成，根据理论计算领域惯例，作者按姓名首字母排序。文章提出了一种利用预测信息来解决在线设施选址问题的算法，在实验中，该算法在预测较为准确时有着比传统算法更优秀的表现。

图文 | 张宇博

北京大学姜少峰课题组

论文链接：https://arxiv.org/abs/2110.08840

1

研究背景

在机器学习领域蓬勃发展的同时，人们也在思考机器学习技术能否给计算机科学中的其他问题提供新的解决方案。近些年来，一些研究者将目光投向了在线问题。由于在线问题的限制，算法需要在仅得到一部分输入的情况下做出全局决策。如果我们可以通过机器学习等技术发掘数据中的规律，为在线算法提供对于未来输入的预测，那么就可以超越传统的最坏情况分析，实现更好的近似比。

本文研究的在线问题是 Online Facility Location （下简称 OFL）。Facility Location 是一个类似于 k-聚类（例如 k-means/k-median）的问题。在这个问题中，我们同样需要把输入的点集划分成若干个聚类，并为每个点付出它到对应的聚类中心距离的代价。和 k-聚类不同的是，Facility Location 允许设立任意多个聚类中心，但每一个都需要额外付出 w 的代价。OFL 问题在其离线版本的基础上，改为按某种顺序给出输入的点集，每次只给出一个点，并要求算法立即输出它对应的聚类中心。

我们采用竞争比来衡量在线算法的性能。竞争比是一种被广泛采用的衡量在线算法精确度的方法，针对 OFL，在线算法的竞争比定义为该算法产生的聚类方案的代价，与离线/全信息版本下的最优解的代价的比值。这反映了在线设定下算法因为信息不完备所导致的代价。

Adam Meyerson 于2001年首次研究了 OFL 问题并提出了一个 竞争比的在线算法。随后 Dimitris Fotakis 提出了一个 竞争比的算法，并证明任何算法在最坏情况下的竞争比都至少是 ，将 OFL 问题做到了最优。我们希望通过引入新的预测技术，突破传统的最坏情况分析，为 OFL 问题提供新的解决思路。

2

理论结果

本文是第一篇研究如何利用预测解决 Non-Uniform Cost 情况下的 OFL 问题的文章（Non Uniform Cost 即在不同的点设立聚类中心的代价是不同的，用代价函数 w 表示）。

本文使用的预测模型十分简单，我们的算法在原有输入的基础上，还会接受一个额外的预测作为输入。对于输入的每一个点，预测器都会预测出最优解中这个点所对应的聚类中心算法的近似比与预测器的预测准确度相关，接受的预测越准确，算法的近似比就越小。

我们使用预测和最优解的实际输出的 距离 作为衡量预测准确度的指标（距离越小越准确）。

图注：基于 的近似比理论上下界

由上图可见，本文提出的算法在预测完全准确时可以做到常数近似，突破了传统的最坏情况分析，而在预测最坏的情况下的表现也几乎与之前的最优算法持平。此外本文还进一步分析了文中预测模型下近似比的理论下界，分析表明本文算法的近似比已经接近最优。

3

算法设计

本文提出的算法基于 Meyerson 算法，即 Meyerson 最初研究 OFL 问题时提出的算法。尽管该算法的近似比在 Non-Uniform Cost 下并不是最优，但它十分简洁，易于分析，并且具有很好的性质。

Meyerson 算法的分析基于一种分层思路：单独考虑最优解中的某个聚类中心 f* 和数据中被分配到 f* 的点集，如果当前我们已经设立了一个距离 f* 不超过 d 的聚类中心，那么该算法可以保证未来输入的近似比为 。

利用这种性质，我们设计了一种辅助算法，将辅助算法和 Meyerson 算法同时运行。辅助算法在设计时保证其花费的代价一定不超过 Meyerson 算法的代价，故不会影响最后的近似比分析。算法的执行分为两个阶段：

第一阶段，在预测的帮助下，辅助算法可以建出距离最优解只有 的近似解。这个阶段很快就会结束，辅助算法保证 Meyerson 算法在这个阶段花费的总代价不会影响到最终的近似比。

第二阶段，由于前一阶段的铺垫工作，Meyerson 算法在此阶段的近似比为 ，实现了更优的近似比。

4

实验结果

我们将上述算法思路进行实现，并在四个聚类算法常用的数据集上进行测试。共有三个欧氏空间下的数据集以及一个图上最短路度量的数据集，其中有三个数据集是 Uniform Cost 的，另外一个是 Non-Uniform Cost 的。数据集的参数概要见下图。

我们为算法提供了两个参照对象，第一个是完全不依赖预测的原始 Meyerson 算法，第二个是直接输出预测结果的算法。需要说明的是，Meyerson 算法的表现在 Uniform Cost 下已经十分优秀，在随机顺序输入下可以达到常数近似。下图展示了三个算法在不同预测质量下的近似比。

5

总结与展望

本文提出了一种利用预测解决 OFL 问题的算法，不仅能在预测较为准确时超越不基于预测的理论下界，还能够在预测最坏时做到近似最优。而在我们设计的实验中，该算法的表现出与预期相符的水平。

如何设计有效利用预测的算法仍是一个新的研究方向，还有很多类似 OFL 的几何问题有待进一步的研究。未来，我们期待本文的技术不仅可以用于解决与 OFL 直接相关的问题，也能在其他几何问题上有更广泛的应用。