This is an extended version of our publication Learning state machines from data streams: A generic strategy and an improved heuristic, International Conference on Grammatical Inference (ICGI) 2023, Rabat, Morocco. It has been extended with a formal proof on PAC-bounds, and the discussion and analysis of a similar approach has been moved from the appendix and now has a full dedicated section. State machine models are models that simulate the behavior of discrete event systems, capable of representing systems such as software systems, network interactions, and control systems, and have been researched extensively. The nature of most learning algorithms however is the assumption that all data be available at the beginning of the algorithm, and little research has been done in learning state machines from streaming data. In this paper, we want to close this gap further by presenting a generic method for learning state machines from data streams, as well as a merge heuristic that uses sketches to account for incomplete prefix trees. We implement our approach in an open-source state merging library and compare it with existing methods. We show the effectiveness of our approach with respect to run-time, memory consumption, and quality of results on a well known open dataset. Additionally, we provide a formal analysis of our algorithm, showing that it is capable of learning within the PAC framework, and show a theoretical improvement to increase run-time, without sacrificing correctness of the algorithm in larger sample sizes.
Figures & tables
Figure 1: The two solutions to the problem of uniform distributions in the sketches.
Heuristic
F==0
F==1
F==2
F==3
F==4
Alergia
1m45s
1m55s
2m8s
2m24s
-
CSS
-
2m1s
2m15s
2m14s
2m50s
CSS-MinHash
-
-
-
3m14s
3m40s
SpaceSave
-
4m37s
6m51s
-
-
Table 1: Runtime comparisons of the heuristics and different future length parameters F , F being a placeholder for either k , Fs , or L . Empty fields do not exist or are not interesting to us.
Figure 2: Boxplots of all heuristics. Due to the difference in magitude in between the SpaceSave heuristic and the other heuristics we separated them into two sub-plots.
Parameter
L==1
L==2
ϵ
0.005
0.005
δ
0.05
0.05
μ
0.6
0.4
K (number of prefixes to track)
20
20
r (number of bootstrapped sketches)
10
10
Table 2: Hyperparameters used for the SpaceSave heuristic. The parameter’s meaning can be taken from ( Balle et al., 2012 ) .
Figure 5
Strategy
Prob. 1
Prob. 5
Prob. 11
Prob. 18
Prob. 23
Prob. 34
Prob. 45
Batch
250MB
56MB
1.1GB
3.1GB
1.0GB
2.4GB
257MB
Stream old
15MB
13MB
34MB
123MB
63MB
53MB
13MB
Stream new
14MB
13MB
29MB
123MB
63MB
44MB
13MB
Table 3: Memory-footprints compared on a few selected problems. Heuristic employed: CSS-MinHash Fs==4 .
Figure 3: The function f(m0) with varying μ and α .
We prove that Moore machines can be exactly realized as state-space models (SSMs), establishing a formal correspondence between symbolic automata and these continuous machine learning architectures. These Moore-SSMs preserve both the complete symbolic structure and input-output behavior of the original Moore machine, but operate in Euclidean space. With this correspondence, we compare the training of SSMs with both passive and active automata learning. In recovering automata from the SYNTCOMP benchmark, we show that SSMs require orders of magnitude more data than symbolic methods and fail to learn state structure. This suggests that symbolic structure provides a strong inductive bias for learning these systems. We leverage this insight to combine the strengths of both automata learning and SSMs in order to learn complex systems efficiently. We learn an adaptive arbitration policy on a suite of arbiters from SYNTCOMP and show that initializing SSMs with symbolically-learned approximations learn both faster and better. We see 2-5 times faster convergence compared to randomly initialized models and better overall model accuracies on test data. Our work lifts automata learning out of purely discrete spaces, enabling principled exploitation of symbolic structure in continuous domains for efficiently learning in complex settings.
William Fishell, Sam Nicholas Kouteili, Mark Santolucito
Columbia University · Yale University · Barnard College, Columbia University
Streaming data systems increasingly underpin Machine Learning workflows that maintain large numbers of continuously updated aggregations. In production settings, each incoming event typically triggers read-modify-write operations to persistent storage, making high-frequency state updates a dominant source of latency, contention, and operational cost. In this work, we decouple inference from state persistence in streaming Machine Learning pipelines via probabilistic thinning: every event is scored, but durable state updates are selectively triggered by informative events. Unlike approaches that shed input or state, we show that persistence-path control is achievable without a high-frequency in-memory control plane or cross-worker coordination, relying exclusively on approximate statistics retrieved from disk-backed key-value stores. We model the resulting stochastic processes, derive bounds on filtering rates, and prove that common time-based aggregations remain unbiased under variance-aware formulations, preventing systemic error accumulation. We evaluate the approach in a controlled setting that isolates per-event costs, demonstrating substantial reductions in storage Input/Output and serialization overhead. Across experiments, up to 90% of events are excluded from the persistence path while preserving and in some cases improving downstream utility.
Latent state space systems are ubiquitous in statistical modelling, arising naturally when time series are observed through noisy measurements. However, training deep state space models (DSSMs) at scale remains difficult. Two largely distinct strategies have emerged for training DSSMs. The first, auto-encoding DSSMs, trains generative models by optimising a variational lower bound. The second backpropagates through the outputs of classical sequential Monte Carlo (SMC) algorithms. Such approaches can train DSSMs for both discriminative and generative tasks, but their inherently sequential forward passes scale poorly on modern hardware. We propose parallel variational Monte Carlo (PVMC), a new training method that bridges these paradigms and robustly trains DSSMs for both discriminative and generative tasks. Across a set of benchmark experiments, PVMC matches or exceeds state-of-the-art performance while training 10× faster than the fastest competing SMC-based approach.
John-Joseph Brady, Nikolas Nusken, Yunpeng Li
Centre for Oral, Clinical and Translational Sciences, King’s College London, London, United Kingdom · Department of Mathematics, King’s College London, London, United Kingdom