D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors

본 문서에서는 ICDE 2020에서 발표된 "D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
  • Jun-Gi Jang et al., D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors, ICDE 2020

Tucker Decomposition 

동영상 (가로, 세로, 시간), 기상 데이터 (오염물질, 위치, 시간) 등과 같이 다양한 데이터들이 밀도 높은 텐서 (Dense tensor)로 표현됩니다. 터커 분해 (Tucker Decomposition)은 텐서 데이터를 분석하는 가장 유명한 모델 중 하나이며 차원 축소, 클러스터링, 추천 시스템 등과 같이 다양한 응용들에서 활용하고 있습니다.
그림 1. 3차원 텐서에 대한 터커 분해 예시
터커 분해는 그림 1의 예시와 같이 주어진 텐서를 각 차원의 저계수 요인행렬 (low-rank factor matrix)과 관계간의 강도를 표현하는 코어 텐서 (core tensor)로 분해합니다. 터커 분해는 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와 입력 텐서간의 차이를 줄이는 방향으로 요인 행렬들과 코어 텐서를 학습합니다.
ALS (Alternating Least Square)는 터커 분해의 요인 행렬들과 코어 텐서를 학습할 때 사용하는 접근법 중 하나입니다. 해당 방법은 임의의 요인 행렬 하나를 제외한 나머지 모두를 고정시키고, 고정되지 않은 하나의 요인 행렬을 업데이트하며, 요인 행렬들을 순서대로 업데이트합니다. 그림 1의 예에서는 행렬 B와 C를 고정시키고 A를 업데이트합니다. 그 다음, A와 C를 고정시키고 B를 업데이트하며, C도 마찬가지로 A와 B를 고정시켜 업데이트합니다. 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와 입력 텐서 간의 차이가 수렴할 때까지 업데이트를 반복합니다.

Limitations of Existing Methods

ALS 방법을 통한 터커 분해는 밀도 높은 입력 텐서와 요인행렬간의 계산을 요구하기 때문에 입력 텐서의 크기가 커짐에 따라 계산량과 메모리 사용량이 폭발적으로 증가합니다. 그러므로 기존의 방법들은 입력 텐서와의 직접적인 계산을 피하고자 하였습니다. 몇몇 터커 분해들은 효율적인 계산방법이나 randomized algorithm들을 활용하여 계산시간을 줄이고자 하였습니다. 또다른 터커 분해들은 입력 텐서를 스케칭 (sketching)하거나 샘플링 (sampling)을 통해 입력 텐서를 근사화하고 근사화된 결과를 이용하여 계산량과 메모리 사용량을 줄였습니다. 하지만, 기존의 방법들은 계산량과 메모리를 줄이는 동시에 높은 정확도를 제공하는 방법은 없었습니다.
그렇다면, 어떻게 해야 높은 정확도를 제공하면서도 빠르고 메모리 효율적으로 터커 분해를 계산할 수 있을까요? 밀도 높은 입력 텐서를 잘 분해하기 위해서는 1) 입력 텐서를 빠르면서도 정확하게 근사화해야 하며, 2) 초기화 및 업데이트 과정에서 많은 계산량과 메모리 사용량을 요구하는 큰 중간 데이터 생성을 피해야 합니다. Proposed Method에서는 이 두가지 과제를 해결함으로써 빠르고 메모리 효율적으로 터커 분해를 수행하는 D-Tucker를 소개합니다.

Proposed Method

그림 2. Overview of D-Tucker

본 논문에서는 밀도 높은 텐서에 대하여 터커 분해를 빠르고 메모리 효율적으로 계산할 수 있는 D-Tucker를 제안합니다. D-Tucker의 핵심적인 목표는 입력 텐서를 빠르게 근사 (압축)하고, 압축 결과를 효율적으로 다루어 빠르고 메모리 효율적인 업데이트를 하는 것으로 D-Tucker는 아래와 같이 3단계로 구성되어 있습니다.
  • Approximation Phase. 실세계 데이터의 특성을 활용하여 입력 텐서를 빠르게 근사화 하는 단계. 
  • Initialization Phase. 업데이트 단계 전 요인 행렬에 대한 초기화를 수행.하는 단계. 좋은 초기화는 업데이트 단계에서의 반복 횟수를 줄일 수 있음
  • Iteration Phase. 근사화된 결과를 이용하여 요인 행렬들과 코어 텐서를 업데이트하는 단계. 근사화된 결과를 입력 텐서 형태로 복원하는 것을 피하여 계산 효율성과 메모리 효율성을 극대화함.
본 문서에서는 터커 분해 계산이 어떻게 진행되는지 대한 핵심적인 내용에 대해서만 논의합니다. 구체적인 방법론 및 수식은 논문을 참고하시면 됩니다. 

Approximation Phase 

