Estimating a generating partition from observed time series: symbolic shadowing

Symbolic extended dynamic mode decomposition

In this paper, we present a new method of performing extended dynamic mode decomposition (EDMD) on systems, which admit a symbolic representation. EDMD generates estimates of the Koopman operator, K, for a dynamical system by defining a dictionary of observables on the space and producing an estimate, Km, which is restricted to be invariant on the span of this dictionary. A central question for the EDMD is what should the dictionary be? We consider a class of chaotic dynamical systems with a known or estimable generating partition. For these systems, we construct an effective dictionary from indicators of the "cylinder sets," which arise in defining the "symbolic system" from the generating partition. We prove strong operator topology convergence for both the projection onto the span of our dictionary and for Km. We also prove practical finite-step estimation bounds for the projection and Km as well. Finally, we demonstrate some numerical results on eigenspectrum estimation and forecasting applied to the dyadic map and the logistic map.

Machine-Learning Optimized Measurements of Chaotic Dynamical Systems via the Information Bottleneck

Deterministic chaos permits a precise notion of a "perfect measurement" as one that, when obtained repeatedly, captures all of the information created by the system's evolution with minimal redundancy. Finding an optimal measurement is challenging and has generally required intimate knowledge of the dynamics in the few cases where it has been done. We establish an equivalence between a perfect measurement and a variant of the information bottleneck. As a consequence, we can employ machine learning to optimize measurement processes that efficiently extract information from trajectory data. We obtain approximately optimal measurements for multiple chaotic maps and lay the necessary groundwork for efficient information extraction from general time series.

A review of symbolic dynamics and symbolic reconstruction of dynamical systems

Discretizing a nonlinear time series enables us to calculate its statistics fast and rigorously. Before the turn of the century, the approach using partitions was dominant. In the last two decades, discretization via permutations has been developed to a powerful methodology, while recurrence plots have recently begun to be recognized as a method of discretization. In the meantime, horizontal visibility graphs have also been proposed to discretize time series. In this review, we summarize these methods and compare them from the viewpoint of symbolic dynamics, which is the right framework to study the symbolic representation of nonlinear time series and the inverse process: the symbolic reconstruction of dynamical systems. As we will show, symbolic dynamics is currently a very active research field with interesting applications.

Maximally predictive states: From partial observations to long timescales

Isolating slower dynamics from fast fluctuations has proven remarkably powerful, but how do we proceed from partial observations of dynamical systems for which we lack underlying equations? Here, we construct maximally predictive states by concatenating measurements in time, partitioning the resulting sequences using maximum entropy, and choosing the sequence length to maximize short-time predictive information. Transitions between these states yield a simple approximation of the transfer operator, which we use to reveal timescale separation and long-lived collective modes through the operator spectrum. Applicable to both deterministic and stochastic processes, we illustrate our approach through partial observations of the Lorenz system and the stochastic dynamics of a particle in a double-well potential. We use our transfer operator approach to provide a new estimator of the Kolmogorov-Sinai entropy, which we demonstrate in discrete and continuous-time systems, as well as the movement behavior of the nematode worm C. elegans.

A Spherical Phase Space Partitioning Based Symbolic Time Series Analysis (SPSP—STSA) for Emotion Recognition Using EEG Signals

Emotion recognition systems have been of interest to researchers for a long time. Improvement of brain-computer interface systems currently makes EEG-based emotion recognition more attractive. These systems try to develop strategies that are capable of recognizing emotions automatically. There are many approaches due to different features extractions methods for analyzing the EEG signals. Still, Since the brain is supposed to be a nonlinear dynamic system, it seems a nonlinear dynamic analysis tool may yield more convenient results. A novel approach in Symbolic Time Series Analysis (STSA) for signal phase space partitioning and symbol sequence generating is introduced in this study. Symbolic sequences have been produced by means of spherical partitioning of phase space; then, they have been compared and classified based on the maximum value of a similarity index. Obtaining the automatic independent emotion recognition EEG-based system has always been discussed because of the subject-dependent content of emotion. Here we introduce a subject-independent protocol to solve the generalization problem. To prove our method’s effectiveness, we used the DEAP dataset, and we reached an accuracy of 98.44% for classifying happiness from sadness (two- emotion groups). It was 93.75% for three (happiness, sadness, and joy), 89.06% for four (happiness, sadness, joy, and terrible), and 85% for five emotional groups (happiness, sadness, joy, terrible and mellow). According to these results, it is evident that our subject-independent method is more accurate rather than many other methods in different studies. In addition, a subject-independent method has been proposed in this study, which is not considered in most of the studies in this field.

