Towards Understanding Evolving Patterns in Sequential Data

Responses to Weakness

1. (Cost function) The cost function of Optimal Transport (OT) is defined in Eq (7). In the literature [1-2], OT typically uses a distance metric between two samples, each sampled from different marginal distributions, as the cost function. For instance, $z^s$ and $z^t$ represent data from source and target domains in domain adaptation tasks [1-2]. In our approach, we account for the dynamic characteristics of sequential data. Specifically, we assume the presence of an autoregressive function $f$ that governs the evolving patterns within the data. Consequently, we design the cost function as the distance between the output of $f$ with historical samples as input $f(\**z**^t_{t-k+1})$, and the subsequent sample $z_{t+1}$. In our implementation, OT aims to find the matching between a batch of samples $\\{z_{t,i}\\}^B_{i=1}$ and $\\{z_{t+1,i}\\}^B_{i=1}$ in a training iteration across time steps.

2. (parameter and architecture) Thanks for pointing it out. We will add this detail in the revision. The autoregressive model $f$ is typically a 2 or 3-layer LSTM, with input size, hidden size, and output size set to 128, 256, or 512, depending on the architecture of the encoder $g$. For tabular data, $g$ is a 2 or 3-layer MLP, with the input size corresponding to the data size, and the hidden and output sizes set to either 128 or 512. For image data, $f$ is a ResNet-12 with a hidden size of 512.

Q: (choose the cost function) We do not select the cost function; rather, we use a cost function that is consistent with the critic function as an autoregressive form in mutual information estimation, which leverages the structure of sequential data.

[1] Optimal Transport for Domain Adaptation, TPAMI 2015

[2] Joint distribution optimal transportation for domain adaptation, NIPS 2017

Responses to Weakness:

1. (scalability & training an auto-encoder) We have added experiments on the scalability of the method with different dimensions in the encoding space using the Video Prediction dataset KITTI.

   Encoding Dim	128	256	512	1024
   EvoRate	2.19	2.37	2.47	2.56

   From the above table, a smaller dimension in the encoding space leads to a lower EvoRate due to greater information loss. However, the performance remains acceptable even with a very low dimension of 128.

   Training an auto-encoder model from scratch can be computationally expensive. However, we can use a pretrained backbone, significantly reducing computational costs by directly learning the dynamic function $f$ from the encoded embeddings.

   Corruption Ratio	0	0.05	0.1	0.25	0.5
   Finetune $g$	2.56	1.52	0.93	0.37	0.05
   Pretrained&fixed $g$	2.54	1.55	0.92	0.39	0.10

   The Corruption Ratio represents the probability of shuffling the sequence to disrupt the evolving patterns. A higher Corruption Ratio should result in a lower EvoRate. We find that with a fixed pretrained encoding function $g$, the estimated EvoRate closely approximates the result of training $g$ with EvoRate on the video dataset KITTI. The pretrained model used is ResNet-18 from torchvision, pretrained on ImageNet-1K.

2. (Absence of real-world datasets) We have utilized real-world datasets: five time-series forecasting datasets presented in Table 2, three EDG datasets (Portraits, Caltran, and Powersupply) in Table 3, and one video prediction dataset (KITTI) in Figure 2-c. Additionally, we included the experimental result of EvoRate on the NLP dataset Associative Recall from zoology [3]. A low EvoRate for the NLP dataset implies either a low prediction potential or that this dataset alone cannot be used to train a good predictive model. Notably, the test accuracy of AR is typically 100%, which is consistent with the high EvoRate of 2.93.

   Corruption Ratio	0	0.25	0.5	0.75	1
   EvoRate	2.93	1.52	1.28	1.18	1.04

3. (True MI are not able to obtain) We acknowledge that for real-world high-dimensional data, MI is often intractable, as highlighted in the literature [1]. However, our experimental results demonstrate that we can achieve a reasonable estimation of MI, as illustrated in Figure 1. Similar to the approach of ForeCA, we use an information-theory-based estimator as an indicator of evolving patterns. While ForeCA uses entropy, we use a mutual information estimator.

Responses to Questions:

1. (MI to evaluate evolution of patterns) Using MI to estimate the relationship between pairs of variables is a fundamental problem in science and engineering. We propose to leverage MI to quantify the strength of the evolving patterns, which reveals that the evolving patterns is strongly related to the latent temporal dependency. We justify our choice of using MI to measure evolving patterns in Section 4.2 and Proposition 1. Specifically, MI is an intrinsic property of the data that directly influences the expected error of the maximum likelihood estimation loss. Therefore, we claim that MI serves as a direct and reliable indicator of evolving patterns.

2. (Why EvoRate better than ForeCA) This limitation is due to ForeCA's inability to detect complex patterns, as illustrated in lines 112-114 of our paper. While temporal patterns can encompass trends, cycles, irregular fluctuations, and more complex behaviors, ForeCA is restricted to detecting only simple linear cyclical patterns. In his paper [2], he assumes that the data from future time steps is a linear transformation of the historical data. However, our methods can leverage MI-guided efficient deep representation learning to describe complex and non-linear evolving patterns.

