Time-Aware Tensor Decomposition for Missing Entry Prediction

본 문에서는 Arxiv에 기재된 Time-Aware Tensor Decomposition for Missing Entry Prediction 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. 

CANDECOMP/PARAFAC (CP) Decomposition

그림 1. 3차원 시간 텐서의 CP 분해

다차원 배열을 의미하는 텐서는 시간에 따라 변화하는 다중적인 관계를 표현할 수 있습니다. 예를 들어, 센서에서 수집된 대기 오염 데이터는 오염 물질의 측정 값을 포함하는 3차원 시간 텐서(장소, 오염 물질, 시간)로 표현됩니다. 텐서 분해(Tensor Decomposition)는 텐서 데이터를 효과적으로 분석하는 방법으로, 클러스터링 및 이상 탐지를 포함한 다양한 응용 프로그램에서 광범위하게 활용되고 있습니다. CANDECOMP / PARAFAC (CP) 분해는 가장 대표적인 텐서 분해 모델 중 하나로, 그림 1과 같이 텐서를 각 차원의 벡터들의 외적의 합으로 나타낼 수 있습니다. 

위와 같은 시간 텐서에는 대표적인 특성 2가지를 관측할 수 있습니다. 첫번째는 텐서의 시간 차원은 인접한 값들끼리는 서로 연관성이 있는 특징이 있습니다. 예를 들어, t번째 시간에서 관측된 오염 데이터는 t-1, t+1번째 시간에서 관측된 오염 데이터와 비슷한 값을 갖을 것입니다. 두번째로는 데이터를 수집하는 센서 및 기계 오류 및 고장으로 인해 텐서는 많은 결측치로 포함하고, 이는 시간 조각(Time Slice) 별로 다른 희소성(혹은 밀도)을 갖게 합니다. 

그러나 표준적인 CP 분해 방법을 포함한 기존 분해 방법들은 위 두 가지 특성 모두 고려하지 않았습니다.  본 논문의 목표는 결측치 예측을 위해 시간 텐서의 대표적인 특성인 1)시간 연속성과 2)시간 조각의 희소성을 고려해 정확한 CP 분해 기법을 개발하는 것입니다.  구체적으로, 모델은 각 시점의 정보가 과거와 미래의 정보와 밀접한 관련이 있기 때문에 과거와 미래의 정보를 모두 이용하는 것과 시간 조각별 희소한 특성을 이용해 시간 연속성을 모델링 하여 더 정확한 결측치 예측을 가능하게 하는 것입니다. 

Time-Aware Tensor Decomposition (TATD)

그림 2. TATD의 핵심 아이디어: smoothing regularization & sparsity penalty. 

본 논문에서는 결측치 예측을 위해 시간 연속성을 고려한 정확한 CP 분해 모델인 TATD를 제안합니다. TATD의 핵심 아이디어에 대한 설명은 아래글과 그림 2와 같습니다. 

Smoothing Regularization 

시간 텐서의 시간 연속성으로 인해 인접한 시간 조각은 서로 밀접하게 관련되어 있습니다. 이는 텐서 분해 결과인 시간 요소 행렬(Time Factor Matrix)에도 같은 특성을 갖게 되어, 인접한 시간 요소 벡터들(Time Factor Vector)의 값 또한 서로 비슷한 경향이 있을것입니다. 이를 위해, 시간 요소 벡터가 주변의 요소 벡터들의 가중합과 가까워지도록 만드는 평활 정규화 항(Smoothing Regularization)을 손실 함수에 추가하여 학습합니다. 이 때, 어떤 가중 함수를 사용하는 것이 중요한데, 제안 기법은 Gaussian Kernel Function을 사용합니다.  본 논문에서 가정한 시간 연속성 성질을 만족하고 따로 파라미터를 학습할 필요가 없어서 보다 더 안정적으로 학습할 수 있기 때문입니다.  

Sparsity penalty

시간 텐서의 시간 조각은 서로 다른 밀도를 갖고 있으므로,  매우 희소한 시간 조각에서는 높은 밀도를 갖는 시간 조각에 비해 덜 정확한 시간 요소 벡터가 만들어집니다.  이를 방지 하기 위해서 모든 시간 요소 벡터들에 동일한 양의 평활 정규화를 적용하는 대신, 더 희소한 시간 조각의 시간 요소 벡터에 정규화를 많이 받도록, 시간 조각의 희소성을 기반으로 평활 정규화의 양을 제어합니다.  시간 조각 별 희소성 페널티(Sparsity Penalty)는 각 시간 조각의 밀도를 구한 후 1에서 뺀 값과 같습니다.  그림 2의 가장 오른쪽 그림의 빨간 선을 보면, 더 희소한 t_1 시간 조각의 시간 요소 벡터는 주변의 값의 영향을 더 많이 받고, 덜 희소한 t_2 시간 조각의 벡터는 주변 값의 영향을 덜 받게 됩니다. 

Experiments

본 논문에서는 크게 두 가지 실험 결과를 제시합니다. 첫 번째는 시간 연속성을 고려하는것이 분해 결과의 정확도를 높여주고 두번째로는 시간 희소성을 추가로 고려하여 보다 높은 분해 정확도를 얻는다는 것입니다. 그림 3에서 TATD-0는 평활 정규화 항을 추가한 기법을 의미하고 TATD는 평활 정규화 항과 시간 조각 별 희소성 를 추가한 기법을 의미합니다. 


그림 3.  TATD와 기존 방법들간의 결측치 예측 성능 비교 (TATD가 가장 좋은 성능을 보여줍니다.)

Conclusion 

본 문서에서는 Arixv에 기재된 ‘Time-Aware Tensor Decomposition for Missing Entry Prediction’ 논문을 소개했습니다. 해당 논문은 실세계 시간 텐서의 특징인 1) 시간 연속성과 2) 시간 조각 별 희소성을 이용하여 정확한 CP분해 기법인 TATD를 제안했습니다. 실험을 통해 제안 기법이 기존 기법들에 비해 더 높은 분해 정확도를 갖는 것을 확인했습니다. 논문에 대한 자세한 내용은 링크를 통해 확인하실 수 있습니다.