学界 | 哈佛研究者推出新型优化算法，指数级提升计算速度

编译：睡不着的iris、涂世文、云舟

一种新出现的算法可以大大缩短电影推荐和出租车路径规划这类问题的计算时间。

这个算法由哈佛大学的研究人员开发，通过减少已有算法的迭代次数来快速解决优化问题。更出人意料的是，哈佛大学高级研究员Yaron Singer指出，这个方法并不以减少最终结果的精确度为代价。

优化问题是在可能的解中选出最佳答案，诸如映射从A点到B点的最快路径。许多专为解决优化问题设计的算法自从20世纪70年代首次被提出后便没有任何改进。

已有的优化算法通常是一个循序渐进的执行过程，迭代次数与所分析的数据量成正比。比如，一个电影推荐算法会依次找到每一部与用户喜欢的电影相似的电影。

然而，已有的优化算法存在“收益递减”的特性：随着算法的执行，每一步产生的相对收益变得越来越小。这意味着涉及海量数据的优化问题，寻找最优解的计算开销会极其昂贵。

在实验中，Singer和共同研究者Eric Balkanski发现他们的算法对包含6000名用户针对4000部电影的100万条评论数据集进行分析时，可以得出与现行算法相似的电影推荐结果，但速度却能提升20倍。

另外，对纽约市出租车公司与Limousine Commission的200万条出租车行车数据集进行分析时，新算法在为出租车挑选最佳位置时，不仅可以覆盖大部分潜在用户，而且比已有算法快6倍。

大部分已有的优化算法是通过单一方向的迭代运行来处理问题，而这一新的算法则采用多个方向并行实现。基于这样的方法，算法舍弃了不理想的优化方向，选取对结果最有价值的方向进行迭代。这种适应算法数据变化的方式，有助于解决收益递减问题。

这种策略可以发挥作用，得益于算法目标的两个不同方面。研究者称之为曲率（curvature）和同质性（homogeneity）。

对于电影推荐问题，具有高曲率的目标与用户看过的电影十分相似——例如，如果你喜欢Die Hard，那么算法推荐的电影很有可能包含这部电影的续集。对于出租车调度问题，具有高曲率的目标是出租车可以在30秒内响应客户的地方。曲率越平缓，算法越高效——例如，当一辆出租车的响应时间为5分钟而非30秒的时候，算法的效率更高。

同样对于电影推荐问题，具有高同质性的目标假设有许多电影可以推荐——例如，你喜欢Die Hard，高同质性的电影诸如Lethal Weapon 的同类型动作片会被算法推荐。对于出租车调度问题，具有高同质性的目标假设基于位置的客户分布相对均衡。同质性越高，算法越高效。

这种新的方法还可以用于解决其他问题，例如识别新药物、从在线健康社区发现药物间的相互作用以及开发医学成像的传感器阵列等等。

Singer说，“事实是我们确实能指数级得加速计算运行时间，这为医疗保健、计算生物学、机器学习和数据挖掘带来了新的契机，过去这些应用程序的计算成本太高，难以考虑太多因素。”

Balkanski和Singer正在探索他们的策略适用于哪些优化问题。他们同时也在计划为GPU编写代码，以在更多领域应用他们的成果。Singer表明，“一般来说，这些算法非常简单，几行代码即可实现。”。

Balkanski和Singer于6月28日在洛杉矶举行的国际计算机协会（ACM）的计算机理论研讨会（STOC）和7月12日在斯德哥尔摩的国际机器学习大会（ICML）上详细介绍了他们的成果。

相关报道：

https://spectrum.ieee.org/tech-talk/computing/software/new-optimization-algorithm-exponentially-speeds-computation

【今日机器学习概念】

Have a Great Definition