DeepMind的人工智能 AlphaTensor 找到了更快的矩阵乘法算法

沉寂了50年之后，人类终于找到了执行 矩阵乘法 更快的算法。

说是“人类”找到的有点不大准确。实际上，执行实际算法探索和开拓任务的是DeepMind公司新创建的人工智能 AlphaTensor——著名的AlphaZero的姊妹系统。AI提出的算法可将某类矩阵的相乘速度提升20%。

矩阵乘法，懂得都懂，是几乎所有软件中的基本计算任务。名为矩阵的数学对象，在图形生成、人工智能(神经网络)、通信、工业设计、线性规划和控制论等应用里，占据核心的位置(更别提整个数值计算学科了)。所以，相关算法的效率，即便微小改进也可能带来巨大的性能提升。

几个世纪以来，人们认为最有效的矩阵乘法算法的用时与矩阵的元素数量成正比，这意味着对于越来越大的矩阵，用时越来越长。

但数学家 Volker Strassen在 1969 年证明，2个2阶矩阵相乘(每个矩阵有4个元素)，不一定需要执行8次乘法，可通过巧妙的技术，把乘法运算减少到 7 次。这被称为Strassen算法，代价是需要一些额外的加法运算——但这是可以接受的，因为计算机执行加法比乘法花费的时间要少得多。

50 多年来，Strassen算法一直是针对大多数矩阵的最有效的算法。但DeepMind的AI现在发现了一种更快的技术，可在当前硬件上完美运行。

AlphaTensor 在任务开始时对解决方案一无所知，我们仅仅向它提出一个问题，即创建一个算法，以最少的步骤完成任务。

AI经过探索，自行发现了一种算法，只需执行47次乘法运算，就可以算出2个4阶的乘积，这优于Strassen的49次乘法运算。它还开发了用于其他规模的矩阵的改进技术。

AlphaTensor 为每种大小的矩阵发现了数千个算法，其中仅 4×4 矩阵就有 14000 个。但只有一小部分人比人类数学家的更好。该研究建立在 DeepMind 的游戏自学习AI框架 AlphaZero 的基础上，且已经进行了两年。

Deepmind 的 Hussein Fawzi 表示，结果在数学上是合理的，但对人类来说远非直观。 “本质上，我们真的不知道系统为什么会发现这个， 为什么它是当前做矩阵乘法的最佳方案？目前还不清楚。”

“不知何故，神经网络对什么看起来好什么看起来不好有了直觉。老实说，我无法确切地告诉你它是如何工作的。我认为关于深度学习究竟是如何做到这些事情的，还没搞清。”Fawzi 说。

DeepMind 发现，这些算法可以将某些硬件的计算速度提高 10% 到 20%，例如 Nvidia V100 图形处理单元 (GPU) 和谷歌张量处理单元 (TPU) v2，但不能保证这些效率收益随处可见。

英国苏塞克斯大学的James Knight指出，在超级计算机和强大硬件上运行的一系列软件，如人工智能系统和气象模拟，实际上是大规模矩阵乘法。

“如果用于这些领域，那它就能带来效率的提升。如果 Nvidia 在他们的 CUDA 库(一种允许 GPU 协同工作的工具)中实现这一点，我会说，它将减少大多数深度学习任务的负载。”

伦敦大学伯贝克分校的 Oded Lachish 表示，新算法可以提高各种软件的效率，因为矩阵乘法是一个非常普遍的问题——可能会出现更多算法。

但AI的进步，并不一定意味着人类程序员的失业。 “程序员应该担心吗？在遥远的未来，或许。实际上，自动优化程序已在微芯片设计行业推广了几十年，这只是武器库中的另一个重要工具。”Lachish 说。

期刊： Nature, DOI: 10.1038/s41586-022-05172-4

https://www.newscientist.com/article/2340343-deepmind-ai-finds-new-way-to-multiply-numbers-and-speed-up-computers/