QCon北京「鸿蒙专场」火热来袭!即刻报名,与创新同行~ 了解详情
写点什么

50 年悬而未决的矩阵乘法难题,被 DeepMind 的新式算法攻克了

  • 2022-10-10
    北京
  • 本文字数:2099 字

    阅读完需:约 7 分钟

50年悬而未决的矩阵乘法难题,被DeepMind的新式算法攻克了

用算法攻克算法,AI 带来了更多可能性。


瑞典数学家 Lars Garding 曾在其名著《Encounter with Mathematics》中说:“如果不熟悉线性代数的概念,要去学习自然科学,现在看来就和文盲差不多。”作为线性代数中的基本概念之一,矩阵的重要性不言而喻,它可以用来表示线性映射,而矩阵乘法可以用来表示线性映射的复合。


作为一种高效的算法,矩阵乘法在过去几十年间应用性极强,不仅在数学中有大量应用,在应用数学、物理学、工程学等领域也有广泛使用。可以说,矩阵乘法在当代数字世界中产生了巨大的影响,在现代计算中无处不在。


近日,DeepMind 推出的 AI 系统 AlphaTensor 发现了一种新型的矩阵乘法,能够将计算速度提升 20%,这创造了矩阵乘法 50 年最新纪录。该研究成果于 10 月 5 日发表在 Nature 杂志上,并登上了 Nature 封面。这项研究展现了使用机器学习解决数学难题的潜力,在未来,AI 或许还会带来更多的惊喜。


详细算法地址:


https://www.nature.com/articles/s41586-022-05172-4

DeepMind 推出 AlphaTensor,可创造新型矩阵乘法


AlphaTensor 是 DeepMind 研发出的 AI 系统,用于为矩阵乘法等基本任务发现新颖、高效且​​可证明正确的算法。它解决了数学界 50 年间悬而未决的难题,即找到将两个矩阵相乘的最快方法。


两个 3x3 的矩阵相乘


几个世纪以来,数学家认为标准矩阵乘法算法是效率最高的算法。但在 1969 年,德国数学家 Volker Strassen 找到了一种新的 2 x 2 矩阵相乘方法,能够将原本的 8 次乘法减少为 7 次。Volker Strassen 的这一发现震惊了数学界,在此之后,更多研究人员开始探索类似的运算量缩减技巧。


与标准算法相比,Strassen 算法使用更少的标量乘法(7 而不是 8)来乘以 2x2 矩阵,大幅提高计算效率


值得一提的是,AlphaTensor 是在 AlphaZero 基础上被开发出来的,后者是应用于象棋、围棋等棋盘游戏中的人工智能体。


AlphaTensor 的训练过程就是将排列在网格或矩阵中的数字相乘,这些数字可能代表图像中的像素集、天气模型中的空气状况,或者人工神经网络的内部神经元。要将两个矩阵相乘,科学家需要先将各个数字相乘,再用特定方式相加以产生新矩阵。


通过强化学习,AI 智能体能够通过与环境交互学习多步骤目标,例如如何赢下棋盘游戏。如果表现出色,智能体就会得到加强——其内部参数会接受更新,增加后续的游戏成功率。


AlphaTensor 还结合了一种名为树搜索的游戏方法。在这种方法中,AI 会在规划下一步行动的同时,探索各种分支的可能性结果。而在树搜索期间进行路径优先度考量时,它会要求神经网络对每一步的潜在最优行动做出预测。在智能体学习期间,它会使用游戏结果作为反馈以提升神经网络性能,在不断改进树搜索的同时总结出更多可供学习的经验。


AlphaTensor 玩的单人游戏,目标是找到正确的矩阵乘法算法。游戏状态是一个由数字组成的立方数组(灰色表示 0,蓝色表示 1,绿色表示 -1),表示剩余的工作。


每轮游戏被转化为一场单人拼图,要求智能体正确填写 3D 张量(数字网格)。AlphaTensor 的目标就是用最少的步骤将所有数字归零,而可用的行动已经被预先设定明确。每一步代表一次计算,并在矩阵反转时结合前两个矩阵中的条目以创建出输出矩阵内的一个新条目。这场游戏极为艰难,智能体的每一步行动都可能要从数万亿种行动中做出选择。


论文合著者、DeepMind 计算机科学家 Hussein Fawzi 在发布会上坦言,“算法发现空间的确定非常复杂,找寻在该空间中导航的方法就更难了。”


为了能在训练期间为 AlphaTensor 助力,研究人员还向它展示了一些成功游戏的例子,免得它从零开始胡乱摸索。而且由于行动的顺序并不重要,所以每当它找到一系列成功行动时,研究人员还会将这些行动打乱排序以作为学习示例。

用算法攻克算法,AlphaTensor 实现高效计算


研究人员在高达 5 x 5 的输入矩阵上测试了新系统。在大多数情况下,AlphaTensor 发现的都是 Strassen 和其他数学家之前已经找到的捷径。但令人兴奋的是,它也做出了前人未曾触及的突破。例如,在将 4 x 5 矩阵与 5 x 5 矩阵相乘时,以往的最佳算法需要 80 次单独乘法计算,而 AlphaTensor 发现了只需要 76 次相乘的新算法。


