今天发表在《Nature》(《自然》)杂志上的论文中,DeepMind提出了AlphaTensor,这是第一个用于发现新的、高效的、可证明正确的矩阵乘法等基本任务算法的人工智能(AI)系统。这揭示了数学中一个长达50年的开放性问题,即寻找两个矩阵相乘的最快方法。
矩阵相乘的重要性 AlphaTensor如何找到更快的矩阵运算方法 AlphaTensor的开源实现和使用使用方法 矩阵相乘的重要性
矩阵相乘是当今深度学习算法的基础运算之一。尽管高中时期可能就已经有了教学,但是它对于当今数字世界有着巨大的影响力。
两个矩阵相乘这一操作被用于处理智能手机上的图像,识别语音命令,为计算机游戏生成图形,运行模拟以预测天气,压缩数据和视频以在互联网上共享,以及其他更多的操作。世界各地的公司花费了大量的时间和金钱来开发计算硬件,以有效地进行矩阵乘法。因此,即使是对矩阵乘法效率的微小改进也会产生广泛的影响。
这篇论文是DeepMind推动科学发展和利用人工智能解开最基本问题的使命中的一块踏脚石。AlphaTensor建立在AlphaZero的基础上,AlphaZero是一个在国际象棋、围棋和象棋等棋类游戏上表现出超人表现的代理,这项工作展示了AlphaZero从玩游戏到首次解决未解决的数学问题的过程。
几个世纪以来,数学家们认为,标准的矩阵乘法算法是人们在效率方面所能达到的最佳状态。但在1969年,德国数学家Volken Strassen(沃尔肯-斯特林)震惊了数学界,他表明确实存在更好的算法。
下图是Volken Strassen的算法示例。
通过研究非常小的矩阵(大小为2x2),他发现了一种巧妙的方法来组合矩阵的条目,从而产生一种更快的算法。尽管经过几十年的研究,这个问题的更大版本仍然没有得到解决—以至于人们不知道如何有效地将两个小到3x3的矩阵相乘。
在我们的论文中,我们探讨了现代人工智能技术如何推进新矩阵乘法算法的自动发现。在人类直觉进步的基础上,AlphaTensor发现了在许多矩阵大小上比现有技术水平更有效的算法。我们的人工智能设计的算法优于人类设计的算法,这是在算法发现领域的一个重大进步。
AlphaTensor如何找到更快的矩阵运算方法
首先,我们将寻找高效的矩阵乘法算法的问题转化为一个单人游戏。在这个游戏中,棋盘是一个三维张量(数字阵列),记录了当前算法离正确的程度。通过一组与算法指令相对应的允许移动,玩家试图修改张量并将其条目清零。当玩家成功做到这一点时,对于任何一对矩阵来说,都会产生一个可证明正确的矩阵乘法算法,而其效率则由将张量清零所需的步骤数来体现。
这个游戏具有难以置信的挑战性—要考虑的可能算法的数量远远大于宇宙中的原子数量,即使是矩阵乘法的小案例。与几十年来一直是人工智能挑战的围棋游戏相比,我们的游戏每一步可能的动作数量要大30个数量级(对于我们考虑的一个设置,超过1033个)。
从本质上讲,要玩好这个游戏,需要在巨大的干草堆中找出最微小的针。为了应对这个明显不同于传统游戏的领域的挑战,我们开发了多个关键组件,包括一个新的神经网络架构,其中包括特定问题的归纳偏见,一个生成有用的合成数据的程序,以及一个利用问题的对称性的配方。
然后,我们利用强化学习训练了一个AlphaTensor代理来玩游戏,开始时没有任何关于现有矩阵乘法算法的知识。通过学习,AlphaTensor随着时间的推移逐渐改进,重新发现了历史上的快速矩阵乘法算法,如Strassen的算法,最终超越了人类的直觉领域,发现的算法比以前已知的更快。
例如,如果学校教授的传统算法是用100次乘法对一个4x5乘以5x5的矩阵进行乘法,而这个数字在人类的聪明才智下被减少到80次,AlphaTensor已经找到了只用76次乘法就能完成相同操作的算法。
除了这个例子,AlphaTensor的算法自50年前发现以来,首次在有限域中改进了Strassen的两级算法。这些小矩阵的乘法算法可以作为基元用于任意大小的大得多的矩阵的乘法。
此外,AlphaTensor还发现了一组具有最先进复杂度的多样化算法—每种大小的矩阵乘法算法多达数千种,表明矩阵乘法算法的空间比以前想象的要丰富。
在这个丰富的空间中的算法具有不同的数学和实践属性。利用这种多样性,我们对AlphaTensor进行了调整,专门寻找在特定硬件上速度快的算法,如Nvidia V100 GPU,以及谷歌TPU v2。 这些算法在相同硬件上比常用的算法快10-20%,这展示了AlphaTensor在优化任意目标方面的灵活性。
AlphaTensor的开源实现和使用
目前,谷歌已经在GitHub上贡献了AlphaTensor,它包含4个方向:
algorithms包含AlphaTensor发现的算法,表示为矩阵乘法张量的因式分解,以及一个显示如何加载这些算法的Colab。 benchmarking包含一个脚本,可以用来测量矩阵乘法算法在NVIDIA V100 GPU上的实际速度。 nonequivalence包含了AlphaTensor为同一个矩阵乘法问题(4x4矩阵相乘)所发现的14236种不对等的算法,以及一个验证其不对等性的Colab。 recombination包含了我们用来分解较大的矩阵乘法张量的代码,通过重新组合较小的矩阵乘法张量的因子。
具体的论文详情和代码详情,请参考:DeepMind最新研究研究AlphaTensor发布——可以快速求解矩阵相乘的AI算法 | 数据学习者官方网站(Datalearner)
访谈
更多做行业赋能者 HID迎接数字化浪潮新机遇 破解新挑战
今年3月份,全球可信身份解决方案提供商HID发布了最新的《安防行业现状报告》(以下简称“报告”),该报告…
数字化浪潮下,安防厂商如何满足行业客户的定制化需求?
回顾近两年,受疫情因素影响,包括安防在内的诸多行业领域都遭受了来自市场 “不确定性”因素的冲击,市场…
博思高邓绍昌:乘产品创新及客户服务之舟,在市场变革中逆风飞扬
11月24日,由慧聪物联网、慧聪安防网、慧聪电子网主办的2022(第十九届)中国物联网产业大会暨品牌盛会,在深…