credit:锐景创意

新算法大大缩短了电影偏好推荐或出租车最优化调度的时间。

高级研究员，哈佛大学的Yaron Singer说，他们减少了以往算法所需的步骤，以更快的速度完成优化分析。令人惊讶的是，该方法“不会牺牲结果的质量”。

优化问题是从所有可能的解决方案中找到效率最高的一个，例如找出最快路线从A点前往B点。许多优化问题的算法自20世纪70年代被发明以来就没有变动过。

先前的优化算法通常采取逐步调整的方式，运算步骤与所分析的数据量成正比。例如，你喜欢文艺片，那么电影推荐算法需要依次查看获得你较高评价的电影，再为这些电影中的每一部寻找相似度高的同类影片，最后依据某种机制——大数据信息——将它们进行优先度排序。

然而，这种算法具有收益递减的特性：随着程序运行，每个步骤的相对增益变得越来越小。这意味着对于涉及大量数据的优化问题，找到最佳解决方案可能会付出极其昂贵的运算成本。

在实验中，Singer和合作者Eric Balkanski发现他们的算法可以对数据集进行分析，其中包含来自6000名用户的4000部电影的100万个评分，并得到了与目前最优算法类似的推荐结果，同时效率提高了20倍。此外，使用来自纽约市出租车和豪华轿车委员会的200万次出租车呼叫相应的数据集，新算法可以为出租车选择最佳等待位置，以覆盖最大数量的潜在客户，比以前的算法快六倍。

先前的优化算法通过在单一方向上逐步调整来解决问题，新算法可以并行地从多个数据维度采样来完成工作。它会过滤掉不太理想的方向，并选择最有价值的方向来推进对结果运算。对数据自适应的演化算法有助于解决收益递减的问题。

自适应策略针对算法目标的两个不同方面。研究人员称之为曲率和同质性。

在为你推荐电影的时候，具有高曲率的对象是与你喜欢看的电影非常相似的其他影片——每个人都经过这样的事情吧，如果您喜欢Die Hard，评分页面的底部就自动地展现其续集的超链接。对于出租车调度问题，高曲率的目标是特定的停车地点，那里可以在30秒内响应新的叫车信息。曲率更温和——例如，出租车响应时间为五分钟而不是30秒——的算法的运算时间更加宽绰。

还是电影推荐问题，同质性描述的对象是同类型的影片——果你依旧喜欢《虎胆龙威》，根据同质性假设，你也会喜欢《致命武器》。对出租车调度公司，同质性假设是客户在不同地点的分布相对均匀。同质性越高，算法的速度也越快。

新算法也可以解决其他问题，包括识别新药，从公共卫生论坛获取药物相互作用的影响后果，以及设计用于医学成像的传感器阵列。

“事实上，我们可以获得指数级的效率提升，这为医疗保健、计算生物学、机器学习和数据挖掘等领域提供了崭新的应用前景。它们以前消耗的运算成本实在太高。”Singer说。

Balkanski和Singer正在进一步发掘可以应用其策略的优化问题。他们还计划为GPU编写代码，以便其他人可以重现他们的工作成果。“一般来说，这些算法非常简单，只需要几行代码就能实现。”Singer说。

6月28日洛杉矶计算机协会计算机理论研讨会(STOC)上，他们做了详细的报告，介绍了自己的成果；7月12日在斯德哥尔摩的国际机器学习大会(ICML)上对外展示了他们的算法。

本文译自 spectrum，由 majer 编辑发布。

PREV : 学中文的欧洲宇航员们
NEXT : 澳洲护林人抓到了体形巨大的咸水鳄鱼