jmlr jmlr2012 jmlr2012-57 jmlr2012-57-reference knowledge-graph by maker-knowledge-mining

57 jmlr-2012-Learning Symbolic Representations of Hybrid Dynamical Systems


Source: pdf

Author: Daniel L. Ly, Hod Lipson

Abstract: A hybrid dynamical system is a mathematical model suitable for describing an extensive spectrum of multi-modal, time-series behaviors, ranging from bouncing balls to air traffic controllers. This paper describes multi-modal symbolic regression (MMSR): a learning algorithm to construct non-linear symbolic representations of discrete dynamical systems with continuous mappings from unlabeled, time-series data. MMSR consists of two subalgorithms—clustered symbolic regression, a method to simultaneously identify distinct behaviors while formulating their mathematical expressions, and transition modeling, an algorithm to infer symbolic inequalities that describe binary classification boundaries. These subalgorithms are combined to infer hybrid dynamical systems as a collection of apt, mathematical expressions. MMSR is evaluated on a collection of four synthetic data sets and outperforms other multi-modal machine learning approaches in both accuracy and interpretability, even in the presence of noise. Furthermore, the versatility of MMSR is demonstrated by identifying and inferring classical expressions of transistor modes from recorded measurements. Keywords: hybrid dynamical systems, evolutionary computation, symbolic piecewise functions, symbolic binary classification


reference text

