新算法将计算时间缩短了几个数量级

• 一种新算法通过大幅减少解决问题所需的迭代次数，以指数方式加快计算速度。
• 它在大规模数据集（例如社交媒体分析和聚类遗传数据）上的表现远远优于传统（顺序）算法。 

数以千计的优化问题（从所有可行的解决方案中找到最佳解决方案的问题），例如将资金分配给股票以最大限度地降低回报风险，或将员工分配到可用的办公室以最大化工作流程和员工统计人员，都严重依赖顺序算法。

这些算法的基本工作模式自 20 世纪 70 年代初首次建立以来一直没有改变（增强）。他们以“n”步顺序解决任何特定问题。

步骤的数量取决于问题的大小（为算法提供某些值作为输入）。这种方法通常会导致计算瓶颈。随着算法的进行，每次迭代的相对增益变得越来越小。

如果一个算法可以通过几次跳跃而不是采取数千个小步骤来解决问题怎么办？如果我们能够使大量当今广泛使用的算法的运行速度呈指数级增长，会怎样？我们正在谈论帮助我们发现新药并避免流量的算法。

为了实现这一点，哈佛大学的研究人员提出了一种新型算法，他们称之为“突破”，该算法通过大幅减少解决问题所需的迭代次数来以指数方式加快计算速度。

它加快了跨多个不同领域的各种问题的计算速度，例如信息提取、拍卖设计、机器视觉、计算生物学、网络分析等。

据开发人员称，它能够在几秒钟内完成以前需要数天或数周才能完成的大型计算。这可以为新的大规模并行化方法打开大门，从而能够以超乎寻常的规模构建实用的汇总流程。

它是如何工作的？

顺序算法的工作原理是一次一步地缩小可行解决方案的数量。而新算法对不同方向进行并行采样，然后消除相关性较低的方向，并选择最有利（高值）的方向来达成解决方案。它有选择地丢弃在未来迭代中将被忽略的值。

突破性算法采用自适应采样 |由研究人员提供

更具体地说，该算法需要 O (log n) 个连续步骤并达到任意接近 1/3 的近似值。当启用并行化时，该算法达到常数因子近似的速度比任何现有的子模最大化方法都要快。

参考：Harvard SEAS | 哈佛出版物

例如，如果任务是推荐类似于《星球大战》的电影，传统算法会在每一步添加一部与《星球大战》具有相似属性（动作、冒险、奇幻）的电影。

另一方面，新开发的算法会随机采样一组电影，删除那些与《星球大战》根本不匹配的电影。这提供了类似于星球大战的多样化电影集合（显然，您不希望在推荐中包含 10 部超人电影）。

该算法将在每一步中继续添加各种电影，直到有足够的项目可供推荐。在每一步做出有价值决策的关键在于自适应采样过程。

顺序（黑色）和突破（红色）算法解决问题所采取的步骤数

测试与应用

研究人员在一个大型数据集上测试了他们的自适应采样算法，该数据集包含 6,000 个用户对 4,000 部电影的 100 万个评分。它成功地为个人推荐个性化、多样化的电影，速度比传统算法快 20 倍。

他们还将这种算法应用于出租车调度问题——选择最佳位置，用有限的出租车为最大数量的客户提供服务。对于 200 万次出租车出行，该算法的运行速度比最先进的算法快 6 倍。

它可以在大规模数据集上产生更好的结果，例如社交媒体分析或聚类遗传数据。  除此之外，该算法还可用于开发多种疾病的临床试验、用于医学成像的传感器阵列以及检测药物之间的相互作用。

阅读：搜索新的自动驾驶汽车算法可以积极改变车道

如今，从数百万张图像/视频中找到有效的数据子集来训练深度学习网络已成为一项具有挑战性的任务。该研究有助于快速提取有价值的子集，并对大规模数据汇总问题产生重大影响。