通过大幅减少达到解决方案所需的并行步骤数量

如果今天使用的一大类算法 - 从帮助我们避免识别新药物分子的算法的流量的算法 - 以指数方式加速工作会怎样?

哈佛大学约翰·保尔森工程与应用科学学院(SEAS)的计算机科学家开发了一种全新的算法，通过大幅减少达到解决方案所需的并行步骤数量，可以指数地加速计算。

研究人员将在即将召开的两个会议上展示他们的新方法：6月25日至29日的ACM计算理论研讨会(STOC)和7月10日至15日的国际机器学习会议(ICML)。

许多所谓的优化问题，从所有可能的解决方案中找到最佳解决方案的问题，例如将最快路线从A点映射到B点，依赖于自20世纪70年代首次描述以来没有改变的顺序算法。这些算法通过遵循连续的逐步过程来解决问题。步数与数据大小成正比。但这导致了计算瓶颈，导致一系列问题和研究领域的计算成本太高，无法探索。

“这些优化问题的回报性能正在下降，”SEAS计算机科学助理教授，该研究的高级作者Yaron Singer说。“随着算法的进步，每一步的相对增益变得越来越小。”

辛格和他的同事问道：如果算法不需要花费数百或数千个小步骤来获得解决方案，那么算法可能只需要几个跳跃?

“这种算法和通用方法使我们能够大大加快计算，解决许多不同领域中的大量问题，包括计算机视觉，信息检索，网络分析，计算生物学，拍卖设计等等，”辛格说。“我们现在可以在几秒钟内完成计算，这些计算之前需要几周或几个月。”

“这项新的算法工作，以及相应的分析，为新的大规模并行化战略打开了大门，这些战略的速度比以往任何时候都要大得多，”大学电气工程系教授Jeff Bilmes说。华盛顿没有参与这项研究。“例如，这些能力将使现实世界的总结过程能够以前所未有的规模发展。”

传统上，优化问题的算法一步一步地缩小搜索空间以获得最佳解决方案。相比之下，这种新算法并行地采样各种方向。基于该样本，该算法从其搜索空间中丢弃低值方向，并选择最有价值的方向来向解决方案前进。

以这个玩具为例：

你有兴趣看一部类似复仇者联盟的电影。传统的推荐算法会在每个步骤中依次添加一个电影，其具有与复仇者相似的属性。相比之下，新算法随机抽取一组电影，丢弃那些与“复仇者”太不相似的电影。剩下的是一批不同的电影(毕竟，你不想要十部蝙蝠侠电影)，但与“复仇者联盟”相似。该算法继续在每个步骤中添加批次，直到它有足够的电影推荐。

这种自适应采样过程是算法在每个步骤做出正确决策的能力的关键。

“这类问题的传统算法贪婪地将数据添加到解决方案中，同时考虑每一步的整个数据集，”SEAS的研究生，该研究的共同作者Eric Balkanski说。“我们算法的优势在于，除了添加数据外，它还可以选择性地修剪将来在步骤中忽略的数据。”

在实验中，Singer和Balkanski证明他们的算法可以筛选出一个数据集，该数据集包含来自4,000部电影的6,000名用户的100万个评级，并为个人用户推荐个性化和多样化的电影集合，比状态的20倍快。 -艺术。

研究人员还测试了出租车调度问题的算法，其中有一定数量的出租车，其目标是选择最佳位置以覆盖最大数量的潜在客户。使用来自纽约市出租车和豪华轿车委员会的200万次出租车行程的数据集，自适应采样算法发现解决方案的速度提高了6倍。

“这种差距在大规模应用中会更加显着，例如聚类生物数据，赞助搜索拍卖或社交媒体分析，”Balkanski说。

当然，该算法的潜力远远超出了电影推荐和出租车调度优化。它可以应用于：

设计用于治疗阿尔茨海默病，多发性硬化症，肥胖症，糖尿病，丙型肝炎，艾滋病毒等的药物的临床试验

进化生物学从不同物种的大型基因数据集中找到不同基因集合的良好代表性子集

设计用于医学成像的传感器阵列

从在线健康论坛确定药物 - 药物相互作用检测

这种主动学习过程是算法在每一步做出正确决策的能力的关键，并解决了收益递减的问题。

“这项研究是大规模离散优化的真正突破，”苏黎世联邦理工学院计算机科学教授Andreas Krause说，他没有参与这项研究。“机器学习中最大的挑战之一是从大量图像或视频集合中找到优秀，有代表性的数据子集，以培训机器学习模型。这项研究可以快速识别这些子集，并对这些大规模数据汇总问题产生实质性影响“。

研究中开发的Singer-Balkanski模型和算法的变体也可用于更快地评估机器学习模型的准确性，谷歌研究的首席科学家Vahab Mirrokni说，他没有参与这项研究。

“在某些情况下，我们对模型精度函数进行了黑盒访问，计算起来非常耗时，”Mirrokni说。“同时，许多功能设置的计算模型精度可以并行完成。这种自适应优化框架是这些重要设置的一个很好的模型，这个框架中开发的算法技术的见解会对这个重要领域产生深远的影响。机器学习研究。“

Singer和Balkanski正在继续与从业者合作实施该算法。