# Predictive Quantization and Symbolic Dynamics
## 3 Symbolization Dynamics  
Given a time series or multi-variable observations of a signal \(X=x_{1},x_{2},\ldots,x_{n},\ldots,x_{T}\), the goal of symbolization is to find a sequence \(S=s_{1},s_{2},\ldots,s_{n},\ldots,s_{T}\) of the same length \(T\), where each observation \(x_{n}\) is labeled by a symbol \(s_{n}\) coming from a finite-sized alphabet \(s_{i}\in\Sigma\). The essential step in the symbolization algorithm described below is finding a threshold value \(\theta\) that partitions the space of observations into categories based on repeated sub-sequences of motifs. For each new observation, a threshold \(\theta\) is used to determine if the incoming \(x_{n}\) is sufficiently similar to an observation that appears as a continuation to an earlier-identified repeated sub-sequence pointed to by a suffix link from a previous step \(n-1\). The recursive procedure of finding repeated suffixes is based on a string-matching algorithm called Factor Oracle (_FO_ hereafter), which will be explained next. Using a repeated suffix link, the algorithm assigns two data points that appear as continuations of the two linked sub-sequences, \(x_{i}\) and \(x_{j}\), and the same label \(s_{i}=s_{j}\in\Sigma\) if \(||x_{i}-x_{j}||\leq\theta\). In extreme cases, setting \(\theta\) too low leads to assigning different labels to every observation in \(X\), while setting \(\theta\) too high leads to assigning the same label to every observation in \(X\). The basis for the selection of a threshold is an analysis of the predictive properties of the suffix structure (also called the oracle structure) found at each threshold value. Wedefine _information rate_ (_IR_ hereafter) as a measure that is used to select the optimal \(\theta\) for an individual time series. We show an example of the oracle structure with extreme \(\theta\) values in Figure 5. It should be noted that the alphabet of the symbolization is constructed dynamically, as new symbols are added when an input sample cannot be assigned to one of the existing clusters that were labeled earlier. We will denote the resulting alphabet for a given \(\theta\) as \(\Sigma_{\theta}\). In the process of _IR_ analysis, the system is performing a search over different \(\theta\) values, where for each threshold value, a different suffix structure is constructed for each resulting symbolization of the same time series, as shown in Figure 5. To select the symbolization with the most informative oracle structures, _IR_ is used to measure the average relative reduction of uncertainty of the current sample in a time series when past samples are known. Let the past samples of a time series be denoted by \(x_{\text{past}}=\{x_{1},x_{2},\ldots,x_{n-1}\}\); the current samples \(x_{n}\) and \(H(x)=-\sum P(x)\log_{2}P(x)\) with the entropy of \(x\) with \(P(x)\) and the distribution of \(x\); and the statistical definition of _IR_ is the mutual information between \(x_{\text{past}}\) and \(x_{n}\),  
\[I(x_{\text{past}},x_{n})=H(x_{n})-H(x_{n}|x_{\text{past}}). \tag{8}\]  
In Ref. [6], the above statistical definition of _IR_ was replaced by an algorithmic notion of compression gain using a measure of code length \(C(\cdot)\) instead of the entropy term \(H(\cdot)\) in (8). The _IR_ algorithm searches over all possible values of the quantization threshold \(\theta\) (9) to find the highest _IR_ value  
\[IR(x_{\text{past}},x_{n})=\max_{\theta,s_{i}\in\Sigma_{\theta}}[C(s_{n})-C(s_ {n}|s_{\text{past}})]. \tag{9}\]  
The _IR_ measure has been used extensively in the analysis of music information contents, known as music information dynamics [7; 8]. The value of the algorithmic _IR_ defined in (9) can then be robustly calculated by complexity measures associated with a compression algorithm with \(C(s_{n})\)--the number of bits used to compress \(s_{n}\) independently--and \(C(s_{n}|s_{\text{past}})\)--the number of bits used to compress \(s_{n}\) using \(s_{\text{past}}\). In Ref. [9], a lossless compression algorithm, _Comporr_, based on _FO_, is provided.