|
本文約3200字，建議閱讀9分鐘 本文介紹了第一原理中推導出卷積，并展示它的平移對稱性。標簽：卷積 TLDR：你有沒有想過卷積有什么特別之處？在這篇文章中，我從第一原理中推導出卷積，并展示它的平移對稱性。
某些事物實質(zhì)上是對其本質(zhì)的一種支持。(Claude Adrien Helvetius)在本科學習期間，我在以色列的Technion參與了電氣工程，令人感到震驚的一個重要的概念是，突如其來的卷積[1]。就像一粒沙子落入眼睛里，它擾亂了信號處理世界原本美麗的畫面。讓卷積從第一原則中產(chǎn)生而不只是假定，將會多么美好！正如我將在這篇文章中所展示的，這里的第一原則即平移不變性或?qū)ΨQ性。首先，從基本信號處理課程中教授的公式開始，定義兩個n維向量x和w的離散卷積[2]：
為了方便起見，假設所有的索引從零到n?1，并且是n模，自然而然地想到在圓上定義的向量，把上面的公式寫成矩陣向量乘法，得到了一個非常特殊的矩陣，稱之為循環(huán)（circulant）矩陣：
循環(huán)矩陣具有多對角結構，每個對角線上的元素具有相同的值。它可以通過將向量w的移位(模n)疊加在一起來生成[3]；因此，用C(W)來表示，指的是由向量w形成的循環(huán)矩陣。由于任何卷積x?w都可以等價地表示為循環(huán)矩陣C(W)x的乘法，所以將交替使用這兩個術語。在線性代數(shù)中學習的第一件事是矩陣乘法不滿足交換率，也就是說，一般情況下，AB≠BA。然而，循環(huán)矩陣是非常特殊的例外：循環(huán)矩陣滿足交換律，即：C(w)C(u)=C(u)C(w)。對于任何循環(huán)矩陣，或u和w的任何選擇，這都是正確的。同樣，可以說卷積是一個滿足交換率的運算，x?w=w?x。
選擇特定的w=[0,1,0…,0]生成一個特殊的循環(huán)矩陣，將向量向右移動一位。這個矩陣叫做（右）移位算子 [4]，用S表示。右移位算子的轉(zhuǎn)置是左移位算子。顯然，左移后右移（或反之）不起任何作用，這意味著S是正交矩陣：
循環(huán)矩陣滿足交換率，它足以表明移位的交換性（在[5]中引理3.1）：
當且僅當矩陣對移位滿足交換率時，稱矩陣是循環(huán)的。首先，“當且僅當”是指一種非常重要的性質(zhì)，即平移或移位等差[6]：卷積與移位的交換性意味著無論我們是先移動向量，然后卷積向量，還是先卷積然后移位，結果都是相同的。
其次，可以將卷積定義為移位等變線性運算：為了使移位符合交換率，矩陣必須具有循環(huán)結構。這正是我們所期望的，從平移對稱[7]的第一原理中導出卷積。而不是給出卷積的公式并證明其移位等差性質(zhì)，這通常是在信號處理書籍中來推導的，我們可以從移位等差的要求開始，得出卷積的公式，作為滿足它的唯一可能的線性運算。
信號處理課程中教授的另一個重要事實是卷積和傅里葉變換[8]之間的聯(lián)系。在這里，傅里葉變換從天而降，之后是它對角化卷積操作，在頻域中執(zhí)行兩個向量的卷積，作為它們的傅里葉變換的元素乘積。從來沒有人解釋過這些正弦和余弦來自哪里，以及它們有什么特別之處。為了弄清真相，回想一下線性代數(shù)中的一個事實：換句話說，滿足AB=BA的兩個矩陣將具有相同的特征向量（但可能是不同的特征值）[9]。由于所有循環(huán)矩陣都滿足交換率，可以選擇其中一個并計算其特征向量-上述定理保證了這些矩陣的特征向量也將是所有循環(huán)矩陣的特征向量。由于S是正交矩陣，所以我們期望它的特征向量也是正交的[10]。一個簡單的計算(見[5]第4.1節(jié))得出了這樣的結論在這一點上，可以有今天的第二個“啊哈”時刻：這便是sines和cosines的來源！它們是移位算子的特征向量；我將它們表示為矩陣Φ的列。注意特征向量是復雜的，所以在轉(zhuǎn)置Φ時需要采取復共軛。和Φ*進行的乘法（從左）稱為傅里葉變換，并通過Φ實現(xiàn)傅里葉逆變換。
由于所有循環(huán)矩陣都是對角的，所以它們也由傅里葉變換[11]對角化，只在特征值上有所不同。最后還要認識到這一點，其中C(w)的特征值為w的傅里葉變換。
現(xiàn)在可以從圖中導出卷積定理：卷積x?w可以通過計算原始坐標系統(tǒng)中x（有時稱為“空間域”卷積）的循環(huán)矩陣C(W)來實現(xiàn)，也可以通過傅里葉（在頻域）變換來實現(xiàn)：首先計算Φ*x的傅里葉變換，再將其和w [12]的傅里葉變換相乘之后，計算傅里葉逆變換。由于Φ具有特殊的冗余結構，Φ*x和Φx的乘積可以用快速傅里葉變換(FFT)算法的復雜度 計算。為什么要這樣來定義卷積？在這里我將重復Helvetius的名言：“對某些原則的了解很容易彌補對某些事實的缺乏”。對于卷積而言，它從第一原則的推導更加容易推廣到其他領域。在下一篇文章中，我將展示如何定義圖形上的卷積，以便生成圖形深度學習體系結構的關鍵架構塊。[1]Dominquez-Torres，卷積的歷史和起源提供了一個迷人卷積操作發(fā)展歷史。卷積首次出現(xiàn)在泰勒定理的推導中。J. B. D’Alembert進行了多方位的研究。優(yōu)先次序常常被錯誤地歸于P.-S. de Laplace, Mémoire sur l’inclinaison moyenne des orbites des comètes, sur la figure de la terre et sur les fonctions (1773)。雖然巴黎皇家科學院的備忘錄里沒有卷積的痕跡。但是，拉普拉斯在他后來寫于1778年并于1781年出版的關于概率的回憶錄中確實使用了卷積。早期卷積稱為résultante（法語“resultant”，最初由查爾斯·凱勒于1899年使用）、Composizione（意大利語“composition”，由維托·沃爾特拉于1910年使用）和faltung(字面意思是德語中的“folding”，由GustavDoetsch于1923年使用)；后者在20世紀初主導了德國文學。英文名稱卷積來自拉丁語con（“在一起”）和volvere（“卷起”），是德語Faltung的直譯，俄羅斯變體свертка也是如此。英語術語的第一次使用可以追溯到1934年AurelFriedrichWintner的論文；它后來被Doetsch（1937年），Gardner和Barnes（1942年)的權威著作在文獻中得到鞏固）。1910年Volterra首次使用了星象符號，不過形式不同。珀西·約翰·丹尼爾用了點符號。卷積的第一個現(xiàn)代表示法為f?g，這是兩者的結合，由Doetsch定義（1923）。[2] 從技術角度上講，我這里定義的是循環(huán)卷積。[3]注意，C(W)的行是向量w的轉(zhuǎn)置，導致卷積公式中出現(xiàn)反射，應將其與相關概念區(qū)分開來。注意邊界條件(C的元素在右上角和左下角)。[5] B.Bamieh，發(fā)現(xiàn)變換：循環(huán)矩陣、圓形卷積和離散傅里葉變換教程（2018）。ar Xiv：1805.05533提供了我在這篇文章中討論的派生的細節(jié)。[6]有些人經(jīng)?；煜蛔冃裕ㄔ诶≌Z中的意思是“不變”)和等變性(“以同樣的方式改變”），許多信號處理書籍提到我在這里討論的屬性為“移位不變性”。如果f(S x)=SF(X)，則函數(shù)是移位等變量。換句話說，不管是先移位，然后f還是反之亦然。不同的是，移位不變性是不受移位影響的性質(zhì)：函數(shù)f(S x)=f(X)是移位不變的。位移不變性是物理學中的一個基本概念（它通常以“平移對稱性”的名義出現(xiàn)），它指出物理定律不取決于空間中的位置。在經(jīng)典力學的變分公式中，動量守恒定律是根據(jù)諾瑟定理由位移不變性發(fā)展而來的。[7]等差的概念更普遍，可以用群體理論來擴展。該框架在T.Cohen和M.Welling，Group等變量卷積網(wǎng)絡（2016）中用到。Proc. ICML 將CNN的卷積層的移位等距擴展到更一般的操作，如旋轉(zhuǎn)。假設f：X→Y，其中X和Y是一些不同的空間，分別在X和Y的元素上定義了相應的組 運算，組等差表示為，其中。請注意不一定等于，因為輸出空間Y的結構和偶數(shù)維數(shù)可以不同于輸入X。在這篇文章中討論的標準卷積是一個特殊的情況，X=Y是n維向量的空間，是平移組，是移位算子。[8] 由于處理的是有限維向量，這里的術語“傅里葉變換”指的是離散傅立葉變換(DFT)。[9]更準確地說，聯(lián)合對角化意味著兩個交換矩陣具有相同的特征空間，就像在一般情況下，特征值可以具有非平凡的多重性一樣。由于在這里討論的所有的特征值都很簡單，所以可以討論一個共同的特征基。[10]然而，由于S是不對稱的，所以它沒有實特征值（對稱實矩陣有實特征值）。S的特征值恰好是一個復根。[11]當稱矩陣C被傅里葉變換“對角化”時，意思是矩陣Φ*CΦ是對角化的。由于傅里葉變換是一個正交矩陣(Φ*Φ=I)，它在幾何上充當坐標系統(tǒng)的變化，相當于n維旋轉(zhuǎn)。在這個坐標系統(tǒng)中，C的作用為元素乘積。[12]在信號處理中，通常在頻域設計濾波器，因此從未顯式計算w的傅里葉變換。Deriving convolution from first principles https:///deriving-convolution-from-first-principles-4ff124888028 陳之炎，北京交通大學通信與控制工程專業(yè)畢業(yè)，獲得工學碩士學位，歷任長城計算機軟件與系統(tǒng)公司工程師，大唐微電子公司工程師，現(xiàn)任北京吾譯超群科技有限公司技術支持。目前從事智能化翻譯教學系統(tǒng)的運營和維護，在人工智能深度學習和自然語言處理（NLP）方面積累有一定的經(jīng)驗。業(yè)余時間喜愛翻譯創(chuàng)作，翻譯作品主要有：IEC-ISO 7816、伊拉克石油工程項目、新財稅主義宣言等等，其中中譯英作品“新財稅主義宣言”在GLOBAL TIMES正式發(fā)表。能夠利用業(yè)余時間加入到THU 數(shù)據(jù)派平臺的翻譯志愿者小組，希望能和大家一起交流分享，共同進步。 工作內(nèi)容：需要一顆細致的心，將選取好的外文文章翻譯成流暢的中文。如果你是數(shù)據(jù)科學/統(tǒng)計學/計算機類的留學生，或在海外從事相關工作，或?qū)ψ约和庹Z水平有信心的朋友歡迎加入翻譯小組。
你能得到：定期的翻譯培訓提高志愿者的翻譯水平，提高對于數(shù)據(jù)科學前沿的認知，海外的朋友可以和國內(nèi)技術應用發(fā)展保持聯(lián)系，THU數(shù)據(jù)派產(chǎn)學研的背景為志愿者帶來好的發(fā)展機遇。 其他福利：來自于名企的數(shù)據(jù)科學工作者，北大清華以及海外等名校學生他們都將成為你在翻譯小組的伙伴。
|
