본 문서에서는 KDD 2021 학회에서 발표된 "Fast and Accurate Partial Fourier Transform for Time Series Data" 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다.
- Title: Fast and Accurate Partial Fourier Transform for Time Series Data
- Authors: Yong-chan Park, Jun-Gi Jang, and U Kang
- Conference: The 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2021
Fourier Transform
고속 푸리에 변환(Fast Fourier Transform, FFT)은 20세기 인류가 발명한 가장 중요한 알고리즘이라고 불릴 만큼 막대한 영향력과 광범위한 응용 분야를 가지고 있는 알고리즘입니다. 실제로 FFT는 MP3, JPEG, MPEG 등의 디지털 데이터를 탄생시킴으로써 오늘날과 같은 디지털 시대의 문을 열어준 알고리즘이라 할 수 있습니다. 인공지능의 시대로 접어들고 있는 21세기에 FFT의 중요성은 더욱 더 커지고 있다고 말할 수 있는데, 앞서 언급한 디지털 데이터의 처리를 비롯하여 데이터 이상 감지, 표현 학습, 합성 곱 신경망 등 수많은 인공지능 분야에 FFT가 널리 사용되고 있기 때문입니다.
구체적으로 푸리에 변환은 시간 또는 공간 영역의 데이터를 주파수 영역으로 변환하는 수학적 연산입니다. 푸리에 변환이 중요한 이유는, 대부분의 실제 세계 데이터가 주파수 영역 내에서 강한 에너지 응축(energy compaction) 현상을 보이기 때문입니다. 다시 말해, 주어진 데이터의 푸리에 계수는 극히 일부분에서만 유의미한 값을 가지며, 나머지 부분에서는 값이 매우 작다는 의미입니다 (그림 1 참조). 그런데, 기존의 FFT는 실제 세계 데이터가 갖는 이러한 성질을 전혀 반영하지 못하는 치명적인 단점을 가지고 있습니다. 즉, FFT는 데이터의 푸리에 계수를 “전부” 계산하는 일만 가능하며, 필요한 부분만 효율적으로 계산하는 일이 불가능합니다. 결과적으로 FFT는 필요하지 않은 (값이 매우 작은) 푸리에 계수를 불가피하게 계산한 뒤, 나중에 이를 폐기하는 비효율적인 방식으로 작동합니다.
 |
| 그림 1. 원본 이미지(좌측)와 그 푸리에 변환(우측). 우측 이미지에서 어두운 부분은 값이 매우 작은 영역임. |
Partial Fourier Transform (PFT)
본 논문에서는 필요한 부분의 푸리에 계수만을 신속하고 정확히 계산할 수 있는 효율적인 알고리즘인 Partial Fourier Transform (PFT)을 제안합니다. 이 알고리즘의 핵심 아이디어는 푸리에 변환을 구성하는 다수의 삼각함수들 중 상대적으로 진동성이 작은 것들을 추출해 그들을 다항함수의 형태로 근사하는 것입니다. 이를 통해 삼각함수의 수를 감소시킴으로써 알고리즘의 연산 복잡도를 획기적으로 낮추는 데에 성공하였습니다. 본 논문이 제안하는 구체적인 기술적 수단 3가지는 다음과 같습니다.
(1) 회전 인자(twiddle factor) 근사
본 논문에서 제안하는 알고리즘의 핵심 수단 중 하나는 이산 푸리에 변환(Discrete Fourier Transform, DFT)이 포함하는 다수의 회전 인자들 중 상대적으로 진동성이 작은 것들만을 추출해 이들을 다항함수의 형태로 근사하는 것입니다. 이를 통해 회전 인자들의 수를 감소시킴으로써 알고리즘 전반의 연산량을 획기적으로 낮추는 것이 가능합니다. 먼저 진동성이 작은 회전 인자를 추출하기 위해 쿨리-튜키(Cooley-Tukey) 알고리즘에 기반하여 DFT를 재귀적인 sub-DFT들의 합으로 분리하는 방식을 이용하고, 다항함수 근사를 위해 최적근사(best approximation) 알고리즘을 이용합니다.
(2) 기저지수함수(base exponential function) 도입
회전 인자들을 다항함수로 근사하는 과정에 의한 연산량의 증가를 억제하기 위해 기저지수함수의 개념을 도입하고, 이를 매개로 입력 데이터와 회전 인자를 분리시켜 사전 계산(precomputation)을 가능하게 합니다. 이러한 방식을 이용하면 데이터가 들어오기 이전에 미리 필요한 계산의 일부를 완료할 수 있으므로, 알고리즘의 실행 시간을 상당히 단축시키는 효과를 얻을 수 있습니다.
(3) 연산 재배열과 분해
푸리에 변환 과정에서 나타나는 다수의 연산들을 재배열하고 그에 맞추어 인자들을 분해합니다. 전반적으로 본 논문의 알고리즘은 그림 2와 같이 각각 행렬곱과 내적으로 구성된 전, 후처리 과정 가운데에 여러 개의 소규모 FFT가 포함되는 구조를 가지고 있는데, 이는 계산의 최종 결과를 변화시키지 않으면서 총 연산량을 최소화할 수 있는 형태로 설계된 것입니다.
 |