H. Akaike. A new look at the statistical model identification. IEEE Transactions on Automatic Control, 19(6):716–723, 1974. A. P. A. Anderson. A hybrid mathematical model of solid tumour invasion: the importance of cell adhesion. Mathematical Medicine and Biology, 22:163–186, 2005. A. Arslan and M. Kaya. Determination of fuzzy logic membership functions using genetic algorithms. Fuzzy Sets and Systems, 118:297–306, 2001. Y. Bengio and P. Frasconi. An input-output HMM architecture. Advances in Neural Information Processing Systems, 7:427–434, 1994. C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. M. S. Branicky. Handbook of Networked and Embedded Control Systems, chapter “Introduction to hybrid systems”, pages 91–116. Birkhauser, 2005. L. Breiman. Statistical modeling: the two cultures. Statistical Science, 16(3):199–231, 2001. S. Chen, S.A. Billings, and B.M Grant. Recursive hybrid algorithm for non-linear system identification using radial basis function networks. International Journal of Control, 55:1051–1070, 1992. 3615 LY AND L IPSON N.L. Cramer. A representation for the adaptive generation of simple sequential programs. International Conference on Genetic Algorithms, pages 183–187, 1985. T.S. Cubitt, J. Eisert, and M.M. Wolf. Extracting dynamic equations from experimental data is NP hard. Physical Review Letters, 108, 2012. A.P. Dempster, N.M. Laird, and D.B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1):1–38, 1977. D. Dickmanns, J. Schmidhuber, and A. Winklhofer. Der genetische algorithmus: eine implementierung in prolog. Fortgeschrittenenpraktikum, Institut f¨ r Informatik, Technische Universit¨ t u a M¨ nchen, 1987. a G. Ferrari-Trecate, M. Muselli, D. Liberati, and M. Morari. A clustering technique for the identification of piecewise affine systems. Automatica, 39:205–217, 2003. A. M. Gonzalez, A. M. S. Roque, and J. Garcia-Gonzalez. Modeling and forecasting electricity prices with input/output hidden Markov models. IEEE Transactions on Power Systems, 20(1): 13–24, 2005. T. A. Henzinger. The theory of hybrid automata. Symposium on Logic in Computer Science, pages 324–335, 1996. B. G. Horne and D. R. Hush. Bounds on the complexity of recurrent neural network implementations of finite state machines. Neural Networks, 9(2):243–252, 1996. H. Iba. Inference of differential equation models by genetic programming. Information Sciences, 178:4453–4468, 2008. R. Jacobs, M. I. Jordan, S. J. Nowlan, and G. E. Hinton. Adaptive mixtures of local experts. Neural Computation, 3:79–87, 1991. H. Jacobsson. Rule extraction from recurrent neural networks: a taxonomy and review. Neural Computation, 17(6):1223–1263, 2006. I. Jagielska, C. Matthews, and T. Whitfort. An investigation into the application of neural networks, fuzzy logic, genetic algorithms and rough sets to automated knowledge acquisition for classification problems. Neurocomputing, 24:37–54, 1999. E. B. Kosmatopouous, M. M. Polycarpou, M. A. Christodoulou, and P. A. Ioannou. High-order neural network structures for identification of dynamical systems. IEEE Transactions on Neural Networks, 9(2):422–431, 1995. J. R. Koza. Genetic Programming: On The Programming of Computers by Means of Natural Selection. MIT Press, 1992. V.L. Le, G. Bloch, and F. Lauer. Reduced-size kernel models for nonlinear hybrid system identification. IEEE Transactions on Neural Networks, 22(12):2398–2405, 2011. J. Lunze. Modelling, Analysis and Design of Hybrid Systems, chapter “What is a hybrid system?”, pages 3–14. Springer, 2002. 3616 L EARNING S YMBOLIC R EPRESENTATIONS OF H YBRID DYNAMICAL S YSTEMS S. Marcel, O. Bernier, J. E. Viallet, and D. Collobert. Hand gesture recognition using input-output hidden Markov models. IEEE International Conference on Automatic Face and Gesture Recognition, pages 456–461, 2000. A.M. Martinez and J. Virtia. Learning mixture models using a genetic version of the EM algorithm. Pattern Recognition Letters, 21:759–769, 2000. R. R. F. Mendes, F. B. Voznika, A. A. Freitas, and J. C. Nievola. Discovering fuzzy classification rules with genetic programming and co-evolution. ECML Principles and Practice of Knowledge Discover in Databases, 2168:314–325, 2001. D. P. Muni, N. R. Pal, and J. Das. A novel approach to design classifiers using genetic programming. IEEE Transactions on Evolutionary Computation, 8(2):183–196, 2004. J.R. Olsson. Inductive functional programming using incremental program transformation. Artificial Intelligence, 74(1):55–81, 1995. C.W. Omlin and C.L. Giles. Extraction, insertion and refinement of symbolic rules in dynamically driven recurrent neural networks. Connection Science, 5(3-4):307–337, 1993. C.W. Omlin and C.L. Giles. Constructing deterministic finite-state automata in recurrent neural networks. Journal of the ACM, 43(6):937–972, 1996a. C.W. Omlin and C.L. Giles. Extraction of rules from discrete-time recurrent neural networks. Neural Networks, 9(1):41–52, 1996b. S. Paoletti, A.L. Juloski, G. Ferrari-Trecate, and R. Vidal. Identification of hybrid systems: a tutorial. European Journal of Control, 13:242–260, 2007. R. Pernkopf and D. Bouchaffra. Genetic-base EM algorithm for learning Gaussian mixture models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(8):1344–1348, 2005. B. D. Reger, K. M. Fleming, V. Sanguineti, S. Alford, and F. A Mussa-Ivaldi. Connecting brains to robots: the development of a hybrid system for the study of learning in neural tissues. International Conference on Artificial Life, pages 263–272, 2000. D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning representations by back-propagating errors. Nature, 323:533–536, 1986. T. Schaul, J. Bayer, D. Wierstra, Y. Sun, M. Felder, F. Sehnke, T. R¨ ckstieß, and J. Schmidhuber. u PyBrain. Journal of Machine Learning Research, 11:743–746, 2010. M. D. Schmidt and H. Lipson. Symbolic regression of implicit equations. Genetic Programming Theory and Practice, 7:73–85, 2009a. M. D. Schmidt and H. Lipson. Distilling free-from natural laws from experimental data. Science, 324(5923):81–85, 2009b. M. D. Schmidt and H. Lipson. Eureqa, 2012. http://creativemachines.cornell.edu/eureqa. A. S. Sedra and K. C. Smith. Microelectronic Circuits. Oxford University Press, 2004. 3617 LY AND L IPSON R.J. Solomonoff. A formal theory of inductive inference I, II. Information and Control, 7:1–22, 224–254, 1964. C. Tomlin, G. J. Pappas, and S. S. Sastry. Conflict resolution for air traffic management: a study in multi-agent hybrid systems. IEEE Transactions on Automatic Control, 43(4):509–521, 1998. A. Vahed and C.W. Omlin. A machine learning method for extracting symbolic knowledge from recurrent neural networks. Neural Computation, 16:59–71, 2004. A. van der Schaft and H. Schumacher. An Introduction To Hybrid Dynamical Systems. Springer, 2000. R. Vidal, S. Soatto, Y. Ma, and S. Sastry. An algebraic geometric approach to the identification of a class of linear hybrid systems. Conference on Decision and Control, pages 167–172, 2003. A. Visintin. Differential Models of Hysteresis. Springer, 1995. E. Vladislavleva, G. Smits, and D. den Hertog. Order of nonlinearity as a complexity measure for models generated by symbolic regression via Pareto genetic programming. IEEE Transactions on Evolutionary Computation, 13(2):333–349, 2009. C.S. Wallace and D.L. Dowe. Minimum message length and Kolmogorov complexity. The Computer Journal, 42(4):270–283, 1999. 3618