Letting the Grammar Decide: Ambiguity-Aware Discretization for Grammar-Based Time-Series Mining

A popular way to find repeated patterns and anomalies in long time series is to turn the signal into a string of letters and then compress that string into a grammar. A grammar here is a set of nested rules, where each rule names a substring that repeats. Frequent rules mark recurring shapes, called motifs. Stretches that no rule covers mark anomalies. The weak point is the first step. Each short segment's average value is assigned a letter by comparing it with fixed thresholds. A segment whose average lies just below a threshold gets a different letter from an almost identical segment just above it. One flipped letter stops two occurrences of a motif from matching, so the grammar never builds the low-level rule. Every higher-level rule that would have contained it then fails to appear. A small, local mistake at the bottom of the hierarchy wipes out structure above it.

This proposal treats that failure as a problem of error spreading up a hierarchy, and borrows the standard remedy from that literature: do not commit to an uncertain decision before the later stage has seen it. When a segment's average sits within its own statistical noise of a threshold, we keep both candidate letters. The grammar-building step then chooses between them, picking the letter that lets the segment join a repetition the rest of the data already supports. The two-sentence version is this. Letter flips near thresholds are the main reason grammar-based motif and anomaly discovery breaks, and their damage grows with the length of the pattern. Marking only statistically ambiguous letters, and letting rule formation resolve them jointly across all occurrences, should recover the lost rules at a cost far below an ensemble of hard discretizations.

Core Claim

We make two claims, one diagnostic and one constructive.

The diagnostic claim concerns how fast patterns are lost. Suppose each letter in a pattern that expands to $L$ letters flips independently with probability $p$. This probability is set by the noise level relative to the gap between thresholds. Then a given occurrence survives intact with probability $(1-p)^L$. A rule needs at least two intact, identical occurrences to form. So the expected number of recoverable occurrences of a deep rule falls exponentially with its expanded length. This exponential form follows directly from the independent-flip assumption, and we will test the assumption itself. It predicts that grammar-based methods lose long motifs first and lose them sharply. That matches the "jagged" sensitivity to discretization settings reported by Ensemble Grammar Induction For Detecting Anomalies in Time Series.

The constructive claim is about joint resolution. Consider what happens if you merely move the thresholds or resample the discretization settings. This changes which positions flip but not how many, so each ensemble member still suffers the same exponential loss. Resolving each ambiguous letter jointly with every other occurrence of the pattern it belongs to removes the loss on the ambiguous positions. The key ingredient is therefore not averaging over discretizations but letting the higher level correct the lower level.

Background and Positioning

The standard discretization is Symbolic Aggregate Approximation (SAX), described in Characterizing Residential Load Patterns by Household Demographic and Socioeconomic Factors. SAX averages equal-length segments and maps each average to a letter using thresholds chosen so that, for normalized data, every letter is equally likely. GrammarViz 2.0 feeds SAX strings to the Sequitur grammar-compression algorithm and reads motifs from frequent rules and anomalies from low rule-coverage curves. It is the pipeline we modify. It treats every letter as ground truth. Ensemble Grammar Induction is the closest prior work and our main competitor. It fights brittleness by running many grammar inductions with randomly drawn word length $w$ and alphabet size $a$, discarding flat coverage curves, and median-filtering the rest. Every member still uses hard letters, so it averages over flip patterns without repairing any of them. RED CoMETS follows the same logic for classification, with random parameter choices and voting across symbolic views.

Other symbolic methods, ECG-Byte and TimeSliver, also rely on hard letters. ECG-Byte uses greedy byte-pair merges on letter-quantized ECG. TimeSliver uses flat SAX-like stencils inside a linear classifier. They motivate the problem, but neither builds a multi-level grammar, so we use them only as context.

