@ 2018.07.17 , 12:00

新算法将电影偏好推荐的效率提升了20倍

新算法将电影偏好推荐的效率提升了20倍
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 编辑发布。

赞一个 (7)