文：蘇劍林
編：兔子醬
單位：追一科技

今天給大家介紹一篇1962年的論文《Computer Multiplication and Division Using Binary Logarithms》^[1]，作者是John N. Mitchell，他在里邊提出了一個相當(dāng)有意思的算法：在二進制下，可以完全通過加法來近似完成兩個數(shù)的相乘，最大誤差不超過1/9。整個算法相當(dāng)巧妙，更有意思的是它還有著非常簡潔的編程實現(xiàn)，讓人拍案叫絕。然而，筆者發(fā)現(xiàn)網(wǎng)上居然找不到介紹這個算法的網(wǎng)頁，所以在此介紹一番。

你以為這只是過時的玩意？那你就錯了，前不久才有人利用它發(fā)了一篇NeurIPS 2020呢！所以，確定不來了解一下嗎？

快速對數(shù)與指數(shù)

說到乘法變加法，大家應(yīng)該很自然能聯(lián)想到對數(shù)和指數(shù)，即

本文是基于二進制的，所以a=2。問題在于上式雖然確實將乘法轉(zhuǎn)為加法了，但是對數(shù)和轉(zhuǎn)換后的指數(shù)算起來都不是一件容易的事情。所以要利用這個等式做乘法，關(guān)鍵在于要實現(xiàn)快速對數(shù)和指數(shù)運算。

對于十進制的非負(fù)數(shù)p，我們假設(shè)它的二進制表示為

其中且各個，那么我們就有

記，我們得到

在這里，Mitchell做了一個相當(dāng)果斷而美妙的近似，那就是（后面我們會再進行誤差分析），于是得到

這個結(jié)果妙在何處呢？首先n是一個整數(shù)，等于p的二進制的整數(shù)部分的位數(shù)減去1，它轉(zhuǎn)換為二進制自然自然也是整數(shù)；那x呢？根據(jù)x的定義我們不難看出，實際上x的二進制表示就是

也就是說x其實就是上述近似的小數(shù)部分，它的二進制表示只不過是p的二進制表示的簡單變形（小數(shù)點平移）。

綜上所述，我們得到對數(shù)的Mitchell近似算法：

將上述過程逆過來，就得到了指數(shù)的Mitchell近似算法：所以，在二進制下對數(shù)和指數(shù)的近似計算就只是數(shù)數(shù)和拼接操作而已！驚艷不？神奇不？

一個乘法的例子

有了快速的（近似的）對數(shù)和指數(shù)算法，我們就可以乘法了，現(xiàn)在我們就用這個思路來算一個具體例子，由此加深我們對上述過程理解。

我們要算的是12.3×4.56，計算流程如下表（近似指數(shù)是對求和的結(jié)果算的）：其中p,qp,qp,q二進制表示為無限循環(huán)小數(shù)，這里只截斷了有限位，如果保留精確的二進制表示，那么最終結(jié)果是53.68，跟上表的53.625相差不大?？梢钥吹?#xff0c;整個過程的主要計算量有兩部分：求和、十進制與二進制之間的轉(zhuǎn)換。然而，盡管十進制與二進制之間的轉(zhuǎn)換對于我們?nèi)藖碚f是計算量比較大的操作，但對于計算機來說，它本身就是二進制存儲的，我們可以認(rèn)為兩者之間的轉(zhuǎn)換計算量可以忽略不計；又或者說，只要我們還是以十進制為輸出，那么不管什么算法這部分計算量都是必然存在的，因此我們不把它算進去算法的復(fù)雜度中。所以，整個算法的計算量就只有求和這一步，實現(xiàn)了將乘法（近似地）轉(zhuǎn)化為加法運算。

神奇的C++實現(xiàn)

更妙的是，上述過程有一個非常簡單的C++實現(xiàn)，參考如下：

#include<stdio.h>int?main()?{float?a?=?12.3f;float?b?=?4.56f;int?c?=?*(int*)&a?+?*(int*)&b?-?0x3f800000;printf("近似結(jié)果：%f\n",?*(float*)&c);printf("精確結(jié)果：%f\n",?a?*?b);return?0; }

