哈佛大学开发新的优化算法，加快复杂问题的最佳解决方案的计算速度

AiTechYun

编辑：chux

哈佛大学研究人员开发的新算法通过减少所需的步骤数，以比以前的算法更快的速度解决优化问题。新算法可以大大缩短计算机推荐电影或计算出租车路线的时间。

哈佛大学的研究高级作者Yaron Singer表示，令人惊讶的是，这种方法“不会牺牲最终解决方案的质量”。

优化问题寻求从所有可能的解决方案中找到最佳答案，例如将最快路线从A点映射到B点。许多用于解决优化问题的算法自20世纪70年代首次描述以来没有改变。

先前的优化算法通常在逐步过程中工作，步骤的数量与所分析的数据量成比例。例如，电影推荐算法可以顺序地查看与每个人喜欢的电影相类似的电影。

然而，先前的优化算法的回报属性具有递减性：随着它们的进展，每个步骤的相对收益变得越来越小。这意味着对于涉及大量数据的优化问题，找到最佳解决方案可能会在计算上极其昂贵。

在实验中，Singer和研究的共同作者Eric Balkanski发现他们的算法可以分析一个数据集，其中包含来自6,000名用户的4,000部电影的100万个评级，并提供与最先进算法类似的电影推荐，同时工作速度提高了20倍。此外，使用来自纽约市出租车和豪华轿车委员会的200万次出租车旅行的数据集，新算法可以为出租车选择最佳位置，以覆盖最大数量的潜在客户，比以前的算法快6倍。

尽管先前的优化算法通过在单个方向上逐步进行来解决问题，但是新算法通过对各种方向进行并行采样来工作。基于该样本，它会丢弃不太理想的方向，而是选择最有价值的方向来推进解决方案。这种自适应地演化算法工作的数据的行为有助于解决收益递减的问题。

该策略适用于算法目标的两个不同方面。研究人员将这些方面称为曲率和同质性。

对于电影推荐问题，具有高曲率的目标是与人们观看的非常相似的电影，例如，如果你喜欢Die Hard，建议可能包括其续集。由于出租车调度问题，高曲率的目标是出租车可以在30秒内响应客户的地方。曲率越平缓，算法运行得越快，例如，出租车响应时间为五分钟而不是30秒。

这种新方法可以解决其他问题，包括识别新药，从在线健康论坛发现药物相互作用以及开发用于医学成像的传感器阵列。

“事实上，我们可以在运行时获得指数级的加速，这为医疗保健，计算生物学，机器学习和数据挖掘等应用提供了机会，这些应用程序以前的成本太高，”Singer说。

Balkanski和Singer正在探索可以应用其策略的优化问题。他们还计划为GPU编写代码，以便其他人可以实现他们的工作。Singer说，“一般来说，这些算法非常简单，并且可以在几行代码中实现。”

科学家于6月28日在洛杉矶举行的计算机协会计算机理论研讨会（STOC）上详细介绍了他们的发现。他们还将于7月12日在斯德哥尔摩的国际机器学习大会（ICML）上展示他们的工作。

论文1：scholar.harvard.edu/files/ericbalkanski/files/the-adaptive-complexity-of-maximizing-a-submodular-function.pdf

论文2：scholar.harvard.edu/files/ericbalkanski/files/approximation-guarantees-for-adaptive-sampling.pdf