Fast Multidimensional Partial Fourier Transform with Automatic Hyperparameter Selection

Posted by 날짜:

 본 문서에서는 KDD 2024 학회에 발표될 "Fast Multidimensional Partial Fourier Transform with Automatic Hyperparameter Selection" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.

  • Title : Fast Multidimensional Partial Fourier Transform with Automatic Hyperparameter Selection
  • Authors: Yong-chan Park, Jongjin Kim, and U Kang
  • Conference: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) 2024

Partial Fourier Transform

이산 푸리에 변환(Discrete Fourier Transform, DFT)은 이상 탐지, 잠재 패턴 추출, 이미지 처리 등 많은 데이터 마이닝 작업에서 중요한 알고리즘입니다. 최근에는 데이터의 에너지 응집 특성을 활용하여 일부 푸리에 계수만 효율적으로 계산하는 것에 대한 관심이 높아지고 있습니다. 시계열, 이미지, 비디오와 같은 대부분의 실제 데이터는 주파수 도메인에서 매우 응집된 형태로 표현됩니다. 예를 들어, 그림 1은 ImageNet의 이미지의 푸리에 계수를 시각화한 것으로, 대부분의 계수가 0이며 일부 저주파 영역에서만 계수가 존재하는 것을 보여줍니다. 이는 불필요한 계수의 계산을 생략하고, non-zero 계수에만 집중함으로써 상당한 계산상의 이점을 얻을 수 있음을 의미합니다.

그림 1. 입력 이미지와 해당 푸리에 맵을 로그 진폭으로 표시한 예시.
중앙 근처의 일부 저주파 영역을 제외하면, 푸리에 계수는 대부분 0에 가깝습니다.


그러나 Goertzel Algorithm, Subband DFT, Pruned FFT 등 기존의 부분 푸리에 변환 방법들은 효율성이 낮다는 문제가 있습니다. 고전적인 빠른 푸리에 변환(FFT)이 모든 계수를 계산하는 것에 비해, 이러한 방법들은 출력 크기가 입력 크기보다 훨씬 작을 때에만 FFT를 능가하여 실제로 사용하기에는 제한적입니다.

최근의 한 연구는 부분 푸리에 변환을 위한 사전 계산 기법을 활용한 PFT를 제안하며, 이를 통해 실용적인 응용에서 FFT를 대체할 수 있을 정도로 성능을 향상시켰습니다. 그러나 PFT의 효과성은 두 가지 주요 한계에 의해 제약을 받습니다. 첫째, PFT는 1차원 데이터에 특화되어 있어 다차원 데이터에는 효율적으로 작동하지 않습니다. 다차원 데이터의 각 축에 PFT를 적용할 수는 있지만, 이 접근 방식은 다차원 데이터를 위해 설계된 알고리즘보다 효율성이 낮다는 것이 이론적/실험적으로 관찰됩니다. 둘째, PFT는 입력 또는 출력 크기가 변경될 때마다 수동으로 하이퍼파라미터 튜닝이 필요합니다. 이는 특히 데이터가 다차원일 경우 하이퍼파라미터 탐색 공간이 커지므로 추가 비용이 발생하게 됩니다.


Proposed Method

