用户名:  密码:   
网站首页即时通讯活动公告最新消息科技前沿学人动向两岸三地人在海外历届活动关于我们联系我们申请加入
栏目导航 — 美国华裔教授专家网最新消息社区报道
关键字  范围   
 
麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍
来源:机器之心 | 2021/9/4 15:26:17 | 浏览:243 | 评论:0
在一篇被 ICML 2021 接收的论文中,MIT 的一位计算机科学博士生及其业界大佬导师为矩阵乘法引入了一种基于学习的算法,该算法具有一个有趣的特性——需要的乘加运算为零。在来自不同领域的数百个矩阵的实验中,这种学习算法的运行速度是精确矩阵乘积的 100 倍,是当前近似方法的 10 倍。

矩阵乘法是机器学习中最基础和计算密集型的操作之一。因此,研究社区在高效逼近矩阵乘法方面已经做了大量工作,比如实现高速矩阵乘法库、设计自定义硬件加速特定矩阵的乘法运算、计算分布式矩阵乘法以及在各种假设下设计高效逼近矩阵乘法(AMM)等。

在 MIT 计算机科学博士生 Davis Blalock 及其导师 John Guttag 教授发表的论文《 Multiplying Matrices Without Multiplying 》中,他们为逼近矩阵乘法任务引入了一种基于学习的算法,结果显示该算法显著优于现有方法。在来自不同领域的数百个矩阵的实验中,这种学习算法的运行速度是精确矩阵乘积的 100 倍,是当前近似方法的 10 倍。这篇论文入选了机器学习顶会 ICML 2021。此外,在一个矩阵提前已知的常见情况下,研究者提出的方法还具有一个有趣的特性——需要的乘加运算(multiply-adds)为零

这些结果表明,相较于最近重点进行了大量研究与硬件投入的稀疏化、因式分解和 / 或标量量化矩阵乘积而言,研究者所提方法中的核心操作——哈希、求平均值和 byte shuffling 结合可能是更有前途的机器学习构建块。

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

  • 论文链接:https://arxiv.org/abs/2106.10860
  • 代码链接:https://github.com/dblalock/bolt

对于研究者提出的无需相乘的矩阵乘法,各路网友给出了极高的评价。有网友表示:「这是一篇不可思议且具有基础性意义的论文。训练 ML 来寻找快速做 ML 的方法。」

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

也有网友表示:「这篇论文为实现更高效的 AI 打开了一扇门。」

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

对于有网友提到的「该研究在硬件实现方面似乎很有发展前景」,一作本人现身 reddit 并给出了回复:「我们的编码表示是密集矩阵,所以布局和访问模式看上去基本与 GEMM 内核相同,也就意味着可以很容易地使用脉动阵列或修正张量核心来实现。在 x86 上,一般只需要一个 vpshufb-add 指令和一个 4-bit 解包指令就可以了。」

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

下面来看这篇论文的技术细节和实验结果。

技术细节

具体来说,该研究专注于 AMM 任务,并假设矩阵是高的(tall),并且相对密集,存在于单个机器内存中。在这种设置下,研究者遇到的主要挑战是在给定保真度水平下最小化近似线性运算所需的计算时间。这种设置会很自然地出现在机器学习和数据挖掘中,当一个数据矩阵 A 的行是样本,而一个线性算子 B 希望应用这些样本,B 可以是一个线性分类器、线性回归器,或嵌入矩阵,以及其他可能性。

举例来说,考虑一个近似 softmax 分类器的任务,以预测来自神经网络嵌入的图像标签。在这里,A 的行是每个图像的嵌入,B 的列是每个类的权值向量。分类是通过计算乘积 AB 并在结果的每一行中取 argmax 来执行的。图 1 结果表明,在 CIFAR-10 和 CIFAR-100 数据集上,使用该研究的方法及其最佳性能竞争对手的方法近似 AB 的结果。

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

该研究所用方法与传统方法背离,传统的 AMM 方法构造矩阵 V_A,V_B ∈ R^(D×d), d<<D,如下所示:

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

通常,V_A、V_B 是稀疏的,包含某种采样方案,或者具有其他结构,使得这些投影操作比密集矩阵乘法更快。简而言之,这些方法使用线性函数对 A 和 B 进行预处理,并将问题简化为低维空间中的精确矩阵乘法。

该研究提出 MADDNESS 方法 ,该方法采用非线性预处理函数,将问题简化为查表。此外,在 B 提前已知的情况下,即将训练好的线性模型应用于新数据等情况时,MADDNESS 不需要任何乘 - 加运算。该方法与用于相似性搜索的矢量量化方法密切相关。然而,该研究没有使用太多的乘 - 加量化函数,而是引入了一系列不需要乘 - 加的量化函数。

本文的贡献总计如下:

  • 一个高效的学习矢量量化函数族,可以在单个 CPU 线程中每秒编码超过 100GB 的数据。
  • 一种用于低位宽整数( low-bitwidth integers)的高速求和算法,可避免 upcasting、饱和和溢出。
  • 基于这些函数的近似矩阵乘法算法。数百个不同矩阵的实验表明,该算法明显优于现有替代方案。并且还具有理论质量保证。

实验结果

