# Predictive Quantization and Symbolic Dynamics
## 1 Introduction  
In this paper, we describe a method for time series symbolization that allows novel applications for various types of signals, such as audio, gestures, and more. Symbolization involves the transformation of raw time series measurements into a series of discretized symbols that are processed to extract information about the generating process. In this paper, the problem of symbolization is formulated in information theoretical terms as a information dynamics bottleneck that optimizes a trade-off between the representation fidelity and predictive quality of the latent discrete representation. The algorithm developed in this paper performs an embedding of the data in a vector space followed by a step of quantization that maximizes a measure that we call information rate that uses approximate string-matching methods to evaluate the mutual information between the signal in the past and present. The move to symbolic data allows for capturing long-term structures that are hard to model using real-valued autoregressive distribution estimation methods. Analysis of data using symbolic dynamics allows the characterization of the time series by various analysis methods, such as recurrent quantification analysis, motif finding, segmentation, and querying, as well as novel methods for transfer entropy estimation between pairs of sequences. There are multiple works that describe the symbolization of time series. A general feature of symbolic dynamics analysis is that it assumes the existence of so-called generating partitions that divide the phase space of the time series trajectory into regions, such that each unique trajectory in phase space is associated with a unique sequence of symbols. Generating partitions can be constructed for certain models; however there is no generalapproach for constructing generating partitions from observations of an unknown system. Accordingly, in the model-free case, various data aggregations techniques are used to cluster nearby data points to induce such partitions. One such popular method, largely due to its simplicity and intuitive nature, is the so-called \"threshold-crossing\" technique. It operates by replacing real-valued data with symbolic indices based on the data values falling within a certain numeric interval. In extreme cases, a single threshold is used to create a binary representation with values above and below thresholds assigned 1's and 0's, respectively. An example of multi-threshold symbolization is the symbolic aggregate approximation (SAX) [1], shown in Figure 1.  
In the SAX approach, a scalar quantization is performed along an amplitude axis using an average value over a fixed time interval. First, the number of letters \(\alpha\) and maximal sequence length \(\omega\) are manually chosen so as to have an overall small number of symbols while not losing too much data detail. The quantization levels are found by fitting a normal distribution to the data amplitude distribution aggregated over time and across multiple data instances. Since the method is meant to be applied for time series databases, for a given \(\omega\), some observations may not be \(\omega\) letters long. It is evident from this example that the choice of partition levels is paramount to establishing a correspondence between the continuous-valued data and their symbolic representation. As an extreme example, for a binary partition, setting a threshold outside of the range of the data values will result in a trivial constant symbolic sequence. Errors in coarse-grained partition relative to original system dynamics can lead to a gross misrepresentation of the dynamical system. In particular, one way to demonstrate sensitivity to threshold change is by mapping the system dynamics into a graph structure where each edge carries a label from the symbolic representation, and the vertices are labeled by all possible words in a sequence of a certain length.