본 문서에서는 TKDD 저널에 게재된 "Static and Streaming Tucker Decomposition for Dense Tensors" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title: Static and Streaming Tucker Decomposition for Dense Tensors
- Authors: Jun-Gi Jang and U Kang
- Journal: ACM Transactions on Knowledge Discovery from Data (TKDD)
이 논문은 ICDE 2020에서 발표된 "D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors" 논문의 확장된 버전으로 본 문서에서는 저널 논문에 새로 추가된 부분만 다룹니다.
Tensor & Tucker decomposition
센서 데이터(센서, 위치, 시간), 기상 데이터(오염물질, 위치, 시간)와 같은 다양한 실세계 데이터들이 텐서(tensor)로 표현됩니다. 터커 분해(Tucker Decomposition)는 주어진 텐서 데이터를 작은 요인 행렬(factor matrix)들과 코어 텐서(core tensor)로 분해하는 방법으로 이상 탐지, 클러스터링, 추천 시스템 등 다양한 응용에 활용됩니다. 그림 1은 3차원 텐서에 대한 터커 분해 예시를 보여줍니다.
 | |
|
Online Streaming Setting
실세계 많은 데이터가 시간 축을 가지는 텐서로 표현됩니다. 나아가, 시간에 따라 데이터가 계속해서 추가되는 상황인 온라인 스트리밍 환경(online streaming setting)에서의 텐서는 시간 축의 크기가 계속해서 커집니다. 그림 2는 온라인 스트리밍 환경에서의 텐서를 보여줍니다.
그림 2. 온라인 스트리밍 환경에서의 텐서. 시간이 지남에 따라 텐서의 시간 축 크기가 커집니다.
텐서의 크기가 계속해서 커지는 상황에서 단순히 주어진 텐서를 분해하는 정적 터커 분해는 매우 비효율적입니다. 데이터가 새로 들어올 때마다 축적된 데이터에 대한 분해를 수행해야 하기 때문에 계산 시간이 기하급수적으로 증가합니다. 따라서, 시간이 지나도 계산 시간이 증가하지 않고 요인 행렬들과 코어 텐서를 업데이트하는 방법이 필요합니다. 또한, 스트리밍 환경에서 동작하는 몇 가지 터커 분해 방법들이 존재하였지만 효율성 측면에서 부족함이 있어 이를 더욱 향상시킬 필요가 있습니다.
Proposed Method
본 논문에서는 온라인 스트리밍 환경에서 터커 분해를 효율적으로 수행하는 방법인 D-TuckerO를 제안합니다. D-TuckerO는 시간이 지남에 따라 계산 시간이 증가하는 것을 피하기 위해 축적된 텐서와의 계산을 철저히 피하는 업데이트 계산을 수행합니다. 또한, 새로 들어온 텐서에 대한 업데이트 시간을 더욱 줄이기 위해 D-Tucker의 근사 단계를 활용하여 새로 들어온 텐서를 근사하고, 근사화된 결과를 활용하여 효율적인 업데이트를 수행합니다.
Update Factor Matrices
단순한 업데이트는 축적된 텐서와의 계산을 필요로 하기 때문에 매우 비효율적입니다. 따라서, 요인 행렬 업데이트 식에서 축적된 텐서와의 계산 항들을 주의깊게 분리하고, 새롭게 들어온 텐서 데이터에 대한 계산만 수행합니다. 축적된 텐서와 관련된 항들은 이전 시간에서 계산된 결과를 그대로 활용하기 때문에, 업데이트 시간은 전체 시간에 비례하지 않습니다. 다시 말해, D-TuckerO는 전체 시간에 비례하는 크기를 가지는 행렬 혹은 텐서와의 계산을 필요로 하지 않습니다. 그림 3에서처럼 시간 요인 행렬(temporal factor matrix)에 대해서는 새로 들어온 텐서의 시간 축에 대응하는 행(row)들만 얻고, 이전 시간에 얻은 행들은 업데이트하지 않습니다. 비시간 축 요인 행렬(non-temporal factor matrix)들은 새로운 텐서 데이터에 대해 전체적으로 업데이트됩니다. 구체적인 수식은 논문을 참고하시길 바랍니다.
그림 3. 새로 들어온 텐서와 이전 시간에 얻은 요인 행렬들과 코어 텐서를 활용하여 요인 행렬들과 코어 텐서를 업데이트합니다.
Approximation
새로운 텐서 데이터의 크기가 큰 경우 해당 텐서를 활용하여 업데이트 하는 것은 비효율적일 수 있습니다. 따라서, D-Tucker에서 활용한 근사 단계를 통해 새로 들어온 데이터를 근사화하고, 그 결과를 주의깊게 활용하여 업데이트 시간을 줄입니다. D-Tucker에서와 마찬가지로, 주어진 새로운 텐서를 행렬들의 모음으로 바라보고, 각 행렬들에 대한 Randomized SVD를 수행합니다. Randomized SVD는 저차원에 대해 빠르게 SVD 계산을 수행합니다. SVD를 통해 얻은 근사 결과들은 새로 들어온 입력 텐서에 비해 매우 작은 크기를 가집니다.
D-Tucker에서와 마찬가지로 근사화된 결과들을 활용하여 요인 행렬과 코어 텐서들을 주의 깊게 업데이트합니다. 근사화된 결과로 재복원 텐서를 만들지 않고 SVD 결과가 가지는 구조적인 특징을 활용하기 때문에 새로 들어온 텐서를 활용하는 것에 비해 더욱 효율적인 업데이트가 가능합니다. 구체적인 수식은 논문을 참고하시길 바랍니다.
Experiments
본 논문에서는 온라인 스트리밍 환경에서의 업데이트 효율성을 평가합니다. 또한, 새로 들어오는 입력 텐서의 크기에 대한 확장성(Scalability)를 평가합니다.
그림 4. 온라인 스트리밍 환경에서의 성능 평가. 제안하는 방법인 D-TuckerO가 기존 터커 분해 방법들에 비해 최소 2.9배 이상 빠름.
그림 4는 새로 들어오는 텐서에 대한 업데이트 시간을 측정하여 성능을 비교합니다. 4개의 시간 축을 가지는 실세계 텐서들을 실험에 활용하였으며, 매 시간마다 들어오는 텐서의 크기는 일정합니다. 제안하는 방법인 D-TuckerO는 정적 환경에서 동작하는 방법인 Tucker-ALS와 달리 시간이 지나도 업데이트 시간이 증가하지 않는 것을 확인할 수 있습니다. 또한, 온라인 스트리밍 환경에서 동작하는 기존 방법들에 비해 최소 2.9배 빠르게 새로 들어온 텐서를 업데이트합니다.
그림 5. 새로 들어오는 텐서의 시간 축 크기에 따른 D-TuckerO의 업데이트 시간 변화 평가. D-TuckerO의 업데이트 시간은 새로 들어온 텐서의 크기에 대해 선형에 가까운 확장성(near-linear scalability)을 가짐.
그림 5는 새로 들어온 텐서의 크기에 대한 D-TuckerO의 확장성을 평가한 결과를 보여줍니다. 새로 들어온 텐서의 시간 축 크기를 증가시키면서 D-TuckerO의 계산시간을 측정하였습니다. 모든 데이터셋에 대해 기울기가 약 1인 것을 확인할 수 있으며, 이는 D-TuckerO가 새로 들어오는 텐서의 크기에 대해 선형에 가까운 확장성(near-linear scalability)를 가지는 것을 나타냅니다.
Conclusion
본 문서에서는 ICDE 2020에서 발표된 논문을 확장한 TKDD 저널 논문을 소개하였습니다. 본 논문은 온라인 스티리밍 환경에서 효율적으로 동작하는 방법인 D-TuckerO를 제안합니다. 제안하는 방법은 새로 들어온 텐서 데이터를 업데이트 할 때 이전에 축적된 텐서와의 계산을 철저히 배제하여 전체 시간에 비례하는 업데이트 시간을 피했으며 새로 들어온 텐서 데이터에 대해 근사화를 수행하여 업데이트 단계를 가속화합니다. 실험적으로, 제안하는 방법인 D-TuckerO가 기존 방법들보다 훨씬 더 효율적으로 요인 행렬과 코어 텐서를 업데이트하는 것을 확인하였습니다. D-TuckerO를 활용하면 실시간 이상 탐지를 수행할 수 있으며 이외에도 새로 들어오는 텐서 데이터에 대해 다양한 실시간 분석을 수행할 수 있습니다. 논문에 대한 상세 정보는 (링크)에서 확인할 수 있습니다.