본 문서에서는 KDD 2023에서 발표될 "Fast and Accurate Dual-Way Streaming PARAFAC2 for Irregular Tensors - Algorithm and Application" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title: Fast and Accurate Dual-Way Streaming PARAFAC2 for Irregular Tensors - Algorithm and Application
- Authors: Jun-Gi Jang, Jeongyoung Lee, Yong-chan Park, and U Kang
- Conference: The 29th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) 2023
Irregular Tensor & PARAFAC2 Decomposition
불규칙 텐서(Irregular tensor). 불규칙 텐서는 특정 축의 크기가 정렬되지 않은 텐서로 행의 크기는 다르지만 열의 크기는 같은 행렬들의 모음으로도 설명될 수 있습니다. 주식 데이터, 교통량 데이터, 센서 데이터 등 다양한 데이터가 불규칙 텐서로 표현될 수 있습니다.
PARAFAC2 분해. PARAFAC2 분해는 불규칙 텐서를 분석할 때 활용되는 텐서 분해 기법 중 하나로 기존 텐서 분해들과 달리 데이터의 불규칙성을 유지한 채 텐서를 분해합니다. PARAFAC2 분해는 이상 탐지, 표현형 발견, 차원 축소 등 다양한 응용에 활용될 수 있습니다. 그림 1은 불규칙 텐서가 주어졌을 때 이를 PARAFAC2로 분해한 결과를 보여주는 예시입니다.
그림 1. 불규칙 텐서 및 PARAFAC2 분해.
Dual-Way Streaming Setting
양방향 스트리밍 상황(Dual-way streaming setting)은 실시간으로 기존 행렬들의 행들이 추가됨과 동시에 새로운 행렬들이 들어오는 상황을 의미합니다. 텐서 데이터의 관점에서 보면 3차원 불규칙 텐서가 주어졌을 때 두 축의 크기가 계속해서 증가하는 상황입니다. 주식 데이터를 예로 들면, 각 종목 데이터는 (시간,피처) 행렬로 표현이 되며 종목마다 상장시기가 다르기 때문에 종목 행렬들의 모음은 불규칙 텐서로 표현됩니다. 피처는 시가, 종가, 5일 이동평균 등을 포함하며, 매일 각 종목의 피처값들이 추가되기 때문에 기존 종목 행렬들의 행 크기는 커집니다. 또한, 새로운 종목이 상장되면 새로운 행렬이 추가되며 다음날부터는 기존 행렬로 행의 크기가 계속해서 커집니다. 그림 2는 양방향 스트리밍 상황에 대한 예시를 보여줍니다.
그림 2. 양방향 스트리밍 상황(Dual-way streaming setting).
Goal & Limitations of Previous Works
본 논문에서의 목표는 기존 행렬들의 새로운 행들이 추가됨과 동시에 새로운 행렬들이 들어오는 양방향 스트리밍 상황에서 효율적인 PARAFAC2 분해를 수행하는 것입니다. 그림 3은 효율적인 분해에 대한 예시를 보여줍니다. 또한, 최근 데이터에 더욱 적합한 분해 결과를 얻습니다. 많은 기존 PARAFAC2 분해 방법들이 주어진 불규칙 텐서를 효율적으로 분해하기 위해 노력하였습니다. 하지만, 대부분의 방법들은 정적인 상황에서 주어진 전체 텐서를 분해하는 것에 초점을 맞추고 있기 때문에 새로운 데이터가 들어올 때마다 전체 텐서에 대한 분해를 수행해야 합니다. 따라서, 이러한 방법들은 시간이 지남에 따라 분해 시간이 점진적으로 증가합니다. 스트리밍 상황을 처리하는 PARAFAC2 분해 방법이 존재하지만 이 방법은 새로 들어온 행렬에 대해서만 처리할 수 있기 때문에, 기존 행렬들의 새로운 행들에 대한 처리 효율성은 높이지 못했습니다.
그림 3. 양방향 스트리밍 상황에서의 효율적인 분해.
양방향 스트리밍 상황에서 효율적이고 정확하게 불규칙 텐서를 분해하기 위해서는 어떻게 해야 할까요?
Proposed Method
본 문서에서는 양방향 스트리밍 상황에서 빠르고 정확하게 분해를 수행하는 PARAFAC2 분해 방법인 Dash를 제안합니다. Dash는 이전에 들어온 데이터와 관련된 계산을 철저히 피함으로써 효율성을 높이며, 망각 요인 인자를 활용하여 분해 결과가 최근 데이터에 더욱 맞춰질 수 있도록 학습합니다.
양방향 스트리밍 상황에서 PARAFAC2 분해를 단순히 계산하게 되면 누적된 전체 텐서와의 계산을 피할 수 없습니다. 따라서, 시간이 지나 데이터가 계속해서 누적됨에 따라 분해 시간도 계속해서 증가합니다. 새 데이터가 들어왔을 때 분해하는 시간이 전체 텐서의 크기에 비례하는 것을 피하기 위해서는 이전 데이터와 관련된 계산을 철저히 피해야 합니다. 본 논문에서는 1) 이전 데이터와 관련된 계산과 새 데이터와 관련된 계산을 철저히 분리하고, 2) 새 데이터와 관련된 계산을 수행하고, 3) 이전 데이터와 관련된 계산을 추가계산없이 재활용하고, 4) 두 계산 결과를 활용하여 분해 결과를 업데이트합니다. N번째 업데이트에서 이전 데이터와 관련된 계산을 필요한 형태로 저장해두고 N+1번째 업데이트에서 추가계산없이 활용합니다. 구체적인 내용은 논문(링크)에서 확인할 수 있습니다.
실시간으로 데이터가 들어오는 상황에서는 오래된 데이터의 정보를 점차적으로 버리고 새 데이터의 패턴에 더욱 초점을 맞추어 분석을 수행하는 것이 필요합니다. Dash는 망각 인자(forgetting factor)를 활용하여 분해 결과에서 오래된 데이터에 대한 정보의 비율을 줄입니다. 망각 인자는 0에서 1사이 값을 가지는 하이퍼파라미터로 오래된 데이터와 관련된 항에 추가됩니다.
Dash를 통해 양방향 스트리밍 상황에서 불규칙 텐서를 실시간으로 분석할 수 있게 되어 본 논문에서는 Dash를 활용하여 실시간 이상 탐지 응용을 수행합니다. 크게 행렬 레벨의 이상 탐지와 텐서 레벨의 이상 탐지를 수행합니다. 텐서 레벨 이상 탐지는 새로 들어온 텐서에 대해 분해 결과를 업데이트하고, 업데이트된 분해 결과를 활용하여 복원 에러를 측정합니다. 복원 에러가 크다면 새 데이터의 패턴이 이전에 들어온 데이터들의 패턴과 크게 다르다고 해석할 수 있습니다. 행렬 레벨 이상 탐지도 유사하게 새로 들어온 텐서에 대해 업데이트를 수행한 후 각각의 행렬에 대한 복원 에러를 측정합니다. 각 행렬별로 복원 에러가 크면 이상 패턴으로 판단합니다.
Experiment
본 문서에서는 Dash의 분해 속도 평가, 확장성 평가, 이상 탐지 응용에 대해 설명합니다. 먼저 그림 4의 (a)와 (b)는 주식 데이터에서 새로운 데이터가 들어올 때마다 분해 결과를 업데이트하는 시간을 측정한 결과입니다. 각 업데이트에서 Dash의 실행시간은 새로 들어온 데이터의 크기에 비례합니다. 기존 PARAFAC2 분해 방법들은 데이터가 계속해서 누적됨에 따라 분해 시간이 점차적으로 증가하는 것을 확인할 수 있습니다.
그림 4. (a-b) 계산 시간 비교, (c-d) 확장성 평가, (e) 이상 탐지 응용.
마지막으로 그림 4의 (e)는 Dash를 활용하여 이상 탐지를 수행한 결과입니다. 미국 주식 데이터에 대해 20일마다 결과를 업데이트하였으며, 업데이트한 결과의 복원 에러를 측정하고 측정된 에러가 임계값보다 클 때 anomaly로 판별하였습니다. 그림에서처럼 가장 큰 차이를 보이는 부분을 살펴보니, 닷컴 버블, 경제 위기, 코로나 시기와 관련이 있었습니다.
Conclusion
본 문서는 KDD 2023에서 발표될 "Fast and Accurate Dual-Way Streaming PARAFAC2 for Irregular Tensors - Algorithm and Application" 논문을 소개합니다. 본 논문은 기존 행렬들의 행들이 새로 추가됨과 동시에 새로운 행렬들이 추가되는 양방향 스트리밍 상황에서 효율적이고 정확하게 텐서를 분해하는 방법인 Dash를 제안합니다. 제안 방법은 기존 데이터와 관련된 계산과 새 데이터와 관련된 계산을 주의깊게 분리하고 기존 데이터와 관련된 계산을 추가 계산없이 재활용합니다. 이 덕분에, 분해 시간이 새로 들어온 데이터의 크기에 비례합니다. 추가적으로, 망각 인자를 활용하여 분해 결과가 최근 데이터를 더 잘 복원할 수 있도록 학습됩니다. Dash는 양방향 스트리밍 상황에서 기존 PARAFAC2 방법에 비해 훨씬 효율적으로 분해를 수행하며, 실세계 데이터에서 효과적으로 이상 패턴을 탐지합니다. Dash는 실세계 양방향 스트리밍 상황에서 이상 탐지뿐만 아니라 요인 분석, 유사도 탐색 등 다양한 실시간 분석을 가능하게 할 것이라 기대합니다. 구체적인 정보는 (링크)에서 확인할 수 있습니다.