Batch and stream entropy with fixed partitions for chaos-based random bit generators

Measures are proposed for reliably estimating the entropy of bits produced in an entropy source using a chaotic physical system. The measures are reliable with respect to a "guessing" attack and depend on the end-to-end method of transfer of entropy from the chaotic physical system to the bit entropy source. Fixed partitions are considered to correspond with practical methods for fast digital sampling of analog signals. We propose two different measures corresponding to the batch and streaming modes of entropy transfer. Numerical examples are provided to demonstrate features of dependence of the batch and stream entropy on fixed partitions with uniform or nonuniform types of chaos.

A generalized permutation entropy for noisy dynamics and random processes

Permutation entropy measures the complexity of a deterministic time series via a data symbolic quantization consisting of rank vectors called ordinal patterns or simply permutations. Reasons for the increasing popularity of this entropy in time series analysis include that (i) it converges to the Kolmogorov-Sinai entropy of the underlying dynamics in the limit of ever longer permutations and (ii) its computation dispenses with generating and ad hoc partitions. However, permutation entropy diverges when the number of allowed permutations grows super-exponentially with their length, as happens when time series are output by dynamical systems with observational or dynamical noise or purely random processes. In this paper, we propose a generalized permutation entropy, belonging to the class of group entropies, that is finite in that situation, which is actually the one found in practice. The theoretical results are illustrated numerically by random processes with short- and long-term dependencies, as well as by noisy deterministic signals.

Permutations uniquely identify states and unknown external forces in non-autonomous dynamical systems

It has been shown that a permutation can uniquely identify the joint set of an initial condition and a non-autonomous external force realization added to the deterministic system in given time series data. We demonstrate that our results can be applied to time series forecasting as well as the estimation of common external forces. Thus, permutations provide a convenient description for a time series data set generated by non-autonomous dynamical systems.

A Locally Optimal Algorithm for Estimating a Generating Partition from an Observed Time Series and Its Application to Anomaly Detection

Estimation of a generating partition is critical for symbolization of measurements from discrete-time dynamical systems, where a sequence of symbols from a (finite-cardinality) alphabet may uniquely specify the underlying time series. Such symbolization is useful for computing measures (e.g., Kolmogorov-Sinai entropy) to identify or characterize the (possibly unknown) dynamical system. It is also useful for time series classification and anomaly detection. The seminal work of Hirata, Judd, and Kilminster ( 2004 ) derives a novel objective function, akin to a clustering objective, that measures the discrepancy between a set of reconstruction values and the points from the time series. They cast estimation of a generating partition via the minimization of their objective function. Unfortunately, their proposed algorithm is nonconvergent, with no guarantee of finding even locally optimal solutions with respect to their objective. The difficulty is a heuristic nearest neighbor symbol assignment step. Alternatively, we develop a novel, locally optimal algorithm for their objective. We apply iterative nearest-neighbor symbol assignments with guaranteed discrepancy descent, by which joint, locally optimal symbolization of the entire time series is achieved. While most previous approaches frame generating partition estimation as a state-space partitioning problem, we recognize that minimizing the Hirata et al. ( 2004 ) objective function does not induce an explicit partitioning of the state space, but rather the space consisting of the entire time series (effectively, clustering in a (countably) infinite-dimensional space). Our approach also amounts to a novel type of sliding block lossy source coding. Improvement, with respect to several measures, is demonstrated over popular methods for symbolizing chaotic maps. We also apply our approach to time-series anomaly detection, considering both chaotic maps and failure application in a polycrystalline alloy material.

Entropy-based generating Markov partitions for complex systems

