Abductive learning of quantized stochastic processes with probabilistic finite automata

作者：Chattopadhyay Ishanu; Lipson Hod^*

来源：Philosophical Transactions of the Royal Society A-Mathematical Physical and Engineering Sciences, 2013, 371(1984): UNSP 20110543.

DOI：10.1098/rsta.2011.0543

• machine learning
• probabilistic finite automata
• stochastic processes
• symbolic dynamics

We present an unsupervised learning algorithm (GenESeSS) to infer the causal structure of quantized stochastic processes, defined as stochastic dynamical systems evolving over discrete time, and producing quantized observations. Assuming ergodicity and stationarity, GenESeSS infers probabilistic finite state automata models from a sufficiently long observed trace. Our approach is abductive; attempting to infer a simple hypothesis, consistent with observations and modelling framework that essentially fixes the hypothesis class. The probabilistic automata we infer have no initial and terminal states, have no structural restrictions and are shown to be probably approximately correct-learnable. Additionally, we establish rigorous performance guarantees and data requirements, and show that GenESeSS correctly infers long-range dependencies. Modelling and prediction examples on simulated and real data establish relevance to automated inference of causal stochastic structures underlying complex physical phenomena.

• 出版日期2013-2-13