《六个领域的算法进展》发布

||论文

算法的进展今天我们发布了访问研究员的一份新的技术报告亚博体育官网卡佳恩典被称为“六领域的算法进展。该报告总结了六个领域的算法进展数据,即每固定数量的计算硬件的更好性能:

  • 坐在解决者,
  • 象棋和围棋程序,
  • 物理模拟,
  • 保理,
  • 混合整数规划
  • 一些形式的机器学习。

我们收集这些数据的目的是为了阐明这个问题智能爆炸微观经济学,尽管我们怀疑该报告将在软件业和计算机科学学术界引起广泛兴趣。

该报告的一项发现曾被罗宾·汉森(Robin Hanson)讨论过在这里.(罗宾看到了关于智力爆炸微观经济学的早期草稿邮件列表.)

通常讨论报告的首选页面是在这里

简介:

在最近布尔可满足性(SAT)竞赛中,SAT解题者的成绩每年增加5-15%,这取决于问题的类型。然而,这些进步是由在特定问题上的巨大差异推动的。对SAT成绩的回顾性调查(对事后选择的问题)显示出明显更快的进步。

国际象棋程序在过去的四十年里,每年提高了大约50个Elo点。对于硬件改进的重要性的估计是非常嘈杂的,但这与硬件改进占了大约一半的进展是一致的。自20世纪60年代以来,除过去5年外,进展一直比较平稳。走程序在过去的三十年里,每年都有大约一英石的改善。硬件翻倍会产生递减的Elo增益,其规模与占进度一半左右的比例一致。

改进的方式多种多样物理模拟(在事实之后选择显示由于软件的性能增加)似乎大约一半是由于硬件的进步。

最大的数分解到目前为止,在过去20年里,它以每年约5.5位数的速度增长;在此期间,计算能力增长了1万倍,目前尚不清楚这种增长有多少是由于硬件的进步。

一些混合整数规划(MIP)算法在现代MIP实例和现代硬件上运行,其速度每年大约翻一番。MIP是一个重要的优化问题,但由于性能的提高而引起了人们的关注。其他优化问题的改进更不一致(也更难确定)。

各种形式的机器学习近几十年来,在百分比准确性方面的进展急剧下降。一些视觉任务最近取得了更快的进展。