为了评估 MADDNESS 的有效性,研究者用 c++ 和 Python 实现了该算法和其他几个现有算法。评估结果如下。

MADDNESS 到底有多快?

研究者首先分析了 MADDNESS 的原始速度。在图 3 中,他们为各种矢量量化方法计算 g(A)函数的时间,结果表明,MADDNESS 比现有方法快两个数量级,其吞吐量随行的长度而增加。

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

从上图可以看出,Bolt(蓝色虚线)是与 MADDNESS 最接近的竞争对手。研究者还使用与 Bolt 相同的基线分析了聚合函数 f(·,·)的速度。如图 4 所示,他们基于 average 的、matrix-aware 的聚合方法明显快于 Bolt 基于 upcasting 的方法。

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

Softmax 分类器

前面说过,研究者在广泛使用的 CIFAR-10 和 CIFAR-100 数据集上近似线性分类器。如图 5 所示,MADDNESS 显著优于所有现有方法,几乎达到了与精确乘法相同的准确率,但比精确乘法快了一个数量级。而且,MADDNESS 是在硬件支持较差的情况下实现了这种性能。

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

基于 kernel 的分类

为了评估该方法在更大、多样性更强的数据集上的表现,研究者在来自 UCR Time Series Archive 的数据集上训练了 kernel 分类器。结果如下图 6 所示,MADDNESS 在给定准确率的情况下明显快于替代方案。

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

图像滤波

为了测试 MADDNESS 的极限,研究者对将小滤波器应用于图像的各种技术能力进行了基准测试。结果如下图 7 所示,只有 MADDNESS 比精确矩阵乘积更有优势。

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

作者简介

Davis Blalock

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

个人主页:https://dblalock.github.io/about/

Davis Blalock 是麻省理工学院的博士生,由 John Guttag 教授指导。他的主要研究方向是设计高性能的机器学习算法,以减少人们在机器学习速度、准确性、隐私和安全性之间的妥协。他于 2014 年获得弗吉尼亚大学学士学位,2016 年获得麻省理工学院硕士学位。他是 Qualcomm Innovation Fellow、NSF Graduate Research Fellow 和 Barry M. Goldwater Scholar。

John Guttag

John Guttag 是麻省理工学院计算机科学与电气工程教授、ACM Fellow。他领导着麻省理工学院计算机科学和人工智能实验室(CSAIL)的临床与应用机器组。该小组负责开发和应用先进的机器学习和计算机视觉技术,以解决各种临床相关问题,目前的研究项目包括预测和减少不良医疗事件,帮助患者匹配治疗方法和治疗者,以及医学成像。

他是《Python 编程导论》一书的作者,其在 MIT 的课程已全部公开,在B站上也可以搜到。

麻省理工学者新研究获极高评价:矩阵乘法无需相乘,速度提升100倍

参考链接:https://www.reddit.com/r/MachineLearning/comments/pffoo8/r_multiplying_matrices_without_multiplying

相关栏目:『社区报道
2021自然科研全球影响力大奖入围名单 | 自然科研全球影响力大奖 2021-09-18 [173]
UCLA段镶锋教授、黄昱教授夫妇联袂今年第三篇Science/Nature正刊 2021-09-18 [172]
中科大物理天才、最年轻哈佛华人正教授尹希入籍美国被骂“叛国贼”? 2021-09-18 [253]
177名斯坦福学者联名要求美司法部停止在美国大学中寻找“中国间谍”, 2021-09-14 [274]
哈佛大学公布2021新生的家庭背景、生活方式和活动经历调查报告 2021-09-13 [170]
美国19岁的山姆泽鲁夫在自家车库里,研制出拥有1200个晶体管的芯片 2021-09-09 [311]
覃树人因向中国出口美国海洋技术被判2年监禁 2021-09-08 [215]
普林斯顿校长致2021新生:敢于分享脆弱,方可得到刚强! 2021-09-07 [322]
耶鲁校长苏必德开学演讲:当世界置身一片火海,年轻人求学意义何在? 2021-09-03 [168]
马斯克的SpaceX与贝索斯的蓝色起源 展开万亿美元级别的“太空商战” 2021-09-04 [295]
相关栏目更多文章
最新图文:
:北京452万人将从北京迁至雄安(附部分央企名单) :《2019全球肿瘤趋势报告》 :阿尔茨海默病预防与干预核心讯息图解 :引力波天文台或有助搜寻暗物质粒子 :Sail Through the Mist - SoCal Innovation Forum 2019(10/5) 游天龙:《唐人街》是如何炼成的:UCLA社会学教授周敏的学术之路 :“为什么海外华人那么爱国,但是让他回国却不愿意?...“ :学术出版巨头Elsevier 彻查433名审稿人“强迫引用”黑幕
更多最新图文
更多《即时通讯》>>
 
打印本文章
 
您的名字:
电子邮件:
留言内容:
注意: 留言内容不要超过4000字,否则会被截断。
未 审 核:  是
  
关于我们联系我们申请加入后台管理设为主页加入收藏
美国华裔教授专家网版权所有,谢绝拷贝。如欲选登或发表,请与美国华裔教授专家网联系。
Copyright © 2021 ScholarsUpdate.com. All Rights Reserved.