입력 단계에서는 아래 두 가지 실세계 텐서 특성을 활용하여 빠르게 입력 텐서를 근사화합니다.
  • Skewed shape of real-world tensors: 실세계 텐서는 각 차원마다 길이가 다릅니다. 예를 들어, 기상 데이터에서 위치나 오염물질  축은 갯수가 제한되어 있으나, 시간 축의 길이는 매우 깁니다.
  • Low dimensional structure in sliced matrices: 실세계 행렬은 중복적이고 상관관계가 있는 구성 요소들이 있어 저차원 구조를 가집니다. 마찬가지로, 텐서의 임의의 두 축을 선택하여 행렬을 만들 수 있는데, 이 행렬 또한 실세계 행렬로 설명 가능합니다. 예를 들어, 기상 데이터에서 시간 축과 오염물질 축을 선택하여 행렬을 구성할 수 있으며, (시간, 위치), (위치, 오염물질) 쌍으로 행렬을 구성하여도 실세계 행렬의 특징을 따릅니다. 
두 가지 실세계 특성을 활용하여 빠르고 메모리 효율적으로 근사화를 수행합니다. 이러한 성질을 활용하기 위해 텐서 축을 길이를 기준으로 내림차순 정렬합니다. 첫번째 축의 길이가 가장 길며, 마지막 축의 길이가 가장 짧습니다. 그 다음, 첫번째 축과 두번째 축을 가지는 행렬들로 입력 텐서를 슬라이싱합니다. 각 슬라이스된 행렬에 대해서 Randomized SVD을 수행하여 입력 텐서를 근사화합니다. Randomized SVD은 저차원 구조를 가지는 행렬에 대해서 빠르고 메모리 효율적으로 SVD 계산을 수행합니다. 각 행렬의 SVD 계산 결과는 U, S, V이며, U, V는 열방향 직교 행렬이고 S는 대각 행렬이고 내림차순 정렬되어 있습니다. 근사화된 결과들은 입력 텐서에 비해 매우 작은 크기를 가집니다.

Initialization Phase 

초기화 단계에서는 업데이트 단계 전 요인 행렬들에 대해서 초기화를 진행합니다. 좋은 초기화는 업데이트 단계에서 업데이트 횟수를 줄일 수 있어 전체 계산시간을 줄이는데 큰 도움이 됩니다. 근사 단계에서 얻은 SVD 결과들을 입력 텐서 형태로 복원하지 않으면서 요인 행렬들을 초기화하는 것이 중요합니다. 근사 단계에서 얻은 결과가 입력 텐서보다 크기가 작기 때문에 복원를 피한다면 계산량과 메모리 사용량을 매우 줄일 수 있습니다. 제안 방법에서는 SVD의 결과들이 가지는 구조적인 특징을 활용하여 입력 텐서 형태로의 복원를 피한 채 초기화를 수행합니다. 구체적인 수식 및 계산은 논문을 참고하시면 됩니다.

Iteration Phase 

업데이트 단계에서는 초기화된 요인 행렬들과 근사 단계에서 얻은 SVD 결과들을 활용하여 요인 행렬들과 코어 텐서를 업데이트합니다. 업데이트 단계에서는 ALS와 마찬가지로 요인 행렬들과 코어 텐서를 업데이트합니다. 효율적인 업데이트를 위해서 근사 단계에서 얻은 SVD 결과들을 재복원 텐서로 복원하지 않고 SVD 결과가 가지는 구조적인 특징을 활용합니다. 근사 (압축)된 결과가 입력 텐서보다 매우 작으므로 복원을 피한다면 빠르고 메모리 효율적으로 각 요인 행렬들을 업데이트할 수 있습니다. 구체적인 수식 및 계산은 논문을 참고하시면 됩니다.

Experimental Results

그림 3. D-Tucker에 대한 계산 시간, 업데이트 시 필요한 메모리 사용량 비교

그림 4는 D-Tucker와 경쟁 방법들간의 계산 시간과 메모리 사용량을 비교합니다. 먼저 그림 4(a), 4(b)는 4개의 텐서 데이터 (Brainq, Boats, Air quality, HSI)에 대해서 계산 시간과 복원 에러간의 Trade-off를 보여줍니다. 모든 데이터에 대해서 제안한 D-Tucker가 최상의 성능을 나타내는 지점인 왼쪽 아래에 제일 가까운 것을 볼 수 있습니다. 
그림 4 (c)는 초기화 단계와 업데이트 단게에서의 메모리 사용량을 비교합니다. Boats 데이터셋을 제외하고는 D-Tucker가 최대 17.2배 메모리 효율성을 보여줍니다. Boats 데이터셋에서 Tucker-ttmts가 제안방법보다 메모리 사용량이 적으나, 에러 측면에서 최대 7.5배 큰 것을 확인할 수 있습니다.

Conclusion

본 문서에서는 ICDE 2020에서 발표된 "D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors" 논문을 소개하였습니다. 해당 논문은 실세계 밀도 높은 텐서의 특징을 활용하여 빠르게 근사화하고 근사화된 결과를 효율적으로 활용하여 터커분해를 계산하는 D-Tucker를 제안하였습니다. 실험을 통해 제안한 기법이 다른 경쟁 기법들 보다 더 빠르고 메모리 효율적인 것을 확인하였습니다. 논문에 대한 상세 정보는 (링크)를 통해 확인할 수 있습니다.