3. (apply to new datasets without finetuning) We acknowledge that the current EvoRate model can utilize a fixed pre-trained encoder $g$ to project data into a lower dimension to reduce computational complexity. However, the autoregressive function $f$ in Eq (4) and (9) still requires fine-tuning for each dataset due to the distinct evolving patterns present in different datasets. Nonetheless, training a larger EvoRate model with more datasets could potentially result in a more robust model capable of testing evolving patterns across various datasets. This is a promising direction for our future research.

[1] Estimating mutual information. Physical Review 2004

[2] Forecastable component analysis. ICML 2013

[3] Zoology: Measuring and Improving Recall in Efficient Language Models, Arxiv 2023

1. (EDG setting) We thank you for pointing it out and will include an illustration of the Evolving Domain Generalization (EDG) setup. A brief explanation of EDG can be found in lines 328-330. More specifically, The EDG tasks setup involves using the training dataset $D_S = \\{ \\{ x_{t,i}, y_{i,t} \\}^N_{i=1} \\}^M_{t=1}$, where $x_{i,t}$ and $y_{i,t}$ represent the data and its label of the $i$-th sample at time $t$ respectively and $N$ is the sample size, to learn a function that can predict the class of samples from future timestamps, which are then evaluated on the test dataset $D_T = \\{ \\{ x_{i,M+t}, y_{i,M+t} \\}^N_{i=1}\\}^L_{t=1}$.

2. • (a: learning performance) Thanks for pointing it out. The term "learning performance" refers to the performance of approximating MI using the trained EvoRate, which is parameterized by the learned autoregressive function $f$ and the encoder function $g$.

   • (b: trade-off between complexity and performance) When the original dimension of the data $D$ equals the dimension of the encoded data's embedding $d$, it provides the most precise MI estimation, comparable to the computational cost of directly training a deep autoregressive model. On the other hand, when $d \ll D$, the estimated precision is lower but more computationally efficient. Specifically, if we directly load a pretrained model for $g$, we only need to train $f$, which is typically only composed of multi-layer perceptrons (MLPs).

   • (c: why measure MI instead of relying on the predictive performance) As pointed out in (b), setting $d \ll D$ makes EvoRate efficient in estimating MI compared to training a deep autoregressive model in the original high dimension, especially for high-resolution videos. The key is to estimate MI in the latent encoding space. We can trade off some precision of EvoRate due to the Data Processing Inequality [1] for computational cost efficiency. We provide additional experimental results with the KITTI dataset:

     Corruption Ratio	0	0.05	0.1	0.25	0.5
     Finetune $g$	2.56	1.52	0.93	0.37	0.05
     Pretrained&fixed $g$	2.54	1.55	0.92	0.39	0.10

     In the above table, the Corruption ratio represents the probability of shuffling the data sequence, where a high ratio leads to a degradation of evolving patterns.

3. (pseudocode) We have included the pseudocode in the global response PDF and will add it to the revised version of the paper.

4. (NLP tasks) We further experiment with EvoRate on the NLP dataset Associative Recall (AR) in zoology [4], and the results are shown below. Due to time limit, we choose this simple synthetic dataset for our experiments. EvoRate is estimated between the historical sequence and its query's recall. A low EvoRate for the NLP dataset implies either a low prediction potential or that this dataset alone cannot be used to train a good predictive model. Notably, the test accuracy of AR is typically 100%, which is consistent with the high EvoRate of 2.93, indicating strong predictive performance..

   Corruption Ratio	0	0.25	0.5	0.75	1
   EvoRate	2.93	1.52	1.28	1.18	1.04

5. ($f$ will converge to $f^*$) In Lemma 1, we show that with our defined autoregressive cost function, if $f$ attains $f^*$, the estimated joint distribution $\pi^*$ will converge to the real distribution. Furthermore, it is a common practice to estimate the joint distribution with optimal transport to build the correspondence, as demonstrated in [2,3]. However, proving the convergence of $f$ to $f^*$ is challenging, and we will try to address this in future research.

6. (Synthetic experiments) For more complex transition functions, the analytical mutual information value is intractable, as there are no methods to compute the ground truth MI value quantitatively. For datasets with correspondences, we test EvoRate on real-world time series forecasting datasets Crypto, Player Traj., M4-Monthly, M4-Weekly, M4-Daily, and video prediction KITTI dataset.

7. (typos) Thank you for pointing them out, and we will revise the paper accordingly.

[1] Elements of information theory. John Wiley & Sons, 1999

[2] Joint distribution optimal transportation for domain adaptation, NIPS 2017

[3] Optimal Transport for Domain Adaptation, TPAMI 2015

[4] Zoology: Measuring and Improving Recall in Efficient Language Models, Arxiv 2023