The hierarchical-error literature supplies both the method and its limits. Stacked Hierarchical Labeling shows that passing soft label proportions rather than hard labels lets later stages correct earlier ones. On MSRC-21 its confident predictions covered 79% of the data at 89% accuracy. BeamAggR keeps several candidates through a question tree and gains 8.5% on average over greedy selection. It also warns that the cost of multiple hypotheses can explode. That warning is why we mark ambiguity only where the data's own noise justifies it, and we cap each ambiguous position at two letters. A Neural Layered Model for Nested Named Entity Recognition documents the bottom-up version of this failure: missing inner entities block outer ones. This is exactly the missing-rule failure we predict for grammars.

A Part-Based Deep Neural Network Cascade Model for Human Parsing is a constraining result. In that cascade, adding smoothing refinement lowered accuracy because it erased small, real details. That is a direct warning that our resolution step could erase true anomalies, and the experiments test for it.

Research Program

The first component is a noise-scaled ambiguity test. For a segment of $n$ raw points with average $\bar x$ and within-segment standard deviation $s$, the standard error of the average is roughly $s/\sqrt{n}$. We call the position ambiguous if

$$|\bar x - \beta| < \kappa\, s/\sqrt{n},$$

where $\beta$ is the nearest threshold and $\kappa$ is a single margin parameter. An ambiguous position carries the pair of letters on either side of $\beta$. All other positions stay hard. The expected fraction of ambiguous positions grows roughly linearly in $\kappa$ times the noise-to-gap ratio. We will report this fraction for every dataset so that the added cost is visible.

The second component is ambiguity-aware grammar induction. Sequitur works online and commits early, so we switch to an offline, repeated-pair style of compression. This style repeatedly replaces the most frequent adjacent pair with a new rule. We need two changes to it. First, pair counts are computed over the ambiguous string: a pair touching an ambiguous position counts toward each compatible concrete pair, with the count split across the options. Second, when a pair is chosen as a rule, every ambiguous position it absorbs is fixed to the letter that pair requires, and the counts are updated. Resolution is therefore driven entirely by support from elsewhere in the series. This is the time-series analogue of the stacking idea: the upper level decides what the lower level meant. Everything after grammar induction stays unchanged from GrammarViz: motifs come from frequent rules and anomalies from low rule coverage. Any gain can then be credited to the input side.

The third component is a propagation analysis. For each induced rule we record its depth and expanded length. For planted motifs we record whether each true occurrence is covered by the correct rule. We then fit survival against expanded length for hard SAX and for the ambiguity-aware version. The prediction is an exponential decay for hard SAX whose rate matches the measured flip rate $p$, and a much flatter decay for our method. If flips turn out to be strongly correlated rather than independent, as they would be under slow baseline drift, the exponential form will fail. Seeing that failure would itself tell us which kind of noise the method addresses.

Baselines

The naive reference point is GrammarViz 2.0 with hard SAX at a fixed, cross-validated $(w, a)$ and window length. This shows the size of the flip problem and gives the survival curve we expect to see decay.

The strongest existing symbolic competitor is Ensemble Grammar Induction, as described in Ensemble Grammar Induction For Detecting Anomalies in Time Series. It will be re-implemented with random $(w, a)$ sampling, pruning of flat curves, and median aggregation, on the same UCR series (ECG, GunPoint, Wafer, Trace, StarLightCurve) and the 600,000-point fridge-freezer record. The window length will be identical for all methods. We will give it an ensemble size chosen so that its total wall-clock time is at least that of our method. The paper reports anomaly results competitive with or better than discord search on Trace and StarLightCurve, and a runtime of about one minute on the fridge-freezer record, roughly ten times faster than STOMP. No reported accuracy scalar for this method was found on Lacuna, so we will report both methods under a common protocol. Beating it means higher planted-motif recovery and higher anomaly hit rate at equal or lower runtime. A draw on anomalies combined with a clear win on long-motif recovery would still support the diagnostic claim, but only weakly support the method.