| 그림 2. PFT의 개요도 |
Experiments
본 실험에서는 제안하는 PFT가 기존 푸리에 변환 알고리즘들에 비해 가장 신속하고 정확하게 작동하는 것을 확인합니다. 또한, 제안하는 방법을 이용하여 실제 세계 데이터에 대한 이상 탐지 분석 결과를 보여줍니다. 그림 3은 제안하는 방법이 기존 최첨단 알고리즘과 비교했을 때 동일 정확도 기준 최대 20배의 속도 향상을 달성하는 것을 보여줍니다. 보다 자세한 실험 결과들은 논문에서 확인할 수 있습니다.
 |
| 그림 3. PFT와 경쟁 기법의 실행시간 비교 |
본 논문에서는 PFT를 이용하여 시계열 데이터에 대한 이상 탐지를 수행합니다. 그림 4는 PFT를 이용하여 페이스북, 아마존, 넷플릭스, 구글 4개 기업의 주가 데이터에 대해 이상 탐지를 실행한 결과입니다. 결과에서 나타난 것과 같이 탐지된 모든 이상 지점들이 해당 시점에 발생했던 실제 사건과 밀접하게 관련되어 있는 것을 확인할 수 있습니다. 이러한 결과는 제안하는 방법이 주어진 시계열 데이터에 대해 유의미한 이상 탐지를 성공적으로 수행할 수 있음을 보여줍니다. 자세한 내용은 논문을 참고하시기 바랍니다.
 |
| 그림 4. PFT를 이용한 페이스북, 아마존, 넷플릭스, 구글의 주가 데이터 이상 탐지 결과 |
Conclusion
본 문서에서는 KDD'21에 발표된 "Fast and Accurate Partial Fourier Transform for Time Series Data" 논문을 소개하였습니다. 해당 논문은 주어진 데이터의 푸리에 계수의 일부를 신속하고 정확하게 계산할 수 있는 효율적인 알고리즘인 PFT를 제안합니다. PFT는 기존 최첨단 알고리즘과 비교했을 때 동일 정확도 기준 최대 20배에 달하는 속도 향상을 이루었으며, 소리, 기후, 주식 가격 등 다양한 실제 세계의 시계열 데이터에 대해서 일관성 있는 성능 향상을 이루어 냈습니다. 본 논문은 데이터 분석에 널리 활용되는 푸리에 변환을 효율적으로 수행하는 방법을 제안하였습니다. 제안된 방법을 통하여 시계열 분석, 데이터 압축, 의학 영상 처리, 이상 탐지 등 광범위한 응용 분야의 효율성을 비약적으로 향상시킬 수 있을 것으로 기대합니다. 자세한 내용은 논문에서 확인할 수 있습니다.