「deepmind」50年后,矩阵乘法迎来全新突破!
原文标题:50年后,矩阵乘法迎来全新突破!
数千年来,算法一直在帮助数学家进行基本运算。
古埃及人发明了一种不需要乘法表就能得出两个数字的乘积的算法;欧几里得描述了一种沿用至今的计算最大公约数的算法;在伊斯兰的黄金时代,花拉子米设计出了求解线性方程和二次方程的新算法。尽管现如今我们对算法已经非常熟悉,但发现新算法的过程仍是非常困难的。
在一篇于近期发表在《自然》杂志上的论文中,DeepMind 团队介绍了第一个用于发现新的、高效的、可证明正确的基本算法(如矩阵乘法)的人工智能系统——AlphaTensor。它打破了一个保持了 50 多年的记录,发现了一种能更快地计算两个矩阵之间的乘法的算法。
核心运算:矩阵乘法
矩阵乘法是我们非常熟悉,也是代数中最基本的运算之一。这个看似简单的数学运算,对当代数字世界有着巨大的影响。
两个 3×3 矩阵相乘的例子。(图 /DeepMind)
矩阵乘法是许多不同应用程序的核心计算类型,从处理智能手机中的图像到识别语音指令,从为电脑游戏生成图像到模拟复杂的物理学 …… 可以说,在我们的日常生活中,矩阵乘法无处不在。
加快这种运算的计算速度可以对无数日常生活和工作中的计算任务产生重大影响。世界各地的公司不惜花费大量的时间和金钱来开发计算硬件,为的就是能够进行有效地矩阵相乘。因此,即使只是微小的改进矩阵乘法的效率,也能产生广泛的影响。
我们很多人在高中时期就学习过应该如何计算矩阵乘法。两个矩阵相乘通常涉及用一个矩阵中的行,乘以另一个矩阵的列。比如两个大小都为 2×2 的矩阵相乘时,就需要进行 8 次乘法运算才能求得两个矩阵的乘积。在长达几个世纪的时间里,数学家们都认为,矩阵乘法的这种标准算法有着最优效率。
但在 1969 年,德国数学家沃尔克 · 施特拉森(Volker Strassen)证明,还有更好的算法存在。通过研究 2x2 矩阵,他发现了一种只需要 7 次就能将 2x2 矩阵相乘的方法。
施特拉森算法
这种算法被称为施特拉森算法,这种算法需要进行多一些的加法,但这是可以接受的,因为计算机在计算加法时要比计算乘法快得多。
标准算法与施特拉森算法的对比:当两个 2×2 的矩阵相乘时,标准算法需要经过 8 次乘法运算,而施特拉森算法只需要进行 7 次乘法运算。对整体效率来说,乘法的影响比加法更大。(图 /DeepMind)
在施特拉森做出突破后,数学家又进行了几十年的研究,尽管发现了一些不适用于计算机代码的微小改进,但对更大的矩阵来说问题仍然没有得到解决——在某种程度上,他们甚至不知道用这种方法计算两个大小仅为 3x3 的矩阵相乘的效率如何。
在新研究中,DeepMind 团队探索了现代人工智能技术如何推动新的矩阵相乘算法的自动发现,并发现了一种可以在当前硬件上完美运作的更快的算法。
一个困难的棋盘游戏
首先,研究人员将寻找矩阵乘法的有效算法的问题,转化为一个名为 TensorGame 的三维棋盘游戏。在这个游戏中,棋盘是一个三维张量,代表要解决的乘法问题;每一步棋都代表解决问题的下一步,因此游戏中所采取的一系列的移动就代表一种算法。
玩家的目标是,通过允许的移动来修改张量,从而用最少的步骤让张量中的所有数字都归零。这是一项极具挑战性的游戏,因为每一步都可能需要从万亿步棋中进行选择。两个矩阵相乘的方法比宇宙中原子数量还要多。在一些例子中,这个游戏每一步可能的走法数量,是 10 的 33 次方(10³³)。
为了解决这一与传统游戏截然不同的挑战,研究人员开发了多个关键组件,包括一个包含特定问题归纳偏倚的新的神经网络架构,一个生成有用合成数据的程序,以及一个能充分利用问题对称性的配方。
然后,研究人员用一种被称为强化学习的机器学习方式,来训练一个 AlphaTensor 智能体来玩这个游戏。在开始时,AlphaTensor 处于不了解任何现有的矩阵相乘算法的状态,通过学习,AlphaTensor 会随着时间的推移逐渐改进:它开始发现那些人类已知的矩阵相乘算法,比如施特拉森算法,并最终超越人类直觉的领域,发现比已知的更快的算法。
由 AlphaTensor 进行的三维棋盘游戏,其目标是找到一个正确的矩阵乘法算法。游戏状态是一个由数字组成的立方数组(灰色表示 0、蓝色表示 1、绿色表示 -1),代表着剩余要做的工作。(图 /DeepMind)
有效的计算
计算一个 4x5 的矩阵乘以一个 5x5 的矩阵,传统算法需要进行 100 次乘法运算;而用在此之前的最佳算法来计算,这个数字可以减少到 80 次;现在,AlphaTensor 发现的算法只需 76 次乘法就能完成运算。
总的来说,AlphaTensor 在超过 70 种大小各异的矩阵上击败了现有的最佳算法。比如它将两个 9×9 的矩阵相乘所需的步数从 511 减少到 498,将两个 11×11 的矩阵相乘所需的步数从 919 减少到 896。在其他许多情况下,AlphaTensor 重新发现了那些现有的最佳算法。
不仅如此,AlphaTensor 还在有限域内改进了施特拉森的二阶算法,这是施特拉森算法自 50 年前发现以来迎来的首个改进。这些用于小矩阵相乘的算法,可作为用来乘任意大小的更大矩阵的原语。
另外,AlphaTensor 还发现了一组具有最先进复杂性的多样化算法,每种大小都有多达数千个矩阵乘法算法,这表明矩阵乘法算法的空间比以前想象的更为丰富。
AlphaTensor 具有一个对应于算法的运行时间的目标。当 AlphaTensor 发现正确的矩阵乘法算法时,就会在目标硬件上对其进行基准测试,然后反馈给 AlphaTensor,以便在目标硬件上学习更高效的算法。(图 /DeepMind)
在这个丰富的空间中,算法具有不同的数学特性和实用特性。利用这种多样性,研究人员将 AlphaTensor 调整为专门寻找能在一些特定硬件上快速运行的算法。用这些算法来计算大矩阵相乘的速度比在相同硬件上的常用算法快 10-20%,这展示了 AlphaTensor 在优化任意目标方面的灵活性。
未来研究与应用
从数学的角度来看,新的结果可以指导复杂性理论(旨在确定解决计算问题的最快算法)的进一步研究。可以说,AlphaTensor 提升了我们对矩阵乘法算法的丰富性的理解,而这种理解或许会为我们带来新的惊喜,比如帮助我们确定计算机科学中最基本的开放问题之一——矩阵乘法的渐近复杂性。
正如前文所提到的,矩阵乘法是计算机图形学、数字通信、神经网络训练和科学计算等许多计算任务的核心组成部分,因此 AlphaTenor 的发现可以大大提高这些领域的计算效率。AlphaTensor 在考虑任何类型的目标上所拥有的灵活性,也可以激发设计不同算法的新应用。
DeepMind 团队也希望,在这次工作的基础上,未来能够有更多的人开始应用人工智能来帮助解决数学和科学领域的一些最重要的挑战。
热门文章:造型大变<\a>
其他人还看了
「国际象棋」智能肛珠作弊案反转:19岁小将告世界冠军诽谤索赔7亿
「科研」清华大学交叉信息研究院杜韬课题组招生,计算机图形学、机器学习方
打开程序弹出"你要允许以下程序对此计算机进行更改吗"解决方法
打开控制面板提示本次操作由于这台计算机的限制而被取消解决方法
无法启动此程序,因此计算机中丢失d3dx9-41.dll怎么解决?
郑重声明:本文“「deepmind」50年后,矩阵乘法迎来全新突破!”,https://nmgjrty.com/shumacp_622344.html内容,由原理提供发布,请自行判断内容优劣。
- 全部评论(0)
- 大香煮伊区一二三四区2021维护成功,可以无限制进出了!
- 大香煮伊区一二三四区2021不再收费了!网友:终于可以免费看了
- 大香煮伊区一二三四区2021不再收费!网友:可以白嫖了
- 一卡二卡3卡4卡视频免费播放重新开放了!网友:久违了
- 一卡二卡3卡4卡视频免费播放出入无限制!网友:平台都这样才好!
- 一卡二卡3卡4卡视频免费播放人气暴涨!网友:毕竟来了很多大主播!
- 欧美xbox和ps大片重新开放了!网友:久违了
- 欧美xbox和ps大片人气暴涨原因,无限制出入是关键!
- 欧美xbox和ps大片免费播放!网友:已经来了不少
- 成品网站w灬源码1688直播身材好!网友:比明星还赞!
- 成品网站w灬源码1688直播更新引热议!上线了多种新功能!
- 成品网站w灬源码1688直播适合晚上看!粉丝:我们懂!
- XXXXXL19waswas重新开放,并且免费使用!
- XXXXXL19waswas不再收费了!网友:终于可以免费看了
- XXXXXL19waswas不再收费!网友:付费内容都取消了
- Japonensisjavacomplete重新开放!网友:爷青回!
最新更新
- 大香煮伊区一二三四区2021维护成功,可以
- 大香煮伊区一二三四区2021不再收费了!网
- 大香煮伊区一二三四区2021不再收费!网友
- 一卡二卡3卡4卡视频免费播放重新开放了
- 一卡二卡3卡4卡视频免费播放出入无限制
- 一卡二卡3卡4卡视频免费播放人气暴涨!
- 欧美xbox和ps大片重新开放了!网友:久违
- 欧美xbox和ps大片人气暴涨原因,无限制出
- 欧美xbox和ps大片免费播放!网友:已经来
- 成品网站w灬源码1688直播身材好!网友:
- 成品网站w灬源码1688直播更新引热议!上
- 成品网站w灬源码1688直播适合晚上看!粉
- XXXXXL19waswas重新开放,并且免费使用!
- XXXXXL19waswas不再收费了!网友:终于可以
- XXXXXL19waswas不再收费!网友:付费内容都
推荐阅读
- 「生物」我们应该寻找什么样的外星生命,高等的还是低等的?
- 「空间望远镜」韦布空间望远镜捕捉到布满恒星的创生之柱
- 「行者」从《双城之战》到《边缘行者》,游改动画迎来盛世?
- 「国际象棋」智能肛珠作弊案反转:19岁小将告世界冠军诽谤索赔7亿
- 「英伟达」不止是游戏党,他们才是被英伟达坑怕的人。
- 「索尼」索尼官宣!猜猜A7R5多钱?R2要价1.9万、R3要价2.4万、R4要价2.7万……
- 「癌症」一种癌症转移的关键因素
- 「智能手表」面世八年后,谷歌的智能手表生态终于迎来开放曙光
- 「adobe」用VR手捏3D模型,PS直接与甲方对线,Adobe新技术确实给设计师炫到了
- 「amd」RTX40的对手来了!AMDRDNA3显卡发布会官宣
- 「奥斯汀」苹果M3准备登场,库克展示奥斯汀AppleSilicon工程团队努力成果
- 「马修」Copilot要摊官司了!工作20年老程序员重新激活律师证,发起集体诉讼,
猜你喜欢
- [iPhone]iPhone13promax远峰蓝128G入手
- [安卓手机]realme真我GTNeo2开箱,金刚石冰芯散热系统+E4屏,5000mAh大电池
- [贴膜]红米9爆屏更换记录,弯曲的中框修复
- [智能机器人]编程从娃娃抓起,MakeBlock程小奔上手体验
- [智能摄像机]内置大电池,无需打孔走线,小米室外摄像机给你满满的安全感
- [充电器]65w网红氮化镓一次看个够
- [电脑支架]原汤化原食,LGErgo显示器支架
- [蓝牙耳机]中端耳机音质天花板,降噪很有一手,鹿图COCO真蓝牙降噪耳机评测
- [音频播放器]关于R01主板的主观看法,和一些碎碎念
- [充电器]双口快充,满足日常需求
- [VR设备]GOOVISLite头戴影院评测
- [蓝牙耳机]魅蓝Blus耳机体验,魅蓝依旧还是当年坚持做良品的青年良品
- [安卓手机]从5988跌至2749,256GB+鸿蒙OS+7nm麒麟,从高端市场跌至中端市场
- 「轻众测|素诺智能可视冲牙器」别急,对准再冲!素诺可视冲牙器让残渣无所
- 「九号新品Nano及Air T15」萌娃初体验——Ninebot九号平衡车Nano