信息摘要:
该算法是由哈佛大学的研究人员开发的,目的是通过减少现有算法的迭代次数来快速解决优化问题。更令人惊讶的是,哈佛大学的高级研究员Yaron Singer指出,这种方法并不以牺牲为代价
该算法是由哈佛大学的研究人员开发的,目的是通过减少现有算法的迭代次数来快速解决优化问题。更令人惊讶的是,哈佛大学的高级研究员Yaron Singer指出,这种方法并不以牺牲为代价。降低了更终结果的准确性。
优化问题是在可能的解中选择更优解,如从A点到B点的更快路径的映射,许多专门为解决优化问题而设计的算法自上世纪70年代首次提出以来一直没有得到改进。
现有的优化算法通常是一个逐步执行的过程,迭代次数与分析的数据量成正比。例如,电影推荐算法将发现每个与用户喜欢的电影相似的电影。
然而,现有的优化算法具有收益递减的特点:随着该算法的实现,每一步产生的相对收益越来越小,这就意味着寻找更优解的计算成本非常昂贵。它涉及到海量数据的优化。
在实验中,Singer和同事Eric Balkanski发现他们的算法分析6000名用户的4000部电影的100万次评论数据集,得到类似于当前算法的推荐,但是速度快了20倍。
此外,在分析纽约市出租车公司和Limousine委员会的200万出租车数据集时,新算法不仅可以覆盖大多数潜在用户,而且在选择出租车更佳位置时比现有算法快6倍。
现有的优化算法大都采用单向迭代的方法进行求解,这种新的算法是在多个方向并行实现的,基于这种方法,该算法摒弃不满意的优化方向,选择更有价值的直接优化方向。这是一种适应算法数据变化的方法,有助于解决收益递减问题。
这种策略可以发挥作用,得益于算法目标的两个不同方面。研究人员称之为曲率(曲率)和齐性(齐性)。
对于电影推荐问题,高曲率的目标与用户看到的电影非常相似,例如,如果您喜欢Die Hard,那么该算法推荐的电影可能包含电影的续集。其中,出租车可以在30秒内响应客户。曲率越平滑,算法就越有效——例如,当出租车的响应时间是5分钟而不是30秒时。
类似地,对于电影推荐,有许多电影可以采用高同质目标假设进行推荐,例如,你喜欢《死硬》,算法推荐高同质电影,如具有相同类型动作片的《致命武器》。ems,具有高同质性的目标假设是基于位置的客户分布相对平衡,同质性越高,算法效率越高。
这种新方法还可以用于解决其他问题,例如识别新药、从在线健康社区发现药物相互作用、以及开发用于医学成像的传感器阵列。
Singer说,我们确实拥有指数级更快的计算运行时间,这为医疗保健、计算生物学、机器学习和数据挖掘开辟了新的机会,这些领域过去过于昂贵,无法考虑太多的因素。
Balkanski和Singer正在探索他们的策略适用于哪些优化策略。他们还计划编写代码给GPU,以便将它们的结果应用到更多的领域。Singer表明,一般来说,这些算法非常简单,并且可以通过几行代码来实现。
巴尔干斯基和辛格于6月28日在洛杉矶举行的国际计算机协会(ACM)计算机理论研讨会(STOC)和7月12日在斯德哥尔摩举行的国际机器学习会议(ICML)上介绍了他们的发现。
http://Simult.IEEE.OrgTalk 计算/软件/新的优化算法指数速度计算