{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T09:56:48Z","timestamp":1768989408483,"version":"3.49.0"},"reference-count":44,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000181","name":"United States Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-19-1-0411"],"award-info":[{"award-number":["FA9550-19-1-0411"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"name":"U. S. Army Research Office","award":["W911NF-18-1-0028"],"award-info":[{"award-number":["W911NF-18-1-0028"]}]},{"name":"U. S. Army Research Office","award":["W911NF-21-1-0048"],"award-info":[{"award-number":["W911NF-21-1-0048"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Reservoir computers (RCs) and recurrent neural networks (RNNs) can mimic any finite-state automaton in theory, and some workers demonstrated that this can hold in practice. We test the capability of generalized linear models, RCs, and Long Short-Term Memory (LSTM) RNN architectures to predict the stochastic processes generated by a large suite of probabilistic deterministic finite-state automata (PDFA) in the small-data limit according to two metrics: predictive accuracy and distance to a predictive rate-distortion curve. The latter provides a sense of whether or not the RNN is a lossy predictive feature extractor in the information-theoretic sense. PDFAs provide an excellent performance benchmark in that they can be systematically enumerated, the randomness and correlation structure of their generated processes are exactly known, and their optimal memory-limited predictors are easily computed. With less data than is needed to make a good prediction, LSTMs surprisingly lose at predictive accuracy, but win at lossy predictive feature extraction. These results highlight the utility of causal states in understanding the capabilities of RNNs to predict.<\/jats:p>","DOI":"10.3390\/e24010090","type":"journal-article","created":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T03:41:32Z","timestamp":1641440492000},"page":"90","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited"],"prefix":"10.3390","volume":"24","author":[{"given":"Sarah E.","family":"Marzen","sequence":"first","affiliation":[{"name":"W. M. Keck Science Department, Pitzer, Scripps, and Claremont McKenna College, Claremont, CA 91711, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4466-5410","authenticated-orcid":false,"given":"James P.","family":"Crutchfield","sequence":"additional","affiliation":[{"name":"Complexity Sciences Center, Physics Department, University of California at Davis, One Shields Avenue, Davis, CA 95616, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1593","DOI":"10.1126\/science.275.5306.1593","article-title":"A neural substrate of prediction and reward","volume":"275","author":"Schultz","year":"1997","journal-title":"Science"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1936","DOI":"10.1523\/JNEUROSCI.16-05-01936.1996","article-title":"A framework for mesencephalic dopamine systems based on predictive Hebbian learning","volume":"16","author":"Montague","year":"1996","journal-title":"J. Neurosci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1038\/4580","article-title":"Predictive coding in the visual cortex: A functional interpretation of some extra-classical receptive-field effects","volume":"2","author":"Rao","year":"1999","journal-title":"Nat. Neurosci."},{"key":"ref_4","unstructured":"Berger, T. (1971). Rate Distortion Theory, Prentice-Hall."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"037111","DOI":"10.1063\/1.3489885","article-title":"Optimal causal inference: Estimating stored information and approximating causal architecture","volume":"20","author":"Still","year":"2010","journal-title":"Chaos Interdiscip. J. Nonlinear Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"968","DOI":"10.3390\/e16020968","article-title":"Information bottleneck approach to predictive inference","volume":"16","author":"Still","year":"2014","journal-title":"Entropy"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1007\/s10955-016-1520-1","article-title":"Predictive Rate-Distortion for Infinite-Order Markov Processes","volume":"163","author":"Marzen","year":"2014","journal-title":"J. Stat. Phys."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"6908","DOI":"10.1073\/pnas.1506855112","article-title":"Predictive information in a sensory population","volume":"112","author":"Palmer","year":"2015","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Tishby, N., and Zaslavsky, N. (2015). Deep Learning and the Information Bottleneck Principle. arXiv.","DOI":"10.1109\/ITW.2015.7133169"},{"key":"ref_10","unstructured":"Shwartz-Ziv, R., and Tishby, N. (2017). Opening the Black Box of Deep Neural Networks via Information. arXiv."},{"key":"ref_11","unstructured":"Ash, R.B. (1965). Information Theory, John Wiley and Sons."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1023\/A:1010388907793","article-title":"Computational Mechanics: Pattern and Prediction, Structure and Simplicity","volume":"104","author":"Shalizi","year":"2001","journal-title":"J. Stat. Phys."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"2409","DOI":"10.1162\/089976601753195969","article-title":"Predictability, complexity, and learning","volume":"13","author":"Bialek","year":"2001","journal-title":"Neural Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1063\/1.1530990","article-title":"Regularities Unseen, Randomness Observed: Levels of Entropy Convergence","volume":"13","author":"Crutchfield","year":"2003","journal-title":"Chaos"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2531","DOI":"10.1162\/089976602760407955","article-title":"Real-time computing without stable states: A new framework for neural computation based on perturbations","volume":"14","author":"Maass","year":"2002","journal-title":"Neural Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/j.neunet.2018.08.025","article-title":"Echo state networks are universal","volume":"108","author":"Grigoryeva","year":"2018","journal-title":"Neural Netw."},{"key":"ref_17","unstructured":"Doya, K. (1993). Universality of Fully Connected Recurrent Neural Networks, Deptartment of Biology, UCSD. Technology Report."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1162\/neco.1989.1.3.372","article-title":"Finite state automata and simple recurrent networks","volume":"1","author":"Cleeremans","year":"1989","journal-title":"Neural Comput."},{"key":"ref_19","unstructured":"Horne, B.G., and Hush, D.R. (December, January 29). Bounds on the complexity of recurrent neural network implementations of finite state machines. Proceedings of the 6th International Conference on Neural Information Processing Systems, Denver, CO, USA."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1735","DOI":"10.1162\/neco.1997.9.8.1735","article-title":"Long short-term memory","volume":"9","author":"Schmidhuber","year":"1997","journal-title":"Neural Comput."},{"key":"ref_21","unstructured":"Collins, J., Sohl-Dickstein, J., and Sussillo, D. (2016). Capacity and trainability in recurrent neural networks. arXiv."},{"key":"ref_22","first-page":"370","article-title":"Generalized linear models","volume":"135","author":"Nelder","year":"1972","journal-title":"J. R. Stat. Stoc. A"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"042119","DOI":"10.1103\/PhysRevE.89.042119","article-title":"Bayesian Structural Inference for Hidden Processes","volume":"89","author":"Strelioff","year":"2014","journal-title":"Phys. Rev. E"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1103\/PhysRevLett.63.105","article-title":"Inferring Statistical Complexity","volume":"63","author":"Crutchfield","year":"1989","journal-title":"Phys. Rev. Let."},{"key":"ref_25","first-page":"1930","article-title":"Probabilistic deterministic infinite automata","volume":"23","author":"Pfau","year":"2010","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_26","first-page":"1555","article-title":"Predictive representations of state","volume":"14","author":"Littman","year":"2002","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1162\/neco.2008.01-07-455","article-title":"Predictive coding and the slowness principle: An information-theoretic approach","volume":"20","author":"Creutzig","year":"2008","journal-title":"Neural Comput."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"041925","DOI":"10.1103\/PhysRevE.79.041925","article-title":"Past-future information bottleneck in dynamical systems","volume":"79","author":"Creutzig","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_29","unstructured":"Tishby, N., Pereira, F.C., and Bialek, W. (2000). The information bottleneck method. arXiv."},{"key":"ref_30","unstructured":"Hopcroft, J.E., and Ullman, J.D. (1979). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"042135","DOI":"10.1103\/PhysRevE.89.042135","article-title":"Many Roads to Synchrony: Natural Time Scales and Their Algorithms","volume":"89","author":"James","year":"2014","journal-title":"Phys. Rev. E"},{"key":"ref_32","unstructured":"L\u00f6hr, W. (2009). Models of Discrete-Time Stochastic Processes and Associated Complexity Measures. [Ph.D. Thesis, University of Leipzig]."},{"key":"ref_33","first-page":"60","article-title":"Pattern discovery in time series, Part I: Theory, algorithm, analysis, and convergence","volume":"10","author":"Shalizi","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1109\/TIT.1974.1055146","article-title":"On the computation of rate-distortion functions (corresp.)","volume":"20","year":"1974","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_35","unstructured":"Johnson, B.D., Crutchfield, J.P., Ellison, C.J., and McTague, C.S. (2010). Enumerating Finitary Processes. arXiv."},{"key":"ref_36","first-page":"223","article-title":"Computation at the Onset of Chaos","volume":"Volume VIII","author":"Zurek","year":"1990","journal-title":"Entropy, Complexity, and the Physics of Information"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Kelso, J.S., Mandell, A.J., and Shlesinger, M.F. (1988). Adaptation toward the Edge of Chaos. Dynamic Patterns in Complex Systems, World Scientific.","DOI":"10.1142\/9789814542043"},{"key":"ref_38","first-page":"497","article-title":"Dynamics, Computation, and the \u201cEdge of Chaos\u201d: A Re-Examination","volume":"Volume XIX","author":"Cowan","year":"1994","journal-title":"Complexity: Metaphors, Models, and Reality"},{"key":"ref_39","first-page":"89","article-title":"Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations","volume":"7","author":"Mitchell","year":"1993","journal-title":"Complex Syst."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1413","DOI":"10.1162\/089976604323057443","article-title":"Real-time computation at the edge of chaos in recurrent neural networks","volume":"16","author":"Bertschinger","year":"2004","journal-title":"Neural Comput."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s12064-011-0146-8","article-title":"Information processing in echo state networks at the edge of chaos","volume":"131","author":"Boedecker","year":"2012","journal-title":"Theory Biosci."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1142\/S0218488598000094","article-title":"The vanishing gradient problem during learning recurrent neural nets and problem solutions","volume":"6","author":"Hochreiter","year":"1998","journal-title":"Int. J. Uncertain. Fuzziness-Knowl.-Based Syst."},{"key":"ref_43","unstructured":"Kingma, D.P., and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"7937","DOI":"10.1073\/pnas.1800521115","article-title":"Efficient compression in color naming and its evolution","volume":"115","author":"Zaslavsky","year":"2018","journal-title":"Proc. Natl. Acad. Sci. USA"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/90\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:00:29Z","timestamp":1760364029000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/1\/90"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,6]]},"references-count":44,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["e24010090"],"URL":"https:\/\/doi.org\/10.3390\/e24010090","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,6]]}}}