沒有C++編譯環(huán)境的朋友也可以找個網(wǎng)頁版的在線C++運行程序試跑一下，測試一下它的結(jié)果。就算是不懂C++的朋友（比如筆者）大概也可以感覺到，這段代碼大概就是轉(zhuǎn)化為兩個數(shù)相加并且減去一個常數(shù)，這怎么就能實現(xiàn)乘法了？還有的讀者可能問Python里邊能這樣寫嗎？

首先，后一個問題的答案是不能，因為Python的數(shù)據(jù)類型已經(jīng)經(jīng)過了高度封裝了，而上述C++代碼的可行性在于浮點數(shù)的IEEE754表示法：一個十進制浮點數(shù)首先會被轉(zhuǎn)化為二進制，然后標(biāo)準(zhǔn)化為科學(xué)計數(shù)法，最后用一個特定的結(jié)構(gòu)將科學(xué)計數(shù)法的結(jié)果存下來。具體來說，IEEE754用32個0/1表示一個浮點數(shù)，其中1位表示正負(fù)號（0為正），8位表示科學(xué)計數(shù)法的指數(shù)，23位表示科學(xué)計數(shù)法的小數(shù)，以9.75為例，它的二進制為1001.11，寫成科學(xué)計數(shù)法就是，這里的10、11都是二進制，對應(yīng)十進制的，注意指數(shù)部分我們還需要加上偏移量127，即3次方實際上存的是130（二進制表示為10000010），因為前面126個數(shù)要用來表示負(fù)整數(shù)冪，而主要部分1.00111，由于第一位必然是1，因此只需要把0.00111存下來，所以9.75背后的表示方式為：

知道IEEE754表示法之后，就可以理解上述代碼了，*(int*)&a和*(int*)&b其實就是把a,ba,ba,b的IEEE754表示拿出來，當(dāng)作普通的整數(shù)來運算，兩者相加，其實正好對應(yīng)著Mitchell近似對數(shù)后的相加結(jié)果，但是指數(shù)部分會多出一個偏移量，所以要減去整個偏移量，由于偏移量是127，并且后面還有23位，所以減去偏移量相當(dāng)于減去常數(shù)127×2^23，表示為十六進制就是3f800000（因為二進制表示太長了，所以計算機一般用十六進制來代替二進制進行IO），最后將加減后的結(jié)果恢復(fù)為浮點數(shù)。

（注：其實筆者也不懂C++，上述理解是東拼西湊勉強得到的，如果不當(dāng)之處，請大家指出。）

最大誤差的分析

標(biāo)題寫到，這個算法的誤差不超1/9，現(xiàn)在我們就來證明這一點。證明需要全部轉(zhuǎn)換到十進制來理解，Mitchell近似實際上是用了如下近似式：

其中n是整數(shù)，而x∈[0,1)，所以分析誤差也是從這兩個近似入手。

假設(shè)兩個數(shù)為，那么根據(jù)近似就有，可見要分兩種情況討論：第一種情況，那么近似指數(shù)的結(jié)果就是，因此近似程度就是

第二種情況，這時候近似指數(shù)的結(jié)果就是，因此近似程度就是

可以按部就班地證明，上面兩種情況的最小值，都是在時取到，其結(jié)果為8/9，所以最大的相對誤差為1/9（如果是除法變成減法，那么它的最大誤差是12.5%）。因為按部就班的證明有點繁瑣，我們這里就不重復(fù)了，而是直接用軟件畫出它的等高線圖，看出誤差最大的地方應(yīng)該是中心處：

作圖代碼：

import?numpy?as?np import?matplotlib.pyplot?as?pltx?=?np.arange(0,?1,?0.001) y?=?np.arange(0,?1,?0.001)X,?Y?=?np.meshgrid(x,?y) Z1?=?(1?+?X?+?Y)?/?(1?+?X?+?Y?+?X?*?Y) Z2?=?2?*?(X?+?Y)?/?(1?+?X?+?Y?+?X?*?Y) Z?=?(X?+?Y?<?1)?*?Z1?+?(X?+?Y?>=?1)?*?Z2 plt.figure(figsize=(7,?6)) contourf?=?plt.contourf(X,?Y,?Z) plt.contour(X,?Y,?Z) plt.colorbar(contourf) plt.show()

