报名参加CloudWeGo黑客松,奖金直推双丰收! 了解详情
写点什么

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:436143

评论 1 条评论

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

区块链技术重新定义 物联网的物与物之间的交易

CECBC

发展空间

进公司不会用 Git 拉项目!第二天被开除?

Java架构师迁哥

《彩食鲜 CTO 乔新亮:程序员如何从技术走向管理》(采访提纲)

这就是编程

推荐25种自媒体运营必备工具 (建议收藏)

科技猫

工具 网站 分享 运营 自媒体

交易所合约跟单软件搭建,火币合约跟单平台开发

Coinbase上市,对加密市场将带来哪些影响?

CECBC

货币

中国数字人民币试点有序扩大至“10+1” 拜登政府正加强研究数字人民币计划

CECBC

数字货币

函数计算助力高德地图平稳支撑亿级流量高峰

阿里巴巴中间件

程序员快乐的一天!

BinTools图尔兹

程序员 运维 开发 dba 数据库管理工具

有道写作浏览器扩展实践

有道技术团队

大前端 浏览器 有道云笔记

微服务转型系列2:微服务转型的三大误区,避坑指南

BoCloud博云

微服务

【科创人】贝锐创始人陈宇晔:花生壳诞生自一次挫折,15年坚守有温度不作恶

科创人

一个极简的冲突管理工具

石云升

28天写作 职场经验 管理经验 4月日更 冲突管理

函数计算助力语雀构建稳定且安全的业务架构

阿里巴巴中间件

文档 企业架构和云服务 业务架构

如何用 Electron + WebRTC 开发一个跨平台的视频会议应用

阿里云CloudImagine

阿里云 音视频 WebRTC Electron 视频云

iceberg查询加速原理

聚变

汽车之家基于 Flink 的数据传输平台的设计与实践

Apache Flink

flink

Spark数据倾斜解决方案

大数据技术指南

spark 4月日更

勇夺桂冠!百度智能云获山东电力输电人工智能技术竞赛第一名

百度大脑

百度智能云

浅析“分布式锁”的实现方式丨C++后端开发丨底层原理

Linux服务器开发

redis zookeeper 分布式锁 Linux服务器开发 C++后端开发

金融科技数据链的DNA

博睿数据

金融科技 博睿数据 数据链DNA

图查询语言的历史回顾短文

NebulaGraph

数据库 数据库设计 图数据库

云存储中不可不知的五个安全问题及应对措施

云计算

腾讯大神为什么会对这份“redis深度笔记”如此爱不释手?

Java架构师迁哥

Java该怎么学?阿里大佬呕心沥血之作,Java全线成长宝典,从P5到P8一应俱全

Java架构师迁哥

阿里P8大牛亲自教你!带你快速通过面试,Android岗

欢喜学安卓

android 程序员 面试 移动开发

Substrate 合约书之合约模型

Patract

智能合约 rust polkadot Patract Wasm

Nacos 2.0 性能提升十倍,贡献者 80% 以上来自阿里之外

阿里巴巴云原生

微服务 开发者 云原生 dubbo 中间件

融云 CTO 杨攀:技术人员如何创业?

Yano

阿里P8亲自讲解!带你一步一步深入Handler源码,满满干货指导

欢喜学安卓

android 程序员 面试 移动开发

Java开发9年经验,三轮技术面+HR面试成功砍下阿里巴巴Offer!

Java架构追梦

Java 阿里巴巴 架构 面试

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