Chapter 4-1. Convolutional Layers, Spectral methods
( 참고 : https://www.youtube.com/watch?v=JtDgmmQ60x8&list=PLGMXrbDNfqTzqxB1IGgimuhtfAhGd8lHF )
이번 장은 코드도 코드지만, 이론에 보다 focus 할 것이다.
1) Convolution의 수식적 정의
CNN에서 자주 사용하던 convolution의 수식적 정의는 아래와 같다.
\(\begin{align*} c[n] = (v * w)[n] = \sum_{m=0}^{N-1} v[m] \cdot w[n-m] \end{align*}\).
2) Fourier Transform 소개
특정 값에, Fourier Transform 과 Inverse Fourier Transform을 적용하면 그 자신이 된다.
( \(\mathcal F: \mathbb{R}^N \to \mathbb{R}^N\) )
\(\begin{align*} \mathcal F^{-1}(\mathcal F (v)) &= v\\ \mathcal F(v * w) &= \mathcal F(v) \cdot \mathcal F(w) \end{align*}\).
이는 곧, 우리가 2개의 서로 다른 값에 각각 Fourier Transform을 수행한 뒤, 이 둘에 대해서 연산을 진행한 이후에, 다시 Inverse Foureir Transform 을 진행해도 값이 동일함을 알 수 있다.
Python Example
import numpy as np
import scipy.fft import fft, ifft
N = 10
v, w = np.random.rand(N), np.random.rand(N)
A = fft(v)
B = ifft(A)
C = np.abs(ifft(fft(v) * fft(w)))
print(v)
print(A)
print(B)
print(C)
[0.96137475 0.28925552 0.95834293 0.08716554 0.40231697 0.37275202
0.32847569 0.9849826 0.61934398 0.29114949]
[ 5.29515949-0.j 0.62317664+0.48917804j -0.40445244-0.65495372j
0.22610561-0.396891j 1.09218964+1.22079799j 1.24454914-0.j
1.09218964-1.22079799j 0.22610561+0.396891j -0.40445244+0.65495372j
0.62317664-0.48917804j]
[0.96137475+0.j 0.28925552+0.j 0.95834293+0.j 0.08716554+0.j
0.40231697+0.j 0.37275202+0.j 0.32847569+0.j 0.9849826 +0.j
0.61934398+0.j 0.29114949+0.j]
[2.62558265 3.55050025 3.17318954 2.95838157 3.28156011 3.04980492
3.43916684 3.1491326 2.69604121 3.47324529]
3) Fourier Transform 정의
FT : \(\mathcal F(v) = U\cdot v\)
iFT : \(\mathcal F^{-1}(v) = \frac{1}{N}\ U^H \cdot v\)
위에서 사용된 \(U\) 행렬은 아래와 같다.
\(\begin{align*} \\U = \begin{bmatrix} u_0(0) & u_1(0) & \dots & u_{N-1}(0)\\ u_0(1) & u_1(1) & \dots & u_{N-1}(1)\\ \vdots & \vdots& & \vdots\\ u_0(N-1) & u_1(N-1) & \dots & u_{N-1}(N-1)\\ \end{bmatrix} \end{align*}\),
위의 각 행렬들의 원소값은, 아래와 같이 cos x i*sin 형태로 이루어져있다.
\(u_n(x):= \cos\left(2 \pi \frac{n}{N} x\right) - i \sin\left(2 \pi \frac{n}{N} x\right)\).
4) Connection with Laplacian
위의 Fourier Transform 식과, Laplacian matrix는 아주 밀접한 관련이 있다.
( 복습 : graph G의 Laplacian matrix : \(L=D-A\) )
위 3)의 \(u_n\)은 ( = Fourier Trasform matrix의 칼럼들 )은, Laplacian matrix의 eigen vector이다.
Summary
\(v * w = U^H ((U w) \odot (U v))\).
\(g_w=\mbox{diag}(U w)\) 로 놓을 경우… \(v * w = U^H g_w U w\)
5) Convolution on GRAPHS
아래와 같은 순서로 소개를 할 것이다.
- Graph Laplacian
- Spectrum
- Fourier Transform
- Convolution on graph
(1) Graph Laplacian
- adjacency matrix : \(A\)
-
degree matrix : \(D\)
- LAPLACIAN : \(L=D-A\)
- NORMALIZED LAPLACIAN : \(L = I - D^{-1/2} A D^{-1/2}\).
(2) Graph Spectrum
spectral decomposition of \(L\) : \(L = U \Lambda U^T\)
(3) Fourier Transform
FT & iFT
\(\mathcal F (v) = U \cdot v, \;\;\mathcal F^{-1} (v) = U^T \cdot v\\\).
(4) Convolution on graph
\(v * w = U ((U^T w) \odot (U^T v) )\).
\(g_w=\mbox{diag}(U w)\) 로 놓을 경우… \(v * w = U^H g_w U w\)
6) Pytorch Geometric을 사용한 Spectral-convolutional layers
문제점 : spectrum을 계산하는 것은 computationally expensive하다
목표 : MESSAGE PASSING 을 구현하자!
이에 대해서는, 다음포스트에서 보다 자세히 알아볼 것이다.