Spectral structure learning for clinical time series

The gist The development and evaluation of a structure learning algorithm for clinical time series involves developing StructGP, a structured multi-task Gaussian process, which encodes ordered conditional relations between time series represented in a directed acyclic graph, and implementing an adapted NOTEARS algorithm to recover this graph by solving continuous optimization problems

Structured Gaussian Process

The paper introduces StructGP as a k-dimensional multi-output or multi-task stationary Gaussian process (GP) that encodes ordered conditional relations between time series, represented in a directed acyclic graph (DAG) This GP is defined by the filtration of white noise wptq by Hptq, where Hptq is a sparse k x k lower triangular matrix-valued impulse response function Taking the Fourier transform of Yptq yields Zpωq, a non-stationary complex white noise multi-output process defined by Equation 1 The covariance of Zpωq or spectral density is given by Equation 2, where H˜ pωq is identified as the Cholesky factor of the covariance matrix of Zpωq The sparsity pattern of H parameterizes ordered conditional relations between time series, and this support can be interpreted as the adjacency matrix of a directed acyclic graph (DAG) G that encodes ordered conditional independence relation Furthermore, the distribution PpYq satisfies the Markov factorization property with respect to the graph G, stated in Theorem 2.49

Learning the Graph

The method switches to a set-based indexing for irregularly sampled data from multiple patients, where each observation is indexed by a triplet composed of the patient index i, task index j, and time t, denoted as x = pi, j, tq The intra-patient covariance of the process for patient i can be written as CovrYpi, u, tq, Ypi, v, t1qs = phu ˚ hT v qpt ´ t1q With classical GP, the set of free parameters θ = (tS, Lu) is learned by maximizing the marginal likelihood of the training observations y given inputs X, denoted as log ppyX, θq To learn the graph, order of tasks, and sparsity pattern within structured GP, the NOTEARS algorithm is followed to learn S and impose an acyclicity constraint on S The objective is to solve the constrained optimization problem: theta˚ = argmin θ´ log ppy, X, θq λ S s.t. TrpexppS ˝ Sqq ´ k = 0 This is solved using dual ascent following the augmented Lagrangian method The primal problem is solved with a proximal gradient method (PGM), and the dual problem is solved by gradient ascent

Simulation Study

The simulation study assesses the algorithm's accuracy by comparing the predicted graph Gˆ with the true simulated graph G using structural hamming distance (SHD) and root mean square error (RMSE) The comparison is made against a random graph from the same distribution as simulated The support of S is sampled from a random (Erdos–Rényi) graph in which the sparsity level is controlled by the mean degree md In EXP3 simulations, varying the number of tasks shows that 4 tasks yield a median recall of 0.93% [IQR, 0.86, 0.97] while keeping a median precision of 0.71% [0.57-0.84] for recovering directed edges

Discussion

The developed algorithm learns ordered conditional independence relations between irregularly sampled time series, parametrized by StructGP, which assumes an invariant structure across continuous frequencies and is built upon a differentiable definition of acyclicity The work aims to recover the true graph by solving a series of continuous optimization problems with high sensitivity and good precision on simulated data The paper notes that the recent work by Dallakyan [14] develops an algorithm imposing a Gaussian linear additive SCM on the discrete Fourier transform, but they learn different weight matrices at each frequency, whereas this study assumes an invariant structure across continuous frequencies parametrized by only one weight matrix The authors suggest that more work is needed regarding the sensitivity to standardization and unmeasured cofounders in real-world data

List of Abbreviations

DAG directed acyclic graph 1, 2, 4 EHRs Electronic Health Records 1 GP Gaussian process 1–3, 5 nmll negative marginal log-likelihood 4 NOTEARS Non-combinatorial Optimization via Trace Exponential and Augmented lagRangian for Structure learning.3 PGM proximal gradient method.3,9 RMSE root mean square error.3 SHD structural hamming distance.3,4 StructGP Structured Gaussian process.1,5 SVAR structural vector autoregressive models.1

Appendix

