Method extracts weighted automata from RNNs using state space regression.
problem Extracting weighted automata from RNNs for better model understanding.
method Regression on RNN state space to prioritize counterexample candidates.
result Quantitative/weighted extension of DFA extraction.
Extracts weighted automata from black box models for sequential data.
problem Global interpretability of black box models for symbolic sequential data.
method Spectral algorithm for extracting weighted automata from black boxes without access to inner representation.
result Approximation of black box models using inferred weighted automata is of high quality.
We show how well known rules of back propagation arise from a weighted combination of finite automata. By redefining a finite automata as a predictor we combine the set of all k-state finite automata using a weighted majority algorithm. This aggregated prediction algorithm can be simplified using symmetry, and we pro…
A framework for analyzing financial systems under scenario constraints.
problem Quantifying worst-case and best-case performance in financial systems.
method Quantitative automata-based framework integrating event history automata and weighted finance finite automata.
result Exact calculation of upper and lower payoff bounds with interpretable witness event histories.
Algorithm extracts deterministic PDFA from probabilistic models with improved performance.
problem Learning deterministic models from probabilistic ones with noise.
method Adapted L* algorithm for probabilistic settings, using conditional probabilities and local tolerance.
result Achieves better performance on WER and NDCG than spectral extraction of WFAs.
In this paper, we unravel a fundamental connection between weighted finite automata~(WFAs) and second-order recurrent neural networks~(2-RNNs): in the case of sequences of discrete symbols, WFAs and 2-RNNs with linear activation functions are expressively equivalent. Motivated by this result, we build upon a recent ext…
Train track automata for fully irreducible elements in Out(F_r).
problem Understanding fully irreducible elements in Out(F_r).
method Describing train track automata and geodesics in Outer Space.
result Geodesics in Culler-Vogtmann Outer Space for fully irreducible elements.
ADT uses adaptive sequences to improve automata learning.
problem Improving efficiency and accuracy of automata learning.
method Developed ADT algorithm with adaptive distinguishing sequences.
result ADT successfully integrated into LearnLib and used in research.
Study immersions of punctured 4-manifolds for quantum automata applications.
problem Existence of immersions between specific 4-manifolds.
method Analyzing immersions of punctured 4-manifolds to establish a partial order.
result Established a partial order on closed 4-manifolds via immersions.
The paper distills a weighted automaton from RNNs for language modeling.
problem Tackles the gap between deep learning and grammatical inference.
method Uses a spectral approach to infer a weighted automaton from a trained RNN.
result Extracted weighted automata are good approximations of the RNNs, validating the approach.
Quantum cellular automata form a homology theory.
problem Understanding the topological structure of quantum cellular automata.
method Formal properties of coarse homology theories.
result Quantum cellular automata naturally form the degree-zero part of a coarse homology theory.
Sparse regularization reduces NLP model complexity without sacrificing accuracy.
problem Excessive parameter usage in neural models for NLP leads to high memory and runtime usage.
method Apply group lasso to rational RNNs to learn sparse, parameter-efficient models.
result Sparse rational RNNs can have significantly fewer parameters than non-sparse models without losing performance.
We obtain an index of the complexity of a random sequence by allowing the role of the measure in classical probability theory to be played by a function we call the generating mechanism. Typically, this generating mechanism will be a finite automata. We generate a set of biased sequences by applying a finite state auto…
ISA learns subgoals for reinforcement learning agents.
problem Learning subgoals for efficient reinforcement learning.
method Induces a subgoal automaton from observation traces using inductive logic programming.
result ISA learns subgoals that improve RL performance and convergence.
We present an interactive version of an evidence-driven state-merging (EDSM) algorithm for learning variants of finite state automata. Learning these automata often amounts to recovering or reverse engineering the model generating the data despite noisy, incomplete, or imperfectly sampled data sources rather than optim…
Automaton models are often seen as interpretable models. Interpretability itself is not well defined: it remains unclear what interpretability means without first explicitly specifying objectives or desired attributes. In this paper, we identify the key properties used to interpret automata and propose a modification o…
Paper verifies RNNs using automata learning and model checking.
problem Verifying the correctness of RNNs is challenging.
method Learn a deterministic finite automaton from RNN, use model checking for verification.
result Can discover and generalize counterexamples to faulty flows.
A new layer learns abstract relations from graph structure using finite-state automata.
problem Learning abstract relations from graph structure for program analysis.
method Relaxing the problem into learning finite-state automata policies on a graph-based POMDP and training these policies using implicit differentiation.
result GFSA layer finds shortcuts in grid-world graphs and reproduces simple static analyses on Python programs.
Designs a Cellular Automata rule for forming touching loop patterns.
problem Forming stable touching loop patterns in a 2D grid.
method Developed a Cellular Automata rule that uses templates to cover the space and match patterns.
result The rule successfully evolves stable touching loop patterns in a 2D grid.
CURIE uses cellular automata to detect concept drift in data streams.
problem Detecting changes in data distribution (concept drift) in data streams.
method CURIE represents data stream distribution in a cellular automata grid and uses its neighborhood rule to detect changes.
result CURIE, when hybridized with base learners, performs competitively in detection metrics and classification accuracy.
Transformers simulate finite-state automata with fewer layers.
problem How do shallow, non-recurrent Transformers simulate complex computations?
method Hierarchical reparameterization of recurrent dynamics to simulate automata.
result Polynomial-sized, O(logT)-depth solutions exist and are common. Classifies knots in the Poincaré sphere, using fixed points and folding automata.
problem Classifying knots in the Poincaré sphere and understanding their properties.
method Theory of train tracks, folding automata, and knot Floer homology.
result Almost completely classified genus-two, hyperbolic, fibered knots.
DeepSynth synthesizes automata to guide deep RL agents through sparse, non-Markovian rewards.
problem Training deep RL agents with sparse, non-Markovian rewards and unknown high-level objectives.
method Employing a novel algorithm for synthesizing compact automata to uncover sequential structure from trace data.
result Reduces the number of iterations required for policy synthesis by two orders of magnitude and improves scalability.
LUNAR uses cellular automata for real-time data classification in fast streams.
problem Real-time machine learning challenges with fast data streams and concept drift.
method Streamified cellular automata approach for incremental learning and adaptation.
result Competitive performance in classification compared to established online learning methods.
Graph Weighted Models (GWMs) have recently been proposed as a natural generalization of weighted automata over strings and trees to arbitrary families of labeled graphs (and hypergraphs). A GWM generically associates a labeled graph with a tensor network and computes a value by successive contractions directed by its e…
The paper develops algorithms for computing in stochastic acceptors.
problem Computing input marginals and acceptance probabilities in stochastic acceptors.
method Dynamic programming for input marginals, EM for parameter estimation.
result Efficient algorithms for computing in stochastic acceptors.
New algorithm learns Markov decision processes from test data.
problem Learning Markov decision processes from limited test data.
method L*-based active learning with sampling.
result Sampling-based algorithm outperforms passive learning.
In the present work we introduce a stochastic cellular automata model in order to simulate the dynamics of the stock market. A direct percolation method is used to create a hierarchy of clusters of active traders on a two dimensional grid. Active traders are characterised by the decision to buy, (+1), or sell, (-1), a …
Combining automata learning and model-based testing generates sufficient training data for hybrid systems.
problem Challenges in constructing models of hybrid systems that combine physical and digital behavior.
method Exploits a combination of automata learning and model-based testing to generate sufficient training data.
result Recurrent neural networks trained with this data achieved significantly better results compared to models learned from random data.
State-regularized RNNs improve interpretability and performance on long-term memory tasks.
problem RNNs struggle with long-term memory and lack of interpretability.
method Introduce a stochastic state transition mechanism to limit state transitions to a finite set.
result State-regularized RNNs perform better on tasks requiring long-term memory.
Dual neural network architecture improves accuracy and interpretability.
problem Improving neural network interpretability and accuracy.
method Stacked recurrent and feedforward layers, binary activation function.
result Binary activation leads to simpler, more interpretable models with higher accuracy.
The paper presents an algorithm to determine discreteness of certain groups.
problem Determining discreteness of specific groups generated by parabolic transformations.
method Algorithmic approach based on historical mathematical paradigms.
result Equivalence of different approaches to the discreteness problem.
Reservoir computers and RNNs fall short of optimal prediction for stochastic PDFA.
problem Predicting stochastic processes generated by probabilistic deterministic finite-state automata.
method Generalized linear models, Reservoir computers, and Long Short-Term Memory (LSTM) RNNs were tested.
result Each method can fall short of maximal predictive accuracy by up to 50% after training.
We provide the first solution for model-free reinforcement learning of ω-regular objectives for Markov decision processes (MDPs). We present a constructive reduction from the almost-sure satisfaction of ω-regular objectives to an almost- sure reachability problem and extend this technique to learning how to control an …
Unified recurrent networks reveal differences in complexity levels of grammars.
problem Understanding the complexity and behavior of recurrent networks.
method Connecting recurrent networks with deterministic finite automata and formal grammars.
result Unified recurrent networks improve performance and match grammars from different complexity levels.
MBQC linked to CQCA, yielding efficient Ansätze.
problem Quantum computation efficiency and Ansatz adaptation.
method Relating MBQC to CQCA and constructing Ansätze.
result MBQC Ansätze can lead to different performances on learning tasks.
MPNPs use message passing to exploit relational structure in stochastic processes.
problem Lack of relational information in NPs limits their effectiveness in tasks with neighborhood rules.
method Introduce MPNPs that explicitly use relational structure through message passing.
result MPNPs outperform NPs in tasks with relational information, showing significant gains in few-shot learning.
Formal constraints improve RL safety in complex environments.
problem Safety constraints in reinforcement learning for complex environments.
method Specify constraints in formal languages, instantiate as finite automata, augment MDP states, learn dense cost function.
result Improved safety in training RL algorithms over various constraints.
This note gives a brief survey of the minimum dilatation problem for pseudo-Anosov mapping classes, and the first explicit train track description of an infinite family of pseudo-Anosov mapping classes with orientable stable foliations and the conjectural minimum dilatation for closed surfaces of even genus g≥2.
Recurrent neural networks trained on regular languages exhibit stable states that can recover from noise.
problem Stability of internal states in recurrent neural networks trained on regular languages.
method Empirical study with analysis of network activation and transitions between states.
result Recurrent neural networks trained on regular languages can recover from random perturbations and maintain stable states.
We introduce a new class of possibly noncompact n-dimensional manifolds without boundary associated to finite data which we call topological automata. This class is large enough to contain many interesting examples of open 2-dimensional and 3-dimensional manifolds of interest to low-dimensional topologists. Our main re…
We discuss here the mean-field theory for a cellular automata model of meta-learning. The meta-learning is the process of combining outcomes of individual learning procedures in order to determine the final decision with higher accuracy than any single learning method. Our method is constructed from an ensemble of inte…
Paper proves hardness of learning various complex models under local pseudorandom generators.
problem Hardness of learning various complex models.
method Existence of local pseudorandom generators.
result Proves hardness of learning shallow ReLU neural networks and other models.
Hidden tree Markov models allow learning distributions for tree structured data while being interpretable as nondeterministic automata. We provide a concise summary of the main approaches in literature, focusing in particular on the causality assumptions introduced by the choice of a specific tree visit direction. We w…
We investigate the problem of reliable communication between two legitimate parties over deletion channels under an active eavesdropping (aka jamming) adversarial model. To this goal, we develop a theoretical framework based on probabilistic finite-state automata to define novel encoding and decoding schemes that ensur…
Enhanced ontology learning from text improves question-answering systems.
problem Improving ontology learning from unstructured text for better question-answering systems.
method Heuristically modified FP-Tree with DFA for concept extraction and frequent pattern mining for ontology learning.
result Our approach significantly improves question-answering system performance, answering 80% of questions compared to 28.4% with Text2Onto.
This work verifies recurrent neural networks using DFA and shows some are robust to adversarial samples.
problem Verifying recurrent neural networks for adversarial robustness.
method Metric for string distance, DFA for oracle, Tomita grammars for testing.
result Some recurrent networks are robust to adversarial samples.
A fixed point theorem is proved for inverse transducers, leading to an automata-theoretic proof of the fixed point subgroup of an endomorphism of a finitely generated virtually free group being finitely generated. If the endomorphism is uniformly continuous for the hyperbolic metric, it is proved that the set of regula…