Finding the correct encoding for a generic dynamical system's trajectory is a complicated task: the symbolic sequence needs to preserve the invariant properties from the system's trajectory. In theory, the solution to this problem is found when a Generating Markov Partition (GMP) is obtained, which is only defined once the unstable and stable manifolds are known with infinite precision and for all times. However, these manifolds usually form highly convoluted Euclidean sets, are a priori unknown, and, as it happens in any real-world experiment, measurements are made with finite resolution and over a finite time-span. The task gets even more complicated if the system is a network composed of interacting dynamical units, namely, a high-dimensional complex system. Here, we tackle this task and solve it by defining a method to approximately construct GMPs for any complex system's finite-resolution and finite-time trajectory. We critically test our method on networks of coupled maps, encoding their trajectories into symbolic sequences. We show that these sequences are optimal because they minimise the information loss and also any spurious information added. Consequently, our method allows us to approximately calculate the invariant probability measures of complex systems from the observed data. Thus, we can efficiently define complexity measures that are applicable to a wide range of complex phenomena, such as the characterisation of brain activity from electroencephalogram signals measured at different brain regions or the characterisation of climate variability from temperature anomalies measured at different Earth regions.

Prediction of flow dynamics using point processes

Describing a time series parsimoniously is the first step to study the underlying dynamics. For a time-discrete system, a generating partition provides a compact description such that a time series and a symbolic sequence are one-to-one. But, for a time-continuous system, such a compact description does not have a solid basis. Here, we propose to describe a time-continuous time series using a local cross section and the times when the orbit crosses the local cross section. We show that if such a series of crossing times and some past observations are given, we can predict the system's dynamics with fine accuracy. This reconstructability neither depends strongly on the size nor the placement of the local cross section if we have a sufficiently long database. We demonstrate the proposed method using the Lorenz model as well as the actual measurement of wind speed.

Dimensionless embedding for nonlinear time series analysis

Recently, infinite-dimensional delay coordinates (InDDeCs) have been proposed for predicting high-dimensional dynamics instead of conventional delay coordinates. Although InDDeCs can realize faster computation and more accurate short-term prediction, it is still not well-known whether InDDeCs can be used in other applications of nonlinear time series analysis in which reconstruction is needed for the underlying dynamics from a scalar time series generated from a dynamical system. Here, we give theoretical support for justifying the use of InDDeCs and provide numerical examples to show that InDDeCs can be used for various applications for obtaining the recurrence plots, correlation dimensions, and maximal Lyapunov exponents, as well as testing directional couplings and extracting slow-driving forces. We demonstrate performance of the InDDeCs using the weather data. Thus, InDDeCs can eventually realize "dimensionless embedding" while we enjoy faster and more reliable computations.

On the limits of probabilistic forecasting in nonlinear time series analysis II: Differential entropy

In a previous paper, the authors studied the limits of probabilistic prediction in nonlinear time series analysis in a perfect model scenario, i.e., in the ideal case that the uncertainty of an otherwise deterministic model is due to only the finite precision of the observations. The model consisted of the symbolic dynamics of a measure-preserving transformation with respect to a finite partition of the state space, and the quality of the predictions was measured by the so-called ignorance score, which is a conditional entropy. In practice, though, partitions are dispensed with by considering numerical and experimental data to be continuous, which prompts us to trade off in this paper the Shannon entropy for the differential entropy. Despite technical differences, we show that the core of the previous results also hold in this extended scenario for sufficiently high precision. The corresponding imperfect model scenario will be revisited too because it is relevant for the applications. The theoretical part and its application to probabilistic forecasting are illustrated with numerical simulations and a new prediction algorithm.

Quantifying the Dynamical Complexity of Chaotic Time Series

A powerful approach is proposed for the characterization of chaotic signals. It is based on the combined use of two classes of indicators: (i) the probability of suitable symbolic sequences (obtained from the ordinal patterns of the corresponding time series); (ii) the width of the corresponding cylinder sets. This way, much information can be extracted and used to quantify the complexity of a given signal. As an example of the potentiality of the method, I introduce a modified permutation entropy which allows for quantitative estimates of the Kolmogorov-Sinai entropy in hyperchaotic models, where other methods would be unpractical. As a by-product, estimates of the fractal dimension of the underlying attractors are possible as well.

Symbolic dynamics-based error analysis on chaos synchronization via noisy channels