본 논문에서는 수동 하이퍼파라미터 검색이 필요 없는 빠르고 정확한 다차원 부분 푸리에 변환 알고리즘인 Auto-MPFT를 제안합니다. 주요 문제점과 이에 대한 접근 방식은 다음과 같습니다.
  • 다차원 DFT에서 부분 푸리에 계수의 효율적인 계산: 저자는 Cooley-Tukey 알고리즘을 수정하여 다차원 DFT에서 매끄러운 삼각함수 집합을 찾습니다. 그런 다음 체비쇼프(Chebyshev) 다항식을 사용하여 삼각함수를 근사합니다. 이 기법은 부분 푸리에 계수의 계산을 행렬 곱셈과 입력의 작은 서브 블록에 대한 다차원 FFT로 분해하여 시간 비용을 크게 줄입니다.
  • Auto-MPFT의 최적 하이퍼파라미터를 자동으로 탐색: 최적의 하이퍼파라미터는 Auto-MPFT의 시간 복잡성을 최소화하는 값입니다. 하지만 이러한 최적화 문제의 제약 함수는 명시적인 형태로 표현할 수 없음이 확인되었습니다. 저자는 이 문제를 해결하기 위해 제약 함수를 체비쇼프 근사법을 통해 재구성하고, 비제약 볼록 최적화 문제를 도출합니다. 이 접근 방식은 뉴턴법(Newton's Method)과 같은 잘 확립된 수치 해석 방법을 사용하여 최적의 하이퍼파라미터를 효율적으로 찾을 수 있게 합니다.

체비쇼프 근사 (Chebyshev Approximation) 

부분 푸리에 계수의 효율적인 계산을 위한 Auto-MPFT의 주요 아이디어는 다음과 같습니다: (1) 구성 단계에서 Auto-MPFT는 DFT에서 삼각함수의 다변수 체비쇼프 다항식 근사를 통한 사전 계산 기법을 사용합니다. 또한, 최적의 하이퍼파라미터를 자동으로 찾고 근사 다항식의 차수를 계산합니다. (2) 계산 단계에서 Auto-MPFT는 다차원 데이터 타입에 최적화된 배치 행렬 곱셈 및 FFT 알고리즘을 활용하여, 기존 방법보다 이론적 및 실험적으로 우수한 결과를 도출합니다.


자동화된 하이퍼파라미터 선택 (Automatic Hyperparameter Selection)

Auto-MPFT의 하이퍼파라미터를 자동적으로 선택하기 위한 주요 아이디어는 제약 함수를 신중하게 근사하여 Auto-MPFT의 원래 최적화 문제를 비제약 볼록 최적화 문제로 변환하는 것입니다. 목적 함수의 볼록성은 뉴턴법 등의 2차 최적화 기법의 수렴을 보장합니다. 목적 함수를 최소화하는 최적의 해를 찾은 후, 본 논문이 제안한 특정 함수를 사용하여 최적 하이퍼파라미터를 근사하고, 수동 선택 과정을 대체합니다.

Experiments

본 실험에서는 제안하는 Auto-MPFT가 기존 푸리에 변환 알고리즘들에 비해 가장 신속하고 정확하게 작동하는 것을 확인합니다. 그림 2는 제안 기법이 기존 최첨단 알고리즘과 비교했을 때 동일 정확도 기준 최대 7.6배의 속도 향상을 달성하는 것을 보여줍니다. 보다 자세한 실험 결과들은 논문에서 확인할 수 있습니다.
그림 2. Auto-MPFT와 경쟁 기법의 실행 시간 비교

본 논문에서는 또한 하이퍼파라미터 최적화 알고리즘의 정확도와 속도를 측정합니다. 먼저 표 1은 최적화 알고리즘의 정확도를 측정한 결과입니다. 괄호 없이 표시된 항목은 제안 기법의 추정치 𝑝ˆ이 실제 값인 𝑝와 같음을 나타내고, 괄호가 있는 항목은 두 값을 𝑝ˆ(𝑝) 형식으로 보여줍니다. Auto-MPFT는 대부분의 경우에서 최적값을 성공적으로 감지하는 것을 확인할 수 있습니다. 표 2는 최적화 알고리즘의 실행 시간을 측정한 결과입니다. 제안 기법이 수동 탐색 방식보다 월등히 빠른 속도를 보이는 것을 알 수 있습니다.

표 1. 하이퍼파라미터 최적화 알고리즘의 정확도 측정

표 2. 하이퍼파라미터 최적화 알고리즘의 실행 시간 측정

Conclusion

본 문서에서는 KDD 2024에 발표될 "Fast Multidimensional Partial Fourier Transform with Automatic Hyperparameter Selection" 논문을 소개하였습니다. 해당 논문은 다차원 데이터의 푸리에 계수의 일부를 신속하고 정확하게 계산할 수 있는 효율적인 알고리즘인 Auto-PFT를 제안합니다. Auto-MPFT는 기존 최첨단 알고리즘과 비교했을 때 동일 정확도 기준 최대 7.6배에 달하는 속도 향상을 이루었으며, 다양한 실제 세계의 데이터에 대해서 일관성 있는 성능 향상을 이루어 냈습니다. 
본 논문은 데이터 분석에 널리 활용되는 푸리에 변환을 효율적으로 수행하는 방법을 제안하였습니다. 제안된 방법을 통하여 이상 탐지, 이미지 처리, 의학 영상 분석 등 광범위한 응용 분야의 효율성을 향상시킬 수 있을 것으로 기대합니다. 본 논문에 대한 자세한 정보는 [링크]에서 확인할 수 있습니다.