CoChat
Sign Up
PreprintCited by 3Gaussian Processes and Bayesian InferenceMarkov Chains and Monte Carlo MethodsTime Series Analysis and Forecasting

Sequential Monte Carlo Learning for Time Series Structure Discovery

Open access
Saad, Feras A., Patton, Brian J., Hoffman, Matthew D., Saurous, Rif A., Mansinghka, Vikash K.·2023·arXiv
DOI 10.48550/arxiv.2307.09607arXiv 2307.09607
Open this paper in CoChat — free accountOpen PDF

Abstract

This paper presents a new approach to automatically discovering accurate models of complex time series data. Working within a Bayesian nonparametric prior over a symbolic space of Gaussian process time series models, we present a novel structure learning algorithm that integrates sequential Monte Carlo (SMC) and involutive MCMC for highly effective posterior inference. Our method can be used both in "online" settings, where new data is incorporated sequentially in time, and in "offline" settings, by using nested subsets of historical data to anneal the posterior. Empirical measurements on real-world time series show that our method can deliver 10x--100x runtime speedups over previous MCMC and greedy-search structure learning algorithms targeting the same model family. We use our method to perform the first large-scale evaluation of Gaussian process time series structure learning on a prominent benchmark of 1,428 econometric datasets. The results show that our method discovers sensible models that deliver more accurate point forecasts and interval forecasts over multiple horizons as compared to widely used statistical and neural baselines that struggle on this challenging data.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2307.09607

Cites

