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

大数据文摘出品

编译:睡不着的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

原文发布于微信公众号 - 大数据文摘(BigDataDigest)

原文发表时间:2018-07-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

独家|专访深度好奇创始人吕正东:通向理解之路

机器之心原创 作者:虞喵喵 「理解应该是对应于某一个特定场景下的语用」。 在斯坦福大学计算机科学与语言学教授 Christopher Manning 2015 ...

34840
来自专栏机器之心

深度 | OpenAI提出强化学习新方法:让智能体学习合作、竞争与交流

选自OpenAI 机器之心编译 作者: Ryan Lowe等 参与:吴攀、Smith 让智能体(agent)学会合作一直以来都是人工智能领域内的一项重要研究课...

37460
来自专栏机器之心

讨论 | Reddit热门话题:你是否也对NLP的现状感到失望?

36960
来自专栏生信宝典

Cell:荧光标记out了,AI不用“侵入”也能识别细胞死活和类型

17840
来自专栏机器之心

吴恩达Deeplearning.ai课程学习全体验:深度学习必备课程(已获证书)

选自Medium 作者:Arvind N 机器之心编译 参与:路雪、李泽南 8 月 8 日,吴恩达正式发布了 Deepleanring.ai——基于 Cours...

476110
来自专栏华章科技

炮灰模型:女生如何选择追求者的数学模型?

上周我的一个朋友第N 次向女生表白遭到拒绝,作为好朋友的我除了同情之外觉得应该做点什么。之前一次聊天受到 菠菜 的启发,加上出于对数学的兴趣,我对女生“选择与拒...

9330
来自专栏大数据挖掘DT机器学习

大数据工程师:如何改进豆瓣电影Top250的算法思路

作者:飞林沙 算法工程师 影迷们经常关注的电影排行榜里,一部由100人评出9.0分的电影,和一部由10000人评出8.0分的电影,谁应该排在前面呢? 这是...

51850
来自专栏大数据文摘

数据科学中的“数据智慧”

186100
来自专栏AI科技评论

ACL2018 明日墨尔本召开:总体论文接收率 24.7%,两大特邀讲者名单公布

雷锋网 AI 科技评论按:ACL2018 将于 7 月 15 日-7 月 20 日在墨尔本召开,这也是 ACL 第二次登陆澳洲。从 2006 年 ACL 首次在...

7820
来自专栏人工智能头条

如何用3个月零基础入门机器学习?

27950

扫码关注云+社区

领取腾讯云代金券