Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries

본 문서에서는 데이터 마이닝 분야 학회 중 하나인 KDD 2021에서 발표될 "Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries" 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다.

  • Title: Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries
  • Authors: Jun-Gi Jang and U Kang
  • Conference: The 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2021

Temporal Dense Tensor

실세계에 존재하는 많은 데이터가 시간 밀도 텐서 (temporal dense tensor)로 표현될 수 있습니다. 시간 밀도 텐서는 한 차원이 시간과 관련이 있으며, 대부분의 값들이 관측된 데이터입니다. 예를 들어, 여러 위치에 설치된 센서들에서 매 시간마다 측정값들을 얻을 수 있습니다. 해당 데이터는 3차원 시간 밀도 텐서로 표현할 수 있습니다. 이 외에도, 주식 데이터, 비디오 데이터, 교통량 데이터 등도 시간 밀도 텐서로 표현할 수 있습니다.

그림 1. 시간 밀도 텐서 예시. 센서 데이터, 주식 데이터, 비디오 데이터, 교통량 데이터 등 다양한 실세계 데이터가 시간 밀도 텐서로 표현할 수 있다.

이렇듯 실세계에 존재하는 많은 데이터가 시간 밀도 텐서로 표현될 수 있으며 여러 차원을 가지는 텐서 특성상 데이터의 크기는 매우 큽니다. 그러므로, 시간 밀도 텐서를 효율적이고 효과적으로 분석하는 방법을 개발하는 것은 매우 중요합니다.

Tucker Decomposition 

터커 분해 (Tucker decomposition)는 주어진 텐서를 분석할 수 있는 가장 핵심적인 도구 중 하나입니다. 터커 분해는 데이터 압축, 클러스터링, 트렌드 분석, 개념 발견 등 다양한 응용들에 활용할 수 있습니다.
그림 2. 터커 분해 개요도.

위의 그림과 같이 터커 분해는 주어진 텐서를 각 차원의 요인 행렬  (factor matrix)과 코어 텐서 (core tensor)로 분해합니다. 이런 터커 분해 결과를 얻기 위해 많이 사용되는 방법은 ALS (Alternating Least Square)입니다. ALS 방법은 임의의 요인 행렬을 제외한 나머지 모두를 고정하고 고정하지 않은 요인 행렬을 업데이트합니다. 반복적으로 요인 행렬들과 코어 텐서를 업데이트해가면서 주어진 텐서와 ALS로 얻은 결과로 복원한 텐서와의 차이를 줄여나갑니다. 최종적으로, 주어진 입력 텐서를 근사할 수 있는 요인 행렬들과 코어 텐서를 얻습니다.

Time Range Query

시간 밀도 텐서가 주어졌을 때, 사용자에 따라 다양한 시간 범위를 분석할 수 있습니다. 예를 들어, 한 사용자는 특정 이벤트 (ex. COVID-19, 선거, 경제 위기 등)가 발생한 기간에 대한 분석을 할 수 있고 다른 사용자는 분기별 분석이나 최근 1달에 대한 분석을 해볼 수 있습니다. 이와 같이 시간 밀도 텐서가 주어졌을 때 다양한 시간 범위 쿼리를 효율적으로 처리해야 합니다.

Problem Definition

본 논문에서의 문제정의는 다음과 같습니다.
  • Given: a time range and temporal dense tensor.
  • Find: the Tucker result of the sub-tensor included in the time range efficiently.
  • The Tucker result includes factor matrices and core tensor.
그림 3. 본 논문의 목표 예시.

기존 터커분해 방법들은 주어진 텐서를 한 번 분해하는 것에 초점을 맞추기 때문에, 임의의 시간 범위에서의 부분 텐서에 대한 터커 분해 수행은 매우 비효율적입니다. 기존 ALS 방법은 쿼리가 들어올 때마다 주어진 입력 텐서를 이용하여 터커 분해를 수행해야 하기 때문에, 속도와 메모리 측면에서 불만족스럽습니다. 전처리를 수행하는 터커 분해 방법들이 존재하지만, 해당 방법들의 전처리 결과로는 주어진 시간 범위에 대해 빠르고, 메모리 효율적이고, 정확한 터커 분해를 수행할 수 없습니다.

Proposed Method