其實這個誤差本質(zhì)上取決于的近似程度，我們知道x是自然對數(shù)的一階泰勒展開式，而e=2.71828更加接近于3，所以如果計算機使用3進制的話，本算法會有更高的平均精度。事實上，確實有一些理論分析表明，對于計算機來說其實最理想是e進制，而3比2更接近于e，所以三進制計算機在不少方面會比二進制更優(yōu)，我國和前蘇聯(lián)都曾研究過三進制計算機，不過由于二進制實現(xiàn)起來更加容易，所以當(dāng)前還是二進制計算機的天下了。

搬到深度學(xué)習(xí)中

Mitchell近似的介紹就到這里了。讀者可能會困惑，這不該是計算機基礎(chǔ)和數(shù)據(jù)機構(gòu)那一塊的東西嗎？你研究它干嘛？還能在深度學(xué)習(xí)中有什么應(yīng)用嗎？

筆者學(xué)習(xí)它的原因有兩個：一是它確實很漂亮，值得學(xué)習(xí)；二是它還真的可以用到深度學(xué)習(xí)中。事實上，筆者是NeurIPS 2020的一篇論文《Deep Neural Network Training without Multiplications》^[2]中發(fā)現(xiàn)它的，該論文在“ImageNet+ResNet50”驗證了直接將神經(jīng)網(wǎng)絡(luò)中的乘法換成Mitchell近似的加法形式，準(zhǔn)確率只有輕微的下降，甚至可能不下降。

當(dāng)然，作者目前的實現(xiàn)只是驗證了這種替換在效果上是可接受的，在速度上其實是變慢了的。這是因為雖然從理論上來講乘法換成近似加法速度一定會有提升，但要實現(xiàn)這個提升需要從硬件底層進行優(yōu)化才行，所以作者是提供了未來深度學(xué)習(xí)硬件優(yōu)化的一個方向吧。此外，Mitchell近似在深度學(xué)習(xí)中的應(yīng)用分析，也不是第一次被討論了，直接Google就可以搜到兩篇，分別是《Efficient Mitchell’s Approximate Log Multipliers for Convolutional Neural Networks》^[3]和《Low-power implementation of Mitchell's approximate logarithmic multiplication for convolutional neural networks》^[4]。

可能讀者聯(lián)想到了華為之前提出的加法神經(jīng)網(wǎng)絡(luò)AdderNet，其目的確實有類似之處，但方法上其實差別很大。AdderNet是將神經(jīng)網(wǎng)絡(luò)的內(nèi)積換成了距離，從而去掉了乘法；這篇論文則是修改了乘法的實現(xiàn)，降低了乘法的計算量，已有的神經(jīng)網(wǎng)絡(luò)運算可能都可以保留下來。

也把新瓶裝舊酒

本文介紹了1962年發(fā)表的Mitchell近似算法，它是一種近似的對數(shù)和指數(shù)計算，基于此我們可以將乘法轉(zhuǎn)化為加法，并保持一定的精度?？瓷先ヒ呀?jīng)過時，但將這個算法“新瓶裝舊酒”一下，就成為了NeurIPS 2020中一篇論文了。

所以，你還發(fā)現(xiàn)了哪些可以裝到新瓶的“舊酒”呢？

后臺回復(fù)關(guān)鍵詞【入群】

加入賣萌屋NLP/IR/Rec與求職討論群

后臺回復(fù)關(guān)鍵詞【頂會】

獲取ACL、CIKM等各大頂會論文集！

?

[1] https://ieeexplore.ieee.org/document/5219391

[2] https://arxiv.org/abs/2012.03458

[3] https://ieeexplore.ieee.org/document/8532287

[4] https://ieeexplore.ieee.org/document/8297391

總結(jié)

以上是生活随笔為你收集整理的NeurIPS 2020 | 没有乘法的神经网络，照样起飞？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。