×

Variational approach for learning Markov processes from time series data. (English) Zbl 1437.37107

Summary: Inference, prediction, and control of complex dynamical systems from time series is important in many areas, including financial markets, power grid management, climate and weather modeling, or molecular dynamics. The analysis of such highly nonlinear dynamical systems is facilitated by the fact that we can often find a (generally nonlinear) transformation of the system coordinates to features in which the dynamics can be excellently approximated by a linear Markovian model. Moreover, the large number of system variables often change collectively on large time- and length-scales, facilitating a low-dimensional analysis in feature space. In this paper, we introduce a variational approach for Markov processes (VAMP) that allows us to find optimal feature mappings and optimal Markovian models of the dynamics from given time series data. The key insight is that the best linear model can be obtained from the top singular components of the Koopman operator. This leads to the definition of a family of score functions called VAMP-\(r\) which can be calculated from data, and can be employed to optimize a Markovian model. In addition, based on the relationship between the variational scores and approximation errors of Koopman operators, we propose a new VAMP-E score, which can be applied to cross-validation for hyper-parameter optimization and model selection in VAMP. VAMP is valid for both reversible and nonreversible processes and for stationary and nonstationary processes or realizations.

MSC:

37M10 Time series analysis of dynamical systems
47N30 Applications of operator theory in probability theory and statistics
65K10 Numerical optimization and variational techniques
60J22 Computational methods in Markov chains

Software:

Spearmint; VAMPnets; GAIO
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andrew, G., Arora, R., Bilmes, J., Livescu, K.: Deep canonical correlation analysis. In: International Conference on Machine Learning, pp. 1247-1255 (2013)
[2] Arlot, S.; Celisse, A., A survey of cross-validation procedures for model selection, Stat. Surv., 4, 40-79 (2010) · Zbl 1190.62080
[3] Bollt, E.M., Santitissadeekorn, N.: Applied and Computational Measurable Dynamics. SIAM (2013) · Zbl 1417.37008
[4] Boninsegna, L.; Gobbo, G.; Noé, F.; Clementi, C., Investigating molecular kinetics by variationally optimized diffusion maps, J. Chem. Theory Comput., 11, 5947-5960 (2015)
[5] Bowman, Gr; Pande, Vs; Noé, F., An Introduction to Markov State Models and Their Application to Long Timescale Molecular Simulation (2014), Heidelberg: Springer, Heidelberg · Zbl 1290.92004
[6] Brunton, Sl; Brunton, Bw; Proctor, Jl; Kutz, Jn, Koopman invariant subspaces and finite linear representations of nonlinear dynamical systems for control, PLoS ONE, 11, 2, e0150171 (2016)
[7] Brunton, Sl; Proctor, Jl; Kutz, Jn, Discovering governing equations from data by sparse identification of nonlinear dynamical systems, Proc. Natl. Acad. Sci., 113, 15, 3932-3937 (2016) · Zbl 1355.94013
[8] Chekroun, Md; Simonnet, E.; Ghil, M., Stochastic climate dynamics: random attractors and time-dependent invariant measures, Physica D Nonlinear Phenom., 240, 21, 1685-1700 (2011) · Zbl 1244.37046
[9] Chodera, Jd; Noé, F., Markov state models of biomolecular conformational dynamics, Curr. Opin. Struct. Biol., 25, 135-144 (2014)
[10] Conrad, Nd; Weber, M.; Schütte, C., Finding dominant structures of nonreversible Markov processes, Multiscale Model. Simul., 14, 4, 1319-1340 (2016) · Zbl 1352.65025
[11] Dellnitz, M.; Froyland, G.; Junge, O.; Fiedler, B., The algorithms behind gaio-set oriented numerical methods for dynamical systems, Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems, 145-174 (2001), Berlin: Springer, Berlin · Zbl 0998.65126
[12] Deuflhard, P.; Weber, M.; Dellnitz, M.; Kirkland, S.; Neumann, M.; Schütte, C., Robust perron cluster analysis in conformation dynamics, Linear Algebra Application, 161-184 (2005), New York: Elsevier, New York · Zbl 1070.15019
[13] Friedman, J.; Hastie, T.; Tibshirani, R., The Elements of Statistical Learning (2001), New York: Springer, New York · Zbl 0973.62007
[14] Froyland, G., An analytic framework for identifying finite-time coherent sets in time-dependent dynamical systems, Physica D Nonlinear Phenom., 250, 1-19 (2013) · Zbl 1355.37013
[15] Froyland, G.; Padberg, K., Almost-invariant sets and invariant manifolds—connecting probabilistic and geometric descriptions of coherent structures in flows, Physica D Nonlinear Phenom., 238, 16, 1507-1523 (2009) · Zbl 1178.37119
[16] Froyland, G.; Padberg-Gehle, K.; Bahsoun, W.; Bose, C.; Froyland, G., Almost-invariant and finite-time coherent sets: directionality, duration, and diffusion, Ergodic Theory, Open Dynamics, and Coherent Structures, 171-216 (2014), Berlin: Springer, Berlin · Zbl 1352.37078
[17] Froyland, G.; Gottwald, Ga; Hammerlindl, A., A computational method to extract macroscopic variables and their dynamics in multiscale systems, SIAM J. Appl. Dyn. Syst., 13, 4, 1816-1846 (2014) · Zbl 1320.37012
[18] Froyland, G.; González-Tokman, C.; Watson, Tm, Optimal mixing enhancement by local perturbation, SIAM Rev., 58, 3, 494-513 (2016) · Zbl 1360.37009
[19] Hardoon, Dr; Szedmak, S.; Shawe-Taylor, J., Canonical correlation analysis: an overview with application to learning methods, Neural Comput., 16, 12, 2639-2664 (2004) · Zbl 1062.68134
[20] Harmeling, S.; Ziehe, A.; Kawanabe, M.; Müller, K-R, Kernel-based nonlinear blind source separation, Neural Comput., 15, 5, 1089-1124 (2003) · Zbl 1085.68625
[21] Hsing, T.; Eubank, R., Theoretical Foundations of Functional Data Analysis, with an Introduction to Linear Operators (2015), Amsterdam: Wiley, Amsterdam · Zbl 1338.62009
[22] Klus, S., Schütte, C.: Towards tensor-based methods for the numerical approximation of the perron-frobenius and koopman operator (2015). arXiv:1512.06527 · Zbl 1369.37080
[23] Klus, S., Koltai, P., Schütte, C.: On the numerical approximation of the perron-frobenius and koopman operator (2015). arXiv:1512.05997 · Zbl 1353.37154
[24] Klus, S.; Gelß, P.; Peitz, S.; Schütte, C., Tensor-based dynamic mode decomposition, Nonlinearity, 31, 7, 3359 (2018) · Zbl 1404.65313
[25] Koltai, P.; Wu, H.; Noe, F.; Schütte, C., Optimal data-driven estimation of generalized Markov state models for non-equilibrium dynamics, Computation, 6, 1, 22 (2018)
[26] Konrad, A., Zhao, B.Y., Joseph, A.D., Ludwig, R.: A Markov-based channel model algorithm for wireless networks. In: Proceedings of the 4th ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, pp. 28-36. ACM (2001)
[27] Koopman, Bo, Hamiltonian systems and transformations in hilbert space, Proc. Natl. Acad. Sci. U.S.A., 17, 315-318 (1931) · JFM 57.1010.02
[28] Korda, M.; Mezić, I., On convergence of extended dynamic mode decomposition to the Koopman operator, J. Nonlinear Sci., 28, 2, 687-710 (2018) · Zbl 1457.37103
[29] Kurebayashi, W., Shirasaka, S., Nakao, H.: Optimal parameter selection for kernel dynamic mode decomposition. In: Proceedings of the International Symposium NOLTA, volume 370, p. 373 (2016) · Zbl 1387.37045
[30] Li, Q.; Dietrich, F.; Bollt, Em; Kevrekidis, Ig, Extended dynamic mode decomposition with dictionary learning: a data-driven adaptive spectral decomposition of the Koopman operator, Chaos, 27, 10, 103111 (2017) · Zbl 06876982
[31] Lusch, B.; Kutz, Jn; Brunton, Sl, Deep learning for universal linear embeddings of nonlinear dynamics, Nat. Commun., 9, 1, 4950 (2018)
[32] Ma, Y.; Han, Jj; Trivedi, Ks, Composite performance and availability analysis of wireless communication networks, IEEE Trans. Veh. Technol., 50, 5, 1216-1223 (2001)
[33] Mardt, A.; Pasquali, L.; Wu, H.; Noé, F., Vampnets for deep learning of molecular kinetics, Nat. Commun., 9, 1, 5 (2018)
[34] Marshall, Aw; Olkin, I.; Arnold, Bc, Inequalities: Theory of Majorization and Its Applications (1979), Berlin: Springer, Berlin · Zbl 0437.26007
[35] Mcgibbon, Rt; Pande, Vs, Variational cross-validation of slow dynamical modes in molecular kinetics, J. Chem. Phys., 142, 124105 (2015)
[36] Mezić, I., Spectral properties of dynamical systems, model reduction and decompositions, Nonlinear Dyn., 41, 309-325 (2005) · Zbl 1098.37023
[37] Mezić, I., Analysis of fluid flows via spectral properties of the Koopman operator, Annu. Rev. Fluid Mech., 45, 357-378 (2013) · Zbl 1359.76271
[38] Molgedey, L.; Schuster, Hg, Separation of a mixture of independent signals using time delayed correlations, Phys. Rev. Lett., 72, 3634-3637 (1994)
[39] Noé, F., Probability distributions of molecular observables computed from Markov models, J. Chem. Phys., 128, 244103 (2008)
[40] Noé, F.; Clementi, C., Kinetic distance and kinetic maps from molecular dynamics simulation, J. Chem. Theory Comput., 11, 5002-5011 (2015)
[41] Noé, F.; Nüske, F., A variational approach to modeling slow processes in stochastic dynamical systems, Multiscale Model. Simul., 11, 635-655 (2013) · Zbl 1306.65013
[42] Nüske, F.; Keller, Bg; Pérez-Hernández, G.; Mey, Asjs; Noé, F., Variational approach to molecular kinetics, J. Chem. Theory Comput., 10, 1739-1752 (2014)
[43] Nüske, F.; Schneider, R.; Vitalini, F.; Noé, F., Variational tensor approach for approximating the rare-event kinetics of macromolecular systems, J. Chem. Phys., 144, 054105 (2016)
[44] Otto, Se; Rowley, Cw, Linearly recurrent autoencoder networks for learning dynamics, SIAM J. Appl. Dyn. Syst., 18, 1, 558-593 (2019) · Zbl 1489.65164
[45] Paul, F.; Wu, H.; Vossel, M.; Groot, B.; Noe, F., Identification of kinetic order parameters for non-equilibrium dynamics, J. Chem. Phys., 150, 164120 (2018)
[46] Perez-Hernandez, G.; Paul, F.; Giorgino, T.; Fabritiis, Gd; Noé, F., Identification of slow molecular order parameters for Markov model construction, J. Chem. Phys., 139, 015102 (2013)
[47] Press, Wh; Teukolsky, Sa; Vetterling, Wt; Flannery, Bp, Numerical Recipes: The Art of Scientific Computing (2007), Cambridge: Cambridge University Press, Cambridge
[48] Prinz, J-H; Wu, H.; Sarich, M.; Keller, Bg; Senne, M.; Held, M.; Chodera, Jd; Schütte, C.; Noé, F., Markov models of molecular kinetics: generation and validation, J. Chem. Phys., 134, 174105 (2011)
[49] Renardy, M.; Rogers, Rc, An Introduction to Partial Differential Equations (2004), New York: Springer, New York · Zbl 1072.35001
[50] Rowley, Cw; Mezić, I.; Bagheri, S.; Schlatter, P.; Henningson, Ds, Spectral analysis of nonlinear flows, J. Fluid Mech., 641, 115 (2009) · Zbl 1183.76833
[51] Schmid, Pj, Dynamic mode decomposition of numerical and experimental data, J. Fluid Mech., 656, 5-28 (2010) · Zbl 1197.76091
[52] Schütte, C.; Fischer, A.; Huisinga, W.; Deuflhard, P., A direct approach to conformational dynamics based on hybrid Monte Carlo, J. Comput. Phys., 151, 146-168 (1999) · Zbl 0933.65145
[53] Schwantes, Cr; Pande, Vs, Improvements in Markov state model construction reveal many non-native interactions in the folding of NTL9, J. Chem. Theory Comput., 9, 2000-2009 (2013)
[54] Schwantes, Cr; Pande, Vs, Modeling molecular kinetics with tica and the kernel trick, J. Chem. Theory Comput., 11, 600-608 (2015)
[55] Snoek, J., Larochelle, H., Adams, R.P.: Practical bayesian optimization of machine learning algorithms. In: Pereira, F., Burges, C.J.C., Bottou, L., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, pp. 2951-2959 (2012)
[56] Song, L.; Fukumizu, K.; Gretton, A., Kernel embeddings of conditional distributions: a unified kernel framework for nonparametric inference in graphical models, IEEE Signal Process. Mag., 30, 4, 98-111 (2013)
[57] Sparrow, C., The Lorenz Equations: Bifurcations, Chaos, and Strange Attractors (1982), New York: Springer, New York · Zbl 0504.58001
[58] Takeishi, N., Kawahara, Y., Yairi, T.: Learning Koopman invariant subspaces for dynamic mode decomposition. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems, pp. 1130-1140 (2017)
[59] Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc. Ser. B (Methodol.), 58, 267-288 (1996) · Zbl 0850.62538
[60] Tu, Jh; Rowley, Cw; Luchtenburg, Dm; Brunton, Sl; Kutz, Jn, On dynamic mode decomposition: theory and applications, J. Comput. Dyn., 1, 2, 391-421 (2014) · Zbl 1346.37064
[61] Williams, Mo; Kevrekidis, Ig; Rowley, Cw, A data-driven approximation of the Koopman operator: extending dynamic mode decomposition, J. Nonlinear Sci., 25, 1307-1346 (2015) · Zbl 1329.65310
[62] Williams, Mo; Rowley, Cw; Kevrekidis, Ig, A kernel-based method for data-driven Koopman spectral analysis, J. Comput. Dyn., 2, 2, 247-265 (2015) · Zbl 1366.37144
[63] Wu, H.; Noé, F., Gaussian Markov transition models of molecular kinetics, J. Chem. Phys., 142, 084104 (2015)
[64] Wu, H.; Nüske, F.; Paul, F.; Klus, S.; Koltai, P.; Noé, F., Variational Koopman models: slow collective variables and molecular kinetics from short off-equilibrium simulations, J. Chem. Phys., 146, 154104 (2017)
[65] Ziehe, A., Müller, K.-R.: TDSEP —an efficient algorithm for blind separation using time structure. In: ICANN 98, pp. 675-680. Springer (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.