写点什么

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

评论 1 条评论

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

产品经理需要掌握哪些技能?一文弄懂PM的方方面面!附知识图谱

彭宏豪95

产品经理 产品设计 PM 在线白板 团队协同

【豆瓣8.4】《RabbitMQ实战指南》PDF

程序员李木子

Atlassian 停服 Bitbucket?三步快速迁移至极狐GitLab

极狐GitLab

最强GTD时间管理工具OmniFocus Pro 3 for Mac最新激活版 附注册机 兼容M1/M2

Rose

苹果软件 OmniFocus 下载 Mac任务管理器 OmniFocus Pro 3 GTD时间管理

应该如何选择轻量级低代码、重量级低代码、轻量级低代码+定制、纯定制软件开发?

天津汇柏科技有限公司

低代码开发 低代码,项目开发 定制软件开发 软件开发定制

【豆瓣9.1】《大数据处理框架Apache Spark设计与实现(全彩)》PDF

程序员李木子

C# 面向对象编程解析:优势、类和对象、类成员详解

小万哥

C# 程序人生 编程语言 软件工程 后端开发

Programming Abstractions in C阅读笔记:p258-282

codists

hazel mac破解版 自动化文件清理工具 含hazel激活码 兼容m1 m2

Rose

苹果软件资源 Hazel 下载 Mac自动清理工具 Hazel Mac破解版

【Linux技术专题】「夯实基本功系列」带你一同学习和实践操作Linux服务器必学的Shell指令(深入Kill指令探索)

码界西柚

Linux Shell 2024年第二十二篇文章 技术指令

HDFS 小文件合并最佳实践

冰心的小屋

NameNode 海量小文件

2024年首期OpenHarmony繁星计划师资培训在东莞圆满举办

新消费日报

秒级响应,显著增效:明日控股携手奇点云,打造大宗贸易的数据中台标杆

Geek_2d6073

Nop入门:极简数据访问层开发

canonical

mybatis 低代码 ORM graphql

Programming Abstractions in C阅读笔记:p254-p257

codists

在线 cURL 参数对比工具,让你的开发工作更加高效

秦少卫

curl 接口工具 调试工具 请求参数对比 参数格式化

Ableton Live如何设置中文?ableton live 11 mac中文破解版 永久可用

Rose

mac音乐制作软件 Ableton Live 11破解版 Ableton Live 11中文版

文心一言 VS 讯飞星火 VS chatgpt (187)-- 算法导论14.1 4题

福大大架构师每日一题

福大大架构师每日一题

上市难不上市更难,谁能佐证中国企服的光明前途?

ToB行业头条

点赞!HashData连续三年获评数据猿“最具投资价值企业奖”

酷克数据HashData

【新手视频】在线快速搭建AI原生应用

AI大咚咚

百度 AI rag AI原生应用 Agent构建

Nop入门:极简服务层开发

canonical

gRPC 低代码 graphql SpringBoot3

听GPT 讲Rust源代码--compiler(30)

fliter

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