In this study, symbolic dynamics is used to research the error of chaos synchronization via noisy channels. The theory of symbolic dynamics reduces chaos to a shift map that acts on a discrete set of symbols, each of which contains information about the system state. Using this transformation, a coder-decoder scheme is proposed. A model for the relationship among word length, region number of a partition, and synchronization error is provided. According to the model, the fundamental trade-off between word length and region number can be optimized to minimize the synchronization error. Numerical simulations provide support for our results.

A complex systems analysis of stick-slip dynamics of a laboratory fault

We study the stick-slip behavior of a granular bed of photoelastic disks sheared by a rough slider pulled along the surface. Time series of a proxy for granular friction are examined using complex systems methods to characterize the observed stick-slip dynamics of this laboratory fault. Nonlinear surrogate time series methods show that the stick-slip behavior appears more complex than a periodic dynamics description. Phase space embedding methods show that the dynamics can be locally captured within a four to six dimensional subspace. These slider time series also provide an experimental test for recent complex network methods. Phase space networks, constructed by connecting nearby phase space points, proved useful in capturing the key features of the dynamics. In particular, network communities could be associated to slip events and the ranking of small network subgraphs exhibited a heretofore unreported ordering.

Self-organized topology of recurrence-based complex networks

With the rapid technological advancement, network is almost everywhere in our daily life. Network theory leads to a new way to investigate the dynamics of complex systems. As a result, many methods are proposed to construct a network from nonlinear time series, including the partition of state space, visibility graph, nearest neighbors, and recurrence approaches. However, most previous works focus on deriving the adjacency matrix to represent the complex network and extract new network-theoretic measures. Although the adjacency matrix provides connectivity information of nodes and edges, the network geometry can take variable forms. The research objective of this article is to develop a self-organizing approach to derive the steady geometric structure of a network from the adjacency matrix. We simulate the recurrence network as a physical system by treating the edges as springs and the nodes as electrically charged particles. Then, force-directed algorithms are developed to automatically organize the network geometry by minimizing the system energy. Further, a set of experiments were designed to investigate important factors (i.e., dynamical systems, network construction methods, force-model parameter, nonhomogeneous distribution) affecting this self-organizing process. Interestingly, experimental results show that the self-organized geometry recovers the attractor of a dynamical system that produced the adjacency matrix. This research addresses a question, i.e., "what is the self-organizing geometry of a recurrence network?" and provides a new way to reproduce the attractor or time series from the recurrence plot. As a result, novel network-theoretic measures (e.g., average path length and proximity ratio) can be achieved based on actual node-to-node distances in the self-organized network topology. The paper brings the physical models into the recurrence analysis and discloses the spatial geometry of recurrence networks.

Application of joint permutations for predicting coupled time series

In this work, we introduce a model for predicting multivariate time series data. This model was obtained by partitioning the state space with joint permutations. We review the theoretical framework of the previous works, show a simple extension to multivariate data, and compare its performance to the previous model obtained by permutations for predicting scalar time series data.

Chaos in neurons and its application: perspective of chaos engineering

We review our recent work on chaos in neurons and its application to neural networks from perspective of chaos engineering. Especially, we analyze a dataset of a squid giant axon by newly combining our previous work of identifying Devaney's chaos with surrogate data analysis, and show that an axon can behave chaotically. Based on this knowledge, we use a chaotic neuron model to investigate possible information processing in the brain.

Describing high-dimensional dynamics with low-dimensional piecewise affine models: applications to renewable energy

We introduce a low-dimensional description for a high-dimensional system, which is a piecewise affine model whose state space is divided by permutations. We show that the proposed model tends to predict wind speeds and photovoltaic outputs for the time scales from seconds to 100 s better than by global affine models. In addition, computations using the piecewise affine model are much faster than those of usual nonlinear models such as radial basis function models.

Unstable periodic orbits and noise in chaos computing

Different methods to utilize the rich library of patterns and behaviors of a chaotic system have been proposed for doing computation or communication. Since a chaotic system is intrinsically unstable and its nearby orbits diverge exponentially from each other, special attention needs to be paid to the robustness against noise of chaos-based approaches to computation. In this paper unstable periodic orbits, which form the skeleton of any chaotic system, are employed to build a model for the chaotic system to measure the sensitivity of each orbit to noise, and to select the orbits whose symbolic representations are relatively robust against the existence of noise. Furthermore, since unstable periodic orbits are extractable from time series, periodic orbit-based models can be extracted from time series too. Chaos computing can be and has been implemented on different platforms, including biological systems. In biology noise is always present; as a result having a clear model for the effects of noise on any given biological implementation has profound importance. Also, since in biology it is hard to obtain exact dynamical equations of the system under study, the time series techniques we introduce here are of critical importance.

