Introduction

텐서(tensor) 또는 다차원 배열(multi-dimensional array) 데이터는 신호 처리, 컴퓨터 비전, 그래프 분석, 통계학 등 광범위한 분야의 핵심적인 구성 요소입니다. 텐서 분해는 행렬 분해의 일반화된 형태로서 데이터의 잠재적 특성 발견 및 결측값 추정 등에서 중요한 역할을 수행합니다.

텐서 데이터는 크게 시간에 따라 크기와 값이 변하는 동적(dynamic) 유형과 그렇지 않은 정적(static) 유형으로 구분할 수 있습니다. 동적 텐서에 대한 분해 연구는 실세계를 모델링하기 위해 필수적이나 지금까지 제안된 기법들은 정확도가 지나치게 낮은 한계를 지니고 있었습니다. 구체적으로 기존의 기법들은 빠른 수행 속도를 위해 시간축 업데이트를 생략하거나 이전 시간 단계의 인수행렬(factor matrix)을 그대로 이용하는 방식을 채택하였는데, 이들은 데이터의 패턴이 시간에 따라 변할 때 정확도가 급격하게 떨어지는 단점을 가지고 있었습니다. 본 논문에서는 이러한 한계점을 극복하여 정확하고 효율적인 텐서 분해를 수행하는 Data-Adaptive Online CP decomposition (DAO-CP)을 제안합니다.

Proposed Method (DAO-CP)

정확하고 효율적인 텐서 분해를 수행하기 위해서는 다음과 같은 한계점을 극복해야 합니다.

[C1] 텐서 스트림의 인수행렬을 업데이트하는 데에 소요되는 연산량을 줄여야 합니다.
[C2] 시간에 따라 변화하는 텐서 스트림의 테마를 탐지할 수 있어야 합니다.
[C3] 탐지된 정보를 이용하여 텐서 분해의 정확도를 증가시켜야 합니다.

본 논문에서 제안하는 Data-Adaptive Online CP decomposition (DAO-CP)은 다음과 같은 해결책으로 각 한계점을 극복합니다.

[S1] 보완행렬(complementary matrices)을 도입하여 시간축에 대한 업데이트 과정에서 중복되는 계산을 제거함으로써, 알고리즘 연산량을 큰 폭으로 감소시켰습니다.
[S2] 텐서 스트림의 국소 오차(local error)를 지속적으로 추적함과 동시에 z-score 분석을 적용함으로써 데이터의 변화 시점을 효과적으로 탐지하였습니다.
[S3] 탐지된 변화의 정도에 따라 재분해(Re-decomposition) 과정 적용해 알고리즘의 정확도와 속도 사이의 trade-off 균형을 정교하게 조절하였습니다.

이어지는 내용에서는 제안된 기법에 대한 좀 더 자세한 설명을 드리도록 하겠습니다.

(a) 보완행렬 (Complementary Matrices)

기존의 텐서 분해 기법에서 널리 사용되던 CP-ALS 알고리즘에서는 업데이트가 반복적으로 진행됨에 따라 불필요한 중복 계산에 의한 속도 저하가 발생하였습니다. DAO-CP에서는 이러한 단점을 해결하기 위해 보완행렬을 도입하고 이들을 오직 시간축에 대한 변화가 없을 때에만 업데이트되도록 설정하여 중복되는 계산을 제거하였습니다. 이러한 기술을 통해 알고리즘 전체적으로 연산량을 큰 폭으로 감소시키는 것이 가능합니다.

(b) 변화점 탐지 (Change Points Detection)

DAO-CP의 핵심 아이디어 중 하나는 주어진 텐서 스트림에서 실시간으로 변화를 탐지하고 이를 텐서 분해 결과에 반영하여 정확도를 향상시키는 것입니다. 이를 위해, 텐서 스트림의 분해 결과에 대한 국소 오차(local error)를 지속적으로 추적하고 이에 대한 z-score 분석을 적용하였습니다. z-score 분석은 실시간 데이터를 빠르게 처리할 수 있는 장점이 있으며, threshold 값을 변화해가며 미세한 변화 수준을 탐지할 수 있다는 장점 또한 가지고 있습니다.

(c) 재분해 (Re-decomposition Process)

텐서 스트림의 변화를 탐지하고 나면, DAO-CP는 이러한 정보를 분해 정확도를 향상시키는 데에 사용하게 됩니다. 구체적으로 DAO-CP는 z-score 분석을 통해 파악한 데이터의 변화 정도에 따라 split 또는 refinement 중 최선의 전략을 자동적으로 적용하게 됩니다. 그림 1은 DAO-CP의 재분해 과정에 대한 간략한 예시를 나타내고 있습니다. 데이터가 급격하게 변하는 지점에서는 split를 적용해 텐서 분해를 초기화하게 되며, 변화의 수준이 일정 범위 내일 때에는 refinement를 적용해 이전 단계의 분해 결과를 얼마나 재사용할지 판단하게 됩니다.

결과적으로, 이러한 재분해 기법은 축적된 분해 결과를 어떻게 활용하는 것이 좋은지 전략적으로 판단함으로써 정확도와 속도 사이의 균형을 정교하게 조절하는 기능을 수행합니다.

그림 1. Visualization of split and refinement processes of DAO-CP

Experiment

본 논문에서는 DAO-CP의 효과를 검증하기 위하여 다양한 실험을 진행하였고, 아래 표는 이 중 가장 대표적인 실험 결과인 텐서 분해의 정확도 실험 결과를 나타내고 있습니다. 실험에서는 4개의 실제 세계 데이터와 1개의 합성 데이터에 대하여 경쟁 기법들과 정확도를 비교하였습니다. DAO-CP는 앞서 언급한 기존 기법들의 한계점들을 극복함으로써 모든 데이터셋들에서 평균적으로 가장 높은 정확도를 보였습니다.

그림 2. Reconstruction errors: Global (upper) and local (lower) fitness

Conclusion

본 문서에서는 PLOS ONE 저널에 게재된 "DAO-CP: Data-Adaptive Online CP Decomposition for Tensor Stream" 논문에 대해 소개하였습니다. 해당 논문에서는 정확하고 효율적인 텐서 분해를 수행하는 DAO-CP를 제안하였으며, 실험을 통해 해당 기법이 기존 기법들을 모든 데이터 셋에서 능가함을 보였습니다.

텐서 분해는 신호 처리, 컴퓨터 비전, 그래프 분석, 통계학 등에 이르기까지 그 활용 범위가 매우 넓습니다. 본 논문이 제안한 DAO-CP 기법은 기존 기법들의 한계점을 훌륭하게 극복하여 이러한 다양한 응용 사례에서 효과적으로 활용될 수 있을 것으로 기대됩니다. 논문에서는 본 문서에서 다룬 내용 이외에도 더욱 자세한 설명들과 다양한 이론적, 실험적 근거들이 있으니 관심 있으신 분들은 논문을 참고해주시면 감사하겠습니다. (링크)

Data Mining Lab. Blog

Search This Blog

DAO-CP: Data-Adaptive Online CP Decomposition for Tensor Stream