A Kernel Two-sample Test for Dynamical Systems

Friedrich Solowjow, Dominik Baumann, Christian Fiedler, Andreas Jocham, Thomas Seel, Sebastian TrimpearXiv 2020 · arXiv

Introduction

In statistical machine learning, the two-sample test is a foundational tool used to determine whether two sets of data are drawn from the same underlying probability distribution. While the Kernel Two-Sample Test is highly effective for independent and identically distributed (i.i.d.) data, its performance degrades significantly when applied to dynamical systems, such as those found in robotics, economics, or human biomechanics.

The primary challenge in these contexts is autocorrelation. In a dynamical system, the current state is heavily dependent on previous states. This violation of the independence assumption leads to "clustering" in data samples, which biases standard statistical tests. Consequently, standard tests often report significant differences between samples where none exist, leading to an explosion of false positives. Historically, researchers addressed this by manually engineering features or relying on untestable assumptions regarding how quickly a system "forgets" its past. This paper proposes a robust, model-free framework to perform two-sample tests on non-independent data streams.

Methodology: The MMD-Mixing Framework

The authors introduce a data-driven approach that bridges the gap between kernel methods and dynamical systems theory through three key components:

1. MMD-Mixing

The researchers define a new notion of "mixing" specifically tailored for the Maximum Mean Discrepancy (MMD) metric. Mixing refers to the rate at which a system's state becomes independent of its history. By aligning the mixing definition with the MMD metric, the authors ensure that the estimation of independence is directly relevant to the final statistical test.

2. Time-Shift Estimation via HSIC

To handle temporal dependencies, the method utilizes the Hilbert-Schmidt Independence Criterion (HSIC). HSIC measures the dependence between samples at different time intervals. This allows the framework to calculate an optimal time shift ($a^*$)—the minimum duration one must wait between samples to treat them as "approximately independent."

3. Theoretical Guarantees

The paper provides a new theoretical foundation (Theorem 3) that adjusts the significance level ($\alpha$) of the standard kernel test. This adjustment accounts for the residual dependencies ($\epsilon$) that remain even after time-shifting, ensuring the test maintains its integrity despite the non-i.i.d. nature of the raw data.

Experimental Evaluation

The proposed method was evaluated across three distinct regimes to test its versatility and precision:

  • Synthetic Linear Time-Invariant (LTI) Systems: 500 randomly generated systems were used to validate the necessity of the time-shift $a^*$ and the precision of the adjusted test.
  • Chaotic Systems: The method was tested on the classical Lorenz Attractor and various "C-mixing" maps (including $\beta$-map, Logistic map, and Gauss map). These experiments proved that the framework remains effective even on deterministic, non-stochastic chaotic data.
  • Human Walking Data: In a real-world application, the authors analyzed 3-axis gyroscopic IMU data from 38 healthy subjects walking on a treadmill. To simulate a pathological gait, subjects wore a knee orthosis to restrict joint movement, creating a subtle but measurable change in the dynamical system.

Key Results and Insights

The framework demonstrated superior performance in identifying system changes without the need for manual feature extraction:

  • Gait Anomaly Detection: The MMD-based method achieved 95.7% accuracy in identifying the presence of the knee orthosis. This significantly outperformed standard classifiers trained on hand-picked features, such as Support Vector Machines (86.9%) and Logistic Regression (92.5%).
  • Precision and Robustness: In synthetic LTI experiments, the test maintained high precision, resulting in only 4 false positives out of 500 trials. This confirms that the theoretical adjustments for $\epsilon$-independence effectively control the type-I error rate.
  • The Danger of Naive Sampling: A critical insight from the study is that ignoring the dynamical nature of data is catastrophic; sampling too quickly without accounting for mixing causes the false positive rate to explode, rendering standard tests useless.

Limitations and Future Directions

While robust, the method has specific requirements:

  • Data Volume: Because the test requires "waiting" for the system to mix (the time shift $a^*$), it necessitates longer data streams than standard i.i.d. tests. Systems that mix slowly may require more data than is practically available.
  • Stationarity: The framework assumes the system has converged to a stationary distribution. It is not yet optimized for systems with heavy transient behavior or those that are fundamentally non-stationary.

Future work aims to explore more data-efficient concentration inequalities to reduce the data volume required for a conclusive test. Additionally, the authors intend to apply this framework to "digital twins" in engineering, verifying the accuracy of complex simulations against real-world hardware performance.

Summary updated

Abstract

Evaluating whether data streams are drawn from the same distribution is at the heart of various machine learning problems. This is particularly relevant for data generated by dynamical systems since such systems are essential for many real-world processes in biomedical, economic, or engineering systems. While kernel two-sample tests are powerful for comparing independent and identically distributed random variables, no established method exists for comparing dynamical systems. The main problem is the inherently violated independence assumption. We propose a two-sample test for dynamical systems by addressing three core challenges: we (i) introduce a novel notion of mixing that captures autocorrelations in a relevant metric, (ii) propose an efficient way to estimate the speed of mixing relying purely on data, and (iii) integrate these into established kernel two-sample tests. The result is a data-driven method that is straightforward to use in practice and comes with sound theoretical guarantees. In an example application to anomaly detection from human walking data, we show that the test is readily applicable without any human expert knowledge and feature engineering.
BibTeX
@misc{solowjow2020kernel,
  author = {Friedrich Solowjow and Dominik Baumann and Christian Fiedler and Andreas Jocham and Thomas Seel and Sebastian Trimpe},
  title = {{A Kernel Two-sample Test for Dynamical Systems}},
  year = {2020},
  eprint = {2004.11098},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.11098},
}
Figure