写点什么

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

评论 1 条评论

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

区块链数字钱包系统开发方案,区块链钱包APP源码

13530558032

11月阿里Spring全家桶+MQ微服务架构笔记:源码+实战

小Q

Java 学习 程序员 面试 微服务

接口测试学习之json

测试人生路

json 接口测试

快进收藏吃灰!字节跳动大佬用最通俗方法讲明白了红黑树算法

小Q

Java 学习 架构 面试 算法

区块链社交即时通许系统开发,区块链社交app开发价格

13530558032

架构师训练营第九周作业

_

极客大学架构师训练营 第九周作业

媲美物理机,裸金属云主机如何轻松应对11.11大促

京东科技开发者

云计算 容器 服务器 云主机

《JAVA多线程设计模式》.pdf

田维常

多线程

DataPipeline CPO 陈雷:实时数据融合之道,博观约取,价值驱动

DataPipeline数见科技

数据融合

DataPipeline CPO 陈雷:实时数据融合之法,便捷可管理

DataPipeline数见科技

数据融合

阿里达摩院副院长亲自所写Java架构29大核心知识体系+大厂面试真题+微服务

Java架构追梦

Java 学习 阿里巴巴 架构 面试

强化学习入门必看之强化学习导识

Alocasia

人工智能 学习

Springboot过滤器和拦截器详解及使用场景

996小迁

Java 编程 架构 面试 springboot

DataPipeline CTO 陈肃:构建批流一体数据融合平台的一致性语义保证

DataPipeline数见科技

数据融合

Scrum指南这么改,我看要完蛋!

华为云开发者联盟

Scrum 敏捷 改版

【JDD京智大咖说】AI 未来,路在何方?NLP、CV 技术的探索与展望

京东科技开发者

人工智能 CV nlp

京东T8Java架构师总结整理的15w字的Java面试手册,2021年金三银四不愁涨不了薪!

Java架构之路

Java 程序员 架构 面试 编程语言

6. 自定义容器类型元素验证,类级别验证(多字段联合验证)

YourBatman

Hibernate-Validator Bean Validation 多字段联合验证

DataPipeline 王睿:业务异常实时自动化检测 — 基于人工智能的系统实战

DataPipeline数见科技

大数据

公众号高频被调整,它不是企业生产文章的机器

Linkflow

客户数据平台 CDP 私域流量

数字货币交易所开发有哪些模式?区块链交易平台

13530558032

合约跟单源码案例,合约跟单模式开发

13530558032

面试官问:如何排除GC引起的CPU飙高?我脱口而出5个步骤

田维常

cpu飙满

DataPipeline CPO 陈雷:实时数据融合之法,稳定高容错

DataPipeline数见科技

数据融合

前嗅教你大数据——史上最全代理IP服务商对比

前嗅大数据

大数据 数据采集 动态代理 静态代理 代理IP

企业工作流设计原则及多项目整合开发注意事项

Marilyn

敏捷开发 工作流 企业开发

UNISKIN COO Kevin|营销数字化:数据沉淀和数据系统化运营一定要趁早!

Linkflow

营销数字化 客户数据平台 CDP

万字图文 | 聊一聊 ReentrantLock 和 AQS 那点事(看完不会你找我)

马丁玩编程

架构 AQS ReentrantLock JUC CLH

号外!5G+X联创营华为云官网上线,5G 创业春天来了!

华为云开发者联盟

华为 程序员 AI 5G

微信官方将打击恶意营销号:自媒体不可过度消费粉丝

石头IT视角

AI技术在音乐类产品中的应用场景

曲多多(嗨翻屋)版权音乐

人工智能 AI 音乐 音乐制作

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