본 연구에서는 임의의 시간 범위에 대해 빠르고 메모리 효율적으로 터커 분해 하는 Zoom-Tucker 방법을 제안합니다. Zoom-Tucker 방법은 크게 전처리 단계와 쿼리 단계, 두가지 단계로 구성됩니다. 전처리 단계는 아래 그림 4와 같이 주어진 시간 밀도 텐서를 시간 축 방향을 따라 블록 단위로 분리하고, 각 블록 텐서를 터커 분해를 활용하여 압축합니다. 쿼리 단계는 전처리 단계에서 압축된 데이터만을 활용하여 주어진 시간 범위에 대해 터커 분해 결과를 계산합니다.
그림 4. 전처리 단계 개요도.
전처리 단계에서의 핵심 아이디어는 시간 축을 따라 블록별로 터커 분해를 수행하는 것입니다. 이를 통해, 지역적인 정보를 잃지 않으면서도 빠르고 메모리 효율적인 쿼리 단계를 지원할 수 있습니다. 쿼리 단계의 핵심 아이디어는 전처리 단계에서 압축된 결과를 적극 활용하여 중간 데이터 크기와 계산량을 최소화하는 것입니다. 특히, 블록 단위로 분리한 것과 터커 분해로 압축함에 따라 블록 행렬 곱셈 및 혼합 곱셈 속성 (the mixed product property)이라는 수학적 기법들을 활용하여 효율성을 극대화할 수 있습니다. 자세한 내용은 논문을 참고하시길 바랍니다. 

쿼리 단계에서 주어진 시간 범위를 처리하는 순서는 다음과 같습니다. 시간 범위 쿼리가 주어지면, 시간 범위 내에 포함된 블록 텐서들의 터커 분해 결과들을 불러옵니다. 첫 블록의 결과와 끝 블록의 결과 중 시간 범위에 포함되지 않는 부분이 있기 때문에, 시간 범위에 맞춰 두 블록들의 결과를 조정합니다. 그 다음, 주어진 블록들의 결과들을 활용하여, ALS 방법과 마찬가지로 반복적으로 요인 행렬들과 코어텐서를 수렴할 때까지 업데이트합니다.

정리하자면, 전처리 단계에서는 데이터를 크게 압축하면서도 정보 손실을 최소화하였고, 쿼리 단계에서는 전처리 단계의 이점들을 최대한 활용할 수 있는 수학적인 기법들을 활용하였기 때문에 빠르고 메모리 효율적으로 시간 범위 쿼리에 대한 터커 분해 결과를 얻을 수 있습니다.

Experiment

본 실험에서는 제안하는 Zoom-Tucker가 기존 터커 분해 방법들에 비해 시간 범위 쿼리를 빠르고 메모리 효율적으로 처리하는 것을 보입니다. 또한, 제안하는 방법을 이용하여 실제 데이터를 분석한 결과를 보여줍니다. 그림 5에서는 제안하는 방법이 짧은 길이와 긴 길이의 시간 범위 모두에서 Zoom-Tucker가 기존 터커 분해 방법들에 비해 빠르면서도 비슷한 에러값을 가지는 것을 확인할 수 있습니다. 그림 6에서는 Zoom-Tucker가 가장 적은 공간을 필요로 하는 것을 확인할 수 있습니다. 저장 공간은 쿼리를 처리할 때의 메모리 사용량과 연관이 깊습니다. 보다 자세한 실험 결과들은 논문에서 확인할 수 있습니다.
그림 5. 실행시간과 에러 간의 trade-off 비교 결과.
그림 6. 공간 비용 비교.

본 논문에서는 
Zoom-Tucker를 이용하여 효율적으로 데이터 분석을 수행합니다. 그림 7은 Zoom-Tucker를 이용하여 2013년과 2018년 각각에 대해 삼성전자 주식과 스마트폰 관련 주식들, 반도체 관련 주식들 간의 유사성을 분석한 결과입니다. 결과에서 보여지는 것과 같이 2013년에는 삼성전자의 주식이 스마트폰 관련 주식들과 유사한데 반해 2018년에는 반도체 관련 주식들과 더 유사한 것을 확인할 수 있습니다. 자세한 내용은 논문을 참고하시길 바랍니다.
그림 7. 2013년과 2018년에 삼성전자와 스마트폰 관련 주식들, 반도체 관련 주식들간의 유사성 측정 결과.

Conclusion

본 문서에서는 KDD'21에 발표될 예정인 "Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries" 논문을 소개하였습니다. 해당 논문은 시간 밀도 텐서와 임의의 시간 범위가 주어졌을 때, 시간 범위에 대응하는 부분텐서를 빠르고 메모리 효율적으로 터커 분해하는 Zoom-Tucker를 제안합니다. 실험적으로 Zoom-Tucker가 빠르고 메모리 효율적인 것을 검증하였으며, 제안하는 방법을 통해 실제 데이터 분석도 진행하였습니다. 본 논문은 다양한 사용자가 다양한 시간 범위에 대해 효율적으로 분석할 수 있는 기회를 제공합니다. 제안하는 방법을 이용하여 시간 밀도 텐서 곳곳에 숨겨진 유의미한 패턴들과 정보들을 탐색할 수 있고, 기존에 방대한 크기로 인해 분석하지 못했던 데이터에서 새로운 정보를 발견할 수 있을 것으로 기대합니다. 논문의 상세정보는 논문 홈페이지에서 확인할 수 있습니다. (링크)