Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited
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 st...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/24/1/90 |
| _version_ | 1797494235603140608 |
|---|---|
| author | Sarah E. Marzen James P. Crutchfield |
| author_facet | Sarah E. Marzen James P. Crutchfield |
| author_sort | Sarah E. Marzen |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T01:31:26Z |
| format | Article |
| id | doaj.art-30f2d8626f49497289f0fce13ef75856 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T01:31:26Z |
| publishDate | 2022-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-30f2d8626f49497289f0fce13ef758562023-11-23T13:41:44ZengMDPI AGEntropy1099-43002022-01-012419010.3390/e24010090Probabilistic Deterministic Finite Automata and Recurrent Networks, RevisitedSarah E. Marzen0James P. Crutchfield1W. M. Keck Science Department, Pitzer, Scripps, and Claremont McKenna College, Claremont, CA 91711, USAComplexity Sciences Center, Physics Department, University of California at Davis, One Shields Avenue, Davis, CA 95616, USAReservoir 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.https://www.mdpi.com/1099-4300/24/1/90time series predictionfinite state machineshidden Markov modelsrecurrent neural networksreservoir computerslong short-term memory |
| spellingShingle | Sarah E. Marzen James P. Crutchfield Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited Entropy time series prediction finite state machines hidden Markov models recurrent neural networks reservoir computers long short-term memory |
| title | Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited |
| title_full | Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited |
| title_fullStr | Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited |
| title_full_unstemmed | Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited |
| title_short | Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited |
| title_sort | probabilistic deterministic finite automata and recurrent networks revisited |
| topic | time series prediction finite state machines hidden Markov models recurrent neural networks reservoir computers long short-term memory |
| url | https://www.mdpi.com/1099-4300/24/1/90 |
| work_keys_str_mv | AT sarahemarzen probabilisticdeterministicfiniteautomataandrecurrentnetworksrevisited AT jamespcrutchfield probabilisticdeterministicfiniteautomataandrecurrentnetworksrevisited |