Mining Real World Tensors via Efficient Tensor Decomposition Methods

Abstract

Many real-world data can be represented as tensors including vectors (1-order tensor), matrices (2-order tensor), and higher-order tensors. For example, there are stock data, healthcare data, video data, sensor data, and movie rating data represented as tensors. Tensor decomposition has been widely used in applications to analyze real-world tensors. Since knowledge is inherent in real-world tensors, it is crucial to devise effective Tensor decomposition methods. However, existing Tensor decomposition-based methods require high computational costs and space costs. Therefore, it is very challenging to discover hidden information in large-scale tensors without efficient tensor decomposition methods. In this thesis, I overcome the limitations of previous tensor analysis methods based on tensor decomposition. Since existing tensor decomposition methods require heavy computations involved with large-scale input tensors, it is crucial to avoid the computations to achieve high efficiency. My proposed methods achieve high efficiency by approximating an input tensor and exploiting the approximation result. I devise highly efficient methods for regular and irregular tensors by exploiting the characteristics of real-world tensors and carefully determining the order of computations. Furthermore, I develop a fast and memory-efficient tensor decomposition-based method that analyzes diverse time ranges. Extensive experiments show that the proposed methods achieve higher efficiency than existing methods while having comparable errors. The proposed methods decompose regular and irregular tensors up to 38.4x and 6x faster than existing methods, respectively. In addition, the proposed method analyzes various time range queries up to 171.9x faster than existing methods. Consequently, the proposed methods allow us to explore meaningful knowledge from various real-world tensors efficiently.

실세계에 존재하는 다양한 다차원 데이터가 텐서로 표현된다. 텐서는 1차원의 벡터, 2차원의 행렬, 3차원 이상의 고차원 텐서를 포함하는 개념이다. 예를 들어, 주식 데이터, 헬스케어 데이터, 동영상 데이터, 센서 데이터, 영화 등급 데이터 등이 텐서로 표현될 수 있다. 실세계 텐서들에는 중요한 지식 및 정보들이 내재 되어있기 때문에 텐서를 분석하는 도구를 개발하는 것은 매우 중요하다. 하지만, 전통적인 텐서 분석 방법들은 대다수의 규모가 매우 큰 실세계 텐서를 분석하는데 있어 많은 시간과 공간 자원을 필요로 하기 때문에, 텐서들로부터 중요한 지식 및 정보들을 탐색하는데 많은 어려움을 겪어왔다. 본 학위 논문에서는 텐서 분해 기반 대규모 실세계 텐서 분석 기술의 한계를 극복하고자 한다. 기존 텐서 분해 방법들은 주어진 대규모 입력 텐서와의 계산이 많기 때문에 이를 줄이는 것이 효율성을 높이는데 매우 중요하다. 따라서, 텐서 데이터의 실세계 구조적 특징을 활용하여 대규모 입력 텐서에 대한 계산량을 줄임으로써 정확도 손실을 최소화하면서도 빠르고 확장성 있는 기법을 제안한다. 또한, 다양한 시간 범위에 숨겨진 지식 정보들을 효율적으로 탐색할 수 있는 텐서 분해 기반 텐서 분석 기술을 제안한다. 본 학위 논문에서 제안하는 방법들이 실세계 텐서를 매우 효율적으로 분석할 수 있다는 것을 실험을 통해 보여준다. 제안하는 방법들은 비슷한 에러를 가지면서도 매우 높은 효율성을 달성한다. 제안하는 방법들은 기존 방법들과 비교하여 주어진 규칙 텐서와 불규칙 텐서를 각각 최대 38.4배, 6배 빠르게 분해한다. 또한, 제안하는 방법은 임의의 시간 범위에 대해 최대 171.9배 빠르게 분석하는 것을 가능하게 해준다. 제안하는 방법들은 다양한 실세계 텐서들로부터 유의미한 지식을 효율적으로 탐구하는 것을 가능하게 한다.