• W1 & Limitation (motivation is not very clear) - Our motivations and contributions: Our work's contribution is three-fold:

  • It is theoretically motivated by the use of MI to estimate evolving patterns.
  • It applies a specially designed similarity critic that considers the autoregressive manner.
  • For cases where data is sampled at each timestamp and lacks correspondence, we propose methods to approximate the absent correspondence between timestamps with optimal transport (OT), thus enabling EvoRate estimation.

• W1 & Q1 (benefit of introducing MI) - Why we use MI: We justify our choice of using MI in Section 4.2 and Proposition 1. Specifically, we show that a larger MI leads to a smaller expected maximum likelihood estimation (MLE) loss, which indicates better autoregression performance. As shown in Eq (5), the expected risk can be decomposed into two terms: the first term is related to the prediction model, and the second term, $H(Z_{t+1}) - I(Z_{t+1};**Z**^t_{t-k+1})$, is only related to the data. Since the inequality $H(Z_{t+1}) \ge I(Z_{t+1}; **Z**^t_{t-k+1})$ always holds, minimizing the prediction risk in autoregressions requires MI to be as close as possible to $H(Z_{t+1})$. The insight behind achieving equality is that we can predict the future state $Z_{t+1}$ if we have complete information about the historical states $**Z**_{t-k+1}^t$. Consequently, we argue that MI serves as a direct and reliable indicator of evolving patterns. Based on this conclusion, our experiments aim to show that EvoRate can effectively approximate MI in sequential data.

• W1 & Q1 (comparing to existing works) - Advantages over the existing work: The problem of evolving patterns in sequential data is under-studied, and to the best of our knowledge, the only related work is ForeCA [1]. However, ForeCA relies on the spectral entropy of data and assumes linear dependency between historical information and future states. Consequently, it can only detect the cyclical pattern and cannot serve as an indicator of complex evolving patterns. Moreover, ForeCA cannot be applied to high-dimensional data, limiting its use for many real-world datasets. EvoRate addresses these issues by MI-guided efficient deep representation learning, and its effectiveness is justified in Table 1 of our paper. More discussions of the benefits of EvoRate over ForeCA are also presented in lines 106-116 of our paper. We also include three statistic indicators for time series in global response.

• Q1 (how to use results of identification of evolving patterns): There are various applications:

  • a) Model selection (sequential vs. static): By establishing an empirical threshold for EvoRate, we can determine the appropriate model for predictions. If EvoRate exceeds the threshold, a sequential model is recommended. Conversely, if EvoRate is below the threshold, indicating a lack of temporal patterns (e.g., coin tossing), a static model should be used. For example, based on the results in Table 3, we should apply a static model for the Portraits and Caltran datasets.

  • b) Temporal order estimation: EvoRate can be used to estimate the temporal order in the data. From Table 1, we suggest building a temporal model with a temporal order of 90 can achieve optimal performance, as EvoRate values for orders 180 and 270 are very close to that of 90.

  • c) Temporal feature selections: EvoRate can be used for feature selection for temporal prediction tasks, allowing for efficient and explainable model training by excluding redundant or irrelevant features, as shown in Figure 2-b.

  • d) Evolving domain generalization (EDG): EvoRate naturally acts as a regularizer to enhance the performance of learning dynamics in sequential data, as verified in EDG tasks in Table 4.

  • e) We further experiment with EvoRate on the NLP dataset Associative Recall (AR) of zoology [4]. The results indicate that a low EvoRate for the NLP dataset implies either a low prediction potential or that the dataset alone cannot be used to train a good predictive model. EvoRate is estimated between the historical sequence and its query's recall.

    Corruption Ratio	0	0.25	0.5	0.75	1
    EvoRate	2.93	1.52	1.28	1.18	1.04

    The Corruption ratio represents the probability of shuffling the data sequence. A high ratio leads to a degradation of evolving patterns, resulting in a lower EvoRate. This is consistent with the results shown in the above table. Notably, the test accuracy of the AR dataset is normally 100%, which aligns with its high EvoRate of 2.93.

• Limitation (EvoRate is edited MI): There are two major differences between EvoRate and existing MI estimation methods (e.g., [5-6]): 1) Existing MI estimation methods are designed for static data, and their concatenated and separable critic functions directly compute the similarity between embeddings in two different domains. In contrast, EvoRate leverages an autoregressive critic function to efficiently account for the structure of sequential data by mapping historical states to the next state and computing similarity in the domain of the next state. As a result, EvoRate underestimates the ground truth MI values of sequential data, as shown in Figure 1-b. 2) Existing MI estimation methods do not account for sequential data without correspondences, and hence cannot directly estimate MI in such cases. EvoRate$_W$ mitigates this issue by building correspondence with optimal transport (OT). However, even with OT, existing MI estimation methods still fail to estimate MI for sequential data due to limitations in their critic functions, as shown in Figure 1.

[1] Forecastable component analysis

[2] Lyapunov exponents

[3] Testing stationarity in time series

[4] Measuring and Improving Recall in Efficient Language Models

[5] Mutual information neural estimation

[6] A contrastive log-ratio upper bound of mutual information