brunch

You can make anything
by writing

C.S.Lewis

by cojette Nov 03. 2015

베이즈 이론이 푸리에 정리를 만났을 때

조제프 푸리에(Joseph Fourier)는 토마스 베이즈(Thomas Bayes)를 한 번도 만난 적이 없다. 푸리에는 베이즈가 사망한 지 7년 후인 1768년에 태어났다. 하지만 최근 베이즈 필터와 푸리에 변환 간의 어떤 연결고리가 있지 않을까 하는 생각이 들어, 관련 내용을 찾아보게 되었다.

"베이즈 필터"라는 건, 베이지안 분류기를 사용해서 스팸 필터링을 하는 것이 아니라, 로보틱스나 다른 분야에서 움직이는 로봇의 위치를 구하는 것처럼 시간에 따라 변화하는 시스템 상태를 추정하는 데에 사용되는 재귀 베이지안 추정에 더 가깝다. 독서 모임에서 Roger Labbes의 'Kalman and Bayesian Filters in Python'라는 책을 읽다가 이 주제에 대해서 관심을 갖게 되었다.

본 글의 파이썬 코드는 이 IPython notebook에 있다. 수학 공식 때문에 머리가 아플 것 같다면, 바로 이 코드로 넘어가도 무방하다.

베이즈 필터

베이즈 필터는 로봇의 초기 위치에 대한 확률적 믿음을 나타내는 분포에서부터 시작한다. 이후 이 분포를 기반으로 예측하고 이 값을 갱신하는 과정을 거친다.

예측 단계에서는 시스템의 물리적 모델과 모델의 현재 상태를 사용해서 미래의 상태를 예측한다. 예를 들어, 현재 로봇의 위치와 속도를 알고 있다면, 다음 시간 단위가 지난 후의 이 로봇의 위치를 예측할 수 있다.

갱신 단계에서는 측정값과 측정 오차 모델을 통해 이 시스템의 상태에 대한 믿음을 갱신한다. 예를 들어, GPS를 사용해서 로봇의 위치를 측정한다면, 측정값에 어느 정도 오차가 섞일 것이고, 이런 오차의 분포를 정의할 수 있을 것이다.

갱신 단계에서 베이즈 이론을 사용하면, 계산 단계에 사전 분포에 우도 분포를 곱한 후 재정규화 과정이 들어간다.

예측 단계에서는 위치와 속도 등에 랜덤 변수를 추가하므로, 계산 시에는 이 두 분포의 컨볼루션(convolution)값이 들어가게 된다.

컨볼루션 정리

컨볼루션 정리는 예측 단계와 갱신 단계 간의 대칭 형태를 만들어, 알고리즘을 보다 효율적으로 만들 수 있도록 한다. 컨볼루션 정리는 Think DSP의 8장에 정리해 놓았다. 이산 신호에 있어서 이 공식은 다음과 같다.

DFT(f ∗ g) = DFT(f) · DFT(g)

즉, 컨볼루션의 이산 푸리에 변환(discrete Fourier transform, DFT) 값을 구하고 싶다면, 신호별로 DFT를 각각 구한 후 결과값들을 곱하면 된다. 시간 차원의 컨볼루션은 빈도 차원의 곱에 대응한다. 또한 역으로, 시간 차원으 곱은 빈도 차원의 컨볼루션에 대응한다.

베이즈 필터 측면에서, 우리가 현재 다루고 있는 것은 시계열 신호가 아닌 공간 분포지만, 컨볼루션 이론에 따르면, "시간 차원" 대신, "공간 차원"을 다루고 있는 것이고, DFT 대신 특성 함수(characteristic function)을 사용하는 것이다.

특성 함수

여기서는 특성 함수와 푸리에 변환이 동일하다는 것을 살펴볼 것이다. 이미 아는 내용이라면, 다음 부분으로 넘어가도 된다.

통계를 배웠다면, 다음과 같은 특성 함수 정의를 본 적이 있을 수도 있다.

X는 랜덤 변수고, t는 (시간, 공간 등에 대한) 빈도에 대응하는 변환 변수며, E는 기대값 상수다.

신호 시스템을 다루는 사람은, 아래의 푸리에 변환 정의를 보았을 것이다.

f 는 함수고,

는 f의 푸리에 변환 함수며,

는 빈도에 대응하는 변환 상수다.

위의 두 정의는 다르게 생겼지만, 기대값 상수를 풀어 쓰면 다음과 같다.

여기서 p(x)는 X의 확률 밀도 함수고, P(t)는 푸리에 변환이다. 여기서 특성 함수와 푸리에 변환 간의 유일한 차이는 지수 표기법 뿐인데, 이는 표기법 선택의 문제다. (P(t) 위에 그려진 바는 복소수 켤레값을 나타내며, 이는 지수 표기법 상 사용된 것이다. )

특성 함수의 전체 모양을 다시 살펴보자: 두 개의 랜덤 변수를 추가하려면 두 분포를 컨볼루션해야 한다. 컨볼루션 이론에 따르자면, 공간 도메인에서 컨볼루션은 빈도 도메인의 곱에 대응하므로, 이런 식으로 랜덤 변수를 추가할 수 있는 것이다.

두 분포의 특성 함수를 계산하자. 특성 함수의 원소 별로 곱하자. 이 합의 분포를 계산한 후 그 값을 역변환한다.

베이즈로 돌아와서

이제 예측 단계와 갱신 단계 간의 대칭 관계를 보다 명확하게 볼 수 있을 것이다.

예측 단계는 빈도 도메인의 곱에 대응하는 공간 도메인의 컨볼루션을 포함한다. 갱신 단계에서는 공간 도메인의 곱을 포함하는데, 이는 빈도 도메인의 컨볼루션에 대응한다.

적어도 나는 이 내용이 매우 흥미로웠고, 유용하게 사용될 것이라고도 생각한다. 이를 활용해서 고속 푸리에 변환(Fast Fourier Transform, FFT) 기반의 효율적인 알고리즘을 사용할 수 있다.기본 컨볼루션을 간단하게 구현한 것은 N이 분포 내 값이라고 할 때, N²에 비례하는 시간이 소모된다. FFT를 사용하면 이를 N log N까지 감소시킬 수 있다.

이 알고리즘을 사용할 때의, 전체 예측-갱신 단계는 다음과 같다.

위치와 속도 분포의 FFT를 계산한다. 이를 원소까리 곱하면, 컨볼루션된 분포의 특성 함수가 도출된다.

예측 분포인 결과의 역 FFT를 곱하자. 우도를 재정규화해서 만들어진 예측 분포를 여기에 곱하자.

1단계와 3단계는 N log N이고, 2단계와 4단계는 선형 증가한다.

이 알고리즘은 이 IPython notebook에서 확인할 수 있다.

베이즈 필터의 베이지안적 내용에 대해서 더 자세히 보고 싶다면, Think Bayes의 6장을 읽어보자. 컨볼루션 이론에 대해 더 알고 싶다면, Think DSP의 8장을 보자. 임의 변수를 추가하는 것에 대해 더 알고 싶다면, Think Stat의 6장을 보도록 하자.