[ML] Convolution 합성곱의 정의와 FFT 고속푸리에 변환에 관하여

아래의 자료들을 모두 참고하여 작성하였다

https://m.blog.naver.com/ycpiglet/222556985523

[신호및시스템] 컨볼루션(Convolution)이란? - 시스템을 몰라도 입력과 임펄스 응답을 통해 출력(결

고속 푸리에 변환에 관한 부분은 아래의 영상을 참고하였다.

https://www.youtube.com/watch?v=KuXjwB4LzSA&t=1178s

Convolution이란

 

Convolution이란 합성곱이라고도 하다. 이는 선형 시불변(Linear Time-invarient system)시스템 h에 x라는 신호가 입력되어서 y가 나올때, x와  y의 관계이다.

Convoluton is just a System: 이 그람은 system을 대표하는 이미지이기도 하다.

이는 Convolution이 선형성(Addivitiy, Homogeneity)을 가지고, 시간에 따라 변화하지 않음을 알 수 있다.

 

Convolution을 우선 개념적으로 쉽게 그림으로 이해하면 다음과 같다. 

convolution은 하나의 값을 뒤집고 곱을 하는 것과 같다

즉, 하나의 값을 뒤집은 다음 이동시키면서 곱한 뒤의 그 sum을 기록하는 것이다. 

 

기호로는 아래와 같이 별표를 사용하면서 이는 Asterisk라고 한다. 

$$\large (f * g)(t) = \int_{-\infty}^{\infty} f(\tau)g(t-\tau)d\tau$$

연속 시스템에서 아래와 같이 정의되며, 이산시스템에서는 적분을 시그마로만 바꾸어주면 된다. 

convolution, x는 원형 데이터, h는 필터함수이다

 

식을 살펴보면, 우리는 h의 타우($\tau$)에 마이너스(-)가 붙어있음으로 으로 반전시켜져(reverse) 있음을 알 수 있다.

이는 시간상으로는 오른쪽에 위치하는 값이 먼저 나타내야하기 때문에 이를 반전시킨 것이다(0번째, 1번째, 순으로이 먼저 곱해져야한다 == 식은 왼쪽에서 오른쪽으로 이동하기에, 오른쪽에 위치한 값이 먼저 만난다, 그럼으로 반전이 필요하다 )

또한 t만큼 이동(shift)되어있음 또한 확인 가능하다. 이때 t는 h의 데이터의 수일 것이다. 

delay에 관한 부분

 

이후 $\tau$를 이동시키면서 변형된(reversed & shifted) h함수와 x함수의 곱한 결과를 하나씩 기록한다. 어떨때는 두 함수가 겹치게 되고, 또 어떨때는 겹치는게 없어서 합쳐도 0이 되기도 한다. 

이것이 convolution이다. 

 

 

합성곱 식을 살펴보면 두 함수 $f$, $g$가 있는데(f = x, g = h)

일반적으로 사용될때 함수 $f$는 우리가 가지고 있는 본래의 신호, 행렬, 이미지 등이 원본 데이터이고,

이때 함수 $g$는 필터, 가중치 같은걸로 표현된다.

이 두 함수를 합성곱 하면? 주어진 신호, 행렬, 이미지를 우리가 원하는 함수로 변형시킬 수 있다. 

즉, 함수 $f$  주어졌을때 우리가 원하는 목적에 따라 함수 $g$를 선정하여 분해, 변환, 필터링 할 수 있는 것이 Convolution인 것이다. 

 

FFT( Fast Fourier Transform)와 Convolution

Convolution 계산은 기본적으로($O(N^2)$)을  빠르게 하는 방법에는 FFT 알고리즘을 이용한 방법($O(NlogN)$)이 있다.

 

우선 우리는 합성곱 계산을 아래 그림과 같은 두 다항식 간의 계수의 연산으로 볼 수 있다. 

즉, 이런 관점을 통해서 우리는 특정 두 다항식의 곱으로 구해지는 새로운 다항식의 계수가 합성곱의 결과와 같음을 알 수 있다. 

이를 이용해서 특정 점에서 f(x), g(x)의 값을 알아낸다면, 이것의 곱이 새로운 다항식에 특정 점에서의 함수값과 같고, 

이것이 다항식의 계수의 개수만큼(N) 존재한다면, 우리가 다항식의 계수를 알아낼 수 있음을 의미한다. 

이때, 당연히 계수의 숫자만큼 값을 구한뒤 이 둘을 곱해야한다면 $O(N^2)$이라는 계산복잡도는 변하지 않느다. 

이를 더 적은양으로 계산하기 위해서는 특정 제곱마다 값이 반복되는 특별한 복수수 집합을 이용하는 방법이 필요하다. 

이것이 Fourier Transform이다($O(NlogN)$)

FFT는 양방향으로 작동함으로 결과값에서 계수로, 계수에서 결과값으로 이동이 모두 가능하다는 특징을 이용해 최종적으로 아래와 같이 계산 가능하다.

1. 합성곱을 할 두 배열에 해당하는 값을 각각 FFT해준자. 

2. 이후 벡터를 행렬곱한다. 

3. Inverse FFT로 계수를 구한다.

 

FFT에 관한 자세한 내용은 다음에 다른 글에서 다루려고한다.