The paper provides details on conditional independence in Section 6.1 and the sparsity pattern of the precision matrix in Section 6.2 The sparsity pattern of the Cholesky factor of the covariance matrix is described in Section 6.3, showing how Lvu can be found in LS The augmented Lagrangian optimization algorithm is detailed in Section 6.4, outlining the primal solver and dual update steps The proximal gradient method is described in Section 6.5, defining the proximal operator for the non-differentiable part of the objective function The simulation study additional results are presented in Section 6.6

References

[1] Jonas Peters, Dominik Janzing, and Bernhard Schölkopf Elements of causal inference: foundations and learning algorithms The MIT Press, 2017

[2] Clark Glymour Kun Zhang Peter Spirtes Review of causal discovery methods based on graphical models Frontiers in genetics, 10:524, 2019

[3] Daphne Koller Nir Friedman Probabilistic graphical models principles and techniques MIT press, 2009

[4] Steffen L Lauritzen Graphical models, volume 17 Clarendon Press, 1996

[5] David Maxwell Chickering Optimal structure identification with greedy search Journal of machine learning research, 3(Nov):507–554, 2002

[6] Robert W Robinson Counting unlabeled acyclic digraphs In Combinatorial Mathematics V: Proceedings of the Fifth Australian Conference, Held at the Royal Melbourne Institute of Technology, August 24–26, 1976, pages 28–43 Springer, 1977

[7] Xun Zheng Bryon Aragam Pradeep Ravikumar Eric P Xing Dags with no tears Continuous optimization for structure learning arXiv preprint arXiv:1803.01422, 2018

[8] Roxana Pamfil Nisara Sriwattanaworachai Shaan Desai Philip Pilgerstorfer Konstantinos Georgatzis Paul Beaumont Bryon Aragam Dynotears Structure learning from time-series data In International Conference on Artificial Intelligence and Statistics, pages 1595–1605 PMLR, 2020

[9] Selva Demiralp Kevin D Hoover Searching for the causal structure of a vector autoregression Oxford Bulletin of Economics and statistics, 65:745–767, 2003 [ref:2502.11680.

1. Improved Causal Structure Discovery for Clinical Data: The improved system can learn the dependency structure of either time-independent variables or, in this study, time series, specifically recovering the directed acyclic graph (DAG) that encode[s] ordered conditional relations between time series. This allows the system to model complex causal pathways in EHR data.

2. Robustness to Irregular Sampling and Multivariate Observations: The algorithm is adapted for irregularly sampled multivariate time series from multiple patients, enabling it to handle real-world clinical data formats effectively where existing algorithms struggle.

3. Flexible Modeling of Time Series Regularity: By utilizing StructGP, the system can learn dependencies that flexibly adapt to different time series regularity, while enabling us to learn these dependencies from observations. This provides a more adaptable framework than models assuming fixed temporal properties.

4. High-Precision Graph Recovery via Differentiable Constraints: The use of an adapted NOTEARS algorithm, which based on a differentiable definition of acyclicity, enables the recovery of the graph by solving a series of continuous optimization problems. This suggests higher precision in identifying the structure compared to discrete methods.

5. Scalable Learning for Large-Scale Clinical Datasets: The framework can be scaled to handle large datasets, as it could be achieved, for instance, with GPU-friendly solvers that exploit block sparsity induced by independence between patients. This allows application to massive patient cohorts without prohibitive computational cost.

We develop and evaluate a structure learning algorithm for clinical time series. Clinical time series are multivariate time series observed in multiple patients and irregularly sampled, challenging existing structure learning algorithms. We assume that our times series are realizations of StructGP, a k-dimensional multi-output or multi-task stationary Gaussian process (GP), with independent patients sharing the same covariance function. StructGP encodes ordered conditional relations between time series, represented in a directed acyclic graph. We implement an adapted NOTEARS algorithm, which based on a differentiable definition of acyclicity, recovers the graph by solving a series of continuous optimization problems. Simulation results show that up to mean degree 3 and 20 tasks, we reach a median recall of 0.93% [IQR, 0.86, 0.97] while keeping a median precision of 0.71% [0.57-0.84], for recovering directed edges. We further show that the regularization path is key to identifying the graph. With StructGP, we proposed a model of time series dependencies, that flexibly adapt to different time series regularity, while enabling us to learn these dependencies from observations.