Symbolic aggregate approximation

Overview

Symbolic aggregate approximation (SAX) replaces a numeric series with a short string of symbols. It averages the series over fixed segments (piecewise aggregate approximation) and maps each average to one of \alpha symbols, using breakpoints that split a standard normal into \alpha equally likely bins 2311.18029 §3 2311.18029 eq. 1 2311.18029 eq. 2. Once a series is a string of symbols, counting substrings gives a fixed-length feature vector, which is the route the bag-of-words classifiers take.

The problem the windowed variants target is cost and repeatability. Earlier bag-of-patterns classifiers use SAX over sliding windows and are deterministic and interpretable, but their window-wise step has quadratic worst-case cost in the series length when the window grows with the series 2311.18029 §4.1 2311.18029 §4.3. The paper formalises window-wise SAX, which earlier work used without a formal definition 2311.18029 §4.1.

This page currently rests on one paper card. All results below are author-reported.

Variants

Classic SAX: segment means and breakpoints

Split the series into equal segments, average each one, and map each average to a symbol with Gaussian quantile breakpoints 2311.18029 §3 2311.18029 eq. 2. The output is one word per series. The paper uses this as the base step of the variants below. Card: BORF paper, arXiv:2311.18029.

Windowed SAX with dilation and stride (wSAX)

Slide a receptive field of length w across the signal. Its points sit d apart, and fields start s points apart 2311.18029 §4 2311.18029 eq. 3. Each field is split into l segments, and each segment mean is z-normalised with the mean and standard deviation of the whole field, then binned into symbols 2311.18029 §4.1 2311.18029 eq. 12. Moving averages compute every segment mean once, so the per-window cost does not grow with window size 2311.18029 §4.1 2311.18029 §4.3. Card: BORF paper, arXiv:2311.18029.

Bag of receptive fields (BORF)

Encode each field's l symbols as one integer, reading the word in base \alpha with the first symbol most significant 2311.18029 §4.2 2311.18029 eq. 13. Count the words over many configurations of (w, d, l) and store the counts as a sparse tensor indexed by series, signal and word 2311.18029 §4.2 2311.18029 §4.3. The paper's default heuristic sets window sizes from powers of two up to the series length, dilations up to \log_2 \log_2 n, word lengths 2, 4 and 8, alphabet size 3 and stride 1 2311.18029 §5 2311.18029 tab. 4. The counts pass through an element-wise inverse hyperbolic sine and a ridge classifier 2311.18029 §5. Card: BORF paper, arXiv:2311.18029.

The paper's explanation is a SHAP value per count, with saliency maps over time. A contained word's contribution is spread over the points it came from, and a word that is absent is shown by its typical shape from a background set 2311.18029 §4.5 2311.18029 eq. 14 2311.18029 fig. 3.

When to use which

Against other SAX-based methods, the paper reports BORF as the most accurate and the fastest 2311.18029 §5 2311.18029 fig. 7. In its ablation on 42 development datasets, the largest accuracy loss comes from restricting word length to 2 (about 0.19). Dropping the arcsinh step costs about 0.02 2311.18029 tab. 4.

Implementation sketch

Language-agnostic pseudocode for the windowed core. Classic SAX is the sax_symbol step.

# Symbol of one value from its breakpoints  [§3] [eq. 2]
# Breakpoints: Gaussian quantiles into alpha equal-probability bins
def sax_symbol(value, breakpoints):
    # Count breakpoints strictly below the value  [eq. 2]
    symbol = 0
    for b in breakpoints:
        if value > b:
            symbol += 1
    return symbol

# Windowed SAX word for each receptive field of one signal  [§4.1]
# Input: signal, window w, dilation d, stride s, word length l
def window_words(signal, w, d, s, l, alphabet_size, breakpoints):
    # Segment size; the paper assumes w is divisible by l  [§4.1]
    q = w // l
    words = []
    # One field per start point, step s  [§4] [eq. 3]
    for i in range(num_fields(len(signal), w, d, s)):
        # Points of the dilated field  [§4] [eq. 3]
        points = [signal[i * s + d * k] for k in range(w)]
        # Mean and population std of the whole field  [§4.1] [eq. 10]
        mu = mean(points)
        sigma = pop_std(points)
        word = 0
        for j in range(l):
            # Segment mean of this field  [§4.1] [eq. 6]
            seg_mean = mean(points[j * q : (j + 1) * q])
            # Z-normalise with the field's own statistics  [§4.1] [eq. 12]
            z = (seg_mean - mu) / sigma
            # Symbol, then append as the next base-alpha digit  [eq. 13]
            word = word * alphabet_size + sax_symbol(z, breakpoints)
        words.append(word)
    return words

Notes on where variants differ:

• Flat windows. The paper sets a threshold \theta = 0.15 for near-flat windows and reports that removing it costs about 0.013 accuracy and adds about 8 s on the development set 2311.18029 §5 2311.18029 tab. 4. The sketch above divides by zero when sigma is 0, so an implementation needs its own rule. The paper does not give one for exactly zero.
• Arcsinh. Apply the inverse hyperbolic sine to the counts before the ridge classifier 2311.18029 §5. The paper does not state the ridge regularisation strength 2311.18029 §5.
• Vocabulary. The paper defines the bag over a fixed set of patterns 2311.18029 §4.2. The library's default vocabulary is built from the training data instead; see the card's Paper vs code section.

Contradictions

No disagreement between papers, since only one paper is on this page. The paper and its library disagree on the following; each side is cited, and the paper's version is the one this page follows:

• Ties at breakpoints. The paper assigns a value equal to a breakpoint to the lower symbol 2311.18029 eq. 2. The library assigns it to the upper symbol, as described in the card's Paper vs code section.
• Flat-window rule. The paper uses \theta = 0.15 and treats values at or below it as constant 2311.18029 §5. The library's default threshold is 0.0, and its comparison is strict; see the card.

Papers

• BORF paper, arXiv:2311.18029: defines window-wise SAX with dilation and stride, a moving-average speed-up, and a deterministic bag-of-receptive-fields classifier. Author-reported on 158 datasets: tied with ROCKET and MiniRocket on accuracy, second-best runtime.