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

아래와 같은 순서로 소개를 할 것이다.

  1. Graph Laplacian
  2. Spectrum
  3. Fourier Transform
  4. 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 을 구현하자!

이에 대해서는, 다음포스트에서 보다 자세히 알아볼 것이다.

Categories:

Updated: