萧箫发自凹非寺
量子位报道|公众号QbitAI
在不做乘加操作（multiply-adds）的情况下 ， 能计算矩阵乘法吗？
矩阵乘法包含大量a+b×c类运算 ， 因此常在运算中将乘法器和加法器进行结合成一个计算单元 ， 进行乘法累加操作 。
用近似算法的话 ， 确实可以！
这是来自MIT的最新研究 ， 他们提出了一种新的近似算法MADDNESS ， 在确保一定精度的情况下 ， 将速度提升到了现有近似算法的10倍 ， 比精确算法速度快100倍 ， 被ICML2021收录 。

文章图片
研究还认为 ， 新算法可能比最近大火的稀疏化、因子化等操作更有前途 。
目前 ， 作者已经开源了算法代码 ， 感兴趣的小伙伴们可以去尝试一下 。
一起来看看 。
用K聚类算法搞个查找表
这个算法 ， 借鉴了一种叫做乘积量化（ProductQuantization）的方法 。
其中 ， 量化本质上是一种近似操作 。
由于矩阵乘法中的每个元素 ， 都可以看做是两个向量的点积 ， 因此可以通过查找相似向量 ， 来近似地估计向量的点积 ， 而无需再进行大量乘法运算 。
乘积量化的具体原理如下：

文章图片
当我们输入一个要计算的向量a的时候 ， 函数g(·)会对a进行一个近似操作 ， 从一个提前设置好的数值查找表中 ， 找到与它最相近的那个值 ， 并输出一个近似的向量g(a) 。
与此同时 ， 这张表格中的每个值 ， 都已经提前做过点积计算了 ， 因此在输出g(a)的同时 ， 它与查询向量（queryvector）b对应的近似点积计算结果h(b)也能被查表并输出 。
最后 ， 只需要用f(·,·)函数对g(a)和h(b)做加法运算 ， 而不需要再做乘法计算了 。
简单来说 ， 就是通过近似查表的方法 ， 节省了矩阵乘法中的乘法计算时间 。
那么 ， 这样的数值查找表 ， 究竟要设置什么数值 ， 才能确保在近似计算过程中 ， 损失的计算精度最小呢？
这里借鉴了一下K聚类算法（K-means）的思路 ， 即将数据预分为K组 ， 随机选取K个对象作为初始聚类中心 ， 再通过训练迭代 ， 确保在将样本分到K个类中时 ， 每个样本与其所属类中心的距离之和最小 。

文章图片
△可视化的K聚类算法
通过这种方法计算出来的数值查找表 ， 能更准确地近似矩阵乘法的数值计算结果 。
根据这样的思路 ， 作者们提出了一种高效的向量乘积量化函数 ， 能在单CPU中每秒编码超过100GB的数据；同时 ， 还提出了一种针对低位宽整数的高速求和函数 。
然后 ， 基于这两类函数 ， 整出了一套全新的矩阵乘法算法MADDNESS 。
这个近似算法的效果如何呢？
精度保持 ， 效率提升数倍
这个算法所需要的算力并不高 ， 在搭载英特尔酷睿i7-4960HQ（2.6GHz）处理器的MacbookPro上就能完成 。
他们在Keras版本的VGG16模型上进行了测试 ， 所用的数据集是CIFAR-10/100 ， 对一系列最新的近似算法进行了评估：

文章图片
从图中来看 ， 在效率提升接近10倍的情况下 ， 采用MADDNESS（图中红线）仍然能在CIFAR-10上保持几乎不变的精度 。
即使是在CIFAR-100上 ， 在精度几乎不变的情况下 ， MADDNESS和MADDNESS-PQ也同样实现了效率最大化的结果 。
除了最新算法外 ， 与其他的现有算法相比（包括作者们在2017年提出的Bolt算法） ， 效果同样非常拔尖 。

• 消研所周报|红杉中国控股WE11DONE；奈雪自主研发自动化制茶设备；bosie正式发布NFT数字艺术作品 | 自动化
• 快充|小米12 Pro首发自研澎湃P1芯片！卢伟冰：是快充行业的巨大突破
• 《自然》《科学》预告2022科学大事件
• 消费级|Mobileye联手极氪开发自动驾驶汽车，预计2024年推出
• 极氪将与Waymo合作开发自动驾驶出租车
• 小米12|首发自研芯片澎湃P1！雷军换上小米12 Pro
• 苹果公司|芯片巨头慌了？苹果拟开发自研无线芯片
• 果然，武汉驶上了AI高速路
• 英特尔|苹果设立新办公室开发自研无线芯片 博通可能被抛弃
• 小马|小马智行，主动退了一步