【AICon】探索RAG 技术在实际应用中遇到的挑战及应对策略!AICon精华内容已上线73%>>> 了解详情
写点什么

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 则从中看到了未来人机协作的潜力,“除了用这种方式推动数学探索的边界之外,我还很高兴地看到理论研究人员开始分析这些新发现的算法,其中也许蕴藏着指向其他算法突破的线索。”

公众号推荐:

2024 年 1 月,InfoQ 研究中心重磅发布《大语言模型综合能力测评报告 2024》,揭示了 10 个大模型在语义理解、文学创作、知识问答等领域的卓越表现。ChatGPT-4、文心一言等领先模型在编程、逻辑推理等方面展现出惊人的进步,预示着大模型将在 2024 年迎来更广泛的应用和创新。关注公众号「AI 前线」,回复「大模型报告」免费获取电子版研究报告。

AI 前线公众号
2022-10-10 14:434850

评论 1 条评论

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

六大类型JavaScript题型

不叫猫先生

JavaScript 6 月 优质更文活动

轻松解决Kafka数据流丢失:提升数据完整性和可靠性

xfgg

Java kafka 6 月 优质更文活动

云计算架构设计原则

穿过生命散发芬芳

6 月 优质更文活动

C语言代码封装MQTT协议报文,了解MQTT协议通信过程

DS小龙哥

6 月 优质更文活动

洞察开源代码平台“创新力”|2023开放原子全球开源峰会开源协作平台分论坛成功举办

开放原子开源基金会

开源 开放原子全球开源峰会 开放原子 开源协作平台

广东省高校人工智能产教融合院长研讨会召开,校企协同探索AI教育新范式

飞桨PaddlePaddle

微软增加100亿美元AI收入,Salesforce如何对垒?

B Impact

首添机密计算创新成果!龙蜥首获 ACM SIGSOFT 杰出论文奖

OpenAnolis小助手

云原生 龙蜥社区 sig 机密计算 ICSE

给你的 ABAP 对象打上标签(Tag)

Jerry Wang

SAP abap Netweaver 思爱普 6 月 优质更文活动

CFlow:从DevOps到BizDevOps,价值流管理是必然的趋势

嘉为蓝鲸

DevOps 价值流 嘉为蓝鲸 VSM

百度文心一格x京东618:打造电商行业首个AI线下广告,节省80%制作成本

飞桨PaddlePaddle

百度 飞桨 AIGC 京东618

TrafficRoute:一体化的DNS解析和流量调度套件

火山引擎边缘云

技术 流量 解析 火山引擎边缘云

原点安全助力金融机构消费者个人信息保护合规

原点安全

数据安全 金融机构 消费者个人信息保护

HarmonyOS 极客马拉松2023 正式启动,诚邀极客们用键盘码出无限可能!

HarmonyOS开发者

HarmonyOS

一行代码将SAP CDS view数据以ALV的方式输出

Jerry Wang

abap Netweaver 思爱普 6 月 优质更文活动

UI自动化的稳定性和效率

QE_LAB

自动化测试 UI自动化测试 appium

华为云CodeArtBuild减负!云端编译构建,让你的开发省时省力!

华为云PaaS服务小智

云计算 代码 华为云 编译构建

Spring框架中的线程池

demo123567

spring 线程池

共建、共享开源EDA核心共性技术框架|2023开放原子全球开源峰会开源EDA分论坛成功举办

开放原子开源基金会

开源 开放原子全球开源峰会 开放原子 开源EDA

C语言编程语法—排序算法

攻城狮Wayne

C语言 排序算法 6 月 优质更文活动

WeOpsV4.1重磅出击,日志监控功能横空出世!

嘉为蓝鲸

运维 日志 weops 嘉为蓝鲸

开源教育决定未来|2023开放原子全球开源峰会开源教育与人才分论坛成功召开

开放原子开源基金会

开源 开放原子全球开源峰会 开放原子 开源教育与人才

玺璐传媒——连续多年获得中央电视台广告一级代理资质

科技热闻

把数字中国,建立在行业感知的底座上

脑极体

行业感知

HarmonyOS 极客马拉松2023 正式启动,诚邀极客们用键盘码出无限可能!

说山水

2023-06-15:说一说Redis的Key和Value的数据结构组织?

福大大架构师每日一题

redis 福大大架构师每日一题

自动化回归测试平台 AREX 的 Mock 实现原理

AREX 中文社区

Java Mock测试框架 流量回放

3个方法,产品迭代延期率降为0?

嘉为蓝鲸

DevOps 持续集成 研发迭代

互联网行业-镭速文件传输系统方案

镭速

Django笔记四十三之使用uWSGI部署Django系统

Hunter熊

Python django 部署 uwsgi

vivo 帐号服务稳定性建设之路-平台产品系列06

vivo互联网技术

帐号 服务稳定性 架构优化

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