Communication patterns in a psychotherapy following traumatic brain injury: a quantitative case study based on symbolic dynamics

BACKGROUND

The role of psychotherapy in the treatment of traumatic brain injury is receiving increased attention. The evaluation of psychotherapy with these patients has been conducted largely in the absence of quantitative data concerning the therapy itself. Quantitative methods for characterizing the sequence-sensitive structure of patient-therapist communication are now being developed with the objective of improving the effectiveness of psychotherapy following traumatic brain injury.

METHODS

The content of three therapy session transcripts (sessions were separated by four months) obtained from a patient with a history of several motor vehicle accidents who was receiving dialectical behavior therapy was scored and analyzed using methods derived from the mathematical theory of symbolic dynamics.

RESULTS

The analysis of symbol frequencies was largely uninformative. When repeated triples were examined a marked pattern of change in content was observed over the three sessions. The context free grammar complexity and the Lempel-Ziv complexity were calculated for each therapy session. For both measures, the rate of complexity generation, expressed as bits per minute, increased longitudinally during the course of therapy. The between-session increases in complexity generation rates are consistent with calculations of mutual information. Taken together these results indicate that there was a quantifiable increase in the variability of patient-therapist verbal behavior during the course of therapy. Comparison of complexity values against values obtained from equiprobable random surrogates established the presence of a nonrandom structure in patient-therapist dialog (P = .002).

CONCLUSIONS

While recognizing that only limited conclusions can be based on a case history, it can be noted that these quantitative observations are consistent with qualitative clinical observations of increases in the flexibility of discourse during therapy. These procedures can be of particular value in the examination of therapies following traumatic brain injury because, in some presentations, these therapies are complicated by deficits that result in subtle distortions of language that produce significant post-injury social impairment. Independently of the mathematical analysis applied to the investigation of therapy-generated symbol sequences, our experience suggests that the procedures presented here are of value in training therapists.

The least channel capacity for chaos synchronization

Recently researchers have found that a channel with capacity exceeding the Kolmogorov-Sinai entropy of the drive system (h(KS)) is theoretically necessary and sufficient to sustain the unidirectional synchronization to arbitrarily high precision. In this study, we use symbolic dynamics and the automaton reset sequence to distinguish the information that is required in identifying the current drive word and obtaining the synchronization. Then, we show that the least channel capacity that is sufficient to transmit the distinguished information and attain the synchronization of arbitrarily high precision is h(KS). Numerical simulations provide support for our conclusions.

Chaos synchronization basing on symbolic dynamics with nongenerating partition

Using symbolic dynamics and information theory, we study the information transmission needed for synchronizing unidirectionally coupled oscillators. It is found that when sustaining chaos synchronization with nongenerating partition, the synchronization error will be larger than a critical value, although the required coupled channel capacity can be smaller than the case of using a generating partition. Then we show that no matter whether a generating or nongenerating partition is in use, a high-quality detector can guarantee the lead of the response oscillator, while the lag responding can make up the low precision of the detector. A practicable synchronization scheme basing on a nongenerating partition is also proposed in this paper.

Optimal instruments and models for noisy chaos

Analysis of finite, noisy time series data leads to modern statistical inference methods. Here we adapt Bayesian inference for applied symbolic dynamics. We show that reconciling Kolmogorov's maximum-entropy partition with the methods of Bayesian model selection requires the use of two separate optimizations. First, instrument design produces a maximum-entropy symbolic representation of time series data. Second, Bayesian model comparison with a uniform prior selects a minimum-entropy model, with respect to the considered Markov chain orders, of the symbolic data. We illustrate these steps using a binary partition of time series data from the logistic and Henon maps as well as the Rössler and Lorenz attractors with dynamical noise. In each case we demonstrate the inference of effectively generating partitions and kth-order Markov chain models.

Globally enumerating unstable periodic orbits for observed data using symbolic dynamics

