矩陣乘法無需相乘，速度提升100倍，MIT開源最新近似算法

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

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

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

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

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

一起來看看。

用K聚類算法搞個查找表

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

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

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

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

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

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

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

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

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

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

△可視化的K聚類算法

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

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

然後，基於這兩類函數，整出了一套全新的矩陣乘法算法MADDNESS。

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

精度保持，效率提升數倍

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

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

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

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

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

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

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

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

作者介紹

Davis Blalock，MIT的計算機系博士生，致力於研發快速機器學習算法，他認爲速度是衡量機器學習模型的一個非常重要的因素。

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

值得一提的是，這兩位研究人員，此前還炮轟過神經網絡中的剪枝算法。

他們針對其中的81種算法進行了橫向對比，發現“沒有明確證據表明，這些算法在10年內，對任務效果有明顯改善”。

研究一作Davis Blalock還認爲：

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

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

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

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