The ablation that isolates the key ingredient is a jittered-threshold ensemble. It runs $K$ hard SAX strings at the same $(w, a)$ with thresholds shifted by random amounts of the same size as our margin, and aggregates their coverage curves the same way. $K$ is set so that the total number of letters processed matches our method's ambiguous-string budget. This baseline has the same information about where thresholds are uncertain but resolves each string independently. If it matches us, joint resolution is not doing the work. Two further ablations separate the parts of the method. One marks the same number of positions as ambiguous but picks them at random rather than by margin. The other keeps the split pair counts but never fixes letters, so rules can form over mixed letters without any resolution.

The strongest non-symbolic reference for anomalies is exact discord search with the matrix profile (STOMP). For STOMP, the file reports only the runtime comparison against Ensemble Grammar Induction, and no accuracy figure was found on Lacuna. We run it on identical series and record anomaly hit rate and runtime.

Why not just…?

Why not just ensemble over discretization settings, as Ensemble Grammar Induction already does? This is the most serious threat. Ensembling smooths the jagged sensitivity over $(w, a)$, but noise near thresholds still flips about the same fraction of letters in every member. Under the survival argument above, every member therefore loses long motifs at the same exponential rate. The jittered-threshold ablation at matched compute tests exactly this. If it recovers long planted motifs as well as joint resolution does, we will report that the simpler method suffices and reduce our contribution to the diagnostic analysis.

Why not just use a smaller alphabet or longer segments, so that fewer letters sit near thresholds? Fewer letters mean wider gaps between thresholds and fewer flips. They also blur motifs that differ in amplitude and merge distinct shapes into one rule. We will sweep $a$ and $w$ for hard SAX and plot planted-motif precision against recall. The ambiguity-aware method must lie above that whole curve, not just beat one setting. If a coarse alphabet reaches the same point on the curve, the proposal fails on that dataset.

Why not just drop symbols and use exact continuous discord search? For anomaly detection alone this may be enough, and STOMP is in the baselines for that reason. Grammars offer variable-length motifs, nested structure, and compression that exact subsequence search does not. GrammarViz 2.0 was built for these. Our claim is limited to making that pipeline reliable. It is not a claim that symbolic methods beat continuous ones at single-anomaly search.

Why not just smooth the letter string afterwards, for example by removing isolated flips? The human-parsing cascade found that smoothing refinement removed small real details and lowered accuracy A Part-Based Deep Neural Network Cascade Model for Human Parsing. A local smoother cannot tell a noise flip from a short true anomaly. Our resolution uses support from repeated patterns across the whole series rather than local neighbors. We will still include a majority-of-neighbors smoother as an extra baseline, to show the difference on short planted anomalies.

Proposed Experiments

The decisive experiment is synthetic. We plant motifs of controlled expanded length (8 to 128 letters) and short anomalies into random-walk and periodic backgrounds, and vary the noise-to-gap ratio. We then measure the fraction of planted occurrences covered by a correct rule. Recovery is plotted against expanded length for every method. This directly tests both the exponential-loss prediction and whether joint resolution flattens it.

The key safety check runs the method on pure random walks with nothing planted. The number and coverage of rules must not grow relative to hard SAX, because false motifs created by forcing matches are the obvious failure mode. The same check applies to planted anomalies: those larger than the noise margin must remain uncovered, which confirms that resolution does not absorb them.

On real data, the UCR series and the fridge-freezer record test anomaly hit rate and runtime against Ensemble Grammar Induction and STOMP. We also report the ambiguous-position fraction as a function of $\kappa$ and show results across a range of $\kappa$ rather than a single tuned value.

A secondary, exploratory check uses PTB-XL, described in PTB-XL, a large publicly available electrocardiography dataset. There we measure how consistently a rule covering the QRS complex, the sharp central spike of each heartbeat, forms across beats of the same patient. This probes whether the effect carries over to physiological signals, where it would matter for tokenizers like ECG-Byte. We make no claim about downstream report generation, where ECG-Byte reports a Rouge-L of 47.08.

The proposal fails if the jittered-threshold ensemble matches joint resolution at equal compute, or if gains on long motifs come with inflated rules on null data.