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

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

用近似算法的話，確實可以,！

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

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

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

一起來看看,。

用K聚類算法搞個查找表

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

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

由于矩陣乘法中的每個元素，都可以看做是兩個向量的點積,，因此可以通過查找相似向量,，來近似地估計向量的點積，而無需再進行大量乘法運算,。

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

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

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

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

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

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

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

△可視化的K聚類算法

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

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

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

這個近似算法的效果如何呢？

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

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

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

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

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

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

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

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

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

但他仍然認為,，這不失為一篇非常有意思的研究,。

作者介紹

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

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

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

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

研究一作Davis Blalock還認為：

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

在對AI模型進行效率提升上，兩位作者確實是很嚴格了,。

項目地址：
https://github.com/dblalock/bolt

論文地址：
https:///abs/2106.10860

參考鏈接：
[1]https://mp.weixin.qq.com/s/VK2W9zD83ddSzYSLLS21UQ
[2]https://news./item?id=28375096

— 完 —

量子位 QbitAI · 頭條號簽約

關(guān)注我們,，第一時間獲知前沿科技動態(tài)