DeepMind 计算机科学家 Pushmeet Kohli 在新闻发布会上表示,“在这场游戏中,它拥有惊人的直觉。AlphaTensor 并没有嵌入任何来自人类的矩阵乘法解题思路。从某种意义上讲,智能体需要从头开始建立自己的知识体系。”


研究人员还创造了一种先将问题拆分成多个较小问题的元算法,借此解决更大的矩阵乘法问题。当 11 x 12 与 12 x 12 矩阵相乘时,这种方法成功将所需的乘法计算次数从 1022 次减少到了 990 次。


AlphaTensor 还能针对特定硬件实现矩阵乘法优化。该团队在两款不同的处理器上进行了智能体训练,不仅减少了计算步骤,也缩短了运行时长。在大多数情况下,与以往的算法相比,该 AI 将矩阵乘法的速度提高了几个百分点。研究人员还发现,有时候一款处理器上最快的算法,在另一处理器上却无法保持优势。


研究人员表示,同样的通用方法也适用于其他类型的数学运算,例如将复杂的波或其他数学对象,分解成更简单的对象。


麻省理工学院计算机科学家 Virginia Vassilevska Williams 表示,“如果能在实践中应用这一成果,将非常令人兴奋。性能的提升将给诸多应用场景带来改善。”维克森林大学的计算机科学家 Gray Ballard 则从中看到了未来人机协作的潜力,“除了用这种方式推动数学探索的边界之外,我还很高兴地看到理论研究人员开始分析这些新发现的算法,其中也许蕴藏着指向其他算法突破的线索。”

2022-10-10 14:436120

评论 1 条评论

发布
用户头像
机器学习的正确运用方式。机器学习能这么用,学到了。模型确实等同于直觉。
2022-10-17 23:07 · 北京
回复
没有更多了
发现更多内容

搞懂 ZooKeeper 集群的数据同步

HelloGitHub

Java zookeeper ZooKeeper原理

​Autonomous Dream Works的独创力杰作EGGNetwork EFTalk

币圈那点事

主数据建设的挑战与发展

EAWorld

Golang号称最快的Json解析器速度可达5623ns/op

happlyfox

学习 3月日更 Go 语言

镜像仓库学习笔记

lenka

3月日更

通俗讲解分布式锁,看完不懂算我输

Java小咖秀

Java 分布式 多线程 并发

Gas费用持续攀升!NA公链NAC公链如何破解高额Gas费用的困局?

区块链第一资讯

智慧公安信息化管理系统,重点人员管控系统的搭建

13828808769

智慧交通

如何正确使用Python临时文件

华为云开发者联盟

Python 安全 临时文件 tempfile 库函数

在全面拥抱人工智能前,这 6 步您的公司做到了吗?| 云途专栏

亚马逊云科技 (Amazon Web Services)

亚马逊云科技和德甲为 2021 赛季新推出三项赛况统计数据,强化实时比赛分析

亚马逊云科技 (Amazon Web Services)

区块链六大应用场景,推动政府信息化发展

13828808769

区块链+ #区块链#

基于深度学习的两种信源信道联合编码

华为云开发者联盟

深度学习 通信 编码 信源编码 信道编码

QCon全球软件开发大会:推动创新,实现技术落地

博文视点Broadview

推荐 2 款必备的 Django 开发神器

星安果

Python django Web 后端

分布式锁的实现方案

360技术

初识Golang之声明函数

Kylin

3月日更 21天挑战 Go 语言

Python基础之:Python中的模块

程序那些事

Python Python3 程序那些事

Rust从0到1-基础概念-数据类型

rust 数据类型

网络连接之协议栈

Kylin

协议栈 3月日更 21天挑战 网络连接

区块链BaaS应用平台搭建,助力企业运用区块链解决业务问题

13828808769

区块链 区块链+ 区块链发展 #区块链#

Worktile 前端工程化之路

PingCode研发中心

大前端

看东鹏饮料如何从150亿条数据中洞察先机 | 精选案例

亚马逊云科技 (Amazon Web Services)

华为云PB级数据库GaussDB(for Redis)揭秘第六期:Feed流场景中的应用

华为云开发者联盟

数据库 redis 华为云 GaussDB Feed流

NoCode 实战 | 零代码应用开发,轻松搞定任务跟踪管理难题(上)

亚马逊云科技 (Amazon Web Services)

用 Redis 实现消息队列是一个好主意么?

escray

redis 学习 极客时间 3月日更 Redis 核心技术与实战

设计与思考,关于资源和生命周期

程序员架构进阶

设计实践 生命周期 28天写作 3月日更 池化技术

Datadog 能成为最大的云监控厂商吗

睿象云

运维 运维平台 Datadog 云监控

异步机制和CPU架构对 Redis 性能的影响

escray

redis 学习 极客时间 3月日更 Redis 核心技术与实战

【LeetCode】删除排序链表中的重复元素 IIJava题解

Albert

算法 LeetCode 3月日更

一段java代码执行旅程

华为云开发者联盟

JVM class 指令 java代码 java栈

50年悬而未决的矩阵乘法难题,被DeepMind的新式算法攻克了_文化 & 方法_核子可乐_InfoQ精选文章