본 문서에서는 ICDE 2022에서 발표될 "DPar2: Fast and Scalable PARAFAC2 Decomposition for Irregular Dense Tensors" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title: DPar2: Fast and Scalable PARAFAC2 Decomposition for Irregular Dense Tensors
- Authors: Jun-Gi Jang and U Kang
- Conference: 38th IEEE International Conference on Data Engineering (ICDE), 2022
PARAFAC2 Decomposition
센서 데이터 (시간, 위치, 센서타입), 주식 데이터 (시간, 피쳐, 종목) 등과 같이 다양한 데이터들이 밀도 높은 불규칙 텐서 (irregular dense tensor)로 표현됩니다. 불규칙 텐서는 행의 크기가 서로 다른 행렬들의 모음으로도 볼 수 있습니다. PARAFAC2 Decomposition은 불규칙 텐서 데이터를 분석하는 가장 유명한 방법 중 하나이며 차원 축소, 고장 탐지, 표현형 발견(phenotype discovery) 등과 같이 다양한 응용들에서 활용되고 있습니다.
그림 1. PARAFAC2 Decomposition
PARAFAC2 Decomposition은 그림 1의 예시와 같이 주어진 불규칙 텐서를 요인행렬(factor matrix)들로 분해합니다. ALS (Alternating Least Square)는 PARAFAC2 Decomposition의 요인행렬들을 구할 때 사용하는 접근법 중 하나입니다. 해당 방법은 요인 행렬 하나를 제외한 나머지 모두를 고정시키고, 고정되지 않은 하나의 요인 행렬을 업데이트하는 방식으로 요인 행렬들을 순서대로 업데이트합니다. 요인 행렬들은 재복원한 텐서와 입력 텐서 간의 차이가 충분히 작아질 때까지 업데이트가 됩니다.
Limitations of Existing Methods
ALS 방법을 통한 PARAFAC2 Decomposition은 밀도 높은 입력 텐서와 요인행렬간의 계산 때문에 많은 계산 비용과 공간 비용을 필요로 합니다. 최근에는 전자의료기록 데이터(Electronic Health Record Data)를 분석하기 위해 PARAFAC2 Decomposition에 대한 연구가 활발히 진행되었습니다. 하지만, 기존 연구들이 희소 불규칙 텐서(irregular sparse tensor)로 표현되는 EHR 데이터를 분석하는 것에만 초점을 맞추었기 때문에, 이 방법들은 EHR 데이터와는 특징이 다른 밀도 높은 불규칙 텐서(irregular dense tensor)를 분석하기에는 적합하지 않았습니다.
그렇다면, 어떻게 해야 효율적으로 PARAFAC2 Decomposition을 수행할 수 있을까요? 밀도 높은 불규칙 텐서를 효율적으로 분해하기 위해서는 입력 텐서와의 계산을 최소화해야 하여 요인 행렬들을 효율적으로 업데이트하고, 멀티 코어 병렬화(multi-core parallelism)을 최대화 해야 합니다. 다음 절에서는 주어진 과제를 해결함으로써 빠르고 확장성 있는 PARAFAC2 Decomposition을 수행하는 방법을 소개합니다.
Proposed Method
그림 2. 제안 방법인 DPar2의 개요도. 주어진 밀도 높은 불규칙 텐서를 효율적으로 근사화하고, 근사화된 결과를 주의깊게 활용하여 요인행렬들의 업데이트 과정을 가속화한다.
본 논문에서는 밀도 높은 불규칙 텐서를 효율적으로 처리하는 PARAFAC2 Decomposition 방법인 DPar2를 제안합니다. DPar2는 주어진 입력 불규칙 텐서를 빠르게 근사화하며, 근사화된 결과만을 주의깊게 활용하여 요인행렬들을 업데이트합니다. 나아가, 데이터의 불규칙함을 고려하여 멀티 코어 병렬화를 최적화합니다. 이 아이디어를 통해 DPar2는 빠르고 확장성 있게 불규칙 입력 텐서를 처리할 수 있습니다.
효율적인 요인행렬 업데이트를 수행하기에 앞서 불규칙 텐서에 대한 근사화를 수행합니다. 불규칙 텐서는 시간 길이가 서로 다른 행렬들의 모음으로 볼 수 있으며, 각 행렬들은 실세계 데이터의 특성을 따릅니다. 그러므로, DPar2는 실세계 데이터 행렬을 빠르면서도 에러 손실이 작은 근사화 방법인 Randomized SVD (Singular Value Decomposition)를 활용합니다. Randomized SVD는 기존 SVD에 Randomized algorithm을 적용하여 SVD 계산을 가속화하는 방법입니다. 자세한 내용은 "Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions" 논문을 참고하시길 바랍니다. DPar2는 Randomized SVD를 활용하여 두 단계의 근사화를 수행합니다. 두 단계의 근사화는 업데이트 단계의 효율성을 최대화합니다.
근사화된 결과를 활용하여 PARAFAC2 Decomposition의 요인행렬들을 효율적으로 업데이트합니다. 가장 단순한 접근으로는, 근사화된 결과를 복원하여 입력 텐서 형태로 만들고, 이를 활용하여 요인행렬들을 업데이트하는 것입니다. 하지만, 이 방법은 효율성 측면에서 도움이 되지 않습니다. DPar2는 입력 텐서를 근사화한 이점을 최대한 살리기 위해, 열 직교성(column orthogonality)이나 혼합 곱셈 속성(mixed product property) 등을 활용하여 계산량을 최소화하고 큰 중간 데이터 발생을 막습니다.
마지막으로, DPar2는 데이터의 불규칙성을 고려하여 멀티 코어 병렬화를 최적화합니다. 불규칙 텐서를 시간 길이가 서로 다른 행렬들의 모음으로 볼 때, 행렬들을 임의로 스레드에 할당하면 병렬화 성능이 좋지 않을 수 있습니다. 예를 들어, 두 개의 스레드를 사용할 때 행의 길이가 긴 행렬 데이터들이 모두 한 스레드에 할당이 되고, 행의 길이가 짧은 행렬 데이터들이 모두 다른 한 스레드에 할당 될 수 있습니다. DPar2는 행렬들의 행 크기를 고려하여 스레드가 처리하는 행렬들의 행 길이 합이 비슷하도록 스레드별로 행렬들을 할당합니다. 그리하여, DPar2는 효과적으로 불규칙 텐서를 병렬 처리합니다.
Experimental Results
본 논문에서는 실세계 불규칙 텐서와 인공적으로 만든 불규칙 텐서를 활용하여 효율성 및 확장성을 비교평가합니다.
그림 3. 계산 시간과 fitness간의 Trade-off 실험 결과. 제안 방법인 DPar2가 최고의 trade-off를 가지며, 최대 6배 빠르면서도 유사한 fitness를 가짐.
그림 3는 DPar2와 경쟁 방법들간의 계산 시간과 fitness을 비교합니다. fitness는 분해 방법들의 결과로부터 복원한 텐서가 입력 텐서와 얼마나 비슷한지를 나타내는 척도입니다. 총 8개의 불규칙 텐서 데이터에 대해서 계산 시간과 fitness 간의 Trade-off를 보여줍니다. 모든 데이터에 대해서 제안한 DPar2가 최상의 성능을 나타내는 지점인 왼쪽 위에 제일 가까운 것을 볼 수 있습니다. DPar2는 비슷한 fitness를 가지면서도 최대 6배 빠르게 불규칙 텐서 분해를 수행하는 것을 확인할 수 있습니다.
그림 4. DPar2의 확장성(scalability) 평가. (a), (b) DPar2는 텐서 크기와 요인 행렬의 rank에 대해 확장성이 있음을 보여줌. (c) Dpar2가 효과적으로 병렬화를 수행함을 보임
그림 4는 DPar2의 확장성을 평가합니다. 확장성은 다양한 인공 데이터(synthetic data)를 생성하여 평가하였습니다. 그림 4(a), (b)에서는 모든 텐서 크기와, 요인 행렬의 rank에 대해 DPar2가 빠름을 보입니다. 그림 4(a)에서는 모든 텐서 크기에 대해서 DPar2가 비교 방법들에 비해 빠르며, 작은 기울기를 가지는 것을 보입니다. 그림 4(b)에서는 rank에 대해 비록 DPar2의 기울기가 비교 방법들에 비해 약간 크나, 큰 rank에서도 Dpar2는 여전히 빠르게 불규칙 텐서를 분해할 수 있음을 보입니다. 그림 4(c)에서는 DPar2가 스레드 수에 비례하여 계산 속도가 빨라짐을 보입니다.
Conclusion
본 문서에서는 ICDE 2022에서 발표될 "DPar2: Fast and Scalable PARAFAC2 Decomposition for Irregular Dense Tensors" 논문을 소개하였습니다. 해당 논문은 실세계 밀도 높은 불규칙 텐서를 빠르게 근사화하고 근사화된 결과를 주의깊게 활용하여 효율적으로 PARAFAC2 Decomposition을 수행하는 DPar2를 제안하였습니다. 실험을 통해 제안한 기법이 다른 경쟁 기법들 보다 더 빠르고 확장성이 큰 것을 확인하였습니다. DPar2 기법을 활용하여 트렌드 분석, 클러스터링 등과 같은 응용들을 매우 효율적으로 할 수 있습니다. 예를 들어, 주식 데이터에서 비슷한 종목 탐색이나 피쳐 분석을 수행해 볼 수 있습니다. 이외에도 제안한 Dpar2 기법을 통해 기존에 분석하기 힘들었던 불규칙 텐서들을 빠르고 쉽게 분석할 수 있으며, 불규칙 텐서를 처리해야 하는 다양한 분야의 연구들도 보조할 수 있을 것이라 기대합니다. 논문에 대한 상세 정보는 (링크)를 통해 확인할 수 있습니다.