算法揭秘：如何用最少数据解决复杂问题的最佳方案

确定在像纽约市这样的都市地下新地铁线路的最便宜的路径是一项巨大的规划挑战——涉及数千条潜在路线穿过数百个城市街区，每条街区的建设成本都不确定。传统观点认为，需要在多个地点进行广泛的实地研究，以确定某些城市街区下挖掘的成本。

因为这些研究成本高昂，城市规划者希望尽量少做研究，同时收集最有用的数据来做出最佳决策。

在几乎无数的可能性中，他们如何知道从哪里开始呢？

麻省理工学院的研究人员开发了一种新算法，可能会有所帮助。他们的数学框架能够证明，识别出保证找到问题最佳解决方案所需的最小数据集，通常需要的测量次数少于传统方法所建议的。

在地铁路线的情况下，这种方法考虑了问题的结构（城市街区的网络、建设限制和预算限制）以及与成本相关的不确定性。然后，算法识别出实地研究的最小位置集，以保证找到最低成本的路线。该方法还指出如何利用这些战略性收集的数据来做出最佳决策。

这个框架适用于一类广泛的结构化决策问题，涉及不确定性，比如供应链管理或电力网络优化。

“数据是人工智能经济中最重要的组成部分之一。模型在越来越多的数据上进行训练，消耗巨大的计算资源。但大多数现实世界的问题都有可以利用的结构。

“我们已经证明，通过仔细选择，可以保证在小数据集上获得最佳解决方案，我们提供了一种方法来准确识别您需要哪些数据，”麻省理工学院电气工程与计算机科学系（EECS）的MathWorks教授、系主任、施瓦茨曼计算学院副院长以及信息与决策系统实验室（LIDS）的主要研究员Asu Ozdaglar表示。

Ozdaglar是发布在arXiv预印本服务器上的一篇关于该研究的论文的共同作者之一，其他共同首席作者包括EECS研究生Omar Bennouna和他的兄弟Amine Bennouna，后者是麻省理工学院的前博士后，现在是西北大学的助理教授；共同高级作者Saurabh Amin是运筹学中心的共同主任，麻省理工学院土木与环境工程系的教授，以及LIDS的主要研究员。该研究将在神经信息处理系统会议（NeurIPS 2025）上展示，会议将于11月30日至12月5日在圣地亚哥举行。

最佳性保证

最近的运筹学研究主要关注如何更好地利用数据来做决策，但这通常假设这些数据已经存在。

麻省理工学院的研究人员首先提出了一个不同的问题——解决一个问题所需的最少数据是什么？有了这些知识，人们就能收集更少的数据来找到最佳解决方案，从而在实验和训练人工智能模型时节省时间、金钱和精力。

研究人员首先开发了一个精确的几何和数学模型来描述数据集的充分性。每一组可能的成本（旅行时间、建设费用、能源价格）使某个特定决策成为最佳。这些“最佳性区域”划分了决策空间。如果一个数据集能够确定哪个区域包含真实成本，那么这个数据集就是足够的。

这种特征描述为他们开发的实用算法提供了基础，该算法能够识别保证找到最优解的数据集。

他们的理论探索表明，通常只需要一个小而精心挑选的数据集。

“当我们说一个数据集是足够的时，我们的意思是它包含了解决问题所需的确切信息。你不需要把所有参数都估计得很准确；只要有能区分不同最优解的数据就行，”阿敏·本努纳说。

基于这些数学基础，研究人员找到最小的足够数据集。

捕捉正确的数据

使用这个工具时，用户需要输入任务的结构，比如目标和约束，还有他们对问题的已知信息。

例如，在供应链管理中，任务可能是减少数十条潜在路线网络的运营成本。公司可能已经知道某些运输路线特别贵，但对其他路线的信息却不够完整。

研究人员的迭代算法通过反复询问：“是否存在任何场景会以我的当前数据无法发现的方式改变最佳决策？”来工作。如果是，它会添加一个能够捕捉这种差异的测量。如果不是，则数据集被证明是足够的。

该算法确定了需要探索的位置子集，以确保找到最低成本的解决方案。

然后，在收集这些数据后，用户可以将其输入到研究人员开发的另一个算法，该算法找到最佳解决方案。在这种情况下，这些路线将是成本最优供应链中需要包含的运输路线。

奥马尔·本努纳说：“该算法保证，无论在您的不确定性范围内可能发生什么场景，您都能找到最佳决策。”

研究人员的评估显示，使用这种方法，可以保证在比通常收集的数据集小得多的情况下做出最佳决策。

阿敏说：“我们挑战关于小数据意味着近似解决方案的误解。这些是具有数学证明的确切的充分性结果。我们已经确定在数据非常少的情况下您可以确保获得最佳解决方案——不是可能，而是确定。”

未来，研究人员希望将他们的框架可以扩展到其他类型的问题以及更复杂的情况。他们还希望研究噪声观测如何影响数据集的最优性。

“我对这项工作的原创性、清晰度和优雅的几何特征感到非常印象深刻。他们的框架为决策中的数据效率提供了全新的优化视角，”可口可乐基金会主席兼教授姚谢（Yao Xie）表示，他并未参与这项工作。

更多信息请见：Omar Bennouna 等人，《数据如何实现最优决策？线性优化的精确特征》，arXiv（2025年）。 DOI: 10.48550/arxiv.2505.21692