ICML 2021文章引发热议：矩阵乘法无需相乘，速度提升100倍
?作者?|?Synced
來源?|?機器之心
在一篇被 ICML 2021 接收的論文中，MIT 的一位計算機科學博士生及其業界大佬導師為矩陣乘法引入了一種基于學習的算法，該算法具有一個有趣的特性——需要的乘加運算為零。在來自不同領域的數百個矩陣的實驗中，這種學習算法的運行速度是精確矩陣乘積的 100 倍，是當前近似方法的 10 倍。
矩陣乘法是機器學習中最基礎和計算密集型的操作之一。因此，研究社區在高效逼近矩陣乘法方面已經做了大量工作，比如實現高速矩陣乘法庫、設計自定義硬件加速特定矩陣的乘法運算、計算分布式矩陣乘法以及在各種假設下設計高效逼近矩陣乘法（AMM）等。
在 MIT 計算機科學博士生 Davis Blalock 及其導師 John Guttag 教授發表的論文《 Multiplying Matrices Without Multiplying 》中，他們為逼近矩陣乘法任務引入了一種基于學習的算法，結果顯示該算法顯著優于現有方法。在來自不同領域的數百個矩陣的實驗中，這種學習算法的運行速度是精確矩陣乘積的 100 倍，是當前近似方法的 10 倍。這篇論文入選了機器學習頂會 ICML 2021。
此外，在一個矩陣提前已知的常見情況下，研究者提出的方法還具有一個有趣的特性——需要的乘加運算（multiply-adds）為零。
這些結果表明，相較于最近重點進行了大量研究與硬件投入的稀疏化、因式分解和 / 或標量量化矩陣乘積而言，研究者所提方法中的核心操作——哈希、求平均值和 byte shuffling 結合可能是更有前途的機器學習構建塊。
論文鏈接：
https://arxiv.org/abs/2106.10860
代碼鏈接：
https://github.com/dblalock/bolt
對于研究者提出的無需相乘的矩陣乘法，各路網友給出了極高的評價。有網友表示：「這是一篇不可思議且具有基礎性意義的論文。訓練 ML 來尋找快速做 ML 的方法。」
也有網友表示：「這篇論文為實現更高效的 AI 打開了一扇門。」
對于有網友提到的「該研究在硬件實現方面似乎很有發展前景」，一作本人現身 reddit 并給出了回復：「我們的編碼表示是密集矩陣，所以布局和訪問模式看上去基本與 GEMM 內核相同，也就意味著可以很容易地使用脈動陣列或修正張量核心來實現。在 x86 上，一般只需要一個 vpshufb-add 指令和一個 4-bit 解包指令就可以了。」
下面來看這篇論文的技術細節和實驗結果。
技術細節
具體來說，該研究專注于 AMM 任務，并假設矩陣是高的（tall），并且相對密集，存在于單個機器內存中。在這種設置下，研究者遇到的主要挑戰是在給定保真度水平下最小化近似線性運算所需的計算時間。這種設置會很自然地出現在機器學習和數據挖掘中，當一個數據矩陣 A 的行是樣本，而一個線性算子 B 希望應用這些樣本，B 可以是一個線性分類器、線性回歸器，或嵌入矩陣，以及其他可能性。
舉例來說，考慮一個近似 softmax 分類器的任務，以預測來自神經網絡嵌入的圖像標簽。在這里，A 的行是每個圖像的嵌入，B 的列是每個類的權值向量。分類是通過計算乘積 AB 并在結果的每一行中取 argmax 來執行的。圖 1 結果表明，在 CIFAR-10 和 CIFAR-100 數據集上，使用該研究的方法及其最佳性能競爭對手的方法近似 AB 的結果。
該研究所用方法與傳統方法背離，傳統的 AMM 方法構造矩陣 V_A,V_B ∈ R^(D×d) , d<<D，如下所示：
通常，V_A、V_B 是稀疏的，包含某種采樣方案，或者具有其他結構，使得這些投影操作比密集矩陣乘法更快。簡而言之，這些方法使用線性函數對 A 和 B 進行預處理，并將問題簡化為低維空間中的精確矩陣乘法。
該研究提出 MADDNESS 方法 ，該方法采用非線性預處理函數，將問題簡化為查表。此外，在 B 提前已知的情況下，即將訓練好的線性模型應用于新數據等情況時，MADDNESS 不需要任何乘 - 加運算。該方法與用于相似性搜索的矢量量化方法密切相關。然而，該研究沒有使用太多的乘 - 加量化函數，而是引入了一系列不需要乘 - 加的量化函數。
本文的貢獻總計如下：
一個高效的學習矢量量化函數族，可以在單個 CPU 線程中每秒編碼超過 100GB 的數據。
一種用于低位寬整數（ low-bitwidth integers）的高速求和算法，可避免 upcasting、飽和和溢出。
基于這些函數的近似矩陣乘法算法。數百個不同矩陣的實驗表明，該算法明顯優于現有替代方案。并且還具有理論質量保證。
實驗結果
為了評估 MADDNESS 的有效性，研究者用 c++ 和 Python 實現了該算法和其他幾個現有算法。評估結果如下。
MADDNESS 到底有多快？
研究者首先分析了 MADDNESS 的原始速度。在圖 3 中，他們為各種矢量量化方法計算 g(A) 函數的時間，結果表明，MADDNESS 比現有方法快兩個數量級，其吞吐量隨行的長度而增加。
從上圖可以看出，Bolt（藍色虛線）是與 MADDNESS 最接近的競爭對手。研究者還使用與 Bolt 相同的基線分析了聚合函數 f(·，·) 的速度。如圖 4 所示，他們基于 average 的、matrix-aware 的聚合方法明顯快于 Bolt 基于 upcasting 的方法。
Softmax 分類器
前面說過，研究者在廣泛使用的 CIFAR-10 和 CIFAR-100 數據集上近似線性分類器。如圖 5 所示，MADDNESS 顯著優于所有現有方法，幾乎達到了與精確乘法相同的準確率，但比精確乘法快了一個數量級。而且，MADDNESS 是在硬件支持較差的情況下實現了這種性能。
基于 kernel 的分類
為了評估該方法在更大、多樣性更強的數據集上的表現，研究者在來自 UCR Time Series Archive 的數據集上訓練了 kernel 分類器。結果如下圖 6 所示，MADDNESS 在給定準確率的情況下明顯快于替代方案。
圖像濾波
為了測試 MADDNESS 的極限，研究者對將小濾波器應用于圖像的各種技術能力進行了基準測試。結果如下圖 7 所示，只有 MADDNESS 比精確矩陣乘積更有優勢。
作者簡介
Davis Blalock
個人主頁：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 的課程已全部公開，不過或許是因為 Guttag 思維敏捷，他的語速有點快。
參考鏈接：https://www.reddit.com/r/MachineLearning/comments/pffoo8/r_multiplying_matrices_without_multiplying/
????
現在，在「知乎」也能找到我們了
進入知乎首頁搜索「PaperWeekly」
點擊「關注」訂閱我們的專欄吧
·
總結
以上是生活随笔為你收集整理的ICML 2021文章引发热议：矩阵乘法无需相乘，速度提升100倍的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 6月16日种红小豆能成熟吗?
- 下一篇： 买基金从哪些方面分析 这几点千万不能忽