[[421266]]

本文經(jīng)AI新媒體量子位（公眾號ID:QbitAI）授權(quán)轉(zhuǎn)載，轉(zhuǎn)載請聯(lián)系出處。

在不做乘加操作（multiply-adds）的情況下，能計(jì)算矩陣乘法嗎？

矩陣乘法包含大量a+b×c類運(yùn)算，因此常在運(yùn)算中將乘法器和加法器進(jìn)行結(jié)合成一個(gè)計(jì)算單元，進(jìn)行乘法累加操作。

用近似算法的話，確實(shí)可以！

這是來自MIT的最新研究，他們提出了一種新的近似算法MADDNESS，在確保一定精度的情況下，將速度提升到了現(xiàn)有近似算法的10倍，比精確算法速度快100倍，被ICML 2021收錄。

研究還認(rèn)為，新算法可能比最近大火的稀疏化、因子化等操作更有前途。

目前，作者已經(jīng)開源了算法代碼，感興趣的小伙伴們可以去嘗試一下。

一起來看看。

用K聚類算法搞個(gè)查找表

這個(gè)算法，借鑒了一種叫做乘積量化（Product Quantization）的方法。

其中，量化本質(zhì)上是一種近似操作。

由于矩陣乘法中的每個(gè)元素，都可以看做是兩個(gè)向量的點(diǎn)積，因此可以通過查找相似向量，來近似地估計(jì)向量的點(diǎn)積，而無需再進(jìn)行大量乘法運(yùn)算。

乘積量化的具體原理如下：

當(dāng)我們輸入一個(gè)要計(jì)算的向量a的時(shí)候，函數(shù)g(·)會(huì)對a進(jìn)行一個(gè)近似操作，從一個(gè)提前設(shè)置好的數(shù)值查找表中，找到與它最相近的那個(gè)值，并輸出一個(gè)近似的向量g(a)。

與此同時(shí)，這張表格中的每個(gè)值，都已經(jīng)提前做過點(diǎn)積計(jì)算了，因此在輸出g(a)的同時(shí)，它與查詢向量（query vector）b對應(yīng)的近似點(diǎn)積計(jì)算結(jié)果h(b)也能被查表并輸出。

最后，只需要用f(·,·)函數(shù)對g(a)和h(b)做加法運(yùn)算，而不需要再做乘法計(jì)算了。

簡單來說，就是通過近似查表的方法，節(jié)省了矩陣乘法中的乘法計(jì)算時(shí)間。

那么，這樣的數(shù)值查找表，究竟要設(shè)置什么數(shù)值，才能確保在近似計(jì)算過程中，損失的計(jì)算精度最小呢？

這里借鑒了一下K聚類算法（K-means）的思路，即將數(shù)據(jù)預(yù)分為K組，隨機(jī)選取K個(gè)對象作為初始聚類中心，再通過訓(xùn)練迭代，確保在將樣本分到K個(gè)類中時(shí)，每個(gè)樣本與其所屬類中心的距離之和最小。

△可視化的K聚類算法

通過這種方法計(jì)算出來的數(shù)值查找表，能更準(zhǔn)確地近似矩陣乘法的數(shù)值計(jì)算結(jié)果。

根據(jù)這樣的思路，作者們提出了一種高效的向量乘積量化函數(shù)，能在單CPU中每秒編碼超過100GB的數(shù)據(jù)；同時(shí)，還提出了一種針對低位寬整數(shù)的高速求和函數(shù)。

然后，基于這兩類函數(shù)，整出了一套全新的矩陣乘法算法MADDNESS。

這個(gè)近似算法的效果如何呢？

精度保持，效率提升數(shù)倍

這個(gè)算法所需要的算力并不高，在搭載英特爾酷睿i7-4960HQ（2.6GHz）處理器的Macbook Pro上就能完成。

他們在Keras版本的VGG16模型上進(jìn)行了測試，所用的數(shù)據(jù)集是CIFAR-10/100，對一系列最新的近似算法進(jìn)行了評估：

從圖中來看，在效率提升接近10倍的情況下，采用MADDNESS（圖中紅線）仍然能在CIFAR-10上保持幾乎不變的精度。

即使是在CIFAR-100上，在精度幾乎不變的情況下，MADDNESS和MADDNESS-PQ也同樣實(shí)現(xiàn)了效率最大化的結(jié)果。

除了最新算法外，與其他的現(xiàn)有算法相比（包括作者們在2017年提出的Bolt算法），效果同樣非常拔尖。

對比計(jì)算速度的話，MADDNESS的點(diǎn)積速度就能比現(xiàn)有最快方法快兩倍左右。

當(dāng)然，也有讀者指出，這篇論文還存在一些待解決的問題：

①論文用的是VGG16模型，但沒有在Transformer等更經(jīng)典的模型（如BERT）中進(jìn)行實(shí)驗(yàn)；②雖然對矩陣乘法進(jìn)行了加速，但畢竟只是近似算法，意味著潛在的精度損失；③沒有在GPU中測試評估結(jié)果。

但他仍然認(rèn)為，這不失為一篇非常有意思的研究。

作者介紹

Davis Blalock，MIT的計(jì)算機(jī)系博士生，致力于研發(fā)快速機(jī)器學(xué)習(xí)算法，他認(rèn)為速度是衡量機(jī)器學(xué)習(xí)模型的一個(gè)非常重要的因素。

John Guttag，MIT計(jì)算機(jī)系教授，研究方向是機(jī)器學(xué)習(xí)、AI和計(jì)算機(jī)視覺，目前的研究項(xiàng)目集中在醫(yī)療AI和醫(yī)學(xué)成像上。

值得一提的是，這兩位研究人員，此前還炮轟過神經(jīng)網(wǎng)絡(luò)中的剪枝算法。

他們針對其中的81種算法進(jìn)行了橫向?qū)Ρ?，發(fā)現(xiàn)“沒有明確證據(jù)表明，這些算法在10年內(nèi)，對任務(wù)效果有明顯改善”。

研究一作Davis Blalock還認(rèn)為：

這些改進(jìn)都是所謂的“微調(diào)”，而不是科研人員聲稱的“核心創(chuàng)新”，甚至有些改進(jìn)方法可能根本就不存在。

在對AI模型進(jìn)行效率提升上，兩位作者確實(shí)是很嚴(yán)格了。

項(xiàng)目地址：
https://github.com/dblalock/bolt

論文地址：
https://arxiv.org/abs/2106.10860