The unstable periodic orbits of a chaotic system provide an important skeleton of the dynamics in a chaotic system, but they can be difficult to find from an observed time series. We present a global method for finding periodic orbits based on their symbolic dynamics, which is made possible by several recent methods to find good partitions for symbolic dynamics from observed time series. The symbolic dynamics are approximated by a Markov chain estimated from the sequence using information-theoretical concepts. The chain has a probabilistic graph representation, and the cycles of the graph may be exhaustively enumerated with a classical deterministic algorithm, providing a global, comprehensive list of symbolic names for its periodic orbits. Once the symbolic codes of the periodic orbits are found, the partition is used to localize the orbits back in the original state space. Using the periodic orbits found, we can estimate several quantities of the attractor such as the Lyapunov exponent and topological entropy.

Embeddings of low-dimensional strange attractors: topological invariants and degrees of freedom

When a low-dimensional chaotic attractor is embedded in a three-dimensional space its topological properties are embedding-dependent. We show that there are just three topological properties that depend on the embedding: Parity, global torsion, and knot type. We discuss how they can change with the embedding. Finally, we show that the mechanism that is responsible for creating chaotic behavior is an invariant of all embeddings. These results apply only to chaotic attractors of genus one, which covers the majority of cases in which experimental data have been subjected to topological analysis. This means that the conclusions drawn from previous analyses, for example that the mechanism generating chaotic behavior is a Smale horseshoe mechanism, a reverse horseshoe, a gateau roulé, an S -template branched manifold, etc., are not artifacts of the embedding chosen for the analysis.

Failure of maximum likelihood methods for chaotic dynamical systems

The maximum likelihood method is a basic statistical technique for estimating parameters and variables, and is the starting point for many more sophisticated methods, like Bayesian methods. This paper shows that maximum likelihood fails to identify the true trajectory of a chaotic dynamical system, because there are trajectories that appear to be far more (infinitely more) likely than truth. This failure occurs for unbounded noise and for bounded noise when it is sufficiently large and will almost certainly have consequences for parameter estimation in such systems. The reason for the failure is rather simple; in chaotic dynamical systems there can be trajectories that are consistently closer to the observations than the true trajectory being observed, and hence their likelihood dominates truth. The residuals of these truth-dominating trajectories are not consistent with the noise distribution; they would typically have too small standard deviation and many outliers, and hence the situation may be remedied by using methods that examine the distribution of residuals and are not entirely maximum likelihood based.

On parameter estimation of chaotic systems via symbolic time-series analysis

Symbolic time-series analysis is used for estimating the parameters of chaotic systems. It is assumed that a "target model" (i.e., a discrete- or continuous-time description of the data-generating mechanism) is available, but with unknown parameters. A time series, i.e., a noisy, finite sequence of a measured (output) variable, is given. The proposed method first prescribes to symbolize the time series, i.e., to transform it into a sequence of symbols, from which the statistics of symbols are readily derived. Then, a symbolic model (in the form of a Markov chain) is derived from the data. It allows one to predict, in a probabilistic fashion, the time evolution of the symbol sequence. The unknown parameters are derived by matching either the statistics of symbols, or the symbolic prediction derived from data, with those generated by the (parametrized) target model. Three examples of application (the Henon map, a population model, and the Duffing system) prove that satisfactory results can be obtained even with short time series.

Constructing dynamical systems with specified symbolic dynamics

In this paper we demonstrate how to construct signals (time series) of continuous-time dynamical systems that exhibit a given symbolic dynamics. This is achieved without construction of the ordinary differential equations that generate the flow. This construction is of theoretical interest and is useful as a source of dynamical data that can be used to test various data analysis algorithms.

Statistically relaxing to generating partitions for observed time-series data

We introduce a relaxation algorithm to estimate approximations to generating partitions for observed dynamical time series. Generating partitions preserve dynamical information of a deterministic map in the symbolic representation. Our method optimizes an essential property of a generating partition: avoiding topological degeneracies. We construct an energy-like functional and use a nonequilibrium stochastic minimization algorithm to search through configuration space for the best assignment of symbols to observed data. As each observed point may be assigned a symbol, the partitions are not constrained to an arbitrary parametrization. We further show how to select particular generating partition solutions which also code low-order unstable periodic orbits in a given way, hence being able to enumerate through a number of potential generating partition solutions.