1. Abstract
Spatio-temporal point process(STPP)란 시간, 공간에 따른 사건의 stochastic collection이다. 계산 복잡도를 고려하여, 기존의 시공간 통계학에서는 시간과 공간(time and space)의 conditional independence를 활용하여 distribution을 따로 구해 STPP의 solution을 도출하였다 (시간을 modeling하기 위해 Poisson process, Hawkes process 등이 사용되며 공간을 modeling하기 위해 kernel density estimator가 사용된다).
그러나 이들은 시공간을 통합하는 joint distribution을 구하지 못하는 것이 제한된 성능을 발휘할 수 밖에 없다고 생각한다 (예를 들어 지진의 발생은 이전 지진과 가까운 지역 및 시간대에 발생한다). 따라서 이를 극복하기 위해 STPP의 parameteriazaion framework를 diffusion model을 사용하여 제안한다.
Diffusion model의 input으로 spatial, temporal domain의 embedding 값을 구하여 사용하였으며, diffusion model을 통해 최종적으로 그들이 얻고자 하는 것은 hidden representation이 given 되었을 때 origial time and space를 estimate한 time and space이다.
2. Difficulties to derive spatio-temporal joint distributions
시공간의 joint distribution을 구하는 것은 아래와 같은 두가지의 이유로 쉽지만은 않다.
- 시공간 joint distribution for STPPs는 sample space가 매우 거대하며, 이는 intractable하다. 따라서 우선 temporal density $p^*(t)$를 fitting한 후에 conditional density $p^*(s\mid t)$를 순차적으로 fitting하는 방법이 있으나, $p^*(s \mid t)$는 특정 model structure (KDEs, CNFs 등)에 제한된다.
- 사건의 발생은 시공간 사이의 복잡한 correlation과 연관이 있다. 다양한 분야에서 발생한 사건은 그 분야에 따라 distinct한 spatio-temporal dependencies를 가진다. 따라서 대부분의 문제에 들어맞는 근본적인 시공간 dependence를 capture하는 방법이 필요하다.
따라서 이들은 새로운 parameterization framework인 Spatio-Temporal Diffusion Point Processes (DSTPP)를 제안한다. 간단히 아이디어를 설명하자면 diffusion 방법의 denoising probabilistic modeling을 활용하여 original complex distribution을 Markov chain of multiple steps로 decompose한다.
3. Spatio-temporal diffusion point processes
이들이 제안한 framework는 위와 같다. 크게 2개의 key module, spatio-temporal self-attention encoder와 spatio-temporal diffusion model로 구성되어 있다.
3.1 Spatio-temporal Encoder
이 단계는 spatio-temporal data를 embedding하고, hidden representation을 추출하는 과정이다. 시공간 데이터를 input하면 embedding layer와 attention layer를 거쳐 hidden representation을 반환한다. 저자들은 이 과정을 Encoding으로 생각하여 Encoder라고 표현한 듯 하다.
우선 시간을 embedding하는 방식은 아래와 같다. $M$은 embedding dimension이며 따라서 $e_t$가 temporal embedding을 나타낸다.
$$[e_t]_j = \begin{cases} \cos(t/10000^{\frac{j-1}{M}}) \text{ if j is odd} \\ \sin(t/10000^{\frac{j-1}{M}}) \text{ if j is even} \end{cases}$$
공간은 다음과 같이 embedding한다. $W_e$는 학습가능한 parameter를 포함하며 공간이 continuous domain인 경우 (like 좌표 데이터)와 discrete domain인 경우 (like lattice data)에 모두 사용 가능하다.
$$e_s = W_e s$$
또한 위 두개의 embedding 결과를 더하여 spatio-temporal embedding $e_{st}$를 정의할 수 있다.
결과적으로, 시공간 데이터 $S = \{(t_i, s_i)\}_{i=1}^L$에 대해 시공간 embedding $E_{st} = \{e_{st,1},\dots,e_{st,L}\}$, 시간 embedding $E_s = \{e_{t,1}, \dots, e_{t,L}\}$, 그리고 공간 embedding $E_s = \{e_{s,1}, \dots, e_{s,L}\}$을 얻을 수 있다.
그 다음 목표는 이 3가지의 embedding을 활용하여 서로다른 시공간마다의 characteristic을 capture하는 것이다. 따라서 논문의 (7), (8)번 수식을 통해 embedding vector들의 연산을 하고 최종적으로 spatial, temporal, and spatio-temporal 각각에 대한 hidden representation에 대해 얻을 수 있게 된다.
3.2 Spatio-temporal Diffusion and Denoising Processes
위에서 hidden representation, $h_{i-1}$을 얻은 그 다음의 목표는 hidden representation을 conditioning하여 미래 event에 대한 spatio-temporal joint distribution의 model을 학습하는 것이다. 그리고 여기에 diffusion model을 활용하였다.
이들은 space와 time에 각각 noise를 더하고 이를 복원하는 식으로 diffusion process와 reverse process를 진행하였다. 각 event $x_i =(\tau_i, s_i), \text{ (where } \tau_i \text{ denotes the time interval since the last event) }$에 대해 diffusion process modeling을 위해 K번의 diffusion process를 거친 Markov process $(x_i^0, x_i^1, \dots, x_i^K)$를 적용하였다. 각 diffusion step에 Guassian noise를 더해가는 과정을 다음과 같이 쓸 수 있다.
$$q_{st}(x_i^k \mid x_i^{k-1}) = (q(\tau_i^k \mid \tau_i^{k-1}),q(s_i^k \mid s_i^{k-1})), \\q(x^k \mid x^{k-1}) = N(x_k ; \sqrt{1-\beta_k}x^k, \beta_k \mathbf{I})$$
반면 noise를 제거해가며 원본 data $x_i = (\tau_i, s_i)$를 복원하는 과정, reverse process는 hidden representation을 condition으로 아래의 분포를 얻는 과정이다.
$$p_\theta(x_i^{k-1} \mid x_i^k, h_{i-1}) = p_\theta(\tau_i^{k-1} \mid \tau_i^k, s_i^k, h_{i-1})p_\theta(s_i^{k-1} \mid \tau_i^k, s_i^k, h_{i-1})$$
이전 event까지의 hidden representation을 given하여 다음 event의 시간과 공간의 joint distribution을 서로 conditionally independent하게 만들 수 있다는 의미인 듯 하다.
따라서 위 방법을 사용하여 diffusion model을 train하고, trained model을 사용하여 real data $(\tau_i^0, s_i^0)$에 대한 prediction값을 얻을 수 있다. 또한 이 prediction에서 중요한 것은 co-attention denoising network를 사용했다는 점이다. 이는 spatial과 temporal domain의 상호의존성을 capture하기 위함이며 3.4에 자세히 나와있다.
4. Experiments
이들은 real dataset과 synthetic dataset에서 다양한 실험을 진행하였다. 그 중 몇가지의 과정과 결과만 살펴보자. 이들은 Earthquakes, COVID-19 등의 real datasetrhk HawkewGMM의 synthetic dataset을 사용하였으며 이들이 구한 model vs 기존의 baseline model에서의 모델 성능을 두가지 측면으로 비교하였다. 첫번째는 space와 time각각의 negative log-likelihood를 구하여 비교하는 것이고, 두번째는 time은 RMSE, spatial location은 Euclidean distance를 계산하여 비교한 것이다.
결과를 살펴보면 이들의 model DSTPP는 모든 dataset에서 가장 뛰어나거나 두번째로 뛰어난 성능을 보였다. 기존의 NSTPP와 같은 conditional distribution을 사용하여 시공간의 distribution을 구하는 방식은 spatial 측면에서는 시간과 공간의 independence를 가정하고 modeling한 결과보다는 뛰어났지만, temporal 측면에서는 temporal modeling만 사용한 다른 방식들에 비해 아주 뛰어난 성능을 보이지는 않았다. 이러한 방법도 시공간의 joint distribution을 구한 것은 동일하지만 temporal domain은 잘 학습하지 못함을 보여주는 결과였다.
References:
Yuan, Y., Ding, J., Shao, C., Jin, D., & Li, Y. (2023, August). Spatio-temporal diffusion point processes. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 3173-3184).