1 卷積

我們先來看一下卷積的定義，卷積是指通過兩個函數 f?和 g?生成第三個函數的一種數學算子，表征函數 f?與經過翻轉和平移的 g?的乘積函數所圍成的曲邊梯形的面積。

對于連續卷積來說，可以定義為：

對于離散卷積來說，可以定義為：

但無論是連續還是離散的卷積，他們都有一個特點，就是f和g中的下標之和是一個定值

1.1 連續卷積舉例——信號分析

如下圖所示，輸入信號是 f(t) ，是隨時間變化的。

系統響應函數是 g(t) ，是隨時間指數下降的，它的物理意義是說：如果在 t=0 的時刻有一個輸入，那么隨著時間的流逝，這個輸入將不斷衰減。

換言之，到了 t=T時刻，原來在 t=0 時刻的輸入f(0)的值將衰減為f(0)g(T)。

??考慮到信號是連續輸入的，也就是說，每個時刻都有新的信號進來。

所以，某一時刻最終輸出的是所有之前輸入信號的累積效果。

如下圖所示，在T=10時刻，輸出結果跟圖中帶標記的區域整體有關。

其中，f(10)因為是剛輸入的，所以其輸出結果應該是f(10)g(0)，而時刻t=9的輸入f(9)，只經過了1個時間單位的衰減，所以產生的輸出應該是 f(9)g(1)，如此類推，即圖中虛線所描述的關系。

這些對應點相乘然后累加，就是T=10時刻的輸出信號值，這個結果也是f和g兩個函數在T=10時刻的卷積值。

??顯然，上面的對應關系看上去比較難看，是擰著的，所以，我們把g函數對折一下，變成了g(-t)，這樣就好看一些了。

這就是為什么卷積要“卷”，要翻轉的原因，這是從它的物理意義中給出的。

然后我們根據定義，把g(-t)向右移動T個單位

我們這算的是10這個時刻的卷積結果，如果要算其他位置的，就是把g(-t)曲線再沿著x軸左右滑動就可以了

1.2?從另一個角度來考慮f和g的離散卷積。

我們可以想成，固定f的位置（f的位置固定在哪里，取決于f和g下標之和的數值），將g翻轉，然后對翻轉后的g（我們稱之為g’）進行滑動。

g‘滑動到不同的位置，會和f包圍出不同的區域。對這些區域里面的元素兩兩乘積，然后累加，就得到了卷積函數的值。

1. 3 二維離散卷積

CNN中的卷積核已經是“扭過”之后的了，所以CNN中直接是對應位置元素相乘再求和。

1.4?卷積等價于多項式相乘

?

?

2 卷積定理

在適當條件下，兩個信號的卷積的傅立葉變換是他們的傅立葉變換的點積。

換句話說，一個域（如時域）的卷積等于另一個域（如頻域）的點乘：

這里F(f)表示函數f的傅里葉變換

2.1 卷積原理的一個用處

利用卷積定理，我們可以簡化卷積的運算量。

對于一個長度為 n 的序列，按照卷積的定義來計算則需要做 2n-1 組對位乘法，即時間復雜度為 O(n^2)?.

2n-1我們可以這樣去理解:

假設進行卷積的兩個序列是f和g，我們固定f的位置，并令f的左端為0，右端為n-1.

卷積的意思是g從左向右滑動，和f包圍起來的面積

所以和固定的f有相交區域的g一共有 (n-1)-[-(n-1)]+1=2n-1個

每一個可能的g和f都需要進行O(n)次運算。

所以時間復雜度為O(n^2)

而利用傅立葉變換后，只需要計算一組對位乘法。而

離散傅立葉變換有快速的算法（快速傅立葉變換），所以總的計算復雜度為O(nlogn)??。

參考資料：

【GNN】萬字長文帶你入門 GCN - 知乎 (zhihu.com)

https://www.zhihu.com/question/22298352/answer/637156871

總結

以上是生活随笔為你收集整理的GNN笔记：卷积的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。