41 of 42 references verified0 citation errors · 1 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Recent advances in probabilistic programming have led to more general and scalable methods for Bayesian inference, probabilistic program synthesis, and automatic differentiation of expected values, which may serve as key enablers for learning and refining world models from data.

    “Recent advances in probabilistic programming have also led to more general and scalable methods for Bayesian inference (Baydin et al., 2019b;Lew et al., 2023b), probabilistic program synthesis (Saad et al., 2023), and automatic differentiation of expected values (Lew et al., 2023a), which may serve as key enablers for learning and refining world models from data.”

    From Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems (2024) · cites this paper as Saad et al., 2023

    Split into 2 atoms — 1 confirmed, 1 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.

    Experimental — accuracy not yet measured

  • Using probabilistic programming, one can leverage sequential Monte Carlo methods to gradually infer a theory represented as a probabilistic program as new data is observed, or by incrementally refining an initially coarse 3D world model.

    “Using probabilistic programming, one can leverage sequential Monte Carlo (SMC) methods to gradually infer a theory T (represented as probabilistic program) as new data is observed (Saad et al., 2023), or by incrementally refining an initially coarse 3D world model (Gothoskar et al., 2023;Stuhlmüller et al., 2015).”

    From Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems (2024) · cites this paper as Saad et al., 2023

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 24

  1. Adams, R. P., Wallach, H., and Ghahramani, Z. Learning the structure of deep sparse graphical models. In Proceed- ings of the 13th International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 1-8. PMLR, 2010.
  2. Duvenaud, D., Lloyd, J., Grosse, R., Tenenbaum, J. B., and Ghahramani, Z. Structure discovery in nonparamet- ric regression through compositional kernel search. In Proceedings of the 30th International Conference on Ma- chine Learning, volume 28 of Proceedings of Machine Learning Research, pp. 1166-1174. PMLR, 2013.
  3. Hamelijnck, O., Wilkinson, W., Loppi, N., Solin, A., and Damoulas, T. Spatio-temporal variational gaussian pro- cesses. In Proceedings of the 35th Conference on Neural Information Processing Systems, volume 34 of Advances in Neural Information Processing Systems, pp. 23621- 23633.
  4. Hamze, F. and de Freitas, N. Hot coupling: A particle ap- proach to inference and normalization on pairwise undi- rected graphs. In Proceedings of the 19th Conference on Neural Information Processing Systems, volume 18 of Advances in Neural Information Processing Systems, pp. 491-498. MIT Press, 2005.
  5. Hyndman, R. J. and Athanasopoulos, G. Forecasting: Prin- ciples and Practice. OTexts, Melbourne, 3rd edition, 2021. URL https://otexts.com/fpp3/.
  6. Hyndman, R. J., Koehler, A. B., Ord, J. K., , and Sny- der, R. Forecasting with Exponential Smoothing: The State Space Approach. Springer-Verlag, Berlin, 2008. doi:10.1007/978-3-540-71918-2. · DOI
  7. Kim, H. and Teh, Y. W. Scaling up the automatic statistician: Scalable structure discovery using Gaussian processes. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, volume 84 of Pro- ceedings of Machine Learning Research, pp. 575-584.
  8. PMLR, 2018.
  9. Lew, A., Cusumano-Towner, M., and Mansinghka, V. Recur- sive Monte Carlo and variational inference with auxiliary variables. In Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, volume 180 of Pro- ceedings of Machine Learning Research, pp. 1096-1106.
  10. PMLR, 2022.
  11. Mansinghka, V., Shafto, P., Jonas, E., Petschulat, C., Gasner, M., and Tenenbaum, J. B. CrossCat: A fully Bayesian nonparametric method for analyzing heterogeneous, high dimensional data. Journal of Machine Learning Research, 17(138):1-49, 2016.
  12. Moretti, A. K., Zhang, L., Naesseth, C. A., Venner, H., Blei, D., and Pe'er, I. Variational combinatorial sequential Monte Carlo methods for Bayesian phylogenetic infer- ence. In Proceedings of the 37th Conference on Uncer- tainty in Artificial Intelligence, volume 161 of Proceed- ings of Machine Learning Research, pp. 971-981. PMLR, 2021.
  13. Naesseth, C. A., Fredrik Lindsten, S., and B., T. Sequential Monte Carlo for graphical models. In Proceedings of the 28th Conference on Neural Information Processing Systems, volume 27 of Advances in Neural Information Processing Systems, pp. 1862-1870. MIT Press, 2014.
  14. Neklyudov, K., Welling, M., Egorov, E., and Vetrov, D. In- volutive MCMC: A unifying framework. In Proceedings of the 37th International Conference on Machine Learn- ing, volume 119 of Proceedings of Machine Learning Research, pp. 7273-7282. PMLR, 2020.
  15. Obermeyer, F., Glidden, J., and Jonas, E. Scaling non- parametric Bayesian inference via subsample-annealing. In Proceedings of the 17th Conference on Artificial In- telligence and Statistics, volume 33 of Proceedings of Machine Learning Research, pp. 696-705. PMLR, 2014.
  16. Quiñonero-Candela, J. and Rasmussen, C. E. A unifying view of sparse approximate Gaussian process regression. Journal of Machine Learning Research, 6(65):1939-1959, 2005.
  17. Roberts, S., Osborne, M., Ebden, M., Reece, S., Gibson, N., and Aigrain, S. Gaussian processes for time-series mod- elling. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 371 (1984):20110550, 2013. doi:10.1098/rsta.2011.0550. · DOI
  18. Rossi, S., Heinonen, M., Bonilla, E., Shen, Z., and Filip- pone, M. Sparse Gaussian processes revisited: Bayesian approaches to inducing-variable approximations. In Pro- ceedings of The 24th International Conference on Ar- tificial Intelligence and Statistics, volume 130 of Pro- ceedings of Machine Learning Research, pp. 1837-1845.
  19. PMLR, 2021.
  20. Saad, F. A. and Mansinghka, V. K. Temporally-reweighted chinese restaurant process mixtures for clustering, imput- ing, and forecasting multivariate time series. In Proceed- ings of the 21st International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 755-764. PMLR, 2018.
  21. Saad, F. A. and Mansinghka, V. K. Hierarchical infinite relational model. In Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 1067- 1077. PMLR, 2021.
  22. Saad, F. A., Cusumano-Towner, M., and Mansinghka, V. K. Estimators of entropy and information via inference in probabilistic models. In Proceedings of the 25th Inter- national Conference on Artificial Intelligence and Statis- tics, volume 151 of Proceedings of Machine Learning Research, pp. 5604-5621. PMLR, 2022.
  23. Saad, F. A. K. Scalable Structure Learning, Inference, and Analysis with Probabilistic Programs. PhD thesis, Mas- sachusetts Institute of Technology, 2022.
  24. Tebbutt, W., Solin, A., and Turner, R. E. Combining pseudo- point and state space approximations for sum-separable Gaussian processes. In Proceedings of the 37th Confer- ence on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 1607-1617. PMLR, 2021.

Cited by

Sorted by citations

Authors
Saad, F. A., Patton, B. J., Hoffman, M. D., Saurous, R. A., & Mansinghka, V. K.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2023
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2307.09607
arXiv
2307.09607
OpenAlex
W4384918601
Cited by
3
References
42
Citations by year
2026: 1 · 2025: 1 · 2024: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Gaussian Processes and Bayesian Inference
  • Physical Sciences › Mathematics › Statistics and Probability › Markov Chains and Monte Carlo Methods
  • Physical Sciences › Computer Science › Signal Processing › Time Series Analysis and Forecasting
Keywords
sequential Monte Carlo, Bayesian nonparametrics, posterior inference, online learning, time series econometrics, point forecasting, prediction intervals, model discovery

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review